IEEE Circuits and Systems Magazine - Q1 2018 - 25

Does a relationship (or exchange formula) exist between the number of
full-adders and the number of flip-flops (in practical implementation of FIR filters)?
The Line Represents the Min Number of FA

5,000
4,500

Number of Flip-Flops (FF)

4,000
3,500
3,000
2,500
2,000

The line is the Locus for
FA + FF = 8,000

Minimal-Complexity
Filter Design

1,500
1,000
This line corresponds to the min number of flip-flops
needed to practically implement the given filter spec.

500
0

0

500

1,000

1,500

2,000
2,500
3,000
Number of Full Adders (FA)

3,500

4,000

4,500

5,000

Figure 13. Illustration of the possible relationship between the number of full-adders and flip-flops needed to practically implement
an fIr filter.

IV. Final Thoughts/Open Questions
Is there any general rule or exchange rate for full-adder (FA)
to flip-flop (FF) conversion (and vice versa) when designing
practical FIR filters? Is there any specific range for the FF/FA
ratio in a minimal-complexity FIR implementation?
Fig. 13 illustrates these questions by showing that
the total hardware complexity (FA + FF), which is highlighted by the thick solid red line, is initially reduced by
a more efficient implementation that decreases the number of full-adders in exchange for a small increase in the
number of flip-flops. This optimization reaches a minimal hardware-complexity point beyond which a further
reduction of the number of full-adders is not justified
since it would require a large flip-flop increase.
Based on empirical data [45]-[60], we have also observed that the minimal hardware-complexity filter
design (non-multirate), illustrated in Fig. 13, has a FF/FA
ratio range between 0.5 and 2 with a higher probability
of containing more flip-flops than full-adders for minimal-complexity FIR filter designs.
Is there any lower bound on the number of full adders
in order to implement a practical FIR filter (given a spec)?
What about the number of adders (shift-add operations)?
This is also illustrated in Fig. 13 for both the number
of full-adders and the number of flip-flops (asymptotic
lines.) We know that a nonrecursive FIR implementation
fIrst quArtEr 2018

requires a minimum number of memory elements to store
all the required samples that contribute to the computation of the output sample. This is realized using registers
which translate into a number of flip-flops depending on
the wordlengths (bitwidths) of the signal and datapath.
We believe it is reasonable to expect that a lower bound
should also exist for the total number of full-adders in order to practically implement an FIR structure that would
satisfy a given desired filter specification (passband ripple and edge, stopband ripple and edge).
We are not aware of any general lower bound on the
number of full-adders (FA) in an FIR filter design. By using empirical data from filter designs published in the
past four decades we postulate that there exists such a
bound. This is illustrated in Fig. 14 where the following
approximate bound is identified through curve-fitting
using empirical data:
y K 2 ^e x

0.36

- 1h

(19)

y = max realizable Remez order for an FIR filter
x = given number of shift-add operations (adder
budget)
Is there a practical definition for the entropy of an
FIR filter?
While entropy, as a key measure of information, is welldefined [14]-[17] (as the average number of bits needed
IEEE cIrcuIts ANd systEMs MAgAzINE

25



Table of Contents for the Digital Edition of IEEE Circuits and Systems Magazine - Q1 2018

Contents
IEEE Circuits and Systems Magazine - Q1 2018 - Cover1
IEEE Circuits and Systems Magazine - Q1 2018 - Cover2
IEEE Circuits and Systems Magazine - Q1 2018 - Contents
IEEE Circuits and Systems Magazine - Q1 2018 - 2
IEEE Circuits and Systems Magazine - Q1 2018 - 3
IEEE Circuits and Systems Magazine - Q1 2018 - 4
IEEE Circuits and Systems Magazine - Q1 2018 - 5
IEEE Circuits and Systems Magazine - Q1 2018 - 6
IEEE Circuits and Systems Magazine - Q1 2018 - 7
IEEE Circuits and Systems Magazine - Q1 2018 - 8
IEEE Circuits and Systems Magazine - Q1 2018 - 9
IEEE Circuits and Systems Magazine - Q1 2018 - 10
IEEE Circuits and Systems Magazine - Q1 2018 - 11
IEEE Circuits and Systems Magazine - Q1 2018 - 12
IEEE Circuits and Systems Magazine - Q1 2018 - 13
IEEE Circuits and Systems Magazine - Q1 2018 - 14
IEEE Circuits and Systems Magazine - Q1 2018 - 15
IEEE Circuits and Systems Magazine - Q1 2018 - 16
IEEE Circuits and Systems Magazine - Q1 2018 - 17
IEEE Circuits and Systems Magazine - Q1 2018 - 18
IEEE Circuits and Systems Magazine - Q1 2018 - 19
IEEE Circuits and Systems Magazine - Q1 2018 - 20
IEEE Circuits and Systems Magazine - Q1 2018 - 21
IEEE Circuits and Systems Magazine - Q1 2018 - 22
IEEE Circuits and Systems Magazine - Q1 2018 - 23
IEEE Circuits and Systems Magazine - Q1 2018 - 24
IEEE Circuits and Systems Magazine - Q1 2018 - 25
IEEE Circuits and Systems Magazine - Q1 2018 - 26
IEEE Circuits and Systems Magazine - Q1 2018 - 27
IEEE Circuits and Systems Magazine - Q1 2018 - 28
IEEE Circuits and Systems Magazine - Q1 2018 - 29
IEEE Circuits and Systems Magazine - Q1 2018 - 30
IEEE Circuits and Systems Magazine - Q1 2018 - 31
IEEE Circuits and Systems Magazine - Q1 2018 - 32
IEEE Circuits and Systems Magazine - Q1 2018 - 33
IEEE Circuits and Systems Magazine - Q1 2018 - 34
IEEE Circuits and Systems Magazine - Q1 2018 - 35
IEEE Circuits and Systems Magazine - Q1 2018 - 36
IEEE Circuits and Systems Magazine - Q1 2018 - 37
IEEE Circuits and Systems Magazine - Q1 2018 - 38
IEEE Circuits and Systems Magazine - Q1 2018 - 39
IEEE Circuits and Systems Magazine - Q1 2018 - 40
IEEE Circuits and Systems Magazine - Q1 2018 - 41
IEEE Circuits and Systems Magazine - Q1 2018 - 42
IEEE Circuits and Systems Magazine - Q1 2018 - 43
IEEE Circuits and Systems Magazine - Q1 2018 - 44
IEEE Circuits and Systems Magazine - Q1 2018 - Cover3
IEEE Circuits and Systems Magazine - Q1 2018 - Cover4
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2023Q3
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2023Q2
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2023Q1
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2022Q4
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2022Q3
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2022Q2
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2022Q1
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2021Q4
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2021q3
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2021q2
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2021q1
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2020q4
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2020q3
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2020q2
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2020q1
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2019q4
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2019q3
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2019q2
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2019q1
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2018q4
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2018q3
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2018q2
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2018q1
https://www.nxtbookmedia.com