Architecture for Signal

Processing Algorithms

Dr. Mrs. A. M. Deshpande

Department of E&Tc Engg.,
CCOEW, Pune
01/13/16 1
Module I
Course Prerequisites
DSP Computations
DSP System Design Objective
Main Challenge in Design
Typical DSP Algorithms

Review of DSP algorithms: Discrete Fourier Transform, properties of DFT,

Decimation in time and decimation in frequency FFT
2-D DFT and its applications
Linear filtering using DFT- overlap and save & overlap and add algorithms
Goertzel algorithm

01/13/16 2
Course Prerequisites

In depth knowledge of Digital Design

Knowledge of DSP

Knowledge of VLSI Design

01/13/16 3
DSP Computations

DSP computations are different from

general purpose computation in the
sense that the DSP programs are non
terminating programs.

In DSP computation the same program

is executed repetitively on an infinite time
series

01/13/16 4
DSP System Design Objective

Design more efficient DSP system by

exploiting the dependency of tasks both
within an iteration and among multiple
iterations

Transform the DSP algorithms for design

of high speed or low power
implementation

01/13/16 5
Main Challenge in Design

Long critical paths in DSP algorithms

limit the performance of DSP system

01/13/16 6
Architectural Transformations

Pipelining
Retiming
Folding
Unfolding
Systolic

01/13/16 7
Algorithm Transformations

Strength reduction
Look ahead
Relaxed look ahead

For example, strength reduction

transformations are applied to reduce
number of multiplications in convolution,
DCT and digital filters.

01/13/16 8
Terms used…and already known to
you……
Correlation
Convolution
Digital filters
DCT
Quantization
Viterbi Algorithm

01/13/16 9
Typical DSP Algorithms
DSP Algorithm System Applications
Speech Coding and Digital cellular phones, cordless phones,
decoding multimedia computers
Speech Recognition User interfaces, Automotive applications,
Digital cellular phones
Modem Algorithms Digital cellular phones, personal
communication system, Wireless, facsimile,
multimedia computers
Noise cancellation Professional audio, Advanced vehicular
audio
Image Compression Digital cameras, Digital video, multimedia
and Decompression
Beam forming Navigation, Radar, Signal intelligence

01/13/16 10
Scaled CMOS technology & DSP applications
(will be discussed in detail in Module-2)

 The design of complex DSP systems has been

possible due to the advances in scaled VLSI
technologies.
 It is predicted that CMOS technology will go down to
0.07 um- with corresponding improvements in density
and speed.
 The number of transistors on single chip :- Reached to
a value of 90M
 A chip from NEC that contains 3.7M transistors has a
peak performance of 12 Giga-operations per sec. (For
MPEG-2 motion estimation---DSP Application)

01/13/16 11
Discrete Fourier Transform
The DFT provides uniformly spaced samples of the Discrete-
Time Fourier Transform (DTFT).

Discrete Fourier transform (DFT) of a discrete-time signal x[n]

with finite extent n  [0, N-1]
 
N1 
2nk N
1 
2nk
1
 
j j
X
[
k]x[
n]
e N
x
[n
] X[
k]eN

n0 N
n0
Twiddle factor:
Discrete Fourier Transform
Let N-point vector xN of the signal sequence x(n) , n = 0, 1, 2, ….(N-1)
and N-point vector XN of frequency samples and NxN matrix WN as
Discrete Fourier Transform

With these definitions, the N-point DFT

may be expressed in matrix form as,

The inverse DFT

OR

Where IN is an NxN identity matrix.

Discrete Fourier Transform
Example:
Compute the DFT of the 4-point sequence

then
Discrete Fourier Transform
Example:
Determine Discrete Fourier Transform (DFT) of the following sequence:

x[n] = an u [n] a 1


X
[
k
]
x
(


nT
)
e 
au
(
n
)
e
 
j
2
k
n
N

j
2
k
n
n N




n 

n


X
[
k
]a
e

(
ae)
k 

j
2
nN
n 2
k

j
N n


n
0 
n
0


1
X
[
k
]2 k
N k = 0 , 1 , 2 , 3 , …..…, N-1
j
1
ae
Discrete Fourier Transform
Example:






X
[
k
]
x
(
n
)
e
a
u
(
n
3
)
e



X
[
k
]a
e

X
[
k
]


(


3
a
2

1


ae
)

j
6
e

j
ae

(

ae


k

k
N
)




n
n



n
3


n
n


j
2
k
j
2
k
n
N
N



j
n
n
2
k
NN
2
k

j 
12
k

j
n Nn


Determine Discrete Fourier Transform (DFT) of the following sequence:

x[n] = anu [n+3]


n
0
a 1

 k = 0 , 1 , 2 , 3 , …………, N-1


n
3
Discrete Fourier Transform

Periodicity:
If x(n) and X(k) are N-point DFT pairs

