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

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

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/alternative_metrics/insertion_deletion/insertion_deletion.yml.