Levenshtein code[1]

Description

Binary codes constructed from combining two codes \(A'\) constructed out of Hadamard matrices.

Let \(H_n\) be a normalized Hadamard matrix. The generator matrix for an \((n-1,n,n/2)\) code \(A_n\) is obtained by taking \(H_n\), replacing the +1's by 0's and the -1's by 1's, and deleting the first column. Taking only the codewords of \(A_n\) which begin with 0 and deleting the leading 0 yields the generator matrix of an \((n-2,n/2,n/2)\) code \(A_n'\).

Next, apply the following way of combining codes. Suppose we have an \((n_1,M_1,d_1)\) code \(C_1\) and an \((n_2,M_2,d_2)\) code \(C_2\). The combined \((an_1+bn_2,\min(M_1,M_2),ad_1+bd_2)\) code \(a C_1\bigoplus b C_2\) may be constructed by pasting \(a\) copies of \(C_1\) and \(b\) copies of \(C_2\) together and omitting the last \(|M_1-M_2|\) rows. Applying this to construct a Levenshtein code with length \(n\) and distance \(d\), define \(k=\lfloor d/(2d-n)\rfloor\), \(a=d(2k+1)-n(k+1)\), and \(b=kn-d(2k-1)\). If \(n\) is even, construct \(\frac{a}{2}A_{4k}'\bigoplus\frac{b}{2}A_{4k+4}'\). If \(n\) is odd and \(k\) is even, construct \(aA_{2k}\bigoplus\frac{b}{2}A_{4k+4}'\). If \(n\) is odd and \(k\) is odd, construct \(\frac{a}{2}A_{4k}'\bigoplus b A_{2k+2}\).