Unit - 3

Discrete Fourier Transform

3.1 Discrete Fourier Transform: Frequency-Domain Sampling and Reconstruction of Discrete-Time Signals

Frequency domain sampling

Sampling in frequency domain is usually used in DFT (Discrete Fourier transform), where continuous signal of spectrum in sampled to get discrete values of spectrum, which results in periodicity in time domain. This helps to process any continuous spectrum signal of non periodic in nature to discretize and digitize for further processing.

The following figure indicates a continuous-time signal x (t) and a sampled signal xs (t). When x (t) is multiplied by a periodic impulse train, the sampled signal xs (t) is obtained.

Fig 1 Sampled Signal

Sampling Rate

To discretize the signals, the gap between the samples should be fixed. That gap can be termed as a sampling period Ts.

Sampling Frequency=1/Ts=fs

Where,

Sampling frequency is the reciprocal of the sampling period. This sampling frequency, can be simply called as Sampling rate. The sampling rate denotes the number of samples taken per second, or for a finite set of values.

Nyquist Rate

Suppose that a signal is band-limited with no frequency components higher than W Hertz. That means, W is the highest frequency. For such a signal, for effective reproduction of the original signal, the sampling rate should be twice the highest frequency.

Which means,

fS=2W

Where,

This rate of sampling is called as Nyquist rate.

Sampling theorem in time domain

The sampling theorem, which is also called as Nyquist theorem, delivers the theory of sufficient sample rate in terms of bandwidth for the class of functions that are bandlimited.

The sampling theorem states that, “a signal can be exactly reproduced if it is sampled at the rate fs which is greater than twice the maximum frequency W.”

Let us consider a band-limited signal, i.e., a signal whose value is non-zero between some –W and W Hertz.

Such a signal is represented as x(f)=0 for ∣f∣>W

For the continuous-time signal x (t), the band-limited signal in frequency domain, can be represented as shown in the following figure.

Fig 2 Band Limited Signal

If the signal x(t) is sampled above the Nyquist rate, the original signal can be recovered, and if it is sampled below the Nyquist rate, the signal cannot be recovered.

The following figure explains a signal, if sampled at a higher rate than 2w in the frequency domain.

Fig 3 fs>2W

The above figure shows the Fourier transform of a signal xs (t).

If fs<2W

The resultant pattern will look like the following figure.

Fig 4 fs<2W

Here, the over-lapping of information is done, which leads to mixing up and loss of information. This unwanted phenomenon of over-lapping is called as Aliasing.

Aliasing

Aliasing can be referred to as “the phenomenon of a high-frequency component in the spectrum of a signal, taking on the identity of a low-frequency component in the spectrum of its sampled version.”

Numerical:

Solution:

We know,

X[n] =x(nT)

      = cos(200πnT)

      = cos(2πn/3) , where n= -1,0,1,2……

The frequency in x(t) is 200π rad/s while that of x[n] is 2π/3.

2.) Determine the Nyquist frequency and Nyquist rate for the continuous-time signal  x(t) which has the form of:

X(t) = 1+ sin(2000πt) + cos (4000πt)

Solution:

The frequencies are 0, 2000π and  4000π.

The Nyquist frequency is   4000π rad/s and the Nyquist rate is 8000π rad/s.

3) Consider an analog signal.

Solution.

The frequency in the analog signal

The largest frequency is

The Nyquist rate is

4) The analog signal

Using a sampling rate

. What is discrete time signal obtained after sampling?

What is analog signal

we can reconstruct from the samples if we use ideal interpolation?

Solution.

2.     For

For   ,the folding frequency is

Hence is not affected by aliasing

Is changed by the aliasing effect

Is changed by the aliasing effect

So those normalizing frequencies are

The analog signal that we can recover is

Which is different than the original signal

5) For

If

, what is the discrete time signal after sampling?

If

, what is the discrete time signal after sampling?

Solution.

a.

The minimum sampling rate is

