The Depth-First Algorithm for Designing 2-D Single-State Block Codes

A two-dimensional (2-D) constrained system consists of 2-D binary sequences satisfying certain properties. Most of the 2-D constrained systems can be represented as a set of forbidden patterns, which should be avoided in the input sequences to the channel. This paper proposes a depth-first algorithm to search for single-state codes with rectangular codewords. The algorithm provides the optimal single-state codes, meaning that no other single-state code can have larger coding rate. For certain 2-D constraints, this algorithm has comparatively low complexity. The coding rate asymptotically approaches the capacity of the 2-D constrained system when the codeword size increases.