Pseudorandom binary sequence


A pseudorandom binary sequence is a binary sequence that, while generated with a deterministic algorithm, is difficult to predict and exhibits statistical behavior similar to a truly random sequence. PRBS generators are used in telecommunication, such as in analog-to-information conversion, but also in encryption, simulation, correlation technique and time-of-flight spectroscopy.

Details

A binary sequence is a sequence of bits, i.e.
A BS consists of ones and zeros.
A BS is a pseudorandom binary sequence if its autocorrelation function, given by
has only two values:
where
is called the duty cycle of the PRBS, similar to the duty cycle of a continuous time signal. For a maximum length sequence, where, 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 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 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. However, as a result of this predictability, PRBS signals can be used as reproducible patterns.

Practical implementation

Pseudorandom binary sequences can be generated using linear-feedback shift registers.
Some common sequence generating monic polynomials are
An example of generating a "PRBS-7" sequence can be expressed in C as

  1. include
  2. include
  3. include

int main

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

Notation

The PRBSk or PRBS-k notation gives an indication of the size of the sequence. is the maximum number 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. For example, PRBS3 = "1011100" could be generated from. If you take every sequential group of three bit words in the PRBS3 sequence, you will find the following 7 word arrangements:
"1011100" → 101
"1011100" → 011
"1011100" → 111
"1011100" → 110
"1011100" → 100
"1011100" → 001
"1011100" → 010
Those 7 words are all of the possible non-zero 3-bit binary words, not in numeric order. The same holds true for any PRBSk, not just PRBS3.