Maximal-Length Sequence , PSEUDO-NOISE (PN) SEQUENCES , what is pseudo noise sequence ? pn sequence generator problems , advantages of pn sequence
PSEUDO-NOISE (PN) SEQUENCES
A pseudo-noise (PN) or pseudorandom sequence is a binary sequence with an autocorrelation that resembles, over a period, the autocorrelation of a random binary sequence. Its autocorrelation also roughly resembles the autocorrelation of bandlimited white noise. Although it is deterministic a pseudonoise sequence has many characteristics that are similar to those of random binary sequences, such as having a nearly equal number of 0s and 1s, very low correlation between shifted versions of the sequence, very low cross correlation between any two sequences, etc. The PN sequence is usually generated using sequential logic circuits. A feedback shift register, which is shown in figure 11.1, consists of consecutive stages of two state memory devices and feedback locig. Binary sequences are shifted through the shift registers in response to clock pulses, and the output of the various stages are logically combined and fed back as the input to the first-stage. ‘1,y-hen the feedback logic consists of exclusive-OR gates, which is usually the case, the shift register is called a linear PN sequence generator.
diagram
FIGURE 11.1 Block diagram of a generalized feedback shift register with m stages
The initial contents of the memory stages and the feedback logic circuit determine the successive contents of the memory. If a linear shift register reaches zero state at some time, it would always remain in the zero state, and the output would subsequently be all 0s. Since there are exactly 2m-1 non zero states for an
m-stage feedback shift register, the period of a PN sequence produced by a linear m-stage shift register cannot exceed 2m – 1 symbols. A sequence of period 2m – 1 generated by a linear feedback register is called a maximal length (ML) sequence.
Let sj(k) denote the state of the jth flip-flop after the kth clock pulse; this state may be represented by symbol 0 or 1. The state of the shift register after the kth clock pulse is then defined by the set {s1(k), s2(k), … sm(k)}, where k > 0. For the initial state, k is zero. From the definition of a shift register, we have
sj (k + 1) = sj – 1 (k),
| DO YOU KNOW? |
| Spread-spectrum systems, in general, are digital commu-nication systems; in a loose sense, the comparable analog technique is frequency modulation (FM), although it is not usually considered a form of spread spectrum. |
where s0(k) is the input applied to the first flip-flop after the kth clock pulse. According to the configuration described in figure 11.1, s0(k) is a Boolean function of the individual states s1(k), s2(k), ….. sm(k). For a specified length m, this Boolean function uniquely determines the subsequent sequence of states and therefore the PN sequence produced at the output of the final flip-flop in the shift register. With a total number of m flip-flops, the number of possible states of the shift register is at most 2m. Therefore, it follows that the PN sequence generated by a feedback shift register must eventually become periodic with a period of at most 2m.
A feedback shift register is said to be linear when the feedback logic consists entirely of modulo-2 adders. In such a case, the zero state (e.g. the state for which all the flip-flops are in state 0) is not permitted. We say so because for a zero state, the input s0(k) produced by the feedback logic would therefore consist entirely of 0s. Consequently, the period of a PN sequence produced by a linear feedback shift register with m flip-flops cannot exceed 2m -1. When the period is exactly 2m – 1, the PN sequence is called a maximal-length-sequence or simply m-sequence.
EXAMPLE 11.1 Given the linear feedback shift register shown in figure 11.2, involving three flip-flops. The input s0 applied to the first flip-flop is equal to the modulo-2 sum of s1, and s2. It is assumed that the initial state of the shift register is 100 (reading the contents of the three flip-flops from left to right). Then, the succession of states will be as under:
100, 110, 111, 011, 101, 010, 001, 100, …..
The output sequence (the last position of each state of the shift register) is therefore
00111010…
diagram
FIGURE 11.2 Maximal-length sequence generator for m = 3
which repeats itself with period 23– 1 = 7.
It may be noted that the choice of 100 as the initial state is arbitrary. Any of the other six permissible states could serve equally well as an initial state. The resulting output sequence would then simply experience a cyclic shift.
11.2.1. Properties of Maximal-Length Sequences
Maximal-length sequences have many of the properties possessed by a truly random binary sequence. A random binary sequence is a sequence in which the presence of binary symbol 1 or 0 is equally probable. Some properties of maximal-length sequences are as follows :
- In each period of a maximal-length sequence, the number of is 1s always one more than the number of 0s. This property is called the balance property.
| DO YOU KNOW? |
| Spread-spectrum systems encompass modulation tech-niques in which the signal of interest, with an information bandwidth Rb, is spread to occupy a much larger trans-mission bondwidth Rc. |
- Among the runs of 1s and of 0s in each period of a maximal-length sequence, one half the runs of each kind are of length one, one-fourth are of length two, one-eighth are of length three, and so on as long as these fractions represent meaningful numbers of runs. This property is called the run property. By a “run”, we mean a subsequence of identical symbols (1s or 0s) within one period of the sequence. The length of this subsequence is the length of the run. For a maximal-length sequence generated by a linear feedback shift register of length m, the total number of runs is (N + 1)/2, where N = 2m – 1.
- The autocorrelation function of a maximal-length sequence is periodic and binary valued. This property is called the correlation property.
The period of a maximum- length sequence is defined by
N = 2m – 1 …(11.2)
where m is the length of the shift register. Let binary symbols 0 and 1 of the sequence be denoted by the levels – 1 and + 1, respectively. Let c(t) denote the resulting waveform of the maximal-length sequence, as illustrated in figure 11.3 (a) for N = 7. The period of the waveform c(t) is (based on terminology used in subsequent sections)
Tb = NTc, …(11.3)
diagram
FIGURE 11.3 (a) Waveform of maximal-length sequence for length in = 3 or period N = 7. (b) Autocorrelation function. (c) Power spectral density. All three parts refer to the output of the feedback shift register of figure 11.2.
where Tc is the duration assigned to symbol 1 or 0 in the maximal-length sequence. By definition, the autocorrelation function of a periodic signal c(t) of period Tb is
equation
where the lag lies in the interval (-Tb/2, Tb/2);
We have
equation
This result is plotted in figure 11.3(b) for the case of m = 3 or N = 7.
From Fourier transform theory, we know that periodicity in the time domain is transformed into uniform sampling in the frequency domain. This interplay between the time and frequency domains is borne out by the power spectral density of the maximal-length wave c(t). Specifically, taking the Fourier transform of equation (11.5), we get the sampled spectrum as under:
equation
which is plotted in figure 11.3(c) from m = 3 or N = 7.
Now we can make the following observations:
(i) For a period of the maximal-length sequence, the autocorrelation function Rc( ) is somewhat similar to that of a random binary wave.
(ii) The waveforms of both sequences have the same envelope, sinc2(fT), for their o densities. The fundamental difference between them is that whereas the random binary sequence has a continuous spectral density characteristic, the corresponding characteristk of a maximal-length sequence consists of delta functions spaced 1/NTc Hz apart
As the shift-register length m, or equivalently, the period N of the maximal-length sequence is increased, the maximal-length sequence becomes increasingly similar to the random binary sequence. Indeed, in the limit, the two sequences become identical when N is made infinitely large. However, the price paid for making N large is an increasing storage requirement, which imposes a practical limit on how large N can actually be made.
11.2.2. Choosing a Maximal-Length Sequence
Now that we understand the properties of a maximal-length sequence and the fact that we can generate it using a linear feedback shift register, the key question that we need to address is : How do we find the feedback logic for a desired period N? The answer to this question is to be found in the theory of error-control codes. The task of finding the required feedback logic is made particularly easy for us by virtue of the extensive tables of the necessary feedback connections for varying shift register lengths that have been compiled in the literature. In Table 11.1, we present the sets of maximal (feedback) taps pertaining to shift-register lengths m = 2, 3, …, 8.
Table 11.1. Maxima-length sequences of shift-register lengths 2 – 8
| Shift-Register Lenght, m |
Feedback Taps |
| 2* 3* 4 5* 6 7* 8 |
[2 ,1] [3 ,1] [4 ,1] [5 ,2], [5, 4, 3, 2], [5, 4, 2, 1] [6 ,1], [6, 5, 2, 1], [6, 5, 3, 2] [7 ,1], [7, 3], [7, 3, 2, 1], [7, 4, 3, 2], [7, 6, 4, 2], [7, 6, 3, 1], [7, 6, 5, 2], [8, 4, 3, 2], [8, 6, 5, 3], [8, 6, 5, 2] [8, 5, 3, 1] [8, 6, 5, 1], [8, 7, 6, 1], [8, 7, 6, 5, 2, 1], [8, 6, 4, 3, 2, 1] |
It may be noted that as m increases, the number of alternative schemes (codes) is enlarged. Also, for every set of feedback connections shown in this table, there is an image set that generates an identical maximal-length code, reversed in time sequence.
The particular sets identified with an asterisk in table 11.1 correspond to Mersenne prime length sequences, for which the period N is a prime number.