Mathuranathan, Author at GaussianWaves

Random Interleaver

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

Random Interleaver:

The Random Interleaver rearranges the elements of its input vector using a random permutation. The incoming data is rearranged using a series of generated permuter indices. A permuter is essentially a device that generates pseudo-random permutation of given memory addresses. The data is arranged according to the pseudo-random order of memory addresses.

The de-interleaver must know the permuter-indices exactly in the same order as that of the interleaver. The de-interleaver arranges the interleaved data back to the original state by knowing the permuter-indices.

The interleaver depth (D) (Not sure what this term means ? – check out this article – click here) is essentially the number of memory addresses taken for permutation at a time. If the number of memory addresses taken for permutation increases, the interleaver depth increases.

In the Matlab simulation that is given below, an interleaver depth of 15 is used for illustration. This means that 15 letters are taken at a time and are permuted (rearranged randomly). This process is repeated consecutively for the next block of 15 letters.

As you may observe from the simulation that increasing the interleaver depth will increase the degree of randomness in the interleaved data and will decrease the maximum burst length after the de-interleaver operation.

Matlab Code:

A sample Matlab code that simulates the above mentioned random interleaver is given below. The input data is a repeatitive stream of following symbols – “THE_QUICK_BROWN_FOX_JUMPS_OVER_THE_LAZY_DOG_“. This code simulates only the interleaving/de-interleaving part.The burst errors produced by channel are denoted by ‘*‘.

%Demonstration of PseudoRandom Interleaver/Deinterleaver
%Author : Mathuranathan for https://www.gaussianwaves.com
%License - Creative Commons - cc-by-nc-sa 3.0

clc;
clear;
%____________________________________________
%Input Parameters
%____________________________________________
D=15; %Interleaver Depth. More the value of D more is the randomness
n=5; %Number of Data blocks that you want to send.
data='THE_QUICK_BROWN_FOX_JUMPS_OVER_THE_LAZY_DOG_'; % A constant pattern used as a data
%____________________________________________
%Make the length of the data to be a multiple of D. This is for
%demonstration only.Otherwise the empty spaces has to be zero filled.
data=repmat(data,1,n); %send n blocks of specified data pattern
if mod(length(data),D) ~=0
    data=[data data(1:(D*(fix(length(data)/D+1))-length(data)))];
end

%We are sending D blocks of similar data
%intlvrInput=repmat(data(1:n),[1 D]);
%fprintf('Input Data to the Interleaver -> \n');
%disp(char(intlvrInput));
%disp('____________________________________________________________________________');

%INTERLEAVER
%Writing into the interleaver row-by-row
permuterIndex=randperm(D);
intrlvrOutput=[];
index=1;

for i=1:fix(length(data)/D)
    intrlvrOutput=[intrlvrOutput data(permuterIndex+(i-1)*D)];
end

for i=1:mod(length(data),D)
    intrlvrOutput=[intrlvrOutput data(permuterIndex(i)+fix(length(data)/D)*D)];
end

uncorruptedIntrlvrOutput=intrlvrOutput;

%Corrupting the interleaver output by inserting 10 '*'
intrlvrOutput(1,25:34)=zeros(1,10)+42;

%DEINTERLEAVER
deintrlvrOutput=[];

for i=1:fix(length(intrlvrOutput)/D)
    deintrlvrOutput(permuterIndex+(i-1)*D)=intrlvrOutput((i-1)*D+1:i*D);
end

for i=1:mod(length(intrlvrOutput),D)
    deintrlvrOutput((fix(length(intrlvrOutput)/D))*permuterIndex+i)=intrlvrOutput((i+1):(i+1)*D);
end

deintrlvrOutput=char(deintrlvrOutput);
disp('Given Data -->');
disp(data);
disp(' ')
disp('Permuter Index-->')
disp(permuterIndex);
disp(' ')
disp('PseudoRandom Interleaver Output -->');
disp(uncorruptedIntrlvrOutput);
disp(' ')
disp('Interleaver Output after being corrupted by 10 symbols of burst error - marked by ''*''->');
disp(char(intrlvrOutput));
disp(' ')
disp('PseudoRandom Deinterleaver Output -->');
disp(deintrlvrOutput);

Simulation Result:

Given Data –>
THE_QUICK_BROWN_FOX_JUMPS_OVER_THE_LAZY_DOG_THE_QUICK_BROWN_FOX
_JUMPS_OVER_THE_LAZY_DOG_THE_QUICK_BROWN_FOX_JUMPS_OVER_THE_LAZY
_DOG_THE_QUICK_BROWN_FOX_JUMPS_OVER_THE_LAZY_DOG_THE_QUICK_BROWN
_FOX_JUMPS_OVER_THE_LAZY_DOG_THE_Q

Permuter Index–>
15 1 11 9 7 12 5 6 13 4 2 10 3 8 14

PseudoRandom Interleaver Output –>
NTBKIRQUO_H_ECWR__PUO_JVXFSOMET_DYAO_LGET_HZ__HR_COUIWQEB_KN_
FOSMVJUE_O_XPRHTO_ZGLA__HDEYTFEOBKWICNU_RQ__TOV_PEUMRJXO_S_EH
GDY_AZTLEO__HO_WR_NCK_IQOUBFHXEOSRMP_U_VJ_T_E_O_TZYHA_GLDEXQN
OB_K_FCUWIROE_RV__PSTMJEUOHQ_TGDHY_EZL_AO_

Interleaver Output after being corrupted by 10 symbols of burst error – marked by ‘*‘->
NTBKIRQUO_H_ECWR__PUO_JV**********AO_LGET_HZ__HR_COUIWQEB_KN_FOS
MVJUE_O_XPRHTO_ZGLA__HDEYTFEOBKWICNU_RQ__TOV_PEUMRJXO_S_EHGDY
_AZTLEO__HO_WR_NCK_IQOUBFHXEOSRMP_U_VJ_T_E_O_TZYHA_GLDEXQNOB_K
_FCUWIROE_RV__PSTMJEUOHQ_TGDHY_EZL_AO_

PseudoRandom Deinterleaver Output –>
THE_QUICK_BROWN_***_JU*P*_OV*R*THE_LAZ*_*OG_*HE_QUICK_BROWN_FOX_
JUMPS_OVER_THE_LAZY_DOG_THE_QUICK_BROWN_FOX_JUMPS_OVER_THE_LA
ZY_DOG_THE_QUICK_BROWN_FOX_JUMPS_OVER_THE_LAZY_DOG_THE_QUICK_BR
OWN_FOX_JUMPS_OVER_THE_LAZY_DOG_THE_Q

As we can see from the above simulation that, even though the channel introduces 10 symbols of consecutive burst error, the interleaver/deinterleaver operation has effectively distributed the errors and reduced the maximum burst length to 3 symbols.

Additional Resources:

[1] Concatenation and Advanced Codes – Applications of interleavers- Stanford University

Recommended Books

Block Interleaver Design for RS codes

Introduction:

A Reed Solomon (RS) encoder, takes user data symbols and converts it into a n symbol wide codeword, by adding parity symbols. The error correcting capability of the RS code is computed as . That is, a RS code with parity symbols can correct a burst error of upto symbol errors.

Block Interleavers:

Suppose, assume that the dominant error mechanism in a channel is of burst type. A burst of length b is defined as a string of b unreliable consecutive symbols. If the expected burst length, b is less than or equal to t (the number of correctable symbol errors by RS coding), the code can be used as it is. However, if bursts length , the error correcting code will fail. This is where interleaving comes to our rescue.

