Abstract:
A dot product operator ( 30 ) uses adder trees ( 10 ) of L-1 adders and no multiplication circuits, where L is the length of the parallel dot product operator. Exclusive-or gates  12  provide the function of multiplication by ±1, with the carry-in ports of adders ( 14, 16, 18, 20, 32, 34, 36, 42 ) being used to form the two&#39;s complement, resulting in an extremely efficient design in terms of area and power.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
     Not Applicable 
     STATEMENT OF FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT 
     Not Applicable 
     BACKGROUND OF THE INVENTION 
     1. Technical Field 
     This invention relates in general to code division multiple access (CDMA) devices and, more particularly, to a method and apparatus for calculating a dot product for use therein. 
     2. Description of the Related Art 
     Spread spectrum communication devices have been used military and commercial devices for many years. These devices use noise-like waves to spread. (cover) the information bits so that transmission bandwidth is much wider than that required for simple point-to-point communication. DS-CDMA (Direct Spreading Code Division Multiple Access) is a form of spread spectrum which uses a conventional communication waveform and a pseudo-noise (PN) sequence; to transmit information. The PN sequence is commonly generated using a Linear Feedback Shift Register (LFSR). Thus, communication channels are separated by means of a pseudo-random modulation that is applied and removed in the digital domain, not on the basis of frequency, like frequency hopping CDMA. 
     CDMA has some significant advantages over other communication techniques, in particular it has improved capacity and quality as compared to narrowband multiple access wireless technologies. 
     Direct Spreading (DS) CDMA systems require correlation operations over two long data sequences in real time. One of the sequences is the 2×M bit wide complex number data and the other is the 2×1 bit complex PN sequence, where M is the data bit width. In correlation calculations, PN bits equal to “0” are mapped to “1”and PN bits equal to “1” are mapped to “−1”. At a specific offset, the correlation becomes a complex number dot product operation, which can be formulated as:        S   =       ∑     k   =   1     N                       D        (   k   )          PN   *     (   k   )                                
     where the data D(k)=D(k) I +jD(k) Q ) and pseudo-noise sequence PN(k)=PN(k) I +jPN(k) Q , “*” is the complex conjugate operator and N is the vector length of the complex data and PN vectors. 
     In a high quality DS-CDMA system, a parallel dot product operator is needed to make the correlation operation faster and more efficient. Because N is usually a very large number, the hardware implementation of the parallel dot product operator has to be piecewise parallel. This can lead to a large amount of circuit area being devoted to calculation of the dot product. 
     Therefore a need has arisen for a more efficient method and apparatus for calculating a dot product with a large integration length. 
     BRIEF SUMMARY OF THE INVENTION 
     The present invention provides a correlator for performing a dot product operation on bits of a pseudo-noise sequence and respective data words of a data stream. Inversion circuits each receive one of the data words along with an associated pseudo-noise sequence bit and selectively invert bits of the data word responsive to its respective pseudo-noise sequence bit. An adder tree comprising a plurality of adders performs a summation of the outputs of the inversion circuits. The carry-in bit inputs of the adders are coupled to the bits of said pseudo-noise sequence bits. 
     The present invention provides significant advantages over the prior art. While a dot product over two vectors generally requires L multiplications and L-1 additions, the present invention does not need expensive multiplier of two&#39;s complement numbers as a normal correlator does. The carry-in ports of the adders complete the two&#39;s complement operation, thereby saving an entire level of L adders. Accordingly, gate counts and power consumption are significantly reduced. 
    
    
     BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWINGS 
     For a more complete understanding of the present invention, and the advantages thereof, reference is now made to the following descriptions taken in conjunction with the accompanying drawings, in which: 
     FIG. 1 illustrates a schematic diagram of an adder tree; 
     FIG. 2 illustrates a schematic diagram of multi-bit exclusive-or circuits used in the adder tree of FIG. 1; 
     FIG. 3 illustrates a dot product operator circuit; 
     FIG. 4 illustrates a multi-bit AND gate used in the circuit of FIG.  3  and 
     FIG. 5 illustrates a spread spectrum device using the dot product operator circuit of FIG.  3 . 
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     The present invention is best understood in relation to FIGS. 1-4 of the drawings, like numerals being used for like elements of the various drawings. 
     As stated above, DS-CDMA systems require a correlation operation which can be set forth as:        S   =       ∑     k   =   1     N                       D        (   k   )          PN   *     (   k   )                                
     where the data D(k)=D(k) I +jD(k) Q  and pseudo-noise sequence PN(k)=PN(k) I +jPN(k) Q , “*” is the complex conjugate operator and N is the vector length of the complex data and PN vectors D(k) I  is the real part of D(k) and D(k) Q  is the imaginary part of D(k). D(k) I  and D(k) Q  are each M bits in width. Similarly, PN(k) I  is the real part of PN(k) and PN(k) Q  is the imaginary part of PN(k). PN(k) I  and PN(k) Q  are each one bit in width. 
     The equation above can be restated as:        S   =         S   I     +     jS   Q       =         ∑     i   =   1       N   /   L                       (       A   i     +     B   i       )       +     j          ∑     i   =   1       N   /   L            (       C   i     +     D   i       )                                    
     where          A   i     =       ∑     k   =     1   +       (     i   -   1     )        L         iL                         D   I          (   k   )              PN   I          (   k   )                     B   i     =       ∑     k   =     1   +       (     i   -   1     )        L         iL                         D   Q          (   k   )              PN   Q          (   k   )                     C   i     =       ∑     k   =     1   +       (     i   -   1     )        L         iL                         D   Q          (   k   )              PN   I          (   k   )                     D   i     =     -       ∑     k   =     1   +       (     i   -   1     )        L         iL                         D   I          (   k   )              PN   Q          (   k   )                                    
     and i=1, 2, . . . N/L is the number of pieces to finish the whole N length integration and L is the width of the parallel dot product generator. 
     As stated above; PN I  and PN Q  are one bit values generated by the LFSR as a stream of “0”s and “1”s. These binary values are generally mapped to and “−1”, respectively. Accordingly, using A i  as an example, if PN I (k)=1(i.e., PN I (k) maps to −1), then PN I (k)D I (k) equals the two&#39;s complement of D I (k). The two&#39;s complement of an M-bit number D I (k) equals 2 M −D I (k) and can also be calculated as the inversion of each bit of D I (k) and adding 1. 
     An adder tree circuit  10  for calculating A i , B i , C i  and D i  is shown in FIG.  1 . The adder tree circuit comprises a first level of L exclusive-or gates  12 , individually referenced as exclusive-or gates  12   a - 12   p . In the illustrated embodiment L=16. Each exclusive-or gate receives an M-bit value for D(k) each bit of D(k) is exclusive-or d with PN(k). The D input and PN input to each gate will depend upon whether A i , B i , C i  or D i  is being calculated. If A i  is being calculated, the b inputs of the exclusive-or gates  12  will receive D I ( 1 ) through D I (L), for i=1, and the PN inputs of the exclusive-or gates  12  will receive PN 1 ( 1 ) through PN I (L). FIG. 2 shows an example of one such exclusive-or circuit  12   a ; the inputs shown would be for the calculation of A i  where i=1 and k=1. 
     Returning to FIG. 1, the output of each exclusive-or gate  12  has an M-bit output. Pairs of exclusive-or gates  12  are coupled to the inputs of adders  14 . In the illustrated embodiment, the output of gates  12   a  and  12   b  are coupled to the inputs of adder  14   a , the output of gates  12   c  and  12   d  are coupled to the inputs of adder  14   b , the output of gates  12   e  and  12   f  are coupled to the input of adder  14   c  the output of gates  12   g  and  12   h  are coupled to the inputs of adder  14   d , the output of gates  12   i  and  12   j  are coupled to the inputs of adder  14   e , the output of gates  12   k  and  12   l  are coupled to the inputs of adder  14   f , the output of gates  12   m  and  12   n  are coupled to the inputs of adder  14   g , and the output of gates  12   o  and  12   p  are coupled to the inputs of adder  14   h , although the addition could be performed in any order. Each adder  14  also receives a carry in of one of the PN bits. In the illustrated embodiment, adder  14   a  receives bit PN( 1 ), adder  14   b  receives bit PN( 3 ), adder  14   c  receives bit PN( 5 ), adder  14   d  receives bit PN( 7 ), adder  14   e  receives bit PN( 9 ), adder  14   f  receives bit PN( 1 ), adder  14   g  receives bit. PN( 13 ), and adder  14   h  receives bit PN( 15 ). Again, as will be discussed in greater detail below, the order of connecting PN bits to carry in ports is not important, so long as each unique PN bit is received by an adder. 
     A next stage of adders  16 , individually referenced as adders  16   a  through  16   d , receives the outputs of pairs of adders  14 . In the illustrated embodiment, adder  16   a  receives the M+1 bit outputs from adders  14   a  and  14   b , adder  16   b  receives the outputs from adders  14   c  and  14   d , adder  16   c  receives the outputs from adders  14   e  and  14   f , and adder  16   d  receives the outputs from adders  14   g  and  14   h . Each adder  16  also receives a unique PN bit. In the illustrated embodiment, adder  16   a  receives bit PN( 2 ), adder  16   b  receives bit PN( 6 ), and adder  16   c  receives bit PN( 10 ), adder  16   d  receives bit PN( 14 ). 
     A third stage of adders  18 , individual referenced as adders  18   a  and  18   b , receives the outputs of pairs of adders  16 . In the illustrated embodiment, adder  18   a  receives the M+2 bit outputs from adders  16   a  and  16   b , adder  18   b  receives the outputs from adders  16   c  and  16   d . Each adder  18  also receives a unique PN bit. In the illustrated embodiment, adder  18   a  receives bit PN( 4 ), and adder  16   b  receives bit PN( 12 ). 
     In a final stage, adder  20  receives the M+3 outputs of adders  18   a  and  18   b , along with bit PN( 8 ). The output of adder  20  is a M+4 bit output. The remaining PN bit which is not connected to a carry-in port of one of the adders  14 - 20  is passed to adders shown in FIG. 3, discussed below. 
     In operation, the exclusive-or gates  12  perform the (1&#39;s complement) multiplication by ±1, depending upon the value &amp;f the associated PN bit. If the PN bit is a “0”, the D bits will pass through the exclusive-or gate  12  unchanged, i.e., D will be multiplied by “1”. If the PN bit is a “1”, the D bits will be inverted. 
     After the multiplication by ±1 has occurred in the exclusive-or gates  12 , the adders  14 - 20  perform the summation as provided in the equations for A i , B i , C i  and D i  and also complete the two&#39;s complement transformation. As discussed above, forming the two&#39;s complement of a number can be done in two steps: (1) inverting the bits of the number and (2) adding a “1” to the inverted bits. The circuit  10  uses the carry-in ports of the various adders  14 - 16  to provided the adding of “1”where appropriate. In cases where the PN bit is equal to “0”, the carry-in will be zero and, therefore, no adding of one will occur. Where the PN bit is equal to “1”, the two&#39;s complement conversion requires that the bits of the associated D bits are inverted (performed by the exclusive-or gate  12 ) and a “1” is added at the carry-in port of its associated adder  14 - 20 . Since there are only L-1 adders in the circuit (fifteen in the illustrated embodiment) and L PN bits, one of the PN bits (PN( 16 ) in the illustrated embodiment) is received by an adder outside of adder tree circuit  10 . (as shown in FIG.  3 ). 
     FIG. 3 illustrates a circuit  30  for calculating S. Circuit  30  includes four adder tree circuits  10 , individually referenced as circuits  10   a ,  10   b ,  10   c  and  10   d , to calculate A i , B i , C i  and D i , respectively. Adder tree circuit  10   a  receives PN I  and D I , adder tree circuit  10   b  receives PN Q  and D Q , adder tree circuit  10   c  receives PN I  and D Q , and adder tree circuit  10   d  receives PN Q , through inverter  31 , and D I . The outputs of these circuits will be A i , B i , C i  and D i , with the exception that each output will be off by “1” if the associated PN( 16 ) is a “1”. The outputs of adder trees  10   a  and  10   b  are coupled to the inputs of adder  32 . PN( 16 ) from adder tree  10   b  is coupled to the carry-in port of adder  32 . The, outputs of adder trees  10   c  and  10   d  are coupled to the inputs of adder  34 . PN( 16 ) from adder tree  10   d  is coupled to the carry-in port of adder  32 . The output of adder  32  is coupled to one input of adder  36 . PN( 16 ) from adder tree  10   a  is coupled to the carry-in port of adder  36 . The output of adder  36  is coupled to register  38 . The output of register  38  is coupled to one input of AND gate  40 ; the second input of m-bit AND gate  40  is coupled to a ACC_CLEAR (accumulate clear) signal, where m is the bit width of S Q  and S I . The output of AND gate  40  is coupled to the other input to adder  36 . The output of register  38  is the S I  value. The output of adder  34  is coupled to one input of adder  42 . PN( 16 ) from adder tree  10   c  is coupled to the carry-in port of adder  42 . The output of adder  42  is coupled to register  44 . The output of register  44  is coupled to one input of m-bit AND gate  46 ; the second input of AND gate  46  is coupled to the ACC_CLEAR (accumulate clear) signal. The output of AND gate  46  is coupled to the other input to adder  42 . The output of register  44  is the S Q  value. 
     AND Gates  40  and  46  are shown in greater detail in connection with FIG.  4 . Each bit of the S Q  output, for AND gate  46 , and each bit of the S I  output, for AND gate  40  is coupled to one input of an AND gate  50 ; the other input of each AND gate  50  is coupled to the ACC_CLEAR signal. This is provided to clear the contents of the accumulating registers  38  and  44 . 
     In operation, the circuit shown in FIGS. 3 and 4 works as follows. Adders  32  and  34  calculate A i +B i  and C i +D i , respectively (with the exception of adding PN( 16 ) bits from adder trees  10   a  and  10   c , which are added into the sum by adders  36  and  42 ). Adders  36  and  42 , along with registers  38  and  44  accumulate the values of A i +B i  and C i +D i  for N/L cycles to compute S I  and S Q . 
     FIG. 5 illustrates a block diagram of a spread spectrum device  58  incorporating the circuit  30  of FIG. 3. A pseudo-noise generator  60  outputs a sequence of pseudo-noise words PN(k) too circuit  30  along with data steam D(k). Data stream D(k) could be any digital-data stream which would benefit from communication using spread spectrum techniques, such as an analog communication signal, which is translated to a digital signal by A/D (analog to digital) converter  62 , or a native digital signal such as the output of a computing device. The digital data stream D(k) and the pseudo-noise sequence PN(k) are combined to output S, as described above. 
     The present invention provides significant advantages over the prior art. While a dot product over two vectors generally requires L multiplications and L-1 additions; the present invention does not need expensive multiplier of two&#39;s complement numbers as a normal correlator does. By utilizing the carry-in ports of the adders to complete the two&#39;s complement operation, a whole level of L M-bit wide adders is saved. Accordingly, gate counts and power consumption are significantly reduced. 
     For illustration purposes, the circuitry has been shown with specific L and M values, but the circuit could easily expanded or reduced to accommodate L and M values other than those shown. Further, while the implementation has been described for a N with is an integer power of 2, other values of N could be accommodated as well. 
     Although the Detailed Description of the invention has been directed to certain exemplary embodiments, various modifications of these embodiments, as well as alternative embodiments, will be suggested to those skilled in the art. The invention encompasses any modifications or alternative embodiments that fall within the scope of the claims.