28-09-2016, 11:16 AM
An Efficient Constant Multiplier Architecture Based on Vertical-Horizontal Binary Common Sub-expression Elimination Algorithm for Reconfigurable FIR Filter Synthesis
1456545888-AnEfficientConstantMultiplierArchitecture.pdf (Size: 1.21 MB / Downloads: 18)
Abstract—This paper proposes an efficient constant multiplier
architecture based on vertical-horizontal binary common
sub-expression elimination (VHBCSE) algorithm for designing a
reconfigurable finite impulse response (FIR) filter whose coeffi-
cients can dynamically change in real time. To design an efficient
reconfigurable FIR filter, according to the proposed VHBCSE
algorithm, 2-bit binary common sub-expression elimination
(BCSE) algorithm has been applied vertically across adjacent
coefficients on the 2-D space of the coefficient matrix initially,
followed by applying variable-bit BCSE algorithm horizontally
within each coefficient. This technique is capable of reducing
the average probability of use or the switching activity of the
multiplier block adders by 6.2% and 19.6% as compared to that
of two existing 2-bit and 3-bit BCSE algorithms respectively.
ASIC implementation results of FIR filters using this multiplier
show that the proposed VHBCSE algorithm is also successful in
reducing the average power consumption by 32% and 52% along
with an improvement in the area power product (APP) by 25%
and 66% compared to those of the 2-bit and 3-bit BCSE algorithms
respectively. As regards the implementation of FIR filter,
improvements of 13% and 28% in area delay product (ADP) and
76.1% and 77.8% in power delay product (PDP) for the proposed
VHBCSE algorithm have been achieved over those of the earlier
multiple constant multiplication (MCM) algorithms, viz. faithfully
rounded truncated multiple constant multiplication/accumulation
(MCMAT) and multi-root binary partition graph (MBPG) respectively.
Efficiency shown by the results of comparing the FPGA and
ASIC implementations of the reconfigurable FIR filter designed
using VHBCSE algorithm based constant multiplier establishes
the suitability of the proposed algorithm for efficient fixed point
reconfigurable FIR filter synthesis
INTRODUCTION
F IR FILTER HAS wide application as the key component
in any digital signal processing, image and video
processing, wireless communication, and biomedical signal
processing systems. Moreover, systems like Software Defined
Radio (SDR) [1] and multi-standard video codec [2] need
a reconfigurable FIR filter with dynamically programmable
filter coefficients, interpolation factors and lengths which may
vary according to the specification of different standards in a
portable computing platform. Significant applicability of an efficient reconfigurable FIR filter motivates the system designer
to develop the chip with low cost, power, and area along with
the capability to operate at very high speed.
In any FIR filter, the multiplier is the major constraint which
defines the performance of the desired filter. Therefore, over the
past three decades, design of an efficient hardware architecture
for fixed point FIR filter has been considered as the major
research focus as reported in published literatures [3]–[14]. In
FIR filter, the multiplication operation is performed between
one particular variable (the input) and many constants (the
coefficients) and known as the multiple constant multiplication
(MCM). The algorithms proposed earlier to implement this
MCM for an efficient FIR filter design can be categorized in
two main groups: 1) graph based algorithms and 2) common
sub-expression elimination (CSE) algorithms [15]–[21]. Most
of these graph based or CSE algorithms presented earlier are
used to obtain efficient FIR filter hardware architecture by
running the algorithms on a particular (fixed) set of coefficients
for some time (a couple of hours to days) on a highly efficient
computing platform (like using 1–20 number of 3.2 GHz
computers in parallel mode as mentioned in [7]). However,
FIR filter implementation employing effective MCM design
by running these algorithms on a fixed set of coefficients is
not suitable for the application like SDR system because of
the following two reasons: 1) coefficient of the filters in SDR
system are dynamically programmable based on requirement
of different standards and 2) highly computationally efficient
platform needed for those algorithms is unaffordable in SDR
system.
Some techniques have been introduced for efficient reconfigurable
constant multiplier design [22], [23] for any application
where the filter's coefficients are changing in real time e.g.
multi-standard digital up/down converter. Binary common
sub-expression elimination (BCSE) algorithm is one of those
techniques, which introduces the concept of eliminating the
common sub-expression in binary form for designing an
efficient constant multiplier, and is thus applicable for recon-
figurable FIR filters with low complexity [13]. However, the
choice of the length of the binary common sub-expressions
(BCSs) in [13] makes the design inefficient by increasing the
adder step and the hardware cost. The efficiency in terms of
speed, power, and area of the constant multiplier has been
increased in the work presented in [14] while designing one
reconfigurable FIR filter for multi-standard DUC by choosing
2-bit long BCS judiciously.
Choice of the BCS of fixed length (3-bit or 2-bit) in the earlier
proposed BCSE algorithm based reconfigurable FIR filter designs
[13], [14] leaves a scope to optimize the designed filter by
considering the BCS across the adjacent coefficients as well as
within a single coefficient. The convention considered for representing
the input and the coefficient of the earlier designed FIR
filter [13], [14] as signed magnitude format also gives a scope
to modify the data representation to signed decimal number for
wider applicability of the proposed FIR filter in any systems.
On studying the above-mentioned literatures, it has been realized
that the development of an efficient reconfigurable constant
multiplier is very much needed for its applicability in any recon-
figurable system.
The organization of the paper is as follows. In Section II,
basic concepts along with the complexity analyses of fixed bit
BCSE (FBCSE), i.e., 2-bit and 3-bit BCSE algorithms proposed
in the earlier literatures have been discussed. The problems related
to the FBCSE algorithms and their solving techniques
proposed in this paper have been narrated in Section III. Step
wise flow chart along with the complexity analysis of the proposed
VHBCSE algorithm based constant multiplier has been
presented in Section IV. Hardware architecture of the proposed
multiplier has been described in Section V. Hardware implementation
results along with discussions on the comparison of
our results with other reported implementation have been provided
in Section VI. Finally, the paper is concluded in Section
VII.
II. CONCEPTS AND COMPLEXITY ANALYSES OF FIXED BIT
BCSE (FBCSE) ALGORITHMS
Considering the coefficients in binary pattern, the fixed bit
BCSE (FBCSE) algorithms described in [13], [14] attempt to
eliminate the redundant computation vertically by considering
3-bit or 2-bit BCS present across the adjacent coefficients. As
defined and explained in [23] and [25], horizontal BCSE algorithm
utilizes CSs occurring within each coefficient to get rid of
redundant computations, while vertical BCSE uses CSs found
across adjacent coefficients to eliminate redundant computations.
According to BCSE algorithm a total of BCSs
can be formed out of an n-bit binary number and the number of
adders required to generate the partial products for n-bit BCS
is [23]. In general, the adder step in BCSE algorithm
which defines the critical path can be calculated as ,
where n is the number of non-zero elements present within the
coefficients.
In a reconfigurable constant multiplier, the coefficient values
can be dynamically programmable. Therefore, the idea behind
the reconfigurable multiplier is to consider the worst case
(which involves the largest number of addition steps) whereby
all the relatively better cases will also be taken care of. Hence,
considering a reconfigurable multiplier having 16-bit input (X)
and the 16-bit coefficient (H), the worst case condition will
occur for the coefficient of values 16'HFF. Shift and add
based multiplication operation between the inputs (X) with this
coefficient (16'HFF) values can be written as