Applications of one-dimensional cellular automata and linear feedback shift registers for pseudo-exhaustive testing

摘要

Recent studies have shown that cellular automata (CA) can be used in place of linear feedback shift registers (LFSRs). Due to their regular structure and local feedback connections, VLSI layout of CA is easy and results in saving silicon area. Some properties of CAs derived using Rules 90 and 150 in terms of characteristic polynomials are presented. In particular, (a) computation of characteristic polynomials in CA, (b) computation of sequence lengths generated by various CA/LFSRs, and (c) pseudo-exhaustive testing by sequences generated by CA/LFSRs are accomplished.