2008/4/22

Chapter 5

Finite-Length Discrete
Transforms

cwlin@ee.nthu.edu.tw
03-5731152 4-1-1
Original PowerPoint slides prepared by S. K. Mitra
The McGraw-Hill Companies, Inc., 2007

Digital Fourier Transform

Definition - The simplest relation between a length-N
sequence x[n], defined for 0 n N 1, and its DTFT
X(ej) is obtained by
b uniformly
niforml sampling X(ej) on the -
axis between 0 < 2 at k = 2k/ N, 0 k N 1
From the definition of the DTFT we thus have

0 k N 1

Note: X[k]
[ ] is also a length-N
g sequence
q in the frequency
q y
domain
The sequence X[k] is called the Discrete Fourier
Transform (DFT) of the sequence x[n]

Original PowerPoint slides prepared by S. K. Mitra 4-1-2

The McGraw-Hill Companies, Inc., 2007

1
 2008/4/22

Digital Fourier Transform

Using the notation WN = ej2/N the DFT is usually
expressed as:

The Inverse Discrete Fourier Transform (IDFT) is

given by

To verify the above expression we multiply both sides of

the above equation by and sum the result from n = 0
to n = N 1

Original PowerPoint slides prepared by S. K. Mitra 4-1-3

The McGraw-Hill Companies, Inc., 2007

Digital Fourier Transform

This results in:

Making
g use of the identity
y

we observe the RHS of the last equation is equal to X[l]

Hence
Original PowerPoint slides prepared by S. K. Mitra 4-1-4
The McGraw-Hill Companies, Inc., 2007

2
 2008/4/22

Digital Fourier Transform

Example - Consider the length-N sequence

Its N-point DFT is given by

, 0 k N 1

Example - Consider the length-N sequence

Its N-point DFT is given by

, 0 k N 1
Original PowerPoint slides prepared by S. K. Mitra 4-1-5
The McGraw-Hill Companies, Inc., 2007

Digital Fourier Transform

Example - Consider the length-N sequence defined for
0 n N 1
g[n] = cos(2rn/ N),
N) 0 r N 1
1
Using a trigonometric identity we can write

The N-point DFT of g[n] is thus given by

0 k N 1
Making use of the identity

We get , 0 k N 1
Original PowerPoint slides prepared by S. K. Mitra 4-1-6
The McGraw-Hill Companies, Inc., 2007

3
 2008/4/22

Matrix Relation
The DFT samples defined by

can be expressed in matrix form as

X = DNx
where
X = [X[0] X[1] ..... X[N 1]]T
x = [x[0] x[1] ..... x[N 1]]T
and DN is the N N DFT matrix given by

Original PowerPoint slides prepared by S. K. Mitra 4-1-7

The McGraw-Hill Companies, Inc., 2007

Matrix Relation
Likewise, the IDFT relation given by

can be expressed in matrix form as

where is the IDFT matrix

Note:

Original PowerPoint slides prepared by S. K. Mitra 4-1-8

The McGraw-Hill Companies, Inc., 2007

4
 2008/4/22

DFT Computation Using MATLAB

The functions to compute the DFT and the IDFT are fft and
ifft
These functions make use of FFT algorithms which are
computationally highly efficient compared to the direct
computation
The DFT and DTFT of the following function is shown below
x[n] = cos(6n/16), 0 n 15

Original PowerPoint slides prepared by S. K. Mitra 4-1-9

The McGraw-Hill Companies, Inc., 2007

DTFT from DFT by Interpolation

The DFT X[k] of a length-N sequence x[n] is simply the freq.
samples of its DTFT X(ej) evaluated at N uniformly spaced
frequency points = k = 2k/N,
2k/N 0 k N 1 1
Compared to the direct computation, these functions are
computationally highly efficient due to the use of FFT
Given the N-point DFT X[k] of a length-N sequence x[n], its
DTFT X(ej) can be uniquely determined from X[k]

Original PowerPoint slides prepared by S. K. Mitra 4-1-10

The McGraw-Hill Companies, Inc., 2007

5
 2008/4/22

DTFT from DFT by Interpolation

