# Discrete Fourier Transform

Discrete Fourier Transform or DFT is a mathematical operation that transforms a time domain signal to frequency domain. It is usually implemented using the Fast Fourier Transform (FFT). The computational complexity of the DFT is N2 whereas its (N)log2N for the FFT, where N is the number of samples of the the time domain signal. Mathematically, the DFT is written as

and this operation can be easily implemented in MATLAB as shown below.

```clear all
close all

fm=100;
fs=1000;
Ts=1/fs;
N=1024;
t=0:Ts:(N-1)*Ts;

x=cos(2*pi*fm*t);
W=exp(-j*2*pi/N);

n=0:N-1;
for k=0:N-1
X(k+1)=sum(x.*(W.^(k*n)));
end

plot((0:k)/N,abs(X))
xlabel ('Normalized Frequency')
ylabel ('X')```

The DFT of the cosine function with frequency of 100Hz is shown below. It must be noted that the frequency in the figure below is normalized by the sampling frequency. So the peaks in the graph occur at 0.1*1000=100Hz and 0.9*1000=900Hz (image frequency). Actually if you zoom in you will see that the peaks are not exactly at 0.1 and 0.9 but  are slightly offset as the frequency bins are not located at exactly those frequencies.

DFT of a cosine wave

In case of multiple sinusoids the resolution of the DFT becomes important. Higher the sample size (duration of the time domain signal) higher is the resolution of the DFT. As stated earlier the DFT is a computationally complex operation and usually the Fast Fourier Transform (FFT) is used to compute the frequency domain behavior. We will discuss this in the following posts.

A simple way to expedite the process of DFT calculation is to use matrix manipulation instead of a “for loop”.This is shown below.

```clear all
close all

fm=100;
fs=1000;
Ts=1/fs;
N=128;
t=0:Ts:(N-1)*Ts;

x=cos(2*pi*fm*t);
W=exp(-j*2*pi/N);

n=0:N-1;
k=0:N-1;

X=x*(W.^(n'*k));

plot(k/N,abs(X))
xlabel ('Normalized Frequency')
ylabel ('X')```

Although matrix manipulation makes for a nice and clean code, it was found that there was no improvement in the computation time. Both the “for loop” code and the “matrix multiplication” code took about 0.35 seconds to execute. However, increasing the sample size from 128 to 1024 results in significant better computation time for the latter scheme.

# CDMA vs OFDMA

 Property CDMA OFDMA 1. Channel bandwidth Full system bandwidth Variable system bandwidth to accommodate users with different data rates, 1.25, 2.50, 5.00, 10.00, 15.00 and 20.00 MHz, actual transmission bandwidth is a bit lower than this 2. Frequency-selective scheduling Not possible A key advantage of OFDMA, although it requires accurate real-time feedback of channel conditions from receiver to transmitter 3. Symbol period Very short—inverse of the system bandwidth Very long—defined by subcarrier spacing and independent of system bandwidth 4. Equalization Complicated time domain equalization Simple frequency domain equalization 5. Resistance to mulitpath Rake receiver can combine various multipath components Highly resistant to multipath due to insertion of cyclic prefix (CP) 6. Suitability for MIMO MIMO is not suited to a wideband frequency selective channel MIMO is suited to the independent narrowband flat fading channels that the subcarriers provide 7. Resistance to narrowband interference Resistant to narrow band interference Some subcarriers to be affected by narrowband interference 8. Separation of users Scrambling and orthogonal spreading codes Frequency and time although scrambling and spreading can be added as well

Reference: Agilent 3GPP Long Term Evolution System Overview, Product Development and Test Challenges Application Note.

# BER of 64-QAM OFDM in Frequency Selective Fading-II

In the previous post we had considered a static frequency-selective channel. We now consider a time-varying frequency selective channel with 7 taps. Each tap of the time domain filter has a Gaussian distributed real component with variance 1/(2*n_tap) and a Gaussian distributed imaginary component with variance 1/(2*n_tap). The amplitude of each tap is thus Rayleigh distributed and the phase is Uniformly distributed. Since the power in each component is normalized by the filter length (n_tap) the BER performance would remain the same even if the filter length is changed (this has been verified experimentally).

