ch5 Mitra DSP C

Chapter 5
Finite-Length Discrete
Transforms
清大電機系林嘉文
cwlin@ee.nthu.edu.tw
03 5731152
03-5731152 4-1-1
Original PowerPoint slides prepared by S. K. Mitra
© The McGraw-Hill Companies, Inc., 2007
Digital Fourier Transform
• Definition
e t o - The e ssimplest
p est relation
e at o bet
between
ee a length-N
e gt
sequence x[n], defined for 0 ≤ n ≤ N −1, and its DTFT
X(ejω) is obtained by uniformly sampling X(ejω) on the ω-
axis between 0 ≤ ω < 2π at ωk = 2πk/ 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 sequence in the frequency

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

• Using
Us g tthe
e notation
otat o WN = e−j2π/N tthe
e DFT iss usually
usua y
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

• Thiss results
esu ts in:
• Making use of the identity
we observe the RHS of the last equation is equal to X[l]

• Hence
• Example
a p e - Co
Consider
s de tthe
e length-N
e gt sequence
seque ce
• Its N-point DFT is given by

, 0 ≤ k ≤ N −1
1
• Example - Consider the length-N sequence
• Its N-point DFT is given by

, 0 ≤ k ≤ N −1
1
• Example - Consider the length-N sequence defined for
0 ≤ n ≤ N −1
g[n] = cos(2πrn/ N), 0 ≤ r ≤ N −1
• Using a trigonometric identity we can write
• The N-point DFT of g[n] is thus given by

0 ≤ k ≤ N −1
1
• We get , 0 ≤ k ≤ N −1
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

Matrix Relation
• Likewise,
Likewise the IDFT relation given by
can be expressed in matrix form as
where is the IDFT matrix
• Note:

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(6πn/16), 0 ≤ n ≤ 15

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 = 2πk/N, 0 ≤ k ≤ N −1
• Compared to the direct computation, these functions are
computationally highly efficient due to the use of FFT
• Given
Gi the
th N-point
N i t DFT X[k] off a length-N
l th N sequence x[n],
[ ] its
it
DTFT X(ejω) can be uniquely determined from X[k]

• To develop a compact expression for the sum S, let
r = e−j(ω−2πk/N)
• Then
• Or, equivalently
S− rS = (1
S (1− r)S =1
=1− rN
• Hence

• Therefore

Sampling the DTFT
• Consider a sequence x[n] with a DTFT X(ejω)
• We sample X(ejω) at N equally spaced points ωk = 2πk/N, 0 ≤
k ≤ N −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

Sampling the DTFT
• That is
we arrive at the desired relation

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, and observing the
sum only l ffor the
th iinterval
t l
• To apply
tto finite-length
fi it l th sequences, we assume ththatt the
th samples
l
outside the specified range are zeros
• Thus if x[n] is a length
length-M
M sequence with M ≤ N then y[n] =
x[n] for 0 ≤ n ≤ N −1

Sampling the DTFT
• Example – Let {x[n]} = {0 1 2 3 4 5}
• By sampling its DTFT X(ejω) at ωk = 2πk/4, 0 ≤ k ≤ 3 and then
applying a 4-point IDFT to these 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]}

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
length N sequence x[n]
• We wish to evaluate X(ejω) at a dense grid of frequencies
ωk = 2πk/M,, 0 ≤ k ≤ M −1,, where M >> N:
• Define a new sequence
• Then

Numerical Computation of the DTFT
Using DFT
• Thus X(ejjω) 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
q employs
p y this approach
pp to evaluate the
frequency response at a prescribed set of frequencies of a
DTFT expressed as a rational function in e−jω

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

x[n] is a complex sequence 4-1-19
Symmetry Relations of DFT

x[n] is a real sequence 4-1-20
General Properties of DFT

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 sequences defined for 0 ≤ n ≤ N −1.
Sample values of such sequences are equal to zero for
values of n < 0 and n ≥ N
• If x[n]
[ ] is
i such
h a sequence, th
then ffor any arbitrary
bit iinteger
t ,
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

Circular Shift of a Sequence
• The desired shift, called the circular shift, is defined using
a modulo operation:
xc[n] = x[‫ۃ‬n − no‫ۄ‬N]
• For no > 0 (right circular shift), the above equation implies
x[‫ۃ‬n − 1‫ۄ‬6] x[‫ۃ‬n − 4‫ۄ‬6]

