Fast multiplierless architecture for general purpose VLSI FIR digital filters with minimized hardware

• US 4,862,402 A
• Filed: 07/24/1986
• Issued: 08/29/1989
• Est. Priority Date: 07/24/1986
• Status: Expired due to Fees

• Current Assignee: North American Philips Corp. (Koninklijke Philips N.V.)
• Original Assignee: North American Philips Corp. (Koninklijke Philips N.V.)
• Inventors: Bhattacharya, Arup K., Shah, Imran A.
• Primary Examiner(s): Harkcom, Gary V.
• Assistant Examiner(s): Shaw, Dale M.
• Application Number:
  US06/890,247
• Time in Patent Office: 1,132 Days
• Field of Search: 364/724, 364/728, 364/724.03, 364/724.12, 364/724.16, 364/728.01
• US Class Current: 708/315
• CPC Class Codes: H03H 17/0225 Measures concerning the multipliers
• CPC Class Codes: H03H 17/0233 Measures concerning the signal representation

Abstract

A digital transversal filter which employs a multiplierless algorithm for effecting convolutions of samples of a digital input word by the filter coefficients. Each of the samples of an input word is bit sliced into segments of two or more bits, and convolutions are carried out in parallel on all segments using only adders and registers. The convolution products are then summed in a pipeline adder tree to derive the convolution of the complete input word. This architecture provides high frequency capability and significantly lower transistor count and hardware complexity, enabling efficient very large scale integration (VLSI) implementation.

Claims

1. A multiplierless digital transversal filter comprising:

a first set of N registers for respectfully receiving and storing respective coefficients of a set of N filter tap coefficients C_i, where i=0, 1, . . . N-1, each coefficient having L bits in successive bit positions j, where j=0, 1, . . . , L-1;

means for receiving successive samples x_n of a digital input word X, all bits of a sample x_n being received in parallel and each such sample having M bits in successive bit positions k, where k=0, 1, . . . , M-1;

means to bit slice each input word sample x_n into a plurality of segments, each segment having a number w of bits, each segment constituting a processing plane of said filter;

means to perform a convolution of the w-bits of the bit-slice segment of each of said processing planes by said set of coefficients C_i in parallel, each segment being convolved with said set of coefficients C_i, the output of each processing plane being the convolution of the w-bits of the bit slice segment thereof and the L bits of each of said set of coefficients C_i ;

means to add the results of all said convolutions of all of said M bits of each input word sample x_n, the sum so derived being Y_n ;

means to output said sum Y_n as a filtered digital output signal sample corresponding to said input word sample x_n ; and

means for biasing the input word samples x_n and the coefficients C_i so that they represent only positive numbers, whereby said sum Y_n is derived over all four possible quadrants of the results of each of said convolutions.

2. The filter of claim 1, wherein said means to perform a convolution comprises:

multiplicaton equivalent means for determining the product of the w-bits of each of said segments by the L bits of a coefficient C_i, there being 2^w possible resultant products for each segment;

means for controlling said multiplication equivalent means to select one of said 2^w possible products for each of said segments;

means for sequentially adding the selected products of a segment by each of said coefficients, such additions being performed in parallel for said plurality of segments;

means for adding the sums of said sequential additions for all of said segments; and

means to output said final sum as a filtered digital output signal.

3. The filter of claim 2 further comprising:

a second set of registers; and

means to precalculate and store in said second set of registers a subset of the total number of product of the w-bits of each of said segments of said input word sample x_n and the L bits of each of said set of coefficients C_i.

4. The filter of claim 3 wherein said subset of products is precalculated and stored in said second set of registers simultaneously with the loading of the set of coefficients C_i in said first set of registers.

5. The filter of claim 2 wherein said means to selecte a product comprises:

means to shift the bits of each coefficient C_i to obtain even multiples of such coefficient;

means to store precalculated odd multiples of C_i ;

respective decoders for the respective bit-slice segment processing planes of said filter, each such decoder translating the w-bits of such bit-slice segment into 2^w respective outputs representing 2^w possible products of a multiplication of the w-bits of such bit-slice segment by C_i ; and

respective tristate multiplexers each having one gate level, regardless of the number of bits w in a bit-slice segment, each connected to the output of a respective decoder for selecting one of said 2^w possible products.

6. The filter of claim 2, wherein said multiplication equivalent means comprises:

respective decoders for the respective bit slice planes of said filter, each such decoder translating the w-bits of such bit-slice into a number 2^w of respective outputs representing 2^w possible products of a multiplicaton of the w-bits of a bit-slice by C_i ;

respective tristate multiplexers each having one gate level, regardless of the number of bits w in a bit-slice, each connected to the output of a respective decoder for selecting one of said 2^w possible products; and

delay means respectively connected to the outputs of the respective multiplexers for delaying the selected products produced at the outputs thereof.

7. The filter of claim 1 wherein said means to perform a w-bit convolution comprises:

means to multiply the w bits of a bit-slice segment by a coefficient C_i, there being 2^w possible resultant products thereof, such multiplying means producing even multiples of C_i by shifting the bits thereof;

means to precalculate and store odd multiples of Ci and supply such odd multiples to said multiplying means;

means for controlling said multiplying means to select one of said 2^w possible products for each of said segments;

means to sequentially add the selected products of a segment by each of said coefficients, such additions taking place in parallel;

means to add the sums of said sequential additions for all of said segments; and

means to output said final sum as a filtered digital output signal.

8. The filter of claim 1, wherein said means to add the results of said convolutions is a pipeline adder tree.

9. The filter of claim 8, wherein said pipeline adder tree comprises:

means to calculate the Y_n,k outputs of the additions of all of said filter planes and shift such outputs in accordance with the significance of the bits thereof, such shifts being related to the variable k in accordance with the equation ##EQU19## in which a, b, . . . d are integers such that a<

b<

. . . <

d<

M-1 and in which. ##EQU20##

10. The filter of claim 9, wherein said pipe line adder tree comprises a plurality of half adders and full adders.