Sequence Folding, Lattice Tiling, and Multidimensional Coding
Tuvi Etzion · IEEE Transactions on Information Theory · 2011
Folding a sequenceBinto 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 sequenceBcan be folded into various shapes and not just a box. The novel definition of folding is based on a lattice tiling for the given shapeSand a direction in theD-dimensional integer grid. Necessary and sufficient conditions that a lattice tiling forScombined with a direction define a folding of a sequence intoSare 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.