Gilbert-Varshamov Bound for Codes in $L_1$ Metric using Multivariate Analytic Combinatorics

Abstract

Analytic combinatorics in several variables refers to a suite of tools that provide sharp asymptotic estimates for certain combinatorial quantities. In this paper, we apply these tools to determine the Gilbert--Varshamov lower bound on the rate of optimal codes in $L_1$ metric. Several different code spaces are analyzed, including the simplex and the hypercube in ${\mathbb{Z}}^n$, all of which are inspired by concrete data storage and transmission models such as the sticky insertion channel, the permutation channel, the adjacent transposition (bit-shift) channel, the multilevel flash memory channel, etc.

33 pages, 3 figures, submitted to IEEE Transactions on Information Theory

References in corpus (6)

• Codes in the Space of Multisets---Coding for Permutation Channels with Impairments
• Asymptotically Optimal Codes Correcting Fixed-Length Duplication Errors in DNA Storage Systems
• Perfect Codes in the Discrete Simplex
• Runlength-Limited Sequences and Shift-Correcting Codes: Asymptotic Analysis
• Asymptotic Behavior and Typicality Properties of Runlength-Limited Sequences
• Evaluation of the Gilbert-Varshamov Bound using Multivariate Analytic Combinatorics

Cited by in corpus (1)

• Quantum error correction beyond $SU(2)$: spin, bosonic, and permutation-invariant codes from convex geometry