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.
Why are PRBSs useful?
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.
What are some common PRBSs?
Some common PRBSs are referred to by the degree of the polynomial that is used to generate them:
- PRBS7 = x7 + x6 + 1
- PRBS15 = x15 + x14 + 1
- PRBS23 = x23 + x18 + 1
- PRBS31 = x31 + x28 + 1
These polynomials are elements of GF(2n) (the Galois Field of two elements). These polynomials can also be represented as binary numbers:
- PRBS7 = 1100 0001
- PRBS15 = 1100 0000 0000 0001
- PRBS23 = 1000 0100 0000 0000 0000 0001
- PRBS31 = 1001 0000 0000 0000 0000 0000 0000 0001
How are PRBSs generated from finite field polynomials?
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:
- Pick a characteristic polynomial of some degree n, where each monomial coefficient is either 0 or 1 (so the coefficients are drawn from GF(2)). (For example, x10+x7+x0.)
- Now, the state of the LFSR is any polynomial with coefficients in GF(2) with degree less than n and not being the all-zero polynomial.
- To compute the next state, multiply the state polynomial by x; divide the new state polynomial by the characteristic polynomial and take the remainder polynomial as the next state.
- Every time a state is generated, treat the coefficient of the x0 monomial term as a generated pseudorandom bit. (Using the coefficient of any other term is also fine, as long as it is at a fixed position for the LFSR.)
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 |
What does a PRBS look like?
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:
- x7 + x6 + 1 → 1000 0011 0000 1010 0011 1100 1000 1011 0011 1010 1001 1111 0100 0011 1000 1001 0011 0110 1011 0111 1011 0001 1010 0101 1101 1100 1100 1010 1011 1111 1000 000
- x5 + x3 + 1 → 1001 0110 0111 1100 0110 1110 1010 000
- x3 + x2 + 1 → 1011 100
How can I make my own PRBS?
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