## Binary linear feedback shift register sequences

When
Start: 02/08/2012 - 4:15pm
End  : 02/08/2012 - 5:15pm

Category
Colloquium

Speaker
Solomon Golomb (USC)

Abstract

A binary linear feedback shift register sequence (BLFSRS) of degree n, $A ={a_k}_0^\infty$, is described mathematically by a linear recurrence relation $a_k = \sum_{i=1}^n c_i a_{k-1}$ over GF(2), plus an initial state $(a_{-1}, a_{-2}, …, a_{-n})$. The characteristic polynomial of the corresponding shift register is  $f(x) = x^n + \sum_{j=1}^n c_j x^{n-j}$. The period of the sequence A depends on its initial state and properties of f(x). If A has its maximum possible period of $2^n – 1$ it is called an m-sequence. Such sequences have a number of interesting (pseudo)-randomness properties, which are described. Interesting results and open problems are enumerated.