To develop a compact expression for the sum S, let
r = ej(2k/N)
Then

Or, equivalently
S rS = (1 r)S =1 rN
Hence
H

Original PowerPoint slides prepared by S. K. Mitra 4-1-11

The McGraw-Hill Companies, Inc., 2007

DTFT from DFT by Interpolation

Therefore

Original PowerPoint slides prepared by S. K. Mitra 4-1-12

The McGraw-Hill Companies, Inc., 2007

6
 2008/4/22

Sampling the DTFT

Consider a sequence x[n] with a DTFT X(ej)
We sample X(ej) at N equally spaced points k = 2k/N, 0
k N 1
1 developing the N frequency samples
These N frequency samples can be considered as an N-point
DFT Y[k] whose N-point IDFT is a length-N sequence y[n]
Now

Taking IDFT of Y[k] yields

Original PowerPoint slides prepared by S. K. Mitra 4-1-13

The McGraw-Hill Companies, Inc., 2007

Sampling the DTFT

That is

Making use of the identity

we arrive at the desired relation

Original PowerPoint slides prepared by S. K. Mitra 4-1-14

The McGraw-Hill Companies, Inc., 2007

7
 2008/4/22

Sampling the DTFT

Thus y[n] is obtained from x[n] by adding an infinite number
of shifted replicas of x[n], with each replica shifted by an
integer multiple of N sampling instants,
instants and observing the
sum only for the interval
To apply

to finite-length sequences, we assume that the samples

outside the specified range are zeros
Thus if x[n] is a length-M sequence with M N then y[n] =
x[n] for 0 n N 1

Original PowerPoint slides prepared by S. K. Mitra 4-1-15

The McGraw-Hill Companies, Inc., 2007

Sampling the DTFT

Example Let {x[n]} = {0 1 2 3 4 5}
By sampling its DTFT X(ej) at k = 2k/4, 0 k 3 and then
applying a 44-point
point IDFT to these samples
samples, we arrive at the
sequence y[n] given by
y[n] = x[n] + x[n + 4] + x[n 4] 0 n 3
i.e.,
{y[n]} = {4 6 2 3}
{{x[n]}
[ ]} cannot be recovered from {y[n]}
{y[ ]}

Original PowerPoint slides prepared by S. K. Mitra 4-1-16

The McGraw-Hill Companies, Inc., 2007

8
 2008/4/22

Numerical Computation of the DTFT

Using DFT
A practical approach to the numerical computation of the
DTFT of a finite-length sequence
Let X(ej) be the DTFT of a length-N sequence x[n]
We wish to evaluate X(ej) at a dense grid of frequencies
k = 2k/M, 0 k M 1, where M >> N:

Define a new sequence

Then

Original PowerPoint slides prepared by S. K. Mitra 4-1-17

The McGraw-Hill Companies, Inc., 2007

Numerical Computation of the DTFT

Using DFT
Thus X(ej) is essentially an M-point DFT Xe[k] of the
length-M sequence xe[n]
The DFT Xe[k] can be computed very efficiently using the
FFT algorithm if M is an integer power of 2
The function freqz employs this approach to evaluate the
frequency response at a prescribed set of frequencies of a
DTFT expressed as a rational function in ej

Original PowerPoint slides prepared by S. K. Mitra 4-1-18

The McGraw-Hill Companies, Inc., 2007

9
 2008/4/22

DFT Properties
Like the DTFT, the DFT also satisfies a number of
properties that are useful in signal processing applications
Some of these properties are essentially identical to those
of the DTFT, while some others are somewhat different

Original PowerPoint slides prepared by S. K. Mitra

x[n] is a complex sequence 4-1-19
The McGraw-Hill Companies, Inc., 2007

Symmetry Relations of DFT

Original PowerPoint slides prepared by S. K. Mitra

x[n] is a real sequence 4-1-20
The McGraw-Hill Companies, Inc., 2007

10
 2008/4/22

General Properties of DFT

Original PowerPoint slides prepared by S. K. Mitra 4-1-21

The McGraw-Hill Companies, Inc., 2007

Circular Shift of a Sequence

