Crosscorrelation of m-sequences with decimation d = (pl + 1)/(pk + 1)
Aina Johansen, Tor Helleseth · 2008
The crosscorrelation between two m-sequences of period pm- 1 that differ by a decimation d is a well studied problem. In 1970 Trachtenberg showed that for odd m the two decimations d = (p2k+ 1)/2 and d = (p3k+ 1)/(pk+ 1) have three-valued crosscorrelation and their correlation distribution was determined. This result was extended by Helleseth to the case m/ gcd(m, k) odd and who noted that the long and complicated proof of Trachtenberg could be modified to this case. We present a more direct and self-contained short proof of Helleseth's generalization of Trachtenberg's result for the second case. Furthermore, we show that the decimation d = (p5k+1)/(pk+1) has at most five-valued crosscorrelation when m/ gcd(m, k) is odd.