Editing code

Editing code[1]

Also known as Insertion and deletion code.

Description

A code designed to protect against insertions, where a new symbol is added somewhere within the string, and deletions, where a symbol at an unknown location is erased.

Protection

The metric measuring distance of an error word to the nearest codeword is the Levenshtein's deletion distance: given vectors \(u,v\), this distance is one-half the smallest number of deletions and insertions needed to change \(u\) to \(v\). A code \(C\) corrects \(e\) deletions if all codewords are separated by at least \(e+1\) in the deletion distance [2]. Similar distances, collectively called editing distances, can be defined for insertions and related operations [3; Sec. 22.7].

Notes

See Refs. [4,5][3; Sec. 22.7] for more details.

Parent

Galois-field \(q\)-ary code

Children

Varshamov-Tenengolts (VT) code
DNA storage code — DNA codes can typically handle base-pair insertions and deletions.

Cousins

Permutation-invariant (PI) code — PI codes of distance \(d\) can protect against \(d-1\) (quantum) deletion errors.
Combinatorial design — Perfect deletion correcting codes can be constructed using combinatorial design theory [6,7].
Perfect code — Perfect deletion correcting codes can be constructed using combinatorial design theory [6,7].

References

[1]: Levenshtein, Vladimir I. "Binary codes capable of correcting deletions, insertions, and reversals." Soviet physics doklady. Vol. 10. No. 8. 1966.
[2]: N. J. A. Sloane, “On Single-Deletion-Correcting Codes”, (2002) arXiv:math/0207197
[3]: M. Firer, "Alternative Metrics." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
[4]: K. Tatwawadi and S. Chandak, “Tutorial on algebraic deletion correction codes”, (2019) arXiv:1906.07887
[5]: B. Haeupler and A. Shahrasbi, “Synchronization Strings and Codes for Insertions and Deletions—A Survey”, IEEE Transactions on Information Theory 67, 3190 (2021) DOI
[6]: P. A. H. Bours, “On the construction of perfect deletion-correcting codes using design theory”, Designs, Codes and Cryptography 6, 5 (1995) DOI
[7]: A. Mahmoodi, Designs, Codes and Cryptography 14, 81 (1998) DOI

Page edit log

Fengxing Zhu (2024-03-16) — most recent
Victor V. Albert (2024-03-16)

Cite as:

“Editing code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2024. https://errorcorrectionzoo.org/c/insertion_deletion

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/q-ary_digits/insertion_deletion/insertion_deletion.yml.