The LFSR: The Queen of Digital Logic Functions
I have a theory that every engineer has his or her favorite fundamental design, component, or function. If we were to generalize by domain, then — in the case of analog engineers — I think most would opt for the op-amp (operational amplifier) as their component of choice.
When you implement a function like an amplifier using an individual transistor, the additional components you use to bias the transistor into its active region and to control the gain and feedback are typically shared, which means the various aspects of the circuit are intertwined. Much the same thing happens with vacuum tubes.
By comparison, the additional components that control an op-amp’s gain are different from those used to control its feedback, so everything is nicely isolated and partitioned. Furthermore, an op-amp can be used to implement myriad functions and perform a cornucopia of tasks, such as amplification, comparison, addition, multiplication, differentiation, integration, creating a high-pass filter, creating a low-pass filter, and providing feedback control.
Having said all this, I’m a digital hardware design engineer by trade. As far as I’m concerned, the logic function that stands proud in the digital crowd is the linear feedback shift register (LFSR). In order to wrap our brains around this, let’s start by considering a simple 4-bit serial-in, parallel-out (SIPO) shift register:
I’m sure that the operation of this little beauty is well known to most readers, but just in case any newbies are reading this (or managers, bless their little cotton socks), the way it works is as follows. The shift register in our example is formed from four positive-edge-triggered D-type flip-flops. A positive (rising or 0 to 1) edge on the clock signal will cause each of the D-type flip-flops to load whatever values they see on their d (data) inputs; after a short delay, these values will appear on their q outputs.
Let’s assume that we have some way of clearing all the flip-flops to contain 0s. The first clock will load whatever value is on the Serial-in signal into DFF0. At the same time, it will load whatever was in DFF0 into DFF1, whatever was in DFF1 into DFF2, and whatever was in DFF2 into DFF3.
Not surprisingly, the reason we call this a SIPO register is that we clock the data in serially and we read it out in parallel. Now consider what happens when we make a tiny modification — adding a 2-input XOR gate — as shown below:
As if by magic, we’ve transformed our humble SIPO shift register into a glorious linear-feedback shift register (LFSR), but what does this mean? Well, for the purposes of this column, let’s assume we have some way of initializing the register so that it contains all 1s. Now consider what will happen when we clock the register as illustrated below:
As we see, the register pseudo-randomly cycles through all the possible patterns, except 0000, before returning to its initial condition. (If we had used an NXOR gate and started with any pattern other than 1111, then our LFSR would have cycled through every pattern, except 1111, before returning to its starting point.)
I can’t even begin to describe the myriad tasks for which an LFSR can be employed, although one obvious application is that of a pseudo-random number generator. And these little beauties also find use with regard to generating cyclic redundancy checks (CRCs) and in encryption and decryption applications.
How about you? Do you agree with me that the LFSR is the Queen of digital logic, or would you argue on behalf of a different function?