And the discrete time signal is

b. if   , the discrete time signal is

c. If Fs=75Hz , the discrete time signal is

d. For the sampling rate

   in part in (c). Hence

So, the analog sinusoidal signal is

6) Suppose a continuous-time signal  x(t) = cos (Ø0t) is sampled at a sampling frequency of 1000Hz to produce x[n]: x[n] = cos(πn/4). Determine 2 possible positive values of Ø0, say, Ø1 and Ø2. Discuss if cos(Ø1t) or cos(Ø2t) will be obtained when passing through the DC converter.

Solution:

Taking T= 1/1000s

cos(πn/4) =x[n] = x(nT) = cos (Ø0n/1000)

Ø1 is easily computed as           

Ø1 = 250π

Ø2 can be obtained by noting the periodicity of a sinusoid:

Ø2n/1000)

Ø2 = 2250π

Reconstruction of Discrete-Time Signals

Reconstruction process

Fig 5 Reconstruction of signal

The sampled data signal is modified by the controller. The hold circuit than converts the signal to analog form. The simplest hold circuit is ZOH (zero order hold) in which the reconstructed signal acquires the same value as the last received sample for the entire sampling period.

The basic sampler is shown in above figure (a) and output in figure (b). The high frequency signal present in the reconstructed signal is filtered by the controller elements which are the low pass in frequency behaviour.

The first or higher order holds have no advantage over the ZOH. In the first order hold the last two signal samples are used to reconstruct the signal for the current sampling period.

Key takeaway

Aliasing can be referred to as “the phenomenon of a high-frequency component in the spectrum of a signal, taking on the identity of a low-frequency component in the spectrum of its sampled version.”

3.2 Discrete Fourier Transform

The discrete Fourier transform transforms a sequence of N complex numbers into another sequence of complex numbers

which is defined by

Example:

Let N =4 and

Here we demonstrate how to calculate the DFT of x using equation (1)

3.3 DFT as a Linear Transformation

Using Linearity property, we can find the DFT easily. The formula for which is given as

X[K] =   =

x[n] = 1/N = 1/N

WN =

Suppose we have signal sequence x[n], then we will define vector xN of N point samples same way we will define vector N point for XN and WN.

xN =          XN =

WN =

Thus, we can represent N point DFT in matrix form

XN = WN xN

Example

Compute 4-point DFT of given sequence {1,0,0,1}. Use matrix for DFT computation?

Sol: x[n] = {1,0,0,1}

N-1 = 3

N= 4

W4 = =

X4 =

X4 =

3.4 Relationship of DFT to other Transforms

Relation to FT of an Aperiodic Sequence

A periodic sequence with FT X |ω| of aperiodic finite energy sequence x[n], sampled at N equally spaced frequencies.

ωk =2πk/N    for   0≤k≤N-1

X[k]= X [ω] for ω = 2πk/N =

Relation with Fourier coefficients of a Periodic Sequence

A periodic sequence x[n] with fundamental period N can be represented in Fourier series

x[n] =

ck = 1/N

DFT and the above equation when compared we get

X[k] =

DFT sequence is given by X[k] = N Ck

x[n] = 1/N 

Thus, N point DFT provides exact line spectrum of a periodic sequence with fundamental period N.

Relation with Z-transform

 Z-transform is given as

X[z] =

z=

X[z] =

The above equation is same as X[k] except the limits of n. So, if x[n] has finite duration length N we can write

X[z]=  = 

It means that X[z] for z= is equal to X[k]

We can express X[z] as a function of DFT X[k] as

X[ω] =

Key takeaway

DFT sequence is given by X[k] = N Ck

x[n] = 1/N 

Thus, N point DFT provides exact line spectrum of a periodic sequence with fundamental period N.

3.5 Properties of DFT: Periodicity, Linearity, and Symmetry Properties

Linear Property

If x(t) -> X(w)

   Y(t) -> Y(w)  then

