The capacity and coding gain of certain checkerboard codes

Abstract

We define a checkerboard code as a two-dimensional binary code that satisfies some constraint, e.g., every binary one must be surrounded by eight zeros, and then investigate the capacity for each of several different constraints. Using a recursive construction we develop a series of loose bounds on the capacity. These bounds, in turn, lead to conjecturally precise estimates of the capacity by the use of a numerical convergence-speeding technique called Richardson extrapolation. Finally, using the value of the capacity, we define and compute a measure of coding gain which allows us to compare checkerboard codes to simple coding schemes.