Perfect Sequence Finder (psf) - finds constructions for perfect sequences and arrays. This program is a spin-off of numerous different programs I have been running since mid 2006. Many details of this program are given in my PhD thesis, in particular Chapter 9.
The goal of this project is to find a perfect sequence which is longer than the Frank sequences, length n^2 over n roots of unity. For example, the discovery of a sequence of length 216 over 6 roots of unity. It is presently unknown if such sequences exist, however they would have immediate applications in communications, providing the phase is not too large.
This program searches for n-phase two dimensional arrays with perfect periodic autocorrelation. The index function of the array is of the form
S(i,j) = \omega^{\sum_{k=1}^{N}floor(p_k(x,y)/d_k)},
where \omega = e^(2 \pi \sqrt{-1}/n), p_k(x,y) are bivariate polyomials and d_k \elem Z_n. Per Ma, Ng "On non-existence of perfect and nearly perfect sequences", Int. J. Information and Coding Theory, Vol. 1, No. 1, 2009, n should not be prime. The polynomials, p_k(x,y), and denominators are randomly generated within user-specified constraints.
Running this program with efficient correlations uses FFTW. Instructions for installing FFTW using brew is given at https://brewformulas.org/Fftw and instructions for the installation of pyfftw is given at https://github.com/pyFFTW/pyFFTW.
Alternatively you can use FFTpack by replacing crosscorrelate_fftw with crosscorrelate_fftpack in max_abs_off_peak(). Note that for larger arrays FFTW will be significantly faster than FFTpack.
In the near future I'll test out replacing the C code for fill_array_2d with a numba compiled python equivalent. Ideally this should not slow down the program too much, if at all, while making everything significantly simpler.
The program requires you to specify the following:
-
The minimum and maximum number of phases. For example: phases = [6,8,12]
-
Bounds on the number of elements in the arrays. For example: size_ranges = [[36,1296]] will generate arrays with all sizes between 36 and 1296.
-
The modulus of the d_k's and p_k(x,y)'s. By default the modulus is the phase of the array. For example: modulus = 'Automatic' will use the array phase.
-
The denominators, by default are generated randomly in Z_n. However they can be user-specified. For example: denominators = [2,3,5].
-
The number of trials for each configuration of phase, array size, and denominator. For example, n_trials = 100.
-
The number of sums, N. For example n_sums = 2.
-
The maximum degree of the polynomial p_k(x,y) in x. For example degX = 2.
-
The maximum degree of the polynomial p_k(x,y) in y. For example degY = 2.
-
The tolerance for a perfect array. For example: tol_perfect = 0.01 specifies that the off-peak shifts be 1% or less of the peak.
-
A flag to specify that the array is square: square_only = True. By default square_only = False.
-
A flag to specify that the dimensions of the arrays are coprime only. diagonal_only = True. By default diagonal_only = False.
If a perfect array is found the array is then checked for the Array Orthogonality Property. If so, a perfect sequence has been discovered. If the array has coprime dimensions then a perfect sequence has been discovered.
The example below often finds the smallest sequence generated by the sequence construction given in S. Blake, A. Z. Tirkel, “A Construction for Perfect Autocorrelation Sequences over Roots of Unity”, SETA 2014, pp. 104-108, November 2014. In fact, an earlier version of this program was used to find the construction.
psf.psf2d(phases = [6], moduli = [2], size_ranges = [[12,12]], n_sums = 1, degX = 2, degY = 1, n_trials = 1000)
An example output from running this is
Perfect array found on 2019-01-22 21:56:30
index = x*y + x^2
phase = 6
size = 2 x 6
type = 2D
Perfect SEQUENCE found on 2019-01-22 21:56:30
index = x*y + x^2
phase = 6
size = 2 x 6
type = column-major
Numerous other examples are given in searches.py.