New classes of perfect maps I

The existence and construction of perfect maps, also known as de Bruijn arrays or de Bruijn tori, is considered. A c-ary (r, s; u, v) perfect map is a two-dimensional periodic array with periods r and s and symbols from an alphabet of size c with the property that every possible u × v 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, v for the existence of perfect maps are given. These conditions are shown to be sufficient when c is a power of a prime by constructing perfect maps for every allowed parameter set. This result will be applied in the second part to construct further c-ary perfect maps.