Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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).

share|improve this question
    
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. –  Felipe Voloch Jul 6 '12 at 11:42
    
@Felipe What is known about this ? Estimates ? References ? What are simple estimates which one can understand how to derive without much sufferings ? –  Alexander Chervov Jul 6 '12 at 11:46
    
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). –  Felipe Voloch Jul 6 '12 at 14:02
    
@quid I think in later posts I use correct tag, if think it is worth please re-tag –  Alexander Chervov Feb 10 '13 at 17:11

1 Answer 1

up vote 5 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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