Folding, Tiling, and Multidimensional Coding

Date Added: Jul 2009
Format: PDF

Folding a sequence S into a multidimensional box is a method that is used to construct multidimensional codes. The well known operation of folding is generalized in a way that the sequence S can be folded into various shapes. The new definition of folding is based on lattice tiling and a direction in the D-dimensional grid. There are potentially (3D -1)/2 different folding operations. Necessary and sufficient conditions that a lattice combined with a direction define a folding are given. The immediate and most impressive application is some new lower bounds on the number of dots in two-dimensional synchronization patterns. This can be also generalized for multidimensional synchronization patterns.