Difference between revisions of "Theory of Stochastic Signals/Generation of Discrete Random Variables"

From LNTwww
 
(10 intermediate revisions by 2 users not shown)
Line 7: Line 7:
 
==Pseudo-random variables==
 
==Pseudo-random variables==
 
<br>
 
<br>
One way to generate a binary random sequence&nbsp; $〈z_{\rm ν}〉 ∈ \{0, 1\}$&nbsp; with good statistical properties is offered by the so-called&nbsp; &raquo;'''pseudo-random generators'''&laquo;,&nbsp; also known as&nbsp; &raquo;'''PN generators'''&laquo;,&nbsp; where&nbsp; "PN"&nbsp; stands for&nbsp; "pseudo-noise".  
+
One way to generate a binary random sequence&nbsp; $〈z_{\rm ν}〉 ∈ \{0, 1\}$&nbsp; with good statistical properties is offered by the so-called&nbsp; &raquo;'''pseudo-random generators'''&laquo;,&nbsp; also known as&nbsp; &raquo;'''PN generators'''&laquo;,&nbsp; where&nbsp; &raquo;PN&laquo;&nbsp; stands for&nbsp; &raquo;pseudo-noise&laquo;.  
  
 
These have the following properties:  
 
These have the following properties:  
*The binary sequence generated by such a generator is not stochastic in a strict sense,&nbsp; but exhibits periodic and thus deterministic properties.   
+
#The binary sequence generated by such a generator is not stochastic in a strict sense,&nbsp; but exhibits periodic and thus deterministic properties.   
*If the period length&nbsp; $P$&nbsp; is sufficiently large,&nbsp; the sequence appears to an observer as random with sufficiently good statistical properties for many applications.  
+
#If the period length&nbsp; $P$&nbsp; is sufficiently large,&nbsp; the sequence appears to an observer as random with sufficiently good statistical properties for many applications.  
*The advantage of a pseudo-random generator over a&nbsp; "real"&nbsp; stochastic source is that the random sequence is reproducible if a few parameters are known.  
+
#The advantage of a pseudo-random generator over a&nbsp; real&nbsp; stochastic source is that the random sequence is reproducible if a few parameters are known.  
  
  
 
{{GraueBox|TEXT=   
 
{{GraueBox|TEXT=   
$\text{Example 1:}$&nbsp; The latter property also gives rise to the main applications of pseudo-noise generators:
+
$\text{Example 1:}$&nbsp; The latter property also gives rise to the main applications of pseudo-noise generators,
*first, the&nbsp; "error frequency measurement"&nbsp; in digital signal transmission,  
+
# the&nbsp; &raquo;error rate measurement&laquo;&nbsp; in digital signal transmission,  
*secondly,&nbsp; for band spreading in CDMA&nbsp; ("Code Division Multiple Access").  
+
# for&nbsp; &raquo;band spreading&laquo;&nbsp; in CDMA&nbsp; $($Code Division Multiple Access$)$.  
  
  
In such a&nbsp; "Spread Spectrum System"&nbsp; the transmitted signal is modulated with a binary random sequence,&nbsp; whose symbol repetition frequency is significantly higher than the bit frequency.&nbsp; This offers the possibility of multiple channel utilization.&nbsp; Since the same sequence must be added in phase at the receiver,&nbsp; the use of reproducible PN sequences is also common here.  
+
In such a&nbsp; &raquo;Spread Spectrum System&laquo;&nbsp; the transmitted signal is modulated with a binary random sequence,&nbsp; whose symbol repetition frequency is significantly higher than the bit frequency.&nbsp; This offers the possibility of multiple channel utilization.&nbsp; Since the same sequence must be added in phase at the receiver,&nbsp; the use of reproducible pseudo-noise sequences is also common here.  
  
Detailed information on bandspreading methods can be found in the chapter&nbsp; [[Examples_of_Communication_Systems/General_Description_of_UMTS|"UMTS - Universal Mobile Telecommunications System"]]&nbsp; of the book&nbsp; "Examples of Communication Systems".}}
+
Detailed information on bandspreading methods can be found in the chapter&nbsp; [[Examples_of_Communication_Systems/General_Description_of_UMTS|&raquo;UMTS - Universal Mobile Telecommunications System&laquo;]]&nbsp; of the book&nbsp; &raquo;Examples of Communication Systems&laquo;.}}
  
  
 
==Realization of PN generators==
 
==Realization of PN generators==
 
<br>
 
<br>
Pseudo-random generators are usually realized by feedback shift registers,&nbsp; where at each clock instant the content of the register is shifted one place to the right&nbsp; (see diagram).&nbsp; For the currently generated symbol,&nbsp; with&nbsp; $g_l ∈ \{0, 1\}$&nbsp; and&nbsp; $l = 1$, ... , $L-1$:
+
Pseudo-random generators are usually realized by &raquo;feedback shift registers&laquo;,&nbsp; where at each clock instant the content of the register is shifted one place to the right&nbsp; $($see diagram$)$.&nbsp; For the currently generated symbol,&nbsp; with&nbsp; $g_l ∈ \{0, 1\}$&nbsp; and&nbsp; $l = 1$, ... , $L-1$:
 
