CIF: Small: RUI: Low Correlation and Highly Nonlinear Structures for Communications and Sensing

The University Corporation, Northridge, Northridge CA

Investigators

Abstract

Many communications and remote sensing systems require modulation protocols that are described by digital sequences, which may be regarded as words composed of symbols from a prescribed alphabet, such as the binary alphabet with symbols 0 and 1. The efficiency of the system will often depend on producing sequences that are as uncorrelated as possible: they should not resemble shifted (time-delayed) versions of each other, nor even of themselves. Lack of resemblance between a sequence and shifted versions of itself aids in synchronization and timing, which is useful in radar and sonar. Lack of resemblance between two different sequences (no matter how they are shifted) prevents confusion between different users in communications networks. Random sequences are not ideal for these applications, as even random sequences are expected to have occasional repetitions. It is more advantageous to use pseudorandom sequences that avoid repetition to a greater degree than random sequences do. These pseudorandom sequences and related mathematical structures, such as Boolean functions, are also significant in other information-theoretic problems, such as in cryptography, where one seeks to design permutations that have a simple underlying mathematical form (to ease encryption and decryption) but avoid resembling easily detectable patterns (to resist cryptanalysis). Pseudorandom sequences find further applications in error-correcting codes, antenna arrays, scientific instrumentation, and acoustic design, and thus science and technology benefit both from the analysis of known digital sequences and the discovery of new ones. The goal of this project is to create and investigate digital sequences and related mathematical structures with good correlation properties. This project considers both periodic and aperiodic forms of correlation, as both are important in applications. In periodic correlation, the shifting of the sequences is cyclic, and the maximum length linear feedback shift register sequences (m-sequences) are a common building block in the design of digital sequences with low periodic correlation. Finding pairs of m-sequences with low mutual correlation is equivalent to finding highly nonlinear permutations of finite fields, which can be used to make cryptosystems resilient to linear cryptanalysis. This project will investigate m-sequence pairs with exceptional correlation properties, which translate into exceptional nonlinearity properties of the corresponding permutations. Extremal properties, such as exceptionally high nonlinearity or exceptionally few correlation values, are sought out, and this project will investigate bounds and limitations on these extremes using tools from abstract algebra, combinatorics, and number theory, as well as empirical computational explorations. In aperiodic correlation, the shifting of sequences is a non-cyclic translation, and various families of sequences whose correlation properties make them superior to random sequences are known, but their analysis has been difficult and many open questions remain. This project will analyze the performance of these sequences both empirically and theoretically, and will seek new families of sequences with good correlation properties This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.