Pseudorandom binary sequence

A binary sequence (BS) is a sequence ${\displaystyle a_{0},\ldots ,a_{N-1}}$ of ${\displaystyle N}$ bits, i.e.

${\displaystyle a_{j}\in \{0,1\}}$ for ${\displaystyle j=0,1,...,N-1}$.

A BS consists of ${\displaystyle m=\sum a_{j}}$ ones and ${\displaystyle N-m}$ zeros.

A BS is a pseudorandom binary sequence (PRBS) if[3] its autocorrelation function, given by

${\displaystyle C(v)=\sum _{j=0}^{N-1}a_{j}a_{j+v}}$

has only two values:

${\displaystyle C(v)={\begin{cases}m,{\mbox{ if }}v\equiv 0\;\;({\mbox{mod}}N)\\\\mc,{\mbox{ otherwise }}\end{cases}}}$

where

${\displaystyle c={\frac {m-1}{N-1}}}$

is called the duty cycle of the PRBS, similar to the duty cycle of a continuous time signal. For a maximum length sequence, where ${\displaystyle N=2^{k}-1}$, the duty cycle is 1/2.

A PRBS is 'pseudorandom', because, although it is in fact deterministic, it seems to be random in a sense that the value of an ${\displaystyle a_{j}}$ element is independent of the values of any of the other elements, similar to real random sequences.

A PRBS can be stretched to infinity by repeating it after ${\displaystyle N}$ elements, but it will then be cyclical and thus non-random. In contrast, truly random sequence sources, such as sequences generated by radioactive decay or by white noise, are infinite (no pre-determined end or cycle-period). However, as a result of this predictability, PRBS signals can be used as reproducible patterns (for example, signals used in testing telecommunications signal paths).[4]

Pseudorandom binary sequences can be generated using linear-feedback shift registers.[5]

Some common[6][7][8][9][10] sequence generating monic polynomials are

PRBS7 = ${\displaystyle x^{7}+x^{6}+1}$

PRBS9 = ${\displaystyle x^{9}+x^{5}+1}$

PRBS11 = ${\displaystyle x^{11}+x^{9}+1}$

PRBS13 = ${\displaystyle x^{13}+x^{12}+x^{2}+x+1}$

PRBS15 = ${\displaystyle x^{15}+x^{14}+1}$

PRBS20 = ${\displaystyle x^{20}+x^{3}+1}$

PRBS23 = ${\displaystyle x^{23}+x^{18}+1}$

PRBS31 = ${\displaystyle x^{31}+x^{28}+1}$

An example of generating a "PRBS-7" sequence can be expressed in C as

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
    
int main(int argc, char* argv[]) {
    uint8_t start = 0x02;
    uint8_t a = start;
    int i;    
    for (i = 1;; i++) {
        int newbit = (((a >> 6) ^ (a >> 5)) & 1);
        a = ((a << 1) | newbit) & 0x7f;
        printf("%x\n", a);
        if (a == start) {
            printf("repetition period is %d\n", i);
            break;
        }
    }
}

In this particular case, "PRBS-7" has a repetition period of 127 values.

A more generalized code for any PRBS-k sequence up to k=32 using C++ templates can be found on GitHub.

The PRBSk or PRBS-k notation (such as "PRBS7" or "PRBS-7") gives an indication of the size of the sequence. ${\displaystyle N=2^{k}-1}$ is the maximum number[4]^: §3 of bits that are in the sequence. The k indicates the size of a unique word of data in the sequence. If you segment the N bits of data into every possible word of length k, you will be able to list every possible combination of 0s and 1s for a k-bit binary word, with the exception of the all-0s word.[4]^: §2 For example, PRBS3 = "1011100" could be generated from ${\displaystyle x^{3}+x^{2}+1}$.[6] If you take every sequential group of three bit words in the PRBS3 sequence (wrapping around to the beginning for the last few three-bit words), you will find the following 7 word arrangements:

  "1011100" → 101
  "1011100" → 011
  "1011100" → 111
  "1011100" → 110
  "1011100" → 100
  "1011100" → 001 (requires wrap)
  "1011100" → 010 (requires wrap)

Those 7 words are all of the ${\displaystyle 2^{k}-1=2^{3}-1=7}$ possible non-zero 3-bit binary words, not in numeric order. The same holds true for any PRBSk, not just PRBS3.[4]^: §2

• Pseudorandom number generator
• Gold code
• Complementary sequences
• Bit Error Rate Test
• Pseudorandom noise
• Linear-feedback shift register

• OEIS sequence A011686 (A binary m-sequence: expansion of reciprocal) -- the bit sequence for PRBS7 = ${\displaystyle x^{7}+x^{6}+1}$