The Ding-Helleseth-Martinsen Sequences: A Breakthrough in 32 Years


In 1969, Sedelnikov constructed a class of binary sequences of length n = 2 (mod 4) with optimal autocorrelation values 2 and -2 [V.M. Sidelnikov, Some k-valued pseudo-random sequences and nearly equidistant codes, Problemy Perrdaci Informacii 5 (1969) 16--22]. This class of sequences were rediscovered by Lempel, Cohn and Eastman in 1977 [see, IEEE Trans. Information Theory 23 (1977) 38--42]. Thirty-two years later in 2001, Ding, Helleseth and Martinsen discovered a few classes of new binary sequences of length n = 2 (mod 4) with optimal autocorrelation values 2 and -2: 


Their paper was published in: IEEE Trans. Information Theory 47 (2001) 428--433. 


These sequences were later named as Ding-Helleseth-Martinsen sequences in many papers.


No other binary sequences of length n = 2 (mod 4) with optimal autocorrelation values are known. Details about these constructions and open problems can be found in the following slides: 


Lecture slides on binary sequences with optimal autocorrelation 


The reader is invited to attack the open problems presented in the slides.

Back to the previous page