Low autocorrelation binary sequences
Low autocorrelation binary sequences
复制标题
DOI：
10.1088/1751-8113/49/16/165001
复制
发表时间：
2015-12
期刊：
影响因子：
--
通讯作者：
Tom Packebusch;S. Mertens
中科院分区：
文献类型：
--
作者：
Tom Packebusch;S. Mertens
具有最小自相关的二进制序列在通信工程、数学和计算机科学中有着广泛的应用。在统计物理学中，它们以Bernasconi模型的基态出现。寻找这些序列是一个众所周知的难题，到目前为止只能通过穷举搜索来解决。我们回顾了最近的算法，并提出了一个新的算法，找到最佳的序列长度为N的时间为O（N1.73 N）？> .我们计算了N ≤ 66？>以及N ≤ 119？> .
Binary sequences with minimal autocorrelations have applications in communication engineering, mathematics and computer science. In statistical physics they appear as groundstates of the Bernasconi model. Finding these sequences is a notoriously hard problem, that so far can be solved only by exhaustive search. We review recent algorithms and present a new algorithm that finds optimal sequences of length N in time O ( N 1.73 N ) ?> . We computed all optimal sequences for N ≤ 66 ?> and all optimal skewsymmetric sequences for N ≤ 119 ?> .