The Asymptotics of Difference Systems of Sets for Synchronization and Phase Detection
The Asymptotics of Difference Systems of Sets for Synchronization and Phase Detection
复制标题
DOI：
10.1109/isit54713.2023.10206585
复制
发表时间：
2023-06
期刊：
影响因子：
--
通讯作者：
Y. Tsunoda;Yuichiro Fujiwara
中科院分区：
文献类型：
--
作者：
Y. Tsunoda;Yuichiro Fujiwara
我们解决了确定最优差分集合系统（简称 DSS）参数的渐近行为的问题，该系统最初是为了在存在加性噪声的情况下计算高效的帧同步而引入的。我们证明，对于任何字母表大小和相对索引，DSS 的最低可实现冗余渐近达到 Levenshtein 的下界，回答了 Levenshtein 在 1971 年提出的问题。我们的证明是概率性的，并给出了一种线性时间随机算法，用于在任何字母表大小和信息率下以高概率构造渐近最优 DSS。这提供了具有强大抗噪能力的高效自同步代码。我们还指出了 DSS 在相位检测中的应用。
We settle the problem of determining the asymptotic behavior of the parameters of optimal difference systems of sets, or DSSes for short, which were originally introduced for computationally efficient frame synchronization under the presence of additive noise. We prove that the lowest achievable redundancy of a DSS asymptotically attains Levenshtein's lower bound for any alphabet size and relative index, answering the question of Levenshtein posed in 1971. Our proof is probabilistic and gives a linear-time randomized algorithm for constructing asymptotically optimal DSSes with high probability for any alphabet size and information rate. This provides efficient self-synchronizing codes with strong noise resilience. We also point out an application of DSSes to phase detection.