Pseudo Random Number

A pseudo random sequence looks random to anything that measures it. A formula produces it, and anyone holding two pieces of information can repeat it exactly. Communication systems want both halves of that at once, and this page is about why.

What is Pseudo Random Number ?
Why we talk about Pseudo Random Number in communication theory ?
Where does randomizing stop being security ?
What kind of Pseudo Random Number (Sequence) are used in communication system ?
Reference

What is Pseudo Random Number ?

You would know what a Random Number is. Even if you may not able to define explictely a random number, you would have some intuitive understanding of your own and I think it is right.

What does it mean by 'Pseudo' ? If you google it or look into a dictionary, the common definition of 'Pseudo' would be 'not-genuin'.... a kind of fake.

Combining these together, you would define 'Pseudo Random Number' as 'nongenuin random number' or 'kind of fake random number'.

Again by googling, I got a definition that I like (short and clear) as follows :

(of a number, a sequence of numbers, or any digital data) satisfying one or more statistical tests for randomness but produced by a definite mathematical procedure.

My own definition of Pseudo Random Number is as follows :

A sequence of numbers that look like random number sequence (a sequence of random numbers), but we know exactly how it is generated and we can duplicate the exact sequence if we are given a few required information.

If you are interested more in the definition, refer to the document in Reference section or google it further. I don't think I need to talk any further on the definition.

One phrase in that second definition carries more weight than it appears to. A few required information is the whole difference between a pseudo random sequence and a random one, so it is worth naming what that information is. For the generators this page lists, it is two things : which polynomial the generator uses, and what the register held when it started.

Those two are usually called the polynomial and the seed, and Figure 1 shows why both ends need them. Neither end ever sends the sequence itself. Each one computes it from the same two pieces, which is the property that makes the whole idea useful.

Figure 1. The two things that have to be agreed, and the one thing that never has to be sent. A sequence generated this way costs no bandwidth at all, which is why a transmitter can afford to use a very long one.

Two pieces of information, not one : the polynomial decides the shape of the sequence and the seed decides where in that sequence you start. Both have to match, and matching only one is the same as matching neither.
The sequence is never transmitted : it is recomputed at each end. That is the difference between a shared sequence and a key sent over a link. It is also why the sequence can be far longer than any message.
Deterministic and random looking are not in conflict : the tests for randomness examine the statistics of the output. A formula can satisfy every one of them and stay completely repeatable.

The word pseudo also implies a limit that the definitions above leave out. A generator built from a register of n bits has only 2ⁿ possible states. It must eventually return to a state it has already visited, and repeat everything from there. The sequence has a period, and a true random source does not.

The length of that period depends on the polynomial rather than on luck. The best choice reaches 2ⁿ - 1, which is every state except the all-zero one. The m sequence page covers how a polynomial is chosen to achieve it. A 31 bit register at that maximum runs for over two billion bits before repeating, which is long enough that a receiver never notices the repetition.

Every generator repeats eventually : n bits of state give at most 2ⁿ - 1 useful steps. A period exists whether or not anybody runs the generator long enough to see it.
The period is designed, not discovered : most polynomials give a much shorter cycle than the maximum. Choosing one that reaches it is the whole point of the m sequence tables.

Why we talk about Pseudo Random Number in communication theory ?

In communication system, there are many cases where you want to randomize some data in a specific structure so that you can un-randomize when you want.

Why do you want to randomize ? There would be several reasons

For Security reason : I want to make my data hard to be recognized by somebody else
For physical / electrical reason : this is especially important in digital communication. By randomizing, you can convert any data in such a way that it has almost same number of 1s and 0s with even distribution and this makes synchronization easier in electrical circuit.

The second of those two reasons carries more weight than its one sentence suggests, so it is worth separating into the three things it actually buys. All three come from the same operation, which is XOR against a pseudo random sequence.

The first is a bound on how long a run of identical bits can get. A receiver recovers its clock from the transitions in the signal, and a long stretch with no transition leaves it drifting. Figure 2 takes forty bits containing a run of fourteen zeros and scrambles them.

Figure 2. The same forty bits before and after. The run of fourteen zeros is gone and the longest run left is four, which is the property a clock recovery circuit cares about. Nothing has been added to the data and nothing has been removed.

The input is the awkward case on purpose : fourteen identical bits in a row is what a file of zeros or an idle channel produces. It is also exactly what a receiver cannot recover a clock from.
The middle row bounds the output : the sequence itself never runs more than six identical bits, because it comes from a six stage register. Whatever the data does, the scrambled result inherits that bound.
The operation is reversible and costs nothing : XOR is its own inverse, so the receiver undoes it by repeating it with the same sequence. That is what makes un-randomizing as cheap as randomizing.

The second thing it buys is balance. A long run of one value pushes the average level of the signal away from centre. A receiver that slices against a running average then makes errors. An m sequence of n stages holds 2^n-1 ones against 2^n-1 - 1 zeros in one full period. The imbalance over that whole period is a single bit.

