Pseudorandom binary sequence

From Wikipedia, the free encyclopedia
  (Redirected from Pseudo-random binary sequence)
Jump to: navigation, search

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 pseudo-random binary sequence (PRBS) if its autocorrelation function:

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.

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, this in contrast to most random sequences, such as sequences generated by radioactive decay or by white noise, that are 'infinite' by nature. The PRBS is more general than the maximum length sequence, which is a special pseudo-random binary sequence of N bits generated as the output of a linear shift register. A maximum length sequence always has a 1/2 duty cycle and its number of elements N = 2^k-1. PRBS's are used in telecommunication, encryption, simulation, correlation technique and time-of-flight spectroscopy.

Practical implementation[edit]

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

Some common sequence generating polynomials are

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

PRBS15 = x^{15} + x^{14} + 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

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
 
main(int argc, char* argv[]) {
    uint8_t start = 0x02;
    uint8_t a = start;
 
    for(int 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;
        }
    }
}

See also[edit]

References[edit]

  1. ^ Paul H. Bardell, William H. McAnney, and Jacob Savir, "Built-In Test for VLSI: Pseudorandom Techniques", John Wiley & Sons, New York, 1987.

External links[edit]