Folding, Tiling and Applications to Multidimensional Coding

Speaker: Prof Tuvi Etzion (Technion IIT)

Time: 11:00AM

Date: Tue 8th September 2009

Location: CASL Seminar Room - Belfield Office Park

Folding a sequence S 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 S can be folded into various shapes and not just a box. The new de nition of folding is based on lattice tiling and a direction in the D-dimensional grid. There are potentially (3^D-1)/2 diff erent folding operations. Necessary and suffcient conditions that a lattice combined with a direction de ne a folding are derived. 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. It is also shown how folding can be used to construct multidimensional error-correcting codes. Finally, multidimensional pseudo-random arrays with various shapes are generated.

(This talk is part of the Algebra/Claude Shannon Institute series.)