Date: Tue, 25 Jun 1996 10:29:13 -0700 (MST) From: Don Yuniskis <dgy@rtd.com> To: jmb@freefall.FreeBSD.org (Jonathan M. Bresler) Cc: freebsd-hackers@freefall.FreeBSD.org (FreeBSD hackers) Subject: Re: LFSR Message-ID: <199606251729.KAA11616@seagull.rtd.com> In-Reply-To: <199606251709.KAA18295@freefall.freebsd.org> from "Jonathan M. Bresler" at Jun 25, 96 10:09:38 am
next in thread | previous in thread | raw e-mail | index | archive | help
> don, > what's an LFSR? and where can i get one? Alfonzo's Produce Market has them on sale -- 5 pounds for a dollar (but make sure you get *fresh* ones... once they get stale, they aren't worth a damn...) Linear Feedback Shift Register -- a common technique used to produce "pseudo-random" numbers. A shift register of N bits is implemented (in this case, in software). Particular bits from the shift register are combined to form the "next" bit to be shifted into the register. By selecting a good N and carefully picking the bits to be combined, you can generate an arbitrarily long sequence of shift register values (you can, of course stroke the register multiple times to ensure that each M -- M < N -- bit sample from the register is not closely related to the previous sample). One advantage to this for memory testing is that it can be readily repeated. So, initialize the LFSR with a value X. Extract an 8 bit (or 32 bit, etc.) sample from the register and store it into memory. Advance the pointer to the next memory "location" (word, byte, etc.) and update the LFSR. Repeat until memory is full. Now, you have some hodgepodge of values in memory. Restart from the first address with a REINITIALIZED (that's "reinitialised" for you folks across the pond :>) LFSR and do a read/compare cycle to verify the contents of memory are unperturbed. This process (write then read/compare) can be repeated several times using different initialization values (i.e. at the start of each write/fill pass, use the *ending* value of the LFSR from the previous read/compare cycle to initialize the LFSR). It's not "exhaustive" but it gives a very fast check of the memory array with unstructured data. It's also pretty tiny to implement. I use this technique often in POST (Power On Self Test) for the embedded products I design. There, you have a fraction of a second to get some feel for any major failures that have crippled the hardware. The "fill all then check" approach is used just to give some added test of refresh failure (years ago, this was an issue... now it's not worth the trouble...) by letting the array sit dormant for a while. > I find use of a LFSR with a long, "relatively prime" period "Relatively prime" ensures that the pattern doesn't repeat in some way that is "realted" to the organization of the memory array. For example, if the LFSR produced samples like 0x00, 0xFF, 0x00, 0xFF :> it wouldn't be very good at detecting a decode error that affected odd (or even) addresses. Whereas 0x00, 0x00, 0xFF (still a pretty lame pattern) *would* detect that failure (0x00, 0x00, 0xFF, 0x00, 0x00, 0xFF, etc.) --don
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?199606251729.KAA11616>