Signal Processing - January 2017 - 92

yn

xn

CIC

N0

NQ-1

R0

~
X n (k)

R L-1

WM-km
2

(1 + z -1)L

M
z -R

z -1

Figure 4.  The partially nonrecursive CIC-SDFT filter structure.

Partially nonrecursive structure

H 2 (z) = (1 + z - 1) L f (1 + z - 2

Although recursive CIC-SDFT reduces
computational complexity for R > 1, it
experiences a bit-growth according to
CIC filter theory. Assuming an input
bit-width B in, the bit-width B used for
all computations in the CIC-SDFT can
be expressed as
B = ^L log 2 (M)h + B in .

(11)

Wider bit-widths have to be used as the
number of stages L and DFT length M
grows. This drawback can be solved by
using nonrecursive structures derived
from polynomial factoring and applying
polyphase decomposition [9]. Then for
power-of-two DFT length M = 2 P, the
transfer function of CIC-SDFT can be
written as
H (z) = e

M-1

/

L

z -m o

M/R - 1

=e

/

P- Q- 1

)L

L

z- m o .

m= 0

(14)

From (13) and (14) it is clear that the
CIC-SDFT transfer function H(z) can
be split into two parts: H 1 (z) computed
in nonrecursive fashion and H 2 (z) computed in recursive fashion.
The first nonrecursive part comprises Q stages where each stage increases
bit-width by L bits and downsamples
the output by two. For each stage, which
calculates (1 + z -1) L, several implementations are possible. For example,
it can be realized as a length-L cascade
of (1 + z -1) operations or direct exponentiation of the whole stage. The latter
can be expressed as a transfer function
H N (z), and for L = 4
H N (z) = (1 + z -1) 4

m=0

= 1 + 6z -2 + z -4

= (1 + z -1) L (1 + z -2) L
P-1

# (1 + z -4) L f (1 + z -2 ) L .
(12)
Assuming a power-of-two downsampling factor R = 2 Q , (12) can be rewritten as
H (z)
Q-1

= (1 + z -1) L (1 + z -2) L g (1 + z -2 ) L
144444444424444444443
H 1 ( z)

P-1

-2 Q L

# (1 + z ) g (1 + z -2 ) L
144444424444443

+ 4z -1 (1 + z -2)
= H N 1 (z) + H N2 (z),

(15)

where H N 1 (z) and H N 2 (z) are new
polyphase components. Note that each
polyphase component may downsample
computations by two prior to performing add operations. The nonrecursive
part experiences bit growth of only
L log 2 (R), which means that the total
bit-width at its output can be written as

H 2 (z )

= H 1 (z) H 2 (z) .

(13)

Next, assuming that the H 1 (z) output
is followed by a downsampler by R, the
transfer function H 2 (z) in (13) can be
simplified to
92

B N = L log 2 (R) + B in .

(16)

The second recursive part now implements an Lth-order moving-average filter
of length M/R with the transfer function
H 2 (z) . Such a filter can be realized using
IEEE Signal Processing Magazine

|

January 2017

|

a cascade of L sections, where each section contains a comb stage followed by
an integrator stage. Then, the bit-width
increases by only log 2 (M/R) = (P - Q)
bits per section. The total bit-width at the
output of partially nonrecursive structure is identical to (11).
Figure 4 illustrates an alternative
partially nonrecursive implementation of
CIC-SDFT. First, it contains Q nonrecursive stages N 0, f N Q - 1 according to the aforementioned description.
Second, nonrecursive stages are followed by a cascade of L recursive
sections R 0, f R L - 1 . Due to the fact
that bit-widths are increased on a
per-stage basis rather than all at once
at the input of the CIC-SDFT, the
computational and circuit complexity
decreases. Moreover, since downsampling is performed as early as possible, the number of add operations is
minimized as well. Another important
advantage of the structure shown in
Figure  4 is the ability to model CICSDFT using floating-point arithmetic,
since overflows in the integrator stages
are avoided. The latter property allows
to implement a rounding operation
between algorithm stages.

Summary
In this article, a novel SDFT algorithm
called CIC-SDFT was introduced. It
generalizes a previous approach by
incorporating a modified CIC filter
structure. Such a generalization adds
two new programmable parameters:
filter order and output rate. Filter
order is responsible for an embedded
window function, and therefore determines the spectrum estimator variance
and interference rejection capabilities.
Sidelobe level is proportional to the
filter order as - 13L dB for the embedded window function. The closed-form
expression for the variance of CICSDFT estimator and its periodogram
was provided.
Programmability of the output rate
allows one to decrease algorithm computational complexity when needed.
Specifically, the number of memory
cells and half of the add operations in
recursive CIC-SDFT are inversely proportional to the downsampling factor R.



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