Abstract

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.

The 2023 IEEE International Symposium on Information Theory was held at Taipei International Convention Center (TICC) in Taipei, Taiwan, from June 25 to June 30, 2023 [Conference Website].