A fast signature computation algorithm for LFSR and MISR

A multiple-input signature register (MISR) computation algorithm for fast s ignature simulation is proposed. Based on the table look-up linear compacti on algorithm and the modularity property of a single input signature regist er (SISR), some new accelerating schemes-partial-input look-up tables and f lying-state look-up tables-are developed to boost the signature computation speed. Mathematical analysis and simulation results show that this algorit hm has an order of magnitude speedup without extra memory requirement compa red with the original linear compaction algorithm. Though this algorithm is derived for SISR, a simple conversion scheme exists that can convert inter nal-EXOR MISR to SISR. Consequently, fast MISR signature computation can be done.