Explicit Formulas for the Weight Enumerators of Some Classes of Deletion Correcting Codes

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 so 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.

arXiv commentIEEE Transactions on Communications, 2019

References in corpus (8)

• On Single-Deletion-Correcting Codes
• Ramanujan sums analysis of long-period sequences and 1/f noise
• Low-Complexity Interactive Algorithms for Synchronization from Deletions, Insertions, and Substitutions
• Restricted linear congruences
• Counting surface-kernel epimorphisms from a co-compact Fuchsian group to a cyclic group with motivations from string theory and QFT
• MMH* with arbitrary modulus is always almost-universal
• On an almost-universal hash function family with applications to authentication and secrecy codes
• Unweighted linear congruences with distinct coordinates and the Varshamov--Tenengolts codes