[AT-1] 組合せ論と情報理論 −最新動向と展望−

[AT-1-4] The resolution of the existence of asymptotically optimal difference systems of sets

Yuichiro Fujiwara (Chiba Univ.)

Keywords:synchronization、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.