In my line of work as a semiconductor test engineer, pseudo-random binary/bit sequences are very useful. They're random-ish streams of bits that can be easily and reliably reproduced using very simple hardware or software. Any semiconductor that can be used to transmit information can be tested at a functional level with a PRBS. Send a PRBS to the device you're testing, tell the device to repeat it back to you, and compare what you received to what you sent.
A PRBS is preferred over a simple square wave because it stresses the device under test in more ways. It's not uncommon for a device to have no problem transmitting a sequence like "010101" but choke on a sequence with repeated bits like "011101". PRBSs include strings of repeated bits as well as strings of alternating bits.
Some common PRBSs are referred to by the degree of the polynomial that is used to generate them:
These polynomials are elements of GF(2n) (the Galois Field of two elements). These polynomials can also be represented as binary numbers:
First, a seed polynomial is chosen. This seed polynomial can be any non-zero polynomial in the field GF(2n) where n is the degree of the PRBS polynomial. Zero can't be chosen as a seed state because the seed is multiplied by x to produce the next state. If the seed is zero, this product is zero and there is no next state.
The Project Nayuki website has a good description of how to calculate the state of the LSFR at each step:
Note that this method produces the states in reverse order when compared with the code given later in this post. Here's an example of the math worked out by hand:
LSFR State | Binary | Multiply by x | Modulus by Characteristic Polynomial |
---|---|---|---|
1 | 001 | (1)*x = x | (x) / (x3+x2+1) = 0 remainder x |
x | 010 | (x)*x = x2 | (x2) / (x3+x2+1) = 0 remainder x2 |
x2 | 100 | (x2)*x = x3 | (x3) / (x3+x2+1) = 1 remainder x2+1 |
x2+1 | 101 | (x2+1)*x = x3+x | (x3+x) / (x3+x2+1) = 1 remainder x2+x+1 |
x2+x+1 | 111 | (x2+x+1)*x = x3+x2+x | (x3+x2+x) / (x3+x2+1) = 1 remainder x+1 |
x+1 | 011 | (x+1)*x = x2+x | (x2+x) / (x3+x2+1) = 0 remainder x2+x |
x2+x | 110 | (x2+x)*x = x3+x2 | (x3+x2) / (x3+x2+1) = 1 remainder 1 |
The javascript below can be used to generate PRBSs from the binary representation of a PRBS polynomial:
var polynomial = "10100";
//"1100000" = x^7+x^6+1
//"10100" = x^5+x^3+1
//"110" = x^3+x^2+1
var start_state = 0x1; /* Any nonzero start state will work. */
var taps = parseInt(polynomial, 2);
var lfsr = start_state;
var period = 0;
var prbs = "";
do
{
var lsb = lfsr & 1; /* Get LSB (i.e., the output bit). */
prbs = prbs + lsb;
lfsr >>= 1; /* Shift register */
if (lsb == 1) { /* Only apply toggle mask if output bit is 1. */
lfsr ^= taps; /* Apply toggle mask, value has 1 at bits corresponding to taps, 0 elsewhere. */
}
++period;
} while (lfsr != start_state);
console.log("period = " + period);
console.log("prbs = " + prbs);
if (period == Math.pow(2, polynomial.length)-1) {
console.log("polynomial is maximal length");
} else {
console.log("polynomial is not maximal length");
}
The script above produced these outputs:
PRBSs produce 2n-1 bits before repeating. See section III. LFSR and Galois Fields in Linear Feedback Shift Registers, Galois Fields, and Stream Ciphers by Mike Thomsen for an overview on how to find PRBS polynomials for a desired repetition length. Additionally, Wikipedia has a list of polynomials for maximal LFSRs and Philip Koopman has provided lists of longer polynomials for maximal LFSRs on his website.
Photo by Vladimer Shioshvili