Lattice Codes for Deletion and Repetition Channels

• Published in: IEEE transactions on information theory 2018-03, Vol.64 (3), p.1595-1603
• Main Authors: Sok, Lin, Belfiore, Jean-Claude, Sole, Patrick, Tchamkerten, Aslan
• Format: Article
• Language: English
• Subjects: <italic xmlns:ali="http://www.niso.org/schemas/ali/1.0/" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance">ν -series; Binary codes; Codes; construction <italic xmlns:ali="http://www.niso.org/schemas/ali/1.0/" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance">A; Decoding; Deletion; Deletion and repetition codes; Encoding; Integers; lattice; Lattices; Lee metric; Lower bounds; Measurement; weight enumerator; Zinc
• ISSN: 0018-9448; 1557-9654
• DOI: 10.1109/TIT.2018.2791990

The construction of deletion codes for the editing metric is reduced to the construction of codes over the integers for the Manhattan metric by run length coding. The latter codes are constructed by expurgation of lattices' translates. These lattices, in turn, are obtained from Construction A applied to binary codes and \mathbb {Z}_{4} -codes. A lower bound on the size of our codes for the Manhattan distance are obtained through generalized theta series of the corresponding lattices. For any fixed number of deletions, provided the number of runs is large enough our method supplies a correction technique. For fixed number of runs and binary sequence length large our lattice construction is shown to be tight up to constants.