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].
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).
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
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).
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.
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
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.
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]
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.
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
Note: There is a rating embedded within this post, please visit this post to rate it.
The following is a function to generate a Walsh Hadamard Matrix of given codeword size. The codeword size has to be a power of 2.
function [H]=generateHadamardMatrix(codeSize)
%[H]=generateHadamardMatrix(codeSize);
% Function to generate Walsh-Hadamard Matrix where "codeSize" is the code
% length of walsh code. The first matrix gives us two codes; 00, 01. The second
% matrix gives: 0000, 0101, 0011, 0110 and so on
% Author: Mathuranathan for https://www.gaussianwaves.com
% License: Creative Commons: Attribution-NonCommercial-ShareAlike 3.0
% Unported
%codeSize=64; %For testing only
N=2;
H=[0 0 ; 0 1];
if bitand(codeSize,codeSize-1)==0
while(N~=codeSize)
N=N*2;
H=repmat(H,[2,2]);
[m,n]=size(H);
%Invert the matrix located at the bottom right hand corner
for i=m/2+1:m,
for j=n/2+1:n,
H(i,j)=~H(i,j);
end
end
end
else
disp('INVALID CODE SIZE:The code size must be a power of 2');
end
Example:
To Generate Walsh Codes used in IS-95 (which utilizes 64 Walsh codes of size 64 bits each, use : [H]=generateHadamardMatrix(64). This will generate 64 Walsh Codes of length 64-bits (for each code).
Test Program:
Click Here to download
Also given below is a program to test the cross-correlation and auto-correlation of Walsh code. A set of 8-Walsh codes are used for this purpose.
% Matlab Program to test Walsh Hadamard Codes and to test their orthogonality
% Plots cross-correlation and auto correlation of Walsh Hadamard Codes
% Author: Mathuranathan Viswanathan for https://www.gaussianwaves.com
% License: Creative Commons: Attribution-NonCommercial-ShareAlike 3.0
% Unported
codeSize=8;
[H]=generateHadamardMatrix(codeSize);
%-----------------------------------------------------------
%Cross-Correlation of Walsh Code 1 with rest of Walsh Codes
h = zeros(1, codeSize-1); %For dynamic Legends
s = cell(1, codeSize-1); %For dynamic Legends
for rows=2:codeSize
[crossCorrelation,lags]=crossCorr(H(1,:),H(rows,:));
h(rows-1)=plot(lags,crossCorrelation);
s{rows-1} = sprintf('Walsh Code Sequence #-%d', rows);
hold all;
end
%Dynamic Legends
% Select the plots to include in the legend
index = 1:codeSize-1;
% Create legend for the selected plots
legend(h(index),s{index});
title('Cross Correlation of Walsh Code 1 with the rest of the Walsh Codes');
ylabel('Cross Correlation');
xlabel('Lags');
%-----------------------------------------------------------
%AutoCorrelation of Walsh Code - 1
autoCorr2(H(2,:),8,2,1);
Simulation Results
From the plots below, it can be ascertained that the Walsh codes has excellent cross-correlation property and poor autocorrelation property. Excellent cross-correlation property (zero cross-correlation) implies orthogonality, which makes it suitable for CDMA applications.
Note: There is a rating embedded within this post, please visit this post to rate it.
IS-95 CDMA Standard uses three types of codes namely 1) Long code 2) Short code and 3) Walsh Hadamard codes.
IS-95 Architecture
Long Code:
Long codes run at 1.2288 Mb/s and are 42 bits longs (created using a 42 bits LFSR register). It takes approx 41.2 days to repeat a long code at this rate. It is used for both encryption and spreading. Encryption is achieved by using a mask called Long Code mask which is a created using a 64-bit authentication key called A-key (assigned by CAVE protocol) and Electronic Serial Number ( ESN – assigned each user based on the mobile number). The Long code changes each time a new connection is created.
Short Code:
Short code is a m-sequence of lenght 215-1 (created using a 15 bit LFSR register) and is used for synchronization purpose in the forward as well as reverse links. The short code is also used to identify cell/base station connection in the forward link. It repeats approx 75 times in 2 seconds. Each base station is assigned a cyclically shifted version of same short code sequence to differentiate the base stations.This is also called PN offset in CDMA jargon. Since the cyclically shifted versions of a same m-sequence offer poor correlation, it is easier to differentiate between different base station links.
During the initial call setup stage, a mobile phone tries to find a base station (in 2 seconds max allowed time), if it find a base station, the mobile phone is validated using a database by the base station and is assigned a PN Short code sequence. This PN short code sequence uniquely identifies the connection between the particular base station and the mobile devices served under that base station.
In reality two short code sequences are used one for I channel and another for Q channel (used in spreading and de-spreading).
Walsh Hadamard Code:
CDMA used another type of code called Walsh Hadamard Code. In IS-95 CDMA, 64 Walsh codes are used per base station. This enables to create 64 separate channels per base stations (i.e. a base station can handle maximum 64 unique users at a given time).In CDMA-2000 standard, 256 Walsh codes are used to handle maximum 256 unique users under a base.
Walsh codes are created using Hadamard Matrix and transform. The codes under a family of Walsh codes, posses a beautiful property of being orthogonal to each other (what else do we want to identify/accommodate users ?).
The first matrix in a Hadamard transform is
$$ H1=\begin{bmatrix} 0 & 0\\ 0 & 1 \end{bmatrix} $$
Each row of a Hadamard matrix represent a unique Walsh code and all the Walsh codes in a given matrices are orthogonal. The length of the row of the matrix ( number of columns otherwise) is the code-length of the Walsh codes. To get a 64-Walsh code matrix we need to transform the matrices till H8 (this matrix contains 64 rows – representing 64 walsh codes and each code is of 64 bits length).
Walsh codes posses excellent cross-correlation property ( cross correlation of one Walsh code with another is always zero) therefore possess excellent orthogonality property. The auto-correlation property of Walsh code is very poor and so it is used only in synchronous CDMA networks, which maintains a synchronizing mechanism to identify the starting of the codeword.
Actually in IS-95, out of the 64 available Walsh codes, Walsh code 0 is reserved for pilot channel, 1 to 7 are assigned for synch channel and paging channels and the remaining 8-63 are assigned for users (traffic channel).
Spread spectrum system, originally developed for military applications, is extremely resistant to unauthorized detection, jamming, interference and noise. It converts a narrowband signal to wideband signal by the means of spreading. Standards like WiFi and bluetooth use spread spectrum technology such as direct sequence spread spectrum and frequency hopping spread spectrum respectively. Spread spectrum techniques rely on the use of one or other form of coding sequences like m-sequences, Gold codes, Kasami codes, etc., The study of properties of these codes is important in the design and implementation of a given spread spectrum technique. In this chapter, generation of spreading sequences and their main properties are covered, followed by simulation models for direct sequence spread spectrum and frequency hopping spread spectrum systems.
Spread spectrum
A spread-spectrum signal is a signal that occupies a bandwidth that is much larger than necessary to the extent that the occupied bandwidth is independent of the bandwidth of the input-data. With this technique, a narrowband signal such as a sequence of zeros and ones is spread across a given frequency spectrum, resulting in a broader or wideband signal. Spread spectrum was originally intended for military application and it offers two main benefits. First, a wideband signal is less susceptible to intentional blocking (jamming) and unintentional blocking (interference or noise) than a narrowband signal. Secondly, a wideband signal can be perceived as part of noise and remains undetected. The two most popular spread spectrum techniques widely used in commercial applications are direct sequence spread spectrum (DSSS) and frequency hopping spread spectrum (FHSS).
Bluetooth, cordless phones and other fixed broadband wireless access techniques use FHSS; WiFi uses DSSS. Given that both the techniques occupy the same frequency band, co-existence of bluetooth and Wifi devices is an interesting issue. Both FSSS and DSSS devices perceive each others as noise, i.e, the WiFi and Bluetooth devices see each other as mutual interferers. All the spread spectrum techniques make use of some form of spreading or code sequences.
Be it DSSS or FHSS, the key element in any spread spectrum technique is the use of code sequences. In DSSS, a narrowband signal representing the input data is XOR’ed with a code sequence of much higher bit rate, rendering a wideband signal. In FHSS, the transmitter/receiver agrees to and hops among a given set of frequency channels according to a seemingly random code sequence. The most popular code sequences used in spread spectrum applications are
These codes are mainly used in the spread spectrum for protection against intentional blocking (jamming) as well as unintentional blocking (noise or interference), to provide a provision for privacy that enables protection of signals against eavesdropping and to enable multiple users share the same resource. The design and selection of a particular code sequence for a given application largely depends on its properties. As an example, we will consider generation of m-sequences and Gold codes, along with the demonstration of their code properties.
Given the choice of numerous spreading codes like m-sequences, Gold codes, Walsh codes etc., the problem of selecting a spreading sequence for a given application reduces to the selection of such codes based on good discrete-time periodic cross-correlation and auto-correlation properties.
The cross-correlation of two discrete sequences x and y, normalized with respect to the sequence length N, is given by
Similarly, the auto-correlation of a discrete sequence refers to the degree of agreement between the given sequence and its phase shifted replica. To avoid problems due to false synchronization, it is important to select a spreading code with excellent auto-correlation properly. The periodic autocorrelation functions of m-sequences approach the ideal case of noise when the sequence length N is made very large. Hence, m-sequences are commonly employed in practice when good autocorrelation functions are required. For applications like code division multiple access (CDMA), the codes with good cross-correlation properties are desired.
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].
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. Kindly check out this article where I detailed the generation of m-sequences using Galois LFSR.
Figure 1, depicts the auto-correlation of an m-sequence of period N=31 using the 5th order characteristic polynomial g(x)=x5+x2+1. The normalized auto-correlation of an m-sequence of length N, takes two values [1,-1/N]. We observe that that auto-correlation 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 -1/N 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 1: Normalized auto-correlation of m-sequence generated using the polynomial g(x) = x5+x2+1
Figure 2, depicts the cross-correlation of two different m-sequences, consider two different primitive polynomials g1(x)=x5+x4+x2+x+1 and g2(x)=x5+x4+x3+x+1. The cross-correlation plot contains high peaks at certain lags (as high as 35%) 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.
Figure 2: Normalized cross-correlation of two m-sequences generated using the polynomials g1(x)=x5+x4+x2+x+1 and g2(x)=x5+x4+x3+x+1
Gold codes
In applications like code division multiple access (CDMA) technique and satellite navigation, a large number of codes with good cross-correlation property is a necessity. Code sequences that have bounded small cross-correlations, are useful when multiple devices are broadcasting in the same frequency range. Gold codes, named after Robert Gold, 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 pair of m-sequences. Kindly check out this article where I detailed the generation of Gold codes using preferred pair m-sequences.
Gold sequences belong to the category of product codes where two preferred pair of m-sequences of same length are XOR’ed (modulo-2 addition) to produce a Gold sequence. The two m-sequences 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.
The auto-correlation of a Gold code sequence, plotted in Figure 3 and the normalized cross-correlation of preferred pair m-sequences (used for Gold code generation) is plotted in Figure 4.
Figure 3: Auto-correlation of Gold code sequence generated using the preferred pair feedback connections [2,3,4,5] and [2,5]
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.
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
This site uses cookies responsibly. Learn more in our privacy policy.
This website uses cookies to improve your experience while you navigate through the website. Out of these, the cookies that are categorized as necessary are stored on your browser as they are essential for the working of basic functionalities of the website. We also use third-party cookies that help us analyze and understand how you use this website. These cookies will be stored in your browser only with your consent. You also have the option to opt-out of these cookies. But opting out of some of these cookies may affect your browsing experience.
Necessary cookies are absolutely essential for the website to function properly. These cookies ensure basic functionalities and security features of the website, anonymously.
Cookie
Duration
Description
cookielawinfo-checbox-analytics
11 months
This cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Analytics".
cookielawinfo-checbox-analytics
11 months
This cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Analytics".
cookielawinfo-checbox-functional
11 months
The cookie is set by GDPR cookie consent to record the user consent for the cookies in the category "Functional".
cookielawinfo-checbox-functional
11 months
The cookie is set by GDPR cookie consent to record the user consent for the cookies in the category "Functional".
cookielawinfo-checbox-others
11 months
This cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Other.
cookielawinfo-checbox-others
11 months
This cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Other.
cookielawinfo-checkbox-necessary
11 months
This cookie is set by GDPR Cookie Consent plugin. The cookies is used to store the user consent for the cookies in the category "Necessary".
cookielawinfo-checkbox-performance
11 months
This cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Performance".
viewed_cookie_policy
11 months
The cookie is set by the GDPR Cookie Consent plugin and is used to store whether or not user has consented to the use of cookies. It does not store any personal data.
Functional cookies help to perform certain functionalities like sharing the content of the website on social media platforms, collect feedbacks, and other third-party features.
Performance cookies are used to understand and analyze the key performance indexes of the website which helps in delivering a better user experience for the visitors.
Analytical cookies are used to understand how visitors interact with the website. These cookies help provide information on metrics the number of visitors, bounce rate, traffic source, etc.