a x(t) + b y(t)  -> a X(w) +b Y(w)

Time Shifting Property

If  x(t)⟷F.TX(ω)

Then Time shifting property states that

x(t−t0)⟷F.T   e−jω0t X(ω)

Frequency Shifting Property

If x(t)⟷X(ω)

Then frequency shifting property states that

ejω0t.x(t)⟷X(ω−ω0)

Time Reversal Property

If x(t)⟷X(ω)

Then Time reversal property states that

x(−t)⟷X(−ω)

Differentiation Property

If x(t)⟷X(ω)

Then Differentiation property states that

dx(t)dt ⟷jω.X(ω)

dnx(t)dtn⟷(jω)n.X(ω)

Integration Property

 Integration property states that

∫x(t)dt⟷1jω X(ω)

Then

∭...∫x(t)dt⟷(jω)n X(ω)

Multiplication and Convolution Properties

If x(t)⟷X(ω)

   y(t)⟷Y(ω)

Then multiplication property states that

x(t).y(t)⟷X(ω)∗Y(ω)

and convolution property states that

x(t)∗y(t)⟷1/2πX(ω).Y(ω)

Key takeaway

Numerical:

2.     Compute the N-point DFT of x(n)=7(n−n0)

Solution − We know that,

Substituting the value of x(n),

3.6 Multiplication of Two DFTs and Circular Convolution

Multiplication of Two DFTs

It is nothing but circular convolution of two sequence which is discussed below.

Circular Convolution

Let us take two finite duration sequences ,having integer length as N. Their DI are reapectively which is shown below

Now we will try to find the DFT of another sequence , which is given by

By taking the IDFT of the above we get

After solving the above equation finally we get

Methods of Circular Convolution

Generally, there are two methods, which are adopted to perform circular convolution and they are −

Concentric Circle Method

Let x1(n) and x2(n) be two given sequences. The steps followed for circular convolution of x1(n) and x2(n) are

Matrix Multiplication Method

Matrix method represents the two-given sequence x1(n) and x2(n) in matrix form.

Numerical:

Perform circular convolution of the two sequences, x1(n)= {2,1,2,-1} and x2(n)= {1,2,3,4}

(2)

When n=0;

The sum of samples of v0(m) gives x3(0)

⸫ x3(0)=2+4+6-2=10

When n=1;

The sum of samples of v1(m) gives x2(1)

⸫ x3(1)=4 + 1 +8-3=10

(3)When n=2;

The sum of samples of v2(m) gives x3(2)

⸫ x3(2)=6+2+2-4=6

(4) When n=3;

The sum of samples of v3(m) gives x3(3)

⸫ x3(3)=8+ 3+ 4-1= 14

x3(n)={10,10,6,14}

      = x1(0) x x2,0(0) + x1(1) x2,0(1) + x1(2) x2,0(2) + x1(3) x2,0(3)

    = 2 x 1 + 1 x 4 + 2 x 3 + (-1) x 2 = 2 +4 +6 -2 =10

3.7 Use of DFT in Linear Filtering

Linear Convolution states that

y(n) = x(n) * h(n)

Example 1: h(n) = { 1 , 2 , 1, -1 } & x(n) = { 1, 2, 3, 1 } Find y(n).

 METHOD 1: GRAPHICAL REPRESENTATION

 Step 1) Find the value of n = nx+ nh = -1 (Starting Index of x(n)+ starting index of h(n))

 Step 2) y(n)= { y(-1) , y(0) , y(1), y(2), ….} It goes up to length(xn)+ length(yn) -1. i.e n=-1

METHOD 2: MATHEMATICAL FORMULA

 Use Convolution formula

k= 0 to 3     (start index to end index of x(n))

 y(n) = x(0) h(n) + x(1) h(n-1) + x(2) h(n-2) + x(3) h(n-3)

METHOD 3: VECTOR FORM (TABULATION METHOD)

