LTI system
(Linear Time Invariant)
Implementation
Fourier Series
• F(t) = ½ a0 + sum (ak*cos(2*pi*k*t) + bk*sin(2*pi*k*t))
• Where frequency k =1 to infinity
• Two components here are
• Constant
• Sum of sine and cosine (sinusoids with all frequencies)
• Any signal can be represented in this way
• Problem is to calculate coefficients ak and bk for every frequency
• Fourier Transform
Fourier Transform
• Multiply function with analyzing function
• Here analyzing function is sinusoids
• Here sinusoids are represented as expression of complex coefficient
• One complex coefficient per frequency
Fourier Transform
• Here time is varying from –infinity to + infinity
• In practice we have a discrete signal so Discrete Fourier Transform is
used
Discrete Fourier Transform
• Transform for N samples, where n=0 to N-1
• We are searching coefficient for each frequency k
• K varies from 1 to sampling freq with interval = resolution of the signal
Discrete Fourier Transform
• Unfold the summation
• bn = 2*pi*k*n/N
• Also by Euler’s formula
• e^(j*x) = cos x + j sin x
• X(k) = x0 [ cos(-b0) + j sin(-b0)] + x1[ cos(-b1) + j sin(-b1)] + ..
• X(k) = A(k) + B(k) j … one complex no with real and imaginary part
Discrete Fourier Transform
• X(k) = A(k) + B(k) j
• Maginitude / Amplitude of Sinusoid at freq K is
• sqrt(a(k)^2 + b(k)^2)
• Phase / Shift of Sinusoid at freq K is
• Tan_inverse(b(k) / a(k))
• Ref: [Link]
Discrete Fourier Transform Example
• Question Find the Amplitude and Phase using DFT by using following signal
• X0 = 0
• X1= 0.707
• X2= 1
• X3= 0.707
• X4= 0
• X5 = -0.707
• X6 = -1
• X7 = -0.707
• Reading NOTE: This is 1Hz Sine wave with amplitude 1
• Sampling freq = 8Hz
• So, samples in 1 sec = 8
Discrete Fourier Transform Example
• So, we can plot frequencies ,
• Freq resolution = sampling freq / no of samples
• So for k=0 ,
• X(0) = x(0) * e ^0 + x(1) * e^ 0 + …
• X(0) = 0 + 0.707 + .. [sum of all samples]
• X(0)= 0
• ----------
• X(1) = x(0) * e ^ -((j * 2pi*1*0)/8) + x(1) * e ^ -((j * 2pi*1*1)/8)+..
• X(1) = 0+0.707 [ cos(-pi/4) + j * sin(-pi/4)] + …
• X(1) = -4j
Discrete Fourier Transform Example
• So for k=2 -6
• X(2) = 0
• ----------
• k=7
• X(7) = 4j
• -----
• Nyquist limit :: states that we can’t measure frequencies beyond sampling freq /
2
• So, all the values before the Nyquist limit are doubled and all values after it are
removed
• So final DFT are
• x(0)= 0, x(1) = -8j, x(2) = 0, x(3) = 0 .. All values fromx(4) are removed
Discrete Fourier Transform Example
• Amplitude(k) = sqrt(a(k)^2 + b(k)^2)
• ampl(0) = 0, ampl(1) = 8, ampl(2) = 0, ..same 0 till 8
• Avg Amplitude of the Signal = Sum of all amplitudes / no of samples
= (0+8+0+0+0+0+0+0)/8
• Avg Amplitude of the Signal = 8/8 = 1
• At freq =1, Phase(1) = tan_inv( -8/0)
• So we need to find phase by plotting it,
• Phase ( 1) = 3*pi/2
Discrete Fourier Transform
• Transform for N samples, where n=0 to N-1
• We are searching coefficient for each frequency k
Discrete Fourier Transform
• Discrete in time as well as frequency domain
• In DFT N*N complex number multiplications so O(n^2)
• It can be represented in matrix multiplication format
• [coefficient matrix](size=n*n) * [ input signal vector x0-xn](Size=1*n)
• Every coefficient is e ^ (-j*2*pi*k*n*/N)
Fast Fourier Transform
• Very fast O(n log n ) streaming of signal becomes easy
• Radix 2 Algorithm
• Length of Input N = 2^v
• Split the seq into two parts, even sample and odd sample
• Once two signals are there then calculate the DFT
• How to do it?
• Reverse the bits of index in bit reversal mode
FFT Circuit
Signal Split in Original Bit Revesed
Index odd Index Index
Even 000 000
0 0 0
001 100
1 2 4
010 010
2 4 2
011 110
3 6 6
100 001
4 1 1
5 3 5 101 101
6 5 3 110 011
7 7 7 111 111
FFT Circuit