Wreath products and cascaded FSRs

Abstract

We show that the transition function of the cascaded connection of two FSRs can be viewed as an element of an imprimitive wreath product. This allows us to study periods of cascaded connections with algebraic methods, obtaining both a general, nontrivial upper bound on the maximum period of a cascaded connection and a complete, explicit understanding of the periods in the important case of the cascaded connection of an n-dimensional de Bruijn sequence into an m-dimensional linear FSR.