Tag: m-sequences

Maximum-length sequence (m-sequence) generator

Key focus: Model and simulate m-sequence generator using Galois linear feedback shift registers (LFSR) that implement linear recursion. Plot correlation properties.

Maximum-length sequences (also called as m-sequences or pseudo random (PN) sequences) are constructed based on Galois field theory which is an extensive topic in itself. A detailed treatment on the subject of Galois field theory can be found in references [1] and [2].

This article is part of the book
● Wireless Communication Systems in Matlab (second edition), ISBN: 979-8648350779 available in ebook (PDF) format and Paperback (hardcopy) format.

Maximum length sequences are generated using linear feedback shift registers (LFSR) structures that implement linear recursion. There are two types of LFSR structures available for implementation – 1) Galois LFSR and 2) Fibonacci LFSR. The Galois LFSR structure is a high speed implementation structure, since it has less clock to clock delay path compared to its Fibonacci equivalent. What follows in this discussion is the implementation of an m-sequence generator based on Galois LFSR architecture (Figure 1).

Galois LFSR architecture
Figure 1: A basic LFSR architecture (m-sequence generator)

The basic Galois LFSR architecture for an -order generating polynomial in is given in Figure 1. The integer value denotes the number of delay elements in the LFSR architecture and represent the coefficients of the generator polynomial. The generator polynomial of the given LFSR is

where, , i.e, they take only binary values. The first and last coefficients are usually unity: .

For generating an m-sequence, the characteristic polynomial that dictates the feedback coefficients, should be a primitive polynomial. Table 1 lists some of the primitive polynomials of degree upto . More comprehensive tables of primitive polynomials can be found in reference [3].

Table 1: Primitive polynomials up to degree L=12 used in m-sequence generator

For implementation in Matlab, the LFSR structure can be coded in a straightforward manner that involves at least two for loops. If we could exploit the linear recursion property of LFSR and its equivalent matrix model, the LFSR can be implemented using only one for loop as shown in the Matlab function given in the book (click here). The function implements the LFSR structure Figure 1 by using the following equivalent matrix equation:

with the initial state of the shift registers represented by the vector , and is an dimensional vector given by

The matrix is of dimension , given by

Correlation properties of m-sequences are demonstrated here. It uses the sequence_correlation function defined in section 12.2.1 in the book (click here).

Let’s generate an m-sequence of period using the order characteristic polynomial . The coefficients of the characteristic polynomial is and let’s start the generator with initial seed . Typically, the autocorrelation function of m-sequences are two valued. The normalized autocorrelation of an m-sequence of length , takes two values . This is demonstrated in Figure 2. We observe that that autocorrelation of m-sequence carries some similarities with that of a random sequence. If the length of the m-sequence is increased, the out-of-peak correlation reduces further and thereby the peaks become more distinct. This property makes the m-sequences suitable for synchronization and in the detection of information in single-user Direct Sequence Spread Spectrum systems.

Figure 2: Normalized autocorrelation of m-sequence generated using the polynomial

To demonstrate cross-correlation properties of two different m-sequences, consider two different primitive polynomials and that could generate two different m-sequences of length . The normalized cross-correlation of the aforementioned m-sequences, shown in Figure 3, is given by the Matlab script given in the book (click here).

Figure 3: Normalized cross_correlation of two m-sequences generated using the polynomials and

The cross-correlation plot contains high peaks at certain lags (as high as ) and hence the m-sequences causes multiple access interference↗ (MAI), leading to severe performance degradation. Hence, the m-sequences are not suitable for orthogonalization of users in multi-user spread spectrum systems like CDMA.

Continue reading on generation of Gold codes using preferred pair m-sequences…

Rate this article: Note: There is a rating embedded within this post, please visit this post to rate it.

References

[1] D. V. Sarwate and M. B. Pursley, Crosscorrelation properties of pseudorandom and related sequences, Proc. IEEE, vol. 68, no. 5, pp. 593–619, May 1980.↗
[2] S. W. Golomb, Shift-register sequences and spread-spectrum communications, Proceedings of IEEE 3rd International Symposium on Spread Spectrum Techniques and Applications (ISSSTA’94), Oulu, Finland, 1994, pp. 14-15 vol.1.↗
[3] R. L. Peterson, R. E. Ziemer, and D. E. Borth, Introduction to Spread Spectrum Communications, Prentice Hall, Inc., 1995.↗

Topics in this chapter

Spread spectrum techniques
● Introduction
● Code sequences
 □ Sequence correlations
 □ Maximum-length sequences (m-sequences)
 □ Gold codes
● Direct Sequence Spread Spectrum
 □ Simulation of DSSS system
 □ Performance of Direct Sequence Spread Spectrum over AWGN channel
 □ Performance of Direct Sequence Spread spectrum in the presence of Jammer
● Frequency Hopping Spread Spectrum
 □ Simulation model
 □ Binary Frequency Shift Keying (BFSK)
 □ Allocation of frequency channels
 □ Frequency hopping generator
 □ Fast and slow frequency hopping
 □ Simulation code for BFSK-FHSS

Books by the author


Wireless Communication Systems in Matlab
Second Edition(PDF)
Note: There is a rating embedded within this post, please visit this post to rate it.
Checkout Added to cart

Digital Modulations using Python
(PDF ebook)
Note: There is a rating embedded within this post, please visit this post to rate it.
Checkout Added to cart

Digital Modulations using Matlab
(PDF ebook)
Note: There is a rating embedded within this post, please visit this post to rate it.
Checkout Added to cart
Hand-picked Best books on Communication Engineering
Best books on Signal Processing

Gold code generator using LFSRs