This property is analogous to the time-shifting property of
the DTFT, but with a subtle difference
Consider length-N
length N sequences defined for 0 n N 1.1
Sample values of such sequences are equal to zero for
values of n < 0 and n N
If x[n] is such a sequence, then for any arbitrary integer ,
the shifted sequence
x1[n] = x[n no]
is no longer defined for the range 0 n N 1
We thus need to define another type of a shift that will
always keep the shifted sequence in the range 0 n N 1

Original PowerPoint slides prepared by S. K. Mitra 4-1-22

The McGraw-Hill Companies, Inc., 2007

11
 2008/4/22

Circular Shift of a Sequence

The desired shift, called the circular shift, is defined using
a modulo operation:
xc[n] = x[n noN]
For no > 0 (right circular shift), the above equation implies

x[n 16] x[n 46]

= x[n + 56] = x[n + 26]
Original PowerPoint slides prepared by S. K. Mitra 4-1-23
The McGraw-Hill Companies, Inc., 2007

Circular Convolution
This operation is analogous to linear convolution, but with a
subtle difference
Consider two length-N
length N sequences,
sequences g[n] and h[n].
h[n] Their linear
convolution results in a length-(2N1) sequence yL[n]:

In computing yL[n] we assume that both length-N sequences

have been zero-padded to extend their lengths to 2N1
The longer form of yL[n] results from the time-reversal of the
sequence h[n] and its linear shift to the right
The first nonzero value of yL[n] is yL[0] = g[0]h[0] , and the
last nonzero value is yL[2N2] = g[N1]h[N1]
Original PowerPoint slides prepared by S. K. Mitra 4-1-24
The McGraw-Hill Companies, Inc., 2007

12
 2008/4/22

Circular Convolution
To develop a convolution-like operation resulting in a length-
N sequence yC[n], we need to define a circular time-
reversal and then apply a circular time-shift
reversal,
Resulting operation, called a circular convolution, is
defined by:

Since the operation defined involves two length-N

sequences it is often referred to as an N-point circular
sequences,
convolution, denoted as

The circular convolution is commutative, i.e.

Original PowerPoint slides prepared by S. K. Mitra 4-1-25

The McGraw-Hill Companies, Inc., 2007

Circular Convolution
Example - Determine the 4-point circular convolution of the
two length-4 sequences
{g[n]} = {1 2 0 1}, {h[n]} = {2 2 1 1}

The result is a length-4 sequence yC[n] given by

From above, we observe

Original PowerPoint slides prepared by S. K. Mitra 4-1-26

The McGraw-Hill Companies, Inc., 2007

13
 2008/4/22

Circular Convolution
Likewise
yC[1] = g[0]h[1] + g[1]h[0] + g[2]h[3] + g[3]h[2] = 7
yC[2] = g[0]h[2] + g[1]h[1] + g[2]h[0] + g[3]h[3] = 6
yC[3] = g[0]h[3] + g[1]h[2] + g[2]h[1] + g[3]h[0] = 5

Original PowerPoint slides prepared by S. K. Mitra 4-1-27

The McGraw-Hill Companies, Inc., 2007

Circular Convolution
Example - Consider the two length-4 sequences repeated
below for convenience:

The 4-point DFT G[k] of g[n] is given by

G[k] = g[0] + g[1] ej2k/4 + g[2] ej4k/4 + g[3] ej6k/4
= 1 + 2ejk/2 + ej3k/2 , 0 k 3
Therefore G[0] = 4, G[1] = 1 j, G[2] = 2, G[3] = 1+ j
Likely
H[k] = 2 + 2ejk/2 + ejk + ej3k/2 , 0 k 3

Original PowerPoint slides prepared by S. K. Mitra 4-1-28

The McGraw-Hill Companies, Inc., 2007

14
 2008/4/22

Circular Convolution
The two 4-point DFTs can also be computed using the
matrix relation given earlier

If YC[k] denotes the 4-point DFT of yC[n], YC[k] = G[k]H[k]

Original PowerPoint slides prepared by S. K. Mitra 4-1-29

The McGraw-Hill Companies, Inc., 2007

Circular Convolution
A 4-point IDFT of YC[k] yields

Original PowerPoint slides prepared by S. K. Mitra 4-1-30

