title title title title


SteamEng

Linear Feedback Shift Register


You're probably familiar with shift registers, but in a nutshell these are multi-element resisters that are rigged to read serial data in and expell it in a parallel fashion or vise-versa. They can also shift data left or right within the resister. There are a lot of designs that interface various bus structures so have unique output buffers to match those designs. But in the case of a Linear Feedback Shift Register (LFSR) the objective is to spit out the longest stream of data we can in a random bit pattern. This is done by using exclusive OR gates to reintroduce various bits back into the resister as it continues to shift. There is a mathematical basis for this hardware arrangement of complex polynomials with the net result of the number of random bits is 2 to the N minus 1, because feeding back a zero would stop the shift. So that combo is left out.

You're probably asking yourself what's this good for. Consider this: if you have a pseudo-random data stream coming in on one input to an XOR gate and good data on a second input, the output stream is now encrypted in a random manor. If you know how to re-create the pseudo-random stream at the other end of a transmission, you can repeat the process with the incoming data and retreive the original "good data." Cool.

So who does this in the real world? Cellphones for one. Of course, a software model of this is also possible based on the math model, but it turns out the hardware version is very efficient compared to the massive data crunch of the software version. The downfall of the hardware version is it can be predicted, copied and a decoder built real easy. So what's a spy to do? If you change the parallel word on the bit inputs of the LFSR on the fly, but the pattern is known to the receiver, the random transmission is very hard to decypher except for this well informed receiver. If you use large prime numbers as the seed words, it's nearly impossible to decode, because the only way to break the code is to use brute force calculations. So currently, this sort of circuit is being used in high-end encryption with a processor supplying the seed words and hardware generating the data stream. For no other reason, I was curious, so I built one.

I kept it simple to study how it works, and I have no reason to get into complex math or software algorithms, so I'm just using hardware and a oscilloscope to gaze at the random pattern. There is another reason I was interested in building up a working model. When I was a young engineer working for Texas Instruments, actually GSI their oil exploration branch, we needed to test a new digital transmission/receiver idea. I used a LFSR to supply a random feed that could be duplicated by the receiver. I then blend the incoming data with the local copy via a XOR gate. If the output remained zero, I knew none of the data was lost during transmission. I had counters to tally bit losses, but it worked great and we didn't get a dropout in six weeks of running the system from two building tops about a mile apart. There is a little more to this story. The transmission medium was a commercial voice radio. It was used by the oil crews, so was readily available. The data was frequency shift modulated between 1000 Hz and 2000 Hz so it could be received within the audio band of the radio. I used a phaselock loop on the reciever to get sync'd up so the data coming in was exactly in time with the local digital timing. Now the trick was to catch the repeating pattern when the pseudo-random pattern came around again. The cool thing is (24 bit shift register) I had three bytes that I could taylor by loading that pattern into the shift register at the start. Those 3 bytes could be seen at the other end and gated to start the other LFSR(of course, 3 bytes later to be in sync). The pattern was 16,777,216 bits long. We thought that was enough randomness to validate the receiver. Not to keep you hanging, we needed to transmit bit patterns between vibrator trucks that shook the ground precisely at the same time to generate a sonic wave to be picked up by geophones. These data words were seen in each truck and they knew when the pattern would end even if they came in late. The trucks would correlate to the pattern, set a timer so at the point the pattern completed, the vibrations would start. Can't tell you how exciting that was to feel a frequency swept earthquake. Very cool. In the field we use the 1000 Hz bit as a LOW and a 2000 Hz bit as a HIGH. Enough about the past. Lets build a LFSR.

There's actually two parts to this project. First we need a clock for the LFSR. I built an 32-bit count-down circuit based off a 24 MHz can-clock module. That gave we a bunch of frequencies to run the LFSR with. I also used a 555 timer to load and run the counter and the LSFR. The LFSR was a column of 74LS194 shift registers and the frequency divider counter used 74HC191 counters. The 555 chip produces a pulse the goes low then high to load and run. I needed to invert the pulse, so there is a 74HC14 hex inverted chip on the breadboard as well. I used my off-board debounce board to trigger the 555. All of this gives me a lot of places to put a scope lead and see what's going on.

With all this switching of ones and zeros at high speed, these chips need to be properly bypassed, which is a fancy way of saying place a 0.1uF cap across the +5V and Gnd of each chip to avoid a lack of electrons at the point when things go from all ones to all zeros of vise- verse. If you don't, you can get glitches that are very hard to find.

Let's pop over to another page and layout the circuits. Click here.


parts