Explicit formulas for the weight enumerators of some classes of deletion correcting codes

Khodakhast Bibak, Olgica Milenkovic

Research output: Contribution to journalArticlepeer-review

Abstract

We introduce a general class of codes which includes several well-known classes of deletion/insertion correcting codes as special cases. For example, the Helberg code, the Levenshtein code, the Varshamov-Tenengolts code, and most variants of these codes including most of those which have been recently used in studying DNA-based data storage systems are all special cases of our code. Then, using a number theoretic method, we give an explicit formula for the weight enumerator of our code which in turn gives explicit formulas for the weight enumerators and for the sizes of all the aforementioned codes. We also obtain the size of the shifted Varshamov-Tenengolts code. Another application which automatically follows from our result is an explicit formula for the number of binary solutions of an arbitrary linear congruence which, to the best of our knowledge, is the first result of its kind in the literature and might be also of independent interest. Our general result might have more applications/implications in information theory, computer science, and mathematics.

Original languageEnglish (US)
Article number8573841
Pages (from-to)1809-1816
Number of pages8
JournalIEEE Transactions on Communications
Volume67
Issue number3
DOIs
StatePublished - Mar 2019

Keywords

  • BLCC
  • Binary solution
  • deletion correcting code
  • linear congruence
  • weight enumerator

ASJC Scopus subject areas

  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Explicit formulas for the weight enumerators of some classes of deletion correcting codes'. Together they form a unique fingerprint.

Cite this