Patent Publication Number: US-7711765-B2

Title: Method and apparatus to perform multiply-and-accumulate operations

Description:
BACKGROUND 
   The present invention relates generally to numeric processing, such as used in communication signal processing contexts, and particularly relates to multiply-and-accumulate operations. 
   A multiply-and-accumulate (MAC) operation multiplies two numbers and adds the result to a saved value or, more generally, to an accumulation register. Useful results, such as signal filtering in the digital domain, are obtained by repeating this operation for a series of number pairs. 
   A conventional approach to performing a desired series of MAC operations requires performing a full precision multiply operation and a full precision addition operation for each number pair in the series. The implementation of conventional MAC operations in software may result in undesirable performance penalties. Performance can be significantly improved by providing dedicated MAC hardware in the form of appropriately interconnected adders/multipliers and control logic. However, performing MAC operations at high rates, such as those associated with digital signal processing in the wireless communication domain, requires very high-speed adders and multipliers. Such hardware may be impractical, at least for some integrated circuit processes, or may be prohibitively expensive or power hungry. 
   SUMMARY 
   In one embodiment, a method for carrying out a desired series of multiply-and-accumulate (MAC) operations comprises counting the occurrence of particular products in the set of products corresponding to the desired series of MAC operations, generating partial sums by multiplying the counts by their corresponding products, and adding the partial sums to obtain a final result for the desired series of MAC operations. As the desired series of MAC operations represents the summation of a series of individual multiplications, with each multiplication involving a multiplier pair, counting products in one embodiment comprises carrying out multiplications of the multiplier pairs and counting the occurrence of products resulting from those multiplications. In another embodiment, counting products comprises counting the occurrence of multiplier pairs corresponding to the products, i.e., the count is obtained without the necessity of carrying out the multiplication of the product pairs. 
   In either case, the counting can be performed by incrementing a corresponding counter for positive occurrences of a given product, and decrementing that counter for negative occurrences of the product. Negative and positive occurrences can be determined based on the signs of the individual multipliers giving rise to the product. Thus, one embodiment of a MAC circuit comprises one or more processing circuits configured to count the occurrence of products in a desired series of MAC operations, multiply the counts by their corresponding products to obtain partial sums, and add the partial sums to obtain the final result. In one or more embodiments of the MAC circuit, the processing circuit(s) include counters and addressing control circuits. The addressing and control circuits address the counters as a function of the products being counted. For example, the addressing and control circuits can be configured to map each unique product magnitude to a given counter, such that the counter is decremented for negative occurrences of the product and incremented for positive occurrences. 
   For embodiments that count the occurrence of products based on counting the multiplier pairs corresponding to those products, the addressing and control circuits can be configured to map multiplier pairs to corresponding counters. For example, one embodiment of a MAC circuit as taught herein includes a counter for each unique multiplier pair. However, to save counters, the addressing and control circuits are, in another embodiment, configured to map “equivalent” multiplier pairs to the same counter. In one embodiment, multiplier pairs are considered equivalent if they correspond to the same product magnitude. In another embodiment, as an addition to considering equivalence based on product magnitudes, or as an alternative to such consideration, multiplier pairs may be considered equivalent if they comprise the same multipliers, e.g., a×b equals b×a (regardless of the signs involved). 
   The various circuit and method embodiments taught herein have broad applicability. For example, in one embodiment, a wireless communication device includes a MAC circuit as taught herein, and is configured to calculate interference correlations for received signal processing at least in part using that MAC circuit. In another embodiment, the wireless communication device is configured to use a MAC circuit as taught herein for the calculation of chip equalization filter values. In another embodiment, the wireless communication device includes a Generalized RAKE receiver circuit, wherein the desired series of MAC operations comprise at least part of a correlation estimation process for a received signal, such as may be used for combining weight generation in Generalized RAKE receivers. By way of further non-limiting examples, a desired series of MAC operations as taught herein can be performed in a sample correlation estimation process, a signal convolution process, a signal correlation process, or a Finite Impulse Response filtering process. 
   Of course, the present invention is not limited to the above features and advantages. Indeed, those skilled in the art will recognize additional features and advantages upon reading the following description and upon viewing the accompanying drawings. 

   
     BRIEF DESCRIPTION OF DRAWINGS 
       FIG. 1  is a logic flow diagram of processing logic for one embodiment of multiply-and-accumulate (MAC) processing. 
       FIG. 2  is table of hypothetical products and their corresponding multiplier pairs, such as may be processed according to the MAC processing method of  FIG. 1 . 
       FIG. 3  is a block diagram of circuit elements for one embodiment of a MAC circuit configured for MAC processing. 
       FIG. 4  is a block diagram of a microprocessor-based circuit, which may be used to implement a MAC circuit. 
       FIG. 5  is a block diagram of MAC circuit details for one embodiment of MAC processing. 
       FIG. 6  is a block diagram of a wireless communication device, which is configured for MAC processing. 
       FIG. 7  is a block diagram for a Generalized RAKE embodiment of a receiver circuit included in the wireless communication device of  FIG. 6 , wherein MAC processing as taught herein is used to obtain interference correlation estimates for combining weights generation. 
       FIG. 8  is a block diagram for a Chip Equalization (CE) embodiment of a receiver circuit included in the wireless communication device of  FIG. 6 , wherein MAC processing as taught herein is used to obtain filter tap coefficients for CE filtering. 
       FIG. 9  is a block diagram of MAC circuit details for one embodiment of MAC processing. 
       FIGS. 10 and 11  are tables illustrating multiplier-to-counter mapping tables as may be implemented by MAC processing logic, as taught herein. 
   

   DETAILED DESCRIPTION 
     FIG. 1  is a logic flow diagram illustrating one embodiment of processing logic for carrying out a desired series of multiply-and-accumulate (MAC) operations, and which may be implemented in hardware, software, or any combination thereof. As a means for better understanding the illustrated method,  FIG. 2  illustrates a set of products  10  representing the product terms involved in a given series of MAC operations. One sees that each of the products (P 1  through P 10 ) correspond to multiplier pairs. For example, multipliers a and b give rise to product P 1 , multipliers b and c give rise to product P 2 , and so on. 
   An inspection of set  10  reveals that some products in the set occur more than once. For example, ignoring any sign differences for the moment, product P 1  is the same as product P 9 . Moreover, if the ordering of the individual multipliers comprising the multiplier pairs corresponding to the products is not important for the given application, the product of multipliers b and c occurs four times in the set of products  10 , i.e., P 2 , P 6 , P 8 , and P 10 . The repetition of products may be significant, particularly over a long series of multiplier pairs. More particularly, where the underlying range of values taken on by the individual multipliers is limited, e.g., the multipliers correspond to low-resolution digital samples, the number of repeated multiplier pairs/products over a long sample series can be significant. 
   With that point in mind, and returning to the logic of  FIG. 1 , processing to determine a final result for a desired series of MAC operations “begins” with counting the occurrence of products in the desired series of MAC operations (Step  100 ). Processing continues with multiplying the counts by their corresponding products to obtain partial sums (Step  102 ), and adding the partial sums to obtain the final result (Step  104 ). Thus, whether for real-valued or complex samples, and whether for multiplier pairs or more complex product terms, the MAC circuits and methods taught herein provide a basis for performing a desired series of MAC operations using a number of simple counters—e.g., up/down counters—and simple post-counting operations to evaluate the desired series. 
   In one or more embodiments, such processing is based on splitting a signed number into two parts, a sign bit and a magnitude. In such embodiments, each counter is associated with the product of two magnitudes. Counters are specifically addressed by the two magnitudes forming the product. If a counter is addressed, it is counted up by 1 when the product of the sign bits—sign bits are represented by +1 or −1—is positive, which herein is referred to as a positive occurrence, and down by 1 if the product of the sign bits is negative, which herein is referred to as a negative occurrence. In this way, the value in a counter represents the accumulated multiplier for the associated magnitude pair. For example, if the desired series of MAC operation is 2·3+(−2−3)+(−2·−3)+2·3+(−2·−3)+(−2·3), one or more embodiments of the MAC processing method taught herein calculate that desired series as (1−1+1+1+1−1)(2·3)=2.6. 
   The up/down counting calculates (1−1+1+1+1−1)=2 in the above manipulation. The final results for the desired series of MAC operations are calculated by multiplying the “count” of the up-down counter (2, according to the above example) and the product of the two magnitudes associated with the counter (6, according to the above example) as illustrated in the final equation above. 
   Note, too, that in one or more embodiments, positive occurrences of a given product may be accumulated in one counter, and negative occurrences of that same product may be accumulated in another counter. Then, the multiplier for that product is determined by subtracting the accumulated negative occurrence counts from the accumulated positive occurrence counts. Alternatively, a negative partial sum and a positive partial sum can be formed prior to accumulation. Such an embodiment can be implemented where it is desirable to use unidirectional, e.g., up, counters, rather than up/down counters. The accumulated count values as multiplied by their corresponding products yield partial sums, which can then be added together to obtain the final result of the desired series of MAC operations. If all numbers are positive (unsigned), then only an up counter is needed, and operations involving sign bits can be eliminated. 
   MAC processing as taught herein can be applied to any desired series of MAC operations. In general, a desired series of MAC operations may be represented as 
                 z   =       ∑     i   =   0       N   -   1       ⁢       x   ⁡     (   i   )       ⁢     y   ⁡     (   i   )                   Eq   .           ⁢     (   1   )                 
