A pseudorandom binary sequence (PRBS), pseudorandom binary code or pseudorandom bitstream is a
binary sequence that, while generated with a deterministic
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
, is difficult to predict
and exhibits statistical behavior similar to a truly random sequence. PRBS generators are used in
telecommunication
Telecommunication is the transmission of information by various types of technologies over wire, radio, optical, or other electromagnetic systems. It has its origin in the desire of humans for communication over a distance greater than that ...
, such as in analog-to-information conversion, but also in
encryption
In cryptography, encryption is the process of encoding information. This process converts the original representation of the information, known as plaintext, into an alternative form known as ciphertext. Ideally, only authorized parties can d ...
,
simulation
A simulation is the imitation of the operation of a real-world process or system over time. Simulations require the use of Conceptual model, models; the model represents the key characteristics or behaviors of the selected system or proc ...
,
correlation
In statistics, correlation or dependence is any statistical relationship, whether causal or not, between two random variables or bivariate data. Although in the broadest sense, "correlation" may indicate any type of association, in statistic ...
technique and time-of-flight
spectroscopy
Spectroscopy is the field of study that measures and interprets the electromagnetic spectra that result from the interaction between electromagnetic radiation and matter as a function of the wavelength or frequency of the radiation. Matter ...
. The most common example is the
maximum length sequence generated by a (maximal)
linear feedback shift register
In computing, a linear-feedback shift register (LFSR) is a shift register whose input bit is a linear function of its previous state.
The most commonly used linear function of single bits is exclusive-or (XOR). Thus, an LFSR is most often a s ...
(LFSR). Other examples are
Gold sequences (used in
CDMA
Code-division multiple access (CDMA) is a channel access method used by various radio communication technologies. CDMA is an example of multiple access, where several transmitters can send information simultaneously over a single communicatio ...
and
GPS),
Kasami sequences and
JPL sequences, all based on LFSRs.
In
telecommunications
Telecommunication is the transmission of information by various types of technologies over wire, radio, optical, or other electromagnetic systems. It has its origin in the desire of humans for communication over a distance greater than that ...
, 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
In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is called ...
of
bits, i.e.
:
for
.
A BS consists of
ones and
zeros.
A BS is a
pseudorandom
A pseudorandom sequence of numbers is one that appears to be statistically random, despite having been produced by a completely deterministic and repeatable process.
Background
The generation of random numbers has many uses, such as for rand ...
binary sequence (PRBS) if its
autocorrelation function, given by
:
has only two values:
:
where
:
is called the ''duty cycle'' of the PRBS, similar to the
duty cycle
A duty cycle or power cycle is the fraction of one period in which a signal or system is active. Duty cycle is commonly expressed as a percentage or a ratio. A period is the time it takes for a signal to complete an on-and-off cycle. As a form ...
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
Radioactive decay (also known as nuclear decay, radioactivity, radioactive disintegration, or nuclear disintegration) is the process by which an unstable atomic nucleus loses energy by radiation. A material containing unstable nuclei is consid ...
or by
white noise
In signal processing, white noise is a random signal having equal intensity at different frequencies, giving it a constant power spectral density. The term is used, with this or similar meanings, in many scientific and technical disciplines ...
, 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 register
In computing, a linear-feedback shift register (LFSR) is a shift register whose input bit is a linear function of its previous state.
The most commonly used linear function of single bits is exclusive-or (XOR). Thus, an LFSR is most often a ...
s.
Some common
sequence generating
monic polynomial
In algebra, a monic polynomial is a single-variable polynomial (that is, a univariate polynomial) in which the leading coefficient (the nonzero coefficient of highest degree) is equal to 1. Therefore, a monic polynomial has the form:
:x^n+c_x^+\ ...
s are
:PRBS7 =
:PRBS9 =
:PRBS11 =
:PRBS13 =
:PRBS15 =
:PRBS20 =
:PRBS23 =
:PRBS31 =
An example of generating a "PRBS-7" sequence can be expressed in C as
#include
#include
#include
int main(int argc, char* argv[])
In this particular case, "PRBS-7" has a repetition period of 127 values.
A more generalized code for any PRBS-k sequence up to k=32 using C++ templates can be foun
on GitHub
Notation
The PRBS''k'' or PRBS-''k'' notation (such as "PRBS7" or "PRBS-7") 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
A word is a basic element of language that carries an objective or practical meaning, can be used on its own, and is uninterruptible. Despite the fact that language speakers often have an intuitive grasp of what a word is, there is no conse ...
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 (wrapping around to the beginning for the last few three-bit words), you will find the following 7 word arrangements:
"
1011100" → 101
"1
011100" → 011
"10
11100" → 111
"101
1100" → 110
"1011
100" → 100
"
10111
00" → 001 (requires wrap)
"
101110
0" → 010 (requires wrap)
Those 7 words are all of the
possible non-zero 3-bit binary words, not in numeric order. The same holds true for any PRBS''k'', not just PRBS3.
See also
*
Pseudorandom number generator
A pseudorandom number generator (PRNG), also known as a deterministic random bit generator (DRBG), is an algorithm for generating a sequence of numbers whose properties approximate the properties of sequences of random numbers. The PRNG-generate ...
*
Gold code
*
Complementary sequences
*
Bit Error Rate Test
In digital transmission, the number of bit errors is the number of received bits of a data stream over a communication channel that have been altered due to noise, interference, distortion or bit synchronization errors.
The bit error rate (BER ...
*
Pseudorandom noise
*
Linear-feedback shift register
In computing, a linear-feedback shift register (LFSR) is a shift register whose input bit is a linear function of its previous state.
The most commonly used linear function of single bits is exclusive-or (XOR). Thus, an LFSR is most often a ...
References
External links
* -- the bit sequence for PRBS7 =
Pseudorandomness
Binary sequences