Focus of this article is to discuss the details of Gold code generator using preferred pair m-sequences, implemented using linear feedback shift registers (LFSR). Finally we plot and investigate correlation properties of the generated Gold codes.

Introduction

In a multi-user environment (like spread spectrum, CDMA ) large number of codes with good correlation properties, is a necessity. Gold codes are suited for this application, since a large number of codes with controlled correlation can be generated by a simple time shift of two preferred m-sequences.

Gold sequences belong to the category of  product codes where two m-sequences of same length are XOR’ed to produce a Gold sequence. The two m-sequence must maintain the same phase relationship till all the additions are performed. A slight change of phase even in one of the m-sequences, produces a different Gold sequence altogether. Gold codes are non-maximal and therefore they have poor auto-correlation property when compared to that of the underlying m-sequences.

This article is part of the book
● Wireless Communication Systems in Matlab (second edition), ISBN: 979-8648350779 available in ebook (PDF) format and Paperback (hardcopy) format.

A typical implementation of Gold code generator is shown in Figure 1. Here, the two linear feedback shift registers (LFSR), each of length , are configured to generate two different m-sequences. As we cannot start the LFSRs with all zero values, there need to be some values in the LFSRs. These initial values are controlled by ‘seed 1‘ and ‘seed 2‘. The phase of the m-sequence loaded into an LFSR can be controlled by shifting the initial seed (initial value of the shift registers in the LFSR) there by providing an option to generate a new Gold sequence.

Figure 1: Generation of Gold Code using LFSR

Note that there exists numerous choice of Gold sequences based on the m-sequence configuration of the LFSRs and what is initially loaded into the two LFSRs. Not all the Gold sequences possess good correlation properties. In order to have a Gold code sequence with three valued peak cross-correlation magnitudes, that is both bounded and uniform, the m-sequences generated by the two LFSRs need to be of preferred type.

Algebraic details on generating two preferred m-sequence for Gold code generation is detailed in Gold’s work [1]. It warrants the need for searching the preferred pairs, instead, the configurations given in Table 1 can be used for generating Gold codes that provide optimal correlation properties (three valued correlation as mentioned in Reference [2]). Following points must be noted when choosing the length of LFSR () when generating the Gold code.

● Three valued cross-correlation values occur when is odd or when .
● The peak cross-correlation magnitude achieves the minimum possible value only when is odd (). Therefore, this is the best choice here.
● When , the m-sequences listed in table are still of preferred type (three valued cross-correlation), but the lower bound is weaker when compared to the lower bound when is odd.

Table 1: Preferred pairs of m-sequences

Hardware implementation

A sample hardware implementation for generating a length 127 Gold code – using the preferred pairs ([7,3,2,1],[7,3]) is shown in Figure 2. Here each register in the LFSR is a D-flip flop,all connected in cascaded fashion and operating at a given synchronous clock. Changing the initial seed values into shift registers produces a different set of Gold codes. Matlab code for implementing a Gold code generator is available in this book.

Figure 2: Length 127 – Gold sequence generator with odd n for the preferred pairs – [7,3,2,1], [7,3]

Correlation properties

Figure 3 on this post shows the periodic cross-correlation of two m-sequences that are not a preferred pair. Let’s take a preferred pair from the Table 1 for N = 31 having the feedback connections – [2,3,4,5] and [2,5]. The correlation of two sequences can be computed using the function given in section 12.2.1 of this book.

Figure 3: Normalized cross-correlation of preferred pair m-sequences using the feedback connections [2,3,4,5] and [2,5]
Figure 4: Autocorrelation of Gold code sequence generated using the preferred pair feedback connections [2,3,4,5] and [2,5]

The normalized cross-correlation of the chosen preferred pair and the auto-correlation of the corresponding Gold code is shown in Figure 3 and Figure 4 respectively. The auto-correlation and cross-correlation plots reveal that the Gold code sequence does not possess the excellent auto-correlation property as that of individual m-sequences, but it possess good cross-correlation properties in comparison with the individual m-sequences.

Rate this article: Note: There is a rating embedded within this post, please visit this post to rate it.

References:

[1] Gold, R. (1967), Optimal binary sequences for spread spectrum  multiplexing, IEEE Transactions on Information Theory, 13 (4), pp. 619-621.↗

[2] Sarwate D.V, Pursley, M.B., “Crosscorrelation Properties of Pseudorandom and Related Sequences”, Proceedings of the IEEE, Volume 68, Issue 5, pp 593 – 619, May 1980.↗

Books by the author


Wireless Communication Systems in Matlab
Second Edition(PDF)
Note: There is a rating embedded within this post, please visit this post to rate it.
Checkout Added to cart

Digital Modulations using Python
(PDF ebook)
Note: There is a rating embedded within this post, please visit this post to rate it.
Checkout Added to cart

Digital Modulations using Matlab
(PDF ebook)
Note: There is a rating embedded within this post, please visit this post to rate it.
Checkout Added to cart
Hand-picked Best books on Communication Engineering
Best books on Signal Processing

Topics in this chapter

Spread spectrum techniques
● Introduction
● Code sequences
 □ Sequence correlations
 □ Maximum-length sequences (m-sequences)
 □ Gold codes
● Direct Sequence Spread Spectrum
 □ Simulation of DSSS system
 □ Performance of Direct Sequence Spread Spectrum over AWGN channel
 □ Performance of Direct Sequence Spread spectrum in the presence of Jammer
● Frequency Hopping Spread Spectrum
 □ Simulation model
 □ Binary Frequency Shift Keying (BFSK)
 □ Allocation of frequency channels
 □ Frequency hopping generator
 □ Fast and slow frequency hopping
 □ Simulation code for BFSK-FHSS