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

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

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.