Pseudo-random bits

A lot of this site needs bits that look random without being random: the pseudo-random codes on Finding signals below the noise, the noise waveform of the SID chip, the CRC on the error-correcting codes page. They all come from the same tiny circuit: a linear-feedback shift register, or LFSR. This page takes it apart.

1 · A shift register that feeds itself

A shift register is a row of one-bit memories: on each step, every bit moves one place along, the last one falls out, and a new one comes in at the start. Feed it its own bits back, XORed together, and it runs by itself: each new bit is the XOR of a few chosen bits, the taps, and the bits that fall out are the output.

out, the latest last

The register written out like a sum, its columns lined up by bit. Its bits, then the taps (click one to switch it on or off), then the bits that are both in the register and tapped, and the XOR of those: 1 if an odd number of them are 1. Step it: everything shifts one place left, the bit leaving bit n joins the output, and the XOR goes round to come in as the new bit 1. The hex beside each row is its value as a number. The taps chosen at first are a good choice: they visit every state but one before repeating. Change them and see.

The register has only so many states (16 for 4 bits), and each state decides the next, so sooner or later it comes back to one it’s been in, and repeats from there. One state is a trap: all zeros. Every tap reads 0, so the XOR is 0, and it stays all zeros for ever. So the longest it can possibly go is every other state: 2ⁿ − 1 steps.

2 · Which taps go the longest?

Not every choice of taps reaches 2ⁿ − 1. First, the oldest bit, bit n, must always be a tap. If it isn’t, it never affects anything fed back: the new bits are decided by the bits up to the highest tap alone, so the register is really a shorter one with a delay on its output, and repeats at least as soon as the shorter one does. (And two states that differ only in that top bit lead to the same next state, so it can’t go round all of them.) Here’s every choice for a 5-bit register with bit 5 tapped:

Every set of taps for a 5-bit register that includes bit 5, as bits (bit 5 on the left, as the register is written in section 1; 1 for a tap), in hex, and as a list, with how many steps it takes to come back to where it started (from the state 00001). Six of the sixteen go all the way round the 31 states; the rest fall into shorter loops, and miss most of the states altogether.

The good ones are no accident. The taps describe a polynomial (taps 5 and 3 are x⁵ + x³ + 1), and the register goes the whole way round exactly when that polynomial is primitive: it can’t be factored, and more besides. Which polynomials are primitive is the subject of a lot of algebra (the cryptography site’s finite fields page works through why, with this table), but for practical purposes it’s a table to look up: every size of register has some, and this page uses the ones in Xilinx’s application note on LFSRs (all checked to give 2ⁿ − 1 steps, up to 20 bits). The sequence such a register makes is a maximal-length sequence, or m-sequence.

3 · As noise

An m-sequence looks random in all the ways that are easy to check. Over a whole period there are 2ⁿ⁻¹ ones and 2ⁿ⁻¹ − 1 zeros: as close to half and half as an odd number allows. Runs of the same bit come in the proportions coin tosses would give: half of them one bit long, a quarter two long, and so on. And its spectrum is flat: white noise.

So it’s how digital synthesisers make noise. The SID chip has a 23-bit register, and takes 8 of its bits as a sample. But the chip doesn’t step it every sample: it steps it each time its oscillator passes a certain point, which happens 16 times per cycle of the voice’s frequency. Between steps the sample holds still. That gives the noise a pitch.

Noise from the SID’s own register (23 bits, the same taps and the same 8 output bits as on the chip), at 48,000 samples a second, with a new value every so many samples and held between. The spectrum is averaged over 8 blocks. Stepping every sample, it’s nearly flat, with one dip, at a quarter of the stepping rate: the chip’s 8 output bits sit 2 to 4 places apart in the register, so each sample shares some of its bits with the one two steps later (their correlation is 0.38). Held, it goes quiet at every multiple of its stepping rate (dashed): the noise becomes a rushing whose pitch follows the note. Listen.

Holding a value for a while makes each step a little block, and a block’s spectrum goes to zero at every multiple of 1 / its length. That’s what drums on the C64 are made of: noise for a moment at a high pitch, a snare, or a low one, a thud.

4 · One sharp peak

Here’s the property that makes m-sequences precious in communications. Compare the sequence with itself shifted: count where the two agree, take away where they disagree. At no shift it agrees everywhere. At every other shift (going round the period) it disagrees exactly once more than it agrees: the answer is −1, every time.

The autocorrelation of an m-sequence (agreements minus disagreements, with itself shifted, all the way round) against the same number of random bits. The m-sequence’s is one sharp peak and −1 everywhere else; the random bits’ wanders, by up to 29 for 127 bits here. Choose a longer register: the peak grows, the m-sequence’s floor stays at −1.

Exactly −1, at every shift, sounds too neat to be true, and it is: it comes from two facts, neither of them luck.

Balance. A maximal-length register visits every state except all-zeros once a period. Half of all 2ⁿ states have a 1 in the bit that’s output, and the one state left out has a 0 there, so a period has exactly one more 1 than 0 (section 3’s 2ⁿ⁻¹ ones and 2ⁿ⁻¹ − 1 zeros).

Shift-and-add. XOR the sequence with a shifted copy of itself, and the result is the same sequence again, at some other shift. Both copies follow the register’s rule (each bit is the XOR of the bits at the taps’ distances back), and the rule is linear, so their XOR follows it too: it’s the same register, run from some other state. Its state isn’t all zeros (a shifted copy isn’t the same as the original), and a maximal register has only one loop, so it’s the same sequence. For 3 bits:

