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

许多通信和遥感系统需要由数字序列描述的调制协议，数字序列可以被认为是由来自规定字母表的符号组成的字，例如具有符号0和1的二进制字母表。系统的效率通常取决于产生尽可能不相关的序列：它们不应该类似于彼此的移位（时间延迟）版本，甚至也不应该类似于它们自己。序列和其自身的移位版本之间缺乏相似性有助于同步和定时，这在雷达和声纳中很有用。两个不同序列之间缺乏相似性（无论它们如何移位）可以防止通信网络中不同用户之间的混淆。随机序列对于这些应用并不理想，因为即使是随机序列也会偶尔重复。使用伪随机序列比随机序列更大程度地避免重复是更有利的。这些伪随机序列和相关的数学结构，如布尔函数，在其他信息理论问题中也很重要，如密码学，其中人们试图设计具有简单的底层数学形式（以简化加密和解密）但避免类似于容易检测的模式（以抵抗密码分析）的排列。伪随机序列在纠错码、天线阵列、科学仪器和声学设计等方面有着广泛的应用，因此，科学和技术都可以从对已知数字序列的分析和新序列的发现中受益。本项目的目标是创建和研究具有良好相关特性的数字序列及其相关数学结构。这个项目考虑了周期性和非周期性的相关性，因为两者在应用中都很重要。在周期相关中，序列的移位是循环的，并且最大长度线性反馈移位寄存器序列（m序列）是低周期相关数字序列设计中的常见构建块。寻找具有低互相关性的m序列对等价于寻找有限域的高度非线性置换，这可以用于使密码系统对线性密码分析具有弹性。这个项目将研究具有特殊相关特性的m序列对，这些特性转化为相应排列的特殊非线性特性。极端的属性，如异常高的非线性或异常少的相关值，寻求出来，这个项目将调查这些极端使用抽象代数，组合数学和数论的工具，以及经验计算探索的界限和限制。在非周期相关中，序列的移位是非循环平移，并且已知其相关特性使其上级随机序列的各种序列族，但是它们的分析一直很困难，并且仍然存在许多未决问题。该项目将分析这些序列的性能，无论是经验和理论，并将寻求新的家庭序列具有良好的相关性properties。该奖项反映了NSF的法定使命，并已被认为是值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估的支持。

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 propertiesThis 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.