The magnitudes of x(i) and y(i) can be used to address up-down counters, and the product of the sign bits of x(i) and y(i) is used to determine whether the addressed counter should be incremented or decremented. Where the multipliers x(i) and y(i) take on a finite range of values, the number of possible products is also finite, and the methods taught herein exploit the repetition of product magnitudes that arise in a given series of MAC operations.
 
   In general, x(i) and y(i) do not need to be real numbers, thus the methods taught herein have broad application to a wide range of signal processing applications, such as communication signal processing. For example, the correlation of two number sequences takes the form of Eq. (1). Thus, the proposed methods can be applied to correlation calculations, which are prevalent in a wide range of communication signal processing functions. 
   For example, in code division multiple access (CDMA) systems, a receiver often needs to compute correlations between complex-valued received samples and a complex-valued spreading sequence, which is referred to as despreading. The despreading operation can be done using the methods proposed herein. In wideband CDMA (WCDMA) and cdma2000, the spreading sequence takes on values {a, b, −a, −b}, where a=1+j and b=1−j. Assume the received samples take on the complex values of {c, d, e, f, −c, −d, −e, −f}. The up-down counters associated with (a,c), (a,d), (a,e), (a,f), (b,c), (b,d), (b,e), (b,f), respectively, can be used to tally the multiplier associated with each pair during correlation. The final correlation can be obtained by
 
 z=c   ac ( a·c )+ c   ad ( a·d )+ c   ae ( a·e )+ c   af ( a·f )+ c   bc ( b·c )+ c   bd ( b·d )+ c   be ( b·e )+ c   bf ( b·f )  Eq. (2)
 
