The theory of error-correcting codes stems from Shannon's 1948 _A mathematical theory of communication_, and from Hamming's 1950 "Error detecting and error correcting codes".

learn more… | top users | synonyms

0
votes
0answers
105 views

A search for optimal order ideals

At the behest of Gerhard Paseman I'll describe the problem that I alluded to in name for a partial order. Let $M = M(\infty)$ denote the set of all finite subsets of the positive integers ...
0
votes
1answer
263 views

Optimization problem related to parity check code

I have n data blocks and k parity blocks distributed across m boxes. Each parity block is Ex-or of some data block (for ease of understanding we can assume each data/parity block as a single bit) and ...
2
votes
1answer
307 views

Lee codes and $n$-torus

This is in continuation with this post: Geometric/Analytic techniques for constructive and asymptotic bounds in the Lee metric Codes over alphabet $\mathbb{Z}_{q}$ of length $n$ for the Lee metric ...
1
vote
0answers
212 views

Geometric/Analytic techniques for constructive and asymptotic bounds in the Lee metric

Slight extension of cross posting from http://cstheory.stackexchange.com/questions/7408/lee-metric-gilbert-varshamov-and-hamming-bounds-for-larger-relative-distance-rang (closed there) The following ...
20
votes
2answers
1k views

What is the complexity of this problem?

Recently on Dick Lipton and Ken Regan's blog there was a post about problems of intermediate complexity, that is, NP problems that are harder than P but easier than NP-complete. The main message of ...
2
votes
1answer
255 views

Doing column permutation under row overlap constraint

In coding theory, there are parity-check codes whose parity-check matrices $H$ are generated via column permutations. For instance, the binary LDPC codes constructed in Gallager's 1962 IRE Trans paper ...
4
votes
1answer
290 views

Probability of false decoding with LDPC codes

It is well known that given a binary linear code $C$ under maximum likelihood decoding the probability of false decoding $P_C$ in a Binary Symmetric Channel with cross over probability $p$, in other ...
6
votes
5answers
691 views

covering by spherical caps

Consider the unit sphere $\mathbb{S}^d.$ Pick now some $\alpha$ (I am thinking of $\alpha \ll 1,$ but I don't know how germane this is). The question is: how many spherical caps of angular radius ...
15
votes
1answer
728 views

Codes, lattices, vertex operator algebras

At the end of "Notes on Chapter 1" in the Preface to the Third Edition of Sphere packings, lattices and groups, Conway and Sloane write the following: Finally, we cannot resist calling attention ...
0
votes
1answer
325 views

Fixed Hamming distance property of binary deletion correcting codes

Let $x=(x_1x_2...x_n)$ be a binary sequence of length $n$. The Varshamov-Tenengolts code $VT_0(n)$ consists of all binary vectors $(x_1, . . . , x_n)$ satisfying $\Sigma_{i=1}^n i*x_i \equiv0 \pmod ...
2
votes
1answer
476 views

Even lattices and binary codes

I have a maybe simple question about even positive-definite lattices and lattices coming from binary codes. They seemed to be used in framed vertex operator algebras. What is known about even ...
14
votes
1answer
930 views

How to keep subsets disjoint?

Given positive integers $n$ and $k\le 2^n$, how to choose a subset $C\subset\{0,1\}^n$ of size $|C|=k$ to maximize the number of pairs $(c_1,c_2)\in C\times C$ with the supports of $c_1$ and $c_2$ ...
1
vote
1answer
283 views

Large subgroups of the Hamming cube

Let's consider the abelian group $\mathbb{Z}^N_2$ equipped with the Hamming metric (the hypercube). Suppose I have a subgroup of this hypercube (not necessarily a subcube) which is generated by a set ...
7
votes
4answers
1k views

“sparse graphs are locally tree-like”

I would like to be able to state with confidence that sparse graphs (graphs with small numbers of edges) are locally tree-like (they have few short cycles). Apparently "Sparse graphs are locally tree ...
1
vote
1answer
415 views

Matrix version of Berlekamp Massey algorithm

What are the most obvious generalizations of Berlekamp Massey algorithm [1] to matrix sequences? [1] Massey, J. L., "Shift-register synthesis and BCH decoding", IEEE Trans. Information Theory ...
2
votes
1answer
275 views

Optimal binary code for points in a metric+probability space

Does anyone know of any results on this topic? Basically I'm considering this problem. You have some space $X$ from which you can draw points $x$ and $y$, a distance metric $d(x,y)$, and a ...
4
votes
4answers
622 views

how to find vector $(\pm 1, \pm 1, \pm 1, … \pm 1)$ which is most close to given vector (r_1,…r_l) ? Is it NP-problem ? What algorithms are available ?

Given: some vector $R=(r_1...r_l)$ - real numbers, and a set of distinct vectors with $+1$ or $-1$ coordinates $$\begin{array}{c} V_1=(c_{1,1} ... c_{1,l}),\\\ V_2=(c_{2,1} ... c_{2,l}),\\\ ...
10
votes
3answers
585 views

MacWilliams Identity for Asymptotic Weight Spectrum of a Code

Introduction Let $C$ be a code of block length $n$ having $A_i^C$ words of Hamming weight $i$, for $i\in [n]$, where $[n]:=\{0,\ldots,n\}$. Then, the sequence $\{ A_i^C \}_{i \in [n]} $ is called the ...
4
votes
2answers
390 views

A Boolean function that is not constant on affine subspaces of large enough dimension

I'm interested in an explicit Boolean function $f \colon \{0,1\}^n \rightarrow \{0,1\}$ with the following property: if $f$ is constant on some affine subspace of $\{0,1\}^n$, then the dimension of ...
7
votes
1answer
2k views

12 balls weighing puzzle

In an article describing the twelve balls weighing problem, the author mentions a solution that involves the finite projective plane of order 3, discovered by Rick Wilson. Does anyone know what this ...
1
vote
1answer
325 views

Algorithm for generating a size k error-correcting code on n bits

I want to generate a code on n bits for k different inputs that I want to classify. The main requirement of this code is the error-correcting criteria: that the minimum pairwise distance between any ...
5
votes
2answers
545 views

Binary codes with large distance

Suppose $C \subset \lbrace 0,1\rbrace^{n}$ is a binary code with distance $\delta * n$, for $1/2 < \delta < 1$. Can $|C|$ be arbitrarily large (if I allow n to be arbitrarily large)? Note that ...