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

2
votes
1answer
254 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
278 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
665 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
719 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
323 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
475 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
906 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
282 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
413 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
273 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
621 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
584 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
379 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
323 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 ...