The McGraw-Hill Companies, Inc., 2007

15
 2008/4/22

Circular Convolution
Example - Extend the two length-4 sequences to length 7 by
appending each with three zero-valued samples, i.e.

We next determine the 7-point circular convolution of ge[n]

and he[n]

From the above, we can obtain y[0] ~ y[6]

y[n] is precisely the sequence yL[n] obtained
by a linear convolution of g[n] and h[n]

Original PowerPoint slides prepared by S. K. Mitra 4-1-31

The McGraw-Hill Companies, Inc., 2007

Circular Convolution
The N-point circular convolution can be written in matrix
form as

Note: The elements of each diagonal of the matrix are equal

Such a matrix is called a circulant matrix

Original PowerPoint slides prepared by S. K. Mitra 4-1-32

The McGraw-Hill Companies, Inc., 2007

16
 2008/4/22

Circular Convolution Using Tabular

Method
Consider the evaluation of y[n] = h[n] g[n] where {g[n]}
and {h[n]} are length-4 sequences
First, the samples of the two sequences are multiplied using
the conventional multiplication method as shown below

The partial products generated in the 2nd, 3rd, and 4th rows
are circularly shifted to the left as indicated above 4-1-33
Original PowerPoint slides prepared by S. K. Mitra
The McGraw-Hill Companies, Inc., 2007

Circular Convolution Using Tabular

Method
The modified table after circular shifting is shown below

The samples of the sequence yC[n] are obtained by adding

the 4 p
partial p
products in the column above of each sample p
yC[0] = g[0]h[0] + g[3]h[1] + g[2]h[2] + g[1]h[3] = 7
yC[1] = g[1]h[0] + g[0]h[1] + g[3]h[2] + g[2]h[3] = 6
yC[2] = g[2]h[0] + g[1]h[1] + g[0]h[2] + g[3]h[3] = 5
yC[3] = g[3]h[0] + g[2]h[1] + g[1]h[2] + g[0]h[3] = 5 4-1-34
Original PowerPoint slides prepared by S. K. Mitra
The McGraw-Hill Companies, Inc., 2007

17
 2008/4/22

N-Point DFTs of Two Length-N Real

Sequences
Let g[n] and h[n] be two length-N real sequences with G[k]
and H[k] denoting their respective N-point DFTs
These two N-point DFTs can be computed efficiently using a
single N-point DFT
Define a complex length-N sequence
x[n] = g[n] + j h[n]
Let X[k] denote the N-point DFT of x[n]

Note that for 0 k N 1,

Original PowerPoint slides prepared by S. K. Mitra 4-1-35

The McGraw-Hill Companies, Inc., 2007

N-Point DFTs of Two Length-N Real

Sequences
Example - We compute the 4-point DFTs of the two real
sequences g[n] and h[n] given below
{g[n]} = {1 2 0 1}, {h[n]} = {2 2 1 1}
Then {x[n]} = {g[n]}+ j{h[n]} = {1+j2 2+j2 j 1+j}
Its DFT X[k] is

From the above

X*[k] = [4j6 2 2 j2], X*[4k4] = [4j6 j2 2 2]
Therefore
{G[k]} = {4 1j 2 1+j}, {H[k]} = {6 1j 0 1+j}
Original PowerPoint slides prepared by S. K. Mitra 4-1-36
The McGraw-Hill Companies, Inc., 2007

18
 2008/4/22

2N-Point DFTs of a Real Sequences

Using an N-Point DFT
Let v[n] be a length-N real sequence with a 2N-point DFT V[k]
Define two length-N real sequences g[n] and h[n] as follows:
g[n] = v[2n], h[n] = v[2n +1], 0 n N
Let G[k] and H[k] denote their respective N-point DFTs
Define a length-N complex sequence
{x[n]} = {g[n]}+ j{h[n]}
with an N-point DFT X[k]
Now
N

That is
Original PowerPoint slides prepared by S. K. Mitra 4-1-37
The McGraw-Hill Companies, Inc., 2007

2N-Point DFTs of a Real Sequences