:$$z_\nu = (g_1\cdot z_{\nu-1}+g_2\cdot z_{\nu-2}+\hspace{0.1cm}\text{...}\hspace{0.1cm}+g_l\cdot z_{\nu-l}+\hspace{0.1cm}\text{...}\hspace{0.1cm}+g_{L-1}\cdot z_{\nu-L+1}+ z_{\nu-L})\hspace{0.1cm} \rm mod \hspace{0.2cm}2.$$
 
:$$z_\nu = (g_1\cdot z_{\nu-1}+g_2\cdot z_{\nu-2}+\hspace{0.1cm}\text{...}\hspace{0.1cm}+g_l\cdot z_{\nu-l}+\hspace{0.1cm}\text{...}\hspace{0.1cm}+g_{L-1}\cdot z_{\nu-L+1}+ z_{\nu-L})\hspace{0.1cm} \rm mod \hspace{0.2cm}2.$$
  
*The binary values&nbsp; $z_{ν-1}$&nbsp; to&nbsp; $z_{ν-L}$&nbsp; generated at previous time points are stored in the memory cells of the shift register.  
+
#The binary values&nbsp; $z_{ν-1}$&nbsp; to&nbsp; $z_{ν-L}$&nbsp; generated at previous time points are stored in the memory cells of the shift register.  
*The coefficients&nbsp; $g_1$, ... ,&nbsp; $g_{L-1}$&nbsp; are also binary values,&nbsp; where a&nbsp; "one"&nbsp; indicates a feedback at the corresponding location and a&nbsp; "zero"&nbsp; indicates no feedback.  
+
#The coefficients&nbsp; $g_1$, ... ,&nbsp; $g_{L-1}$&nbsp; are also binary values,&nbsp; where&nbsp; $1$&nbsp; indicates a feedback at the corresponding location and&nbsp; $0$&nbsp; indicates no feedback.  
*Modulo-2 addition can be implemented,&nbsp; for example,&nbsp; using an XOR operation:  
+
#Modulo-2 addition can be implemented,&nbsp; for example,&nbsp; using an XOR operation:  
 
[[File:EN_Sto_T_2_5_S2.png |right|frame| Pseudo-noise generator]]
 
[[File:EN_Sto_T_2_5_S2.png |right|frame| Pseudo-noise generator]]
 
:$$(x + y)\hspace{0.15cm} \rm mod\hspace{0.15cm}2 = \it x\hspace{0.15cm}\rm XOR\hspace{0.15cm} \it y = \left\{\begin{array}{*{2}{c}} \rm 0 & \rm if\hspace{0.15cm} \it x= y,\\ 1 & \rm if\hspace{0.15cm} \it x\neq y. \\ \end{array} \right.$$
 
:$$(x + y)\hspace{0.15cm} \rm mod\hspace{0.15cm}2 = \it x\hspace{0.15cm}\rm XOR\hspace{0.15cm} \it y = \left\{\begin{array}{*{2}{c}} \rm 0 & \rm if\hspace{0.15cm} \it x= y,\\ 1 & \rm if\hspace{0.15cm} \it x\neq y. \\ \end{array} \right.$$
Line 39: Line 39:
 
The statistical properties of the generated pseudo-noise random sequence&nbsp; $〈z_{\rm ν}〉$&nbsp; are essentially determined by
 
The statistical properties of the generated pseudo-noise random sequence&nbsp; $〈z_{\rm ν}〉$&nbsp; are essentially determined by
 
*the&nbsp; &raquo;'''degree'''&laquo;&nbsp; $L$,&nbsp; and
 
*the&nbsp; &raquo;'''degree'''&laquo;&nbsp; $L$,&nbsp; and
 +
 
*the&nbsp; &raquo;'''feedback coefficients'''&laquo;&nbsp; $g_{\hspace{0.05cm}l}$&nbsp; $($with&nbsp; $l = 1$, ... , $L-1)$.  
 
*the&nbsp; &raquo;'''feedback coefficients'''&laquo;&nbsp; $g_{\hspace{0.05cm}l}$&nbsp; $($with&nbsp; $l = 1$, ... , $L-1)$.  
  
  
A prerequisite for the generation of a PN sequence is that not all memory elements are preallocated with zeros, otherwise the modulo-2 addition would always generate the symbol&nbsp; "$0$".  
+
A prerequisite for the generation of a pseudo-noise sequence is that not all memory elements are preallocated with zeros,&nbsp; otherwise the modulo-2 addition would always generate the symbol&nbsp; $0$.  
  
To identify different PN generators one uses in the literature alternatively:  
+
To identify different pseudo-noise generators one uses in the literature alternatively:  
*The&nbsp; &raquo;'''generator polynomials'''&laquo;&nbsp; of the type
+
*The&nbsp; &raquo;'''generator polynomial'''&laquo;&nbsp;
 
:$$G(D) = g_L\cdot D^L+g_{L-1}\cdot D^{L-1}+ \ \text{...} \ +g_1\cdot D+g_0 .$$
 
:$$G(D) = g_L\cdot D^L+g_{L-1}\cdot D^{L-1}+ \ \text{...} \ +g_1\cdot D+g_0 .$$
 
:Here,&nbsp;  $g_0 = g_L = 1$&nbsp; is always to be set;&nbsp; $D$&nbsp; is a formal parameter indicating a delay by one clock&nbsp; $(D^L$&nbsp; indicates a delay by&nbsp; $L$&nbsp; clocks$)$.
 
:Here,&nbsp;  $g_0 = g_L = 1$&nbsp; is always to be set;&nbsp; $D$&nbsp; is a formal parameter indicating a delay by one clock&nbsp; $(D^L$&nbsp; indicates a delay by&nbsp; $L$&nbsp; clocks$)$.
 
   
 
   
*The&nbsp; &raquo;'''octal representation'''&laquo;&nbsp; of the binary number&nbsp; $(g_L\ \text{ ...} \ g_2 \ g_1 \ g_0)$.&nbsp; It is important that here the feedback coefficients &ndash; starting from the right with&nbsp; $g_0$&nbsp; &ndash; are combined into triples and these are written octal&nbsp; $(0 \ \text{...}\ 7)$.
+
*The&nbsp; &raquo;'''octal representation'''&laquo;&nbsp; of the binary number&nbsp; $(g_L\ \text{ ...} \ g_2 \ g_1 \ g_0)$.&nbsp; <br>It is important that the feedback coefficients &ndash; starting from the right with&nbsp; $g_0$&nbsp; &ndash; are combined into triples and these are written octal&nbsp; $(0 \ \text{...}\ 7)$.
  
  
Line 55: Line 56:
 
$\text{Example 2:}$&nbsp;
 
$\text{Example 2:}$&nbsp;
 
The generator polynomial&nbsp; $D^4 + D^3 + 1$&nbsp; belongs to a shift register of degree&nbsp; $L = 4$&nbsp; with the following octal representation.  
 
The generator polynomial&nbsp; $D^4 + D^3 + 1$&nbsp; belongs to a shift register of degree&nbsp; $L = 4$&nbsp; with the following octal representation.  
:$$(g_4 \ g_3 \ g_2 \ g_1 \ g_0) = (11001)_{\rm bin} = (31)_{\rm oct}. $$}}
+
:$$(g_4 \ g_3 \ g_2 \ g_1 \ g_0) = (11\hspace{0.05cm} 001)_{\rm bin} = (31)_{\rm oct}. $$}}
  
 
==Sequences of maximum length (M-sequences)==
 
