Constructing Binary Sequences With Good Correlation Properties: An Efficient Analytical-Computational Interplay

Binary sequence sets with asymptotically optimal auto/cross correlation peak sidelobe level (PSL) growth have been known in the literature for a long time, and their construction has been studied both analytically and numerically. In contrast, it has been a long-standing problem whether we can construct a family of binary sequences whose auto-correlation PSL grows in an optimal manner. In this paper, we devise a construction method of binary sequences with asymptotically optimal PSL growth from the sequence sets with good correlation properties. A key component of the design follows from the observation that if the PSL of the sequence set grows optimally or nearly optimally, then the PSL of the constructed binary sequence will experience a similar growth as a consequence. The proposed construction is simple-to-implement, and is shown to be accomplished in polynomial time. With such a construction, we not only bridge the gap between analytical construction and computational search, but also pave the way to settle the long-standing design problem of binary sequences with an optimal growth of the auto-correlation PSL.