Using an N-Point DFT
Example - Let us determine the 8-point DFT V[k] of the
length-8 real sequence
{v[n]} = {1 2 2 2 0 1 1 1}
We form two length-4 real sequences as follows
g[n] = v[2n] = {1 2 0 1}, h[n] = v[2n +1] = {2 2 1 1}
Now

S
Substituting the values off the 4-point DFTs G[k]
G and H[k],
we can obtain V[k]

Original PowerPoint slides prepared by S. K. Mitra 4-1-38

The McGraw-Hill Companies, Inc., 2007

19
 2008/4/22

Linear Convolution Using DFT

Since a DFT can be efficiently implemented using FFT
algorithms, it is of interest to develop methods for the
implementation of linear conconvolution
ol tion using
sing the DFT
Let g[n] and h[n] be two finite-length sequences of length N
and M, respectively
Define two length-L (L = N + M 1) sequences

Then

Original PowerPoint slides prepared by S. K. Mitra 4-1-39

The McGraw-Hill Companies, Inc., 2007

Linear Convolution Using DFT

The corresponding implementation scheme is illustrated
below

We next consider the DFT-based implementation of

where h[n] is a finite-length sequence of length M and x[n] is

an infinite length (or a finite length sequence of length much
greater than M) 4-1-40
Original PowerPoint slides prepared by S. K. Mitra
The McGraw-Hill Companies, Inc., 2007

20
 2008/4/22

Overlap-Add Method
We first segment x[n], assumed to be a causal sequence
here without any loss of generality, into a set of contiguous
finite-length
finite length subsequences of length N each:

where

Thus we can write

where

Since h[n] is of length M and is of length N, ym[n] is of length

N + M 1 4-1-41
Original PowerPoint slides prepared by S. K. Mitra
The McGraw-Hill Companies, Inc., 2007

Overlap-Add Method
The desired linear convolution y[n] = h[n] x[n] is broken up
into a sum of infinite number of short-length linear
convolutions of length N + M 11 each: ym[n] = h[n] xm[n]
Consider implementing the following convolutions using the
DFT-based method, where now the DFTs (and the IDFT)
are computed on the basis of (N + M 1) points

The first convolution in the above sum, y0[n] = h[n] x0[n], is

of length N + M 1 and is defined for 0 n N + M 2
The second short convolution y1[n] = h[n] x1[n], is also of
length N + M 1 but is defined for N n 3N + M 2
There is an overlap of samples between these two short
Originallinear
PowerPointconvolutions
slides prepared by S. K. Mitra 4-1-42
The McGraw-Hill Companies, Inc., 2007

21
 2008/4/22

Overlap-Add Method
In general, there will be an overlap of M 1 samples
between the samples of the short convolutions h[n] xr-1[n]
and h[n] xm[n] for (r 1)N
1)N n rN + M 2

Original PowerPoint slides prepared by S. K. Mitra 4-1-43

The McGraw-Hill Companies, Inc., 2007

Overlap-Add Method

Therefore, y[n] obtained by a linear convolution of x[n] and

h[n] is given by

Original PowerPoint slides prepared by S. K. Mitra 4-1-44

The McGraw-Hill Companies, Inc., 2007

22
 2008/4/22

Overlap-Add Method
The above procedure is called the overlap-add method
since the results of the short linear convolutions overlap and
the overlapped portions are added to get the correct final
result
The MATLAB function fftfilt can be used to implement the
above method
The following illustrates an example of filtering of a noise-
corrupted signal using a length-3 moving average filter:

Original PowerPoint slides prepared by S. K. Mitra 4-1-45

The McGraw-Hill Companies, Inc., 2007

Overlap-Save Method
In implementing the overlap-add method using the DFT, we
need to compute two (N + M 1)-point DFTs and one (N + M
1)-point
1) point IDFT for each short linear convolution
It is possible to implement the overall linear convolution by
performing instead circular convolution of length shorter than
(N + M 1)
To this end, it is necessary to segment x[n] into
overlapping blocks xm[n], keep the terms of the circular
convolution of h[n] with that corresponds to the terms
obtained by a linear convolution of h[n] and xm[n], and throw
away the other parts of the circular convolution