```%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% FUNCTION TO SIMULATE PERFORMANCE OF 64-OFDM IN TIME VARYING FREQUENCY SELECTIVE CHANNEL
% n_bits: Input, length of binary sequence
% n_fft: Input, length of FFT (Fast Fourier Transform)
% EbNodB: Input, energy per bit to noise power spectral density ratio
% ber: Output, bit error rate
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Eb=7;
M=64;
k=log2(M);
n_cyc=32;
EbNo=10^(EbNodB/10);
x=transpose(round(rand(1,n_bits)));
h1=modem.qammod(M);
h1.inputtype='bit';
h1.symbolorder='gray';
y=modulate(h1,x);
n_sym=length(y)/n_fft;
n_tap=7;

for n=1:n_sym;
s_ofdm=sqrt(n_fft)*ifft(y((n-1)*n_fft+1:n*n_fft),n_fft);
s_ofdm_cyc=[s_ofdm(n_fft-n_cyc+1:n_fft); s_ofdm];
ht=(1/sqrt(2))*(1/sqrt(n_tap))*(randn(1,n_tap)+j*randn(1,n_tap));
Hf=fft(ht,n_fft);
r_ofdm_cyc=conv(s_ofdm_cyc,ht);
r_ofdm_cyc=(r_ofdm_cyc(1:n_fft+n_cyc));
wn=sqrt((n_fft+n_cyc)/n_fft)*(randn(1,n_fft+n_cyc)+j*randn(1,n_fft+n_cyc));
r_ofdm_cyc=r_ofdm_cyc+sqrt(Eb/(2*EbNo))*wn.';
r_ofdm=r_ofdm_cyc(n_cyc+1:n_fft+n_cyc);
s_est((n-1)*n_fft+1:n*n_fft)=(fft(r_ofdm,n_fft)/sqrt(n_fft))./Hf.';
end

h2=modem.qamdemod(M);
h2.outputtype='bit';
h2.symbolorder='gray';
h2.decisiontype='hard decision';
z=demodulate(h2,s_est.');
ber=(n_bits-sum(x==z))/n_bits
return
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
```

As before we have used an FFT size of 128 and cyclic prefix of 32 samples. The FFT and IIFT operations are normalized to maintain the signal to noise ratio (SNR). The extra energy transmitted in the cyclic prefix is also accounted for in the SNR calibration.

It is observed that the BER performance of 64-QAM OFDM in the time-varying frequency-selective channel is quite similar to that in the static frequency-selective channel with complex filter taps. It must be noted that with 64-QAM the goal is to achieve higher bit rate, error rates can be improved using antenna diversity and channel coding schemes.

Given below is the wrapper that should be used along with the above code. The wrapper basically calls the above routine for each value of EbNodB. The length of the binary sequence and the FFT size are other inputs to the function. The bit error rate at the specific EbNodB is the output of the function.

```%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
clear all;
close all;
k=6;
n_fft=128;
l=k*n_fft*1e3;
EbNodB=0:2:20;
for n=1:length(EbNodB);n
end;
semilogy(EbNodB,ber,'O-');
grid on
xlabel('EbNo')
ylabel('BER')
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%```

In future we would use the standard LTE channel models, namely EPA, EVA and ETU in our simulation.

# OFDM Modulation and Demodulation (AWGN)

OFDM modulation works on the principle of converting a serial symbol stream to a parallel symbol stream with each symbol from the parallel set modulating a seperate carrier. The spacing between the carriers is 1/T where T is the duration of the OFDM symbols (without cyclic prefix). This guarantees orthogonality of the carriers i.e. there is no interference between carriers. The addition of orthogonal carriers modulated by parallel symbol streams is equivalent to taking the IFFT of the parallel symbol set. At the receiver the inverse operation of FFT is performed and the parallel symbol streams are converted to serial symbol streams.

The main advantage of this scheme is that one carrier (or set of carriers) may undergo severe fading but other carriers would be able to carry data. Equalization on these narrowband channels is also much easier than equalization of one wideband channel. Intersymbol Interference (ISI) which effects the signal in the time domain is removed by adding a guard period between symbols, called cyclic prefix (which we will discuss later).

We demonstrate the performance of OFDM with QPSK modulation in a simple AWGN channel. Although the true benefits of OFDM are really visible when we have a fading channel but this simple example would serve as a good starting point.

```%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% FUNCTION TO CALCULATE BER OF OFDM IN AWGN
% seq_len: Input, number of OFDM symbols
% n_carr: Input, number of subcarriers
% EbNo: Input, energy per bit to noise PSD
% ber: Output, bit error rate
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function[ber]=OFDM_err(seq_len,n_carr,EbNo)
for n=1:seq_len
si=2*(round(rand(1,n_carr))-0.5);
sq=2*(round(rand(1,n_carr))-0.5);
s=si+j*sq;
s_ofdm=sqrt(n_carr)*ifft(s,n_carr);
wn=(1/sqrt(2*10^(EbNo/10)))*(randn(1,n_carr)+j*randn(1,n_carr));
r=s_ofdm+wn;
s_est=fft(r,n_carr);
si_est=sign(real(s_est));
sq_est=sign(imag(s_est));
ber1(n)=(n_carr-sum(si==si_est))/n_carr;
ber2(n)=(n_carr-sum(sq==sq_est))/n_carr;
end
ber=mean([ber1 ber2]);
return
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
```

As expected in an AWGN channel the BER performance of OFDM is simply the BER performance of QPSK in AWGN. With cyclic prefix, some of the transmitted energy would be wasted and the BER performance would be a bit worse (to be discussed in future posts).