Feedback shift registers (Q792769)

In many problems of discrete mathematics there appear infinite sequences satisfying the following recurrence equation: \[ x_{i+n}=f(x_ i...x_{i+n-1}), \] where \(f:K^ n\to K,\) and K is in general a Galois field. From a technical point of view such sequences may be generated by physical objects, called n-stage feedback shift registers. A theory of these objects, inspired by practical applications, has been developed since more than twenty years. Till now its development was based on classical algebraic methods. The reviewed book is an attempt for a new point of view of some aspects of the theory of shift registers. Its main purpose is to create a specific algebraic tool allowing a uniform description of most of the known facts. The central point of the presented theory is the notion of unitary ideal (as a special case of some structure composed from operators acting on sequences) and its equivalence to a set \(\tau\) of all sequences generated by some shift register, whenever \(\tau\) is closed with respect to the shift operation (i.e., if \(s_ 1s_ 2...\in \tau,\) then \(s_ is_{i+1}...\in \tau\) for each natural i). Most of the further obtained results are consequences of this equivalence. These are, in particular, simpler proofs of theorems from \textit{E. S. Selmer's} work: ''Linear recurrence relations over finite fields'' (Bergen, 1966). It also surveys the known randomness properties of sequences generated by feedback shift registers, as well as many other problems. The clear conception of the discussed book is, in my opinion, somewhat destroyed by the less clear system of notations. The author gives some incorrect formulations which imply that Proposition 28 and 29 are false. I also suppose that Definition 21 is not correct. Apart from the above remarks I think that the reviewed book is a valuable item in the literature on shift registers, especially as a starting point to further research. The presented theory implies many new problems whose formulation and solution will enrich the knowledge about shift registers.