where c ij  are the values of the counter associated with (i, j).
 
   As a further example, finite-impulse-response (FIR) filtering is also a MAC operation, and can be represented as, 
                   z   ⁡     (   n   )       =       ∑     i   =   0       N   -   1       ⁢       x   ⁡     (   i   )       ⁢     y   ⁡     (     n   -   i     )                   Eq   .           ⁢     (   3   )                 
Thus, x(i) can represent the coefficients of the FIR filter and y(i) can represent the signal samples input to the filter. As such, the methods taught herein apply directly to FIR filtering. Furthermore, convolution between signals x(i) and y(i) is of the form of Eq. (3), and the methods taught herein thus apply directly to the convolution of two signals.
 
   With these and other applications in mind,  FIG. 3  illustrates one embodiment of a MAC circuit  12  that can be configured to carry out the method of performing MAC operations taught herein. The illustrated MAC circuit  12  comprises a counter control circuit  14  that is configured to control a plurality of counters  16  included in, or associated with, the MAC circuit  12 , and one or more calculation circuits  18 . The calculation circuits  18  are configured to obtain the partial sums based on the product occurrence counts that accumulate in the counters  16  as a function of the counter control circuit  14  processing the products corresponding to the desired series of MAC operations, and to generate the final results by adding the partial sums together. 
   It should be understood that the circuit elements depicted in  FIG. 3  may comprise hardware-based circuits, software-based circuits, or any combination thereof. For example,  FIG. 4  illustrates a microprocessor (or DSP)  20  that includes or is associated with program memory  22  storing computer program instructions embodying the MAC circuit  12 , and that is further associated with data memory  24  providing registers for implementing the counters  16  and storing the set of products  10  (or the corresponding multiplier pairs). (Note, too, that, the products or multipliers do not need to be pre-stored and can be processed on an as-generated basis for a given series of MAC operations being performed in real time or near real time. Further, note that rather than a microprocessor, an ASIC, FPGA, or other programmable logic device may be used to implement the MAC circuit  12 .) 
   Regardless of its implementation details, in one embodiment the MAC circuit  12  counts the occurrence of products in the desired series of MAC operations by carrying out multiply operations for the multiplier pairs corresponding to the products, and counting positive and negative occurrences of each product. (Alternatively, an associated circuit may perform the multiplier pair multiplications to obtain the products and provide them to the MAC circuit  12  for counting.) Further, the product values may be rounded or quantized to limit the number of possible product values, hence reducing the number of counters needed. In one embodiment, counting positive and negative occurrences of each product comprises using product magnitudes to address corresponding ones of the counters  16 , incrementing the corresponding counter for each positive occurrence of a given product, and decrementing the corresponding counter for each negative occurrence. With this approach, multiplying the counts by their corresponding products to obtain partial sums comprises multiplying the count stored in each counter by the corresponding product. 
   Counting product occurrences by carrying out the multiplication of multiplier pairs in the desired series of MAC operations represents a significant computational advantage compared to a conventional, direct approach to MAC operations, wherein each multiplier pair is multiplied and the resulting product added to a MAC accumulator. For example, to perform a series of 100 MAC operations, a conventional (direct) MAC circuit would perform 100 full-precision multiplications and 100 full-precision additions, including carry/overflow tracking. However, one embodiment of the MAC circuit  12  would simply count the occurrence of same-valued products as it carried out the 100 multiplications, use the accumulated counts to multiply the corresponding same-valued products, and then add together those results to obtain the final results. If the 100 products included only fifteen unique values, then only fifteen additions would be needed, rather than the 100 additions conventionally required. The product of the corresponding multiplier pair can be determined using, for example, a look-up table, or other data structure, holding predetermined product values. More generally, the products for at least some of the multiplier pairs corresponding to products in a desired series of MAC operations can be stored in memory as pre-computed values. 
   In one or more other embodiments, the MAC circuit  12  and the corresponding method obtain even greater computational efficiency by counting the occurrence of products in the desired series of MAC operations based on counting the occurrence of multiplier pairs corresponding to the products. In such embodiments, product counts are obtained without need for first carrying out the multiplication of the multiplier pairs. Again, pre-computed values can be stored for products of the various multiplier pairs, such that product values for the multiplier pairs can be determined using a look-up function, rather than by carrying out the multiplication. A memory including look-up data thus may be included in the MAC circuit  12 , or may be directly or indirectly associated with the MAC circuit  12 . The multiplier pair values may be further quantized to reduce the number of counters needed. 
   Among other advantages, the gains in computational efficiency offered by MAC processing as taught herein may allow significant reductions in power consumption. For example, power savings may be realized because the MAC circuit  12  is relatively simple in functional terms, and because the number of operations required to compute results for a desired series of MAC operations may be reduced using the methods taught herein. Further, MAC processing as taught herein may make high-speed MAC processing more feasible. For example, it may be difficult to perform multiplications at, for example, 160 MIPS, but it may be much easier to perform counting-based MAC operations as taught herein at a similar rate. 
   To better illustrate one or more embodiments of product counting,  FIG. 5  depicts the counter control circuit  14  of the MAC circuit  12  as comprising an address generation circuit  30  and an increment/decrement control circuit  32 , which are associated with counters  16 . For example, in one embodiment, the one or more processing circuits comprising the MAC circuit  12  are configured to generate counter addresses as a function of product magnitudes, and to control counter incrementing and decrementing as a function of product signs, such that a corresponding counter in a plurality of counters is incremented or decremented for each occurrence of a given product. In one or more embodiments, counters and pre-processing functions, such as identifying multiplier signs, etc., for the desired series of MAC operations, may be included within the one or more processing circuits comprising the MAC circuit  12 . 
   Regardless, the product magnitudes may be input to the address generation circuit  30 , which can be configured to generate a corresponding counter address as a function of each unique product. Further, the corresponding product signs may be input to the increment/decrement control circuit  32 . With this arrangement, each unique product in the series is mapped to a particular one of the counters  16 . Thus, each occurrence of a unique product in the series causes the corresponding counter to be incremented if the occurrence is positive, or decremented if the occurrence is negative. Occurrences are individually determined to be positive or negative by the sign value(s) input to the increment/decrement control circuit  32  in conjunction with the occurrence being counted. 
   In another embodiment, the MAC circuit  12  counts products in the desired series of MAC operations by processing the multiplier pairs corresponding to the products based on addressing a corresponding counter for each occurrence of a given multiplier pair, incrementing the corresponding counter if the occurrence is positive, and decrementing the corresponding counter if the occurrence is negative. Thus, the address generation circuit  30  may be configured to generate a counter address for each occurrence of a given multiplier pair by determining the counter address based on magnitudes of individual multipliers comprising the given multiplier pair. That is, the multiplier pairs, or their corresponding magnitudes, may be input to the address generation circuit  30  in conjunction with inputting the multiplier pairs or their corresponding sign values into the increment/decrement control circuit  32 . 
   In one embodiment, the address generation circuit  30  generates a unique counter address for each unique multiplier pair. For example, using real numbers by way of non-limiting example, the address generation circuit  30  can be configured to generate a different counter address for the multiplier pairs (a·b) and (b·a), although their corresponding product magnitudes are the same. One advantage to mapping every unique multiplier pair to a different counter address is simplification of the address generation logic. Such simplification may be desirable for very high-rate signal processing applications. 
   While such mapping may result in simplified counter address generation, it does require, in general, a greater number of counters in the plurality of counters  16 . Because the counters  16  can be implemented using addressable memory registers, there may be an abundance of counter resources available. On the other hand, if counter resources are a concern and/or circuit performance is not an issue, the address generation circuit  30  can be configured to map “equivalent” multiplier pairs to the same counter address. An equivalent multiplier pair is defined in one embodiment as multiplier pairs whose individual multipliers have the same magnitudes. For example, the multiplier pair (3, 2) would be equivalent to (2, 3). Additionally, or alternatively, the definition of equivalent multiplier pairs may be extended to include multiplier pairs corresponding to the same product magnitude. Thus, (3, 2), (2, 3), (1, 6), and (6, 1), all would be equivalent and the occurrence of any one of these products would generate the same counter address. 
   The choices of whether to count actual products or to count corresponding multiplier pairs, and whether to favor simplified counter address generation over a greater number of counters depends at least to some extent on the particular application at hand. For example, the MAC circuit  12  and the corresponding method of carrying out MAC operations may be applied in communication signal processing applications, as noted earlier herein 
   On that point, in commercial CDMA systems (e.g., WCDMA and cdma2000 wireless communication networks), performance is often limited by multiple-access interference. At least a portion of the multiple access interference can be modeled as colored noise. In the downlink from the base stations to the access terminals, colored noise arises from a few base station signals received through dispersive channels. Each base station signal is colored by frequency-selective fading. Similarly, in the uplink, the high-power, high-data-rate signals received from the access terminals through dispersive channels gives rise to colored interference at the base station receiver. 
   In either the base station receivers or the access terminal receivers, when colored noise dominates, receiver performance can be significantly improved by exploiting interference correlation to suppress interference. Because the determination of interference correlation estimates generally involves performing potentially many MAC operations, interference correlation determination can be computationally simplified by carrying out at least some of the desired MAC operations using the circuits and methods taught herein. Note that interference correlation includes data or chip sample correlation. 
   For example,  FIG. 6  illustrates a wireless communication device  40  that is configured to implement MAC processing as taught herein. In the illustrated embodiment, the wireless communication device  40  comprises a receive/transmit antenna  42 , a switch/duplexer  44 , a receiver front-end  46 , a transmit amplifier circuit  48 , a baseband processor circuit  50 , including a receive processor  52  and a transmit processor  54 , a system controller  56 , and a user interface  58 . Of course, those skilled in the art will appreciate that the wireless communication device  40  may deviate from the depicted circuit arrangement according to its intended use. For example, the wireless communication device  40  may comprise a mobile radiotelephone (e.g., a cellular handset), a Portable Digital Assistant (PDA) with wireless communications, a wireless pager, a palmtop/laptop computer or a network card therein, etc. 
   In one embodiment, shown in  FIG. 7 , the receive processor  52  includes a Generalized RAKE (G-RAKE) receiver  60 , comprising a despread unit  62 , a combining weight generator  64 , an interference correlation circuit  66 , which includes an embodiment of the MAC circuit  12 , and a combining circuit  68 . In operation, the interference correlation circuit  66  implements an interference correlation estimation process, which yields interference correlation estimates for the received data samples, for use in combining weight generation as carried out by the combining weight generator  64 . To the extent that the interference correlation estimates accurately represent colored interference correlations, application of the generated combining weights to the despread signals output by the despread unit  62  results in colored interference cancellation in the combined signal output by the combining circuit  68 . 
   Notably, the interference correlation circuit  66  performs interference correlation estimation at least in part using its included MAC circuit  12 , although it may include or have access to conventional MAC circuits, as well. As such, the computational efficiency, processing speed, and/or power consumption characteristics are improved for the interference correlation estimation process carried out by the receive processor  52 . (It should be understood that the receive processor  52  may be implemented within a microprocessor, ASIC, FPGA, or other processing circuit.) 
   Further, those skilled in the art will appreciate that G-RAKE processing is equivalent to linear minimum mean square error (LMMSE) based chip equalization (CE). To that end,  FIG. 8  depicts another embodiment of the receive processor  52 , wherein it includes a chip equalization circuit  70  comprising a (chip) equalization filter  72 , a filter coefficient generator  74 , a data correlation circuit  76 , which includes an embodiment of the MAC circuit  12 , and a despreading correlator  78 . 
   In operation, the equalization filter  72  equalizes the received signal samples based on the filter coefficients generated by the filter coefficient generator  74 . In turn, the filter coefficients are generated based at least in part on data correlation estimates generated by the data correlation circuit  76 , which is configured to generate data sample correlations using its included MAC circuit. The equalized received signal samples are then input to the despreading correlator  78  for detection of the transmitted symbol information. 
   As with the interference correlation circuit  66  in  FIG. 7 , the data correlation circuit  76  of  FIG. 8  improves the computational efficiency during its data correlation estimation process by using the MAC circuit  12  for at least a portion of the MAC operations needed for generating the interference correlation estimates. For linear interference-suppressing receivers in general, then, various embodiments of the MAC circuit  12  can yield significant performance and/or efficiency advantages in the estimation of interference correlations in G-RAKE implementations for combining weight generation, or in the estimation of data correlations in CE implementations for filter tap coefficients. 
   For G-RAKE, the combining weights can be formulated as w GR =R u   −1 h, where R u  is the interference correlation and his the net response. For CE, the tap coefficients can be determined by w CE =R d   −1 f, where R d  is the receive samples correlation and f is the correlation between the receive samples and the chip value of interest. The weight vectors w GR  and w CE  are related by a positive scaling factor. That is, w GR =λw CE , where λ&gt;0. Thus, the combining weights of G-RAKE can be determined using the receive samples correlation R d  matrix. As such, the efficient calculation of R d  as provided by the MAC circuit  12  and corresponding method taught herein benefits not only the chip equalizers, but also G-RAKE receivers. Indeed, in the G-RAKE context, basing combining weight estimations on the chip samples, rather than on despread values, can yield improved performance under fast-fading conditions. 
   Thus, efficient MAC processing as taught herein offers significant benefits to communication receivers in general. Thus, while particular embodiments are illustrated herein, those skilled in the art will recognize that the methods and circuits taught herein may be implemented in both fixed and mobile receivers, e.g., base stations and/or mobile stations. 
   In looking at communication receiver applications in more detail, let y(i) represent the ith complex-valued receive sample and d 1 , d 2 , . . . , d J , be the finger (or tap) delays in the unit of samples. Receive samples correlation matrix R d  can be estimated by 
                   R   d     =       1   N     ⁢       ∑     i   =   0       N   -   1       ⁢       y   ⁡     (   i   )       ⁢       y   H     ⁡     (   i   )                     Eq   .           ⁢     (   4   )                 