Original PowerPoint slides prepared by S. K. Mitra 4-1-46

The McGraw-Hill Companies, Inc., 2007

23
 2008/4/22

Overlap-Save Method
To understand the correspondence between the linear and
circular convolutions, consider a length-4 sequence x[n] and
a length-3
length 3 sequence h[n]
Let yL[n] denote the result of a linear convolution of x[n] with
h[n]
The six samples of yL[n] are given by
yL[0] = h[0]x[0]
yL[1] = h[0]x[1] + h[1]x[0]
yL[2] = h[0]x[2] + h[1]x[1] + h[2]x[0]
yL[3] = h[0]x[3] + h[1]x[2] + h[2]x[1]
yL[4] = h[1]x[3] + h[2]x[2]
yL[5] = h[2]x[3]
Original PowerPoint slides prepared by S. K. Mitra 4-1-47
The McGraw-Hill Companies, Inc., 2007

Overlap-Save Method
If we append h[n] with a single zero-valued sample and
convert it into a length-4 sequence he[n], the 4-point circular
convolution yC[n] of he[n] and x[n] is given by
yC[0] = h[0]x[0] + h[1]x[3] + h[2]x[2]
yC[1] = h[0]x[1] + h[1]x[0] + h[2]x[3]
yC[2] = h[0]x[2] + h[1]x[1] + h[2]x[0]
yC[3] = h[0]x[3] + h[1]x[2] + h[2]x[1]
If we compare the expressions for the samples yL[n] of with
those of yC[n],
[n] we observe that the first 2 terms of yC[n] do
not correspond to the first 2 terms of yL[n], whereas the last 2
terms of yC[n] are precisely the same as the 3rd and 4th
terms of yL[n], i.e.
yL[0] yC[0], yL[1] yC[1], yL[2] = yC[2], yL[3] = yC[3]
Original PowerPoint slides prepared by S. K. Mitra 4-1-48
The McGraw-Hill Companies, Inc., 2007

24
 2008/4/22

Overlap-Save Method
General case: N-point circular convolution of a length-M
sequence h[n] with a length-N sequence x[n] with N > M
First M 1 samples of the circular convolution are incorrect
and are rejected
Remaining N M + 1 samples correspond to the correct
samples of the linear convolution of h[n] with x[n]
Now, consider an infinitely long or very long sequence x[n]
Break it up as a collection of smaller length (length-4)
overlapping
l i sequences xm[n] [ ] as xm[n]
[ ] = x[n
[ + 2m],
2 ] 0 n 3,
3
0m
Next, form
wm[n] = h[n] xm[n]
Original PowerPoint slides prepared by S. K. Mitra 4-1-49
The McGraw-Hill Companies, Inc., 2007

Overlap-Save Method
Or, equivalently,
wm[0] = h[0]xm[0] + h[1]xm[3] + h[2]xm[2]
wm[1] = h[0]xm[1] + h[1]xm[0] + h[2]xm[3]
wm[2] = h[0]xm[2] + h[1]xm[1] + h[2]xm[0]
wm[3] = h[0]xm[3] + h[1]xm[2] + h[2]xm[1]
Computing the above for m = 0, 1, 2, 3, . . . , and substituting
the values of xm[n] we arrive at
w0[0] = h[0]x[0] + h[1]x[3] + h[2]x[2] Reject
w0[1] = h[0]x[1]
h[0] [1] + h[1]x[0]
h[1] [0] + h[2]x[3]
h[2] [3] Reject
R j
w0[2] = h[0]x[2] + h[1]x[1] + h[2]x[0] = y[2] Save
w0[3] = h[0]x[3] + h[1]x[2] + h[2]x[1] = y[3] Save

Original PowerPoint slides prepared by S. K. Mitra 4-1-50

The McGraw-Hill Companies, Inc., 2007

25
 2008/4/22

Overlap-Save Method
w1[0] = h[0]x[2] + h[1]x[5] + h[2]x[4] Reject
w1[1] = h[0]x[3] + h[1]x[2] + h[2]x[5] Reject
w1[2] = h[0]x[4] + h[1]x[3] + h[2]x[2] = y[4] Save
w1[3] = h[0]x[5] + h[1]x[4] + h[2]x[3] = y[5] Save

