Constructions for Perfect Autocorrelation Sequences and Multi-Dimensional Arrays

This thesis presents new constructions for perfect periodic autocorrelation sequences, zero periodic auto-correlation zone sequences, perfect periodic two-dimensional arrays, and perfect periodic multi-dimensional arrays over complex roots of unity (including new perfect binary arrays) and the unit quaternions.

The perfect sequences constructed in this thesis complement the known constructions of Heimiller-Frank, Zadoff-Chu, Milewski, and Liu-Fan. Three new constructions possess the array orthogonality property, and one construction is from a perfect two-dimensional array with coprime dimensions. This construction does not possess the array orthogonality prop- erty and is a counterexample to Mow’s conjecture that his unified construction generates all known perfect sequences.

Families of perfect two and multi-dimensional arrays are presented which possess good cross-correlation. Due to the combinatorial nature of the construction, the size of these families is exponentially large.

We introduce a multi-dimensional generalisation of the array orthogonality property of Mow, Frank, and Heimiller. This generalised array orthogonality property is used to con- struct new perfect multi-dimensional arrays and families of pairwise orthogonal arrays.

We introduce new constructions for perfect sequences, two-dimensional and four-dimensional arrays over the unit quaternions. One sequence construction possesses the array orthogo- nality property and its length is the square of the number of elements in the alphabet: {−1, 1, −i, i, −j, j, −k, k}. We conjecture, as an extension of the Heimiller-Frank conjecture, that longer perfect sequences with the array orthogonality property over the unit quaternions do not exist.

A novel algorithm was used to find many of the constructions in this thesis. Unlike many search algorithms considered previously, we do not exhaustively search through the all permutations of possible sequences or arrays of a given size. We instead randomly generate a symbolic representation for mathematical constructions of sequences and arrays and test their properties. We give a detailed overview of this algorithm and show many of the exam- ple outputs from its execution on the Monash Campus Cluster.

The sequences and arrays constructed in this thesis could see applications in many areas. These include electronic digital watermarking of images, video and audio, channel estimation and synchronisation, fast start-up equalisation, pulse compression radars, CDMA systems. 3D television, acoustic absorbers and diffusers, antenna and loudspeaker arrays.

Parts of this thesis have been published:
S. Blake, T. E. Hall, A. Z. Tirkel, “Arrays over Roots of Unity with Perfect Autocorrelation
and Good ZCZ Cross–Correlation”, Advances in Mathematics of Communications (AMC), vol. 7, no. 3, pp. 231–242, 2013
S. Blake, A. Z. Tirkel, “A Construction for Perfect Autocorrelation Sequences over Roots of Unity”, SETA, 2014, pp. 104-108, November 2014
S. Blake, A. Z. Tirkel, “A Multi-Dimensional Block-Circulant Perfect Array Construction”, Advances in Mathematics of Communications, accepted for publication 2017, presented at WMC, 2016