Pseudorandom binary sequence

<h2 id="details">Details</h2>
A binary sequence (BS) is a <a href="/facts/Sequence/gV2S4uqp">sequence</a> 
 
 
 
 
 a
 
 0
 
 
 ,
 …
 ,
 
 a
 
 N
 −
 1
 
 
 
 
 {\displaystyle a_{0},\ldots ,a_{N-1}}
 
 of 
 
 
 
 N
 
 
 {\displaystyle N}
 
 bits, i.e.

a
 
 j
 
 
 ∈
 {
 0
 ,
 1
 }
 
 
 {\displaystyle a_{j}\in \{0,1\}}
 
 for 
 
 
 
 j
 =
 0
 ,
 1
 ,
 .
 .
 .
 ,
 N
 −
 1
 
 
 {\displaystyle j=0,1,...,N-1}
 
.
A BS consists of 
 
 
 
 m
 =
 ∑
 
 a
 
 j
 
 
 
 
 {\displaystyle m=\sum a_{j}}
 
 ones and 
 
 
 
 N
 −
 m
 
 
 {\displaystyle N-m}
 
 zeros.
A BS is a <a href="/facts/Pseudorandomness/kfs1wfhY">pseudorandom</a> binary sequence (PRBS) if<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a> its <a href="/facts/Autocorrelation_function/dm4MqK0A">autocorrelation function</a>, given by

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

has only two values:

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

where

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

