Well-spaced labelings of points in rectangular grids

We describe methods to label the M-1 x M-2 grid with the integers 1 to M1M2 so that any K consecutively labeled cells are relatively far apart in the grid in the Manhattan metric. Constructions of such labelings are given whi ch are nearly optimal in a range of conditions. Such labelings can be used in addressing schemes for storing data on two-dimensional arrays that inclu de randomly located blobs of defective cells. The data can be precoded usin g block error-correcting codes before storage, and the usefulness of well-s paced points is to decrease the probability of burst errors which cannot be corrected. Possible applications include the storage of speech or music on low-quality memory chips and in holographic memories to store bit-mapped d ata. More generally, we present a general family of mappings of the integers 1 t o M1M2 ... M-d onto the d-dimensional grid of size M-1 x M-2 x ... x M-d, c alled mixed radix vector mappings. These mappings give labelings whenever t hey are one to one. We give a sufficient condition for these mappings to be one to one, which is easy to verify in many cases.