# 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}\).

## Protection

## Parent

## Zoo code information

## References

- [1]
- V.I. Levenshtein, Application of Hadamard matrices to a problem in coding theory, Problems of Cybernetics, vol. 5, GIFML, Moscow, 1961, 125–136.
- [2]
- F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977

## Cite as:

“Levenshtein code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/levenshtein

Github: https://github.com/errorcorrectionzoo/eczoo_data/tree/main/codes/classical/bits/levenshtein.yml.