Let us assume that and , where d (the interleaving depth) is an integer. The Reed-Solomon code can be used if we can spread the burst error sequence over several code blocks so that each block has no more than t errors (which can then be corrected). This can be accomplished using block interleaving as follows. Instead of encoding blocks of k symbols and then sending the encoded symbols consecutively, we can interleave the encoded blocks and transmit the interleaved data. In the case where ,the data bytes output from the Reed-Solomon encoder would appear as shown below , where bytes numbered 0 to 234 are the data bytes and bytes 235 to 254 are the parity check bytes.

Code Structure for Reed Solomon (RS) Codes

Here, the data is written row by row and read back column by column.Consider now the effect of a burst error of length , (where is the number of correctable errors per block) and for some , on the received symbols in the table. Because of the order in which the symbols are sent, a burst length less than or equal to will effect at most consecutive columns of the table, depending on where the burst starts. Notice that any single row (which corresponds to a codeword) has no more than v errors in it. If , these errors are within the error correction capability of the code and can be corrected. In this case, becomes the interleaving depth. The trade-off is that extra buffer space is required to store the interleaver table and additional delay is introduced. The worst case burst length determines the size of the table (and the interleaving depth) and the table size determines the amount of buffer space required and the delay.

Design Example:

Consider a (255,235) Reed Solomon coding system. This code can correct upto symbols errors. Lets assume that the channel that we are going to use, is expected to cause symbols. Then the interleaver depth is calculated as

In this case , an interleaver depth of 26 is enough to combat the burst errors introduced by the channel. The block interleaver dimensions would be (26 rows by 255 columns).

Matlab Code:

A sample matlab code that simulates the above mentioned block interleaver design is given below. The input data is a repeatitive stream of following symbols – “THE_QUICK_BROWN_FOX_JUMPS_OVER_THE_LAZY_DOG_“. A (255,235) Reed Solomon decoder (with correction capability of 10 symbols) is used. We assume that the channel is expected to produce a maximum of consecutive 20 symbols of burst error. The burst errors are denoted by ‘*‘.

%Demonstration of design of Block Interleaver for Reed Solomon Code
%Author : Mathuranathan for https://www.gaussianwaves.com
%License - Creative Commons - cc-by-nc-sa 3.0
clc;
clear;
%____________________________________________
%Input Parameters
%____________________________________________
%Interleaver Design for Reed-Solomon Codes
%RS code parameters
n=255;  %RS codeword length
k=235;  %Number of data symbols
b=20;  %Number of symbols that is expected to be corrupted by the channel
%____________________________________________

p=n-k;  %Number of parity symbols
t=p/2; %Error correction capability of RS code

fprintf('Given (%d,%d) Reed Solomon code can correct : %d symbols \n',n,k,fix(t));
fprintf('Given - expected burst error length from the channel : %d symbols \n',b);
disp('____________________________________________________________________________');
if(b&gt;t)
    fprintf('Interleaving  MAY help in this scenario\n');
else
    fprintf('Interleaving will NOT help in this scenario\n');
end
disp('____________________________________________________________________________');
D=ceil(b/t)+1; %Intelever Depth

memory = zeros(D,n); %constructing block interleaver memory

data='THE_QUICK_BROWN_FOX_JUMPS_OVER_THE_LAZY_DOG_'; % A constant pattern used as a data

%If n&gt;length(data) then repeat the pattern to construct a data of length 'n'
data=char([repmat(data,[1,fix(n/length(data))]),data(1:mod(n,length(data)))]);

%We sending D blocks of similar data
intlvrInput=repmat(data(1:n),[1 D]);

fprintf('Input Data to the Interleaver -&gt; \n');
disp(char(intlvrInput));
disp('____________________________________________________________________________');

%INTERLEAVER
%Writing into the interleaver row-by-row
for index=1:D
    memory(index,1:end)=intlvrInput((index-1)*n+1:index*n);
end
intlvrOutput=zeros(1,D*n);
%Reading from the interleaver column-by-column
for index=1:n
    intlvrOutput((index-1)*D+1:index*D)=memory(:,index);
end

%Create b symbols error at 25th Symbol location for test in the interleaved output
%'*' means error in this case
intlvrOutput(1,25:24+b)=zeros(1,b)+42;
fprintf('\nInterleaver Output after being corrupted by %d symbol burst error - marked by ''*''-&gt;\n',b);
disp(char(intlvrOutput));
disp('____________________________________________________________________________');

%Deinteleaver
deintlvrOutput=zeros(1,D*n);
%Writing into the deinterleaver column-by-column
for index=1:n
    memory(:,index)=intlvrOutput((index-1)*D+1:index*D)';
end

%Reading from the deinterleaver row-by-row
for index=1:D
    deintlvrOnput((index-1)*n+1:index*n)=memory(index,1:end);
end
fprintf('Deinterleaver Output-&gt;\n');
disp(char(deintlvrOnput));
disp('____________________________________________________________________________');

Simulation Result:

Given : (255,235) Reed Solomon code can correct : 10 symbols
Given : expected burst error length from the channel : 20 symbols

Interleaving MAY help in this scenario

Input Data to the Interleaver ->
THE_QUICK_BROWN_FOX_JUMPS_OVER_THE_LAZY_DOG_THE_QUICK_BROWN_FOX_JUMPS_OVER_T
HE_LAZY_DOG_THE_QUICK_BROWN_FOX_JUMPS_OVER_THE_LAZY_DOG_THE_QUICK_BROWN_FOX_
JUMPS_OVER_THE_LAZY_DOG_THE_QUICK_BROWN_FOX_JUMPS_OVER_THE_LAZY_DOG_THE_QUIC
K_BROWN_FOX_JUMPS_OVER_THE_THE_QUICK_BROWN_FOX_JUMPS_OVER_THE_LAZY_DOG_THE_
QUICK_BROWN_FOX_JUMPS_OVER_THE_LAZY_DOG_THE_QUICK_BROWN_FOX_JUMPS_OVER_THE_
LAZY_DOG_THE_QUICK_BROWN_FOX_JUMPS_OVER_THE_LAZY_DOG_THE_QUICK_BROWN_FOX_JU
MPS_OVER_THE_LAZY_DOG_THE_QUICK_BROWN_FOX_JUMPS_OVER_THE_THE_QUICK_BROWN_FOX
JUMPS_OVER_THE_LAZY_DOG_THE_QUICK_BROWN_FOX_JUMPS_OVER_THE_LAZY_DOG_THE_QUIC
K_BROWN_FOX_JUMPS_OVER_THE_LAZY_DOG_THE_QUICK_BROWN_FOX_JUMPS_OVER_THE_LAZY
DOG_THE_QUICK_BROWN_FOX_JUMPS_OVER_THE_LAZY_DOG_THE_QUICK_BROWN_FOX_JUMPS_O
VER_THE_____________________________________________________________________________

