imported>MüllerMarcus: /* Practical implementation */ Removing a link to a not even merged pull request on Github. That's not a source, that's more like an attempt to give weight to one's code contribution.

2024-02-05T16:26:22Z

Practical implementation: Removing a link to a not even merged pull request on Github. That's not a source, that's more like an attempt to give weight to one's code contribution.

New page

{{Use American English|date = March 2019}}
{{Short description|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<ref name="TTI">{{cite web |url=http://www.tti-test.com/go/tgxa/prbs.htm |title=PRBS Pseudo Random Bit Sequence Generation |website=TTi |access-date=21 January 2016}}</ref> and exhibits statistical behavior similar to a truly random sequence. PRBS generators are used in [[telecommunication]], such as in analog-to-information conversion,<ref>{{cite web |url=https://www.imeko.org/publications/tc4-2016/IMEKO-TC4-2016-14.pdf |title=PRBS non-idealities affecting Random Demodulation Analog-to-Information Converters |last1=Daponte |first1=Pasquale |last2=De Vito |first2=Luca |last3=Iadarola |first3=Grazia |last4=Rapuano |first4=Sergio}}</ref> 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|linear feedback shift register]] (LFSR). Other examples are [[Gold code|Gold sequences]] (used in [[CDMA]] and [[Global Positioning System|GPS]]), [[Kasami code|Kasami sequences]] and [[JPL sequence|JPL sequences]], all based on LFSRs.

In [[Telecommunication|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]] <math>a_0,\ldots, a_{N-1}</math> of <math>N</math> bits, i.e.

:<math>a_j\in \{0,1\}</math> for <math>j=0,1,...,N-1</math>.

A BS consists of <math>m=\sum a_j</math> ones and <math>N-m</math> zeros.

A BS is a '''[[pseudorandomness|pseudorandom]] binary sequence''' (PRBS) if<ref>{{cite web |url=http://www.scriptwell.net/correlation.htm |title=Articles on Correlation and Calibration |last1=Naszodi |first1=Laszlo |archive-url=https://web.archive.org/web/20131111050840/http://www.scriptwell.net/correlation.htm |archive-date=11 November 2013 |url-status=dead}}</ref> its [[autocorrelation function]], given by

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

has only two values:

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

where

:<math>c=\frac{m-1}{N-1}</math>

is called the ''duty cycle'' of the PRBS, similar to the [[duty cycle]] of a continuous time signal. For a [[maximum length sequence]], where <math>N = 2^k - 1</math>, 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 <math>a_j</math> 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 <math>N</math> 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).<ref name="O150">{{cite web|url=http://www.itu.int/rec/T-REC-O.150-199210-S |title=ITU-T Recommendation O.150 |date=October 1992}}</ref>

== Practical implementation ==
Pseudorandom binary sequences can be generated using [[linear-feedback shift register]]s.<ref>Paul H. Bardell, William H. McAnney, and Jacob Savir, "Built-In Test for VLSI: Pseudorandom Techniques", John Wiley & Sons, New York, 1987.</ref>

Some common<ref name="Bloopist">{{cite web |url=http://blog.kurttomlinson.com/posts/prbs-pseudo-random-binary-sequence |title=PRBS (Pseudo-Random Binary Sequence) |last1=Tomlinson |first1=Kurt |website=Bloopist|date=4 February 2015 |access-date=21 January 2016}}</ref><ref>{{cite web |url=https://users.ece.cmu.edu/~koopman/lfsr/index.html |title=Maximal Length LFSR Feedback Terms |last1=Koopman |first1=Philip |access-date=21 January 2016}}</ref><ref>{{cite web |url=https://www.altera.com/support/support-resources/knowledge-base/solutions/rd02142013_406.html |title=What are the PRBS7, PRBS15, PRBS23, and PRBS31 polynomials used in the Altera Transceiver Toolkit? |website=[[Altera]] |date=14 February 2013 |access-date=21 January 2016}}</ref><ref>{{cite web |url=http://www.xilinx.com/support/documentation/application_notes/xapp884_PRBS_GeneratorChecker.pdf |title=An Attribute-Programmable PRBS Generator and Checker (XAP884) |last1=Riccardi |first1=Daniele |last2=Novellini |first2=Paolo |date=10 January 2011 |at=Table 3:Configuration for PRBS Polynomials Most Used to Test Serial Lines |website=[[Xilinx]] |access-date=21 January 2016}}</ref><ref>{{cite web |url=https://www.itu.int/rec/T-REC-O.150-199605-I/en |title=O.150 : General requirements for instrumentation for performance measurements on digital transmission equipment |date=1997-01-06}}</ref> sequence generating [[monic polynomial]]s are

:PRBS7 = <math>x^{7} + x^{6} + 1</math>

:PRBS9 = <math>x^{9} + x^{5} + 1</math>

:PRBS11 = <math>x^{11} + x^{9} + 1</math>

:PRBS13 = <math>x^{13} + x^{12} + x^{2} + x + 1 </math>

:PRBS15 = <math>x^{15} + x^{14} + 1</math>

:PRBS20 = <math>x^{20} + x^{3} + 1</math>

:PRBS23 = <math>x^{23} + x^{18} + 1</math>

:PRBS31 = <math>x^{31} + x^{28} + 1</math>

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

<syntaxhighlight 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;
}
}
}
</syntaxhighlight>

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

== Notation ==

The PRBS''k'' or PRBS-''k'' notation (such as "PRBS7" or "PRBS-7") gives an indication of the size of the sequence. <math>N = 2^k - 1</math> is the maximum number<ref name="O150" />{{Rp|§3}} of bits that are in the sequence. The ''k'' indicates the size of a unique [[Word (computer architecture)|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.<ref name="O150" />{{Rp|§2}} For example, PRBS3 = "1011100" could be generated from <math>x^{3} + x^{2} + 1</math>.<ref name="Bloopist" /> 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 <math>2^k - 1 = 2^3 - 1 = 7</math> possible non-zero 3-bit binary words, not in numeric order. The same holds true for any PRBS''k'', not just PRBS3.<ref name="O150" />{{Rp|§2}}

== See also ==
* [[Pseudorandom number generator]]
* [[Gold code]]
* [[Complementary sequences]]
* [[Bit Error Rate Test]]
* [[Pseudorandom noise]]
* [[Linear-feedback shift register]]

==References==
{{reflist}}

== External links ==
* {{OEIS el|1=A011686|2=A binary m-sequence: expansion of reciprocal|formalname=A binary m-sequence: expansion of reciprocal of x^7 + x^6 + 1}} -- the bit sequence for PRBS7 = <math>x^{7} + x^{6} + 1</math>

[[Category:Pseudorandomness]]
[[Category:Binary sequences]]

Pseudorandom binary sequence - Revision history

imported>MüllerMarcus: /* Practical implementation */ Removing a link to a not even merged pull request on Github. That's not a source, that's more like an attempt to give weight to one's code contribution.