w2[0] = h[0]x[4] + h[1]x[5] + h[2]x[6] Reject

w2[1] = h[0]x[5] + h[1]x[4] + h[2]x[7] Reject
w2[2] = h[0]x[6] + h[1]x[5] + h[2]x[4] = y[6] Save
w2[3] = h[0]x[7]
h[0] [7] + h[1]x[6]
h[1] [6] + h[2]x[5]
h[2] [5] = y[7]
[7] Save
S
It should be noted that to determine y[0] and y[1], we need to
form x1[n]: x1[0] = 0, x1[1] = 0, x1[2] = x[0] , x1[3] = x[1]
and compute w1[n] = h[n] x1[n] for 0 n 3, reject w1[0]
and w1[1], and save w1[2] = y[0], and w1[3] = y[1] 4-1-51
Original PowerPoint slides prepared by S. K. Mitra
The McGraw-Hill Companies, Inc., 2007

Overlap-Save Method
General Case: Let h[n] be a length-N sequence
Let xm[n] denote the m-th section of an infinitely long
sequence x[n] of length N and defined by
xm[n] = x[n + m(N M + 1)], 0 n N 1 with M < N
Let wm[n] = h[n] xm[n]
Then, we reject the first M 1 samples of wm[n] and abut
the remaining M M + 1 samples of wm[n] to form yL[n], the
linear convolution of h[n] and x[n]
If ym[n] denotes the saved portion of wm[n], i.e.,

1
Then yL[n + m(N M + 1)] = ym[n], M 1 n N 1
Original PowerPoint slides prepared by S. K. Mitra 4-1-52
The McGraw-Hill Companies, Inc., 2007

26
 2008/4/22

Overlap-Save Method
The approach is called overlap-save method since the
input is segmented into overlapping sections and parts of the
results of the circular convolutions are saved and abutted to
determine the linear convolution result

Original PowerPoint slides prepared by S. K. Mitra 4-1-53

The McGraw-Hill Companies, Inc., 2007

Overlap-Save Method

Original PowerPoint slides prepared by S. K. Mitra 4-1-54

The McGraw-Hill Companies, Inc., 2007

27
 2008/4/22