Interleaver Output after being corrupted by 20 symbols burst error – marked by ‘*‘->
TTTHHHEEE___QQQUUUIIICCC********************N___FFFOOOXXX___JJJUUUMMMPPPSSS___OOOVV
VEEERRR___TTTHHHEEE___LLLAAAZZZYYY___DDDOOOGGG___TTTHHHEEE___QQQUUUIIICCCKKK
___BBBRRROOOWWWNNN___FFFOOOXXX___JJJUUUMMMPPPSSS___OOOVVVEEERRR___TTTHHH
EEE___LLLAAAZZZYYY___DDDOOOGGG___TTTHHHEEE___QQQUUUIIICCCKKK___BBBRRROOOWWWN
NN___FFFOOOXXX___JJJUUUMMMPPPSSS___OOOVVVEEERRR___TTTHHHEEE___LLLAAAZZZYYY___
DDDOOOGGG___TTTHHHEEE___QQQUUUIIICCCKKK___BBBRRROOOWWWNNN___FFFOOOXXX___JJJ
UUUMMMPPPSSS___OOOVVVEEERRR___TTTHHHEEE___LLLAAAZZZYYY___DDDOOOGGG___TTTHHHEE
E___QQQUUUIIICCCKKK___BBBRRROOOWWWNNN___FFFOOOXXX___JJJUUUMMMPPPSSS___OOOV
VVEEERRR___TTTHHHEEE___LLLAAAZZZYYY___DDDOOOGGG___TTTHHHEEE___QQQUUUIIICCCKKK___
BBBRRROOOWWWNNN___FFFOOOXXX___JJJUUUMMMPPPSSS___OOOVVVEEERRR___TTTHHHEEE__
_____________________________________________________________________________
Deinterleaver Output->
THE_QUIC*******_FOX_JUMPS_OVER_THE_LAZY_DOG_THE_QUICK_BROWN_FOX_JUMPS_OVER_THE_
LAZY_DOG_THE_QUICK_BROWN_FOX_JUMPS_OVER_THE_LAZY_DOG_THE_QUICK_BROWN_FOX_JUM
PS_OVER_THE_LAZY_DOG_THE_QUICK_BROWN_FOX_JUMPS_OVER_THE_LAZY_DOG_THE_QUICK_BR
OWN_FOX_JUMPS_OVER_THE_THE_QUIC*******_FOX_JUMPS_OVER_THE_LAZY_DOG_THE_QUICK_BRO
WN_FOX_JUMPS_OVER_THE_LAZY_DOG_THE_QUICK_BROWN_FOX_JUMPS_OVER_THE_LAZY_DOG_TH
E_QUICK_BROWN_FOX_JUMPS_OVER_THE_LAZY_DOG_THE_QUICK_BROWN_FOX_JUMPS_OVER_THE_
LAZY_DOG_THE_QUICK_BROWN_FOX_JUMPS_OVER_THE_THE_QUIC******N_FOX_JUMPS_OVER_THE_L
AZY_DOG_THE_QUICK_BROWN_FOX_JUMPS_OVER_THE_LAZY_DOG_THE_QUICK_BROWN_FOX_JUMPS
_OVER_THE_LAZY_DOG_THE_QUICK_BROWN_FOX_JUMPS_OVER_THE_LAZY_DOG_THE_QUICK_BROWN
_FOX_JUMPS_OVER_THE_LAZY_DOG_THE_QUICK_BROWN_FOX_JUMPS_OVER_THE________________
_____________________________________________________________