where N is the smoothing factor and vector y(i)=[y(iK+d 1 ), y(iK+d 2 ), . . . , y(iK+d J )] T . The term K is typically set to the number of samples in a chip period.
 
   Commonly, obtaining an accurate estimate of R d  requires a large smoothing factor N. The amount of computation required for Eq. (4) can be rather large for a large N. More particularly, there are J·J elements in R d , and, for each element, calculation of N complex multiplications are needed. Thus, overall N·J 2  complex multiplications are needed. However, processing circuits can be configured to exploit the Hermitian symmetry property of R d  to reduce the number of complex multiplications to roughly N·J 2 /2. For example, in the context of a WCDMA-based communication signal, for J=6, N=1000, and assuming R d  is updated in every WCDMA slot, the computation of R d  using a conventional approach to MAC operations would consume more than 160 million instructions per second (MIPS). 
   Using an embodiment of the MAC circuit  12  for such operations yields significant reductions in the required MIPS, which may be illustrated by using the estimation of the (1,1) and (1,2) element of R d  as examples. The former case represents the diagonal elements of R d , where the latter case represents the off-diagonal elements of R d . Starting with the off-diagonal element r 1,2 , 
                   r     1   ,   2       =       1   N     ⁢       ∑     i   =   0       N   -   1       ⁢       y   ⁡     (     iK   +     d   1       )       ⁢   y   *     (     iK   +     d   2       )                   Eq   .           ⁢     (   5   )                 