The third is spectral. A repeating data pattern concentrates energy at the frequency of its repetition. That appears as a line in the spectrum, and it can breach an emission limit. Scrambling spreads that energy across the band. The effect also matters inside OFDM, where subcarriers carrying identical values add to a single large peak in time and force the amplifier into back-off.

Three separate gains from one XOR : bounded run length for the clock, balance for the slicer, and a spread spectrum for the emission mask. Any one of them would justify the operation.
The bound comes from the sequence, not from the data : a six stage generator caps the run at six whatever it is scrambling. That independence is what makes the guarantee worth having.
Un-randomizing is the same operation again : the receiver needs no inverse and no extra hardware, only the same polynomial and the same seed.

Where does randomizing stop being security ?

The first of the two reasons above needs a qualification, and it is the kind worth stating plainly. Scrambling does make data unrecognisable to anyone reading the link casually. It does not make the data secret, and the gap between those two is not a matter of degree.

The reason is the structure that makes these generators cheap. Feedback is a sum in GF(2) with no products and no thresholds, so every output bit is a fixed combination of earlier ones. That linearity is what lets a short register produce a long sequence, and it is also what makes the sequence recoverable.

Observing 2n consecutive output bits recovers both the taps and the state of an n stage generator. The Berlekamp-Massey algorithm does it in time proportional to n squared. A 31 stage generator therefore falls to 62 observed bits. The LFSR page covers that attack in more detail.

An attacker often needs less than that. Protocols put known values in known places, such as a fixed header or a padding field. XOR a guessed plaintext against the observed output, and that stretch of the sequence falls out directly. From a stretch of the sequence the rest follows by the paragraph above.

What scrambling buys is therefore narrower than the word security suggests. It removes structure from a bit stream. It stops a long run, it spreads the spectrum, and it stops a casual observer recognising a pattern by eye. Real confidentiality is a separate mechanism with its own keys, and cellular systems run both, at different layers and for different reasons.

Linear is the point and the weakness : one property lets 31 bits of state produce two billion bits of sequence. The same property lets 62 observed bits reconstruct the generator.
Known plaintext is the practical route : a fixed header XORed against the observed stream reveals the sequence over that stretch. The rest needs no cleverness at all.
Call it whitening rather than encryption : scrambling is a signal conditioning operation. Treating it as protection is the one mistake worth avoiding here.

What kind of Pseudo Random Number (Sequence) are used in communication system ?

There are many different types of Pseudo Random Number that are used in communication system. Usually they are named by the algorithm or properties of the sequence. Followings are some of the examples

These are a few commonly used Algorithm to generate a pseudo random number. Followings are some of real application how these algorithms are used in communication system.

One machine sits underneath all three of those names, and the list above does not mention it. Each is produced by a linear feedback shift register. That is a row of flip-flops, with an XOR feeding the result of a few of them back to the input. The differences between the three are differences in how that register is configured and how many of them are used.

The table below sets the three side by side. Read the third column first. The count of distinct sequences decides whether a scheme can give every user in a cell a code of their own.

Name	What it is	How many exist at degree n	What it is used for
PRBS	the output of a register whose polynomial reaches the maximum period. The standard test patterns are named by the register length, as PRBS7, PRBS15 and PRBS31.	one family for each register length	bit error rate testing. Both ends generate the same pattern, so the receiver counts errors without anything being sent to compare against.
m-Sequence	the same output named after the property that defines it, that the period reaches the maximum of 2ⁿ - 1 rather than falling into a shorter cycle.	phi(2ⁿ - 1) divided by n, so 2 at degree 4, 6 at degree 5 and 16 at degree 8	scrambling and ranging, wherever one sharp correlation peak against a flat floor is what the receiver needs.
Gold Code	two m-sequences of the same degree, chosen as a preferred pair and XORed together at every relative shift between them.	2ⁿ + 1 members in one family	giving many users a code each, where what matters is how weakly one user's code correlates against another's.

The three rows are less like alternatives than like three steps of one construction. A PRBS is a register output. An m sequence is a register output whose polynomial was chosen so that the period reaches its maximum. A Gold code is two of those combined. Each step costs something and buys something specific.

Choosing the polynomial carefully buys the longest period the register can reach, and it also buys a correlation that takes only two values. Combining two of them buys a large family whose members correlate weakly against each other, which one m sequence family cannot offer. The price of that second step is a slightly worse correlation of a code against itself.

That last trade explains the two links given after the list above. Both LTE and NR need one sequence per cell and per channel rather than one sequence in total. Both therefore use a Gold sequence built from two m sequences.

All three come out of the same hardware : a shift register with an XOR in the feedback. The names describe how it is configured rather than three unrelated inventions.
The count in the third column is the design question : scrambling one link needs one sequence. Separating users needs a family with many members.
Autocorrelation and cross-correlation are traded against each other : an m sequence is better on the first and a Gold code on the second. No family is best at both.
PRBS is the test bench name for the same thing : PRBS7 and PRBS31 name the register length. A receiver that knows the pattern counts errors with nothing sent alongside the data.

Reference

[1] Pseudo-random

[2] Pseudorandom binary sequence