PERFECT MAPS

Given positive integers r, s, u, and v, an (r, s; u, v) Perfect Map (P M) is defined to be a periodic r x s binary array in which every u x v binary array appears exactly once as a periodic subarray. Perfect Map s are the natural extension of the de Bruijn sequences to two dimensio ns. In this paper the existence question for Perfect Maps is settled b y giving constructions for Perfect Maps for all parameter sets subject to certain simple necessary conditions. Extensive use is made of prev iously known constructions by finding new conditions which guarantee t heir repeated application. These conditions are expressed as bounds on the linear complexities of the periodic sequences formed from the row s and columns of Perfect Maps.