The real part or in-phase component (I) of r 1,2  can be expressed as
 
                   r     1   ,   2     I     =         1   N     ⁢       ∑     i   =   0       N   -   1       ⁢         y   I     ⁡     (     iK   +     d   1       )       ⁢       y   I     ⁡     (     iK   +     d   2       )             +         y   Q     ⁡     (     iK   +     d   1       )       ⁢       y   Q     ⁡     (     iK   +     d   2       )                   Eq   .           ⁢     (   6   )                 
where y I (i) and y Q (i) are the real part and imaginary part (quadrature component (Q)) of received sample y(i), respectively. Similarly, the imaginary part of r 1,2  can be expressed as
 
   
     
       
         
           
             
               
                 
                   r 
                   
                     1 
                     , 
                     2 
                   
                   Q 
                 
                 = 
                 
                   
                     
                       1 
                       N 
                     
                     ⁢ 
                     
                       
                         ∑ 
                         
                           i 
                           = 
                           0 
                         
                         
                           N 
                           - 
                           1 
                         
                       
                       ⁢ 
                       
                         
                           
                             y 
                             Q 
                           
                           ⁡ 
                           
                             ( 
                             
                               iK 
                               + 
                               
                                 d 
                                 1 
                               
                             
                             ) 
                           
                         
                         ⁢ 
                         
                           
                             y 
                             I 
                           
                           ⁡ 
                           
                             ( 
                             
                               iK 
                               + 
                               
                                 d 
                                 2 
                               
                             
                             ) 
                           
                         
                       
                     
                   
                   - 
                   
                     
                       
                         y 
                         I 
                       
                       ⁡ 
                       
                         ( 
                         
                           iK 
                           + 
                           
                             d 
                             1 
                           
                         
                         ) 
                       
                     
                     ⁢ 
                     
                       
                         y 
                         Q 
                       
                       ⁡ 
                       
                         ( 
                         
                           iK 
                           + 
                           
                             d 
                             2 
                           
                         
                         ) 
                       
                     
                   
                 
               
             
             
               
                 Eq 
                 . 
                 
                     
                 
                 ⁢ 
                 
                   ( 
                   7 
                   ) 
                 
               
             
           
         
       
     
   
   The use of up-down counters for the calculation of Eq. (6) and Eq. (7) yields significant gains in computational efficiency, in comparison to performing the potentially large number of conventional MAC operations that would be required for their calculation. For example, assume the real and imaginary parts of the receive sample y(i) are both quantized into 3 bits, which consists of a 1-bit sign and a 2-bit magnitude. The 3-bit quantized values represent levels −7, −5, −3, −1, 1, 3, 5, and 7. The product of two 3-bit signed integer numbers can be calculated by (s 1 s 2 )(u 1 u 2 ), where s 1  and s 2  are the signs and u 1  and u 2  are the 2-bit magnitudes. The product of the signs can be used to decide whether to count up or down (increment or decrement the count). One way to implement Eq. (5) is to have separate counters for the in phase component of Eq. (6) and the quadrature component of Eq. (7) with each counter being updated twice each iteration. 
     FIG. 9  illustrates an embodiment of the counter control circuit  14  of the MAC circuit  12  that is configured to count the occurrence of products in a desired series of MAC operations based on processing the corresponding multiplier pairs in magnitude and sign form, as described immediately above. In more detail, the address generation circuit  30  is configured to generate counter addresses (counter (i, j)) as a function of the [u 1 (1),u 1 (2)] and [u 2 (1),u 2 (2)] magnitudes for the multiplier pairs (u 1 ,u 2 ), where u k (1) and u k (2) denote the two bits of the two-bit magnitude of u k . Further, the increment/decrement control circuit  32  is configured to increment or decrement the addressed counter as a function of the multiplier pair signs (s 1 ,s 2 ).  FIG. 10  is a product table for the two-bit magnitudes, and illustrates a mapping between the magnitudes of the multiplier pairs and their corresponding products, that may be used for addressing counters. 
   Thus, the MAC circuit  12  can be configured to use the magnitude bits of multiplier pairs corresponding to the products in a desired series of MAC operations as addresses for accessing a specific counter, i.e., magnitude bits (i,j) will address counter (i,j). For example, if the two magnitudes are 3 and 5, counter (3, 5) will be addressed. The addressed counter will be counted up or down if the product of the multiplier pair sign bits is 1 or −1, respectively. 
   As noted earlier, the MAC circuit  12  can be configured to map each unique multiplier pair to a different counter. That approach requires sixteen counters for the multiplier pair mappings depicted in  FIG. 10 . However, as also noted earlier, several combinations of multiplier pairs map to the same product value. Thus, fewer counters can be used by mapping equivalent multiplier pairs to the same counter. For example, by doing so for the values given in  FIG. 10 , only ten counters are needed. 
   In any case, once all the product terms of Eq. (6) are used in addressing the counter for up-down counting, the summation of Eq. (6) can be computed by 
                   r     1   ,   2     I     =       1   N     ⁢       ∑     m   =   1     M     ⁢       c   ⁡     (   m   )       ⁢     p   ⁡     (   m   )                     Eq   .           ⁢     (   8   )                 