As we can see from the above simulation that, eventhough the channel introduces 20 symbols of consecutive burst error (which is beyond the correction capability of the RS decoder), the interleaver/deinterleaver operation has effectively distributed the errors and reduced the maximum burst length to 7 symbols (which is easier to correct by (255,235) Reed Solomon code.

Additional Resources:

[1] Notes on theory and construction of Reed Solomon Codes – Bernard Sklar
[2] Concatenation and Advanced Codes – Applications of interleavers- Stanford University

Interleavers and deinterleavers

Note: There is a rating embedded within this post, please visit this post to rate it.
Interleavers and Deinterleavers are designed and used in the context of characteristics of the errors that might occur when the message bits are transmitted through a noisy channel. To understand the functions of an interleaver/deinterleaver, understanding of error characteristics is essential. Two types are errors concern communication system design engineer. They are burst error and random error

Random Errors:

Error locations are independent of each other. Error on one location will not affect the errors on other locations. Channels that introduce these types of errors are called channels without memory (since the channel has no knowledge of error locations since the error on location does not affect the error on another location).

Burst Errors:

Errors are depended on each other. For example, in channels with deep fading characteristics, errors often occur in bursts (affecting consecutive bits). That is, error in one location has a contagious effect on other bits. In general, these errors are considered to be dependent and such channels are considered to be channels with memory.

Interleaver/Deinterleaver :

One of the most popular ways to correct burst errors is to take a code that works well on random errors and interleave the bursts to “spread out” the errors so that they appear random to the decoder. There are two types of interleavers commonly in use today, block interleavers and convolutional interleavers.

The block interleaver is loaded row by row with L codewords, each of length n bits. These L codewords are then transmitted column by column until the interleaver is emptied. Then the interleaver is loaded again and the cycle repeats. At the receiver, the codewords are deinterleaved before they are decoded. A burst of length L bits or less will cause no more than 1 bit error in any one codeword. The random error decoder is much more likely to correct this single error than the entire burst.The parameter L is called the interleaver degree, or interleaver depth. The interleaver depth is chosen based on worst case channel conditions. It must be large enough so that the interleaved code can handle the longest error bursts expected on the channel. The main drawback of block interleavers is the delay introduced with each row-by-row fill of the interleaver.

Convolutional interleavers eliminate the problem except for the delay associated with the initial fill. Convolutional interleavers also reduce memory requirements over block interleavers by about one-half [1]. The big disadvantage of either type of interleaver is the interleaver delay introduced by this initial fill. The delay is a function of the interleaver depth and the data rate and for some channels it can be several seconds long. This long delay may be unacceptable for some applications. On voice circuits (as in GSM), for example, interleaver delays confuse the unfamiliar listener by introducing long pauses between speaker transitions. Even short delays of less than one second are sufficient to disrupt normal conversation. Another disadvantage of interleavers is that a smart jammer can choose the appropriate time to jam to cause maximum damage. This problem is overcome by randomizing the order in which the interleaver is emptied.

In practice, interleaving is one of the best burst-error correcting techniques. In theory, it is the worst way to handle burst errors. Why? From a strict probabilistic sense, we are converting “good” errors into “bad” errors. Burst errors have structure and that structure can be exploited. Interleavers “randomize” the errors and destroy the structure. Theory differs from reality,however. Interleaving may be the only technique available to handle burst errors successfully.

For example, Viterbi [2] showed that, for a channel impaired by a pulse jammer, exploiting the burst structure is not enough. Interleaving is still required. This does not mean that we should be careless about our choice of code and take up the slack with long interleavers. Codes designed to correct burst errors can achieve the same performance with much shorter interleavers. Until the coding theorists discover a better way, interleaving will be an essential error control coding technique for bursty channels.

References :

[1]B. Sklar, Digital Communications Fundamentals and Applications, Englewood Cliffs, New Jersey: Prentice Hall, 1988.
[2]A. J. Viterbi, “Spread Spectrum Communications – Myths and Realities,” IEEE Communications Magazine, vol. 17, No. 5, pp. 11-18, May 1979.

Additional Resources:

[1] Notes on theory and construction of Reed Solomon Codes – Bernard Sklar
[2] Concatenation and Advanced Codes – Applications of interleavers- Stanford University

Recommended Books

QPSK – Quadrature Phase Shift Keying

Quadrature Phase Shift Keying (QPSK) is a form of phase modulation technique, in which two information bits (combined as one symbol) are modulated at once, selecting one of the four possible carrier phase shift states.

*Figure 1: Waveform* simulation model for QPSK modulation

The QPSK signal within a symbol duration \(T_{sym}\) is defined as

\[s(t) = A \cdot cos \left[2 \pi f_c t + \theta_n \right], \quad \quad 0 \leq t \leq T_{sym},\; n=1,2,3,4 \quad \quad (1) \]

where the signal phase is given by

\[\theta_n = \left(2n – 1 \right) \frac{\pi}{4} \quad \quad (2)\]

Therefore, the four possible initial signal phases are \(\pi/4, 3 \pi/4, 5 \pi/4\) and \(7 \pi/4\) radians. Equation (1) can be re-written as

\[\begin{align} s(t) &= A \cdot cos \theta_n \cdot cos \left( 2 \pi f_c t\right) – A \cdot sin \theta_n \cdot sin \left( 2 \pi f_c t\right) \\ &= s_{ni} \phi_i(t) + s_{nq} \phi_q(t) \quad\quad \quad \quad \quad\quad \quad \quad \quad\quad \quad \quad \quad\quad \quad \quad (3) \end{align} \]

The above expression indicates the use of two orthonormal basis functions: \( \left\langle \phi_i(t),\phi_q(t)\right\rangle\) together with the inphase and quadrature signaling points: \( \left\langle s_{ni}, s_{nq}\right\rangle\). Therefore, on a two dimensional co-ordinate system with the axes set to \( \phi_i(t)\) and \(\phi_q(t)\), the QPSK signal is represented by four constellation points dictated by the vectors \(\left\langle s_{ni}, s_{nq}\right\rangle\) with \( n=1,2,3,4\).

This article is part of the following books
● Digital Modulations using Matlab : Build Simulation Models from Scratch, ISBN: 978-1521493885
● Digital Modulations using Python ISBN: 978-1712321638
All books available in ebook (PDF) and Paperback formats

The transmitter

The QPSK transmitter, shown in Figure 1, is implemented as a matlab function qpsk_mod. In this implementation, a splitter separates the odd and even bits from the generated information bits. Each stream of odd bits (quadrature arm) and even bits (in-phase arm) are converted to NRZ format in a parallel manner.

Refer Digital Modulations using Matlab : Build Simulation Models from Scratch for full Matlab code.
Refer Digital Modulations using Python for full Python code

File 1: qpsk_mod.m: QPSK modulator

function [s,t,I,Q] = qpsk_mod(a,fc,OF)
%Modulate an incoming binary stream using conventional QPSK
%a - input binary data stream (0's and 1's) to modulate
%fc - carrier frequency in Hertz
%OF - oversampling factor (multiples of fc) - at least 4 is better
%s - QPSK modulated signal with carrier
%t - time base for the carrier modulated signal
%I - baseband I channel waveform (no carrier)
%Q - baseband Q channel waveform (no carrier)
L = 2*OF;%samples in each symbol (QPSK has 2 bits in each symbol)
ak = 2*a-1; %NRZ encoding 0-> -1, 1->+1
I = ak(1:2:end);Q = ak(2:2:end);%even and odd bit streams
I=repmat(I,1,L).'; Q=repmat(Q,1,L).';%even/odd streams at 1/2Tb baud
I = I(:).'; Q = Q(:).'; %serialize
fs = OF*fc; %sampling frequency
t=0:1/fs:(length(I)-1)/fs; %time base
iChannel = I.*cos(2*pi*fc*t);qChannel = -Q.*sin(2*pi*fc*t);
s = iChannel + qChannel; %QPSK modulated baseband signal

The timing diagram for BPSK and QPSK modulation is shown in Figure 2. For BPSK modulation the symbol duration for each bit is same as bit duration, but for QPSK the symbol duration is twice the bit duration: \(T_{sym}=2T_b\). Therefore, if the QPSK symbols were transmitted at same rate as BPSK, it is clear that QPSK sends twice as much data as BPSK does. After oversampling and pulse shaping, it is intuitively clear that the signal on the I-arm and Q-arm are BPSK signals with symbol duration \(2T_b\). The signal on the in-phase arm is then multiplied by \(cos (2 \pi f_c t)\) and the signal on the quadrature arm is multiplied by \(-sin (2 \pi f_c t)\). QPSK modulated signal is obtained by adding the signal from both in-phase and quadrature arms.

Note: The oversampling rate for the simulation is chosen as \(L=2 f_s/f_c\), where \(f_c\) is the given carrier frequency and \(f_s\) is the sampling frequency satisfying Nyquist sampling theorem with respect to the carrier frequency (\(f_s \geq f_c\)). This configuration gives integral number of carrier cycles for one symbol duration.

*Figure 2: Timing diagram for BPSK and QPSK modulations*

The receiver

Due to its special relationship with BPSK, the QPSK receiver takes the simplest form as shown in Figure 3. In this implementation, the I-channel and Q-channel signals are individually demodulated in the same way as that of BPSK demodulation. After demodulation, the I-channel bits and Q-channel sequences are combined into a single sequence. The function qpsk_demod implements a QPSK demodulator as per Figure 3.

Read more about QPSK, implementation of their modulator and demodulator, performance simulation in these books:

*Figure 3: Waveform simulation model for QPSK demodulation*

Performance simulation over AWGN

The complete waveform simulation for the aforementioned QPSK modulation and demodulation is given next. The simulation involves, generating random message bits, modulating them using QPSK modulation, addition of AWGN channel noise corresponding to the given signal-to-noise ratio and demodulating the noisy signal using a coherent QPSK receiver. The waveforms at the various stages of the modulator are shown in the Figure 4.

*Figure 4: Simulated QPSK waveforms at the transmitter side*

The performance simulation for the QPSK transmitter-receiver combination was also coded in the code given above and the resulting bit-error rate performance curve will be same as that of conventional BPSK. A QPSK signal essentially combines two orthogonally modulated BPSK signals. Therefore, the resulting performance curves for QPSK – \(E_b/N_0\) Vs. bits-in-error – will be same as that of conventional BPSK.

QPSK variants

QPSK modulation has several variants, three such flavors among them are: Offset QPSK, π/4-QPSK and π/4-DQPSK.

Offset-QPSK

Offset-QPSK is essentially same as QPSK, except that the orthogonal carrier signals on the I-channel and the Q-channel are staggered (one of them is delayed in time). In OQPSK, the orthogonal components cannot change states at the same time, this is because the components change state only at the middle of the symbol periods (due to the half symbol offset in the Q-channel). This eliminates 180° phase shifts all together and the phase changes are limited to 0° or 90° every bit period.

Elimination of 180° phase shifts in OQPSK offers many advantages over QPSK. Unlike QPSK, the spectrum of OQPSK remains unchanged when band-limited [1]. Additionally, OQPSK performs better than QPSK when subjected to phase jitters [2]. Further improvements to OQPSK can be obtained if the phase transitions are avoided altogether – as evident from continuous modulation schemes like Minimum Shift Keying (MSK) technique.

π/4-QPSK and π/4-DQPSK

In π/4-QPSK, the signaling points of the modulated signals are chosen from two QPSK constellations that are just shifted π/4 radians (45°) with respect to each other. Switching between the two constellations every successive bit ensures that the phase changes are confined to odd multiples of 45°. Therefore, phase transitions of 90° and 180° are eliminated.

π/4-QPSK preserves the constant envelope property better than QPSK and OQPSK. Unlike QPSK and OQPSK schemes, π/4-QPSK can be differentially encoded, therefore enabling the use of both coherent and non-coherent demodulation techniques. Choice of non-coherent demodulation results in simpler receiver design. Differentially encoded π/4-QPSK is referred as π/4-DQPSK.

Read more about QPSK and its variants, implementation of their modulator and demodulator, performance simulation in these books:

Constellation diagram

The phase transition properties of the different variants of QPSK schemes, are easily investigated using constellation diagram. Refer this article that discusses the method to plot signal space constellations, for the various modulations used in the transmitter.

*Figure 5: Constellations plots for: (a) a = 0.3 RC-filtered QPSK, (b) α = 0.3 RC-filtered O-QPSK, (c) α = 0.3 RC-filtered π/4-DQPSK and (d) MSK*

Refer Digital Modulations using Matlab : Build Simulation Models from Scratch for full Matlab code.
Refer Digital Modulations using Python for full Python code

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

References

[1] S. A. Rhodes, “Effects of hardlimiting on bandlimited transmissions with conventional and offset QPSK modulation”, in Proc. Nat. TeIecommun. Conf., Houston, TX, 1972, PP. 20F/1-20F/7
[2] S. A. Rhodes, “Effect of noisy phase reference on coherent detection of offset QPSK signals”, IEEE Trans. Commun., vol. COM-22, PP. 1046-1055, Aug. 1974.↗

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

Digital Modulators and Demodulators - Passband Simulation Models
● Introduction
● Binary Phase Shift Keying (BPSK)
□ BPSK transmitter
□ BPSK receiver
□ End-to-end simulation
● Coherent detection of Differentially Encoded BPSK (DEBPSK)
● Differential BPSK (D-BPSK)
□ Sub-optimum receiver for DBPSK
□ Optimum noncoherent receiver for DBPSK
● Quadrature Phase Shift Keying (QPSK)
□ QPSK transmitter
□ QPSK receiver
□ Performance simulation over AWGN
● Offset QPSK (O-QPSK)
● π/p=4-DQPSK
● Continuous Phase Modulation (CPM)
□ Motivation behind CPM
□ Continuous Phase Frequency Shift Keying (CPFSK) modulation
□ Minimum Shift Keying (MSK)
● Investigating phase transition properties
● Power Spectral Density (PSD) plots
● Gaussian Minimum Shift Keying (GMSK)
□ Pre-modulation Gaussian Low Pass Filter
□ Quadrature implementation of GMSK modulator
□ GMSK spectra
□ GMSK demodulator
□ Performance
● Frequency Shift Keying (FSK)
□ Binary-FSK (BFSK)
□ Orthogonality condition for non-coherent BFSK detection
□ Orthogonality condition for coherent BFSK
□ Modulator
□ Coherent Demodulator
□ Non-coherent Demodulator
□ Performance simulation
□ Power spectral density

Spread Spectrum Communications – Introduction

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.

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.

Code sequences for spread spectrum

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

● Maximum-length sequences (m-sequences)
● Gold codes
● Walsh-Hadamard sequences
● Kasami sequences
● Orthogonal codes
● Variable length orthogonal codes

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.

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.

Sequence correlations

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.

Check the book Wireless communication systems in Matlab for Matlab code on computing the sequence correlation between two arbitrary sequences.

Maximum-length sequences (m-sequences)

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.

Check the book Wireless communication systems in Matlab for Matlab code on generating m-sequences and computing their sequence correlation properties.

Figure 1, depicts the auto-correlation of an m-sequence of period N=31 using the 5^th order characteristic polynomial g(x)=x⁵+x²+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) = x⁵+x²+1*

