A thesis on evaluation of the gilbert-varshamov bound for constrained systems

Abstract

Obtaining nontrivial lower bounds on the rates of optimal codes in nonuniform spaces is gener- ally a difficult problem. This thesis is devoted to the study of the well-known Gilbert-Varshamov (GV) bound for constrained systems. Evaluation of this GV bound for specific constrained sys- tems poses a significant computation challenge. In 1991, Kolesnik and Krachkovsky showed that the GV bound can be determined via the solution of some optimization problems. Later, Mar- cus and Roth (1992) modified the optimization problem and improved the GV bound in many instances. This thesis aims to mitigate the computation challenges by introducing two different graph-theoretic and combinatorial approaches for the evaluation of the GV bound. We empha- size that the graph-theoretic approach is preferable for constrained systems for which graph pre- sentation is well known. On the other hand, a combinatorial approach is preferable when the generating function for total ball size is easy to find. In the graph-theoretic approach, we provide explicit numerical procedures to solve these two optimization problems and hence, compute the bounds for several constrained systems in Ham- ming metric including Run length constrained systems and Sliding Window constrained systems. We then show the procedures can be further simplified when we plot the respective curves. In the case where the graph presentation comprises a single state, we provide explicit formulas for both bounds. Analytic combinatorics in several variables refers to a suite of tools that provide sharp asymp- totic estimates for certain combinatorial quantities. In our combinatorial approach, we apply these tools to determine the Gilbert–Varshamov lower bound on the rate of optimal codes in the $L_1$ metric. Several different code spaces are analyzed, including the simplex and the hypercube in $Z^n$, all of which are inspired by concrete data storage and transmission models such as the permu- tation channel, the repetition channel, the adjacent transposition (bit-shift) channel, the multilevel flash memory channel, etc.