A covering space approach to (d,k) constrained codes

Abstract

The capacity of the (d, k) constrained codes and of the (d, k) L level charge constrained codes is considered. The case of rational capacity is examined. and an error in the literature is corrected. This leads to an interesting (0.3)L = 4 level charge constrained code. The error control for this code is done using the finite field GF(3). A table of the ternary convolutional codes of greatest free distance is given for possible applications. The topological properties of the (d, k) constraint graphs are examined. The fundamental group of a constraint graph and covering spaces of a constraint graph are discussed. A constructive process for building a covering space of a constraint graph is given. The construction of (d, k) constrained block codes from covering spaces of the (d, k) constraint graph is examined. Several types of block codes are introduced. The base point codes consist of the (d, k) constrained sequences whose associated edge paths in the covering space are loops at a specified vertex. The parity point codes consist of the (d, k) constrained sequences whose associated edge paths in the covering space conned two specified vertices. It is shown that an [n, k] cyclic code can be constructed as a base point code for a 2^(n-k) fold covering of the (0,∞) constraint graph. Systematic (d, k) constrained block codes are constructed for detecting all single shift errors, drop in errors, and drop out errors. The average probability of an undetected error for the systematic (d, k) constrained block codes is shown to decrease exponentially with the parity length times the capacity of a (d, k) constrained code.