Signal Processing - January 2017 - 89

TIPS & Tricks
Denis A. Gudovskiy and Lichung Chu

An Accurate and Stable Sliding DFT
Computed by a Modified CIC Filter

T

he sliding discrete Fourier transform
(SDFT) is a popular algorithm used
in nonparametric spectrum estimation when only a few frequency bins
of an M-point discrete Fourier transform
(DFT) are of interest. Although the classical SDFT algorithm described in [1] is
computationally efficient, its recursive
structure suffers from accumulation and
rounding errors, which lead to potential instabilities or inaccurate output.
Duda [2] proposed a modulated SDFT
(mSDFT) algorithm, which has the property of being guaranteed stable without
sacrificing accuracy, unlike previous
approaches described in [1],  [3], and
[4]. However, all of these conventional SDFT methods presume DFT computation on a sample-by-sample basis. This
is not computationally efficient when the
DFT needs only to be computed every
R ^ R 2 1h samples. To address such
cases when R-times downsampling is
needed, Park et al. [5] proposed a hopping SDFT (HDFT) algorithm. Recently, Wang et al. [6] presented a modulated
HDFT (mHDFT) algorithm, which combines the HDFT algorithm with the
mSDFT idea to maintain stability and
accuracy at the same time. In parallel,
Park [7] updated the HDFT algorithm
with its guaranteed stable modification
called gSDFT, which exists only for certain M and L relationships.

Digital Object Identifier 10.1109/MSP.2016.2620198
Date of publication: 11 January 2017

1053-5888/17©2017IEEE

Introduction
In this article, we present a method
to improve the SDFT algorithm. The
improved algorithm is called cascade
integrator-comb (CIC)-SDFT, which is
based on extending the idea established
in the mSDFT algorithm and mostly
in the context of spectrum estimation
application. Similarly to mSDFT, we
move the DFT bin of interest k to the
zero position to exclude complex coefficient multiplication in the recursive
stage and avoid instabilities. In addition, CIC-SDFT comprises a modified CIC filter structure proposed by
Hogenauer [8]. Two goals are achieved
using this approach. First, the accuracy
of spectrum estimation is improved by
using high-order CIC filters without
computationally expensive windowing
in the frequency domain as described in
[1]. Second, the complexity of the SDFT
can be further decreased by reducing
the DFT output rate, also achieved by
[5]-[7].

SDFT and mSDFT
The kth frequency bin of an M-point
DFT at time index n for input signal x
is defined by

X n (k) =

M- 1

/

W -Mkm x q + m,

(1)

m= 0

where q = n - M + 1, 0 # k # M - 1,
and the complex exponential factor
W M = e j2r/M. A recursive equivalent of
(1) is given by
IEEE Signal Processing Magazine

|

January 2017

|

X n (k) = W kM ^ X n - 1 (k) + x n - x n - M h .
(2)
Equation  (2) can be implemented as a
filter with a comb stage followed by an
integrator stage, as shown in Figure 1(a).
This conventional SDFT filter has a
z-domain pole on the unit circle located
at z = W kM. Hence, it is only marginally
stable in finite precision recursive calculations with accumulation, except at
points when poles z = ! 1 or z = ! j.
Duda [2] proposed to shift the X (k)
DFT bin of interest to the k = 0 bin prior
to calculating the comb stage in SDFT.
Thus, the X n (k) calculation is simplified to multiplication of input signal
x n by the modulation sequence W -Mkm,
followed by calculation of a new zerofrequency Yn (0) DFT bin expressed as
X n (k) = Yn (0) = Yn - 1 (0) + y n - y n - M,
(3)
w h e r e y n = W -Mkm x n a n d y n - M =
-k (m - M )
WM
xn - M .
The mSDFT structure is shown
in Figure  1(b). Complex multiplication in the integrator stage is unnecessary because W 0M = 1. Therefore, the
mSDFT filter becomes guaranteedstable and accurate at the same time. In
addition, complex multiplication in the
recursive stage might limit the clock rate
of the digital circuit, which is avoided in
this method by effectively moving it into
the feedforward part.
The drawback of the mSDFT algorithm compared to the conventional
89



Table of Contents for the Digital Edition of Signal Processing - January 2017