Linearity:
Discrete Fourier Transform

Circular Convolution:
Discrete Fourier Transform
Multiplication of 2 DFT sequence:
Suppose we have 2 finite-duration sequences of length N, x1(n) and
x2(n)

Convolution sum called Circular Convolution

DFT Properties and Proofs

Multiplication property

Circular symmetry properties

Discrete Fourier Transform
Understanding circular convolution
Discrete Fourier Transform
Circular Convolution
Example: Perform the circular convolution of the following 2 sequence:

m=0 m=2

= 14 = 14

m=1 m=3

= 16 = 16
Circular Convolution
Circular Convolution
Circular Convolution

Obtain Circular Convolution Result…….

Discrete Fourier Transform
Example:
Using DFT and IDFT determine the sequence x3(n) corresponding to
the circular convolution of the sequences x1(n) and x2(n) given in the
previous example.
Example: (cont.)

N
1 
2nk
1

j
x
[n
] X[
k]eN
N
n0

IDFT 1/4
Fast Fourier Transform
Fast Fourier Transform
 1807-> J.B.J. Fourier- First published Fourier Series
for theory of heat
 1822-> Revised Fourier theory
 1829-> Dirichlet proved Fourier’s claim
 1965-> (Next 150 years) Cooley & Tukey expanded
and generalized the ideas of Fourier and introduced
FFT.
 FFT- King of all transforms, countless number of
applications in Engg., Finance, Engg. Mathematics,
Signal processing etc.
 FFT is what signal processing made possible!!!
Fast Fourier Transform
The DFT is computable transform, the straightforward implementation
is very inefficient, especially when the sequence length N is large.
 FFT decomposes the computation of the DFT of a sequence of length N
into successively smaller DFTs.
 DFT definition:
 N
1 
2nk
2nk 1

N1  j


j
X
[
k]x[
n]
e N x
[n
] X[
k]eN

n0
N
n0

N 1
X [k ]  x[ n ] WN
nk
 X(k)=WNx(n) (WN: N*N, x: 1*N, X: 1*N)
n 0

Requires N2 complex multiplies and N(N-1) complex additions.

Fast Fourier Transform
 Ex. Direct DFT with N=8
 No. of complex Multiplications=?
 No. of complex Additions=?
 Now FFT computations??
 We’ll see later:
 N/2 log2(N) complex multiplications
 N log2(N) complex additions.
 Ex. 2 Million point DFT (N=2,097,152)
 Computing on Desktop computer with DFT takes…..
 Computing with Radix-2 FFT takes only 10 seconds.
Discrete Fourier Transform:
Computational Complexity
N Multiplications Additions
4 16 12
16 256 240
64 4096 4032
256 65536 65280

1024 1,048,576 1,047,552

Fast Fourier Transform
Faster DFT computation:
Take advantage of the symmetry and periodicity of the complex
exponential (let WN=e-j2π/N)

Symmetry:

Periodicity: CN=N×log2N

For
Multiplication
example:
is reduced by
factor 2
 Note that two length N/2 DFTs take less computation than one length N
DFT: 2(N/2)2<N2
 Algorithms that exploit computational savings are collectively called
Fast Fourier Transforms. The common algorithm is Radix-2 FFT
Fast Fourier Transform
 Efficient algorithms for computing the DFT
 Two different approaches:
 Divide and conquer approach->DFT of size N is
reduced to the computation of smaller DFTs from
which larger DFT is computed
 Decimation in Time (DIT) algorithm
 Decimation in Frequency (DIF) algorithm
 Linear filtering operation
 Goertzel algorithm
 Chirp-Z transform
 FFT makes strategic use of following 2 complex
identities:
Fast Fourier Transform
Symmetry property:

Periodicity property:
Fast Fourier Transform
Cooley-Tukey algorithm:
Based on decimation, leads to a factorization of
computations.
N point DFT: N=rv where r=radix of the FFT
algorithm. e.g. For N=8, v=3 as 8=23 ; where
v=number of stages in FFT algorithm
Let us first look at the classical radix 2 decimation
in time (DIT).
This particular case of the algorithm requires the
time sequence length to be a power of 2.
First we split the computation between odd and
even samples:
 Fast Fourier Transform
Derivation: Assume N is even and power of two
Derivation of the Radix-2 DIT FFT Algorithm (covered on board)

Substitute n = 2r for n even and n = 2r+1 for odd

Using the property

where G[k] & H[k] are N/2

point DFTs
 As G(k) and H(k) are periodic with period N/2,

Using the property,

Fast Fourier Transform
First Stage of Decimation: Flow graph of N-point DFT
computation into two (N/2)-point DFT computation. (N = 8)

Repeat same process:

