Abstract
The basic principle of Orthogonal Frequency Division Multiplexing (OFDM) is present in books from many years, but this technique is studied and being researched intensively now a days. The main reason behind its importance is that, it is playing very important role in new technologies like 4G Mobile Technology. So idea is to understand some basic processes that are put together to form a Complete OFDM system.
In this paper, the main focus will be on some important concepts that are used in OFDM transmitter and Receiver. But investigation will begin from a basic level like what basically OFDM is? And what are the features that make it important? Then main focus will be laid upon the processes that make an OFDM transmitter and receiver. For example how channel coding is done on transmitter side, and how interleaving and Mapping is done. Similarly for receiver, focus will on things like Channel Decoding, deinterleaving and demapping etc. And of course FFT/IFFT will also be taken in to consideration. So we may be able to understand how an OFDM transmitter and Receiver work. This will help us to really understand its (OFDM's) role in modern technologies.
Keyword: OFDM, FFT, IFFT, 4G
INTRODUCTION
Frequency division multiplexing (FDM) uses the concept of multiple subcarriers to send data over the same channel.Each subcarrier has its own frequency which is then modulated by data. In FDM there is guard band between the adjacent subcarriers to avoid interference from adjacent subcarriers. This is not the efficient utilization of bandwidth. It is actually possible to use the set of subcarriers that are orthogonal to each other. If we do so the guard band that is essential in ordinary FDM system will no longer be essential. The use of orthogonal subcarriers will even allow the subcarrier to overlap. So we can achieve a high level of spectral efficiency. It is still possible to retrieve the individual subcarrier's signal despite of overlapping, but orthogonality must be maintained. The use of orthogonal subcarrier is the concept that separates OFDM from FDM.
http://www.wifi-doc.com/O.Reilly-802.11.Wireless.Netwo/0596100523/images/0596100523/figs/wireless802dot112_1302.gif;431830
Figure : OFDM vs. FDM [1]
OFDM Transmitter:
The OFDM transmitter uses a serial to parallel converter and output of this serial to parallel converter is then fed to the modulators which are parallel and orthogonal to each other. There are some important things to be considered while converting the data from serial to parallel form. We use a holding register to hold 'n' and are held there for 'n' symbol period. The duration of OFDM symbol is then increased by factor 'nxTb' (where Tb is duration of 'n' sequential bits) [4].To mantain the orthogonality between the subcarriers the frequencies must be separated by factor [4],
… [4]
So now we can imagine that we will be receiving 'n' narrowband FDM signals, instead of single wideband signal [4]. There is another important concept to be investigated i.e. "Multipath effect".
Multipath occurs when signals arrives at receiver from many different paths. For example if a signal got reflected from ground or building or tress or mountain or from any other surface we will be receiving many copies of transmitted signal. This reflection depends upon the reflection and reflective index of the material from which signal is being reflected. The strength of this reflected signal as compared to the original signal is important [4]. Sometimes the path delay of signals from different paths is short enough for the channel's response to be constant. This gives rise to the flat fading. Rayleigh fading occurs when there are many propagation paths. If the path delays are long enough, then the channel's frequency response should change rapidly. This is called frequency selective fading and in this case the original signal will face some serious distortions. The flat fading can be combated by increasing the power of transmitter but we cannot combat the frequency selective fading by doing so. To mitigate this multipath effect we use convolution encoder and decoder at transmitter and receiver side respectively.
Convolution Encoder:
Convolution encoder can have following key parameters,
y= Shows number of o/p bits
Normally Ranges from 1-8
x=Shows number of i/p bits
Normally ranges from 1-8
N=shows no. of memory registers
Code rate=x/y i.e. if we have 1 input bits,then for encoder of rate ½ we will have 02 output bits.
Constraint Length, L=x(N-1)
'L' shows the no. of the bits in memory register that will play their part in generation of output bits 'y' [5].
Structure of Convolution Codes:
Another important thing to be considered is that, how to determine which bit contributes in generation of output. This is called generator polynomial 'g'. list of good generator polynomial is as under,
Constraint length
Incoming bit position
The unshaded register holds the incoming bit. This means that 2 bits or 4 possible combinations can be present in memory register. These 4 different combinations determine what output we will get
The number of combinations of bits in shaded register are called the states of the code and are given by
'Number of states =2^L, Where L=constraint length=k (m-1)
Now assume that initially encoder has all 0 bits, if 1 comes as input bit then,
Present state=00
Next state =10
Output= 101
Now we are at state 10 and if 0 comes as input bit then;
Present State =10
Next state=01
Output=110
Similarly for present state 10 if 1 comes as input bit then,
Present state=10
Next state=11
Output=011
Similarly for every incoming bit we can jump to next state and we can also compute all the output bits. In this way we can make a look up table of state transitions and output bits relative to incoming bit for encoder of any parameters. Important thing here is that, at every present we can have 02 possible inputs 0 and 1. So for every encoder the state transitions and number of output bits are different depending upon generator polynomials 'g' and other parameter described above.
To have a good understanding of how an encoder operates, we normally uses different techniques.
Tree diagrams
State diagrams
Trellis diagrams
State Diagram:
Figure : (2, 1, 4) Encoder State Diagram [5]http://www.complextoreal.com/convo_files/image026.gif
This diagram shows that we have 8 possible states which mean the constraint length is 3. 3 bit value in circle shows the possible state and value present besides the arrows shows the output of encoder. The solid arrows show that we have 0 as an incoming bit and dotted line shows that we have 1 as incoming bit.
Let's assume that we are present at stat 101. If 1 comes as incoming bit we will move to state 110 and output of encoder will be 11. At the same state if 0 comes as incoming bit we will move to 010 and output will be 00. So in this ways we can visualize how the states of a particular encoder changes and how outputs are generated. Again note that, at every possible state we can have 02 inputs 0 or 1 depending on which states changes.
TREE Diagrams:
Tree diagram is also an approach to understand the functionality of convolution encoder. Here again we have 02 possible incoming bits at every state. If 1 comes as an incoming bit we move towards the upper portion of the diagram and if 0 comes as incoming bit we move towards down portion.http://www.wirelesstrainingsolutions.com/class/file.php/1/Images/OFDM_Part_3/Tx_Decision_Tree_640.png
Referring to diagram we have 4 bits '1011' to be encoded. Initially we are at state 00. Depending upon the look up table for this particular encoder we have the information that from a particular state where we have to go if 1 comes as input bit and where we have to go if 0 comes. When 1 comes we move to next state which obviously will be plotted in down portion of the diagram based upon look up table information and output of encoder is noted. Similarly we continue changing the states and noting the outputs bits relative to incoming bit and generate an encoded sequence. The complete path in Fig. 3 is shown with a green color line and final encoded sequence is shown on right side of the diagram.
TRELLIS Diagrams:
The trellis diagrams are a bit complex but they are generally preferred over other approaches as they can show the sequence of time as well. On axis we normally show the incoming bits relative to the time and on Y axis we place all the possible states. We normally move from left to right in horizontal direction with the passage of time. Depending upon the look up table of state transition and output bits of a particular encoder we continue to move from left to right relative to incoming bits and output are noted at every branch when we move to next state. Here again a dotted line represents that incoming bit was 1 and solid line shows that it was 0.
Figure : Trellis Diagramhttp://www.complextoreal.com/convo_files/image030.gif
Figure : Tree Diagram [7]
Interleaving:
Interleaving means to rearrange the coded bits in such a pattern that, if burst of errors occur during the transmission, after the deinterleaving these error bits should be separated and should appear as single independent error bits. Now correcting these single errors will be quite easy for us.
Commonly there are two type of interleaver used;
Block interleaver
Convolution interleaver
According to 802.11a standard bock interleaver is commonly used.
In Block interleaver we make a block of the coded bits in such a way that when we compute output of this block the consecutive bits are rearranged depending upon the parameters of the block interleaver. In block interleaver we make a matrix of order MxN, by filling the consecutive bits in columns. Once the matrix is filled the output is permuted and fed to modulator one row at a time. The order of matrix used is of special importance. The number of column N over bounds the expected burst length [5].For block codes, M should be larger than the code block length [5].
Mapping:
Now these interleaved and coded bits are ready for mapping on a constellation diagram. For example if we have 16 points on our map which means we are using QAM-16 and in this case each symbol will be carrying 4 bits.
Where, 'm' = number of bits per symbol
'n'= shows number of level.
Now every 4 bits will plotted on a specific position on constellation diagram and this particular point will also be correspondent to a vector have some magnitude and phase. This complex vector (for example 3+3j or 1+1j and so on) will be fed to IFFT block for further processing.
A constellation diagram for rectangular 16-QAM.
Figure : Constellation Diagram [9]
In Figure 6 we can see that every combination of four bits is representing a specific point on the map, and also this very point can be represented by a vector.
IFFT:
Now we are moving towards the discussion of IFFT, which is the most important block in OFDM system. Practically OFDM can be implemented by using IFFT on transmitter side and FFT on receiver side. FFT and IFFT are simply DFT and IDFT respectively but these are regarded as fast because we compute the twiddle factors and many of these twiddle factors have exactly same values with only negative sign with them. This means that we have to do less computation which makes it quite fast. One more important thing here is that, the FFT and IFFT are almost same the reason of using IFFT on transmitter side is that, it will receive the complex signal and consider it as to be in frequency domain and transforms it to time domain. So original signal that is transmitted will be in time domain.
OFDM RECEIVER
FFT:
FFT is basic building block of OFDM, so in order to understand the OFDM system completely it is very important to understand the mathematics of FFT. The FFT and IFFT both are derived from basic function called Discrete Fourier transform (DFT). So we start our investigation from simple DFT equation i.e.
We can alter this equation for simplicity as,
Where is called Twiddle factors.
Now we will start deriving the equations of 02 point FFT, then 04 point and then finally 08 point equations. In this we will be able to understand how the FFT block works in OFDM system
Two- point FFT
Using the equation;
Now we have calculated the Twiddle factor values now we can write the equations for Two Point FFT.
Figure : Two Point Butterfly [2]
We can generalize it as;
… [2]
Four-point FFT
Similarly, we can use the same process to find out the equations for four Point FFT.
This equation can be elaborated as;
Now we have to calculate 4 twiddle factors.
Using these results we can now write the equations;
Now consider;
Xe[n] =x[2n], n=0,1;
Xo[n] =x[2n+1], n=0,1
Then,
The factors in bracket of above equation can also be written as;
The four-point DFT then is
So we can now say that if we combine 02, 2 point FFT algorithms we can get a 4 point algorithm.
[4 point FFT of X[n]]=[2 point FFT of Xe[n]]+ [2 point DFT of Xo[n]]
This equation is also called decomposition equation for 4 point FFT.
Similarly we can continue our process for Eight point FFT, as four point FFT is combination of 02, 02 point FFT, similarly the 8 point FFT will be combination of 02 4 point FFT.
Figure : QAM 16 Constellation Diagrams [3]
Demapping:
Now the output of the FFT is a complex vector, we use a constellation diagram to plot these vectors and make decisions about received bits. Now if the output of the FFT is 3+3j, then it will be plotted on this constellation diagram and corresponding bits (4 bits if QAM 16 is used) will be the input of next block.16QAM modulation with Gray coded mapping
DeInterleaving:
Deinterleaver simply performs the reverse operation of the interleaver. It receives the symbols and fills the matrix of same order as used on transmitter side (MxN). The process of filling the matrix is totally opposite here i.e. we fill the matrix row wise and remove the bits column wise.
Let the stream be received from channel i
The shaded portion shows three bits burst error.
We will assume a deinterleaver array of order 3x4.
As shown bits '7 8 9' are error bits, and after deinterleaver process burst error will be converted into single bit random error.
Result after Deinterleaving is,
As it can be clearly seen that three bit burst error is converted to single bit random error (shaded portion), and then fed to decoder.
Decoding:
There are many techniques to decode the convolution codes. For example,
Fano Algorithm… which is a sequential decoding technique
Viterbi Algorithm… which is a maximum likelihood method
Viterbi algorithm is commonly used so we will focus this in this paper.
For decoding we use the same Trellis diagram as we used in coding part but here we will also consider some other thing as well. Remember in trellis diagram we move from left to right relative to the incoming bits. But on coding side we were certain about the incoming bit and we have to move to one other state when a bit comes. Here we have to go to both the possible states as we are not certain that incoming bit is correct or there is a error bit involved. And final decoding decision is made on the basis of path metric. Each intermediate branch has its own hamming metrics which is computed by taking the XNOR of the incoming bits and output bits of encoder. The same look up table of the encoder containing the information about states and output bits will be used for states transitions and for calculating branch and path metrics.
Bits received=00
Valid codeword=00
Hamming Metric=2
This all process makes the algorithm even more complex.
Similarly we continue calculating the branch metrics and add these to find out the path metrics. Every step we keep the path with higher path metrics and discard the path with lower path metrics. At last stage the path with the highest path metrics is kept and all other all discarded. This final path is traced back and finally decoded.
