Families of Multidimensional Arrays with Good Autocorrelation and Asymptotically Optimal Cross-correlation

Biphase sequence families with low periodic off peak autocorrelation and low cross-correlation are highly sought after for CDMA wireless communications. This has been an active research area since the landmark paper of Gold in 1967[7], and numerous constructions of such families are known.

The concept of binary two-dimensional doubly periodic arrays with optimal off-peak autocorrelation was introduced by Gordon in 1966[8]. Such arrays are two-dimensional analogues of m-sequences. They are either solitary, or have very small family sizes called maximal connected sets[17], and higher-dimensional families are rare[9]. Perfect binary arrays in two and higher-dimensions have also been studied[11], but they are solitary, and most have unfavourable aspect ratios for applications. In 1988, Lüke surveyed existing constructions of two-dimensional arrays[14]. In 1989, the Legendre sequences were generalised to two and higher-dimensional analogues[15][6].

Two and three-dimensional arrays find applications in optics, where they are used for coded aperture imaging, or in structured light, where they are used for image alignment or registration. The first families of two-dimensional arrays were constructed in 1991 by Green et al[10], where the small Kasami and No–Kumar sequences were interpreted as arrays.

In 1997, Tirkel et al, motivated by finding two-dimensional patterns for use as spread spectrum watermarks, constructed families of arrays. The arrays were of size $p\times p$, where $p$ is a prime number. Later this was extended to $p\times p-1$, $p\times p+1$, and $p-1\times p+1$ [13] and to higher dimensions[2].

The periodic cross-correlation of two $N$-dimensional arrays, A and B, both of size $l_{0}\times l_{1}\times\cdots\times l_{N-1}$, for shift $s_{0},s_{1},\cdots,s_{N-1}$ is defined as

Similarly, the periodic autocorrelation of a $N$-dimensional array for shift $s_{0},s_{1},\cdots,s_{N-1}$ is given by $\theta_{\textbf{A}}\left(s_{0},s_{1},\cdots,s_{N-1}\right)=\theta_{\textbf{A},\textbf{A}}\left(s_{0},s_{1},\cdots,s_{N-1}\right)$. $\theta_{\textbf{A}}(s_{0},s_{1},\cdots,s_{N-1})$ is called an off-peak autocorrelation if not all $s_{i}=0\text{ mod }l_{i}$. We denote the array of all autocorrelations and cross-correlations for all shifts as $\theta_{\textbf{A}}$ and $\theta_{\textbf{A},\textbf{B}}$ respectively.

Sequences with flat periodic autocorrelation which used properties of the Legendre symbol were first discovered by Lerner in 1958[12], where the sequences were termed Legendre sequences. In the same year, Zierler showed the Legendre sequences possessed flat periodic autocorrelation[21].

If $a=0$, then all off-peak autocorrelations of the Legendre sequences equal to -1. If $a=\pm 1$, then all off-peak autocorrelations of the Legendre sequences $-1$ when $p=4k-1$, and $1$ and $-3$ otherwise.

In 1990, Bömer and Antweiler introduced a construction of two-dimensional Legendre arrays of sizes $p\times p$ where $p$ is an odd prime[5]. These arrays possessed flat autocorrelation, with all off-peak autocorrelations equal to -1.

If $a=0$, then all the off-peak periodic autocorrelations are $-1$, and if $a=\pm 1$ then all the off-peak periodic autocorrelations are $\pm 1$ and $\pm 3$.

This construction readily generalises to $n$-dimensions by using a primitive polynomial of degree $n$ in $\text{GF}\left(p^{n}\right)$.

In 2017, Blake and Tirkel introduced a construction for multi-dimensional, block-circulant perfect autocorrelation arrays[1][4]. A special case of this construction is a two-dimensional perfect array, constructed from a circulant array[3, const. XII, pp. 38].

The sequence, a, is termed the multiplication sequence.

We now introduce a construction for families of $2n$-dimensional arrays.

Similarities between this construction and the 2D circulant construction are clearly evident. In particular, the multiplication sequence $a_{j}$ and its counterpart the multiplication array $A_{i_{0},i_{1},\cdots,i_{n-1}}$; and the circulant array of columns $\,c_{i+j\text{ mod }n}$ and its counterpart $A_{m\,i_{0}+i_{n}\text{ mod }p,m\,i_{1}+i_{n+1}\text{ mod }p,\cdots,m\,i_{n-1}+i_{2n-1}\text{ mod }p}$.

These arrays are asymptotically optimal in the sense of the Welch bound[19][20]. Each array has $p^{2n}-2p^{n}+1$ non-zero entries. Then the cross-correlation bound to peak ratio is given by $(p^{n}+1)/(p^{2n}-2p^{n}+1)$ and is asymptotic to the Welch bound of $p^{n}/p^{2n}$. For example, for $p=67$, the relative difference is $1.5\times 10^{-5}\%$.

In this section we introduce a new application for higher-dimensional arrays with good autocorrelation and cross-correlation. We develop a new technique for embedding higher-dimensional arrays into imagery using spread spectrum watermarking techniques[16].

In the past, spread spectrum watermarking schemes used a sequence or array of dimensionality commensurate to the dimensionality of the dataset. Thus, a two-dimensional array is used to watermark an image; and every array embedded in the image supports a payload of two integers (the horizontal and vertical periodic shifts of the two-dimensional array). Then in order to support larger payloads, multiple arrays are embedded into the imagery. The embedding of multiple arrays relies on the cross-correlation properties of the families of arrays. However, even with families of optimal arrays, the signal-to-noise ratio (SNR) will decrease as more arrays are embedded.

We propose increasing the watermark payload, and subsequently increasing the SNR of the extraction, by increasing the dimensionality of the embedded arrays. We embed a $2n$-dimensional array into an image by partially flattening the array into a two-dimensional array.

We embed a $2n$-dimensional array, $\textbf{S}=\left[S_{i_{0},i_{1},\cdots,i_{2n-1}}\right]$ of size $d_{0}\times d_{1}\times\cdots\times d_{2n-1}$, into an image (2-dimensional dataset), $\textbf{I}=\left[I_{i,j}\right]$, by successively decreasing the dimensionality of S from $2n$, $\textbf{S}^{2n}$ to $n$, $\textbf{S}^{n}$, until we have a 2-dimensional array, where

where $i_{0}=q_{0}d_{0}+r_{0},i_{1}=q_{1}d_{1}+r_{1},\cdots,i_{n-1}=q_{n-1}d_{n-1}+r_{n-1}$.

Conversely, we partition the two-dimensional image into a $2n$-dimensional representation prior to cross-correlating with the family of $2n$-dimensional arrays.

This scheme embeds $2n$ integers (as periodic shifts of the array) for each array embedded, which greatly increases the payload per array in comparison with lower-dimensional arrays.