Block Codes for the Hard-Square Model

The hard-square model is a two-dimensional (2-D) constrained system consisting of all binary arrays on a rectangular grid in which 1's are isolated both horizontally and vertically. This paper proposes algorithms to search for single-state and finite-state block codes with rectangular codewords that satisfy the hard-square constraint. Although the codeword size is small, single-state block codes with coding rates larger than 0.5 can be designed. Letting the 2-D constrained sequences have finite memory increases the achievable coding rate. A method for designing low-complexity encoders and decoders is also presented. When the codeword size increases, the coding rate asymptotically approaches the capacity but with rapidly increasing complexity of the encoder and decoder.