NEW CLASSES OF PERFECT MAPS .1.

The existence and construction of perfect maps, also known as de Bruij n arrays or de Bruijn tori, is considered. A c-ary (r, s; u, upsilon) perfect map is a two-dimensional periodic array with periods r and s a nd symbols from an alphabet of size c with the property that every pos sible u x upsilon array of symbols occurs exactly once in a period of the array. They generalise the well-known de Bruijn sequences. Simple necessary conditions on the parameters r,s, u, upsilon for the existen ce of perfect maps are given. These conditions are shown to be suffici ent when c is a power of a prime by constructing perfect maps for ever y allowed parameter set. This result will be applied in the second par t to construct further c-ary perfect maps. (C) 1996 Academic Press, In c.