(Again, see that article on easy discrete logarithms for details.) It is therefore advantageous to use an LFSR with a period that is smooth - that is, it consists of the product of a bunch of small factors, so that the Silver-Pohlig-Hellman algorithm can be used to decode the count. The challenge in this sort of application is not implementing an LFSR, but rather in decoding the count from the LFSR state, which amounts to a discrete logarithm. If the polynomial is a primitive polynomial, then the LFSR cycles through all nonzero patterns, for a total of \( 2^ N-1 \) states in an \( N \)-bit LFSR, after which the same series repeats, having a period of \( 2^N-1 \). All you need to construct an LFSR is a bunch of flip-flops and a couple of XORs, one for each nonzero term in the characteristic polynomial. The idea here is that the propagation delay in an LFSR is smaller than in a counter, since the logic to compute the next LFSR state is simpler than in an ordinary counter. I mentioned counters briefly in the article on easy discrete logarithms. Today we are starting to look in detail at some applications of LFSRs, namely counters and encoders. Last time we looked at LFSR output decimation and the computation of trace parity.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |