Digital Signal Processing

(BEC-42)

Unit-1

Digital Signal Processing(BEC-42)

 Syllabus

UNIT-I
• Discrete Fourier Transforms: Definitions, Properties of the
DFT, Circular Convolution, Linear Convolution
• Fast Fourier Transform Algorithms: Introduction,
Decimation in Time (DIT) Algorithm, Computational
Efficiency, Decimation in Frequency (DIF) Algorithm.

UNIT-II
IIR Filter Design: Structures of IIR – Analog filter design –
Discrete time IIR filter from analog filter – IIR filter design by
Impulse Invariance, Bilinear transformation, Approximation of
derivatives – (LPF, HPF, BPF, BRF) filter design using
frequency translation.

Digital Signal Processing(BEC-42)

UNIT-III
FIR Filter Design: Windowing and the Rectangular Window,
Other Commonly Used Windows, Examples of Filter Designs
Using Windows, Kaiser Window.

UNIT-IV
• Realization of Discrete Time Systems: FIR systems – Direct
form, cascaded, parallel and lattice structures, IIR systems –
Direct form, cascaded, parallel, lattice and lattice ladder
structures
• Finite Word length Effects: Quantization effect in filter
coefficients, round-off effect in digital filters

Digital Signal Processing(BEC-42)

 Books & References

1. John G Prokias, Dimitris G Manolakis, “Digital Signal

Processing”, Pearson Education.
2. Oppenheim & Schafer, “Digital Signal Processing” PHI
3. Johnny R. Johnson, “Digital Signal Processing”, PHI
Learning Pvt Ltd., 2009.
4. S. Salivahanan, ““Digital Signal Processing” Mc Graw
Hill Education
5. https://nptel.ac.in/courses/117/102/117102060/

Digital Signal Processing(BEC-42)

 Signal:
A signal is defined as a as any physical quantity that varies with
time, space, or any other independent variable or variables.
Mathematically, a signal is described as a function of one or more
independent variables.
Examples:

Continuous-Time Signal : A signal x(t) is said to be a continuous

time signal if it is defined for all time t.
Discrete-Time Signal : A discrete time signal x[nT] has values
specified only at discrete points in time.

Digital Signal Processing(BEC-42)

 Continuous Time Sinusoidal Signals

A simple harmonic oscillation is mathematically described as

x(t) = Acos (ω t + )

This signal is completely characterized by three parameters:

A = amplitude, ω = 2f = frequency in rad/s, and  = phase in
radians.

A T=1/f

Digital Signal Processing(BEC-42)

 Discrete Time Sinusoidal Signals

A discrete time sinusoidal signal may be expressed as

x[n] = Acos (ωn + ) - < n < 
Properties:
A discrete time sinusoid is periodic only if its frequency is a rational number.

Discrete time sinusoids whose frequencies are separated by an integer

multiple of 2 are identical.

The highest rate of oscillation in a discrete time sinusoid is attained when ω =

 ( or ω = - ), or equivalently f = 1/2 (or f = -1/2).

-1
0 2 4 6 8 10

Digital Signal Processing(BEC-42)

 System:
A system is defined as an entity that manipulates one or more signals
to accomplish a function, thereby yielding new signals.

Signal Processing:

A system characterized by the type of operation that it performs on

the signal. For example, if the operation is linear, the system is
called linear. If the operation is non-linear, the system is said to be
non-linear, and so forth. Such operations are usually referred to as
“Signal Processing”.

Digital Signal Processing(BEC-42)

 Basic Elements of a Signal Processing System

Analog input Analog output

signal Analog signal
Signal Processor

Analog Signal Processing

Analog Analog
input output
signal signal
A/D Digital D/A
converter Signal Processor converter

Digital Signal Processing

Digital Signal Processing(BEC-42)
 Advantages of Digital over Analogue Signal Processing

 Flexibility in reconfiguring

 Better control of accuracy requirements

 Easily stored on media

 Implementation of more sophisticated signal processing

algorithms

 Cheaper than its analogue counterpart

Digital Signal Processing(BEC-42)

 DSP Applications

Space photograph enhancement

Space
Data compression
Intelligent sensory analysis

Medical
Medical image storage and retrieval

Image and sound compression for

Commercial multimedia presentation.
Movie special effects
Video conference calling

Video and data compression

Telephone echo reduction
signal multiplexing
filtering

Digital Signal Processing(BEC-42)

 Classification of Signals

Deterministic and non-deterministic signals

 Periodic and aperiodic signals

Even and odd signals

Causal and non-causal signal

Energy and power signals

Digital Signal Processing(BEC-42)

 Classification of Signals

Deterministic Signals
A deterministic signal behaves in a fixed known way with respect
to time. Thus, it can be modeled by a known function of time t for
continuous time signals, or a known function of a sampler number
n, and sampling spacing T for discrete time signals.

Random or Stochastic Signal:

In many practical situations, there are signals that either cannot be
described to any reasonable degree of accuracy by explicit
mathematical formulas, or such a description is too complicated to
be of any practical use. The lack of such a relationship implies that
such signals evolve in time in an unpredictable manner. We refer to
these signals as random.
Digital Signal Processing(BEC-42)
 Periodic and Aperiodic Signals

A continuous signal x(t) is periodic if it exhibits periodicity, i.e.

x(t + T) = x(t)
where T is the period of the signal in units of time.

f = 1/T is the frequency of the signal in Hz. ω = 2/T is the angular

frequency in radians per second.

The discrete time signal x[nT] is periodic if and only if there exists
an N > 0 such that
x[nT + N] = x[nT]
where N is the period of the signal in number of sample spacing.

Example:

Frequency = 5 Hz or 10 rad/s

0 0.2 0.4
If there is no values of T and N that satisfies the above equations ,the
signal is called aperiodic (nonperiodic). Digital Signal Processing(BEC-42)
 Even and Odd Signals

A continuous time signal x(t) is said to an even signal if it satisfies

the condition
x(-t) = x(t) for all t
For discrete time signal
x(n)=x(-n)
The signal x(t) is said to be an odd signal if it satisfies the condition
x(-t) = -x(t)
For discrete time signal
x(n)=-x(-n)
In other words, even signals are symmetric about the vertical axis
or time origin, whereas odd signals are anti-symmetric about the
time origin. Similar remarks apply to discrete-time signals.
Example:

Even
Odd Odd
Digital Signal Processing(BEC-42)
 Causal and Non-causal Signals

A continuous time signal is said to be causal if its amplitude is

zero for negative time, i.e. , x(t)=0 for t ‹ 0

