Introduction

This chapter describes fields of discrete symbols over finite alphabets A (with ∣A∣ symbols). Such fields can serve as models of graphics media or of other forms of two-dimensional (2-D) storage medium. By addressing the storage medium as a surface on which an image array may be written, the density may be increased. Besides optical storage, new storage techniques based on holography and nano-technology have been demonstrated. Two-dimensional barcodes have also been designed for coding small messages, but increasing the capacity compared with conventional barcodes, which carry information in one dimension only. The Datamatrix is an example of such a code. We focus on 2-D constrained coding for storage applications, but the models presented are more general and they may be used for other applications as well.

Two-dimensional fields with a finite constraint

The symbols are placed in a regular grid (commonly referred to as a lattice) and indexed a(i, j), where i, j are integers. The first index indicates rows and the symbols are spaced at equal intervals within the row. We usually consider rectangular grids on which the symbols are aligned in columns indicated by the second index. However, the symbols in row i + 1 can be shifted a fraction of a symbol interval relative to row i. In particular, a shift of half a symbol interval gives a hexagonal grid. The mutual dependency of symbols is often described in terms of neighbors.