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

Levenshtein codes meet the Plotkin bound \(K\leq 2\left\lfloor\frac{d}{2d-n}\right\rfloor\), where \(K\) is the number of codewords, \(d\) is the distance, and \(n\) is the length, and with the assumption that the Hadamard matrices for such parameters exist. The general proof depends on the correctness of Hadamard''s conjecture [2].

Parent

Zoo code information

Internal code ID: levenshtein

Your contribution is welcome!

on github.com (edit & pull request)

edit on this site

Zoo Code ID: levenshtein

Cite as:
“Levenshtein code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/levenshtein
BibTeX:
@incollection{eczoo_levenshtein, title={Levenshtein code}, booktitle={The Error Correction Zoo}, year={2022}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/levenshtein} }
Permanent link:
https://errorcorrectionzoo.org/c/levenshtein

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.