For discrete time signal, the condition for causality is

x(n)=0 for n ‹ 0

Anti-causal signal if the amplitude of signal is zero for positive

time
 For continuous time signal, x(t)=0 for t › 0
For discrete time signal, x(n)=0 for n › 0

 A signal which is neither causal nor ant-causal is called non-

causal signal.

Digital Signal Processing(BEC-42)

 Energy and Power Signals

A signal is referred to as an energy signal, if and only if the total

energy of the signal satisfies the condition 0 < E < 

On the other hand, it is referred to as a power signal, if and only

if the average power of the signal satisfies the condition 0 < P < 

An energy signal has zero average power, whereas a power

signal has infinite energy.

Periodic signals and random signals are usually viewed as

power signals, whereas signals that are both deterministic and
non-periodic are energy signals.

Digital Signal Processing(BEC-42)

 Some Elementary Discrete-Time Signals

1. Unit sample sequence

1 for n  0
 ( n)  
0 for n  0

Digital Signal Processing(BEC-42)

2.Unit step signal

1 for n  0
u ( n)  
0 for n  0

Digital Signal Processing(BEC-42)

3.Unit ramp signal

Digital Signal Processing(BEC-42)

4. Exponential signal: It is a sequence of the form

Where if the parameter a is real signal.

When the parameter a is complex valued, it can be expressed as

Where r and θ are the parameters.

real part

Imaginary part

Digital Signal Processing(BEC-42)

What is a System?

➢ Systems process input signals to produce output signals.

 Examples:
➢ A circuit involving a capacitor can be viewed as a system that
transforms the source voltage (signal) to the voltage (signal)
across the capacitor
➢ A CD player takes the signal on the CD and transforms it into a
signal sent to the loud speaker
➢ A communication system is generally composed of three sub-
systems, the transmitter, the channel and the receiver. The
channel typically attenuates and adds noise to the transmitted
signal which must be processed by the receiver
How is a System Represented?
➢ A system takes a signal as an input and transforms it into
another signal

Input signal Output signal

System
x(t) y(t)

➢ In a very broad sense, a system can be represented as the

ratio of the output signal over the input signal

➢ That way, when we “multiply” the system by the input signal, we

get the output signal
➢ This concept will be firmed up in the coming weeks
Types of Systems
 Causal & Non-causal
 Linear & Non Linear
 Time Variant &Time-invariant
 Stable & Unstable
 Static & Dynamic
 Invertible
Causal Systems

 Causal system : A system is said to be causal

if the present value of the output signal
depends only on the present and/or past
values of the input signal.
 Example: y[n]=x[n]+1/2x[n-1]
Non-causal Systems

 Non-causal system : A system is said to be

anticausal if the present value of the output signal
depends only on the future values of the input
signal.
 Example: y[n]=x[n+1]+1/2x[n-1]
Linear & Non Linear Systems

 A system is said to be linear if it satisfies the

principle of superposition
 For checking the linearity of the given
system, firstly we check the response due to
linear combination of inputs
 Then we combine the two outputs linearly in
the same manner as the inputs are combined
and again total response is checked
 If response in step 2 and 3 are the same,the
system is linear othewise it is non linear.
Time Invariant and Time Variant Systems

 A system is said to be time invariant

if a time delay or time advance of
the input signal leads to a identical
time shift in the output signal.
yi (t) = H{x(t − t0 )}
= H{S t 0{x(t)}} = HS t 0{x(t)}
y0(t) = S t 0 {y(t)}
= S t 0{H{x(t)}} = S t 0 H{x(t)}
 Linear Time-Invariant Systems

 Special importance for their mathematical tractability

 Most signal processing applications involve LTI systems
 LTI system can be completely characterized by their impulse
response
 
y n  =T x [n ] =T   x k  n − k  Linearity
 k =− 
 

 x k T  n − k =  x k h n Time − Inv

k
k =− k =−

 x k  h n − k  = x k  h k
k =−
Stable & Unstable Systems

 A system is said to be bounded-input

bounded-output stable (BIBO stable) iff
every bounded input results in a bounded
output.
i.e.
t | x(t) | M x   → t | y(t) | M y  
Stable & Unstable Systems

Example: The system represented by

y(t) = A x(t) is unstable ;A˃1
Reason: let us assume x(t) = u(t), then at
every instant u(t) will keep on multiplying
with A and hence it will not be bonded.
Static Systems

 A static system is memoryless system

 It has no storage devices
 its output signal depends on present values
of the input signal
 For example
Dynamic Systems
 A dynamic system possesses memory
 It has the storage devices
 A system is said to possess memory if its
output signal depends on past values and
future values of the input signal
Invertible Systems

A system is said to be invertible, if a distinct input produces

a distinct output. For two inputs 𝑥1 (𝑛) and 𝑥2 (𝑛) with
𝑥1 𝑛 ≠ 𝑥2 (𝑛) , an invertible system produces outputs
𝑦1 (𝑛) and 𝑦2 (𝑛) such that 𝑦1 𝑛 ≠ 𝑦2 𝑛 . For every
invertible system, there exists an inverse system.
Memoryless System

A system is memoryless if the output y[n] at every value

of n depends only on the input x[n] at the same value of n
Example :
Square y[n] = (x[n])2

y[n] = signx[n]
Sign

counter example: y[n] = x[n − no ]

Ideal Delay System
Discrete-Time Systems
 Discrete-Time Sequence is a mathematical operation that maps a
given input sequence x[n] into an output sequence y[n]

y[n] = T{x[n]} x[n] T{.} y[n]

 Example Discrete-Time Systems
 Moving (Running) Average

y[n] = x[n] + x[n − 1] + x[n − 2] + x[n − 3]

 Maximum
y[n] = max x[n],x[n − 1],x[n − 2]
 Ideal Delay System

y[n] = x[n − no ]
 System Properties

𝐻
Notation: Let H represent the system, 𝑥 𝑡 ՜ 𝑦 𝑡 represent
a system with input 𝑥 𝑡 and output 𝑦 𝑡 .

1. Stability: BIBO (Bounded input⇨Bounded output)

𝑥(𝑡) ≤ 𝑀𝑥 < ∞ ⇨ 𝑦(𝑡) ≤ 𝑀𝑦 < ∞
𝑥 𝑡 ≤ 𝑀𝑥′ < ∞ ⇨ 𝑦 𝑡 ≤ 𝑀𝑦′ < ∞
2.Memory /Memoryless:
➢ Memory system: present output value depend on
future/past input.
➢ Memoryless system: present output value depend only on
present input.
➢ Example:
3. Causal/noncausal
▪ Causal: present output depends on present/past values
of inputs.
▪ Noncausal: present output depends on future values of
input.
Note: Memoryless ⇨ causal, but causal not necessarily be
memoryless.

4. Time invariance (TI): time delay or advance of input ⇨

an identical time shift in the output.
Let us define a system mapping 𝑦 𝑡 = 𝐻(𝑥 𝑡 ). The system is
time-invariant if
𝐻
𝑥(𝑡 − 𝑡0 ) ՜ 𝑦(𝑡 − 𝑡0 )
𝐻
𝑥 𝑛 − 𝑛0 ՜ 𝑦[𝑛 − 𝑛0 ]
5.Linearity
𝐻 𝐻
Linear system: If 𝑥1 (𝑡) ՜ 𝑦1 (𝑡), 𝑥2 (𝑡) ՜ 𝑦2 (𝑡), then
𝐻
a𝑥1 𝑡 + 𝑏𝑥2 𝑡 ՜ 𝑎𝑦1 𝑡 + 𝑏𝑦2 (𝑡). Else, nonlinear.

• Superposition property (addition)

• Homogeneity (scaling)
Properties of a System:
➢ On this course, we shall be particularly interested in signals with
certain properties:
➢ Causal: a system is causal if the output at a time, only depends on
input values up to that time.
➢ Linear: a system is linear if the output of the scaled sum of two
input signals is the equivalent scaled sum of outputs
➢ Time-invariance: a system is time invariant if the system’s
output is the same, given the same input signal, regardless of
time.

➢ These properties define a large class of tractable, useful systems

and will be further considered in the coming lectures
 Fourier Analysis of Discrete Time Signals

For a discrete time sequence we define two classes of Fourier Transforms:

1. DTFT (Discrete Time Fourier Transform) for sequences having infinite duration
which relate the time and frequency domain
2. DFT (Discrete Fourier Transform) for sequences having finite duration.
 The Discrete Time Fourier Transform (DTFT)
Given a sequence x(n) having infinite duration, we define the DTFT as follows:

+
X () = DTFT x(n) =  x ( n ) e − j n

n =−

Similarly Inverse Discrete Time Fourier Transform (IDFT) is given as

+
x(n) = IDTFT X () =
1

jn
X () e d
2 −

x ( n) X ( )

….. …..

N −1 n −  
discrete time continuous frequency
Observations:

• The DTFT X ( ) is periodic with period 2 ;

• The frequency  is the digital frequency and therefore it is limited to the interval

−     +

Recall that the digital frequency  is a normalized frequency relative to the sampling frequency,
defined as
F
 = 2
Fs

one period of X ( )

− Fs − Fs / 2 0 Fs / 2 Fs F
− 2 − 0  2 
Example:

DTFT
x[n]
1

0 N −1 n

since
N −1
1 − e − j N
X ( ) =  e − j n
=
n =0 1 − e − j
sin( N / 2 )
= e − j ( N −1) / 2
sin( / 2 )
Example:

X ( ) = A e j  ( −  0) +
x[n] = A cos( 0n +  ) + A e − j  ( +  0)
 Frequency Domain Sampling: Discrete Fourier Transform (DFT)

Definition (Discrete Fourier Transform): Given a finite sequence

x = [ x(0), x(1),..., x( N −1)]

its Discrete Fourier Transform (DFT) is a finite sequence
X = DFT ( x) = [ X (0), X (1),..., X ( N −1)]

where
N −1
X (k ) =  x(n) wN ,wN = e − j 2 / N
kn

n =0

x DFT
X
Definition (Inverse Discrete Fourier Transform): Given a sequence

X = [ X (0), X (1),..., X ( N − 1)]

its Inverse Discrete Fourier Transform (IDFT) is a finite sequence

x = IDFT ( X ) = [ x(0), x(1),..., x( N −1)]

where
N −1
1
x ( n) =
N
 X (k )w
k =0
N
− kn
, wN = e − j 2 / N

X x
IDFT
Observations:
• The DFT and the IDFT form a transform pair.

x DFT
X

back to the same signal !

x IDFT
X

• The DFT is a numerical algorithm, and it can be computed by a digital computer.

 DFT as a Vector Operation
Let

 x[0]   X [ 0]   1 
 x[1]   X [1]   w− k 
x= , X = DFT {x} =   ek =  N ,
        
     − k ( N −1) 
 x[ N − 1]  X [ N − 1]  wN 

Then:
x
X [k ] = ek*T x
ek 1
X [k ]ek
x=
1
( X [0]e0 + X [1]e1 + ... + X [ N − 1]eN −1 ) N
N
  X [0]  1 1  1   x[0] 
 X [1]  1 w  w N −1   x[1] 
X = DFT {x} =  = N N  
       
   N −1 ( N −1)( N −1)   
 −   −
  
X [ N 1] 1 w w x[ N 1]
N
 N
WN

X = WN x
 1 *T
x = WN X
N 

WN−1
Example: Find the inverse DFT of X(k) ={1,2,3,4 }.

Solution : The inverse DFT is defined as

𝑁−1
1
𝑥(𝑛) = ෍ 𝑋 𝑘 𝑒 𝑗2𝜋𝑛𝑘/𝑁 𝑛 = 0,1,2,3, … … … . 𝑁 − 1
𝑁
𝑘=0
Given N=4,
3
1 𝑗2𝜋𝑛𝑘
𝑥 𝑛 = ෍𝑋 𝑘 𝑒 𝑁 𝑛 = 0,1,2,3
4
𝑘=0
When n=0
3
1 𝑗2𝜋0𝑘 1 5
𝑥 = ෍𝑋 𝑘 𝑒 𝑁 = 1+2+3+4 =
4 4 2
𝑘=0
When n=1
3
1
𝑥(1) = ෍ 𝑋 𝑘 𝑒 𝑗𝜋1𝑘/2
4
𝑘=0
1
1 + 2𝑒 𝑗𝜋/2 + 3𝑒 𝑗𝜋 + 4𝑒 𝑗3𝜋/2
=
4
1 1 1 1
= 1 + 2 𝑗 + 3 −1 + 4 −𝑗 = −2 − 𝑗2 = − − 𝑗
4 4 2 2
When n=2
3
1
𝑥(2) = ෍ 𝑋 𝑘 𝑒 𝑗𝜋𝑘
4
𝑘=0

1
= 1 + 2𝑒 𝑗𝜋 + 3𝑒 𝑗2𝜋 + 4𝑒 𝑗3𝜋
4

1 1 1
= 1 + 2 −1 + 3 1 + 4 −1 = −2 = −
4 4 2
When n=3
3
1
𝑥(3) = ෍ 𝑋 𝑘 𝑒 𝑗3𝜋𝑘/2
4
𝑘=0

1
= 1 + 2𝑒 𝑗3𝜋/2 + 3𝑒 𝑗3𝜋 + 4𝑒 𝑗9𝜋/2
4

1 1 1 1
= 1 + 2 −𝑗 + 3 −1 + 4 𝑗 = −2 + 𝑗2 = − + 𝑗
4 4 2 2
5 1 1 1 1 1
𝑥 𝑛 = ,− − 𝑗 ,− ,− + 𝑗
2 2 2 2 2 2
 Properties of the DFT

1. Periodicity
If X(k) is an N-point DFT of x(n),then

x(n+N)=x(n) for all n

X(k+N)=X(k) for all k

2.Linearity
If X1 (k) and X2 (k) are an N-point DFTs of x1 (n) and x2 (n)
respectively, and a and b are arbitrary constants either real or complex-
valued ,then

𝐷𝐹𝑇
a x1 (n) +bx2 (n) a X1 (k)+bX2 (k)
3.Shifting Property
Let 𝑥𝑝 (n)is a periodic sequence with period N, which is obtained by extending
x(n)periodically,
∞

𝑥𝑝 𝑛 = ෍ 𝑥(𝑛 − 𝐼𝑁)
𝑙=−∞

Now ,Shift he sequence 𝑥𝑝 (n)by k units to the right. Let the resultant signal be
expressed as
∞

X′p (n)=𝑥𝑝 (n−k)= ෍ 𝑥(𝑛 − 𝑘 − 𝐼𝑁)

𝑙=−∞
The finite duration sequence
𝑥′ (n) 𝑥 ≤𝑛 ≤𝑁−1
X′ (n)= ቊ 𝑝
0, 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒
Can be obtained from x(n) by circular shift.
the circular shift of a sequence can be represent by the index modulo N
X′ (n)= x (n-k,(mod N))
4.Convolution Theorem
DFT
If x1(n) X1(k)
DFT
And x2(n) X2(k)
DFT
Then x (n) = x1(n)* x2(n) X (k) = X1(k) X2(k)
Proof –We know that the convolution formula is
∞

x (n)= x1(n)∗ x2(n) = ෍ x1(k) x2(n − k)

𝑛=−∞
Multiplying both sides of this equation by 𝑒 −𝑗2𝜋𝑘𝑛/𝑁 and summing over all n, we get
∞ ∞ ∞
𝑗2𝜋𝑘𝑛 𝑗2𝜋𝑘𝑛
− 𝑁 −
X (k)= ෍ x(n) 𝑒 = ෍ ෍ x1(k) x2(n − k) 𝑒 𝑁
𝑛=−∞ 𝑛=−∞ 𝑛=−∞
= X1(k) X2(k)

Hence, if two signals are converted in the time domain, then it is equivalent to
multiplying their spectra in the frequency domain.
5. Time Reversal of a sequence
DFT
If x(n) X(k), then
N
DFT
x(-n,(mod N))=x(N-n) ) X(-k,(mod N))=X(N-k)
N
Hence, when the N-point sequence in time is reversed, it is equivalent to reversing
the DFT values.
6.Circular Time Shift
DFT
If x1(n) X1(k), then
N
DFT 𝑗2𝜋𝑘𝑙
−
X(n-l,(mod N)) X k 𝑒 𝑁

N
Shifting of the sequence by l units in the time-domain is equivalent to
𝑗2𝜋𝑘𝑙
multiplication of 𝑒− 𝑁 in the frequency domain.
7.Circular Frequency Shift
DFT
If x(n) X(k), then
N
 𝑗2𝜋𝑙𝑛 DFT
x n 𝑒 𝑁 X(k-l,(mod N))
N
8.Complex Conjugate Property
DFT
If x(n) X(k), then
N
DFT
x*(n) X*(-k,(mod N)) =X*(N-k)
N
∗
𝑁−1 𝑁−1
IDFT 1 ∗ 𝑗2𝜋𝑘𝑛/𝑁
1
X∗(k) ෍ 𝑋 (k)𝑒 = ෍ 𝑋(𝑘)𝑒 −𝑗2𝜋𝑘(𝑁−𝑛)/𝑛
𝑁 𝑁
𝑘=0 𝑘=0
Hence,
DFT
𝑥 ∗ (-n,(mod N))=𝑥 ∗ (N-n) X*(k)
| N
9.Circular Convolution
DFT DFT
If 𝑥1 (n) 𝑋1 (k), and 𝑥2 (n) 𝑋2 (k), then
N N
DFT
𝑥1 𝑛 N 𝑥2 (n) 𝑋1 (k)𝑋2 (k)
N
Where 𝑥1 𝑛 N 𝑥2 (n) denotes the circular convolution of the sequence
𝑥1 𝑛 𝑎𝑛𝑑 𝑥2 (n) defined as
 N−1

x3 n = ෍ x1 (m)x2 (n − m, mod N )
m=0
N−1

= ෍ x2 (m)x1 (n − m, mod N )
m=0
10.Circular Correlation
For complex- valued sequences x(n)and y(n),
DFT DFT
If x(n) N X(k), and y(n) N Y(k), then
DFT
𝑟𝑥𝑦 (l) 𝑅𝑥𝑦 (k)=X(k)Y*(k)
N

Where𝑟𝑥𝑦 (l) is the (unnormalised) circular cross- correlation sequence,

𝑁−1

𝑟𝑥𝑦 (l) = ෍ 𝑥 𝑛 𝑦 ∗ (𝑛 − 1, 𝑚𝑜𝑑 𝑁 )

𝑛=0
11.Multiplication of two sequences

DFT DFT
If 𝑥1 (n) N 𝑋1 (k), and 𝑥2 (n) N
𝑋2 (k), then

DFT 1
𝑥1 (𝑛)𝑥2 (n) 𝑋 (k)
N 𝑁 1 N 𝑋2 (k)
12.Parseval’s Theorem
For complex-valued sequences x(n) and y(n),
DFT DFT
If x(n) X(k), and y(n) Y(k), then
N N

𝑁−1 𝑁−1
1
෍𝑥 𝑛 𝑦∗ 𝑛 = ෍ 𝑋 𝑘 𝑌 ∗ (𝑘)
𝑁
𝑛=0 𝑘=0
If y(n)=x(n), then the above equation reduces to
𝑁−1 𝑁−1
2
1 2
෍ 𝑥(𝑛) = ෍ 𝑋(𝑘)
𝑁
𝑛=0 𝑘=0
This expression relates the energy in the finite duration sequence x(n) to the
power in the frequency components X(k).
 Circular Convolution (Periodic Convolution)
Consider the two sequences 𝑥1 (𝑛) and 𝑥2 (n) which are of finite duration. Let
𝑋1 (k) and 𝑋2 (k) be the N-point DFTs of the sequences respectively and they are
given by
N−1
2𝑗𝜋𝑛𝑘
−
𝑋1 𝑘 = ෍ 𝑥1 𝑛 𝑒 𝑁 , 𝑘 = 0,1, … … 𝑁 − 1,
n=0

N−1
2𝑗𝜋𝑛𝑘
−
𝑋2 𝑘 = ෍ 𝑥2 (𝑛)𝑒 𝑁 , 𝑘 = 0,1, … … 𝑁 − 1,
n=0

Let 𝑋3 (n) be another sequence of length N and its N-point DFT be 𝑋3 (k)
which is a product of 𝑋1 (k) and 𝑋2 (k),

𝑋3 𝑘 = 𝑋1 (𝑘)𝑋2 (k),k=0,1,…..N-1.
The sequence 𝑥3 (𝑛) can be obtained by taking the inverse DFT of 𝑋3 (𝑘),
𝑥3 (𝑚)= IDFT[𝑋3 (𝑘)]
N−1 N−1
1 2𝑗𝜋𝑚𝑘 1 2𝑗𝜋𝑚𝑘
= ෍ 𝑋3 (𝑘)𝑒 𝑁 = ෍ 𝑋1 (𝑘)𝑋2 𝑘 𝑒 𝑁
𝑁 𝑁
k=0 k=0

N−1 N−1 N−1

1 −2𝑗𝜋𝑛𝑘 −2𝑗𝜋𝑙𝑘 𝑗2𝜋𝑚𝑘
= ෍ ෍ 𝑥1 (𝑛)𝑒 𝑁 ෍ 𝑥2 (𝑙)𝑒 𝑁 𝑒 𝑁
𝑁
k=0 n=0 𝑙=0

N−1 N−1 N−1

1 𝑗2𝜋𝑘(𝑚−𝑛−𝑙)
= ෍ 𝑥1 (𝑛) ෍ 𝑥2 (𝑙) ෍ 𝑒 𝑁
𝑁
k=0 l=0 l=0

Consider the term within the brackets: it has the form

N−1 𝑁, 𝑓𝑜𝑟 𝑎 = 1
෍ 𝑎 𝑘 = ൞1 − 𝑎 𝑁
, 𝑓𝑜𝑟 𝑎 ≠ 1
k=0 1−𝑎
 𝑗2𝜋(𝑚−𝑛−𝑙)
Where, a=𝑒 𝑁 ,when (𝑚 − 𝑛 − 𝑙) is a multiple of N. then a = 1, otherwise
𝑎𝑁 =1 for any value of a ≠ 0.
Therefore,
N−1
𝑁, 𝑙 = 𝑚 − 𝑛 + 𝑝𝑁, 𝑁 = 𝑚 − 𝑛 𝑚𝑜𝑑 𝑁 , 𝑝: 𝑖𝑛𝑡𝑒𝑔𝑒𝑟)
෍ 𝑎𝑘 = ቊ
0, 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒
k=0
𝑥3 𝑚 𝑏𝑒𝑐𝑜𝑚𝑒𝑠
N−1

𝑥3 𝑚 = ෍ 𝑥1 𝑛 𝑥2 𝑚 − 𝑛, 𝑚𝑜𝑑 𝑁 , 𝑚 = 0,1, … … . , 𝑁 − 1
k=0
, where 𝑥2 𝑚 − 𝑛, 𝑚𝑜𝑑 𝑁 is the reflected and circularly shifted version of 𝑥2 (𝑚)
and n represents the number of indices that the sequence x(n) is shifted to the right.
The above equation has a form similar to the convolution sum and it is
called circular convolution The circularly shifted versions of x(m) are
given below:
x(m) =[x(0),x(1)…x(N-3),x(N-2),x(N-1)]

x(m-1,(mod N))=[ x(N-1),x(0),x(1)…x(N-3),x(N-2)]

x(m-2,(mod N))=[ x(N-2),x(N-1),x(0),x(1)…x(N-3)]

.
.
.
x(m-n,(mod N))=[ x(N-n),x(N-n+1)..…x(N-n-1)]
.
.
.
x(m-N,(mod N))=[ x(0),x(1)..…x(N-3),x(N-2),x(N-1)]

It just noted that a shift of n=N results in the original signal x(m).
Matrix Multiplication Method

The circular convolution of two sequences x(n) and h(n) can be obtained by representing these
sequences in the matrix form as given below.

𝑥 0𝑥 𝑁−1 𝑥 𝑁 − 2 ….𝑥 2 𝑥 1 ℎ 0 𝑦 0
𝑥 1 𝑥 0 𝑥 𝑁 − 1 ……𝑥 2 𝑥 2 ℎ 1 𝑦(1)
𝑥 2𝑥 1 𝑥 0 ……………𝑥 4 𝑥 3 ℎ 2 𝑦(2)
….. . .
=
…… . .
…… . .
𝑥 𝑁−2 𝑥 𝑁−3 𝑥 𝑁 − 4 ….𝑥 0 𝑥 𝑁 − 1 ℎ 𝑁−2 𝑦 𝑁−2
𝑥 𝑁−1 𝑥 𝑁−2 𝑥 𝑁 − 3 ….𝑥 1 𝑥(0) ℎ 𝑁−1 𝑦(𝑁 − 1)

The sequence x(n) is repeated via circular path shift of samples and represented in
N×N matrix form. The sequence h(n) is represented as column matrix. The
multiplication of these two matrices gives the sequence y(n).
Linear Convolution vs Circular Convolution

Consider a finite duration sequence x(n) of length 𝑁1 which is given a input to an FIR
system with impulse response h(n) of length 𝑁2 . then the output is given by
y(n)=x(n)*h(n)

𝑁1 −1

= ෍ 𝑥 𝑘 ℎ 𝑛 − 𝑘 , 𝑛 = 0,1, … … . , 𝑁1 + 𝑁2 − 1
k=0
or
𝑁1 −1

Y(n)= ෍ 𝑥 𝑘 ℎ 𝑛 − 𝑘 , 𝑛 = 0,1, … … . , 𝑁1 + 𝑁2 − 1
k=0

where, x(n) = 0,n<0 and n≥𝑁1

h(n) = 0,n<0 and n≥𝑁2

In the frequency-domain,
Y(ꙍ)=H(ꙍ)X(ꙍ)
If the sequence y(n) has to be represented uniquely in the frequency domain by
samples of its spectrum Y(ꙍ) then

Y(k)= Y(ꙍ)│ꙍ=2nk/N, K=0,1…..N-1

= X(ꙍ)H(ꙍ)│ꙍ=2nk/N, K=0,1…..N-1
Y(k)=X(k)H(k)

where X(k) and H(k) are the N-point DFTs of the sequence x(n) and h(n) respectively.
Since y(n) can be obtained by
Y(n)=IDFT X(k) H(k)
The N-point circular convolution of x(n) with h(n) must be equivalent to the linear
convolution of x(n) with h(n).
➢ Linear convolution of two sequences and x(n) and h(n) with lengths N1 and N2
respectively will give a sequence with a length of N≥N1+N2- 1
➢ When x(n) and h(n) have a duration less than N, for implementing linear
convolution using circle convolution N1- 1 and N2-1 zeros are padded (added) at
the end of x(n) and h(n) in respectively to increase their length to N.
Example
1,0 ≤ 𝑛 ≤ 𝑁 − 1
Let x1(n)=x2(n)=ቊ
0, 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒
Find out the circular convolution of this sequence.

Solution:

➢ Here x1(n) and x2(n) are the given N-point sequences.

➢ The circular convolution of x1(n) and x2(n) yields another N-point sequences x3(n).
➢ (N×N) matrix is formed using one of the sequences and another sequences is
arranged as an (N × 1) column matrix.
➢ The product of these two matrices gives the resultant sequences x3(n) as shown
below.
 Using matrix approach, we can formulate circular convolution as

𝑥1 0 𝑥1 𝑁 − 1 𝑥1 𝑁 − 2 … . 𝑥1 1 𝑥2 0 𝑥3 0
𝑥1 1 𝑥1 0 𝑥1 𝑁 − 1 … 𝑥1 1 𝑥2 1 𝑥3 (1)
…… . .
….. . .
=
…… . .
…… . .
𝑥1 𝑁 − 2 𝑥1 𝑁 − 3 𝑥1 𝑁 − 4 … 𝑥1 𝑁 − 1 𝑥2 𝑁 − 2 𝑥3 𝑁 − 2
𝑥1 𝑁 − 1 𝑥1 𝑁 − 2 𝑥1 𝑁 − 3 … 𝑥1 (0) 𝑥2 𝑁 − 1 𝑥3 (𝑁 − 1)
For the given sequences, the circular convolution x3(n) is determined by
1 1 1 . . . .1 1 𝑁
1 1 1 . . . .1 1 𝑁
. . . . . . . . .
. . . . . . . . .
=
. . . . . . . . .
. . . . . . . . .
1 1 1 . . . .1 1 𝑁
1 1 1 . . . .1 1 𝑁
Hence, x3(n) = (N,N… N,N)
Example: Compute (a) linear and (b)
circular periodic convolutions of the two
sequences x1 (n) ={1, 1,2,2} and
x2(n)={1,2,3,4}. (c) Also find circular
convolution using the DFT and IDFT.

Solution:

(a)Using matrix representation given as follows, the linear convolution of the two
sequences can be determined.
Hence, x3(n) = x1(n)*x2(n) ={1,3,7,13,14,14,8}
(b)Similarly, circular convolution of the two sequences is shown in Fig. E6, 15.
 N−1

𝑥3 𝑚 = ෍ 𝑥1 𝑛 𝑥2 𝑚 − 𝑛, 𝑚𝑜𝑑 𝑁 , 𝑚 = 0,1, … … . , 𝑁 − 1
n=0

For m=0
3

𝑥3 0 = ෍ 𝑥1 𝑛 𝑥2 −𝑛, 𝑚𝑜𝑑 4
𝑛=0

𝑥2 −𝑛, 𝑚𝑜𝑑 4 𝑖𝑠 the sequence x2(n) folded. The folded sequence is obtained by
plotting x2(n) in a clockwise direction.

𝑥2 0, 𝑚𝑜𝑑 4 = x2(0)
𝑥2 −1, 𝑚𝑜𝑑 4 = x2(3)
𝑥2 −2, 𝑚𝑜𝑑 4 = x2(2)
𝑥2 −3, 𝑚𝑜𝑑 4 = x2(1)
x3(0) is obtained by computing the product sequence, i.e. multiplying the sequences
x1(n) and x2(- n, (mod 4)), point by point and taking the sum, we get x3(0)= 15.
For m=1:
3

𝑥3 1 = ෍ 𝑥1 𝑛 𝑥2 1 − 𝑛, 𝑚𝑜𝑑 4
n=0

x2(1-n, (mod 4)) is the sequence 𝑥2 (-n ,(mod 4)) rotated counterclockwise by one unit
in time. From the product sequence, the sum is x3(1) = 17.
For m=2:
3

𝑥3 2 = ෍ 𝑥1 𝑛 𝑥2 2 − 𝑛, 𝑚𝑜𝑑 4
n=0

x2(2- n, (mod 4)) is the sequence x2(-n, (mod 4)) rotated counterclockwise by two units
in time. From the product sequence, the sum is x3(2) = 15.
For m= 3:
3

𝑥3 3 = ෍ 𝑥1 𝑛 𝑥2 3 − 𝑛, 𝑚𝑜𝑑 4
n=0
x(3- n,(mod 4)) is the sequence x2(- n, (mod 4)) rotated counterclockwise by three units
in time, From the product sequence, the sum is x3(3) = 13.
Hence, the circular convolution of the two sequences x1(n) and x2(n) is
x3(n)= {15,17,15,13}
(c) Here the DFT and IDFT are used for finding circular convolution
X3(k)= X1(k) X2 (k)
And
N−1
1 2𝑗𝜋𝑘
x3(n) = ෍ 𝑋3 𝑘 𝑒 𝑁 , n=0,1,….,N−1
𝑁
k=0
(i)When x1(n) = [1, 1, 2, 2]
N−1
−2𝑗𝜋𝑛𝑘
X1(k) = ෍ 𝑥1 (𝑛)𝑒 𝑁 , k=0,1,….,N−1
n=0
For N=4
3
−2𝑗𝜋𝑛𝑘
X1(k) = ෍ 𝑥1 (𝑛)𝑒 4 , k=0,1,23
n=0
For k=0
3
−2𝑗𝜋𝑛 0
X1(0) = ෍ 𝑥1 𝑛 𝑒 4 =6
n=0
For k=1
3
−𝑗𝜋𝑛
X1(1) = ෍ 𝑥1 (𝑛)𝑒 2
n=0
 −𝑗𝜋 −𝑗3𝜋
=1+𝑒 2 +2𝑒 −𝑗𝜋 + 2𝑒 2 = 1- j+2(-1) + 2(j)= -1 + j
For k=2
3

X1(2) = ෍ 𝑥1 (𝑛)𝑒 −𝑗𝑛𝜋

n=0
= 1+ 𝑒 −𝑗𝜋 +2𝑒 −2𝜋 + 2𝑒 −𝑗3𝜋 =1 - 1 + 2 (1) + 2 (-1)=0
For k=3
3

X1(1) = ෍ 𝑥1 𝑛 𝑒 −𝑗3𝑛𝜋/2
n=0
= 1+ 𝑒 −𝑗3𝜋/2 + 2𝑒 −𝑗3𝜋 + 2𝑒 −𝑗𝑛/2 = 1+ j+2 (-1) – j (2) = -1- j
𝑋1 𝑘 = {6, −1 + 𝑗, 0, −1 − 𝑗}
(ii) When x2(n) = {1, 2, 3,4}

Here, N=4. Therefore,

3
−2𝑗𝜋𝑛𝑘
X2(k) = ෍ 𝑥2 (𝑛)𝑒 4 , k=0,1,2,3
n=0
For k=0
3
−2𝑗𝜋𝑛 0
X2(0) = ෍ 𝑥2 𝑛 𝑒 4 = 10
n=0
For k=1
3
−𝑗𝜋𝑛
𝑋2 (1) = ෍ 𝑥2 (𝑛)𝑒 2
n=0
−𝑗𝜋 −𝑗3𝜋
=1+ 2𝑒 2 + 3𝑒 −𝑗𝜋 + 4𝑒 2 =1 + 2 (-j)+ 3 (-1) + 4(j) = -2 + j2
For k=2
3

X2(2) = ෍ 𝑥2 (𝑛)𝑒 −𝑗𝑛𝜋

n=0
= 1 + 2𝑒 −𝑗𝜋 + 3𝑒 −𝑗𝜋
+ 4𝑒 −𝑗3𝜋 = 1+ 2(-1) + 3(1) + 4(-1)= -2
For k=3
3
3𝜋
−𝑗 𝑛
𝑋2 (3) = ෍ 𝑥2 𝑛 𝑒 2
n=0
= 1+2𝑒 −𝑗3𝜋/2 +3𝑒 −𝑗3𝜋
+ 4𝑒 −𝑗9𝜋/2 = 1+2(j)+3(-1)+4(-j) = -2-2j
X2(k)={10,-2+2j, -2, -2 -2j}
 X3(k) = X1(k) X2 (k)
={60,(-1+ j) (-2 + 2j), 0 , ( -1- j) (-2 - 2j)} = {60, -4j, 0, 4j}
We know that x3(n)=IDFT[𝑋3 (k)]
Hence,
3
1 2𝑗𝜋𝑛𝑘
x3(n) = ෍ 𝑥3 (𝑘)𝑒 4 , n=0,1,2,3
4
k=0
1
= 60 + −4𝑗 𝑒 𝑗𝜋𝑛/2 + 4𝑗 𝑒 𝑗3𝜋𝑛/2
4

1
x3(0) = 60 + −4𝑗 + (4𝑗) = 15
4

1 1
x3(1) = 60 − 4𝑗𝑒 𝑗𝜋/2 + 4𝑗 𝑒 𝑗3𝜋/2 == 60 − 4𝑗(+𝑗) + 4𝑗 −𝑗
4 4
1
= 60 + 4 + 4 =17
4

1
x3(2) = 60 − 4𝑗𝑒 𝑗𝜋 + 4𝑗 𝑒 𝑗3𝜋
4
1
= 60 − 4𝑗(−1) + 4𝑗 −1 =15
4
 1
X3(3) = 60 − (4𝑗)𝑒 𝑗3𝜋/2 + 4𝑗 𝑒 𝑗9𝜋/2
4
1
= 60 + 4𝑗(−4𝑗)(−𝑗) + 4𝑗 −𝑗
4
1
= 60 − 4 − 4 =13
4

Therefore, x3 (n) = {15,17,15,13}

 FAST FOURIER TRANSFORM
