Adaptive precision arithmetic unit for error tolerant applications

Abstract

Two process-tolerant arithmetic circuit architectures are implemented to develop functional blocks for error-tolerant applications such as FIR filters and FFT blocks. The resulting blocks may achieve computational performance of up to 42 times higher than conventional architectures. Embodiments adaptively change the precision of the computation to achieve a high precision computation given the underlying speed of the circuit. The resulting improvement can be allocated to increasing yield or dynamically trading off between reduced power consumption, faster computation, or higher-fidelity computation.

What is claimed is: 
     
         1 . An apparatus comprising:
 multiplier-receiving circuitry to receive a multiplier;   multiplicand-receiving circuitry to receive a multiplicand;   list-generating circuitry coupled to the multiplier-receiving circuitry and the multiplicand-receiving circuitry to generate a list that includes only non-zero partial products of a binary multiplication of the multiplier and the multiplicand, wherein the list-generating circuitry generates partial products beginning with the most significant bit (MSB) of the multiplier; and   a serial adder coupled to the list-generating circuitry to add the non-zero partial products in the list.   
     
     
         2 . The apparatus of  claim 1 , further comprising circuitry to provide a clock input signal to the serial adder at a variable rate. 
     
     
         3 . The apparatus of  claim 1  wherein the serial adder comprises an asynchronous serial adder. 
     
     
         4 . The apparatus of  claim 3  wherein the asynchronous serial adder comprises:
 an adder; and 
 an accumulation register coupled to the adder, 
 wherein the adder is to perform at least one computation on the non-zero partial products in the list and to generate a signal to indicate to the accumulation register that computation is complete, 
 wherein the accumulation register is to store the latest computation completed by the adder, and 
 wherein the signal to indicate that the computation is complete is coupled to clock the latest computation into the accumulation register. 
 
     
     
         5 . The apparatus of  claim 1  wherein the serial adder comprises an adaptive synchronous serial adder. 
     
     
         6 . The apparatus of  claim 1  wherein the adaptive synchronous serial adder comprises:
 an adder; 
 a register; 
 a process monitor; and 
 a clock generator, 
 wherein the process monitor is to measure a critical path delay of the adder, 
 wherein the clock generator is to generate a clock signal having a period slightly longer than the critical path delay of the adder, 
 wherein the adder is to perform at least one computation on the non-zero partial products in the list, 
 wherein the register is to store the latest computation completed by the adder, and 
 wherein the clock signal is coupled to clock the latest computation into the accumulation register. 
 
     
     
         7 . The apparatus of  claim 6  wherein the clock generator comprises a phase-locked loop (PLL). 
     
     
         8 . The apparatus of  claim 1  wherein the list-generating circuitry comprises a Booth multiplier. 
     
     
         9 . The apparatus of  claim 1  wherein the list-generating circuitry comprises:
 a lookup table to receive the multiplier; 
 a first register coupled to an output of the lookup table; 
 reset logic, the first register having an output coupled to an input of the reset logic; 
 a finite state machine, the first register having an output coupled to an input of the finite state machine; 
 a second register having a first input coupled to an output of the reset logic and a second input coupled to a first output of the finite state machine; 
 an XOR gate having a first input coupled to receive the multiplicand and a second input coupled to a second output of the finite state machine; 
 a shifter having a first input coupled to an output of the XOR gate, a second input coupled to a third output of the finite state machine, and an output coupled to a third input of the second register; and 
 a serial accumulator having a first input coupled to an output of the second register and a second input coupled to the first output of the finite state machine. 
 
     
     
         10 . The apparatus of  claim 9  wherein the multiplier is a filter tap coefficient. 
     
     
         11 . The apparatus of  claim 1  wherein the list-generating circuitry generates partial products beginning with the most significant bit (MSB) of the multiplier and continuing in descending order of significance to the least significant bit (LSB) of the multiplier. 
     
     
         12 . The apparatus of  claim 1  wherein the list-generating circuitry generates partial products beginning with a center tap of a FIR filter. 
     
     
         13 . A method of computing a result for a filter, the method comprising:
 generating a list that includes only non-zero partial products of the binary multiplication of a multiplier and a multiplicand, wherein generating the list comprises generating partial products beginning with the most significant bit (MSB) of the multiplier; and   computing a result of the binary multiplication from the non-zero partial products in the list.   
     
     
         14 . The method of  claim 13  wherein generating the list comprises generating partial products beginning with the most significant bit (MSB) of the multiplier and continuing in descending order of significance to the least significant bit (LSB) of the multiplier. 
     
     
         15 . The method of  claim 13  wherein generating the list comprises generating partial products beginning with a center tap of a FIR filter. 
     
     
         16 . The method of  claim 13  wherein computing the result of the binary multiplication comprises:
 performing at least one computation on the non-zero partial products in the list; 
 generating a signal to indicate that computation is complete; 
 storing the latest computation completed; and 
 clocking the latest computation into an accumulation register. 
 
     
     
         17 . The method of  claim 13  wherein computing the result of the binary multiplication comprises:
 measuring a critical path delay of an adder; 
 generating a clock signal having a period slightly longer than the critical path delay of the adder; 
 using the added to perform at least one computation on the non-zero partial products in the list; 
 storing the latest computation completed by the adder; and 
 clocking the latest computation into an accumulation register. 
 
     
     
         18 . A system comprising:
 a finite impulse response (FIR) filter having:
 multiplier-receiving circuitry to receive a multiplier, 
 multiplicand-receiving circuitry to receive a multiplicand, 
 list-generating circuitry to generate a list that includes only non-zero partial products of the binary multiplication of the multiplier and the multiplicand, wherein the list-generating circuitry generates partial products beginning with the most significant bit (MSB) of the multiplier, and 
 a serial adder coupled to the list-generating circuitry to add the non-zero partial products in the list; 
   circuitry coupled to an input of the FIR filter; and   circuitry coupled to an output of the FIR filter.   
     
     
         19 . The system of  claim 18  wherein the list-generating circuitry generates partial products beginning with the most significant bit (MSB) of the multiplier and continuing in descending order of significance to the least significant bit (LSB) of the multiplier. 
     
     
         20 . The system of  claim 18  wherein the list-generating circuitry generates partial products beginning with a center tap of the FIR filter. 
     
     
         21 . The system of  claim 18  wherein the list-generating circuitry generates partial products beginning with a center tap of the FIR filter and followed by the remaining taps alternating on either side of the center tap in order of distance from the center tap. 
     
     
         22 . The system of  claim 18  wherein the list-generating circuitry generates partial products beginning with a center tap of the FIR filter followed by the remaining taps in order of decreasing absolute value. 
     
     
         23 . The system of  claim 18  wherein the circuitry coupled to the input of the FIR filter further comprises:
 a rectangular quadrature amplitude modulator (QAM) coupled to an input sequence of numbers to be filtered; 
 a cosine interpolator coupled to the rectangular QAM; and 
 an AW/GN channel coupled to the cosine interpolator. 
 
     
     
         24 . The system of  claim 18  wherein the circuitry coupled to the output of the FIR filter comprises a rectangular quadrature amplitude (QAM) demodulator.