Pseudorandom binary sequence

Quality 0.50 · 3 views · Updated 2 months ago

Seemingly random, difficult to predict bit stream created by a deterministic algorithm

title: "Pseudorandom binary sequence" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["pseudorandomness", "binary-sequences"] description: "Seemingly random, difficult to predict bit stream created by a deterministic algorithm" topic_path: "general/pseudorandomness" source: "https://en.wikipedia.org/wiki/Pseudorandom_binary_sequence" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0

::summary Seemingly random, difficult to predict bit stream created by a deterministic algorithm ::

A pseudorandom binary sequence (PRBS), pseudorandom binary code or pseudorandom bitstream 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. The most common example is the maximum length sequence generated by a (maximal) linear feedback shift register (LFSR). Other examples are Gold sequences (used in CDMA and GPS), Kasami sequences and JPL sequences, all based on LFSRs.

In telecommunications, pseudorandom binary sequences are known as pseudorandom noise codes (PN or PRN codes) due to their application as pseudorandom noise.

Details

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

:a_j\in {0,1} for j=0,1,...,N-1.

A BS consists of m=\sum a_j ones and N-m zeros.

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

:C(v)=\sum_{j=0}^{N-1} a_ja_{j+v}

has only two values:

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

where

: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 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 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 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).

Practical implementation

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

Some common sequence generating monic polynomials are

:PRBS7 = x^{7} + x^{6} + 1

:PRBS9 = x^{9} + x^{5} + 1

:PRBS11 = x^{11} + x^{9} + 1

:PRBS13 = x^{13} + x^{12} + x^{2} + x + 1

:PRBS15 = x^{15} + x^{14} + 1

:PRBS20 = x^{20} + x^{3} + 1

:PRBS23 = x^{23} + x^{18} + 1

:PRBS31 = x^{31} + x^{28} + 1

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

::code[lang=c] #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.

Notation

The PRBSk or PRBS-k notation (such as "PRBS7" or "PRBS-7") gives an indication of the size of the sequence. N = 2^k - 1 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 x^{3} + x^{2} + 1. 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 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.

References

References

  1. "PRBS Pseudo Random Bit Sequence Generation".
  2. "PRBS non-idealities affecting Random Demodulation Analog-to-Information Converters".
  3. "Articles on Correlation and Calibration".
  4. (October 1992). "ITU-T Recommendation O.150".
  5. Paul H. Bardell, William H. McAnney, and Jacob Savir, "Built-In Test for VLSI: Pseudorandom Techniques", John Wiley & Sons, New York, 1987.
  6. (4 February 2015). "PRBS (Pseudo-Random Binary Sequence)".
  7. "Maximal Length LFSR Feedback Terms".
  8. (14 February 2013). "What are the PRBS7, PRBS15, PRBS23, and PRBS31 polynomials used in the Altera Transceiver Toolkit?".
  9. (10 January 2011). "An Attribute-Programmable PRBS Generator and Checker (XAP884)".
  10. (1997-01-06). "O.150 : General requirements for instrumentation for performance measurements on digital transmission equipment".

::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::

pseudorandomnessbinary-sequences