Signal Processing - January 2017 - Cover1
Signal Processing - January 2017 - Cover2
Signal Processing - January 2017 - 1
Signal Processing - January 2017 - 2
Signal Processing - January 2017 - 3
Signal Processing - January 2017 - 4
Signal Processing - January 2017 - 5
Signal Processing - January 2017 - 6
Signal Processing - January 2017 - 7
Signal Processing - January 2017 - 8
Signal Processing - January 2017 - 9
Signal Processing - January 2017 - 10
Signal Processing - January 2017 - 11
Signal Processing - January 2017 - 12
Signal Processing - January 2017 - 13
Signal Processing - January 2017 - 14
Signal Processing - January 2017 - 15
Signal Processing - January 2017 - 16
Signal Processing - January 2017 - 17
Signal Processing - January 2017 - 18
Signal Processing - January 2017 - 19
Signal Processing - January 2017 - 20
Signal Processing - January 2017 - 21
Signal Processing - January 2017 - 22
Signal Processing - January 2017 - 23
Signal Processing - January 2017 - 24
Signal Processing - January 2017 - 25
Signal Processing - January 2017 - 26
Signal Processing - January 2017 - 27
Signal Processing - January 2017 - 28
Signal Processing - January 2017 - 29
Signal Processing - January 2017 - 30
Signal Processing - January 2017 - 31
Signal Processing - January 2017 - 32
Signal Processing - January 2017 - 33
Signal Processing - January 2017 - 34
Signal Processing - January 2017 - 35
Signal Processing - January 2017 - 36
Signal Processing - January 2017 - 37
Signal Processing - January 2017 - 38
Signal Processing - January 2017 - 39
Signal Processing - January 2017 - 40
Signal Processing - January 2017 - 41
Signal Processing - January 2017 - 42
Signal Processing - January 2017 - 43
Signal Processing - January 2017 - 44
Signal Processing - January 2017 - 45
Signal Processing - January 2017 - 46
Signal Processing - January 2017 - 47
Signal Processing - January 2017 - 48
Signal Processing - January 2017 - 49
Signal Processing - January 2017 - 50
Signal Processing - January 2017 - 51
Signal Processing - January 2017 - 52
Signal Processing - January 2017 - 53
Signal Processing - January 2017 - 54
Signal Processing - January 2017 - 55
Signal Processing - January 2017 - 56
Signal Processing - January 2017 - 57
Signal Processing - January 2017 - 58
Signal Processing - January 2017 - 59
Signal Processing - January 2017 - 60
Signal Processing - January 2017 - 61
Signal Processing - January 2017 - 62
Signal Processing - January 2017 - 63
Signal Processing - January 2017 - 64
Signal Processing - January 2017 - 65
Signal Processing - January 2017 - 66
Signal Processing - January 2017 - 67
Signal Processing - January 2017 - 68
Signal Processing - January 2017 - 69
Signal Processing - January 2017 - 70
Signal Processing - January 2017 - 71
Signal Processing - January 2017 - 72
Signal Processing - January 2017 - 73
Signal Processing - January 2017 - 74
Signal Processing - January 2017 - 75
Signal Processing - January 2017 - 76
Signal Processing - January 2017 - 77
Signal Processing - January 2017 - 78
Signal Processing - January 2017 - 79
Signal Processing - January 2017 - 80
Signal Processing - January 2017 - 81
Signal Processing - January 2017 - 82
Signal Processing - January 2017 - 83
Signal Processing - January 2017 - 84
Signal Processing - January 2017 - 85
Signal Processing - January 2017 - 86
Signal Processing - January 2017 - 87
Signal Processing - January 2017 - 88
Signal Processing - January 2017 - 89
Signal Processing - January 2017 - 90
Signal Processing - January 2017 - 91
Signal Processing - January 2017 - 92
Signal Processing - January 2017 - 93
Signal Processing - January 2017 - 94
Signal Processing - January 2017 - 95
Signal Processing - January 2017 - 96
Signal Processing - January 2017 - 97
Signal Processing - January 2017 - 98
Signal Processing - January 2017 - 99
Signal Processing - January 2017 - 100
Signal Processing - January 2017 - 101
Signal Processing - January 2017 - 102
Signal Processing - January 2017 - 103
Signal Processing - January 2017 - 104
Signal Processing - January 2017 - 105
Signal Processing - January 2017 - 106
Signal Processing - January 2017 - 107
Signal Processing - January 2017 - 108
Signal Processing - January 2017 - 109
Signal Processing - January 2017 - 110
Signal Processing - January 2017 - 111
Signal Processing - January 2017 - 112
Signal Processing - January 2017 - 113
Signal Processing - January 2017 - 114
Signal Processing - January 2017 - 115
Signal Processing - January 2017 - 116
Signal Processing - January 2017 - Cover3
Signal Processing - January 2017 - Cover4
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201809
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201807
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201805
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201803
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201801
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1117
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0917
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0717
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0517
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0317
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0117
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1116
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0916
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0716
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0516
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0316
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0116
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1115
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0915
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0715
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0515
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0315
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0115
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1114
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0914
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0714
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0514
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0314
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0114
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1113
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0913
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0713
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0513
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0313
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0113
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1112
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0912
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0712
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0512
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0312
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0112
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1111
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0911
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0711
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0511
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0311
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0111
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1110
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0910
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0710
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0510
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0310
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0110
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1109
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0909
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0709
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0509
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0309
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0109
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1108
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0908
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0708
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0508
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0308
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0108
https://www.nxtbookmedia.com