The merit factor of a$\{-1, 1\}$binary sequence measures the collective smallness of its non-trivial aperiodic autocorrelations. Binary sequences with large merit factor are important in digital communications because they allow the efficient separation of signals from noise. It is a longstanding open question whether the maximum merit factor is asymptotically unbounded and, if so, what is its limiting value. Attempts to answer this question over almost sixty years have identified certain classes of binary sequences as particularly important: skew-symmetric sequences, symmetric sequences, and anti-symmetric sequences. Using only elementary methods, we find an exact formula for the mean and variance of the reciprocal merit factor of sequences in each of these classes, and in the class of all binary sequences. This provides a much deeper understanding of the distribution of the merit factor in these four classes than was previously available. A consequence is that, for each of the four classes, the merit factor of a sequence drawn uniformly at random from the class converges in probability to a constant as the sequence length increases.

An efficient compressed sensing scheme requires a small number of measurements, a fast recovery algorithm, a small approximation error, and little or no randomness. In 2014, Iwen presented two compressed sensing schemes with near-optimal runtime, based on binary matrices. We combine ideas from these two schemes with a classical construction, used by Porat and Rothschild for near-optimal group testing, to produce a new compressed sensing scheme requiring significantly less randomness without compromising runtime. We give two variants of this compressed sensing scheme: the first is measurement-optimal, and the second is deterministic.

A Costas array is a permutation array for which the vectors joining pairs of 1s are all distinct. We propose a new 3-D combinatorial object related to Costas arrays: an order n Costas cube is an array (di, j,k) of size n× n× n over ℤ2for which each of the three projections of the array onto two dimensions, namely (Σidi, j,k) and (Σjdi, j,k) and (Σkdi, j,k), is an order n Costas array. We determine all Costas cubes of order at most 29, showing that Costas cubes exist for all these orders except 18 and 19 and that a significant proportion of the Costas arrays of certain orders occur as projections of Costas cubes. We then present constructions for four infinite families of Costas cubes.

A Costas array is a permutation array in which the vectors joining pairs of 1s are all distinct. The toroidal vectors of a permutation array are the vectors occurring when the array is written on a torus, and the deficiency of a permutation array of order n is the number of toroidal vectors, out of the (n-1)2possible, which are missing from the array. The smallest deficiency among all permutation arrays of order q-1, where q is a power of a prime other than 3, is known, and it is of interest to find examples of permutation arrays attaining this minimum value. The deficiency of Costas arrays is studied computationally and theoretically. It is shown that all Welch Costas arrays of a given order have the same deficiency. It is shown that the deficiency of Golomb-Rickard Costas arrays of order q-1 attains the minimum value over all permutation arrays when q is a power of a prime other than 3. Computational experiments show that the deficiency distribution of Costas arrays of a given order acts as a filter that highlights the Welch Costas arrays, isolates the Golomb-Rickard Costas arrays, and gives further insights into the structure of other Costas arrays. In particular, four Costas arrays with exceptionally small deficiency are recognised, and it is asked if they could be used to identify a new algebraic construction for Costas arrays.

A recent paper by Jedwab and Wodlinger renewed interest in a problem of multislit spectrometer design first proposed by Golay in 1951 but subsequently forgotten. It is shown that Golay's formulation of the problem in terms of 0/1 binary sequences is unduly restrictive. By relaxing the restrictions, infinitely many spectrometer designs satisfying all the original physical criteria can be found. Three constructions for such spectrometer designs are presented, involving Golomb rulers and variants. These constructions explain all nontrivial examples involving at most 26 slits.

In 1999, Davis and Jedwab gave an explicit algebraic normal form for$m! \cdot 2^{h(m+2)}$ordered Golay pairs of length$2^{m}$over$ {\BBZ }_{2^{h}}$, involving$m!/2 \cdot 2^{h(m+1)}$Golay sequences. In 2005, Li and Chu unexpectedly found an additional 1024 length 16 quaternary Golay sequences. Fiedler and Jedwab showed in 2006 that these new Golay sequences exist because of a “crossover” of the aperiodic autocorrelation function of certain quaternary length eight sequences belonging to Golay pairs, and that they spawn further new quaternary Golay sequences and pairs of length$2^{m}$for$m > 4$under BudiŠin's 1990 iterative construction. The total number of Golay sequences and pairs spawned in this way is counted, and their algebraic normal form is given explicitly. A framework of constructions is derived in which Turyn's 1974 product construction, together with several variations, plays a key role. All previously known Golay sequences and pairs of length$2^{m}$over$ {\BBZ }_{2^{h}}$can be obtained directly in explicit algebraic normal form from this framework. Furthermore, additional quaternary Golay sequences and pairs of length$2^{m}$are produced that cannot be obtained from any other known construction. The framework generalizes readily to lengths that are not a power of$2$, and to alphabets other than$ {\BBZ }_{2^{h}}$.