Figure 2, depicts the cross-correlation of two different m-sequences, consider two different primitive polynomials g₁(x)=x_⁵+x⁴+x²+x+1 and g₂(x)=x⁵+x⁴+x³+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.

Check the book Wireless communication systems in Matlab for Matlab code on generating m-sequences and computing their sequence correlation properties.

*Figure 2: Normalized cross-correlation of two m-sequences generated using the polynomials g₁(x)=x_⁵+x⁴+x²+x+1 and g₂(x)=x⁵+x⁴+x³+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]*

*Figure 4: Normalized cross-correlation of preferred pair m-sequences using the feedback connections [2,3,4,5] and [2,5]*

Check the book Wireless communication systems in Matlab for Matlab code on generating preferred pair m-sequences, Gold code sequences and computing their sequence correlation properties.

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] 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.↗

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

Viterbi Decoding of Convolutional codes

Note: There is a rating embedded within this post, please visit this post to rate it.
Viterbi algorithm is utilized to decode the convolutional codes. Again the decoding can be done in two approaches. One approach is called hard decision decoding which uses Hamming distance as a metric to perform the decoding operation, whereas, the soft decision decoding uses Euclidean distance as a metric.

As stated in one of the previous posts the soft decision decoding improves the performance of the code to a significant extent compared to the hard decision decoding.

Viterbi Algorithm (VA) decoding involves three stages, namely,

1) Branch Metric Calculation
2) Path Metric Calculation
3) Trace back operation

Branch Metric Calculation :

The pair of received bits (for (n=2) , if (n=3) then we call it triplets, etc.,) are compared with the corresponding branches in the trellis and the distance metrics are calculated. For hard decision decoding, Hamming distances are calculated. Suppose if the received pair of bits are ’11’ and the hamming distance to {’00’,’01’,’10’,’11’} outputs of the trellis are 2,1,1,0 respectively.

For soft decision decoding, see previous article

Path Metric Calculation:

Path metrics are calculated using a procedure called ACS (Add-Compare-Select). This procedure is repeated for every encoder state.

1. Add – for a given state, we know two states on the previous step which can move to this state, and the output bit pairs that correspond to these transitions. To calculate new path metrics, we add the previous path metrics with the corresponding branch metrics.

2. Compare, select – we now have two paths, ending in a given state. One of them (with greater metric) is dropped.

Trace back Operation :

Track back operation is needed in hardware that generally has memory limitations and if the transmitted message is of greater length compared to the memory available. It is also required to maintain a constant throughput at the output of the decoder.

Using soft decision decoding is recommended for Viterbi decoders, since it can give a gain of about 2 dB (that is, a system with a soft decision decoder can use 2 dB less transmitting power than a system with a hard decision decoder with the same error probability).

Two Level Coding System:

Convolution codes with Viterbi decoding are not good at burst error correction, but they are good at random error correction.On the contrary, the Reed Solomon coding is good at burst error correction and not so good at random error correction. So the advantages of these two codes are exploited in many systems to provide good error correction capability against both random and burst errors.

In such systems, data are encoded firstly with a Reed-Solomon code, then they are processed by an interleaver (which places symbols from the same Reed-Solomon codeword far from each other), and then encoded with a convolutional code.

At the receiver, data are firstly processed by a Viterbi decoder. The bursts of errors from its output are then deinterleaved (with erroneous symbols from one burst getting into different Reed-Solomon codewords) and decoded with a Reed-Solomon decoder.

Additional Resources:

[1] A graphical illustration of “How Viterbi Decoding works”

Recommended Books

Performance comparison of Digital Modulation techniques

Key focus: Compare Performance and spectral efficiency of bandwidth-efficient digital modulation techniques (BPSK,QPSK and QAM) on their theoretical BER over AWGN.

