Abstract:
A multiply accumulate unit processes a signal according to a sum-of-products function based upon a plurality of multibit sampled values and a corresponding plurality of multibit constants. A multiply-add block receives the sampled values and the constants. A portion of each constant is selected. A plurality of multipliers multiple sampled values and selected portions of the corresponding constants. The products are added and shifted corresponding to the significance of the selected portion of the constants. These are added to generate a sum of sequential outputs of the multiply-add block. The multiply accumulate unit repeats operation employing the same sample values but portions of said corresponding constants having sequentially less significant bits. This sequence repeats until the sum of all prior sum-of-products functions has a desired level of accuracy.

Description:
This application claims priority under 35 U.S.C. § 119 of provisional application Ser. No. 60/013,954, filed Mar. 22, 1996. 
    
    
     TECHNICAL FIELD OF THE INVENTION 
     This invention relates in general to the field of electronic circuits, and more particularly to a multiply accumulate unit for processing a signal and a method of operation. 
     BACKGROUND OF THE INVENTION 
     Processing a signal by determining the result of a sum-of-products function often is important to the operation of digital signal processors and forms the basis for transforms used in MPEG algorithms and used by various filters. A sum-of-products function generally comprises calculating results of the form: 
     
         Y=(C.sub.0 *X.sub.0)+(C.sub.1 *X.sub.1)+(C.sub.2 *X.sub.2) 
    
     where (C 0 ,C 1 ,C 2 , . . . ) are constants and (X 0 ,X 1 ,X 2 , . . . ) are values sampled from a signal being processed. Often, the constants (C 0 ,C 1 ,C 2 . . . ) are fixed numbers, but sometimes they are allowed to vary. 
     Determining the result of a sum-of-products function is typically accomplished using a multiply accumulate unit which comprises a multiplier and an adder. In a conventional multiply accumulate unit, the multiplier and adder are used in sequence to compute a product of each term (C i  *X i )and to add that product to a partial sum such that a new term is added each cycle. The result Y is valid only after all terms have been added, and truncated if necessary. The number of cycles needed for the computation is hence independent of the accuracy required. 
     In some custom implementations, noting that multiplication can be accomplished using a set of adders, an optimized structure can be obtained by deleting adders associated with zero bits in the coefficients (C 0 ,C 1 ,C 2 , . . . ). Coefficients (C 0 ,C 1 ,C 2 , . . . ) can also be chosen to contain a large number of zeroes if the application permits. Many circuits also make use of the fact that subtraction is as efficient as addition and use canonical signed digit representation (CSD) for the constants (C 0 ,C 1 ,C 2 , . . . ) to reduce the number of adders required in the circuit. This reduction in adders allows a reduction of the size of the circuit. 
     However, these implementations suffer from the problem that in order to provide a result they need enough cycles to calculate each term (C i  *X i ) irrespective of the needed accuracy of the results. 
     SUMMARY OF THE INVENTION 
     In accordance with the present invention, a multiply accumulate unit for processing a signal and a method of operation are provided that substantially eliminate or reduce disadvantages and problems associated with prior electronic circuits. 
     According to one embodiment of the present invention, a multiply accumulate unit is provided for processing a signal according to a sum-of-products function based upon a plurality of sampled values and a corresponding plurality of constants. The multiply accumulate unit includes a first-order block operable to receive the plurality of sampled values. The first-order block is further operable to generate a first-order approximation of the sum-of-products function and to provide an output representing the first-order approximation where the sum-of-products function is characterized by the plurality of constants. A correction block is also operable to receive the plurality of sampled values. The correction block is further operable to generate a correction to the first-order approximation and to provide an output representing the correction. An adder is coupled to receive the output of the first-order block and the output of the correction block. The adder is operable to provide an output representing the sum of the first-order approximation and the correction such that the output provides a result of processing the signal according to the sum-of-products function. 
     According to another embodiment of the present invention, a multiply accumulate unit is provided for processing a signal according to a sum-of-products function based upon a plurality of sampled values and a corresponding plurality of constants. The multiply accumulate unit includes a multiply-add block which is operable to receive the plurality of sampled values and to receive a portion of each of the plurality of constants. The multiply-add block is further operable to provide an output representing a sum of each sampled value multiplied by the portion of a corresponding constant. An adder is coupled to receive the output of the multiply-add block and is operable to generate a sum of sequential outputs of the multiply-add block. The adder is further operable to provide an output representing the sum of sequential outputs of the multiply-add block such that the output provides a result of processing the signal according to the sum-of-products function. 
     The processing of a signal according to a sum-of-products functions by generating a series of approximations is a technical advantage of the present invention. This approach allows specifiable accuracy and selection of higher speed or less silicon area versus accuracy as a design trade-off. 
     Another technical advantage of the present is the use of a double adder structure and adaptive multiplication factors compatible with product form realization to implement a multiply accumulate unit for processing a signal. 
     A further technical advantage of the present invention is a reduced die area, higher speed and lower power multiply accumulate unit. The present invention is beneficial to devices such as digital signal processors, MPEG filters, HDTV and telecommunication devices, and analog-to-digital converters. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     A more complete understanding of the present invention and advantages thereof may be acquired by referring to the following description taken in conjunction with the accompanying drawings in which like reference numbers indicate like features and wherein: 
     FIG. 1 is a graphical representation of a result of a sum-of-products function; 
     FIG. 2 is a block diagram of one embodiment of a multiply accumulate unit for processing a signal, constructed according to the teachings of the present invention; 
     FIGS. 3A and 3B are graphical representations of one embodiment of the first-order approximation and correction implemented by the multiply accumulate unit of FIG. 2; 
     FIG. 4 a block diagram of one implementation of the multiply accumulate unit shown in FIG. 2; 
     FIG. 5 is a block diagram of another implementation of the multiply accumulate unit shown in FIG. 2; and 
     FIG. 6 is a block diagram of another embodiment of a multiply accumulate unit for processing a signal, constructed according to the teachings of the present invention. 
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     FIG. 1 is a graphical representation of a result of a sum-of-products function. As shown in FIG. 1, the result of the following sum-of-products function. 
     
         Y=C.sub.0 X.sub.0 +C.sub.1 X.sub.1 +C.sub.2 X.sub.2 + . . . 
    
     can be represented graphically as the area formed by rectangles of sides X i  and C i . According to the teachings of the present invention, an efficient realization of this area is used to develop a multiply accumulate unit that efficiently determines the result of such a sum-of-products function. According to the present invention, the result can be determined to an appropriate level of accuracy using a smaller circuit area and less power. 
     In general, sum-of-products functions are widely used to implement desired processing of sampled signals. The constants (C 0 ,C 1 ,C 2 , . . . ) are selected to provide the appropriate signal processing of the sample values (X 0 ,X 1 ,X 2 , . . . ). According to the teachings of the present invention, the precise mathematical result of the sum-of-products function is recognized as more accurate than necessary for many applications. The present invention provides a multiply accumulate unit that can resolve a sum-of-products function to a desired level of accuracy while providing benefits over conventional multiply accumulate units in terms of physical layout and operating speed. 
     FIG. 2 is a block diagram of one embodiment of a multiply accumulate unit for processing a signal, indicated generally at 10, constructed according to the teachings of the present invention. Multiply accumulate unit 10 receives sample values (X 0 ,X 1 ,X 2 ,X 3 , . . . ), sampled from a signal being processed. Multiply accumulate unit 10 operates to provide an output Y&#39; which represents an approximation of the result Y of a sum-of-products function such as that shown in FIG. 1. 
     A first-order block 12 and a correction block 14 receive the sample values (X 0 ,X 1 ,X 2 ,X 3 , . . . ). First-order block 12 comprises an integer implementation circuit 16 which receives the sample values (X 0 ,X 1 ,X 2 ,X 3 , . . . ) and provides an output to a number transform circuit 18. Number transform circuit 18 provides an output, Y 1 , of first-order block 12. The output, Y 1 , comprises a first-order approximation of the sum-of-products function of FIG. 1. 
     Correction block 14 comprises an integer implementation circuit 20 which receives the sample values (X 0 ,X 1 ,X 2 ,X 3 , . . . ). Integer implementation circuit 20 provides an output to a number transform circuit 22. Number transform circuit 22 provides an output, Y 2 , of correction block 14. The output, Y 2 , comprises a correction to the first-order approximation provided by Y 1 . 
     An adder circuit 24 receives the output, Y 1 , of first-order block 12 and the output, Y 2 , of correction block 14. Adder circuit 24 adds Y 1  and Y 2  and provides an output, Y&#39;, of multiply accumulate unit 10. 
     In operation, first-order block 12 operates to generate Y 1  as a first-order approximation of the area shown in FIG. 1. Correction block 14 operates to generate Y 2  as a correction to Y 1 . Adder circuit 24 then adds the first-order approximation, Y 1 , and the correction, Y 2 , to provide an output Y&#39;. It should be understood that additional correction blocks could be added to provide further correction such that the output Y&#39; would more accurately represent the result Y of the sum-of-products function of FIG. 1. Correction units could be added until a desired accuracy is achieved. 
     Multiply accumulate unit 10 provides a technical advantage in that integer implementation circuits 16 and 20 and number transform circuits 18 and 22 can be implemented using adders and shifters and without multipliers. 
     FIGS. 3A and 3B are graphical representations of one embodiment of the first order approximation, Y 1 , and the correction, Y 2 , implemented by multiply accumulate unit 10 of FIG. 2. FIGS. 3A and 3B limit the terms of the sum-of-products function at C 3  X 3  for purposes of explanation. It should be understood that fewer or more terms could be implemented. 
     As shown in FIG. 3A, the area of FIG. 1 can be conceptualized as horizontal rectangles rather than vertical rectangles. According to the teachings of the present invention, the area of the horizontal rectangles can be approximated by multiply accumulate unit 10 to efficiently determine a result of the sum-of-products function to a desired level of accuracy. 
     As shown in FIG. 3A, the constants (C 0 ,C 1 ,C 2 ,C 3 ) can be approximated as integer multiples of C 3  &#39;, which is an approximation of C 3 . In this manner, Y 1  can be implemented as the function shown in FIG. 3A. This approximation allows C 3  &#39; to be selected as a multiplication factor easily implemented in shift registers and adders and allows the integer multiples of the sample values (X 0 ,X 1 ,X 2 ,X 3 , . . . ) to be implemented in double adder structures. 
     FIG. 3B is a graphical representation of the error from the approximation, Y 1 , of FIG. 3A. In FIG. 3B, the constants (D 0 ,D 1 ,D 2 ,D 3 ) represent the difference between the constants (C 0 ,C 1 ,C 2 ,C 3 ) and the approximation provided by C 3  &#39; and multiples of C 3  &#39;. 
     The correction, Y 2 , can similarly be implemented as an approximation of the actual area shown in FIG. 3B. An approximation D 3  &#39; of the constant D 3  can be used to realize Y 2  in a manner similar to the approximation of FIG. 3A. Using the same principles, further corrections could be implemented to correct any error in the value of Y 2 . However, for purposes of description, a first-order approximation and one correction are described. 
     FIG. 4 is a block diagram of one implementation of first-order block 12 of FIG. 2 according to the approximation shown in FIG. 3A. According to the teachings of the present invention, integer implementation circuit 16 has a double adder structure. 
     A first adder 30 receives the sample value X 0  and receives the shifted output of a second adder 32. Adder 32 receives the sample values X 0  and X 1 . The output of adder 32 is shifted to the left once by shift register 34 such that the input to adder 30 is 2(X 0  +X 1 ). A third adder 36 receives sample value X 2  and receives the output of adder 32. A fourth adder 38 receives the output of adder 30 and adder 36. A fifth adder 40 receives the sample value X 3  and the output of adder 36. Lastly, an adder 42 receives the output of adder 38 and adder 40. 
     The result of the double adder structure of integer implementation circuit 16 is the generation of the sum of integer multiples of the sample values (X 0 ,X 1 ,X 2 ,X 3 ), as shown. The sum shown as the output of integer implementation circuit 16 is the factor shown in FIG. 3A which is multiplied by the constant C 3  &#39;. 
     Number transform circuit 18 receives the output of integer implementation circuit 16 and transforms that output to provide output Y 1 . Number transform circuit 18 transforms the output of integer implementation circuit 16 to represent multiplication by the constant C 3  &#39;. According to the teachings of the present invention, number transform circuit 18 does not use multipliers. Due to the choice of C 3  &#39;, number transform circuit 18 can comprise shift registers and adders. 
     C 3  &#39; can be chosen in order to realize the first-order approximation, Y 1 , by allowing the values of constants (C 0 ,C 1 , . . . ,C i ) to be relaxed and to vary. A binary number can be chosen such that it is an integral divisor into constants (C 0 ,C 1 , . . . ,C i ) with as small a range of quotient as possible and it can be easily realized as a product of the form (1+-1/2 m1 )*(1+-1/2 m2 ). For example, 
     
         C.sub.1 =C.sub.1 &#39;(1/2.sup.m0)*(1+-1/2.sup.m1)*(1+-1/2.sup.m2) 
    
     
         C.sub.0 &#39;=I.sub.0 *N.sub.0 
    
     
         C.sub.1 &#39;=I.sub.1 *N.sub.0 
    
     
         C.sub.2 &#39;=I.sub.2 *N.sub.0 
    
     where, I 0 ,I 1 ,I 2  are small integers; and C 0  &#39;,C 1  &#39;, . . . ,C i  &#39; are approximations of C 0 ,C 1 , . . . ,C i . The form of C 1  can be contrasted with binary numbers which typically are represented as 
     
         N=(1/2.sup.m0)*(1+-1/2.sup.m1 +-1/2.sup.m2 ) 
    
     It should be noted that wiring resource requirements to implement the expression for C 1  is less while maintaining the same number of adder bits. There is a trade-off in the complexity of C 1  compared to the number of adder bits required to realize I 0 ,I 1 , . . . ,I i . However, the integer sum-of-products can benefit from a coupled adder structure like that shown in FIG. 4. 
     The double adder structure is advantageous in that the overall delay is less than the product of delay of an adder and a number of stages. In fact a carry wave is generated that makes the overall delay that of (N+BW) one bit adders, where N is the number of stages and BW is the bit-width of the resulting word. This structure enjoys good track sharing and small interconnect length. Low power circuits are possible due to small fan-out and the local nature of blocks. 
     Once the computation of the first-order approximation is completed, correction circuits can be designed using essentially the same method. A new number that is an approximate common factor of residues and realizable as a product of (1+/-1/2 m ) terms and shifts is used to realize corrections. Additional advantages can be realized by keeping the word-width as small as possible. This tends to reduce power and active area. However, area of the overall cell may be determined by the largest bit-width and not affected as much. The present invention allows a synthesis procedure that leads to low power implementation of a multiply accumulate unit and is useful in realizing many devices used to process signal samples. 
     An example implementation is provided below and is based upon part of IDCT that is used in MPEG. A multiply accumulate unit used in IDCT can be described as follows: ##EQU1## If a number for representing the first-order approximation is chosen to be C 4&#39;=  0.2, it can be seen that 
     
         Y.sub.1 =C.sub.4 &#39;*(5*X.sub.1 +4*X.sub.2 +3*X.sub.3 +X.sub.4) 
    
     is a good first approximation. 
     In addition, (1/8)*(1+1/2)*(1+1/16)=0.19922 is a relatively accurate representation of C 4  &#39;. So, Y can be rewritten as ##EQU2## 
     As an approximation of Y 2 , it can be seen that the multiplicand of X 2  is (2.25*0.01531) and that of X 3  is (2.75*0.01531) and that of X 4 , (0.25*0.01531). By taking a weighted average, the factor of 3.844e -3  can be used as an overall multiplication factor. In the interest of realizability, (1-1/64)/256=3.84521e -3  is a reasonable implementation. Using this, Y 2  can be implemented as: ##EQU3## 
     If needed, the same procedure can be used to implement Y 3 . However, there is often an allowable error that would make it unnecessary to further correct the result. This can be true in devices where, using realizability as a criterion, a limited space of coefficients can be searched to get desired performance. One embodiment of a circuit implementation of the function Y&#39;=Y 1  +Y 2 , as set forth above, is shown in FIG. 5. 
     FIG. 5 is a block diagram of an implementation of multiply accumulate unit 10 constructed according to the teachings of the present invention. The multiply accumulate unit of FIG. 5 includes first-order block 12 and correction block 14. First-order block 12 and correction block 14 comprise integer implementation circuits 16 and 20 and number transform circuits 18 and 22, respectively. 
     Integer implementation circuit 16 comprises six adders interconnected in a double adder structure. Adder 50 receives sample values X 1  and X 2  and provides an output to adder 52 and adder 54. Adder 52 receives sample value X 1  and the output of adder 50. Adder 54 receives the output of adder 50 and sample value X 3 . Adder 56 receives the output of adder 52 and the shifted output of adder 54. Adder 58 receives the output of adder 54 and sample value X 4 . Lastly, adder 60 receives the output of adder 56 and the output of adder 58. Integer implementation circuit 16 provides an output representing the sum of integer multiples of sample values (X 1 ,X 2 ,X 3 ,X 4 ) as described above for Y 1 . 
     Number transform circuit 18 receives the output of integer implementation circuit 16. Number transform circuit 18 comprises adder 62 which adds the output of adder 60 and the shifted output of adder 60. In this manner, adder 62 implements a multiplication of the output of adder 60 by a factor of (1+1/2). Similarly, adder 64 adds the output of adder 62 and the shifted output of adder 62 to implement a multiplication by a factor of (1+1/16). Lastly, the output of adder 64 is shifted to the right to implement a multiplication by a factor of (1/8). Thus, number transformer circuit 18 implements multiplication by a factor of (1/8)(1+1/2)(1+1/16) without the use of a multiplier. The resulting output of number transform circuit 18, Y 1 , is provided to adder 24 and represents a first-order approximation as described above. 
     Integer implementation circuit 20 of correction block 14 comprises five adders and a subtractor. Subtractor 70 receives sample values X 3  and X 2  and subtracts X 2  from X 3 . Adder 72 receives the output of subtractor 70 and receives sample value X 3 . Adder 74 receives sample value X 1  and the output of subtractor 70. Adder 76 receives the output of adder 72 and the output of adder 74. Adder 76 receives sample value X 4  and the output of subtractor 70. Lastly, adder 80 receives the shifted output of adder 76 and the output of adder 78. Integer implementation circuit 20 produces an output comprising integer multiples of the sample values (X 1 ,X 2 ,X 3 ,X 4 ) according to the correction, Y 2 , described above. The output of integer implementation circuit 20 is provided to number transform circuit 22. 
     Number transform circuit 22 comprises a subtractor 82 that receives the output of adder 80 and the shifted output of adder 80. Subtractor 82 implements a multiplication of the output of adder 80 by a factor of (1-1/64). Number transform circuit 22 then shifts the output of subtractor 82 to the right such that multiplication by a factor of (1/256) is implemented. The output, Y 2 , of correction block 14 implements a correction to the output of first-order block 12 as described above. The output, Y 2 , is provided to adder 24 which adds Y 1  and Y 2  together to provide the output Y&#39;. 
     Assuming X i  are 12 bits, for example, an analysis of the number of bits required at each stage can be performed to build the stages with only the required width, thus saving power. The bit sizes shown in FIG. 5 provide an example of such a bit width analysis. The loading on X i  is also reduced compared to conventional use of a multiplier. Delay can be estimated as a carry propagation of 16+8 bits of addition. For area estimation, besides the area of adders, the area associated with large shifts is also included. It should be understood that the implementation of FIG. 5 is not unique, and a synthesis program could be used to search the feasibility region to arrive at a better implementation. 
     FIG. 6 is a block diagram of another embodiment of a multiply accumulate unit for processing a signal, indicated generally at 100, constructed according to the teachings of the present invention. Multiply accumulate unit 100 has an architecture suitable for applications where coefficients need to be changed and is appropriate for use in a programmable device such as a digital signal processor. 
     According to the teachings of the present invention, multiply accumulate unit 100 receives sample values (X 0 ,X 1 ,X 2 ,X 3 ) in parallel along with a portion of corresponding constants (C 0 ,C 1 ,C 2 ,C 3 ) . This use of full sample values (X 0 ,X 1 ,X 2 ,X 3 ) in parallel accompanied by discrete portions of the constants (C 0 ,C 1 ,C 2 ,C 3 ) provides a technical advantage in terms of selectability of accuracy, speed and size of multiply accumulate unit 100. As shown in FIG. 6, multiply accumulate unit 100 comprises a multiply-add block 102. 
     Multiply-add block 102 receives the sample values (X 0 ,X 1 ,X 2 ,X 3 ). A first multiplier 104 receives sample value X 0  and receives a portion of a corresponding constant C 0 . In the illustrated embodiment, each constant (C 0 ,C 1 ,C 2 ,C 3 ) includes eight bits, and multiplier 104 initially receives the two most significant bits of constant C 0 . Multiplier 106 receives sample value X 1  and receives a portion of corresponding constant C 1 . In the eight bit embodiment, multiplier 106 initially receives the two most significant bits of constant C 1 . Multiplier 108 and multiplier 110 likewise receive sample values X 2  and X 3  and receive portions of corresponding constants C 2  and C 3 , respectively. Where the constants are eight bits, mulitpliers 108 and 110 initially receive the two most significant bits of C 2  and C 3 , respectively. 
     Each multiplier 104, 106, 108, and 110 multiplies the associated sample value (X 0 ,X 1 ,X 2 ,X 3 ) by the portion of the corresponding constant (C 0 ,C 1 ,C 2 ,C 3 ). The output of each multiplier 104, 106, 108, and 110 are provided to adder 112. Adder 112 provides an output representing the sum of the four terms to a number transform circuit 114. 
     Number transform circuit 114 transforms the result from adder 112 as appropriate for the portion of the constants (C 0 ,C 1 ,C 2 ,C 3 ) that was used. In one embodiment, number transform circuit 114 comprises a shift register operable to shift the output of adder 112. For example, in the eight bit constant embodiment, shift register 114 initially shifts the output of adder 112 to the left six bits because the two most significant bits of an eight-bit constant were used by each multiplier 104, 106, 108, and 110. The output of number transform circuit 114 is provided to adder 116. 
     Multiply-add block 102 can be used sequentially with successive portions of constants (C 0 ,C 1 ,C 2 ,C 3 ) beginning with the most significant portions of constants (C 0 ,C 1 ,C 2 ,C 3 ). In one embodiment, two-bit portions are used, but other implementations are possible. 
     Adder 116 adds sequential outputs of multiply-add block 102 to provide an output Y&#39;. The number of sequential outputs can be from one to N where N sequences would implement the use of the entire constants (C 0 ,C 1 ,C 2 ,C 3 ). Where the entire constants (C 0 ,C 1 ,C 2 ,C 3 ) are not used, the output Y&#39; represents an approximation of the actual result of the sum-of-products function: 
     
         Y=C.sub.0 X.sub.0 +C.sub.1 X.sub.1 +C.sub.2 X.sub.2 +C.sub.3 X.sub.3 
    
     and has a built-in error. However, the error produced by omitting some of the least significant bits of the constants (C 0 ,C 1 ,C 2 ,C 3 ) may be negligible based upon the error margin of the application. In such a case, the multiply accumulate unit architecture of FIG. 6 can provide a multiply accumulate unit that is more efficient and consumes less space than would be required to determine the result using all of the bits of constants (C 0 ,C 1 ,C 2 ,C 3 ). 
     According to the teachings of the present invention, regardless the size of each constant, the accuracy is selectable by using multiply-add block 102 in sequence with different portions of constants (C 0 ,C 1 ,C 2 ,C 3 ). Further, it should be understood that other sizes and numbers of constants can be implemented as well. 
     The technical advantages of the architecture of FIG. 6 is the programmable nature of multiply accumulate unit 100. Number transform circuit 114 can be programmed to accomplish an appropriate shift. Further, the inputs to each multiplier can be programmed to accomplish desired accuracy. Thus, a digital signal processor that includes a multiply accumulate unit as shown in FIG. 6 could be programmable as to the number bits of the constants (C 0 ,C 1 . . . ,C 1 ) used. With each pass, accuracy is increased and the computation can be halted when the desired accuracy is reached. For some implementations, the digital signal processor may only need one pass, while for others it may be desirable to use more. 
     In this manner, a single multiply accumulate unit can provide scalable performance. This allows, for example, one digital signal processor product to be used both for a function that requires high speed and relatively low accuracy and for a function that requires higher accuracy and has lower speed requirements. 
     Although the present invention has been described in detail, it should be understood that various changes, substitutions, and alterations can be made thereto without departing from the spirit and scope of the invention as defined by the appended claims.