Synthesis of minimal cost nonlinear feedback shift registers (Q5958504)

This paper is concerned with the determination of the ``minimal'' nonlinear feedback shift register (NLFSR) that generates a given sequence. A total ordering between structural vectors that takes into account the implementation cost is specified. Minimality is defined with respect to this ordering. A block as well as a sequential algorithm are developed that combine a linear dependence test implemented by an extension of the fundamental iterative algorithm (EFIA) with a minimality procedure that traces the totally ordered structural vectors.