More detailed analysis of Shannon’s theorem and Channel capacity is available in the following book
● Wireless Communication Systems in Matlab (second edition), ISBN: 979-8648350779 available in ebook (PDF) format and Paperback (hardcopy) format.

Simulation of various digital modulation techniques are available in these books
● Digital Modulations using Matlab : Build Simulation Models from Scratch, ISBN: 978-1521493885
● Digital Modulations using Python ISBN: 978-1712321638

Let’s take up some bandwidth-efficient linear digital modulation techniques (BPSK,QPSK and QAM) and compare its performance based on their theoretical BER over AWGN. (Readers are encouraged to read previous article on Shannon’s theorem and channel capacity).

Table 1 summarizes the theoretical BER (given SNR per bit ration – E_b/N₀) for various linear modulations. Note that the E_b/N₀ values used in that table are in linear scale [to convert E_b/N₀ in dB to linear scale – use E_b/N₀(linear) = 10^(E_b/N₀(dB)/10) ]. A small script written in Matlab (given below) gives the following output.

*Figure 1: Eb/N0 Vs. BER for various digital modulations over AWGN channel*

*Table 1: Theoretical BER over AWGN for various linear digital modulation techniques*

The following table is obtained by extracting the values of Eb/N0 to achieve BER=10^-6 from Figure-1. (Table data sorted with increasing values of E_b/N₀).

*Table 2: Capacity of various modulations their efficiency and channel bandwidth*

where,

is the bandwidth efficiency for linear modulation with M point constellation, meaning that η_Bbits can be stuffed in one symbol with R_b bits/sec data rate for a given minimum bandwidth.

is the minimum bandwidth needed for information rate of R_b bits/second. If a pulse shaping technique like raised cosine pulse [with roll off factor (a)] is used then B_min becomes

Next the data in table 2 is plotted with E_b/N₀ on the x-axis and η on the y-axis (see figure 2) along with the well known Shannon’s Capacity equation over AWGN given by,

which can be represented as (refer [1])

*Figure 2: Spectral efficiency vs Eb/N0 for various modulations at P_b=10^-6*

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

Matlab Code

EbN0dB=-4:1:24;
EbN0lin=10.^(EbN0dB/10);
colors={'b-*','g-o','r-h','c-s','m-d','y-*','k-p','b--&gt;','g:&lt;','r-.d'};
index=1;

%BPSK
BPSK = 0.5*erfc(sqrt(EbN0lin));
plotHandle=plot(EbN0dB,log10(BPSK),char(colors(index)));
set(plotHandle,'LineWidth',1.5);
hold on;

index=index+1;

%M-PSK
m=2:1:5;
M=2.^m;
for i=M,
    k=log2(i);
    berErr = 1/k*erfc(sqrt(EbN0lin*k)*sin(pi/i));
    plotHandle=plot(EbN0dB,log10(berErr),char(colors(index)));
    set(plotHandle,'LineWidth',1.5);
    index=index+1;
end

%Binary DPSK
Pb = 0.5*exp(-EbN0lin);
plotHandle = plot(EbN0dB,log10(Pb),char(colors(index)));
set(plotHandle,'LineWidth',1.5);
index=index+1;

%Differential QPSK
a=sqrt(2*EbN0lin*(1-sqrt(1/2)));
b=sqrt(2*EbN0lin*(1+sqrt(1/2)));
Pb = marcumq(a,b,1)-1/2.*besseli(0,a.*b).*exp(-1/2*(a.^2+b.^2));
plotHandle = plot(EbN0dB,log10(Pb),char(colors(index)));
set(plotHandle,'LineWidth',1.5);
index=index+1;

%M-QAM
m=2:2:6;
M=2.^m;

for i=M,
    k=log2(i);
    berErr = 2/k*(1-1/sqrt(i))*erfc(sqrt(3*EbN0lin*k/(2*(i-1))));
    plotHandle=plot(EbN0dB,log10(berErr),char(colors(index)));
    set(plotHandle,'LineWidth',1.5);
    index=index+1;
end

legend('BPSK','QPSK','8-PSK','16-PSK','32-PSK','D-BPSK','D-QPSK','4-QAM','16-QAM','64-QAM');
axis([-4 24 -8 0]);
set(gca,'XTick',-4:2:24); %re-name axis accordingly
ylabel('Probability of BER Error - log10(Pb)');
xlabel('Eb/N0 (dB)');
title('Probability of BER Error log10(Pb) Vs Eb/N0');
grid on;

Reference

[1] “Digital Communications” by John G.Proakis ,Chapter 7: Channel Capacity and Coding.↗

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

BPSK – Binary Phase Shift Keying

Key focus: BPSK, Binary Phase Shift Keying, bpsk modulation, bpsk demodulation, BPSK matlab, BPSK python implementation, BPSK constellation

BPSK – introduction

BPSK stands for Binary Phase Shift Keying. It is a type of modulation used in digital communication systems to transmit binary data over a communication channel.

In BPSK, the carrier signal is modulated by changing its phase by 180 degrees for each binary symbol. Specifically, a binary 0 is represented by a phase shift of 180 degrees, while a binary 1 is represented by no phase shift.

BPSK is a straightforward and effective modulation method and is frequently utilized in applications where the communication channel is susceptible to noise and interference. It is also utilized in different wireless communication systems like Wi-Fi, Bluetooth, and satellite communication.

Implementation details

Binary Phase Shift Keying (BPSK) is a two phase modulation scheme, where the 0’s and 1’s in a binary message are represented by two different phase states in the carrier signal: \(\theta=0^{\circ}\) for binary 1 and \(\theta=180^{\circ}\) for binary 0.

In digital modulation techniques, a set of basis functions are chosen for a particular modulation scheme. Generally, the basis functions are orthogonal to each other. Basis functions can be derived using Gram Schmidt orthogonalization procedure [1]. Once the basis functions are chosen, any vector in the signal space can be represented as a linear combination of them. In BPSK, only one sinusoid is taken as the basis function. Modulation is achieved by varying the phase of the sinusoid depending on the message bits. Therefore, within a bit duration \(T_b\), the two different phase states of the carrier signal are represented as,

\begin{align*} s_1(t) &= A_c\; cos\left(2 \pi f_c t \right), & 0 \leq t \leq T_b \quad \text{for binary 1}\\ s_0(t) &= A_c\; cos\left(2 \pi f_c t + \pi \right), & 0 \leq t \leq T_b \quad \text{for binary 0} \end{align*}

where, \(A_c\) is the amplitude of the sinusoidal signal, \(f_c\) is the carrier frequency \(Hz\), \(t\) being the instantaneous time in seconds, \(T_b\) is the bit period in seconds. The signal \(s_0(t)\) stands for the carrier signal when information bit \(a_k=0\) was transmitted and the signal \(s_1(t)\) denotes the carrier signal when information bit \(a_k=1\) was transmitted.

The constellation diagram for BPSK (Figure 3 below) will show two constellation points, lying entirely on the x axis (inphase). It has no projection on the y axis (quadrature). This means that the BPSK modulated signal will have an in-phase component but no quadrature component. This is because it has only one basis function. It can be noted that the carrier phases are \(180^{\circ}\) apart and it has constant envelope. The carrier’s phase contains all the information that is being transmitted.

BPSK transmitter

A BPSK transmitter, shown in Figure 1, is implemented by coding the message bits using NRZ coding (\(1\) represented by positive voltage and \(0\) represented by negative voltage) and multiplying the output by a reference oscillator running at carrier frequency \(f_c\).

