# 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

## 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