X(n)= {x1,x2,x3} &       h(n) ={ h1,h2,h3}

y(-1) = h1 x1

y(0) = h2 x1 + h1 x2

y(1) = h1 x3 + h2x2 + h3 x1 …………

METHOD 4: SIMPLE MULTIPLICATION FORM

3.8 Filtering of Long Data Sequences

The two methods used for filtering long sequences to short sequence are

Overlap-Save Method

The below figure shows this method. The steps involved are

L -1 zeros

h(0), …………, h (M -1)

Fig 7 Overlap-Save Method

[k] = H[k] Xm[k]   for 0≤ k ≤ N-1

[n] = {ym(0),  ym(1),…. ym(N-1)}

=ym[n]

Example

The unit sample response sequence of a system h[n] = {3,2,1}. Use the overlap save method to determine its output sequence in response to the repeating input sequence {2,0,-2,0,2,1,0,-2,-1,0}. Take N=8.

Sol:

8=L+2

L=6

The length of block selected is 6.

Block 1   Zeros added

Block 2

Block 3

h[n] = {3,2,1,0,0,0,0,0}

Fig 8 Final answer from overlap save method

Overlap-Add Method

L -1 zeros

h(0), …………, h (M -1)

Fig 9 Linear FIR Filtering by overlap add method

 1st block

 2nd block

 3rd block

After multiplying impulse response of length of M with DFT of input sequence we get

Ym[k] = H[k] Xm[k]

Taking IDFT of Ym[k]. The output of IDFT is block of length M

N= L+M-1. The M-1 points from each output block must overlap and should be added to first M-1 points of succeeding block. The output sequence is given by

y1[n] = y1[0], y1[1],….y1[L-1],y1[L],y1[L+1]……..y1[L+M-1]

y2[n] = y2[0], y2[1],….y2[L-1],y2[L],y2[L+1]……..y2[L+M-1]

y[n] = y[0],y[1],……y[L-1],y[L],y[L+1]……..y[L+M-1]

Example

The unit sample sequence of a system is h[n] = {3,2,1}. Use overlap add method to determine its output sequence in response to the repeating input sequence {2,0,-2,0,2,1,0,0,-2,-1,0}. Take N=8.

Sol:

8=L+2

L=6

From input every time 6 elements are selected and two zeros (M-1) are padded after them as shown below.

Fig 10 Breaking up long input sequence into blocks of data

h[n] = {3,2,1,0,0,0,0,0}

Fig 10 Final answer from overlap add method

3.9 Efficient Computation of DFT: FFT Algorithms

Certain algorithms permit implementations of Discrete Fourier transform with considerable savings in computation time. These algorithms are known as Fast Fourier Transform.

FFT algorithm are based on fundamental principle of decomposing the computation of DFT of sequence length into successively smaller discrete Fourier transforms.

They are basically two classes of FFT algorithms

3.10 Direct Computation of the DFT

Assume that WknN has been precomputed and stored in a table for the N of interest. WmN is periodic in m with period N, so we just need to tabulate the N values:

WmN = cos(2πm/N) – j sin (2πm/N)

for m = 0, . . . , N – 1

Now we can compute each X[k] directly form the formula as follows

X[k]=

For each value of k, there are N complex multiplications, and N − 1 complex additions. There are N values of k, so the total number of complex operations is N · N + N (N − 1) = 2N 2 − N ≡ O (N2). Complex multiplies require 4 real multiplies and 2 real additions, whereas complex additions require just 2 real additions. So, the N2 complex multiplies are the primary concern.

 N2 increases rapidly with N, so how can we reduce the amount of computation? By exploiting the following properties of W:

• Symmetry property: WNk+N/2 = −WKN = ejπ WkN

• Periodicity property: WNk+N = WkN

• Recursion property: W2N = WN/2 The first and third properties hold for even N, i.e., when 2 is one of the prime factors of N. There are related properties for other prime factors of N.

Key takeaway

X[k]=

