# What is matrix A such that Hamming weight of [x, Ax] is maximal ? (Min distance of 1/2 block code?)

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

-
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

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