[HN Gopher] Understanding Linear Feedback Shift Registers in FPGAs
___________________________________________________________________
Understanding Linear Feedback Shift Registers in FPGAs
Author : signalhound
Score : 71 points
Date : 2024-04-03 11:14 UTC (2 days ago)
(HTM) web link (www.adiuvoengineering.com)
(TXT) w3m dump (www.adiuvoengineering.com)
| artemonster wrote:
| I have used LFSR counter as a program counter in my relay CPU.
| Instead of building a 12bit half adder that increments +1 that
| would require 12 relays I got away with only 3 XORs and 3 relays.
| When assembling, the linker just scrambles program memory
| according to LFSR counting pattern and I get +1 counting
| behaviour :) This technique is used for some very tiny hard-coded
| CPUs (where program memory is not even ROM, but directly decoded
| datapath control, like decoded microops in real CPUs) that really
| need to save on area.
| JoeAltmaier wrote:
| How about Grey code? It's a one-bit change to 'increment'.
| Wonder if that would be about as simple.
|
| FYI conversion between normal binary and grey code is to simply
| XOR successive pairs of bits.
| artemonster wrote:
| grey code is heavy on combinational logic to implement, its
| goal is not to reduce logic but force counting behaviour in
| such a way that only 1 bit is changing between transitions,
| as opposed in normal binary (i.e. 4b0111+1 would cause 4 bit
| changes). this is useful when crossing clock domains or to
| add extra builtin error detection capabilities
| JoeAltmaier wrote:
| Used to use it for contact-switches. You turn a knob, say
| four brushes slide across copper contacts to encode knob
| position. If you coded position in binary you'd be sparking
| several bit-changes which for some instants would jump all
| over the number range, e.g. from three (011) to four (100)
| could instantaneously go to seven (111) or two (010) etc.
|
| Grey code would at most oscillate between the two values
| e.g. from 010 (three in Grey Code) to 110 (four in Grey
| Code).
| kevin_thibedeau wrote:
| Gray code can be implemented with an ordinary binary
| counter and an XOR with a right-shifted count. It isn't
| particularly "heavy".
| artemonster wrote:
| Sorry, after doing extremely low area designs every extra
| useless gate is ,,heavy" :)
| oasisaimlessly wrote:
| The thing you're missing is that an LFSR counter can be
| 20% of the gates of a binary counter.
| meindnoch wrote:
| The original comment was precisely about avoiding an
| ordinary binary counter.
| mzs wrote:
| Nintendo's CIC did a similar ting for the same reason, a
| polynomial counter though:
| https://forums.nesdev.org/viewtopic.php?p=55288#p55288
| artemonster wrote:
| also FYI: so called "golden codes" that are used to modulate GPS
| information bitstream are also bunch of LFSR counters and chosen
| in such a way that the whole set of them (around 30? dotn
| remember) has a very low correlation factor between them
| willis936 wrote:
| This is how PRBS works more generally. It's in everything. Use
| the same factors and set the start point.
|
| Iiuc what you're describing is using different sets of factors,
| which would guarantee low correlation, if differing spectra.
|
| https://en.wikipedia.org/wiki/Pseudorandom_binary_sequence
| kurthr wrote:
| Yes, for LFSRs it is often the high ratio of auto/cross
| correlation for the particular encode phase, along with the
| ease of generation and deconvolution for single bit signaling
| at low SNR. I don't know that most other pseudo-random codes
| have this property.
| andyjohnson0 wrote:
| > so called "golden codes"
|
| A minor point, but they are called _Gold codes_ -- after Robert
| Gold, who developed the technique in the 60s.
|
| https://en.wikipedia.org/wiki/Gold_code
| kurthr wrote:
| There are also the related Kasami codes. Both are made by
| selecting uncorrelated LFSR sequences and combining them.
| That has the advantage of extending code length, while
| maintaining cross-correlation and whiteness properties.
| Really helpful in early error correction.
| dietrichepp wrote:
| I have a more mathematical / software oriented article about
| LFSRs here:
|
| https://www.moria.us/articles/demystifying-the-lfsr/
| dfawcus wrote:
| FWIW - The DVD CSS scheme is build upon a couple of LFSRs.
| They're then combined in 4 different ways (XOR of the streams,
| as is or inverted).
|
| Three of the combinations are used for the "authentication"
| portion (as used by s/w), the other combination for the
| "encryption" portion.
| jhallenworld wrote:
| I used LFSRs all the time in early FPGAs (XC2000 and XC3000
| series). These did not have fast carry chains, so LFSR made a
| much faster counter than binary. Used them for video timing
| generators.
___________________________________________________________________
(page generated 2024-04-05 23:02 UTC)