3.11 Radix-2 FFT Algorithms

Usually, we calculate N point DFT as N is an important factor. It can also be considered as N= r1, r2, r3, …… rv

r is selected because it represents Radix of FFT algorithm.

N = rv

For instance, if N= 8 and r =2 we can write

N = rv = 2v

8=2v

v= 3

v represents the number of stages in the FFT algorithm. But in signal processing we only relate to the number of samples. For DFT we select number of samples N and we divide by r. For example

Let N= 8

N’ = N/2 =4

N’ is still divisible by 2. N’=N/2=4/2 =2

Now N’’=r=2 and stop the process.

3.12 Decimation-In-Time (DIT), Decimation-In-Time (DIF)

Decimation-in-time algorithm

This algorithm is known as Radix-2 DIT-FFT algorithm which means the number of output points N can be expressed as a power of 2 that is N = 2M where, M is an integer.

Let x(n) be a sequence where N is assumed to be a power of 2. Decimate or break this sequence into two sequences of length N/2 where one sequence consists of even-indexed values of x(n) and the other of odd-indexed values of x(n).

xe(n)  = x(2n)       n= 0,1,……….. N/2-1

xo(n) = x(2n+1)      n= 0,1,……….. N/2 -1

The N-pt DFT of x(n) can be written as

X(k) =    WN nk       where k=0,1……….. N-1.

Separating x(n) into even and odd indexed values of x(n) we obtain

X(k) =    WN nk   +    WN nk  

 ( n even)  (n odd)

= WN 2nk  + WN (2n+1)k

=  WN 2nk   + Wnk    W N 2nk

X(k) =   WN 2nk  +  Wnk    W N 2nk

WN2  =( e-j2π/N) 2 =    e-j2π/N/2 = W N/2  .

WN2 = W N/2

X(k) = W N/2n k  +  WNk     WN/2kn

W84 = -1

W8 5 = - W 81

W86 = - W82

W87 = - W83

G(0) – H(0) = x(4)

G(1)  - W 81 H(1) = x(5)

G(2) - W82 H(2) = x(6)

G(3) - W83  H(3) = x(7)

Consider the sequence x[n]={ 2,1,-1,-3,0,1,2,1}. Calculate the FFT.

Arrange the sequence as x(0) x(4) x(2) x(6) x(1) x(5) x(3) x(7)

Since N=8 find the values W8 0 to W 87

Apply the butterfly diagram to obtain the  values.

Decimation in Frequency FFT

Apart from time sequence, an N-point sequence can also be represented in frequency. Let us take a four-point sequence to understand it better.

Let the sequence be x[0],x[1],x[2],x[3]………..x[7]

Mathematically, this sequence can be written as;

 X(k) =    WN n-k       where k=0,1……….. N-1.

Now let us make one group of sequence number 0 to 3 and another group of sequence 4 to 7. Now, mathematically this can be shown as

=    WN nk      +     WN nk

 Let us replace n by r, where r = 0, 1 , 2….N/2−1.

=     W N/2 nr

We take the first four points  x[0],x[1],x[2],x[3] initially, and try to represent them mathematically as follows –

  W 8 nk + W8 (n+4) k

= + W8 (n+4) k

=    + { W8 (4) k }  W8 nk 

 X[0] =    +  X[n+4]

X[1] =   + X[n+4]) W8 nk

= X(0) – X(4) + (x[1] – X[5]) W8 1 + ( X[2] – X[6] )W82  +  X(3) – X(7) W8 3

Fig 11 DIF –FFT Algorithm

Find the DIF –FFT of the sequence x(n)= { 1,-1,-1,1,1,1,-1} using Dif-FFT algorithm.

X(0)= 20      X(4) =0

X(1) = -5.828- j2.414    X(5) = -0.1716 + j 0.4141

X(2) = 0      X(6) = 0

X(3) = -0.171 – j 0.4142    X(7) = -5.8284 + j2.4142

Reference