the sequence          1 1 1 0 1 0 0
shifted by one        1 1 0 1 0 0 1
XOR                   0 0 1 1 1 0 1    the sequence again, starting from its sixth bit

A 1 in the XOR is a place where the two disagree. The XOR is the sequence, which has one more 1 than 0: so there’s one more disagreement than agreement, and the answer is −1 (here 4 disagree, 3 agree). Why not 0? The period, 2ⁿ − 1, is odd, so agreements minus disagreements is odd too: −1 is as close to 0 as it can get.

So it’s a sign of structure, not of randomness. Truly random bits wander by around the square root of their length (the grey line); a sequence that comes out −1 at every one of its shifts gives itself away as an m-sequence at once. For finding signals that’s exactly what’s wanted; for keeping a secret it’s the first crack, which section 7 opens up.

A sharp peak and a flat floor are exactly what finding a signal needs: correlate what’s received with the code, and the peak says the code is there and exactly when it arrived, with nothing at the other shifts to be mistaken for it. That’s pulse compression in radar and sonar, the spreading codes GPS satellites send (Gold codes, made by XORing two m-sequences), and the m-sequences played through loudspeakers to measure rooms.

5 · The same circuit, dividing: CRCs

Turn the register round a little: instead of only feeding back its own bits, feed in a message, a bit at a time, XORed in with the feedback. When the message has gone through, the register holds what’s left over from dividing the message by the taps’ polynomial (in arithmetic where adding is XOR). That remainder is the CRC, the check that catches errors on the error-correcting codes page.

The modem’s CRC-16 (polynomial x¹⁶ + x¹² + x⁵ + 1, starting from all ones), computed as hardware does: a 16-bit register, the message’s bits fed in one at a time. Each step the register shifts, and if the bit leaving the top doesn’t match the bit coming in, it’s XORed with the taps. What’s left at the end is the CRC: the same number the site’s CRC function gives (checked in the tests). Change the message: one character changes everything after it.

A CRC is cheap in hardware for the same reason an LFSR is: sixteen flip-flops and three XOR gates check a message of any length, a bit at a time, as it goes past.

6 · Scrambling

A receiver keeps its timing by watching the bits change. A long run of the same bit, all zeros say, gives it nothing to lock onto, and real data has plenty of those (silence in a sound file, blank parts of an image). So many systems scramble the data first: XOR it with an m-sequence. Zeros become the m-sequence itself, which changes often; at the far end, XORing with the same sequence (from the same start) gives back the data.

Data scrambled by XORing with a 7-bit LFSR’s sequence (x⁷ + x⁴ + 1, as Wi-Fi uses), then unscrambled by doing the same again. A run of 128 equal bits comes out with no run longer than 7; unscrambled, it’s exactly the data again.

Scrambling isn’t encryption: anyone who knows the standard knows the sequence. It only makes the data look busy.

7 · Not a secret

It might seem that a long LFSR, kept secret, would make a good cipher: XOR the message with its output, and only someone with the same register could undo it. It doesn’t, because the register is linear: every output bit is an XOR of earlier ones, always with the same rule. Given some output, that rule can be solved for, like any set of linear equations. The Berlekamp–Massey algorithm does it efficiently: it finds the shortest register that makes the bits seen so far, and needs only twice the register’s length in bits to find it exactly.

A hidden register (with taps from the table and a starting state you can change), and Berlekamp–Massey watching its output. The plot is the length of the shortest register that explains the bits seen so far: it climbs, and settles on the true length once twice that many bits have been seen (dashed). From there it predicts the rest of the output without a single error. Here its rule comes out with the same numbers as the register’s taps.

A 23-bit register gives itself away in 46 bits. If its taps are already known, it’s quicker still: its starting state is just where in its one loop it began, which correlating with the known sequence finds (the peak is at the offset: it’s how a GPS receiver lines its code up with a satellite’s), and in the form on this page any n output bits in a row simply are one of its states, from which it can be run on.

Even seeing only some of its bits is enough. Imagine a radio that hops from frequency to frequency, choosing each next channel from a few bits of an LFSR’s state, so that only a receiver with the same register knows where to listen next. Someone listening across the whole band sees which channel each hop lands on, so learns those few bits. Each of them is an XOR of the starting state’s bits (the register is linear), so each is a linear equation in the unknown start; after about n of them, solving the equations gives the start, and every hop to come. (That finds the signal, not necessarily what it means: the data it carries may be encrypted separately.) Hopping systems meant to resist this choose their hops with a keyed cipher; those that only hop to dodge interference, such as Bluetooth, work theirs out from a device’s address and clock, which aren’t secret.

So ciphers that use LFSRs combine several in non-linear ways (one register deciding when another steps, say, as GSM’s A5/1 does), and even those have been broken. LFSRs make excellent noise, codes and checks; secrets need more.

Summary

A linear-feedback shift register shifts its bits along and feeds back the XOR of a few taps.
With the right taps (a primitive polynomial) it visits every state but all-zeros: 2ⁿ − 1 steps, an m-sequence.
It looks random: balanced, with coin-toss runs and a flat spectrum. Held between steps, its noise has a pitch, as the SID’s does.
Its autocorrelation is one sharp peak and exactly −1 everywhere else (from balance and shift-and-add): ideal for finding codes in noise, and a sign of how much structure it has.
The same circuit, with data fed in, computes CRCs; XORed with data, it scrambles.
It’s linear, so Berlekamp–Massey finds an n-bit register from 2n of its bits.