is called the duty cycle of the PRBS, similar to the <a href="/facts/Duty_cycle/B2tbtXTh">duty cycle</a> of a continuous time signal. For a <a href="/facts/Maximum_length_sequence/VqXvnRvs">maximum length sequence</a>, where 
 
 
 
 N
 =
 
 2
 
 k
 
 
 −
 1
 
 
 {\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 
 
 
 
 
 a
 
 j
 
 
 
 
 {\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 
 
 
 
 N
 
 
 {\displaystyle N}
 
 elements, but it will then be cyclical and thus non-random. In contrast, truly random sequence sources, such as sequences generated by <a href="/facts/Radioactive_decay/Ya6FVjt4">radioactive decay</a> or by <a href="/facts/White_noise/wJ0SR21n">white noise</a>, 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).<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a>

<h2 id="practical-implementation">Practical implementation</h2>
Pseudorandom binary sequences can be generated using <a href="/facts/Linear-feedback_shift_register/22pktBbX">linear-feedback shift registers</a>.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a>
Some common<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a><a class="footnote-ref" id="fnref:7" href="#fn:7">7</a><a class="footnote-ref" id="fnref:8" href="#fn:8">8</a><a class="footnote-ref" id="fnref:9" href="#fn:9">9</a><a class="footnote-ref" id="fnref:10" href="#fn:10">10</a> sequence generating <a href="/facts/Monic_polynomial/4JzuIJ5R">monic polynomials</a> are

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

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

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

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

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

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

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

PRBS31 = 
  
    
      
        
          x
          
            31
          
        
        +
        
          x
          
            28
          
        
        +
        1
      
    
    {\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.

<h2 id="notation">Notation</h2>
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
 
 
 {\displaystyle N=2^{k}-1}
 
 is the maximum number<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a>: §3  of bits that are in the sequence. The k indicates the size of a unique <a href="/facts/Word_(computer_architecture)/2e5umRaj">word</a> 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.<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a>: §2  For example, PRBS3 = "1011100" could be generated from 
 
 
 
 
 x
 
 3
 
 
 +
 
 x
 
 2
 
 
 +
 1
 
 
 {\displaystyle x^{3}+x^{2}+1}
 
.<a class="footnote-ref" id="fnref:13" href="#fn:13">13</a> 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
 
 
 {\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.<a class="footnote-ref" id="fnref:14" href="#fn:14">14</a>: §2 

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Pseudorandom_number_generator/sIrCxIBq">Pseudorandom number generator</a></li>
<li><a href="/facts/Gold_code/a0FsE0Mc">Gold code</a></li>
<li><a href="/facts/Complementary_sequences/rYSLfbWU">Complementary sequences</a></li>
<li><a href="/facts/Bit_Error_Rate_Test/ovAAPFjV">Bit Error Rate Test</a></li>
<li><a href="/facts/Pseudorandom_noise/86cGG34T">Pseudorandom noise</a></li>
<li><a href="/facts/Linear-feedback_shift_register/22pktBbX">Linear-feedback shift register</a></li></ul>

<h2 id="external-links">External links</h2>
<ul><li>OEIS <a href="https://oeis.org/A011686">sequence A011686 (A binary m-sequence: expansion of reciprocal)</a> -- the bit sequence for PRBS7 = 
 
 
 
 
 x
 
 7
 
 
 +
 
 x
 
 6
 
 
 +
 1
 
 
 {\displaystyle x^{7}+x^{6}+1}
 
</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">"PRBS Pseudo Random Bit Sequence Generation". TTi. Retrieved 21 January 2016. <a href="http://www.tti-test.com/go/tgxa/prbs.htm" target="_blank">http://www.tti-test.com/go/tgxa/prbs.htm</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Daponte, Pasquale; De Vito, Luca; Iadarola, Grazia; Rapuano, Sergio. "PRBS non-idealities affecting Random Demodulation Analog-to-Information Converters" (PDF). <a href="https://www.imeko.org/publications/tc4-2016/IMEKO-TC4-2016-14.pdf" target="_blank">https://www.imeko.org/publications/tc4-2016/IMEKO-TC4-2016-14.pdf</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Naszodi, Laszlo. "Articles on Correlation and Calibration". Archived from the original on 11 November 2013. <a href="https://web.archive.org/web/20131111050840/http://www.scriptwell.net/correlation.htm" target="_blank">https://web.archive.org/web/20131111050840/http://www.scriptwell.net/correlation.htm</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">"ITU-T Recommendation O.150". October 1992. <a href="http://www.itu.int/rec/T-REC-O.150-199210-S" target="_blank">http://www.itu.int/rec/T-REC-O.150-199210-S</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Paul H. Bardell, William H. McAnney, and Jacob Savir, "Built-In Test for VLSI: Pseudorandom Techniques", John Wiley & Sons, New York, 1987. <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Tomlinson, Kurt (4 February 2015). "PRBS (Pseudo-Random Binary Sequence)". Bloopist. Retrieved 21 January 2016. <a href="http://blog.kurttomlinson.com/posts/prbs-pseudo-random-binary-sequence" target="_blank">http://blog.kurttomlinson.com/posts/prbs-pseudo-random-binary-sequence</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Koopman, Philip. "Maximal Length LFSR Feedback Terms". Retrieved 21 January 2016. <a href="https://users.ece.cmu.edu/~koopman/lfsr/index.html" target="_blank">https://users.ece.cmu.edu/~koopman/lfsr/index.html</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">"What are the PRBS7, PRBS15, PRBS23, and PRBS31 polynomials used in the Altera Transceiver Toolkit?". Altera. 14 February 2013. Retrieved 21 January 2016. <a href="https://www.altera.com/support/support-resources/knowledge-base/solutions/rd02142013_406.html" target="_blank">https://www.altera.com/support/support-resources/knowledge-base/solutions/rd02142013_406.html</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Riccardi, Daniele; Novellini, Paolo (10 January 2011). "An Attribute-Programmable PRBS Generator and Checker (XAP884)" (PDF). Xilinx. Table 3:Configuration for PRBS Polynomials Most Used to Test Serial Lines. Retrieved 21 January 2016. <a href="http://www.xilinx.com/support/documentation/application_notes/xapp884_PRBS_GeneratorChecker.pdf" target="_blank">http://www.xilinx.com/support/documentation/application_notes/xapp884_PRBS_GeneratorChecker.pdf</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">"O.150 : General requirements for instrumentation for performance measurements on digital transmission equipment". 1997-01-06. <a href="https://www.itu.int/rec/T-REC-O.150-199605-I/en" target="_blank">https://www.itu.int/rec/T-REC-O.150-199605-I/en</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">"ITU-T Recommendation O.150". October 1992. <a href="http://www.itu.int/rec/T-REC-O.150-199210-S" target="_blank">http://www.itu.int/rec/T-REC-O.150-199210-S</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">"ITU-T Recommendation O.150". October 1992. <a href="http://www.itu.int/rec/T-REC-O.150-199210-S" target="_blank">http://www.itu.int/rec/T-REC-O.150-199210-S</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">Tomlinson, Kurt (4 February 2015). "PRBS (Pseudo-Random Binary Sequence)". Bloopist. Retrieved 21 January 2016. <a href="http://blog.kurttomlinson.com/posts/prbs-pseudo-random-binary-sequence" target="_blank">http://blog.kurttomlinson.com/posts/prbs-pseudo-random-binary-sequence</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
<li id="fn:14">"ITU-T Recommendation O.150". October 1992. <a href="http://www.itu.int/rec/T-REC-O.150-199210-S" target="_blank">http://www.itu.int/rec/T-REC-O.150-199210-S</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></li>
</ol>

Pseudorandom binary sequence open-in-new

Pseudorandom binary sequence