Signal Transform
Motivation:
Represent a vector (e.g. a block of image samples) as
the
h superposition
i i off some typical
i l vectors (bl
(block
k
patterns)

+
t1 t2 t3 t4

Original PowerPoint slides prepared by S. K. Mitra 4-1-55

The McGraw-Hill Companies, Inc., 2007

Transform Coding of a Image

Original PowerPoint slides prepared by S. K. Mitra 4-1-56

The McGraw-Hill Companies, Inc., 2007

28
 2008/4/22

1-D 16-Pont DFT Basis Vectors

Original PowerPoint slides prepared by S. K. Mitra 4-1-57

The McGraw-Hill Companies, Inc., 2007

Disadvantages of DFT in Signal

Coding
Fourier Transform of a real function results in
complex numbers

May result in artifacts due to discontinuity

at the block boundary

Discontinuities (high freq. components)

Original PowerPoint slides prepared by S. K. Mitra 4-1-58
The McGraw-Hill Companies, Inc., 2007

29
 2008/4/22

From DFT to DCT

DFT of any real and symmetric sequence contains only
real coefficients corresponding to the cosine terms of
the series
Construct a new symmetric sequence y(n) of length 2N
out of x(n) of length N

y (n) = x(n),0 n N 1,
y (n) = x(2N 1 n), N n 2N 1.
Y(n) is symmetrical about n = N - (1/2)

Original PowerPoint slides prepared by S. K. Mitra 4-1-59

The McGraw-Hill Companies, Inc., 2007

From DFT to DCT

DCT has a higher compression ration than DFT
DCT avoids the generation of spurious spectral
components

No discontinuities

Original PowerPoint slides prepared by S. K. Mitra 4-1-60

The McGraw-Hill Companies, Inc., 2007

30
 2008/4/22

From DFT to DCT

2 N 1 1
(n + )k
Y (k ) =
n =0
y ( n )W 2N
2
,

N 1 1 2 N 1 1
(n + )k (n + )k
=
n=0
y ( n )W 2N
2
+
n=N
y ( n )W 2N
2

N 1 1 2 N 1 1
(n + )k (n + )k
=
n=0
x ( n )W 2N
2
+
n=N
x ( 2 N 1 n )W 2N
2

N 1 1 N 1 1
(n + )k [2N (n + )k ]
=
n=0
x ( n )W 2N
2
+
n=0
x ( n )W 2N
2

N 1
( 2 n + 1) k
=
n=0
2 x (n ) co s
2N
,
2
j
0 k 2 N 1, a n d W 2N = e 2N

Original PowerPoint slides prepared by S. K. Mitra 4-1-61

The McGraw-Hill Companies, Inc., 2007

1-D N-Point DCT

N 1
( 2 n + 1) k
F ( k ) = C ( k ) f ( n ) c o s ,
n =0 2N
k = 0 ,1, " , N 1,
N 1
( 2 n + 1) k
f (n ) =
k =0

C ( k )F ( k ) c o s
2N ,

n = 0 ,1, " , N 1,
where

1 2
C (0) = , C (k ) = , k = 1,2,", N 1
N N
The constants are often defined differently
Original PowerPoint slides prepared by S. K. Mitra 4-1-62
The McGraw-Hill Companies, Inc., 2007

31
 2008/4/22

1-D N-Point DCT

cos ( (2n + 1)0 /16 ) cos ( (2n + 1)2 /16 ) cos ( (2n + 1)4 /16 ) cos ( (2n + 1)6 /16 )

cos ( (2n + 1)1 /16 ) cos ( (2n + 1)3 /16 ) cos ( (2n + 1)5 /16 ) cos ( (2n + 1)7 /16 )

Original PowerPoint slides prepared by S. K. Mitra 4-1-63

The McGraw-Hill Companies, Inc., 2007

Example of 1-D DCT

Row 256 of Lena 2500.00
200.00

160.00
2000.00 absolute DCT values of Lena row 256

1500.00
120.00

80.00 1000.00

40.00 500.00

0.00 0.00
0.00 200.00 400.00 600.000.00 200.00 400.00 600.00

Original PowerPoint slides prepared by S. K. Mitra 4-1-64

The McGraw-Hill Companies, Inc., 2007

32
 2008/4/22

Illustration of Image Coding

Using 2-D DCT

Original PowerPoint slides prepared by S. K. Mitra 4-1-65

The McGraw-Hill Companies, Inc., 2007

DCT-Based Image Coding with

Different Quantization Levels
DCT coding with increasingly coarse quantization, block size 8x8

quantizer step-size quantizer step-size quantizer step-size

for AC coefficient: for AC coefficient: for AC coefficient:
25 100 200
Original PowerPoint slides prepared by S. K. Mitra 4-1-66
The McGraw-Hill Companies, Inc., 2007

33
 2008/4/22

Image Coding with Different

Numbers of DCT Coefficients

with 16/64
original coefficients

with 8/64 with 4/64

coefficients coefficients

Original PowerPoint slides prepared by S. K. Mitra 4-1-67

The McGraw-Hill Companies, Inc., 2007

Comparison of Basis Vectors of

Different Transform (1-D)

Original PowerPoint slides prepared by S. K. Mitra 4-1-68

The McGraw-Hill Companies, Inc., 2007

34
 2008/4/22

Comparison of Basis Vectors of

Different Transform (2-D)

Cosine Sine

Original PowerPoint slides prepared by S. K. Mitra Haar 4-1-69

69
The McGraw-Hill Companies, Inc., 2007

DCT-Based Coding: JPEG

8x8 blocks Compressed
DC
DPCM image data
Zigzag Entropy
DCT Q
scan encoder
AC
Source
image data Quantization Table
table specification
8x8 blocks
DC Compressed
DPCM image data
Zigzag Entropy
IDCT IQ
scan decoder
AC
Reconstructed
image data
Quantization Table
table specification
Original PowerPoint slides prepared by S. K. Mitra 4-1-70
The McGraw-Hill Companies, Inc., 2007

35