- Divide N/2-point DFTs into Two N/4-point DFTs
- Combine outputs
Fast Fourier Transform
Further break down: Second Stage of Decimation
Second Stage: Four N/4-point DFTs
Fast Fourier Transform
Third stage: Two-Point DFT
- The N/4 point sequences are further splitted in their even & odd parts

1
X
(
k
)
x
(
n
)W
2
nk
k
0
,
1

n
0
1 1
X
(
0
)x (n
)
W
2
n
0
 x(
n
) x(
0
)
x(
1
)
n
0 n 0
1 1
X (1)  2  x ( n )W
n1
2
n
  x ( n )W  x ( 0 )W 2 0  x (1)W 2 1
n0 n0

 x ( 0 )  x (1)W 2 (1 / 2 ) 2  x ( 0 )  x (1)( 1)  x ( 0 )  x (1)


X
[
0
]x
[
0
]
x
[1
]

X
[
1
]x
[
0
]
x
[1
]

Flow graph of 2-point FFT

Fast Fourier Transform
Flow graph/ Butterfly diagram of the 8-point FFT algorithm using
decimation-in-time
Butterfly computation
a A=a + WrNb

b B=a - WrNb

 A N-point FFT can be decomposed into log2N

stages.
 Each stage has N/2 butterfly cells, each cell
needs 1 multiplication and 2 additions.
 Therefore the computational complexity for a N-
Point FFT is:
(N/2)log2N complex multiplications
2(N/2) log2N complex additions
Comparison of DFT Vs. FFT

Direct DFT Computation FFT Algorithm Speed

improvement
factor

N Complex Complex Complex Complex for Multiplications

Multiplications Additions Multiplications Additions N2
N2 N/2 log2(N)
N(N-1) N log2(N) N/2 log2(N)

8 64 52 12 24 5.3 times

256 65536 65280 1024 2048 64 times

1024 1,048,576 1,047,552 5120 10240 204.8 times

Memory requirement and In-place computation
 Once a butterfly operation is performed on a pair of
complex numbers (a,b) to produce (A,B) there is no need
to save input pair. Hence we can save the result (A,B) in
the same locations as (a,b).
 Since A,B or a,b are complex numbers, they need 2
memory locations each. Thus computation of 1 butterfly
requires 4 memory locations.
 If N=2r, we have r=log2(N) stages. For each one we have
N/2 butterflies. (i.e., 4 for N=8)
 Therefore number of memory locations required for one
stage=4xN/2=2N and the stages are computed
successively.
 Thus total 2N locations are required to compute N-point
FFT.
 In such computations A is stored in place of a & B is
stored in place of b, therefore this is called as ‘in-place
computation’.
Input index Bit reversal for an 8-point FFT
At each step of the algorithm, data are split between even and odd values.
This results in scrambling the order.
Fast Fourier Transform- Problems
1:
 IFFT

2:
above
Radix-2 Decimation-In-Frequency (DIF) FFT Algorithm

The DFT equation

N

1

X
k
x
[
n]
Wnk
N
n

0
N

1 N/
2
1 N

1

X
2
r
x
[
n
]
W 
x
[
n
]W
n
2
r
x
[
n
]
NW n
2
r
N N
n
2
r

n

0 n
0 n
N
/2

Split the DFT equation into even and odd

frequency indexes
N
/
2

1N /
2

1 N
/
2

1


X
2
r

x[
n
]
W
x
[
n

N
/2
]
W
N

x
[
n
]n
2
r

x
[
n
N

N
/
2
]
Wn
N
/
2

n

N
/
2
2r

n

0 n

0 n

0
Substitute variables to get
N
/
2

1




X
2
r

1

x[
n
]

x
[
n

N
/
2
]
W 

n
2
r

1
N
/
2
n

0
Decimation-In-Frequency (DIF) FFT Algorithm

Final flow graph for 8-point decimation in

frequency
 Example 3:

Solution:

The number
of complex
multiplication
s are:
Example 4:

above
Inv. Fast Fourier Transform using DIF
Inv. Fast Fourier Transform using DIT
Summary

Fast Fourier Transform (FFT)

 To reduce the burden of computing DFT coefficients, the FFT
algorithm is used, which requires the data length to be a power of 2.
Sometimes zero padding is employed to make up the data length.
 Two radix-2 FFT algorithms—decimation-in-time and decimation in-
frequency—are developed via the graphical illustrations.
 FFT algorithm takes advantage of symmetry & periodicity properties
of twiddle factor for reducing computation overhead.
 Computational complexities of DFT and FFT are compared to
understand speed improvement & reduction in computations of DFT
coefficients
 Various terminologies of FFT like butterfly computation, memory
locations, in-place computations and bit reversal are studied.
Summary

• Goertzel Algorithm (On board)

• Overlap add and overlap save method (On board)

• References:
• DSP- by Proakis
• Adv. DSp- by Dr. Apte
• Web resources

01/13/16