Example1:
Consider a length-N sequence defined for n = 0,1,2,……,(N-1) where
Find the DFT of the given sequence .
The N-point DFT is equal to
Example2:
Consider a length-N sequence defined for n = 0,1,2,……,(N-1) where
Find the DFT of the given sequence .
The N-point DFT is equal to
Example 3:
Consider an L up-sampler described by the discrete sequence
Find the DTFT of this sequence.
The input/output relationship in frequency domain is:
Substituting, m = (n/L)
Example:
Commonly used General Properties of the DFT
Assume that we denote the data sequence x(nT) as x[n] .
(1) Symmetry property
Re[X(N-k)]=ReX(k)
This implies that amplitude has symmetry .
Im[X(N-k)]= - Im[X(k)]
This implies that the phase spectrum is antisymmetric.
(2) If x[n] is an even function xe[n] then
This implies that the transform is also even
(3) If x[n] is odd function xo[n] than
This implies that the transform is purely imaginary and odd
(4) Parseval’s Theorem
The normalized energy in the signal is given by either of the following expressions
(5) Delta Function
(6) Unit step function
(7)
Fourier transform of a CT complex exponential is interpreted as an impulse at w=w0. For discrete-time we expect something similar but difference is that DTFT is periodic in w with period 2p. This says that FT of x[n] should have impulses at w0, w0 ±2p, w0±4p etc.
(8)
(9) Linear cross-correlation of two data sequences or series may be computed using DFTs. The linear cross correlation of two finite-length sequences x1[n] and x2[n] each of length N is defined to be:
Circular correlation of finite length periodic sequences x1p[n] and x2p[n] is described as:
This circular correlation can be evaluated using DFTs as shown below:
The circular correlation can be converted into a linear correlation by using augmenting zeros. If the sequences are x1[n] of length N1 and x2[n] of length N2, then their linear correlation will be of length N1+N2-1.
To achieve this x1[n] is replaced by x1a[n] which consists of x1[n] with (N2-1) zeros added and x2[n] is augmented by (N1-1) zeros to become x2a[n].
Symmetry Relations of the T of a real sequence
Sequence / FourierTransformx[n] /
conjugate symmetry
real part is even
imaginary part is odd
even magnitude
odd phase
General Properties of the DT Fourier Transform
Property / Periodic signal / Fourier Series CoefficientsLinearity / /
Time Shifting / /
Conjugation / /
Time Reversal / /
Frequency Shifting / /
First Difference / /
Conjugate Symmetry for Real Signals / x[n] real /
Real & Even Signals / x[n] real and even / real and even
Real & Odd signals / x[n] real and odd / purely imaginary and odd
Even-Odd Decomposition
Of Real Signals / /
Parseval’s Relation /
Example:
Given the discrete sequence below find and plot the DTFT of the signal.
Using
that is;
and repeats with period of 2p as shown below:
Time Shifting:
Example.
Find the DTFT of an impulse function which occurs at time zero.
Convolution Property:
If x[n] , h[n] and y[n] denote the input , impulse response and output of an LTI system then
where, , and are the DTFT of the DT sequences.
Example: Consider an LTI system with impulse response and input as given below
Develop an expression for the response of the system?
Using (1) and (2) and solving for A and B gives
Hence
Case2: If
the above expression is also equal to :
Proof:
We know that the differentiation in frequency dictates the following
since we can together with above property say the following is also correct
to account for the factor we need to use a time-shift in the time-domain signal
Finally to account for the factor we can write
We note that is still zero prior to n = 0 since (n+1) = 0 at n = -1
Hence the final result can be written as:
Example:
Consider the sequence x[n] whose Fourier Transform X(ejw) is depicted for -p <= w <= p. Determine if x[n] is periodic, real, even, and/or finite energy.
If a signal is periodic and yet discrete the discrete-time Fourier Transform of it can not be continuous. It shall be zero except possibly for impulses located at various integer multiples of the fundamental frequency.
è x[n] is not periodic
From the symmetry properties for Fourier transforms a real valued sequence must have a Fourier transform of EVEN magnitude and a phase function that is ODD.
è x[n] is real by observation of the plots given above
If x[n] is an even function then by symmetry properties for real signals X(ejw) must be real and even.
Since
The DTFT can not be a real valued function due to the complex ecponential
è x[n] is not even
Finally to test the finite-energy property we can use Parseval’s relation.
it is clear from the above figure that carrying out this integral will lead to a finite quantity. We conclude that x[n] has finite energy.
DTFT Computation Using MATLAB
The related matlab functions that can be used are :
freqz
abs
angle
unwrap
real
imag
Function “freqz” can be used to compute the values of the DTFT of a sequence described as a rational function in terms of ejw:
at a predefined set of discrete frequency points w = wl .
For an accurate plot a fairly large number of frequency points should be selected.
There are various forms of the function:
H = freqz( num, den, w)
H = freqz( num, den, f, FT)
[H,w] = freqz( num,den,k)
[H, f] = freqz(num,den, k, FT)
[H,w] = freqz( num,den,k,’whole’)
[H, f] = freqz(num,den, k, ‘whole’FT)
freqz refers to the frequency response values as a vector H of a DTFT defined in terms of the vectors num and den containing the coefficients {pi} and {di} respectively at a predefined set of frequency values.
‘w’ is a vector which contains the prescribed set of frequencies between 0 and 2p.
In H = freqz(num,den,f,FT)
FT is the sampling frequency
Vector f provides the pre-defined values in range 0 à FT/2
Also it is possible to specify the total number of frequency points by ‘k’ in the argument of freqz. In this case DTFT values H are computed at k equally spaced points between 0 and p and returned as the output vector w.
For faster computations it is recommended that the number ‘k’ be chosen as a power of 2 such as 256 or 512.
Once the DTFT values have been determined they can be plotted either showing their real or imag parts or by magnitude and phase components using functions “abs” and “angle”. Function angle computes the phase in radians.
freqz(num,den) with no output arguments computes and plots the magnitude and phase response values as a function of frequency in the current figure window.
Reminder: Here show the slides about a MATLAB program using some of the above
Computational Complexity of the DFT
A large number of multiplications and additions are required for the calculation of the DFT. Let us try to analyze the following case.
For an 8-point DFT the expansion for X(k) becomes the following:
(1)
If we rename the quantity ( k2p/8 ) as K we can write the expanded summation as :
(2)
Equation (2) contains eight terms on the right hand side . Each term consists of a multiplication of an exponential term (complex) by an other term which is real or complex. Then each of the product terms is added together.
Therefore there are eight complex multiplications and seven complex additions to be calculated.
\ For a N-point DFT there will be N-complex multiplications
(N-1) complex additions
for the 8-point DFT there are also 8 harmonic components to be evaluated (k=0,1,……,7) . For the N-point DFT this number becomes N.
Therefore the total calculations of the 8-point DFT requires :
8×8 = 64 complex multiplications
8×7 = 56 complex additions.
For the N-point DFT this becomes :
N×N=N2 complex multiplications
N(N-1) complex additions
These numbers may seem small but then N= 1024 then approximately one million complex multiplications and one million complex additions are required. Clearly we need some means of reducing these numbers.
These numbers can be reduced if we note the redundancy that exists in the DFT expression.
The Decimation-in-time fast Fourier Transform algorithm
In this section we show how the redundancy in DFT is used o reduce the number of calculations. For the 1024-point DFT the number of calculations required can be reduced by a factor of 204.8. The algorithm which can achieve this is given the name fast Fourier Transform (FFT). When applied in the time-domain the algorithm is referred to as the decimation-in-time (DIT) FFT. Decimation here refers to the significant reduction in the number of calculations performed on time-domain data. The first DIT algorithm was introduced by Cooley and Tukey (1965).
NOTE: Computational savings will be seen to increase as
We will first try to establish some mathematical relationships.
Let us start with the DFT definition:
Also the factor will be written as WN.
Hence
We note at this point some of the properties of WN.
Firstly;
Secondly;
For exploiting the computational redundancy the data-sequence is divided into two equal sequences: one of even-numbered data, and one of odd-numbered data. For the sequences to be of equal length they must all contain an even-number of data. If not an augmenting zero can be added.
This allows the DFT to be converted into two DFTs each o N/2 points. This process then repeated until X1(k) is decomposed into N/2 DFTs each of two points both of which are initial data.
In practice the initial data is re-ordered and the N/2 two-point DFTs are calculated by taking the data in pairs.
These DFT outputs are combined to provide N/4 four-point DFTs.
Then these N/4 four-point DFTs are combined to form the N/8 eight-point DFTs
Etc .
Reminder: Draw the table 3.1 on board as example
Table 1. Structure of 8-point FFTk- ranges / N ranges
Data Sequence A0 / / 0,…….,7
8-point DFT of A0 / / 0,……,7 / 0,…….,7
Re-ordered A0 into two
Sequences A1 and A2 / A1 / / A2 / / 0,….....,7
4-point DFTs of A1 and A2 / / / 0,…….,3 / 0,…….,3
Reordered
Sequences A1 and A2
four sequences
A3, A4, A5, A6 / A3 / / A4 / / A5 / / A6 / /
0, 1
2-point DFTs of A3, A4, A5 and A6 / / / / / 0,1
The suffixes , n, extend from n = 0 to n =N-1 corresponding to the data values.
The terms in the even sequence may be designated x2n with n = 0 to n = N/2 -1.
The terms in the odd sequence becomes x2n+1 .
Even sequence Odd sequence
Using the fact that one can write .
Hence
(3)
Equation above can be written as
Here; is the DFT of the even sequence
is the DFT of the odd sequence
The factor occurs in both sums but needs calculating only once.