Abstract
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 Z4 -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.
| Original language | English |
|---|---|
| Pages (from-to) | 1595-1603 |
| Number of pages | 9 |
| Journal | IEEE Transactions on Information Theory |
| Volume | 64 |
| Issue number | 3 |
| DOIs | |
| Publication status | Published - 1 Mar 2018 |
| Externally published | Yes |
Keywords
- Deletion and repetition codes
- Lee metric
- construction A
- lattice
- v-series
- weight enumerator