# 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][3; Sec. 22.7] for more details.

## Parent

## Children

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

## 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]
- B. Haeupler and A. Shahrasbi, “Synchronization Strings and Codes for Insertions and Deletions—A Survey”, IEEE Transactions on Information Theory 67, 3190 (2021) 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