The following function (bpsk_mod) implements a baseband BPSK transmitter according to Figure 1. The output of the function is in baseband and it can optionally be multiplied with the carrier frequency outside the function. In order to get nice continuous curves, the oversampling factor (\(L\)) in the simulation should be appropriately chosen. If a carrier signal is used, it is convenient to choose the oversampling factor as the ratio of sampling frequency (\(f_s\)) and the carrier frequency (\(f_c\)). The chosen sampling frequency must satisfy the Nyquist sampling theorem with respect to carrier frequency. For baseband waveform simulation, the oversampling factor can simply be chosen as the ratio of bit period (\(T_b\)) to the chosen sampling period (\(T_s\)), where the sampling period is sufficiently smaller than the bit period.

Refer Digital Modulations using Matlab : Build Simulation Models from Scratch for full Matlab code.
Refer Digital Modulations using Python for full Python code

File 1: bpsk_mod.m: Baseband BPSK modulator

function [s_bb,t] = bpsk_mod(ak,L)
%Function to modulate an incoming binary stream using BPSK(baseband)
%ak - input binary data stream (0's and 1's) to modulate
%L - oversampling factor (Tb/Ts)
%s_bb - BPSK modulated signal(baseband)
%t - generated time base for the modulated signal
N = length(ak); %number of symbols
a = 2*ak-1; %BPSK modulation
ai=repmat(a,1,L).'; %bit stream at Tb baud with rect pulse shape
ai = ai(:).';%serialize
t=0:N*L-1; %time base
s_bb = ai;%BPSK modulated baseband signal

BPSK receiver

A correlation type coherent detector, shown in Figure 2, is used for receiver implementation. In coherent detection technique, the knowledge of the carrier frequency and phase must be known to the receiver. This can be achieved by using a Costas loop or a Phase Lock Loop (PLL) at the receiver. For simulation purposes, we simply assume that the carrier phase recovery was done and therefore we directly use the generated reference frequency at the receiver – \(cos( 2 \pi f_c t)\).

*Figure 2: Coherent detection of BPSK (correlation type)*

In the coherent receiver, the received signal is multiplied by a reference frequency signal from the carrier recovery blocks like PLL or Costas loop. Here, it is assumed that the PLL/Costas loop is present and the output is completely synchronized. The multiplied output is integrated over one bit period using an integrator. A threshold detector makes a decision on each integrated bit based on a threshold. Since, NRZ signaling format was used in the transmitter, the threshold for the detector would be set to \(0\). The function bpsk_demod, implements a baseband BPSK receiver according to Figure 2. To use this function in waveform simulation, first, the received waveform has to be downconverted to baseband, and then the function may be called.

Refer Digital Modulations using Matlab : Build Simulation Models from Scratch for full Matlab code.
Refer Digital Modulations using Python for full Python code

File 2: bpsk_demod.m: Baseband BPSK detection (correlation receiver)

function [ak_cap] = bpsk_demod(r_bb,L)
%Function to demodulate an BPSK(baseband) signal
%r_bb - received signal at the receiver front end (baseband)
%N - number of symbols transmitted
%L - oversampling factor (Tsym/Ts)
%ak_cap - detected binary stream
x=real(r_bb); %I arm
x = conv(x,ones(1,L));%integrate for L (Tb) duration
x = x(L:L:end);%I arm - sample at every L
ak_cap = (x > 0).'; %threshold detector

End-to-end simulation

The complete waveform simulation for the end-to-end transmission of information using BPSK modulation is given next. The simulation involves: generating random message bits, modulating them using BPSK modulation, addition of AWGN noise according to the chosen signal-to-noise ratio and demodulating the noisy signal using a coherent receiver. The topic of adding AWGN noise according to the chosen signal-to-noise ratio is discussed in section 4.1 in chapter 4. The resulting waveform plots are shown in the Figure 2.3. The performance simulation for the BPSK transmitter/receiver combination is also coded in the program shown next (see chapter 4 for more details on theoretical error rates).

The resulting performance curves will be same as the ones obtained using the complex baseband equivalent simulation technique in Figure 4.4 of chapter 4.

Refer Digital Modulations using Matlab : Build Simulation Models from Scratch for full Matlab code.
Refer Digital Modulations using Python for full Python code

File 3: bpsk_wfm_sim.m: Waveform simulation for BPSK modulation and demodulation

*Figure 3: (a) Baseband BPSK signal,(b) transmitted BPSK signal – with carrier, (c) constellation at transmitter and (d) received signal with AWGN noise*

References:

[1] Lloyd N. Trefethen, David Bau III , Numerical linear algebra, Philadelphia: Society for Industrial and Applied Mathematics, ISBN 978-0-89871-361-9, pp.56

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

Understanding Gibbs Phenomenon in signal processing

Introduction

Gibbs phenomenon is a phenomenon that occurs in signal processing and Fourier analysis when approximating a discontinuous function using a series of Fourier coefficients. Specifically, it is the observation that the overshoots near the discontinuities of the approximated function do not decrease with increasing numbers of Fourier coefficients used in the approximation.

In other words, when a discontinuous function is approximated by its Fourier series, the resulting series will exhibit oscillations near the discontinuities that do not diminish as more terms are added to the series. This can lead to a “ringing” effect in the signal, where there are spurious oscillations near the discontinuity that can persist even when the number of Fourier coefficients used in the approximation is increased.

The Gibbs phenomenon is named after American physicist Josiah Willard Gibbs, who first described it in 1899. It is a fundamental limitation of the Fourier series approximation and can occur in many other areas of signal processing and analysis as well.

Gibbs phenomenon

Fourier transform represents signals in frequency domain as summation of unique combination of sinusoidal waves. Fourier transforms of various signals are shown in the Figure 1. Some of these signals, square wave and impulse, have abrupt discontinuities (sudden changes) in time domain. They also have infinite frequency content in the frequency domain.

*Figure 1: Frequency response of various test signals*

Therefore, abrupt discontinuities in the signals require infinite frequency content in frequency domain. As we know, in order to represent these signals in computer memory, we cannot dispense infinite memory (or infinite bandwidth when capturing/measurement) to hold those infinite frequency terms. Somewhere, the number of frequency terms has to be truncated. This truncation in frequency domain manifests are ringing artifacts in time domain and vice-versa. This is called Gibbs phenomenon.

*Figure 2: Ringing artifact (Gibbs phenomenon) on a square wave when the number of frequency terms is truncated*

These ringing artifacts result from trying to describe the given signal with less number of frequency terms than the ideal. In practical applications, the ringing artifacts can result from

● Truncation of frequency terms – For example, to represent a perfect square wave, an infinite number of frequency terms are required. Since we cannot have an instrument with infinite bandwidth, the measurement truncates the number of frequency terms, resulting in the ringing artifact.

● Shape of filters – The ringing artifacts resulting from filtering operation is related to the sharp transitions present in the shape of the filter impulse response.

FIR filters and Gibbs phenomenon

Owing to their many favorable properties, digital Finite Impulse Response (FIR) filters are extremely popular in many signal processing applications. FIR filters can be designed to exhibit linear phase response in passband, so that the filter does not cause delay distortion (or dispersion) where different frequency components undergo different delays.

The simplest FIR design technique is the Impulse Response Truncation, where an ideal impulse response of infinite duration is truncated to finite length and the samples are delayed to make it causal. This method comes with an undesirable effect due to Gibbs Phenomenon.