where M is the total number of counters, c(m) is the value of the mth counter, and p(m) is the product value associated with the mth counter. Continuing our example of 3-bit signed integers for the real and imaginary parts of receive samples and exploiting the symmetry of multiplications, M=10, p(1)=1·1=1, p(2)=1·3=3, p(3)=1·5=5, p(4)=1·7=7, p(5)=3·3=9, p(6)=3·5=15, p(7)=3·7=21, p(8)=5·5=25, p(9)=5·7=35, and p(10)=7.7=49. Note that p(m) can be pre-calculated and stored.
 
   For the diagonal elements of R d , for example element (1,1), the MAC circuit  12  can use the same logic as that used for computing the off-diagonal elements of R d . As the diagonal elements are purely real, calculation of Eq. (7) can be omitted. Alternatively, the MAC circuit  12  can include addressing logic that exploits the diagonal element properties. On this point, note that the diagonal elements of R d , e.g., the (1,1) element, r 1,1 , can be computed as 
                   r     1   ,   1     I     =       1   N     ⁢       ∑     i   =   0       N   -   1       ⁢         y   I   2     ⁡     (     iK   +     d   1       )       ⁢       y   Q   2     ⁡     (     iK   +     d   1       )                     Eq   .           ⁢     (   9   )                 
Thus, only the two magnitude bits of y i  or y q  are needed for addressing the corresponding counter. Once all the y i  and y q  are used in addressing the counter (which needs only to count “up” in this case), the summation of Eq. (9) can be computed by
 
                   r     1   ,   1     I     =       1   N     ⁢       ∑     m   =   1       M   ′       ⁢         c   ′     ⁡     (   m   )       ⁢       p   ′     ⁡     (   m   )                     Eq   .           ⁢     (   10   )                 
