Page 187 - Applied Numerical Methods Using MATLAB

176 INTERPOLATION AND CURVE FITTING
3.19 Interpolation by Using DFS: Zero-Padding on the Frequency Domain
The fitting curve in Fig. 3.14d has been obtained by zeroing out all the
digital frequency components higher than π/2 [rad](N/4 <k < 3N/4)ofthe
sequence x[n] in Fig. 3.14a. Plot another fitting curve obtained by removing
all the frequency components higher than π/4 [rad](N/8 <k < 7N/8) and
compare it with Fig. 3.14d.
3.20 On-Line Recursive Computation of DFT
For the case where you need to compute the DFT of a block of data every
time a new sampled data replaces the oldest one in the block, we derive
the following recursive algorithm for DFT computation.
Defining the first data block and the mth data block as

{x 0 [0],x 0 [1],.. . ,x 0 [N − 1]}= {0, 0,. .., 0} (P3.20.1)
{x m [0],x m [1],. ..,x m [N − 1]}= {x[m],x[m + 1],...,x[m + N − 1]} (P3.20.2)

the DFT for the (m + 1)th data block

{x m+1 [0],x m+1 [1],... ,x m+1 [N − 1]}={x[m + 1],x[m + 2],... ,x[m + N]}
(P3.20.3)

can be expressed in terms of the DFT for the mth data block
N−1
−j2πnk/N
X m (k) = x m [n]e , k = 0: N − 1 (P3.20.4)
n=0
as follows:
N−1 N−1
X m+1 (k) = x m+1 [n]e −j2πnk/N = x m [n + 1]e −j2πnk/N
n=0 n=0
N−1
e
= x m [n + 1]e −j2π(n+1)k/N j2πk/N
n=0
N
e
= x m [n]e −j2πnk/N j2πk/N
n=1

N−1
= x m [n]e −j2πnk/N + x[N] − x[0] e j2πk/N
n=0
j2πk/N
={X m (k) + x[N] − x[0]}e (P3.20.5)
You can compute the 128-point DFT for a block composed of 128 random
numbers by using this RDFT algorithm and compare it with that obtained