Sequence Folding, Lattice Tiling, and Multidimensional Coding

Folding a sequence B into a multidimensional box is a well-known method which is used as a multidimensional coding technique. The operation of folding is generalized in a way that the sequence B can be folded into various shapes and not just a box. The novel definition of folding is based on a lattice tiling for the given shape S and a direction in the D-dimensional integer grid. Necessary and sufficient conditions that a lattice tiling for S combined with a direction define a folding of a sequence into S are derived. The immediate and most impressive applications are some new lower bounds on the number of dots in two-dimensional synchronization patterns. Asymptotically optimal such patterns were known only for rectangular shapes. We show asymptotically optimal such patterns for a large family of hexagons. This is also generalized for multidimensional synchronization patterns. The best known patterns, in terms of dots, for circles and other polygons are also given. The technique and its application for two-dimensional synchronization patterns, raises some interesting problems in discrete geometry. We will also discuss these problems. It is also shown how folding can be used to construct multidimensional error-correcting codes. Finally, by using the new definition of folding, new types of multidimensional pseudo-random arrays with various shapes are generated.