Exercise 2.6: PN Generator of Length 5

• Return to book

PN generator of length  $L = 5$

In the graphic you can see a pseudo-random generator of length  $L = 5$,  which can be used to generate a binary random sequence  $\langle z_{\nu} \rangle$.

• At the start time,  let all memory cells be preallocated with  "ones".
• At each clock time,  the content of the shift register is shifted one place to the right.
• And the currently generated binary value  $z_{\nu}$  $(0$  or  $1)$  is entered into the first memory cell.
• Hereby  $z_{\nu}$  results from the modulo-2 addition between  $z_{\nu-3}$  and  $z_{\nu-5}$.

Hints:

• The exercise belongs to the chapter  Generation of Discrete Random Variables.

• The topic of this chapter is illustrated with examples in the  (German language)  learning video:
      "Erläuterung der PN-Generatoren an einem Beispiel"   $\Rightarrow$   "Explanation of PN generators using an example".

Question

1

What is the generator polynomial  $G(D)$  of the PN generator shown?

	$G(D) = D^5 + D^2 +1$.
	$G(D) = D^5 + D^3 +1$.
	$G(D) = D^4 + D^2 +D$.

2

What octal identifier  $O_{\rm G}$  does this PN generator have?

$O_{\rm G} \ = \ $ $\ \rm (octal)$

3

Assume that the generator polynomial  $G(D)$  is primitive.
Is the initial sequence  $〈z_ν \rangle$  an M-sequence?  How large is the period  $P$?

$P\ = \ $

4

What octal identifier  $O_{\rm R}$  describes the polynomial  $G_{\rm R}(D)$  reciprocal to  $G(D)$?

$O_{\rm R} \ = \ $ $\ \rm (octal)$

5

What statements hold for the configuration with the polynomial  $G_{\rm R}(D)$?

	It is also a sequence of maximum length.
	The output sequence of  $G_{\rm R}(D)$  is the same as that of the generator polynomial  $G(D)$.
	The output sequences of  $G_{\rm R}(D)$  and  $G(D)$  are inverses of each other.
	Both sequences show the same statistical properties.
	In  $G_{\rm R}(D)$  all memory elements can be preallocated with zeros.

Solution

Solution

(1)  Correct is the proposed solution 2   ⇒   $G(D) = D^5 + D^3 +1$.

• The generator polynomial  $G(D)$  denotes the returns used for modulo-2 addition.
• $D$  is a formal parameter indicating a delay by one clock.
• $D^3$  then indicates a delay of three measures.

(2)  It is  $g_0 = g_3 = g_5 = 1$. 

• All other Rückf  coefficients are $0$. It follows that:

$$(g_{\rm 5}\hspace{0.1cm}g_{\rm 4}\hspace{0.1cm}g_{\rm 3}\hspace{0.1cm}g_{\rm 2}\hspace{0.1cm}g_{\rm 1}\hspace{0.1cm}g_{\rm 0})=\rm (101001)_{bin}\hspace{0.15cm} \underline{=(51)_{oct}}.$$

(3)  Since the generator polynomial  $G(D)$  is primitive, one obtains an M-sequence.

• Accordingly, the period is maximal:

$$P_{\rm max} = 2^{L}-1 \hspace{0.15cm}\underline {= 31}.$$

• In the theory part, the table with PN generators of maximum length (M sequences) for degree  $5$  lists the configuration  $(51)_{\rm oct}$.

(4)  The reciprocal polynomial is:

$$G_{\rm R}(D)=D^{\rm 5}\cdot(D^{\rm -5}+\D^{\rm -3}+ 1)= D^{\rm 5}+D^{\rm 2}+1.$$

• Thus, the octal identifier für this configuration  $\rm (100101)_{bin}\hspace{0.15cm} \underline{=(45)_{oct}}.$

(5)  The correct solutions are solutions 1, 3, and 4:

• The initial sequence of the reciprocal realization  $G_{\rm R}(D)$  of a primitive polynomial  $G(D)$  is always also an M-sequence.
• Both sequences are inverses of each other. This means:
• The initial sequence of  $(45)_{\rm oct}$  is equal to the sequence of  $(51)_{\rm oct}$ when read from right to left and additionally taking into account a phase (cyclic shift).
• A precondition is again that not all memory cells are preallocated with zeros.
• Under this condition, both sequences actually also have the same statistical properties.