The fast fourier transform (FFT) is an algorithm that efficiently computes the discrete
fourier transform (DFT). The DFT of a sequence {(x(n)} of length N is given by a
complex-valued sequence {X(k)}

let WN be the complex-valued phase factor, which is an Nth root of unity expressed by
WN=

Hence X(k) becomes

Similarly, IDFT becomes

If x(n) is a complex-valued sequence, then the N-point DFT given in Eq. (1)
can be expressed as

Equating the real and imaginary parts of the above equation

Symmetry Property WNk+N/2 = -WkN

Periodicity Property WNk+N =WkN

Radix-2 FFT

By adopting a divide and conquer approach, a computationally efficient

algorithm for the DFT can be developed. This approach depends on the
decomposition of an N-point DFT into successively smaller size DFTS. If N
is factored as N =r1 r2 r3 .rLt where r1= r2 = .=rL =r ,then N= rL. Hence,
the DFT will be of where this number is called the radix of the
FFT algorithm.
the most widely used radix-2 FFT algorithms are described. FFT algorithms
take advantage of the periodcity and symmetry of the complex number

WN nk =
 Decimation-in-Time(DIT) Algorithm
In this case, let us assume that x(n) represents a sequence of N values, where N is an
integer power of 2, that is, N= , The given sequence is decimated (broken) into two
N-point sequence consisting of the even numbered values of x(n) and the odd
numbered values of x(n).

The N-point DFT of sequence x(n) is given by

Breaking x(n) into its even and odd numbered values, we obtain

Substituting n=2r for n even and n= 2r +1 for n odd, we have

Here, =

Therefore, can be written as Eq.(2)

=G(k)+
where G(k) and H(k) are the N/2-point DFTs of the even and odd numbered
sequences respectively.
-1 since G(K) and H(k) are considered
period with period N/2.
Therefore,
Using the symmetry property of =-

Figure 1 shows the flow graph of the decimation-in-time decomposition of an

8-point (N = 8) DFT computation into two 4-point DFT computations.
 Figure:1 Flow graph of the second Stage Decimation-in-time FFT Algorithm for N=8

X(0) is obtained by multiplying H(0) by and adding the product to G(0). X(1) is
obtained y multiplying H(1) by and adding that result to G(1). For X(4),H(4) is
multiplied by and the result is added to G(4). But, since G(k) and H(k) are both
periodic in k with period 4,H(4)=H(0) and G(4) = G (0). Therefore, X(4) is obtained by
multiplying H(0) by and adding the result to G(0).
 G(k)=A(k)+ B(k)
Where A(k)is the (N/4)-point DFT of even numbers ,B(k)is the (N/4)-point DFT of odd numbers

H(k)=C(k)+ D(K)
Figure:2 Flow Graph of second Decimation in time FFT algorithm for
N=8
We get
For k=0, G(0)= A(0) +
For k=1, G(1)= A(1) +
For k=2, G(2)= A(2) +
For k=3, G(3)= A(3) +

In the above equations, since and

A(0)=A(2) and A(1)=A(3)
B(0)=B(2) and B(1)=A(3)
Similarly,
H(0)
H(1)=
H(2)=
H(3)=

The above process, of reducing an L-point DFT (L is a power of 2) to an L/2 point

DFTs, can be continued until we are left with 2-point DFTs,or there are
L(=
A 2- point DFT ,F(k), k=0,1 may be evaluated as,

F(0)=f (0) + f(1)

F(1)=f (0) + f(1)

f(n), n= 0,1 is a 2-point sequence.

=1,

Therefore,
F(0)=f (0) + f(1) =f (0) + f(1)
F(1)=f (0) + f(1) =f (0) - f(1)
The corresponding flow graph of a 2-point DFT is shown in above Figure 3.

Figure: 3 Flow Graph of a 2- point DFT

Figure: 4 The Flow-Graph of the decimation-in-time FFT Algorithm for N=8

Figure: 5 Basic Butterfly Flow Graph for the

Table:1
computation in the DIT FFT Algorithm
Figure: 6 Reduced Flow- Graph for an 8-Point DIT FFT
Example. Given x(n)={1,2,3,4,4,3,2,1},find X(k)using DIT FFT algorithm.
Solution:

we know that

Using DIT FFT algorithm, we can find X(k) from the given sequence x(n)as shown
figure

Therefore, X(k)={ 20,-5.828- j 2.414 , 0 , 0.172 j 0.414 , 0 , -0.172 + j 0.414 , 0 , -

5.828 + j 2.414 }
Figure :7 X(k) from the given sequence x(n)
 Decimation in frequency algorithms

To derive into the decimation-in-frequency FFT algorithm for N , a power of 2, the

input sequence x(n) is divided into the first half and the last half of the points as
discussed below.
 Since, =cos(

Decomposing the sequence in the frequency domain , X(k), into an even numbered
subsequence X(2r) and an odd numbered subsequence X(2r + 1) where
r=0,1,2, ..(N/2 -1),yields
 = ] (3)

From Eq. (3),

From Eq. (4),

 For an 8-point DFT N=8,

g(0)=x(0)+x(4) h(0)=x(0)-x(4)
g(1)=x(1)+x(5) h(1)=x(1)-x(5)
g(2)=x(2)+x(6) h(2)=x(2)-x(6)
g(3)=x(3)+x(7) h(3)=x(3)-x(7)

The flow graph of the first stage of an 8 point DFT computation scheme defined by
Eqs(3)and (4) is shown in Fig.1

Equation (3) is
Therefore,

Substituting the identity = -1in the above equation, we get

When r =2l (even)

When r = 2l + 1(odd),
 Figuar:1 Flow Graph of the First Stage of Decimation-in-Frequency
FFT for N=8
Where B(n)=g(n)
Figure 6.9 shows the flow-graph of the second stage of decimation in frequency
decomposition of an 8-point DFT into four 2-point DFT computations.

Figure :2 Flow Graph of the second Stage of decimation in-frequency FFT

foe N=8
The above decomposition process can be continued through decimation of the N/2-
point DFTs X(2r) and X(2r+1).The complete process consists of L=
where each stage involves N/2 butterflies of the tye shown in
Fig. 6.10.These butterflies are different form those in the decimation-in-time algorithm.
As a result, for computing the N-point DFT down to 2-point transforms, the DIF FFT
algorithm requires (n/2)log2 N complex multiplications and N log 2N complex
additions, just as in the case of radix-2 DIT FFT algorithm ii Fig.6.11.
It is observed from Fig. 6.11 that in the DIF FFT algorithm the input sequence x(n)
appears in natural order while the output X(k) appears in the bit-reversed order. The
algorithm has in place calculations given below with the butterfly structure shown in
Fig 6.10.

Figure : 3 Basic butterfly for DIF FFT

 Figure: 4 Reduced Flow Graph of Final Stage DIF FFT for N=8

A= a + b
B=(a b )
Example : Given x(n)={1,2,3,4,4,3,2,1}, find X(k) using DIF FFT
algorithm.

Solution: Given N=8.

We know tha

Hence,

Using DIF FFT algorithm, we can find X(k) from the given sequence x(n) as
shown in Fig

Hence , X(k)={20,-5.828-j 2.414,0, -0.172- j0.414,0, -0.172+j0.414, 0, -

5.828+j2.414}
Fig :X(k) from the given sequence x(n)
 Extension to General Intervals of Definition

Take the case of a sequence defined on a different interval:

How do we compute the DFT, without reinventing a new formula?

 First see the periodic extension, which looks like this:

Then look at the period

Example: determine the DFT of the finite sequence

Then take the DFT of the vector

Q1. Derive the DFT of the sample data sequence x(n)={1, 1, 2, 2, 3, 3} and
compute the corresponding amplitude and phase spectrum.
Q2. Determine the IDFT of X(k) = {3, (2 + j), 1, (2 j)}.
Q3. Compute
and

Given that N=5.

=1 =0

=-1 =-1

=1 =1

=-1 =0

=0 =1
 =1 =1

=-1 =0

=1 =1

=-1 =-1
Folded sequence
=0 =0

=1
=1
=1
=-1

=0
=1

=-1 =0

Folded sequence
=0 =-1
rotated by one
unit in time
 =0
=1

=-1 =1

=1 =-1

=-1 =1
Folded sequence
rotated by two
=0 =0 unit in time

=1 =-1

=-1
=0

=1
=0

=-1
=1
Folded sequence
=0 rotated by three
=1
unit in time
 =1 =0

=-1
=-1

=1
=1

=-1
=0

=0 Folded sequence
=1
rotated by four
unit in time

Therefore,