Cross correlation of m-sequences : An overview and recent results on five-valued correlations
Speaker: Tor Helleseth (University of Bergen, Norway)
Time: 4:00PM
Date: Mon 7th April 2008
Location: Mathematical Sciences Seminar Room
Abstract
Let {a_t} and {b_t} be two binary sequences of period n. The crosscorrelation function between these two sequences at shift ?, where 0 ? ? < n, is defined by
C(?) =sum_{t=0}^n (-1)^{a_{t+?}+b_t}. A maximal linear sequence, or an m-sequence, is a sequence {s_t} of period 2^m?1 that obeys a linear recursion with characteristic polynomial being a primitive polynomial. There are numerous applications of m-sequences in moderncommunication system. Finding the cross correlation between two m-sequences {s_t} and {s_dt} of the same period 2^m? 1, that differ by a decimation d where gcd(d,2^m?1) = 1, is a problem that has been thoroughly studied for the last 40years.
In the first part of the talk we give an overview of known results on three and four-valued cross correlation as well as a discussion of some open general problems in this area. In the second part we present some recent results devoted to special values of d of the form d =(2^l+ 1)/(2^k+ 1).
In some cases these are known to lead to at most five-valued cross correlation. In particular Kasami and Welch showed that the cross correlation is three-valued
for l = 3k. The complete correlation distribution for other values of k and l that frequently lead to five-valued correlation is an open problem. We discuss the apparently simple and previously unsolved special case when l = 2k, k = 1 and m odd. The correlation distribution is completely determined and showed to be five-valued. The results are proved by using evaluations of several exponential sums including Kloosterman sums that may explain why related cases appear rather hard to solve.
(This talk is part of the Algebra/Claude Shannon Institute series.)
Social Media Links