2
$\begingroup$

Everything over F_2.

For any matrix $A$ define the number $N(A) = min_{x}$ HammingWeight $( [x , Ax])$. Where $x$ is vector and [a,b] is just concatenation of vectors: (a_1,...a_n, b_1,...,b_m).

Question What is $max_{A \in Mat(n,m) } (N(A))$ ?

Particular case n=m.


Motivation.

The map $x \to [x, Ax] $ can be considered as error-correcting coding, $x$ - information bits, $Ax$ are redundancy bits.

The code is good if distance between codewords is small.

Reformulation of question: what is the "best possible" code of type above ? ("best possible" in the sense of minimal distance -- it is not always "best" from practical point of view nevertheless).

$\endgroup$
4
  • $\begingroup$ You want to know the best error-correcting rate of a binary code of information rate 1/2. I am sure this is an open problem. $\endgroup$ Jul 6, 2012 at 11:42
  • $\begingroup$ @Felipe What is known about this ? Estimates ? References ? What are simple estimates which one can understand how to derive without much sufferings ? $\endgroup$ Jul 6, 2012 at 11:46
  • $\begingroup$ Varshamov-Gilbert gives a lower bound and Elias gives an upper bound. This is already in MacWilliams and Sloane. I don't think there has been any improvement (certainly not substantial ones). $\endgroup$ Jul 6, 2012 at 14:02
  • $\begingroup$ @quid I think in later posts I use correct tag, if think it is worth please re-tag $\endgroup$ Feb 10, 2013 at 17:11

1 Answer 1

5
$\begingroup$

This is, indeed, an open question for most values of $n$. A.D. Brouwer maintains a database of the best known lower and upper bounds, and everything that is known for small $n$ can be found there. A minute of googling points me at

http://mint.sbg.ac.at/desc_CBrouwerTable-Bound.html

Asymptotically the best bound is usually the linear programming bound due to McEliece-Rodemich-Rumsey and Welch, but the asymptotic bounds may not be very good for rate 1/2 codes.

An interesting simple general existence proof is described in van Lint's book (Springer GTM series). Fix a basis for $F=GF(2^n)$. Treat $x$ as an element of $F$, and use encoding $x\mapsto (x,ax)$, where $a$ is an element of $F$ that we choose carefully. Fix a target minimum distance. Let $S(i)$ be the set of elements of $F$ of weight $i$, so $|S(i)|={n\choose i}.$ We must disallow all those elements $a$ that can be written in the form $a=y/x$, where $x\in S(i), y\in S(j), i+j\lt d$. The number of disallowed elements $a$ is thus at most $$ N(d)=\sum_{0\lt i,j\lt d; i+j\lt d}{n\choose i}{n\choose j}. $$ If $N(d)\lt 2^n$ we have not disallowed all the elements of $F$, so the construction succeeds.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.