On multiple insertion/deletion correcting codes

Author

Helberg, Albertus S J ; Ferreira, Hendrik C.

Author_Institution

Sch. for Electr. & Electron. Eng., Potchefstroom Univ. for CHE, South Africa

Volume

48

Issue

1

fYear

2002

fDate

1/1/2002 12:00:00 AM

Firstpage

305

Lastpage

308

Abstract

We investigate binary, number-theoretic, bit insertion/deletion correcting codes as pioneered by Levenshtein (1965, 1966, 1989). The weight spectra and Hamming distance properties of single insertion/deletion error-correcting codes are analyzed. These relationships are then extended to investigate codes that can correct multiple random insertions and deletions. From these relationships, new bounds are derived and a general construction for multiple insertion/deletion correcting codes is proposed and evaluated

Keywords

binary codes; error correction codes; number theory; Hamming distance; Levenshtein code; binary codes; bit insertion/deletion correcting codes; cardinality; multiple insertion/deletion correcting codes; multiple random deletions; multiple random insertions; number-theoretic codes; single insertion/deletion error-correcting codes; upper bound; weight spectra; Additives; Africa; Binary codes; Binary sequences; Decoding; Error analysis; Error correction codes; Forward error correction; Hamming distance; Information theory;

fLanguage

English

Journal_Title

Information Theory, IEEE Transactions on

Publisher

ieee

ISSN

0018-9448

Type

jour

DOI

10.1109/18.971760

Filename

971760