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: 4)

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