In 1995, the IEEE approved the 802.12 standard for data transmission at 100-Mbit/s using the Demand Priority Network Access protocol. 100 VG-AnyLAN products conforming to this standard offered an upgrade path for Ethernet and token ring networks, without requiring new building wiring. A key factor in the approval of the 802.12 standard was the demonstrated error detection properties of its coding scheme. In particular, the coding scheme allows the detection of error bursts affecting encoded data carried on four parallel conductors, using nothing more than the standard IEEE 32-bit cyclic redundancy check applied to the unencoded data. Although these error detection properties were presented for verification as part of the standards process, for many years commercial considerations prevented public disclosure of how the code was actually found. These considerations no longer apply, and, in this paper, we explain in detail the design principles of the code, combining geometrical insight, linear algebra, combinatorial reasoning, and computer search.

A numerical investigation is presented for the peak sidelobe level (PSL) of Legendre sequences and maximal length shift register sequences (m-sequences). The PSL gives an alternative to the merit factor for measuring the collective smallness of the aperiodic autocorrelations of a binary sequence. The growth of the PSL of these infinite families of binary sequences is tested against the desired growth rate o(radic(n ln n)) for sequence length n. The claim that the PSL of m-sequences grows like O(radicn), which appears frequently in the radar literature, is concluded to be unproven and not currently supported by data. Notable similarities are uncovered between the PSL and merit factor behaviour under cyclic rotations of the sequences

In 1999, Davis and Jedwab gave a direct construction of Golay complementary sequences over Zopf2hof length 2m. Recently, Li and Chu found 1024 more quaternary Golay complementary sequences of length 16, that cannot be obtained by the direct construction, using exhaustive computer enumeration. It is shown how these sequences arise from interleaving and concatenation of two classes of Golay complementary sequences given as an example by Davis and Jedwab. These examples spawn new Golay sequences over Zopf2hof length 2mfor all h ges 2 and m ges 4

A numerical investigation is presented for the peak sidelobe level (PSL) of Legendre sequences, maximal length shift register sequences (m-sequences), and Rudin-Shapiro sequences. The PSL gives an alternative to the merit factor for measuring the collective smallness of the aperiodic autocorrelations of a binary sequence. The growth of the PSL of these infinite families of binary sequences is tested against the desired growth rate o(/spl radic/nlnn) for sequence length n. The claim that the PSL of m-sequences grows like O(/spl radic/n), which appears frequently in the radar literature, is concluded to be unproven and not currently supported by data. Notable similarities are uncovered between the PSL and merit factor behavior under cyclic rotations of the sequences.

The maximum known asymptotic merit factor for binary sequences has been stuck at a value of 6 since the 1980s. Several authors have suggested that this value cannot be improved. In this paper, we construct an infinite family of binary sequences whose asymptotic merit factor we conjecture to be greater than 6.34. We present what we believe to be compelling evidence in support of this conjecture. The numerical experimentation that led to this construction is a significant part of the story.

We present a range of coding schemes for OFDM transmission using binary, quaternary, octary, and higher order modulation that give high code rates for moderate numbers of carriers. These schemes have tightly bounded peak-to-mean envelope power ratio (PMEPR) and simultaneously have good error correction capability. The key theoretical result is a previously unrecognized connection between Golay complementary sequences and second-order Reed-Muller codes over alphabets Z/sub 2/h. We obtain additional flexibility in trading off code rate, PMEPR, and error correction capability by partitioning the second-order Reed-Muller code into cosets such that codewords with large values of PMEPR are isolated. For all the proposed schemes we show that encoding is straightforward and give an efficient decoding algorithm involving multiple fast Hadamard transforms. Since the coding schemes are all based on the same formal generator matrix we can deal adaptively with varying channel constraints and evolving system requirements.

A Barker array is a two-dimensional array with elements $ \pm 1$ such that all out-of-phase aperiodic autocorrelation coefficients are $0,1$, or $ - 1$. No $s \times t$ Barker array with $s,t > 1$ and $( s,t ) \ne ( 2,2 )$ is known, and it is conjectured that none exists. A class of arrays that includes Barker arrays is defined. Nonexistence results for this class of arrays in the case $st$ even, providing support for the Barker array conjecture, are proved. Several connections, in the case $st$ even, between this class of arrays and perfect, quasi-perfect, and doubly quasi-perfect binary arrays are demonstrated.

A Barker array is a two-dimensional array with elements $ \pm 1$ such that all out-of-phase aperiodic autocorrelation coefficients are $0,1$, or $ - 1$. No $s \times t$ Barker array with $s,t > 1$ and $( s,t ) \ne ( 2,2 )$ is known, and it is conjectured that none exists. Nonexistence results for a class of arrays that includes Barker arrays have been previously given, in the case where $st$ is even. We prove nonexistence results for this class of arrays in the case where $st$ is odd, providing further support for the Barker array conjecture.