Binary Linear Codes of Minimum Distance 3

Question

Let $B_n$ denote the maximum size of a binary linear code (a binary code that is closed under addition) whose codewords have length $n$ and whose minimum distance is $3$. I have been searching for the best-known lower bounds for $A(n,3)$, but I can't seem to find anything. My question is simply: What are some lower bounds for the numbers $B_n$?

Answer 1

The binary Hamming code with parameters $[n,k,d]=[2^m-1,2^m-m-1,3]$ is perfect (no larger code exists) and for the values of $n=2^m-1,$ $m\geq 3$ provides the lower bound $$A_{2^m-1}\geq 2^{(2^m-m-1)}$$.

So $A_7\geq 16,$ etc.

The Gilbert-Varshamov bound states that for alphabet size $q$ a prime power, there exists a linear $[n,k]$ code with minimum distance at least $d$ provided $$q^{n-k}\geq \sum_{i=0}^{d-2} {n-1 \choose i} (q-1)^i.$$ So you can take $q=2$ and find the largest $k$ satisfying this inequality.

There is a table in Roman's Coding Theory book, which has the following information (but for all, not necessarily linear codes). $$ \begin{array}{cl} n & A(n,d) \\ 5 & 4\\ 6& 8 \\ 7 & 16\\ 8 & 20\\ 9 & 40 \\ 10 & 72-79 \\ \cdots & \cdots \\ 16 & 2560-3276 \end{array}$$

Answer 2

Because you specify the minimum distance to $d=3$ and constrain yourself to binary linear codes, the question can be answered explicitly.

Let the code $C$ be given by a check matrix $$ H=(H_1\ |\ H_2\ |\ H_3\ |\ \cdots\ H_n), $$ where the columns $H_i, 1\le i\le n$, are binary vectors of with $m$ components. For the code to have minimum distance $\ge3$ it is necessary and sufficient that all the columns $H_i$ are non-zero and distinct, i.e. $H_i\neq H_j$ whenever $i\neq j$. This is easy to understand. If $H_i=0$ for some $i$, then the word of weight one with its unique non-zero component will be a codeword. Similarly the existence of a word of weight two in $C$ is equivalent to finding two linearly dependent columns from $H$ (the non-zero components are located at the positions of the dependent columns). Over the binary field a set of two vectors is linearly dependent, iff the two vectors are equal.

Because the columns have exactly $m$ bits, the maximum number of non-zero distinct column vectors is $2^m-1$. This leads to the following answer:

Given the code length $n$, find the unique positive integer $m$ such that $$2^{m-1}\le n\le 2^m-1.$$ The maximum dimension of a binary linear code of length $n$ and $d_{min}=3$ is then $k=n-m.$ The above recipe allows us to easily also construct a check matrix $H$ with required properties, and hence also a code. The number of words in such a linear code is $$B_n=2^k=2^{n-\lfloor \log_2(n+1)\rfloor}.$$