Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2002-08-09
2003-06-24
Ngo, Chuong Dinh (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06584481
ABSTRACT:
FIELD OF THE INVENTION
The present invention generally relates to digital infinite impulse response (IIR) filters, and more particularly to the implementation of an IIR filter on a field programmable gate array (FPGA).
BACKGROUND
An example programmable logic device (PLD) is the field programmable gate array (FPGA), first introduced by Xilinx in 1985. PLDs such as FPGAs are becoming increasingly popular for use in electronics systems. For example, communications systems employ FPGAs in large measure for their re-programmability. In general, the use of FPGAs continues to grow at a rapid rate because they permit relatively short design cycles, reduce costs through logic consolidation, and offer flexibility in their re-programmability. The capabilities of and specifications for Xilinx FPGAs are set forth in “The Programmable Logic Data Book,” published in 1999 by Xilinx, Inc., pp. 3-3 through 3-22.
Advances in semiconductor process technology are delivering FPGAs having logic densities in the range of a million system gates and having operating speeds in excess of 100 MHz. These powerful devices are capable of and have been used to implement digital signal processing (DSP) algorithms which are inherently parallel and normally require multiple DSP microprocessors in order to meet the high data rates. It is feasible to implement such algorithms on a single FPGA because such devices offer a programmable parallel architecture.
For applications requiring sample rates in the range of tens of MHz, for example, radar, HDTV, and digital video broadcasting, the consolidation of multiple DSP microprocessors into a single FPGA has been popular for economic as well as performance reasons. However, applications requiring lower sample rates in the range of tens of kHz (for example, industrial digital control systems, servo-motor controllers, and pick-and-place controllers) have not realized the benefit of DSP algorithms implemented on FPGAs. The lack of implementations of DSPs on FPGAs for low sample rate applications may partially be a result of economics. Sequential, low-cost DSPs provide designers with solutions for low sample rate applications, while FPGAs would require a new design methodology, new designs, and marginal cost advantages if FPGA resources are not used efficiently.
Filters are key elements in digital controller technology, and IIR structures are often chosen as the implementation. Filters are used, for example, for low pass and band pass filtering to remove the effects of EMF induced noise. Many fixed-point DSP processors are available to implement IIR filters. However, many of the economical fixed-point DSP processors are 16-bit processors which limits the precision achievable with the filter.
FIR filters often require a large number of taps as compared to IIR filters, thereby requiring many DSP processor clock cycles. However, this can be addressed with higher performance DSP processors. FIR filters can alternatively be implemented on FPGAs. However, memory to store the samples for many taps becomes the limiting factor in implementing large order FIR filters on FPGAs. Thus, the solution often chosen is procuring a faster DSP processor.
IIR filters can be used in place of FIR filters, and they require far fewer taps. In addition, when a sample is input to a FIR filter, there will be a number of system level delays (each delay period denoted as Z
−1
) before the input sample influences the output. A sample input to an IIR filter, in contrast, influences the output immediately. In an IIR filter, an input sample value is scaled by a single coefficient, usually close to 1.0. Therefore, a large portion of the newest sample has an immediate effect on the output. However, IIR filters require much greater precision to maintain stability. In view of the cost of high precision DSPS, IIR filters are less often implemented on DSPs.
While an FPGA possesses all the resources required to implement a cost-effective IIR filter that meets low sample rate performance objectives, an FPGA design is generally not chosen because it is not understood how to implement an IIR filter on an FPGA in a manner that uses resources efficiently. An apparatus that address the aforementioned problems, as well as other related problems, is therefore desirable.
SUMMARY OF THE INVENTION
In various embodiments, the invention provides an FPGA implementation of a bit-serial multiplier and an IIR filter implemented therewith. In accordance with one embodiment, a bit-serial multiplier implemented on an FPGA is provided. The bit-serial multiplier comprises function generators configured as multiplicand, multiplier, and product memories. A 2's-complement 1×1 bit multiplier is implemented with at least two function generators and is coupled to the multiplier and multiplicand memories. A 1×1 bit adder is implemented with at least two function generators and is coupled to the output of the multiplier. The adder accumulates partial results in the product memory. A control circuit is coupled to address inputs of the multiplicand, multiplier, and product memories.
In another embodiment, an n-order infinite impulse response filter is implemented in an FPGA. The filter is comprised of n function generators configured as sample memories. A first one of the sample memories is configured with a data input to receive a sample input value, and others of the sample memories serially coupled with data outputs coupled to data inputs. Another n−1 function generators are configured as feedback memories. A first one of the feedback memories is configured with a data input to receive a feedback input value, and others of the feedback memories are serially coupled with data outputs coupled to data inputs. An additional 2n−1 function generators are configured as coefficient memories, and another 2n−1 function generators are configured as bit-serial multipliers, each coupled to outputs of a respective sample/coefficient memory pair and feedback/coefficient memory pair. The multipliers coupled to sample/coefficient memory pairs are sample multipliers, and the multipliers coupled to the feedback/coefficient memory pairs are feedback multipliers. Another 2n−1 function generators are configured as bit-serial adders. A feed-forward chain includes n−1 of the bit-serial adders coupled with the sample multipliers, and n−1 others of the bit-serial adders are coupled with the feedback multipliers as a feedback chain. A first adder of the feed-forward chain is coupled to outputs of two of the sample multipliers, a first adder of the feedback chain is coupled to outputs of two of the feedback multipliers, others of the adders in the feed-forward chain are coupled to respective outputs of multiplier/adder pairs in the feed-forward chain, and others of the adders in the feedback chain are coupled to respective outputs of multiplier/adder pairs in the feedback chain. One of the adders is coupled to a last adder in the feed-forward chain and a last adder in the feedback chain. A scaling accumulator is implemented with a plurality of function generators and includes an adder and a memory. The adder of the accumulator has a data input coupled to the output of the one adder and an output coupled to the memory of the accumulator and to a first one of the feedback memories, and the memory of the accumulator has an output coupled to an input of the adder of the accumulator. A control circuit is arranged to address the sample, coefficient, and feedback memories and the memory of the accumulator.
REFERENCES:
patent: 3633014 (1972-01-01), Lemp et al.
patent: 3714402 (1973-01-01), Baumwolspiner
patent: 3777130 (1973-12-01), Croisier et al.
patent: 4569031 (1986-02-01), Backes
patent: 4680727 (1987-07-01), White
patent: 4839847 (1989-06-01), Laprade
patent: 4860240 (1989-08-01), Hartley et al.
patent: 4970674 (1990-11-01), White
patent: 4970676 (1990-11-01), Fling
patent: 4994997 (1991-02-01), Martin et al.
patent: 5033019 (1991-07-01), White
patent: 5034909 (1991-07-01), Hartley
patent: 5339265 (1994-08-01)
Maunu LeRoy D.
Ngo Chuong Dinh
Xilinx , Inc.
Young Edel M.
LandOfFree
FPGA implemented bit-serial multiplier and infinite impulse... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with FPGA implemented bit-serial multiplier and infinite impulse..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and FPGA implemented bit-serial multiplier and infinite impulse... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3120042