==Sequences of maximum length (M-sequences)==
 
<br>
 
<br>
 
If not all&nbsp; $L$&nbsp; memory cells of the shift register are preallocated with zeros,&nbsp; a periodic random sequence&nbsp; $〈z_ν\rangle$ always results:
 
If not all&nbsp; $L$&nbsp; memory cells of the shift register are preallocated with zeros,&nbsp; a periodic random sequence&nbsp; $〈z_ν\rangle$ always results:
[[File: EN_Sto_T_2_5_S5.png|right|frame|Composition of some favorable generator polynomials '''Korrektur:''' identisch, Polynom]]  
+
[[File:EN_Sto_T_2_5_S5_neu.png|right|frame|Composition of some favorable generator polynomials]]  
*The period length&nbsp; $P$&nbsp; of this sequence depends to a strong degree on the feedback coefficients.  
+
*The period length&nbsp; $P$&nbsp; of the pseudo-noise sequence depends to a strong degree on the feedback coefficients.  
 
*For each degree&nbsp; $L$&nbsp; there is at least one configuration with&nbsp; &raquo;'''maximum period length'''&laquo;
 
*For each degree&nbsp; $L$&nbsp; there is at least one configuration with&nbsp; &raquo;'''maximum period length'''&laquo;
 
:$$P_{\rm max} = \rm 2^{\it L}-\rm 1.$$
 
:$$P_{\rm max} = \rm 2^{\it L}-\rm 1.$$
*Such a PN sequence is also often referred to as&nbsp; &raquo;'''M-sequence'''&laquo;,&nbsp; where the&nbsp; "M"&nbsp; stands for&nbsp; "Maximum".  
+
*Such a pseudo-noise sequence is also often referred to as&nbsp; &raquo;'''M-sequence'''&laquo;,&nbsp; where the&nbsp; &raquo;$\rm M$&laquo;&nbsp; stands for&nbsp; &raquo;maximum&laquo;.  
<br><br><br><br><br><br><br>  
+
<br><br>  
The table on the right lists PN generators of maximum length up to degree&nbsp; $L = 31$&nbsp;.  
+
The table lists pseudo-noise generators of maximum length up to degree&nbsp; $L = 31$.
*The selection is limited to configurations with only one tap &ndash; that is, with two returns.  
+
 
*This means that the associated polynomials consist of only three summands.  
+
<u>Note:</u>
*For applications that require high speed, such generators are very useful.
+
#The selection is limited to configurations with only one tap&nbsp; $($two returns$)$.  
 +
#This means that the associated polynomials consist of only three summands.  
 +
#For applications that require high speed, such generators are very useful.
 
<br clear=all>
 
<br clear=all>
 