where M′ is the total number of counters used for computing the diagonal elements of R d , c′(m) is the value of the m th counter, and p′(m) is the product value associated with the mth counter. Continuing our example of 3-bit signed integers for the real and imaginary parts of receive samples, M=4, p′(1)=1×1=1, p′(2)=3·3=9, p′(3)=5·5=25, and p′(4)=7·7=49. Note that p′(m) can be pre-calculated and stored.
 
   To further ease the computation of Eq. (8), the MAC circuit  12  can be configured to use shift operations in combination with addition/subtraction operations to compute all the products of c(m)p(m). As is known, multiplication by a power of 2 can be realized using a left shift, thus c(1)p(1)=c(1); c(2)p(2)=c(2)·3=4c(2)−c(2) or 2c(2); c(3)p(3)=c(3)·5=4c(3)+c(3); c(4)p(4)=c(4)·7=8c(4)−c(4); c(5)p(5)=c(5)·9=8c(5)+c(5); c(6)p(6)=c(6)·15=16c(6)−c(6); c(7)p(7)=c(7)·21=16c(7)+4c(7)+c(7); c(8)p(8)=c(8)·25=16c(8)+8c(8)+c(8); c(9)p(9)=c(9)·35=32c(9)+4c(9)−c(9); c(10)p(10)=c(10)·49=64c(10)−16c(10)+c(10). 
   In one or more embodiments, the MAC circuit  12  includes hardware and/or software based logic tailored to perform these computations, and it should be understood that similar computations can be used to compute Eq. (10). Further, the smoothing factor N can be chosen as power of 2 to ease division computations. If absolute units are unimportant, the division by N can be omitted. 
   Of course, although the above examples used multiplier pairs to illustrate MAC processing, it should be understood that the MAC circuit  12  can be used to perform a desired series of MAC operations wherein the products arise from multiple computations. For example, in computing r 1,1   1 , a table two-dimensional counter mapping table as shown in  FIG. 11  can be used for the sum of the real part and imaginary part squared, y I   2 (iK+d 1 )+y Q   2 (iK+d 1 ). In this case, the counters are updated only once instead of two or four times for each sample. 
   Broadly, then, MAC processing as taught herein can be applied to simple product pairs of real numbers, or to complex-valued product pairs, or to a desired series of MAC operations where the products represent several multiplications, e.g., three more multipliers giving rise to the product terms. Thus, MAC processing taught herein applies to essentially any type of signal processing or other numeric computation involving a desired series of MAC operations. Where the range of possible values taken on by the products arising in the desired series of MAC operations is limited, significant gains in processing efficiencies are obtained. 
   Even in instances where the range of possible products is quite large, or unlimited, it may be that a subset of the overall series of MAC operations is well bounded. That is, some products may occur more frequently than others. Thus, MAC processing as taught herein, i.e., the counter-based approach to determining MAC results, can be applied to a first subset of the products in an overall set of products. The remaining subset of products can be processed using conventional (direct) MAC operations, i.e., brute force multiply-and-accumulate processing, or by carrying out equivalent lookup table processing. In this manner, at least the most commonly occurring products, i.e., those repeated most frequently for the series of MAC operations to be performed, can be processed as taught herein. The final results for each subset can then be combined to obtain final results for the overall series of MAC operations. 
   Thus, those skilled in the art will appreciate that the present invention is not limited by the foregoing discussion, nor by the accompany drawings. Indeed, the present invention is limited only by the following claims and their legal equivalents.