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

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

Your contribution is welcome!

on github.com (edit & pull request)— see instructions

edit on this site

Zoo Code ID: insertion_deletion

Cite as:
“Editing code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2024. https://errorcorrectionzoo.org/c/insertion_deletion
BibTeX:
@incollection{eczoo_insertion_deletion, title={Editing code}, booktitle={The Error Correction Zoo}, year={2024}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/insertion_deletion} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/insertion_deletion

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.