{{BlueBox|TEXT=   
 
{{BlueBox|TEXT=   
$\text{For now, without proof:}$&nbsp;  
+
$\text{For now without proof:}$&nbsp;
#&nbsp; A&nbsp; &raquo;'''M-sequence'''&laquo;&nbsp; can be recognized by the fact that the generator polynomial&nbsp; $G(D)$&nbsp; is primitive.&nbsp;
+
#&nbsp; As detailed in the book&nbsp; [[Channel_Coding|"Channel Coding"]],&nbsp; a polynomial&nbsp; $G(D)$&nbsp; of degree&nbsp; $L$&nbsp; is called&nbsp; &raquo;'''primitive'''&laquo; if the following condition is satisfied:  
+
$(1)$&nbsp; An&nbsp; &raquo;'''M-sequence'''&laquo;&nbsp; can be recognized by the fact that the generator polynomial&nbsp; $G(D)$&nbsp; is&nbsp; &raquo;'''primitive'''&laquo;.&nbsp;
::$$\frac{D^n+ 1}{G(D)} \neq 0\hspace{0.5cm} {\rm for}\hspace{0.5cm}\it n<P_{\rm max} \rm = \rm 2^{\it L}-\rm 1.$$}}  
+
 
 +
$(2)$&nbsp; As detailed in the book&nbsp; [[Channel_Coding|&raquo;Channel Coding&laquo;]],&nbsp; a polynomial&nbsp; $G(D)$&nbsp; of degree&nbsp; $L$&nbsp; is called&nbsp; &raquo;primitive&laquo; if the following condition is satisfied:  
 +
::$${\rm For}\hspace{0.2cm}\it n<P_{\rm max} \rm = \rm 2^{\it L}-\rm 1\text{:}\hspace{0.5cm}\frac{D^n+ 1}{G(D)} \neq 0. $$}}  
 
<br clear=all>
 
<br clear=all>
 