Ideal brick wall characteristics in frequency domain is desired for most of the filters. For example, a typical ideal low pass filter necessitates sharp transition between passband and stopband. Any discontinuity (abrupt transitions) in one domain requires infinite number of components in the other domain.

For example, a rectangular function with abrupt transition in frequency domain translates to a \(sinc(x)=sin(x)/x\) function of infinite duration in time domain. In practical filter design, the FIR filters are of finite length. Therefore, it is not possible to represent an ideal filter with abrupt discontinuities using finite number of taps and hence the \(sinc\) function in time domain should be truncated appropriately. This truncation of an infinite duration signal in time domain leads to a phenomenon called Gibbs phenomenon in frequency domain. Since some of the samples in time domain (equivalently harmonics in frequency domain) are not used in the reconstruction, it leads to oscillations and ringing effect in the other domain. This effect is called Gibbs phenomenon.

Similar effect can also be observed in the time domain if truncation is done in the frequency domain.

This effect due to abrupt discontinuities will exists no matter how large the number of samples is made. The situation can be improved by using a smoothly tapering windows like Blackman, Hamming , Hanning , Keiser windows etc.,

Demonstration of Gibbs Phenomenon using Matlab:

In this demonstration, a sinc pulse in time domain is considered. Sinc pulse with infinite duration in time domain, manifests as perfect rectangular shape in frequency domain. In this demo, we truncate the sinc pulse in the time domain at various length and use FFT (Fast Fourier Transform) to visualize it frequency domain. As the duration of time domain samples increases, the ringing artifact become less pronounced and the shape approaches ideal brick wall filter response.

%Gibbs Phenomenon
clearvars; % clear all stored variables

Nsyms = 5:10:60; %filter spans in symbol duration

Tsym=1; %Symbol duration
L=16; %oversampling rate, each symbol contains L samples
Fs=L/Tsym; %sampling frequency

for Nsym=Nsyms,
    [p,t]=sincFunction(L,Nsym); %Sinc Pulse

    subplot(1,2,1);
    plot(t*Tsym,p,'LineWidth',1.5);axis tight;
    ylim([-0.3,1.1]);
    title('Sinc pulse');xlabel('Time (s)');ylabel('Amplitude');
    
    [fftVals,freqVals]=freqDomainView(p,Fs,'double'); %See Chapter 1
    subplot(1,2,2);
    plot(freqVals,abs(fftVals)/abs(fftVals(length(fftVals)/2+1)),'LineWidth',1.5);
    xlim([-2 2]); ylim([0,1.1]);
    title('Frequency response of Sinc (FFT)');
    xlabel('Normalized Frequency (Hz)');ylabel('Magnitude');
    pause;% wait for user input to continue
end

Simulation Results:

*Figure 3: Sinc pulse constructed with Nsym = 5 (filter span in symbols) and L =16 (samples/symbol)*

*Figure 4: Sinc pulse constructed with Nsym = 15 (filter span in symbols) and L =16 (samples/symbol)*

*Figure 5: Sinc pulse constructed with Nsym = 35 (filter span in symbols) and L =16 (samples/symbol)*

I have also discussed with examples, Gibbs phenomenon applied to truncation of Fourier series coefficients. You can read about it here.

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

Young’s model for Rayleigh fading

Introduction

Young’s fading channel model is a mathematical model used to describe the behavior of a wireless communication channel. It is a type of frequency selective fading channel model that is commonly used to simulate the effects of multipath interference on wireless signals.

The model is based on the assumption that the transmitted signal reaches the receiver through multiple paths, each with a different attenuation and phase shift. The attenuation and phase shift of each path are modeled as independent random variables with specific probability distributions.

The model uses the sum of these attenuated and phase-shifted paths to simulate the received signal. The resulting signal experiences fading due to the constructive and destructive interference of the individual paths.

Young’s fading channel model is useful for simulating the performance of wireless communication systems in a multipath environment. It can help researchers and engineers evaluate the performance of different modulation and coding schemes and develop techniques to mitigate the effects of fading.

Young’s model

In the previous article, the characteristics and types of fading was discussed. Rayleigh Fading channel with Doppler shift is considered in this article.

Consider a channel affected by both Rayleigh Fading phenomena and Doppler Shift. Rayleigh Fading is caused due to multipath reflections of the received signal before it reaches the receiver and the Doppler Shift is caused due to the difference in the relative velocity/motion between the transmitter and the receiver. This scenario is encountered in day to day mobile communications.

A number of simulation algorithms are proposed for generation of correlated Rayleigh random variables. David J.Young and Norman C Beaulieu proposed a method in their paper titled “The Generation of Correlated Rayleigh Random Variates by Inverse Discrete Fourier Transform”[1] based on the inverse discrete Fourier transform (IDFT). It is a modification of the Smith’s algorithm which is normally used for Rayleigh fading simulation. This method requires exactly one-half the number of IDFT operations and roughly two-thirds the computer memory of the original method – as the authors of the paper claims.

Rayleigh Fading can be simulated by adding two Gaussian Random variables as mentioned in my previous post. The effect of Doppler shift is incorporated by modeling the Doppler effect as a frequency domain filter.

The model proposed by Young et.al is shown below.

The Fading effect + Doppler Shift is simulated by multiplying the Gaussian Random variables and the Doppler Shift’s Frequency domain representation. Then IDFT is performed to bring them into time domain representation. The Doppler Filter used to represent the Doppler Shift effect is derived in Young’s paper.

The equation for the Doppler Filter is :

Matlab Code

Check this book for full Matlab code.
Simulation of Digital Communication Systems Using Matlab – by Mathuranathan Viswanathan

Matlab code Output:

Reference:

[1] D.J. Young and N.C. Beaulieu, “The generation of correlated Rayleigh random variates by inverse discrete fourier transform,” IEEE transactions on Communications, vol. 48, pp. 1114-1127, July 2000.

External Resources

[1]Theoretical expressions for BER under various conditions
[2]Capacity of MRC on correlated Rician Fading Channels

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.

Random Interleaver:

Matlab Code:

Simulation Result:

See also:

Additional Resources:

Recommended Books

Introduction:

Block Interleavers:

Design Example:

Matlab Code:

Simulation Result:

See also:

Additional Resources:

Random Errors:

Burst Errors:

Interleaver/Deinterleaver :

References :

See also:

Additional Resources:

Recommended Books

The transmitter

The receiver

Performance simulation over AWGN

QPSK variants

Offset-QPSK

π/4-QPSK and π/4-DQPSK

Constellation diagram

References

Books by the author

Topics in this chapter

Spread spectrum

Code sequences for spread spectrum

Sequence correlations

Maximum-length sequences (m-sequences)

Gold codes

References

Books by the author

Topics in this chapter

Branch Metric Calculation :

Path Metric Calculation:

Trace back Operation :

Two Level Coding System:

Additional Resources:

Recommended Books

Matlab Code

Reference

Related topics

Books by the author

BPSK – introduction

Implementation details

BPSK transmitter

BPSK receiver

End-to-end simulation

References:

Books by the author

Topics in this chapter

Introduction

Gibbs phenomenon

FIR filters and Gibbs phenomenon

Demonstration of Gibbs Phenomenon using Matlab:

Simulation Results:

Similar articles

Books by the author

Introduction

Young’s model

Matlab Code

Matlab code Output:

Reference:

See also

External Resources