Aliasing Probability in Multiple Input Linear Signature Automata
Geetani Edirisooriya, John P. Robinson · 1991
The aliasing probability in single and multiple input Linear Automata Signature Registers (LASRs: Linear Feedback Shift Registers (LFSRs) and Linear Cellular Automata) has been widely studied under the independent bit error model. This paper examines aliasing in a class of Multiple-Input LASRs (MILASRs), under the q-ary symmetric error model. By modeling the signature analyzer as a two-state Markov process, we show that the closed form expression derived for aliasing probability in [14], for multiple-input LFSRs with primitive polynomials holds for a far more general class of linear automata signature analyzers, including all multiple-input LFSRs. An easily verifiable criterion is given to determine whether a MILASR falls into this category. Finally we show that for q-ary symmetric errors, the circuit complexity and the propagation delay can be minimized by using a set of m single bit LFSRs.