= x[‫ۃ‬n + 5‫ۄ‬6] = x[‫ۃ‬n + 2‫ۄ‬6]
Circular Convolution
• This operation is analogous to linear convolution, but with a
subtle difference
• Consider two length-N sequences, g[n] and h[n]. Their linear
convolution results in a length-(2N−1) sequence yL[n]:
• In computing yL[n] we assume that both length-N sequences

h
have b
been zero-padded
dd d tot extend
t d their
th i llengths
th tto 2N
2N−11
• 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[2N−2] = g[N−1]h[N−1]
• 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
• Resulting
R lti operation,
ti called
ll d a circular
i l convolution,
l ti i
is
defined by:
• Since the operation

p defined involves two length-N
g
sequences, it is often referred to as an N-point circular
convolution, denoted as
• The circular convolution is commutative, i.e.

• Example - Determine the 4-point circular convolution of the
t
two length-4
l th 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

• 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

• Example - Consider the two length-4 sequences repeated
b l
below ffor convenience:
i
• The 4-point DFT G[k] of g[n] is given by

G[k] = g[0] + g[1] e−j2πk/4 + g[2] e−j4πk/4 + g[3] e−j6πk/4
= 1 + 2e−jπk/2 + e−j3πk/2 , 0 ≤ k ≤ 3
• Therefore G[0] = 4, G[1] = 1− j, G[2] = −2, G[3] = 1+ j
• Likely
H[k] = 2 + 2e−jπk/2 + e−jπk + e−j3πk/2 , 0 ≤ k ≤ 3

• The two 4-point DFTs can also be computed using the
matrix
t i relation
l ti given
i earlier
li
• If YC[k] denotes the 4-point DFT of yC[n], YC[k] = G[k]H[k]

• A 4-point IDFT of YC[k] yields

• Example - Extend the two length-4 sequences to length 7 by
appending
di each h with
ith th
three zero-valued
l d samples,
l ii.e.
• We next determine the 7-point circular convolution of ge[n]

and he[n]
• From the above, we can obtain y[ y[0]] ~ y[

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

• 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

Circular Convolution Using Tabular
Method
• Consider
Co s de the ee
evaluation
a ua o o of y[n] = h[n] g[
g[n]] where
e e {g[
{g[n]}
]}
and {h[n]} are length-4 sequences
• First, the samples
p of the two sequences
q are multiplied
p usingg
the conventional multiplication method as shown below
• The ppartial p
products ggenerated in the 2nd, 3rd, and 4th rows
are circularly shifted to the left as indicated above 4-1-33
Circular Convolution Using Tabular
Method
• The
e modified
od ed tab
table
eaafter
te ccircular
cu a sshifting
t g is
s sshown
o be
below
o
• The samples of the sequence yC[n] are obtained by adding

the 4 partial products in the column above of each sample
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
N-Point DFTs of Two Length-N Real
Sequences
• Let
et g[
g[n]] and
a d h[n]
[ ] be ttwo
o length-N
e gt real
ea sequences
seque ces witht G[
G[k]]
and H[k] denoting their respective N-point DFTs
• These two N-point
p DFTs can be computed p efficiently
y using
ga
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,

N-Point DFTs of Two Length-N Real
Sequences
• Example
a p e - We e co
compute
pute tthe
e 4-point
po t DFTs so
of tthe
e ttwo
o real
ea
sequences g[n] and h[n] given below
{g[n]}
{g[ ]} = {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] = [4−j6 2 −2 −j2], X*[‫ۃ‬4−k‫ۄ‬4] = [4−j6 −j2 −2 2]
• Therefore
{G[k]} = {4 1−j −2 1+j}, {H[k]} = {6 1−j 0 1+j}
2N-Point DFTs of a Real Sequences
Using an N-Point DFT
• Let
et v[n]
[ ] be a length-N
e gt real
ea sequence
seque ce with t a 2N-point
po t 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],
1], 0 ≤ n ≤ N
• Let G[k] and H[k] denote their respective N-point DFTs
• Define a length-N
length N complex sequence
{x[n]} = {g[n]}+ j{h[n]}
with an NN-point
point DFT X[k]
• Now
• That is
2N-Point DFTs of a Real Sequences
Using an N-Point DFT
• Example
a p e - Letet us dete
determinee tthe
e8 8-point
po t DFT V[k]
[ ] of
o tthe
e
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]
g[ [ ] = {{1 2 0 1}, }, h[n]
[ ] = v[2n
[ +1]] = {{2 2 1 1}}
• Now
• Substituting the values of the 4-point DFTs G[k] and H[k],

we can obtain V[k]

Linear Convolution Using DFT
• Since
S ce a DFT ca can be e efficiently
c e t y implemented
p e e ted us
using
g FFT
algorithms, it is of interest to develop methods for the
implementation of linear convolution using 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

Linear Convolution Using DFT
• The
e co
corresponding
espo d g implementation
p e e tat o sc
scheme
e e is
s illustrated
ust ated
below
• We next consider the DFT-based implementation

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

g ((or a finite length
an infinite length g sequence
q of length
g much
greater than M) 4-1-40
Overlap Add Method
Overlap-Add
• We first segment x[n], assumed to be a causal sequence
h
here without
ith t any loss
l off generality,
lit iinto
t a sett off contiguous
ti
finite-length subsequences of length N each:
where
• Thus we can write
where
• Since h[n]
[ ] is of length
g M and is of length
g N, ym[[n]] is of length
g
N + M −1 4-1-41
Overlap Add Method
Overlap-Add
• The desired linear convolution y[n] = h[n] x[n] is broken up
i t a sum off infinite
into i fi it number
b off short-length
h tl th lilinear
convolutions of length N + M −1 each: ym[n] = h[n] xm[n]
• Consider implementing the follo
following
ing con
convolutions
ol tions using
sing the
DFT-based method, where now the DFTs (and the IDFT)
are computed on the basis of (N + M −1) 1) points
• Th The first
fi convolution l i iin the h above
b sum, y0[n]
[ ] = h[n]
h[ ] x0[n],
[ ] isi
of length N + M −1 and is defined for 0 ≤ n ≤ N + M − 2
• TheTh second d short
h t convolution l ti y1[n]
[ ] = h[n]
h[ ] x1[n],
[ ] is
i also
l off
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
Overlap Add Method
Overlap-Add
• In general, there will be an overlap of M −1 samples
b t
between the
th samplesl off the
th short
h t convolutions
l ti h[ ] xr-1[n]
h[n] [ ]
and h[n] xm[n] for (r −1)N ≤ n ≤ rN + M − 2

Overlap Add Method
Overlap-Add
• Therefore, y[n] obtained by a linear convolution of x[n] and

h[n] is given by

Overlap Add Method
Overlap-Add
• The above procedure is called the overlap-add method
since
i th
the results
lt off th
the short
h t linear
li convolutions
l ti overlap
l andd
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
p signal
g using g a length-3
g movingg average
g filter:

Overlap Save Method
Overlap-Save
• In implementing the overlap-add method using the DFT, we
need d tto compute
t two
t (N + M −1)-point
1) i t DFTs
DFT and d one (N + M
−1)-point IDFT for each short linear convolution
• It is possible to implement the ooverall
erall linear convolution
con ol tion by
b
performing instead circular convolution of length shorter than
(N + M −1) 1)
• To this end, it is necessary to segment x[n] into
overlapping ], keep
pp g blocks xm[[n], p 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 off the circular convolution

Overlap Save Method
Overlap-Save
• To understand the correspondence between the linear and
circular
i l convolutions,
l ti consider
id a length-4
l th 4 sequence x[n]
[ ] andd
a length-3 sequence h[n]
• Let yL[n] denote the res
result
lt of a linear convolution
con ol tion of x[n]
[n] with
ith
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]
h[2] [3]
Overlap Save Method
Overlap-Save
• If we append h[n] with a single zero-valued sample and
convertt it into
i t a length-4
l th 4 sequence he[n],
[ ] the
th 4-point
4 i t circular
i l
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], 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]
Overlap Save Method
Overlap-Save
• General case: N-point circular convolution of a length-M
sequence h[n]
h[ ] with
ith a length-N
l th N sequence x[n]
[ ] with
ith 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
(length-4)
4)
overlapping sequences xm[n] as xm[n] = x[n + 2m], 0 ≤ n ≤ 3,
0≤m≤∞
• Next, form
wm[n] = h[n] xm[n]
Overlap Save Method
Overlap-Save
• 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]x
h[0] m[2] + h[1]x
h[1] m[1] + h[2]x
h[2] m[0]
wm[3] = h[0]xm[3] + h[1]xm[2] + h[2]xm[1]
• Computing
C ti ththe above
b ffor m = 0,
0 11, 2
2, 3
3, . . . , and
d substituting
b tit ti
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[1]x[0] + h[2]x[3] Å Reject
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