{{GraueBox|TEXT=   
 
{{GraueBox|TEXT=   
 
$\text{Example 3:}$&nbsp; A shift register of degree&nbsp; $L = 4$&nbsp; with octal identifier&nbsp; $(31)$&nbsp; and generator polynomial&nbsp; $G(D) = D^4 + D^3 + 1$&nbsp; leads to a sequence of maximum length:  
 
$\text{Example 3:}$&nbsp; A shift register of degree&nbsp; $L = 4$&nbsp; with octal identifier&nbsp; $(31)$&nbsp; and generator polynomial&nbsp; $G(D) = D^4 + D^3 + 1$&nbsp; leads to a sequence of maximum length:  
 
:$$P_{\rm max} = 2^4 - 1 = 15.$$  
 
:$$P_{\rm max} = 2^4 - 1 = 15.$$  
The mathematical proof for this is complex:  
+
The mathematical proof for this equation is rathercomplex:  
*Using the above polynomial division for&nbsp; $n = 1$, &nbsp;...&nbsp; , $14$&nbsp; one must show that the quotient is always nonzero.  
+
#Using the above polynomial division for&nbsp; $n = 1$, &nbsp;...&nbsp; , $14$&nbsp; one must show that the quotient is always non&ndash;zero.  
*First the division&nbsp; $(D^{15} + 1)/G(D)$&nbsp; may give a result without remainder.  
+
#First the division&nbsp; $(D^{15} + 1)/G(D)$&nbsp; may give a result without remainder.  
*Here it is to be considered that in the modulo-2 algebra&nbsp; $+1$&nbsp; and&nbsp; $-1$&nbsp; are identical. }}
+
#Here it is to be considered that in the modulo-2 algebra&nbsp; $+1$&nbsp; and&nbsp; $-1$&nbsp; are identical. }}
  
 
==Reciprocal polynomials==
 
==Reciprocal polynomials==
Line 93: Line 98:
  
  
Between the two shift registers with polynomials&nbsp; $G(D)$&nbsp; and&nbsp; $G_{\rm R}(D)$&nbsp; respectively,&nbsp; there are the following relations:  
+
There are the following relations between the two shift registers with polynomials&nbsp; $G(D)$&nbsp; resp.&nbsp; $G_{\rm R}(D)$:  
*If&nbsp; $G(D)$&nbsp; provides a sequence of maximum length &nbsp; ⇒ &nbsp; $P_{\rm max} = 2^L - 1$,&nbsp; then the period length of the reciprocal polynomial&nbsp; $G_{\rm R}(D)$&nbsp; is also maximum.  
+
#If&nbsp; $G(D)$&nbsp; provides a sequence of maximum length &nbsp; ⇒ &nbsp; $P_{\rm max} = 2^L - 1$,&nbsp; then the period length of the reciprocal polynomial&nbsp; $G_{\rm R}(D)$&nbsp; is also maximum.  
*The output sequences of reciprocal configurations are inverses of each other.&nbsp; That is:  
+
#The output sequences of reciprocal configurations are&nbsp; &raquo;inverses of each other&laquo;. &nbsp; That is:<br> &nbsp; &nbsp; &nbsp; The sequence of&nbsp; $G(D)$ &ndash; read from right to left &ndash; gives the sequence of the reciprocal configuration&nbsp; $G_{\rm R}(D)$.  
*The sequence of&nbsp; $G(D)$ &ndash; read from right to left &ndash; gives the sequence of the reciprocal configuration&nbsp; $G_{\rm R}(D)$.  
 
  
  
Line 103: Line 107:
 
{{GraueBox|TEXT=   
 
{{GraueBox|TEXT=   
 
$\text{Example 4:}$&nbsp;
 
$\text{Example 4:}$&nbsp;
We consider again the degree&nbsp; $L = 4$.  
+
We consider again a pseudo-noise generator with degree&nbsp; $L = 4$&nbsp; and shift register structure&nbsp; $(31)_{\rm oct}$&nbsp;:
 +
:$$G(D) =  1+D^{3} + D^{4}.$$
  
*Based on the shift register structure&nbsp; $(31)_{\rm oct}$&nbsp; we obtain for the reciprocal polynomial:  
+
* For the reciprocal polynomial we obtain the configuration with the octal identifier&nbsp; $(23)$:  
:$$G_{\rm R}(D) = D^{\rm 4}\cdot (1+D^{-3} + D^{ -4})=D^{ 4}+D^{1}+\rm 1$$
+
:$$G_{\rm R}(D) = D^{\rm 4}\cdot (1+D^{-3} + D^{ -4})=D^{ 4}+D^{1}+\rm 1.$$
 
+
:and thus the configuration with the octal identifier&nbsp; $(23)$.
 
 
*The corresponding output sequences each have the maximum period length&nbsp; $P_{\rm max} = 15$&nbsp; and are inverses of each other:  
 
*The corresponding output sequences each have the maximum period length&nbsp; $P_{\rm max} = 15$&nbsp; and are inverses of each other:  
 
:* ... $0 \ 0 \ 0 \ 1 \ 0 \ 0 \ 1 \ 1 \ 0 \ 1 \ 0 \ 1 \ 1 \ 1 \ 1$ ...  
 
:* ... $0 \ 0 \ 0 \ 1 \ 0 \ 0 \ 1 \ 1 \ 0 \ 1 \ 0 \ 1 \ 1 \ 1 \ 1$ ...  
Line 114: Line 118:
  
 
*This means that the upper initial sequence of&nbsp; $(31)$,&nbsp; read from right to left,&nbsp; yields the sequence of reciprocal order&nbsp; $(23)$&nbsp; given below.  
 
*This means that the upper initial sequence of&nbsp; $(31)$,&nbsp; read from right to left,&nbsp; yields the sequence of reciprocal order&nbsp; $(23)$&nbsp; given below.  
 +
 
*However,&nbsp; a cyclic phase shift of four binary digits can be seen. }}
 
*However,&nbsp; a cyclic phase shift of four binary digits can be seen. }}
  
  
:The topic of this chapter is illustrated with examples in the&nbsp; (German language)&nbsp;  learning video: <br> &nbsp; &nbsp; [[Erläuterung_der_PN–Generatoren_an_einem_Beispiel_(Lernvideo)|"Erläuterung der PN-Generatoren an einem Beispiel"]]&nbsp; $\Rightarrow$ Explanation of PN generators using an example.
+
==Generation of multi-level random variables==
 
 
 
 
==Generation of multilevel random variables==
 
 
<br>
 
<br>
Many high-level programming languages provide pseudo-random generators that return real random numbers&nbsp; $x$&nbsp; equally distributed between&nbsp; $0$&nbsp; and&nbsp; $1$.&nbsp;  For example,&nbsp; a corresponding C&nbsp; function call is:  
+
Many high-level programming languages provide pseudo-random generators that return real random numbers&nbsp; $x$&nbsp; equally distributed between&nbsp; $0$&nbsp; and&nbsp; $1$.&nbsp;  For example,&nbsp; a corresponding C&ndash;function call is:  
  
 
:$$x = \text{random()}.$$
 
:$$x = \text{random()}.$$
  
By successively calling this&nbsp; "random function",&nbsp; a periodically repeating sequence of real numbers is created,&nbsp; where all values&nbsp; $0 \le x < 1$&nbsp; are equally likely &nbsp; &rArr; &nbsp; see chapter&nbsp; [[Theory_of_Stochastic_Signals/Uniformly_Distributed_Random_Variables|"Uniformly Distributed Random Variables"]].  
+
By successively calling this&nbsp; random function,&nbsp; a periodically repeating sequence of real numbers is created,&nbsp; where all values&nbsp; $0 \le x < 1$&nbsp; are equally likely <br>(see chapter&nbsp; [[Theory_of_Stochastic_Signals/Uniformly_Distributed_Random_Variables|&raquo;Uniformly Distributed Random Variables&raquo;$)$]].  
*However,&nbsp; since the period&nbsp; $P$&nbsp; is very large,&nbsp; this sequence can be considered as&nbsp; "pseudo-random".  
+
#However,&nbsp; since the period&nbsp; $P$&nbsp; is very large,&nbsp; this sequence can be considered as&nbsp; &raquo;pseudo-random&laquo;.  
*By specifying a starting value,&nbsp; the pseudo-random sequence is started at certain points.  
+
#By specifying a starting value,&nbsp; the pseudo-random sequence is started at certain points.  
  
  
Line 135: Line 137:
 
{{GraueBox|TEXT=   
 
{{GraueBox|TEXT=   
 
$\text{Example 5:}$&nbsp;
 
$\text{Example 5:}$&nbsp;
The graphic shows the principle for the special case&nbsp; $M = 3$ &nbsp; &rArr; &nbsp; ternary random sequence&nbsp; $〈z_{\rm ν}〉$&nbsp; with&nbsp; $z_{\rm ν} ∈ \{0,\ 1,\ 2\}$.&nbsp; Assumed here is the between&nbsp; $0$&nbsp; and&nbsp; $1$&nbsp; uniformly distributed random variable&nbsp; $x$.  
+
The graphic shows the principle for the special case&nbsp; $M = 3$ &nbsp; &rArr; &nbsp; ternary random sequence&nbsp; $〈z_{\rm ν}〉$&nbsp; with&nbsp; $z_{\rm ν} ∈ \{0,\ 1,\ 2\}$.&nbsp;  
[[File:P_ID457__Sto_T_2_5_S6neu.png|right|frame|For generating multilevel random variables]]
+
[[File:P_ID457__Sto_T_2_5_S6neu.png|right|frame|For generating multi-level  random variables]]
The desired probabilities are designated as follows:
+
*Assumed is the between&nbsp; $0$&nbsp; and&nbsp; $1$&nbsp; uniformly distributed random variable&nbsp; $x$.
*$p_0 = {\rm Pr}(z_{\rm ν} =0)$,
+
*$p_1 = {\rm Pr}(z_{\rm ν} =1)$,
+
*The desired probabilities are designated as follows:
*$p_2 = {\rm Pr}(z_{\rm ν} =2)$.  
+
:$$p_0 = {\rm Pr}(z_{\rm ν} =0),\hspace{0.5cm} p_1 = {\rm Pr}(z_{\rm ν} =1),\hspace{0.5cm} p_2 = {\rm Pr}(z_{\rm ν} =2). $$
 +
 
 +
Then holds:
 +
#If the current&nbsp; $x_{\rm ν} <p_0$,&nbsp; then the ternary random variable is set to&nbsp; $z_{\rm ν} = 0$.  
 +
#In the range&nbsp; $p_0 ≤ x_{\rm ν} < p_0 + p_1$&nbsp; the output is&nbsp; $z_{\rm ν} = 1$&nbsp;.
 +
#For&nbsp; $x_{\rm ν} \ge p_0 + p_1$&nbsp; the ternary random variable becomes&nbsp; $z_{\rm ν} =2$.
 +
 
 +
 
 +
In the listed C&ndash;program,
 +
*we get for&nbsp; $M = 3$&nbsp; and for the current random value&nbsp; $x = 0.57$&nbsp;
  
 +
*the product&nbsp; $x · M = 0.57 · 3 = 1.71$&nbsp; and thus the ternary random variable&nbsp; $z = 1$.
  
 +
*For an other random value&nbsp; $x = 0.95$&nbsp; on the other hand,&nbsp; the function would return the result&nbsp; $z = 2$.
  
Then holds:
 
*If the current&nbsp; $x_{\rm ν} <p_0$,&nbsp; then the ternary random variable is set to&nbsp; $z_{\rm ν} = 0$.
 
*In the range&nbsp; $p_0 ≤ x_{\rm ν} < p_0 + p_1$&nbsp; the output is&nbsp; $z_{\rm ν} = 1$&nbsp;.
 
*For&nbsp; $x_{\rm ν} \ge p_0 + p_1$&nbsp; the ternary random variable becomes&nbsp; $z_{\rm ν} =2$.
 
<br clear=all>
 
In the C program listed, for&nbsp; $M = 3$&nbsp; and for the current random value&nbsp; $x = 0.57$&nbsp; we get the product&nbsp; $x · M = 0.57 · 3 = 1.71$&nbsp; and thus the ternary random variable&nbsp; $z = 1$. For an other random value&nbsp; $x = 0.95$&nbsp; on the other hand,&nbsp; the function would return the result&nbsp; $z = 2$.
 
  
For reasons of comprehension,&nbsp; a cumbersome programming was chosen here&nbsp; The given C program part could also be written more compactly:  
+
For reasons of comprehension,&nbsp; a cumbersome programming was chosen here.&nbsp; The given C&ndash;program part could also be written more compactly:  
  
 
:$$\text{\{ float random(); return((long) (random()*M)); \} }$$}}
 
:$$\text{\{ float random(); return((long) (random()*M)); \} }$$}}

Latest revision as of 18:39, 8 February 2024

Pseudo-random variables


One way to generate a binary random sequence  $〈z_{\rm ν}〉 ∈ \{0, 1\}$  with good statistical properties is offered by the so-called  »pseudo-random generators«,  also known as  »PN generators«,  where  »PN«  stands for  »pseudo-noise«.

These have the following properties:

  1. The binary sequence generated by such a generator is not stochastic in a strict sense,  but exhibits periodic and thus deterministic properties.
  2. If the period length  $P$  is sufficiently large,  the sequence appears to an observer as random with sufficiently good statistical properties for many applications.
  3. The advantage of a pseudo-random generator over a  real  stochastic source is that the random sequence is reproducible if a few parameters are known.


$\text{Example 1:}$  The latter property also gives rise to the main applications of pseudo-noise generators,

  1. the  »error rate measurement«  in digital signal transmission,
  2. for  »band spreading«  in CDMA  $($Code Division Multiple Access$)$.


In such a  »Spread Spectrum System«  the transmitted signal is modulated with a binary random sequence,  whose symbol repetition frequency is significantly higher than the bit frequency.  This offers the possibility of multiple channel utilization.  Since the same sequence must be added in phase at the receiver,  the use of reproducible pseudo-noise sequences is also common here.

Detailed information on bandspreading methods can be found in the chapter  »UMTS - Universal Mobile Telecommunications System«  of the book  »Examples of Communication Systems«.


Realization of PN generators


Pseudo-random generators are usually realized by »feedback shift registers«,  where at each clock instant the content of the register is shifted one place to the right  $($see diagram$)$.  For the currently generated symbol,  with  $g_l ∈ \{0, 1\}$  and  $l = 1$, ... , $L-1$:

$$z_\nu = (g_1\cdot z_{\nu-1}+g_2\cdot z_{\nu-2}+\hspace{0.1cm}\text{...}\hspace{0.1cm}+g_l\cdot z_{\nu-l}+\hspace{0.1cm}\text{...}\hspace{0.1cm}+g_{L-1}\cdot z_{\nu-L+1}+ z_{\nu-L})\hspace{0.1cm} \rm mod \hspace{0.2cm}2.$$
  1. The binary values  $z_{ν-1}$  to  $z_{ν-L}$  generated at previous time points are stored in the memory cells of the shift register.
  2. The coefficients  $g_1$, ... ,  $g_{L-1}$  are also binary values,  where  $1$  indicates a feedback at the corresponding location and  $0$  indicates no feedback.
  3. Modulo-2 addition can be implemented,  for example,  using an XOR operation:
Pseudo-noise generator
$$(x + y)\hspace{0.15cm} \rm mod\hspace{0.15cm}2 = \it x\hspace{0.15cm}\rm XOR\hspace{0.15cm} \it y = \left\{\begin{array}{*{2}{c}} \rm 0 & \rm if\hspace{0.15cm} \it x= y,\\ 1 & \rm if\hspace{0.15cm} \it x\neq y. \\ \end{array} \right.$$

The statistical properties of the generated pseudo-noise random sequence  $〈z_{\rm ν}〉$  are essentially determined by

  • the  »degree«  $L$,  and
  • the  »feedback coefficients«  $g_{\hspace{0.05cm}l}$  $($with  $l = 1$, ... , $L-1)$.


A prerequisite for the generation of a pseudo-noise sequence is that not all memory elements are preallocated with zeros,  otherwise the modulo-2 addition would always generate the symbol  $0$.

To identify different pseudo-noise generators one uses in the literature alternatively:

  • The  »generator polynomial« 
$$G(D) = g_L\cdot D^L+g_{L-1}\cdot D^{L-1}+ \ \text{...} \ +g_1\cdot D+g_0 .$$
Here,  $g_0 = g_L = 1$  is always to be set;  $D$  is a formal parameter indicating a delay by one clock  $(D^L$  indicates a delay by  $L$  clocks$)$.
  • The  »octal representation«  of the binary number  $(g_L\ \text{ ...} \ g_2 \ g_1 \ g_0)$. 
    It is important that the feedback coefficients – starting from the right with  $g_0$  – are combined into triples and these are written octal  $(0 \ \text{...}\ 7)$.


$\text{Example 2:}$  The generator polynomial  $D^4 + D^3 + 1$  belongs to a shift register of degree  $L = 4$  with the following octal representation.

$$(g_4 \ g_3 \ g_2 \ g_1 \ g_0) = (11\hspace{0.05cm} 001)_{\rm bin} = (31)_{\rm oct}. $$

Sequences of maximum length (M-sequences)


If not all  $L$  memory cells of the shift register are preallocated with zeros,  a periodic random sequence  $〈z_ν\rangle$ always results:

Composition of some favorable generator polynomials
  • The period length  $P$  of the pseudo-noise sequence depends to a strong degree on the feedback coefficients.
  • For each degree  $L$  there is at least one configuration with  »maximum period length«
$$P_{\rm max} = \rm 2^{\it L}-\rm 1.$$
  • Such a pseudo-noise sequence is also often referred to as  »M-sequence«,  where the  »$\rm M$«  stands for  »maximum«.



The table lists pseudo-noise generators of maximum length up to degree  $L = 31$.

Note:

  1. The selection is limited to configurations with only one tap  $($two returns$)$.
  2. This means that the associated polynomials consist of only three summands.
  3. For applications that require high speed, such generators are very useful.


$\text{For now without proof:}$ 

$(1)$  An  »M-sequence«  can be recognized by the fact that the generator polynomial  $G(D)$  is  »primitive«. 

$(2)$  As detailed in the book  »Channel Coding«,  a polynomial  $G(D)$  of degree  $L$  is called  »primitive« if the following condition is satisfied:

$${\rm For}\hspace{0.2cm}\it n<P_{\rm max} \rm = \rm 2^{\it L}-\rm 1\text{:}\hspace{0.5cm}\frac{D^n+ 1}{G(D)} \neq 0. $$


$\text{Example 3:}$  A shift register of degree  $L = 4$  with octal identifier  $(31)$  and generator polynomial  $G(D) = D^4 + D^3 + 1$  leads to a sequence of maximum length:

$$P_{\rm max} = 2^4 - 1 = 15.$$

The mathematical proof for this equation is rathercomplex:

  1. Using the above polynomial division for  $n = 1$,  ...  , $14$  one must show that the quotient is always non–zero.
  2. First the division  $(D^{15} + 1)/G(D)$  may give a result without remainder.
  3. Here it is to be considered that in the modulo-2 algebra  $+1$  and  $-1$  are identical.

Reciprocal polynomials


$\text{Definition:}$  The  »reciprocal polynomial«  associated with the generator polynomial  $G(D)$  is:

$$G_{\rm R}(D)=D^{L}\cdot G(D^{-1}).$$


There are the following relations between the two shift registers with polynomials  $G(D)$  resp.  $G_{\rm R}(D)$:

  1. If  $G(D)$  provides a sequence of maximum length   ⇒   $P_{\rm max} = 2^L - 1$,  then the period length of the reciprocal polynomial  $G_{\rm R}(D)$  is also maximum.
  2. The output sequences of reciprocal configurations are  »inverses of each other«.   That is:
          The sequence of  $G(D)$ – read from right to left – gives the sequence of the reciprocal configuration  $G_{\rm R}(D)$.


In the  $\text{table above}$  the reciprocal polynomials  $G_{\rm R}(D)$  associated to  $G(D)$  are given in the third column up to register degree  $L = 31$ .

$\text{Example 4:}$  We consider again a pseudo-noise generator with degree  $L = 4$  and shift register structure  $(31)_{\rm oct}$ :

$$G(D) = 1+D^{3} + D^{4}.$$
  • For the reciprocal polynomial we obtain the configuration with the octal identifier  $(23)$:
$$G_{\rm R}(D) = D^{\rm 4}\cdot (1+D^{-3} + D^{ -4})=D^{ 4}+D^{1}+\rm 1.$$
  • The corresponding output sequences each have the maximum period length  $P_{\rm max} = 15$  and are inverses of each other:
  • ... $0 \ 0 \ 0 \ 1 \ 0 \ 0 \ 1 \ 1 \ 0 \ 1 \ 0 \ 1 \ 1 \ 1 \ 1$ ...
  • ... $0 \ 1 \ 0 \ 1 \ 1 \ 0 \ 0 \ 1 \ 0 \ 0 \ 0 \ 1 \ 1 \ 1 \ 1$ ...
  • This means that the upper initial sequence of  $(31)$,  read from right to left,  yields the sequence of reciprocal order  $(23)$  given below.
  • However,  a cyclic phase shift of four binary digits can be seen.


Generation of multi-level random variables


Many high-level programming languages provide pseudo-random generators that return real random numbers  $x$  equally distributed between  $0$  and  $1$.  For example,  a corresponding C–function call is:

$$x = \text{random()}.$$

By successively calling this  random function,  a periodically repeating sequence of real numbers is created,  where all values  $0 \le x < 1$  are equally likely
(see chapter  »Uniformly Distributed Random Variables»$)$.

  1. However,  since the period  $P$  is very large,  this sequence can be considered as  »pseudo-random«.
  2. By specifying a starting value,  the pseudo-random sequence is started at certain points.


When generating a discrete-value multilevel random variable  $z$  it is convenient to assume such a uniformly distributed random variable  $x$.

$\text{Example 5:}$  The graphic shows the principle for the special case  $M = 3$   ⇒   ternary random sequence  $〈z_{\rm ν}〉$  with  $z_{\rm ν} ∈ \{0,\ 1,\ 2\}$. 

For generating multi-level random variables
  • Assumed is the between  $0$  and  $1$  uniformly distributed random variable  $x$.
  • The desired probabilities are designated as follows:
$$p_0 = {\rm Pr}(z_{\rm ν} =0),\hspace{0.5cm} p_1 = {\rm Pr}(z_{\rm ν} =1),\hspace{0.5cm} p_2 = {\rm Pr}(z_{\rm ν} =2). $$

Then holds:

  1. If the current  $x_{\rm ν} <p_0$,  then the ternary random variable is set to  $z_{\rm ν} = 0$.
  2. In the range  $p_0 ≤ x_{\rm ν} < p_0 + p_1$  the output is  $z_{\rm ν} = 1$ .
  3. For  $x_{\rm ν} \ge p_0 + p_1$  the ternary random variable becomes  $z_{\rm ν} =2$.


In the listed C–program,

  • we get for  $M = 3$  and for the current random value  $x = 0.57$ 
  • the product  $x · M = 0.57 · 3 = 1.71$  and thus the ternary random variable  $z = 1$.
  • For an other random value  $x = 0.95$  on the other hand,  the function would return the result  $z = 2$.


For reasons of comprehension,  a cumbersome programming was chosen here.  The given C–program part could also be written more compactly:

$$\text{\{ float random(); return((long) (random()*M)); \} }$$


Exercises for the chapter


Exercise 2.6: PN Generator of Length 5

Exercise 2.6Z: PN Generator of Length 3

Exercise 2.7: C Programs "z1" and "z2"

Exercise 2.7Z: C Program "z3"