Efficient filter implementation

Details Efficient filter implementation Efficient filter implementation

1998-08-10

2002-06-25

Ngo, Ohuong Dinh (Department: 2121)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

Reexamination Certificate

active

06411976

ABSTRACT:

TECHNICAL FIELD
This invention relates to digital filters useful in environments where power consumption must be reduced such as in wireless telephone systems, and, more particularly, in code division multiple access (CDMA) wireless telephone terminals.
BACKGROUND OF THE INVENTION
Finite impulse response (FIR) filters can be implemented in several forms, the most popular of which are the transversal and direct implementations. An FIR filter of order N performs the dot product of a received sample vector [y(n)] and a filter coefficient vector [X(n)], both of length N. The received filter vector, made up of values stored in registers (memory elements) of the filter, is updated each clock cycle by eliminating the oldest value in the vector, shifting the received filter vector values toward the position of the eliminated value, and appending the new filter value at the opposite end of the received filter vector. The successive dot products create an FIR convolution.
More specifically, when a transversal filter is implemented with filter coefficients (tap weight vectors) that are either −1 or 1, the output function, C
n
, of the filter may be mathematically described by the equation:
C
n
=
∑
k
=
0
N
-
1
⁢
y
⁡
(
n
-
k
)
·
x
⁡
(
k
)
eq
.
 
⁢
1
where, C
n
is the filter output; y(n−k) is the filter input at time n−k; x(k) is the filter coefficient for the k
th
stage of the filter; and N is the number of stages in the filter; with each stage including at least one multiplier. At each clock cycle, for each stage of the filter, the incoming sample is multiplied by the filter coefficient for that stage. Each resulting product, which is the weighted sample input for a stage, is added to the value of its respective preceding stage of the filter, or zero if there is no preceding stage, and stored for use on the next clock cycle.
FIG. 1
shows an exemplary, prior art, N-stage transversal filter for performing such FIR filtering with coefficients that are either −1 or 1. Each stage includes a two input multiplier (
101
i
), a register (
105
i
) and a two input port adder (
103
i
). Each multiplier
101
i
multiplies an incoming sample y(n) with a respective one of filter coefficients X
0
through X
N−1
. The output of each multiplier
101
i
is supplied to an input port of a corresponding adder
103
i
, except for the output of multiplier
101
-N receiving coefficient X
N−1
, whose output is supplied directly to the input of register
105
(N−1) furthest from output C
n
. The output of multiplier
101
-N, receiving coefficient X
N−1
is supplied directly to the input of register
105
(N−1) because there is no prior stage of the filter to feed into this stage, and so, if this stage had an adder, its inputs would be the sample and 0, which renders its function unnecessary. One input port of each adder (
103
i
) is supplied with the output of its corresponding multiplier (
101
i
), and the other input port is supplied with the output that was stored during the immediately preceding clock cycle in its corresponding register
105
i.
The adder
103
i
of each stage sums the outputs of its multiplier
101
i
and the outputs of its associated register
105
i
. The output port of each adder is connected to the input port of the next register
105
along the filter chain towards the output C
n
.
To implement the output function C
n
of eq. 1, the input samples [y(n)] are multiplied by filter coefficients [X(n)] selected to be either 1 or −1. To effectuate this computation using a two's complement operation results in several problems associated with the circuit of
FIG. 1
, which may be explained by reference to
FIGS. 1A
,
1
B,
1
C and
1
D and by noting that each input sample is comprised of a number of bits. For purpose of illustration, it is assumed that each input sample consists of 4 bits (e.g., A
0
, A
1
, A
2
, A
3
). Note also that in order to multiply the input samples by filter coefficients of 1 and −1, each multiplier
101
must include, for each bit being multiplied, a summing circuit,
12
, and a carry circuit,
13
, as shown for blocks
11
a
,
11
b
,
11
c
, and
11
d
in FIG.
1
A. The summing circuit
12
, for each multiplier bit, may be implemented as shown in FIG.
1
B and the carry circuit
13
, for each multiplier bit, may be implemented as shown in FIG.
1
C.
Furthermore, as shown in
FIG. 1D
, each multiplier
101
i
may be required to have five outputs; i.e., one output for each of the four bits and one output for the carry. This requires that even the left most register (
105
-N−1) in
FIG. 1
may need five inputs. Consequently, even register
105
-N−1 may need to have five (5) outputs coupled to the next adder down the line. The next adder down the line must be capable of adding the outputs of its associated register and the outputs of its associated multiplier resulting in an increasing number of outputs being supplied down the filter chain. Hence, as a result, the size of the adders and registers along the filter chain increase and, where a filter has a large number of stages, the size of the adders and registers may increase substantially.
Therefore it is evident from
FIGS. 1A
,
1
B,
1
C and
1
D that the multiplier circuitry for enabling multiplication by coefficients which are 1 or −1 is highly complex. It should also be noted that a significant amount of power is dissipated in the multiplier circuit due to the substantial amount of switching being performed by the highly complex circuitry. In addition, there is also a significant amount of switching and ensuing power dissipation in the adder circuits (
103
-
i
) along the filter chain.
By way of example, it may be desirable to form these filter circuits using complementary metal oxide semiconductor (CMOS) components because of their extremely low power consumption; i.e., they do not consume power when the bit values in the circuits are constant. However, when CMOS circuits are switched (toggled) in value, i.e., changed from 0 to 1 or from 1 to 0, power is consumed. Applicants recognized that when the filter coefficients call for multiplication by −1, as is required by the prior art filter, many bits are caused to change in value. So does the rippling of changes in bit values while adders
103
perform their calculations. All of these bit changes cause a substantial amount of power consumption even when the circuits of
FIG. 1
are implemented using CMOS components.
Moreover, in the case where noise is expected at the output of the filter, the values at the intermediate stages in the prior art filter will be in the neighborhood of zero, and so the values are often changing between small positive and negative values. These changes in value result in a large number of the bits which are used to represent the values toggling from 0 to 1 or from 1 to 0. This toggling causes power consumption even when the circuits of
FIG. 1
are implemented using CMOS circuitry.
SUMMARY OF THE INVENTION
Applicants recognized that a high level of circuit complexity and a high degree of power dissipation exists in the filter circuit formed in accordance with the prior art because the filter coefficients (or tap weight vectors) were selected to be either 1 or −1.
Applicants' invention resides, in part, in the recognition that the multipliers (
101
) in the circuit of
FIG. 1
may be greatly simplified with much power savings and that the power dissipated in the adders (
103
) may also be greatly reduced by having a first filter section whose filter coefficients are made either 1 or zero (rather than 1 and −1) in order to produce a first output (i.e., C1) and by adding a compensation network for producing a second output (i.e., C2), which when combined (added to or subtracted from) with the first output produces the output function (i.e., C
n
) of equation 1, above.
Applicants invention also resides, in part, in the recognition that equation 1 may be recast

Affiliated with

Also associated with

Rating

Efficient filter implementation does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Efficient filter implementation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient filter implementation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2895091