Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!ncrcom!ncrlnk!ncr-mpd!Mike.McManus From: Mike.McManus@FtCollins.NCR.com (Mike McManus) Newsgroups: sci.electronics Subject: Re: Pseudo-random numbers Message-ID: Date: 4 Apr 91 09:01:35 GMT References: <1991Mar27.101754.5326@specialix.co.uk> Sender: uucp@ncr-mpd.FtCollins.NCR.COM Distribution: sci Organization: NCR Microelectronic Products, Ft. Collins, CO Lines: 35 In-reply-to: stevem@specialix.co.uk's message of 27 Mar 91 10:17:54 GMT (Couldn't get this to go via email.) I'll admit up front that most of what little I know about Linear Feedback Shift Registers (LSFRs) comes from a 3-day "survey" class on testability techniques, so it's not terribly complete, but here goes... You are looking for what are colled "primitive polynomials", those which are irreducible (no factors) and for which the smallest positive integer that allows the polynomilal to divide evenly (modulo 2) into (x^r + 1) is r = 2^m - 1. It can be shown that such primitive polynomials can be used to describe maximal length LSFRs (based on the degree of the polynomial). Research has been done on the subject (and the table you are looking for compiled) by W. W. Peterson and E. J. Weldon, though I don't have an exact reference for you. One possibility might be "Error-correcting Codes", 2nd Ed., The Colonial Press, 1972 (at least that's the reference stated in my class notes). Not sure if their table goes up to degree 33, though! As far a start-up state of the circuit, you will need to set the seed yourself to make sure it's not 0. Having a power-on circuit to set at least one element of your LFSR to 1 should suffuce, with the rest reseting randomly. In some sequencial circuits, however, the starting seed condition may be very important if you are trying to produce pseudo-ramdom test patterns! Good luck. -- Disclaimer: All spelling and/or grammar in this document are guaranteed to be correct; any exseptions is the is wurk uv intter-net deemuns,. Mike McManus Mike.McManus@FtCollins.NCR.COM, or NCR Microelectronics ncr-mpd!mikemc@ncr-sd.sandiego.ncr.com, or 2001 Danfield Ct. uunet!ncrlnk!ncr-mpd!garage!mikemc Ft. Collins, Colorado (303) 223-5100 Ext. 378