Overlap Save Method
Overlap-Save
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[0] [5] + h[1]x[4]
h[1] [4] + h[2]x[3]
h[2] [3] = y[5]
[5] Å Save
S
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[1]x[6] + h[2]x[5] = y[7] Å Save
• It should be noted that to determine y[0] and y[1],y[1] we need to
form x−1[n]: x−1[0] = 0, x−1[1] = 0, x−1[2] = x[0] , x−1[3] = x[1]
and
a d co
compute
pu e w−1[[n]] = h[n]
[ ] x−1[[n]] for
o 0 ≤ n ≤ 3, reject
ejec w−1[0]
and w−1[1], and save w−1[2] = y[0], and w−1[3] = y[1] 4-1-51
Overlap Save Method
Overlap-Save
• 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
• Th yL[n
Then [ + m(N
(N − M + 1)] = ym[n],
[ ] M−1≤n≤N−1
Overlap Save Method
Overlap-Save
• The approach is called overlap-save method since the
i
input
t is
i segmented t d into
i t overlapping
l i sections
ti and
d parts
t off the
th
results of the circular convolutions are saved and abutted to
determine the linear convolution result

Overlap Save Method
Overlap-Save

Signal Transform
• Motivation:
– Represent a vector (e.g. a block of image samples) as
the superposition of some typical vectors (block
patterns)
+
t1 t2 t3 t4

Transform Coding of a Image

1 D 16
1-D 16-Pont
Pont DFT Basis Vectors

Disadvantages of DFT in Signal
Coding
• Fourier
ou e Transform
a so o of a real
ea function
u ct o results
esu ts in
complex numbers
• May result in artifacts due to discontinuity

at the block boundary
Discontinuities (high freq. components)

From DFT to DCT
• DFT of any real and symmetric sequence contains only
reall coefficients
ffi i t corresponding
di tot the
th cosine
i terms
t off
the series
• Construct a new symmetric sequence y(n) of length 2N
out of x(n) of length N
y (n ) = x(n ),0
) 0 ≤ n ≤ N − 1,
y (n ) = x((2N − 1 − n ), N ≤ n ≤ 2N − 1.
• Y(n) is symmetrical about n = N - (1/2)

From DFT to DCT
• DCT has a higher compression ration than DFT
• DCT avoids the generation of spurious spectral
components
No discontinuities

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

1DN
1-D N-Point
Point DCT
⎡ ( 2 n + 1) k π ⎤
N −1
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 ) = ∑ C ( k )F ( k ) c o s ⎢ ⎥ ,
k =0 ⎣ 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
1DN
1-D N-Point
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 )

Example of 1
1-D
D DCT
Row 256 of Lena 2500 00
2500.00
200.00
160 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 0.00
600.00 200.00 400.00 600.00

Illustration of Image Coding
Using 2-D DCT

DCT-Based Image Coding with
Different Quantization Levels
• DCT coding
di with
i h increasingly
i i l coarse quantization,
i i block
bl k size
i 8x8
8 8
quantizer step-size quantizer step-size quantizer step-size

for AC coefficient: for AC coefficient: for AC coefficient:
25 100 200
Image Coding with Different
Numbers of DCT Coefficients
with 16/64
original coefficients
with 8/64 with 4/64

coefficients coefficients

Comparison of Basis Vectors of
Different Transform (1-D)

Comparison of Basis Vectors of
Different Transform (2-D)
Cosine Sine
Original PowerPoint slides prepared by S. K. Mitra Haar 4-1-69

69
DCT Based Coding: JPEG
DCT-Based
8x8 blocks Compressed
DC
C
DPCM i
image d
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

ch5 Mitra DSP C

Uploaded by

Copyright:

Available Formats

ch5 Mitra DSP C

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

ch5 Mitra DSP C

Uploaded by

Copyright:

Available Formats

Chapter 5

• Note: X[k] is also a length-N sequence in the frequency

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

• The Inverse Discrete Fourier Transform ((IDFT)) is

• To verify the above expression we multiply both sides of

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

• Making use of the identity

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

• Its N-point DFT is given by

• Example - Consider the length-N sequence

• Its N-point DFT is given by

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

can be expressed in matrix form as

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

can be expressed in matrix form as

where is the IDFT matrix

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

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

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

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

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

• Taking IDFT of Y[k] yields

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

• Making use of the identity

we arrive at the desired relation

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

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

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

• Define a new sequence

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

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

Original PowerPoint slides prepared by S. K. Mitra

Original PowerPoint slides prepared by S. K. Mitra

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

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

x[‫ۃ‬n − 1‫ۄ‬6] x[‫ۃ‬n − 4‫ۄ‬6]

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

• Since the operation

• The circular convolution is commutative, i.e.

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

• 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

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

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

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

• 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

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

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

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

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

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

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

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

• Note that for 0 ≤ k ≤ N −1,

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

• From the above

• Substituting the values of the 4-point DFTs G[k] and H[k],