# Patent

## Title
Fast joint detection base station

## Abstract

A code division multiple access base station receives K data signals over a shared spectrum. The base station receives and samples a combined signal having the K transmitted data signals. A combined channel response matrix is produced. A block column of a cross correlation matrix is determined using the combined channel response matrix. Each block entry of the block column is a K by K matrix. A fourier transform of a complex conjugate transpose of the combined channel response matrix multiplied to the combined signal samples is taken. An inverse of a fourier transform of each block entry is multiplied to a result of the fourier transform to produce a fourier transform of the data vector. An inverse fourier transform of the data vector fourier transform is taken to produce data of the K signals.

## Background
This application is a continuation of U.S. patent application Ser. No. 10/079,334, filed Feb. 20, 2002, now U.S. Pat. No. 7,447,255, which is a continuation of U.S. patent application Ser. No. 10/037,710, filed Dec. 31, 2001, now U.S. Pat. No. 6,625,203, which claims priority from U.S. Provisional Patent Application No. 60/287,431, filed Apr. 30, 2001, which applications are all incorporated herein by reference.


BACKGROUND
The invention generally relates to wireless communication systems. In particular, the invention relates to data detection in a wireless communication system.
FIG. 1 is an illustration of a wireless communication system 10. The communication system 10 has base stations 121 to 125 (12) which communicate with base stations 141 to 143 (14). Each base station 12 has an associated operational area, where it communicates with UEs 14 in its operational area.
In some communication systems, such as frequency division duplex using code division multiple access (FDD/CDMA) and time division duplex using code division multiple access (TDD/CDMA), multiple communications are sent over the same frequency spectrum. These communications are differentiated by their channelization codes. To more efficiently use the frequency spectrum, TDD/CDMA communication systems use repeating frames divided into timeslots for communication. A communication sent in such a system will have one or multiple associated codes and timeslots assigned to it.
Since multiple communications may be sent in the same frequency spectrum and at the same time, a receiver in such a system must distinguish between the multiple communications. One approach to detecting such signals is multiuser detection (MUD). In MUD, signals associated with all the UEs 14, users, are detected simultaneously. Another approach to detecting a multi-code transmission from a single transmitter is single user detection (SUD). In SUD, to recover data from the multi-code transmission at the receiver, the received signal is passed through an equalization stage and despread using one or multiple codes. Approaches for implementing MUD and the equalization stage of SUD include using a Cholesky or an approximate Cholesky decomposition. These approaches have a high complexity. The high complexity leads to increased power consumption, which at the UE 14 results in reduced battery life. Accordingly, it is desirable to have alternate approaches to detecting received data.
SUMMARY
A code division multiple access base station receives K data signals over a shared spectrum. The base station receives and samples a combined signal having the K transmitted data signals. A combined channel response matrix is produced. A block column of a cross correlation matrix is determined using the combined channel response matrix. Each block entry of the block column is a K by K matrix. Each block entry of the block column is a K by K matrix. A fourier transform of a complex conjugate transpose of the combined channel response matrix multiplied to the combined signal samples is taken. An inverse of a fourier transform of each block entry is multiplied to a result of the fourier transform to produce a fourier transform of the data vector. An inverse fourier transform of the data vector fourier transform is taken to produce data of the K signals.



BRIEF DESCRIPTION OF THE DRAWING(S)
FIG. 1 is a wireless communication system.
FIG. 2 is a simplified transmitter and a fast joint detection receiver.
FIG. 3 is an illustration of a communication burst.
FIG. 4 is a flow chart of a preferred embodiment for fast joint detection.
FIG. 5 is an illustration of a data burst indicating extended processing areas.
FIGS. 6-11 are graphs illustrating the simulated performance of fast joint detection to other data detection approaches.



DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT(S)
FIG. 2 illustrates a simplified transmitter 26 and receiver 28 using fast joint detection in a TDD/CDMA communication system, although fast joint detection is applicable to other systems, such as FDD/CDMA. In a typical system, a transmitter 26 is in each UE 14 and multiple transmitting circuits 26 sending multiple communications are in each base station 12. The joint detection receiver 28 may be at a base station 12, UEs 14 or both.
The transmitter 26 sends data over a wireless radio channel 30. A data generator 32 in the transmitter 26 generates data to be communicated to the receiver 28. A modulation/spreading/training sequence insertion device 34 spreads the data with the appropriate code(s) and makes the spread reference data time-multiplexed with a midamble training sequence in the appropriate assigned time slot, producing a communication burst or bursts.
A typical communication burst 16 has a midamble 20, a guard period 18 and two data fields 22, 24, as shown in FIG. 3. The midamble 20 separates the two data fields 22, 24 and the guard period 18 separates the communication bursts to allow for the difference in arrival times of bursts transmitted from different transmitters 26. The two data fields 22, 24 contain the communication burst's data.
The communication burst(s) are modulated by a modulator 36 to radio frequency (RF). An antenna 38 radiates the RF signal through the wireless radio channel 30 to an antenna 40 of the receiver 28. The type of modulation used for the transmitted communication can be any of those known to those skilled in the art, such as quadrature phase shift keying (QPSK) or M-ary quadrature amplitude modulation (QAM).
The antenna 40 of the receiver 28 receives various radio frequency signals. The received signals are demodulated by a demodulator 42 to produce a baseband signal. The baseband signal is sampled by a sampling device 43, such as one or multiple analog to digital converters, at the chip rate or a multiple of the chip rate of the transmitted bursts. The samples are processed, such as by a channel estimation device 44 and a fast joint detection device 46, in the time slot and with the appropriate codes assigned to the received bursts. The channel estimation device 44 uses the midamble training sequence component in the baseband samples to provide channel information, such as channel impulse responses. The channel impulse responses for all the transmitted signals can be viewed as a matrix, H. The channel information is used by the fast joint detection device 46 to estimate the transmitted data of the received communication bursts as soft symbols.
The fast joint detection device 46 uses the channel information provided by the channel estimation device 44 and the known spreading codes used by the transmitter 26 to estimate the data of the desired received communication burst(s).
Although fast joint detection is explained using the third generation partnership project (3GPP) universal terrestrial radio access (UTRA) TDD system as the underlying communication system, it is applicable to other systems. That system is a direct sequence wideband CDMA (W-CDMA) system, where the uplink and downlink transmissions are confined to mutually exclusive timeslots.
The receiver 28 receives a total of K bursts that arrive simultaneously. The K bursts are superimposed on top of each other in one observation interval. For the 3GPP UTRA TDD system, each data field of a time slot corresponds to one observation interval. A code used for a kth burst is represented as C(k). The K bursts may originate from K different transmitters or for multi-code transmissions, less than K different transmitters.
Each data field of a communication burst has a predetermined number of transmitted symbols, NS. Each symbol is transmitted using a predetermined number of chips, which is the spreading factor, SF. Accordingly, each data field has NS×SF chips. After passing through the wireless radio channel, each symbol has an impulse response, such as of length W chips. A typical value for W is 57. As a result, each received field has a length of SF×NS+W−1 chips or NC chips.
Each kth field of the K data fields in one observation interval can be modeled at the receiver by Equation 1.

r(k)=A(k)d(k), k=1 . . . K  Equation 1

r(k) is the received contribution of the kth field. A(k) is the combined channel response for the kth field. A(k) is a NC×NS matrix. Each jth column in A(k) is a zero-padded version of the symbol response S(k) of the jth element of d(k). The symbol response S(k) is the convolution of the kth field's estimate response, h(k), and spreading code C(k) for the field. d(k) is the unknown data symbols in the kth data field. h(k) is of length W chips and can be represented by Equation 2.

h(k)=γ(k)·{tilde over (h)}(k)  Equation 2

γ(k) reflects the transmitter gain and path loss. {tilde over (h)}(k) is the channel impulse response.

For uplink communications, each {tilde over (h)}(k) as well as each γ(k) are distinct. For the downlink, all of the fields have the same {tilde over (h)}(k) but each γ(k) is different. If transmit diversity is used in the downlink, each γ(k) and {tilde over (h)}(k) are distinct.
The overall received vector r from all K fields sent over the wireless channel is per Equation 3.




  
    
      
        
          r
          _
        
        =
        
          
            
              ∑
              
                k
                =
                1
              
              K
            
            ⁢
            
              
                r
                _
              
              
                (
                k
                )
              
            
          
          +
          
            n
            _
          
        
      
    
    
      
        Equation
        ⁢
        
          
        
        ⁢
        3
      
    
  




n is a zero-mean noise vector.

By combining the A(k) for all data fields into a total channel response matrix A and all the unknown data for each burst d(k) into a total data vector d, Equation 1 becomes Equation 4.

r=Ad+n  Equation 4

Determining d using a MMSE solution is per Equation 5.

d=R−1(AHr)  Equation 5

(•)H represents the Hermetian function (complex conjugate transpose). R for a MMSE solution is per Equation 6.

R=AHA+σ2I  Equation 6

σ2 is the noise variance, typically obtained from the channel estimation device 44, and I is the identity matrix.

Using fast fourier transforms (FFTs), although other fourier transforms may be used, this equation is solved, preferably, per Equation 7.

[F(d)]k=[Λ(k)]−1[F(AHr)]k  Equation 7

F(•) indicates the FFT function. The [•]k indicate that the equation is solved at each frequency point k. Λ(k) are block entries of size K by K of a block diagonal matrix Λ. The derivation of Λ is described subsequently. Instead of directly solving Equation 7, Equation 7 can be solved using forward and backward substitution.

FIG. 4 is a flow chart for a preferred method of determining the data vector d using fast joint detection. The combined channel response matrix A is determined using the estimated responses h(k) and the spreading code c(k) for each burst c(k), 48, form the combined channel correlation matrix, R=AHA, 49. At each frequency point, a K by K matrix Λ(K) is determined by taking the fourier transform of block entries of a block column of R (block FFT), 50. Preferably, a central column is used, at least w columns from the left or right of the R matrix.
F[AHr]k is determined using a FFT of a matrix multiplication, 51. The inverse of each Λ(k), [Λ(k)]−1, is determined. To determine [F(d)]k, [Λ(k)]−1 and [F(AHr)]k are multiplied at each frequency point. Alternately, [F(d)]k is determined using LU decomposition. Λ(k) is decomposed into a lower triangular matrix, L, and an upper triangular matrix, U, 52. Using forward, Ly=[F(AHr)], 53, and backward substitution, U[F(d)]K=y, 54, [F(d)]K is determined. d is determined by an inverse FFT of F(d), 55.
The derivation of Equation 7 is as follows. A minimum mean square error solution of Equation 4 is determined per Equation 8. Although Equation 7 is a MMSE based solution, fast joint detection can be implemented using other approaches, such as a zero forcing approach.

Rd=(AHA+σ2I)d=AHr  Equation 8

If a zero forcing solution is used, the σ2I term drops out of Equation 8, such as Rd=(AHA)d=AHr. The following is a derivation for the MMSE solution, although an analogous derivation can be used for a zero forcing solution. For illustrative purposes, a simplified example of R with Ns=10 and W=2 is per Equation 9. This example is readily extendable to any Ns and W.





  
    
      
        R
        =
        
          [
          
            
              
                
                  R
                  0
                
              
              
                
                  R
                  1
                  H
                
              
              
                
                  R
                  2
                  H
                
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
            
            
              
                
                  R
                  1
                
              
              
                
                  R
                  0
                
              
              
                
                  R
                  1
                  H
                
              
              
                
                  R
                  2
                  H
                
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
            
            
              
                ...
              
              
                ...
              
              
                ...
              
              
                ...
              
              
                ...
              
              
                ...
              
              
                ...
              
              
                ...
              
              
                ...
              
              
                ...
              
            
            
              
                
                  R
                  2
                
              
              
                
                  R
                  1
                
              
              
                
                  R
                  0
                
              
              
                
                  R
                  1
                  H
                
              
              
                
                  R
                  2
                  H
                
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
            
            
              
                0
              
              
                
                  R
                  2
                
              
              
                
                  R
                  1
                
              
              
                
                  R
                  0
                
              
              
                
                  R
                  1
                  H
                
              
              
                
                  R
                  2
                  H
                
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
            
            
              
                0
              
              
                0
              
              
                
                  R
                  2
                
              
              
                
                  R
                  1
                
              
              
                
                  R
                  0
                
              
              
                
                  R
                  1
                  H
                
              
              
                
                  R
                  2
                  H
                
              
              
                0
              
              
                0
              
              
                0
              
            
            
              
                0
              
              
                0
              
              
                0
              
              
                
                  R
                  2
                
              
              
                
                  R
                  1
                
              
              
                
                  R
                  0
                
              
              
                
                  R
                  1
                  H
                
              
              
                
                  R
                  2
                  H
                
              
              
                0
              
              
                0
              
            
            
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                
                  R
                  2
                
              
              
                
                  R
                  1
                
              
              
                
                  R
                  0
                
              
              
                
                  R
                  1
                  H
                
              
              
                
                  R
                  2
                  H
                
              
              
                0
              
            
            
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                
                  R
                  2
                
              
              
                
                  R
                  1
                
              
              
                
                  R
                  0
                
              
              
                
                  R
                  1
                  H
                
              
              
                
                  R
                  2
                  H
                
              
            
            
              
                ...
              
              
                ...
              
              
                ...
              
              
                ...
              
              
                ...
              
              
                ...
              
              
                ...
              
              
                ...
              
              
                ...
              
              
                ...
              
            
            
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                
                  R
                  2
                
              
              
                
                  R
                  1
                
              
              
                
                  R
                  0
                
              
              
                
                  R
                  1
                  H
                
              
            
            
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                
                  R
                  2
                
              
              
                
                  R
                  1
                
              
              
                
                  R
                  0
                
              
            
          
          ]
        
      
    
    
      
        Equation
        ⁢
        
          
        
        ⁢
        9
      
    
  




The matrix R is of size (KNs) by (KNs) in general. Each entry, Ri, in the R matrix is a K by K block. The sub-matrix, within the dotted lines of R, is block-circulant, i.e. a block-wise extension of a circulant matrix. The portion of R, which is not block-circulant, depends on the maximum multipath delay spread, W.
A block-circulant extension of the matrix R, RC, in Equation 9 is per Equation 10.




  
    
      
        
          R
          c
        
        =
        
          [
          
            
              
                
                  R
                  0
                
              
              
                
                  R
                  1
                  H
                
              
              
                
                  R
                  2
                  H
                
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                
                  R
                  2
                
              
              
                
                  R
                  1
                
              
            
            
              
                
                  R
                  1
                
              
              
                
                  R
                  0
                
              
              
                
                  R
                  1
                  H
                
              
              
                
                  R
                  2
                  H
                
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                
                  R
                  2
                
              
            
            
              
                ...
              
              
                ...
              
              
                ...
              
              
                ...
              
              
                ...
              
              
                ...
              
              
                ...
              
              
                ...
              
              
                ...
              
              
                ...
              
            
            
              
                
                  R
                  2
                
              
              
                
                  R
                  1
                
              
              
                
                  R
                  0
                
              
              
                
                  R
                  1
                  H
                
              
              
                
                  R
                  2
                  H
                
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
            
            
              
                0
              
              
                
                  R
                  2
                
              
              
                
                  R
                  1
                
              
              
                
                  R
                  0
                
              
              
                
                  R
                  1
                  H
                
              
              
                
                  R
                  2
                  H
                
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
            
            
              
                0
              
              
                0
              
              
                
                  R
                  2
                
              
              
                
                  R
                  1
                
              
              
                
                  R
                  0
                
              
              
                
                  R
                  1
                  H
                
              
              
                
                  R
                  2
                  H
                
              
              
                0
              
              
                0
              
              
                0
              
            
            
              
                0
              
              
                0
              
              
                0
              
              
                
                  R
                  2
                
              
              
                
                  R
                  1
                
              
              
                
                  R
                  0
                
              
              
                
                  R
                  1
                  H
                
              
              
                
                  R
                  2
                  H
                
              
              
                0
              
              
                0
              
            
            
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                
                  R
                  2
                
              
              
                
                  R
                  1
                
              
              
                
                  R
                  0
                
              
              
                
                  R
                  1
                  H
                
              
              
                
                  R
                  2
                  H
                
              
              
                0
              
            
            
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                
                  R
                  2
                
              
              
                
                  R
                  1
                
              
              
                
                  R
                  0
                
              
              
                
                  R
                  1
                  H
                
              
              
                
                  R
                  2
                  H
                
              
            
            
              
                ...
              
              
                ...
              
              
                ...
              
              
                ...
              
              
                ...
              
              
                ...
              
              
                ...
              
              
                ...
              
              
                ...
              
              
                ...
              
            
            
              
                
                  R
                  2
                  H
                
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                
                  R
                  2
                
              
              
                
                  R
                  1
                
              
              
                
                  R
                  0
                
              
              
                
                  R
                  1
                  H
                
              
            
            
              
                
                  R
                  1
                  H
                
              
              
                
                  R
                  2
                  H
                
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                
                  R
                  2
                
              
              
                
                  R
                  1
                
              
              
                
                  R
                  0
                
              
            
          
          ]
        
      
    
    
      
        Equation
        ⁢
        
          
        
        ⁢
        10
      
    
  




A “Discrete Fourier Transform (DFT)-like” matrix D is determined such that Rc=DΛDH. One such matrix D is per Equation 11.




  
    
      
        D
        =
        
          [
          
            
              
                I
              
              
                
                  
                    e
                    
                      
                        j
                        ⁢
                        
                          
                        
                        ⁢
                        2
                        ⁢
                        
                          
                        
                        ⁢
                        π
                      
                      
                        N
                        s
                      
                    
                  
                  ⁢
                  
                    I
                    K
                  
                
              
              
                
                  
                    e
                    
                      
                        j
                        ⁢
                        
                          
                        
                        ⁢
                        4
                        ⁢
                        
                          
                        
                        ⁢
                        π
                      
                      
                        N
                        s
                      
                    
                  
                  ⁢
                  
                    I
                    K
                  
                
              
              
                ...
              
              
                ...
              
              
                
                  
                    e
                    
                      
                        j
                        ⁢
                        
                          
                        
                        ⁢
                        18
                        ⁢
                        
                          
                        
                        ⁢
                        π
                      
                      
                        N
                        s
                      
                    
                  
                  ⁢
                  
                    I
                    K
                  
                
              
            
            
              
                I
              
              
                
                  
                    e
                    
                      
                        j
                        ⁢
                        
                          
                        
                        ⁢
                        4
                        ⁢
                        
                          
                        
                        ⁢
                        π
                      
                      
                        N
                        s
                      
                    
                  
                  ⁢
                  
                    I
                    K
                  
                
              
              
                
                  
                    e
                    
                      
                        j
                        ⁢
                        
                          
                        
                        ⁢
                        8
                        ⁢
                        
                          
                        
                        ⁢
                        π
                      
                      
                        N
                        s
                      
                    
                  
                  ⁢
                  
                    I
                    K
                  
                
              
              
                ...
              
              
                ...
              
              
                
                  
                    e
                    
                      
                        j
                        ⁢
                        
                          
                        
                        ⁢
                        36
                        ⁢
                        
                          
                        
                        ⁢
                        π
                      
                      
                        N
                        s
                      
                    
                  
                  ⁢
                  
                    I
                    K
                  
                
              
            
            
              
                ⋮
              
              
                ⋮
              
              
                ⋮
              
              
                
                  
                
              
              
                
                  
                
              
              
                ⋮
              
            
            
              
                I
              
              
                
                  
                    e
                    
                      
                        j
                        ⁢
                        
                          
                        
                        ⁢
                        18
                        ⁢
                        
                          
                        
                        ⁢
                        π
                      
                      
                        N
                        s
                      
                    
                  
                  ⁢
                  
                    I
                    K
                  
                
              
              
                
                  
                    e
                    
                      
                        j
                        ⁢
                        
                          
                        
                        ⁢
                        36
                        ⁢
                        
                          
                        
                        ⁢
                        π
                      
                      
                        N
                        s
                      
                    
                  
                  ⁢
                  
                    I
                    K
                  
                
              
              
                ...
              
              
                ...
              
              
                
                  
                    e
                    
                      
                        j
                        ⁢
                        
                          
                        
                        ⁢
                        162
                        ⁢
                        
                          
                        
                        ⁢
                        π
                      
                      
                        N
                        s
                      
                    
                  
                  ⁢
                  
                    I
                    K
                  
                
              
            
            
              
                I
              
              
                
                  
                    e
                    
                      
                        j
                        ⁢
                        
                          
                        
                        ⁢
                        20
                        ⁢
                        
                          
                        
                        ⁢
                        π
                      
                      
                        N
                        s
                      
                    
                  
                  ⁢
                  
                    I
                    K
                  
                
              
              
                
                  
                    e
                    
                      
                        j
                        ⁢
                        
                          
                        
                        ⁢
                        40
                        ⁢
                        
                          
                        
                        ⁢
                        π
                      
                      
                        N
                        s
                      
                    
                  
                  ⁢
                  
                    I
                    K
                  
                
              
              
                ...
              
              
                ...
              
              
                
                  
                    e
                    
                      
                        j
                        ⁢
                        
                          
                        
                        ⁢
                        180
                        ⁢
                        
                          
                        
                        ⁢
                        π
                      
                      
                        N
                        s
                      
                    
                  
                  ⁢
                  
                    I
                    K
                  
                
              
            
          
          ]
        
      
    
    
      
        Equation
        ⁢
        
          
        
        ⁢
        11
      
    
  




IK is a K by K identity matrix.

The product DHD is per Equation 9.

DHD=NsIKNs  Equation 12

IKNs is a KNs by KNs identity matrix. The block circulant matrix Rc is multiplied by the D matrix, such as per Equation 13.





  
    
      
        
          
            R
            c
          
          ⁢
          D
        
        =
        
          [
          
            
              
                
                  (
                  
                    
                      
                        
                          
                            R
                            0
                          
                          +
                          
                            R
                            1
                            H
                          
                          +
                        
                      
                    
                    
                      
                        
                          
                            R
                            2
                            H
                          
                          +
                          
                            R
                            1
                          
                          +
                          
                            R
                            2
                          
                        
                      
                    
                  
                  )
                
              
              
                ⋮
              
              
                
                  (
                  
                    
                      
                        
                          
                            
                              R
                              0
                            
                            ⁢
                            
                              e
                              
                                
                                  j
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  2
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  π
                                
                                
                                  N
                                  s
                                
                              
                            
                          
                          +
                          
                            
                              R
                              1
                              H
                            
                            ⁢
                            
                              e
                              
                                
                                  j
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  4
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  π
                                
                                
                                  N
                                  s
                                
                              
                            
                          
                          +
                          
                            
                              R
                              2
                              H
                            
                            ⁢
                            
                              e
                              
                                
                                  j
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  6
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  π
                                
                                
                                  N
                                  s
                                
                              
                            
                          
                          +
                        
                      
                    
                    
                      
                        
                          
                            
                              R
                              2
                            
                            ⁢
                            
                              e
                              
                                
                                  j
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  18
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  π
                                
                                
                                  N
                                  s
                                
                              
                            
                          
                          +
                          
                            
                              R
                              1
                            
                            ⁢
                            
                              e
                              
                                
                                  j
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  20
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  π
                                
                                
                                  N
                                  s
                                
                              
                            
                          
                        
                      
                    
                  
                  )
                
              
              
                ⋮
              
              
                ...
              
              
                
                  (
                  
                    
                      
                        
                          
                            
                              R
                              0
                            
                            ⁢
                            
                              e
                              
                                
                                  j
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  18
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  π
                                
                                
                                  N
                                  s
                                
                              
                            
                          
                          +
                          
                            
                              R
                              1
                              H
                            
                            ⁢
                            
                              e
                              
                                
                                  j
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  36
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  π
                                
                                
                                  N
                                  s
                                
                              
                            
                          
                          +
                          
                            
                              R
                              2
                              H
                            
                            ⁢
                            
                              e
                              
                                
                                  j
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  54
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  π
                                
                                
                                  N
                                  s
                                
                              
                            
                          
                          +
                        
                      
                    
                    
                      
                        
                          
                            
                              R
                              2
                            
                            ⁢
                            
                              e
                              
                                
                                  j
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  162
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  π
                                
                                
                                  N
                                  s
                                
                              
                            
                          
                          +
                          
                            
                              R
                              1
                            
                            ⁢
                            
                              e
                              
                                
                                  j
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  180
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  π
                                
                                
                                  N
                                  s
                                
                              
                            
                          
                        
                      
                    
                  
                  )
                
              
            
            
              
                
                  (
                  
                    
                      
                        
                          
                            R
                            0
                          
                          +
                          
                            R
                            1
                            H
                          
                          +
                        
                      
                    
                    
                      
                        
                          
                            R
                            2
                            H
                          
                          +
                          
                            R
                            1
                          
                          +
                          
                            R
                            2
                          
                        
                      
                    
                  
                  )
                
              
              
                ⋮
              
              
                
                  (
                  
                    
                      
                        
                          
                            
                              R
                              1
                            
                            ⁢
                            
                              e
                              
                                
                                  j
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  2
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  π
                                
                                
                                  N
                                  s
                                
                              
                            
                          
                          +
                          
                            
                              R
                              0
                            
                            ⁢
                            
                              e
                              
                                
                                  j
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  4
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  π
                                
                                
                                  N
                                  s
                                
                              
                            
                          
                          +
                          
                            
                              R
                              1
                              H
                            
                            ⁢
                            
                              e
                              
                                
                                  j
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  6
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  π
                                
                                
                                  N
                                  s
                                
                              
                            
                          
                          +
                        
                      
                    
                    
                      
                        
                          
                            
                              R
                              2
                              H
                            
                            ⁢
                            
                              e
                              
                                
                                  j
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  18
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  π
                                
                                
                                  N
                                  s
                                
                              
                            
                          
                          +
                          
                            
                              R
                              2
                            
                            ⁢
                            
                              e
                              
                                
                                  j
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  20
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  π
                                
                                
                                  N
                                  s
                                
                              
                            
                          
                        
                      
                    
                  
                  )
                
              
              
                ⋮
              
              
                ...
              
              
                
                  (
                  
                    
                      
                        
                          
                            
                              R
                              1
                            
                            ⁢
                            
                              e
                              
                                
                                  j
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  18
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  π
                                
                                
                                  N
                                  s
                                
                              
                            
                          
                          +
                          
                            
                              R
                              0
                            
                            ⁢
                            
                              e
                              
                                
                                  j
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  36
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  π
                                
                                
                                  N
                                  s
                                
                              
                            
                          
                          +
                          
                            
                              R
                              1
                              H
                            
                            ⁢
                            
                              e
                              
                                
                                  j
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  54
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  π
                                
                                
                                  N
                                  s
                                
                              
                            
                          
                          +
                        
                      
                    
                    
                      
                        
                          
                            
                              R
                              2
                              H
                            
                            ⁢
                            
                              e
                              
                                
                                  j
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  72
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  π
                                
                                
                                  N
                                  s
                                
                              
                            
                          
                          +
                          
                            
                              R
                              2
                            
                            ⁢
                            
                              e
                              
                                
                                  j
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  180
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  π
                                
                                
                                  N
                                  s
                                
                              
                            
                          
                        
                      
                    
                  
                  )
                
              
            
            
              
                ⋮
              
              
                
                  
                
              
              
                ⋮
              
              
                ⋮
              
              
                
                  
                
              
              
                ⋮
              
            
            
              
                
                  (
                  
                    
                      
                        
                          
                            R
                            0
                          
                          +
                          
                            R
                            1
                            H
                          
                          +
                        
                      
                    
                    
                      
                        
                          
                            R
                            2
                            H
                          
                          +
                          
                            R
                            1
                          
                          +
                          
                            R
                            2
                          
                        
                      
                    
                  
                  )
                
              
              
                
                  
                    
                  
                  ⁢
                  ⋮
                
              
              
                
                  (
                  
                    
                      
                        
                          
                            
                              R
                              2
                            
                            ⁢
                            
                              e
                              
                                
                                  j
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  12
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  π
                                
                                
                                  N
                                  s
                                
                              
                            
                          
                          +
                          
                            
                              R
                              1
                            
                            ⁢
                            
                              e
                              
                                
                                  j
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  14
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  π
                                
                                
                                  N
                                  s
                                
                              
                            
                          
                          +
                          
                            
                              R
                              0
                            
                            ⁢
                            
                              e
                              
                                
                                  j
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  16
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  π
                                
                                
                                  N
                                  s
                                
                              
                            
                          
                          +
                        
                      
                    
                    
                      
                        
                          
                            
                              R
                              1
                              H
                            
                            ⁢
                            
                              e
                              
                                
                                  j
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  18
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  π
                                
                                
                                  N
                                  s
                                
                              
                            
                          
                          +
                          
                            
                              R
                              2
                              H
                            
                            ⁢
                            
                              e
                              
                                
                                  j
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  20
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  π
                                
                                
                                  N
                                  s
                                
                              
                            
                          
                        
                      
                    
                  
                  )
                
              
              
                ⋮
              
              
                ...
              
              
                
                  (
                  
                    
                      
                        
                          
                            
                              R
                              0
                            
                            ⁢
                            
                              e
                              
                                
                                  j
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  108
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  π
                                
                                
                                  N
                                  s
                                
                              
                            
                          
                          +
                          
                            
                              R
                              1
                              H
                            
                            ⁢
                            
                              e
                              
                                
                                  j
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  126
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  π
                                
                                
                                  N
                                  s
                                
                              
                            
                          
                          +
                          
                            
                              R
                              0
                            
                            ⁢
                            
                              e
                              
                                
                                  j
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  144
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  π
                                
                                
                                  N
                                  s
                                
                              
                            
                          
                          +
                        
                      
                    
                    
                      
                        
                          
                            
                              R
                              1
                              H
                            
                            ⁢
                            
                              e
                              
                                
                                  j
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  162
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  π
                                
                                
                                  N
                                  s
                                
                              
                            
                          
                          +
                          
                            
                              R
                              2
                              H
                            
                            ⁢
                            
                              e
                              
                                
                                  j
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  180
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  π
                                
                                
                                  N
                                  s
                                
                              
                            
                          
                        
                      
                    
                  
                  )
                
              
            
            
              
                ⋮
              
              
                
                  
                
              
              
                ⋮
              
              
                
                  
                
              
              
                
                  
                
              
              
                ⋮
              
            
          
          ]
        
      
    
    
      
        Equation
        ⁢
        
          
        
        ⁢
        13
      
    
  




Each entry of RcD is a K by K block. A block-diagonal matrix Λ is per Equation 14.





  
    
      
        Λ
        ⁢
        
          
            Δ
            =
          
          ⁡
          
            [
            
              
                
                  
                    Λ
                    
                      (
                      1
                      )
                    
                  
                
                
                  
                    
                  
                
                
                  
                    
                  
                
                
                  
                    
                  
                
                
                  
                    
                  
                
              
              
                
                  
                    
                  
                
                
                  
                    Λ
                    
                      (
                      2
                      )
                    
                  
                
                
                  
                    
                  
                
                
                  
                    
                  
                
                
                  
                    
                  
                
              
              
                
                  
                    
                  
                
                
                  
                    
                  
                
                
                  
                    Λ
                    
                      (
                      3
                      )
                    
                  
                
                
                  
                    
                  
                
                
                  
                    
                  
                
              
              
                
                  
                    
                  
                
                
                  
                    
                  
                
                
                  
                    
                  
                
                
                  ⋰
                
                
                  
                    
                  
                
              
              
                
                  
                    
                  
                
                
                  
                    
                  
                
                
                  
                    
                  
                
                
                  
                    
                  
                
                
                  
                    Λ
                    
                      (
                      
                        N
                        s
                      
                      )
                    
                  
                
              
            
            ]
          
        
      
    
    
      
        Equation
        ⁢
        
          
        
        ⁢
        14
      
    
  




Λ is of size (KNs) by (KNs). Each entry Λ(i) of Λ is per Equation 15.





  
    
      
        
          Λ
          
            (
            i
            )
          
        
        =
        
          
            [
            
              
                
                  
                    λ
                    11
                    
                      (
                      i
                      )
                    
                  
                
                
                  ...
                
                
                  
                    λ
                    
                      1
                      ⁢
                      
                        
                      
                      ⁢
                      K
                    
                    
                      (
                      i
                      )
                    
                  
                
              
              
                
                  ⋮
                
                
                  
                    
                  
                
                
                  ⋮
                
              
              
                
                  
                    λ
                    
                      K
                      ⁢
                      
                        
                      
                      ⁢
                      1
                    
                    
                      (
                      i
                      )
                    
                  
                
                
                  ...
                
                
                  
                    λ
                    KK
                    
                      (
                      i
                      )
                    
                  
                
              
            
            ]
          
          .
        
      
    
    
      
        Equation
        ⁢
        
          
        
        ⁢
        15
      
    
  




Λ(i) is a K by K block and has K2 non-zero entries.

The D matrix is multiplied to the Λ matrix, such as per Equation 16.




  
    
      
        
          D
          ⁢
          
            
          
          ⁢
          Λ
        
        =
        
          [
          
            
              
                
                  Λ
                  
                    (
                    1
                    )
                  
                
              
              
                
                  
                    Λ
                    
                      (
                      2
                      )
                    
                  
                  ⁢
                  
                    e
                    
                      
                        j
                        ⁢
                        
                          
                        
                        ⁢
                        2
                        ⁢
                        
                          
                        
                        ⁢
                        π
                      
                      
                        N
                        s
                      
                    
                  
                
              
              
                
                  
                    Λ
                    
                      (
                      3
                      )
                    
                  
                  ⁢
                  
                    e
                    
                      
                        j
                        ⁢
                        
                          
                        
                        ⁢
                        4
                        ⁢
                        
                          
                        
                        ⁢
                        π
                      
                      
                        N
                        s
                      
                    
                  
                
              
              
                ...
              
              
                
                  
                    Λ
                    
                      (
                      
                        
                          N
                          s
                        
                        -
                        1
                      
                      )
                    
                  
                  ⁢
                  
                    e
                    
                      
                        j
                        ⁢
                        
                          
                        
                        ⁢
                        16
                        ⁢
                        
                          
                        
                        ⁢
                        π
                      
                      
                        N
                        s
                      
                    
                  
                
              
              
                
                  
                    Λ
                    
                      (
                      
                        N
                        s
                      
                      )
                    
                  
                  ⁢
                  
                    e
                    
                      
                        j
                        ⁢
                        
                          
                        
                        ⁢
                        18
                        ⁢
                        
                          
                        
                        ⁢
                        π
                      
                      
                        N
                        s
                      
                    
                  
                
              
            
            
              
                
                  Λ
                  
                    (
                    1
                    )
                  
                
              
              
                
                  
                    Λ
                    
                      (
                      2
                      )
                    
                  
                  ⁢
                  
                    e
                    
                      
                        j
                        ⁢
                        
                          
                        
                        ⁢
                        4
                        ⁢
                        
                          
                        
                        ⁢
                        π
                      
                      
                        N
                        s
                      
                    
                  
                
              
              
                
                  
                    Λ
                    
                      (
                      3
                      )
                    
                  
                  ⁢
                  
                    e
                    
                      
                        j
                        ⁢
                        
                          
                        
                        ⁢
                        8
                        ⁢
                        
                          
                        
                        ⁢
                        π
                      
                      
                        N
                        s
                      
                    
                  
                
              
              
                ...
              
              
                
                  
                    Λ
                    
                      (
                      
                        
                          N
                          s
                        
                        -
                        1
                      
                      )
                    
                  
                  ⁢
                  
                    e
                    
                      
                        j
                        ⁢
                        
                          
                        
                        ⁢
                        32
                        ⁢
                        
                          
                        
                        ⁢
                        π
                      
                      
                        N
                        s
                      
                    
                  
                
              
              
                
                  
                    Λ
                    
                      (
                      
                        N
                        s
                      
                      )
                    
                  
                  ⁢
                  
                    e
                    
                      
                        j
                        ⁢
                        
                          
                        
                        ⁢
                        36
                        ⁢
                        
                          
                        
                        ⁢
                        π
                      
                      
                        N
                        s
                      
                    
                  
                
              
            
            
              
                ⋮
              
              
                ⋮
              
              
                ⋮
              
              
                
                  
                
              
              
                ⋮
              
              
                ⋮
              
            
            
              
                
                  Λ
                  
                    (
                    1
                    )
                  
                
              
              
                
                  
                    Λ
                    
                      (
                      2
                      )
                    
                  
                  ⁢
                  
                    e
                    
                      
                        j
                        ⁢
                        
                          
                        
                        ⁢
                        14
                        ⁢
                        
                          
                        
                        ⁢
                        π
                      
                      
                        N
                        s
                      
                    
                  
                
              
              
                
                  
                    Λ
                    
                      (
                      3
                      )
                    
                  
                  ⁢
                  
                    e
                    
                      
                        j
                        ⁢
                        
                          
                        
                        ⁢
                        28
                        ⁢
                        
                          
                        
                        ⁢
                        π
                      
                      
                        N
                        s
                      
                    
                  
                
              
              
                ...
              
              
                
                  
                    Λ
                    
                      (
                      
                        
                          N
                          s
                        
                        -
                        1
                      
                      )
                    
                  
                  ⁢
                  
                    e
                    
                      
                        j
                        ⁢
                        
                          
                        
                        ⁢
                        112
                        ⁢
                        
                          
                        
                        ⁢
                        π
                      
                      
                        N
                        s
                      
                    
                  
                
              
              
                
                  
                    Λ
                    
                      (
                      
                        N
                        s
                      
                      )
                    
                  
                  ⁢
                  
                    e
                    
                      
                        j
                        ⁢
                        
                          
                        
                        ⁢
                        126
                        ⁢
                        
                          
                        
                        ⁢
                        π
                      
                      
                        N
                        s
                      
                    
                  
                
              
            
            
              
                
                  Λ
                  
                    (
                    1
                    )
                  
                
              
              
                
                  
                    Λ
                    
                      (
                      2
                      )
                    
                  
                  ⁢
                  
                    e
                    
                      
                        j
                        ⁢
                        
                          
                        
                        ⁢
                        16
                        ⁢
                        
                          
                        
                        ⁢
                        π
                      
                      
                        N
                        s
                      
                    
                  
                
              
              
                
                  
                    Λ
                    
                      (
                      3
                      )
                    
                  
                  ⁢
                  
                    e
                    
                      
                        j
                        ⁢
                        
                          
                        
                        ⁢
                        32
                        ⁢
                        
                          
                        
                        ⁢
                        π
                      
                      
                        N
                        s
                      
                    
                  
                
              
              
                ...
              
              
                
                  
                    Λ
                    
                      (
                      
                        
                          N
                          s
                        
                        -
                        1
                      
                      )
                    
                  
                  ⁢
                  
                    e
                    
                      
                        j
                        ⁢
                        
                          
                        
                        ⁢
                        128
                        ⁢
                        
                          
                        
                        ⁢
                        π
                      
                      
                        N
                        s
                      
                    
                  
                
              
              
                
                  
                    Λ
                    
                      (
                      
                        N
                        s
                      
                      )
                    
                  
                  ⁢
                  
                    e
                    
                      
                        j
                        ⁢
                        
                          
                        
                        ⁢
                        144
                        ⁢
                        
                          
                        
                        ⁢
                        π
                      
                      
                        N
                        s
                      
                    
                  
                
              
            
            
              
                ⋮
              
              
                ⋮
              
              
                ⋮
              
              
                
                  
                
              
              
                ⋮
              
              
                ⋮
              
            
          
          ]
        
      
    
    
      
        Equation
        ⁢
        
          
        
        ⁢
        16
      
    
  




Each entry of DΛ as shown in Equation 16 is a K by K block.

The system of equations produced by equating each row of RcD with each row of DΛ is consistent. Accordingly, the same set of equations result by equating any row of RcD with the same row of DΛ. To illustrate for Equation 13, the first row-block of RcD is per Equation 17.




  
    
      
        [
        
          
            
              
                
                  (
                  
                    
                      R
                      0
                    
                    +
                    
                      R
                      1
                      H
                    
                    +
                    
                      R
                      2
                      H
                    
                    +
                    
                      R
                      1
                    
                    +
                    
                      R
                      2
                    
                  
                  )
                
                ,
              
            
          
          
            
              
                
                  (
                  
                    
                      
                        R
                        0
                      
                      ⁢
                      
                        e
                        
                          
                            j
                            ⁢
                            
                              
                            
                            ⁢
                            2
                            ⁢
                            
                              
                            
                            ⁢
                            π
                          
                          
                            N
                            s
                          
                        
                      
                    
                    +
                    
                      
                        R
                        1
                        H
                      
                      ⁢
                      
                        e
                        
                          
                            j
                            ⁢
                            
                              
                            
                            ⁢
                            4
                            ⁢
                            
                              
                            
                            ⁢
                            π
                          
                          
                            N
                            s
                          
                        
                      
                    
                    +
                    
                      
                        R
                        2
                        H
                      
                      ⁢
                      
                        e
                        
                          
                            j
                            ⁢
                            
                              
                            
                            ⁢
                            6
                            ⁢
                            
                              
                            
                            ⁢
                            π
                          
                          
                            N
                            s
                          
                        
                      
                    
                    +
                    
                      
                        R
                        2
                      
                      ⁢
                      
                        e
                        
                          
                            j
                            ⁢
                            
                              
                            
                            ⁢
                            18
                            ⁢
                            
                              
                            
                            ⁢
                            π
                          
                          
                            N
                            s
                          
                        
                      
                    
                    +
                    
                      
                        R
                        1
                      
                      ⁢
                      
                        e
                        
                          
                            j
                            ⁢
                            
                              
                            
                            ⁢
                            20
                            ⁢
                            
                              
                            
                            ⁢
                            π
                          
                          
                            N
                            s
                          
                        
                      
                    
                  
                  )
                
                ,
                ...
                ⁢
                
                  
                
                ,
              
            
          
          
            
              
                
                  (
                  
                    
                      
                        R
                        0
                      
                      ⁢
                      
                        e
                        
                          
                            j
                            ⁢
                            
                              
                            
                            ⁢
                            16
                            ⁢
                            
                              
                            
                            ⁢
                            π
                          
                          
                            N
                            s
                          
                        
                      
                    
                    +
                    
                      
                        R
                        1
                        H
                      
                      ⁢
                      
                        e
                        
                          
                            j
                            ⁢
                            
                              
                            
                            ⁢
                            32
                            ⁢
                            
                              
                            
                            ⁢
                            π
                          
                          
                            N
                            s
                          
                        
                      
                    
                    +
                    
                      
                        R
                        2
                        H
                      
                      ⁢
                      
                        e
                        
                          
                            j
                            ⁢
                            
                              
                            
                            ⁢
                            48
                            ⁢
                            
                              
                            
                            ⁢
                            π
                          
                          
                            N
                            s
                          
                        
                      
                    
                    +
                    
                      
                        R
                        2
                      
                      ⁢
                      
                        e
                        
                          
                            j
                            ⁢
                            
                              
                            
                            ⁢
                            144
                            ⁢
                            
                              
                            
                            ⁢
                            π
                          
                          
                            N
                            s
                          
                        
                      
                    
                    +
                    
                      
                        R
                        1
                      
                      ⁢
                      
                        e
                        
                          
                            j
                            ⁢
                            
                              
                            
                            ⁢
                            160
                            ⁢
                            
                              
                            
                            ⁢
                            π
                          
                          
                            N
                            s
                          
                        
                      
                    
                  
                  )
                
                ,
              
            
          
          
            
              
                (
                
                  
                    
                      R
                      0
                    
                    ⁢
                    
                      e
                      
                        
                          j
                          ⁢
                          
                            
                          
                          ⁢
                          18
                          ⁢
                          
                            
                          
                          ⁢
                          π
                        
                        
                          N
                          s
                        
                      
                    
                  
                  +
                  
                    
                      R
                      1
                      H
                    
                    ⁢
                    
                      e
                      
                        
                          j
                          ⁢
                          
                            
                          
                          ⁢
                          36
                          ⁢
                          
                            
                          
                          ⁢
                          π
                        
                        
                          N
                          s
                        
                      
                    
                  
                  +
                  
                    
                      R
                      2
                      H
                    
                    ⁢
                    
                      e
                      
                        
                          j
                          ⁢
                          
                            
                          
                          ⁢
                          54
                          ⁢
                          
                            
                          
                          ⁢
                          π
                        
                        
                          N
                          s
                        
                      
                    
                  
                  +
                  
                    
                      R
                      2
                    
                    ⁢
                    
                      e
                      
                        
                          j
                          ⁢
                          
                            
                          
                          ⁢
                          162
                          ⁢
                          
                            
                          
                          ⁢
                          π
                        
                        
                          N
                          s
                        
                      
                    
                  
                  +
                  
                    
                      R
                      1
                    
                    ⁢
                    
                      e
                      
                        
                          j
                          ⁢
                          
                            
                          
                          ⁢
                          180
                          ⁢
                          
                            
                          
                          ⁢
                          π
                        
                        
                          N
                          s
                        
                      
                    
                  
                
                )
              
            
          
        
        ]
      
    
    
      
        Equation
        ⁢
        
          
        
        ⁢
        17
      
    
  




The first row-block of DΛ is per Equation 18.




  
    
      
        [
        
          
            
              
                
                  Λ
                  
                    (
                    1
                    )
                  
                
                ,
                
                  
                    Λ
                    
                      (
                      2
                      )
                    
                  
                  ⁢
                  
                    e
                    
                      
                        j
                        ⁢
                        
                          
                        
                        ⁢
                        2
                        ⁢
                        
                          
                        
                        ⁢
                        π
                      
                      
                        N
                        s
                      
                    
                  
                
                ,
                
                  
                    Λ
                    
                      (
                      3
                      )
                    
                  
                  ⁢
                  
                    e
                    
                      
                        j
                        ⁢
                        
                          
                        
                        ⁢
                        4
                        ⁢
                        
                          
                        
                        ⁢
                        π
                      
                      
                        N
                        s
                      
                    
                  
                  ⁢
                  
                    
                  
                  ⁢
                  ...
                
                ⁢
                
                  
                
                ,
              
            
          
          
            
              
                
                  
                    Λ
                    
                      (
                      
                        
                          N
                          s
                        
                        -
                        1
                      
                      )
                    
                  
                  ⁢
                  
                    e
                    
                      
                        j
                        ⁢
                        
                          
                        
                        ⁢
                        16
                        ⁢
                        
                          
                        
                        ⁢
                        π
                      
                      
                        N
                        s
                      
                    
                  
                
                ,
                
                  
                    Λ
                    
                      (
                      
                        N
                        s
                      
                      )
                    
                  
                  ⁢
                  
                    e
                    
                      
                        j
                        ⁢
                        
                          
                        
                        ⁢
                        18
                        ⁢
                        
                          
                        
                        ⁢
                        π
                      
                      
                        N
                        s
                      
                    
                  
                
              
            
          
        
        ]
      
    
    
      
        Equation
        ⁢
        
          
        
        ⁢
        18
      
    
  




Equating the entries of these two rows, Equations 19 and 20 result.




  
    
      
        
          Λ
          
            (
            1
            )
          
        
        =
        
          (
          
            
              R
              0
            
            +
            
              R
              1
              H
            
            +
            
              R
              2
              H
            
            +
            
              R
              1
            
            +
            
              R
              2
            
          
          )
        
      
    
    
      
        Equation
        ⁢
        
          
        
        ⁢
        19
      
    
  
  
    
      
        
          
            
              
                
                  Λ
                  
                    (
                    2
                    )
                  
                
                ⁢
                
                  e
                  
                    
                      j
                      ⁢
                      
                        
                      
                      ⁢
                      2
                      ⁢
                      
                        
                      
                      ⁢
                      π
                    
                    
                      N
                      s
                    
                  
                
              
              =
              
              ⁢
              
                (
                
                  
                    
                      
                        
                          
                            R
                            0
                          
                          ⁢
                          
                            e
                            
                              
                                j
                                ⁢
                                
                                  
                                
                                ⁢
                                2
                                ⁢
                                
                                  
                                
                                ⁢
                                π
                              
                              
                                N
                                s
                              
                            
                          
                        
                        +
                        
                          
                            R
                            1
                            H
                          
                          ⁢
                          
                            e
                            
                              
                                j
                                ⁢
                                
                                  
                                
                                ⁢
                                4
                                ⁢
                                
                                  
                                
                                ⁢
                                π
                              
                              
                                N
                                s
                              
                            
                          
                        
                        +
                        
                          
                            R
                            2
                            H
                          
                          ⁢
                          
                            e
                            
                              
                                j
                                ⁢
                                
                                  
                                
                                ⁢
                                6
                                ⁢
                                
                                  
                                
                                ⁢
                                π
                              
                              
                                N
                                s
                              
                            
                          
                        
                        +
                      
                    
                  
                  
                    
                      
                        
                          
                            R
                            2
                          
                          ⁢
                          
                            e
                            
                              
                                j
                                ⁢
                                
                                  
                                
                                ⁢
                                18
                                ⁢
                                
                                  
                                
                                ⁢
                                π
                              
                              
                                N
                                s
                              
                            
                          
                        
                        +
                        
                          
                            R
                            1
                          
                          ⁢
                          
                            e
                            
                              
                                j
                                ⁢
                                
                                  
                                
                                ⁢
                                20
                                ⁢
                                
                                  
                                
                                ⁢
                                π
                              
                              
                                N
                                s
                              
                            
                          
                        
                      
                    
                  
                
                )
              
            
          
        
        
          
            
              =
              
              ⁢
              
                
                  e
                  
                    
                      j
                      ⁢
                      
                        
                      
                      ⁢
                      2
                      ⁢
                      
                        
                      
                      ⁢
                      π
                    
                    
                      N
                      s
                    
                  
                
                ⁡
                
                  (
                  
                    
                      
                        
                          
                            R
                            0
                          
                          +
                          
                            R
                            
                              
                                H
                                1
                              
                              ⁢
                              
                                e
                                
                                  
                                    j
                                    ⁢
                                    
                                      
                                    
                                    ⁢
                                    2
                                    ⁢
                                    
                                      
                                    
                                    ⁢
                                    π
                                  
                                  
                                    N
                                    s
                                  
                                
                              
                            
                          
                          +
                          
                            
                              R
                              2
                              H
                            
                            ⁢
                            
                              e
                              
                                
                                  j
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  4
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  π
                                
                                
                                  N
                                  s
                                
                              
                            
                          
                          +
                        
                      
                    
                    
                      
                        
                          
                            
                              R
                              2
                            
                            ⁢
                            
                              e
                              
                                
                                  
                                    -
                                    j
                                  
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  4
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  π
                                
                                
                                  N
                                  s
                                
                              
                            
                          
                          +
                          
                            
                              R
                              1
                            
                            ⁢
                            
                              e
                              
                                
                                  
                                    -
                                    j
                                  
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  2
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  π
                                
                                
                                  N
                                  s
                                
                              
                            
                          
                        
                      
                    
                  
                  )
                
              
            
          
        
      
    
    
      
        Equation
        ⁢
        
          
        
        ⁢
        20
      
    
  




As a result, Λ(2) is per Equation 21.




  
    
      
        
          Λ
          
            (
            2
            )
          
        
        =
        
          (
          
            
              
                
                  
                    R
                    0
                  
                  +
                  
                    
                      R
                      1
                      H
                    
                    ⁢
                    
                      e
                      
                        
                          j
                          ⁢
                          
                            
                          
                          ⁢
                          2
                          ⁢
                          
                            
                          
                          ⁢
                          π
                        
                        
                          N
                          s
                        
                      
                    
                  
                  +
                  
                    
                      R
                      2
                      H
                    
                    ⁢
                    
                      e
                      
                        
                          j
                          ⁢
                          
                            
                          
                          ⁢
                          4
                          ⁢
                          
                            
                          
                          ⁢
                          π
                        
                        
                          N
                          s
                        
                      
                    
                  
                  +
                
              
            
            
              
                
                  
                    
                      R
                      2
                    
                    ⁢
                    
                      e
                      
                        
                          
                            -
                            j
                          
                          ⁢
                          
                            
                          
                          ⁢
                          4
                          ⁢
                          
                            
                          
                          ⁢
                          π
                        
                        
                          N
                          s
                        
                      
                    
                  
                  +
                  
                    
                      R
                      1
                    
                    ⁢
                    
                      e
                      
                        
                          
                            -
                            j
                          
                          ⁢
                          
                            
                          
                          ⁢
                          2
                          ⁢
                          
                            
                          
                          ⁢
                          π
                        
                        
                          N
                          s
                        
                      
                    
                  
                
              
            
          
          )
        
      
    
    
      
        Equation
        ⁢
        
          
        
        ⁢
        21
      
    
  




Similarly, Λ(N,−1) is per Equation 22.




  
    
      
        
          Λ
          
            (
            
              
                N
                s
              
              -
              1
            
            )
          
        
        =
        
          (
          
            
              
                
                  
                    R
                    0
                  
                  +
                  
                    
                      R
                      1
                      H
                    
                    ⁢
                    
                      e
                      
                        
                          j
                          ⁢
                          
                            
                          
                          ⁢
                          2
                          ⁢
                          
                            
                          
                          ⁢
                          
                            (
                            
                              
                                N
                                s
                              
                              -
                              2
                            
                            )
                          
                          ⁢
                          π
                        
                        
                          N
                          s
                        
                      
                    
                  
                  +
                  
                    
                      R
                      2
                      H
                    
                    ⁢
                    
                      e
                      
                        
                          j
                          ⁢
                          
                            
                          
                          ⁢
                          4
                          ⁢
                          
                            
                          
                          ⁢
                          
                            (
                            
                              
                                N
                                s
                              
                              -
                              2
                            
                            )
                          
                          ⁢
                          π
                        
                        
                          N
                          s
                        
                      
                    
                  
                  +
                
              
            
            
              
                
                  
                    
                      R
                      2
                    
                    ⁢
                    
                      e
                      
                        
                          
                            -
                            j
                          
                          ⁢
                          
                            
                          
                          ⁢
                          4
                          ⁢
                          
                            
                          
                          ⁢
                          
                            (
                            
                              
                                N
                                s
                              
                              -
                              2
                            
                            )
                          
                          ⁢
                          π
                        
                        
                          N
                          s
                        
                      
                    
                  
                  +
                  
                    
                      R
                      1
                    
                    ⁢
                    
                      e
                      
                        
                          
                            -
                            j
                          
                          ⁢
                          
                            
                          
                          ⁢
                          2
                          ⁢
                          
                            
                          
                          ⁢
                          
                            (
                            
                              
                                N
                                s
                              
                              -
                              2
                            
                            )
                          
                          ⁢
                          π
                        
                        
                          N
                          s
                        
                      
                    
                  
                
              
            
          
          )
        
      
    
    
      
        Equation
        ⁢
        
          
        
        ⁢
        22
      
    
  




Λ(Ns) is per Equation 23.




  
    
      
        
          Λ
          
            (
            
              N
              s
            
            )
          
        
        =
        
          (
          
            
              
                
                  
                    R
                    0
                  
                  +
                  
                    
                      R
                      1
                      H
                    
                    ⁢
                    
                      e
                      
                        
                          j
                          ⁢
                          
                            
                          
                          ⁢
                          2
                          ⁢
                          
                            
                          
                          ⁢
                          
                            (
                            
                              
                                N
                                s
                              
                              -
                              1
                            
                            )
                          
                          ⁢
                          π
                        
                        
                          N
                          s
                        
                      
                    
                  
                  +
                  
                    
                      R
                      2
                      H
                    
                    ⁢
                    
                      e
                      
                        
                          j
                          ⁢
                          
                            
                          
                          ⁢
                          4
                          ⁢
                          
                            
                          
                          ⁢
                          
                            (
                            
                              
                                N
                                s
                              
                              -
                              1
                            
                            )
                          
                          ⁢
                          π
                        
                        
                          N
                          s
                        
                      
                    
                  
                  +
                
              
            
            
              
                
                  
                    
                      R
                      2
                    
                    ⁢
                    
                      e
                      
                        
                          
                            -
                            j
                          
                          ⁢
                          
                            
                          
                          ⁢
                          4
                          ⁢
                          
                            
                          
                          ⁢
                          
                            (
                            
                              
                                N
                                s
                              
                              -
                              1
                            
                            )
                          
                          ⁢
                          π
                        
                        
                          N
                          s
                        
                      
                    
                  
                  +
                  
                    
                      R
                      1
                    
                    ⁢
                    
                      e
                      
                        
                          
                            -
                            j
                          
                          ⁢
                          
                            
                          
                          ⁢
                          2
                          ⁢
                          
                            
                          
                          ⁢
                          
                            (
                            
                              
                                N
                                s
                              
                              -
                              1
                            
                            )
                          
                          ⁢
                          π
                        
                        
                          N
                          s
                        
                      
                    
                  
                
              
            
          
          )
        
      
    
    
      
        Equation
        ⁢
        
          
        
        ⁢
        23
      
    
  




Although Equations 17-23 illustrate using the first row of RCD and DΛ, any row can be used to determine the Λ(i)s.

To illustrate using a center row, (Ns/2)th row (row 5 of Equation 7), Λ(1) is per Equation 19.

Λ(1)=(R0+R1H+R2H+R1+R2)  Equation 19

Equations 19-23 compute the FFT of K by K blocks. Since these blocks are multiplied by scalar exponentials, this process is referred to as a “block FFT.” Typical approaches for calculating FFTs, such as the Matlab function “fft,” compute the FFTs of a one-sided sequence. Since each Λ(i) is a two sided sequence, the computation of Λ(i) can be implemented by an fft {0, 0, . . . , R2, R1, R0, R1H, R2H, . . . , 0, 0} and multiplying it by an appropriate exponential function as per Equation 27 for a center row.





  
    
      
        
          e
          
            j
            ⁢
            
              
            
            ⁢
            2
            ⁢
            
              
            
            ⁢
            
              π
              ⁡
              
                (
                
                  k
                  -
                  1
                
                )
              
            
            ⁢
            v
          
        
        ,
        
          
            where
            ⁢
            
              
            
            ⁢
            v
          
          =
          
            
              [
              
                
                  ceil
                  ⁡
                  
                    (
                    
                      
                        N
                        s
                      
                      2
                    
                    )
                  
                
                -
                1
              
              ]
            
            
              N
              s
            
          
        
      
    
    
      
        Equation
        ⁢
        
          
        
        ⁢
        27
      
    
  




As shown in Equations 17-27, calculating all the Λ(i) can be performed using a single column of R. Accordingly, RC is not required to be determined. Any column of R can be used to derive the Λ(i)s directly. Preferably, a row at least W rows from either edge of R is used, since these rows have a full set of Ris.
Using the Λ(i)s and the D matrix, the block-circulant matrix Rc can be re-written as Equations 28 and 29.

RcD=DΛ  Equation 28

Rc=(1/Ns)[DΛDH]  Equation 29

D and Λ are each of size (KNs) by (KNs).

Since DHD=NsIKNs, D−1=(1/Ns)DH, Equation 30 results.




  
    
      
        
          R
          c
          
            -
            1
          
        
        =
        
          
            
              N
              s
            
            ⁡
            
              [
              
                
                  
                    (
                    
                      D
                      H
                    
                    )
                  
                  
                    -
                    1
                  
                
                ⁢
                
                  
                    
                      Λ
                      
                        -
                        1
                      
                    
                    ⁡
                    
                      (
                      D
                      )
                    
                  
                  
                    -
                    1
                  
                
              
              ]
            
          
          =
          
            
              N
              s
            
            ⁡
            
              [
              
                
                  D
                  
                    N
                    s
                  
                
                ⁢
                
                  Λ
                  
                    -
                    1
                  
                
                ⁢
                
                  
                    D
                    H
                  
                  
                    N
                    s
                  
                
              
              ]
            
          
        
      
    
    
      
        Equation
        ⁢
        
          
        
        ⁢
        30
      
    
  




The MMSE solution is per Equation 31.

d=Rc−1(AHr)  Equation 31

The detected data vector d is of size (NsK) by 1.

The MMSE solution is per Equation 32.

DHd=Λ−1[DH(AHr)]  Equation 32

The matrix Λ is of size (KNs) by (KNs) with K by K blocks, and its inverse is per Equation 33.





  
    
      
        
          
            
              
                Λ
                
                  -
                  1
                
              
              =
              
                
                  [
                  
                    
                      
                        
                          Λ
                          
                            (
                            1
                            )
                          
                        
                      
                      
                        
                          
                        
                      
                      
                        
                          
                        
                      
                      
                        
                          
                        
                      
                      
                        
                          
                        
                      
                    
                    
                      
                        
                          
                        
                      
                      
                        
                          Λ
                          
                            (
                            2
                            )
                          
                        
                      
                      
                        
                          
                        
                      
                      
                        
                          
                        
                      
                      
                        
                          
                        
                      
                    
                    
                      
                        
                          
                        
                      
                      
                        
                          
                        
                      
                      
                        
                          Λ
                          
                            (
                            3
                            )
                          
                        
                      
                      
                        
                          
                        
                      
                      
                        
                          
                        
                      
                    
                    
                      
                        
                          
                        
                      
                      
                        
                          
                        
                      
                      
                        
                          
                        
                      
                      
                        ⋰
                      
                      
                        
                          
                        
                      
                    
                    
                      
                        
                          
                        
                      
                      
                        
                          
                        
                      
                      
                        
                          
                        
                      
                      
                        
                          
                        
                      
                      
                        
                          Λ
                          
                            (
                            
                              N
                              s
                            
                            )
                          
                        
                      
                    
                  
                  ]
                
                
                  -
                  1
                
              
            
          
        
        
          
            
              =
              
                [
                
                  
                    
                      
                        
                          [
                          
                            Λ
                            
                              (
                              1
                              )
                            
                          
                          ]
                        
                        
                          -
                          1
                        
                      
                    
                    
                      
                        
                      
                    
                    
                      
                        
                      
                    
                    
                      
                        
                      
                    
                    
                      
                        
                      
                    
                  
                  
                    
                      
                        
                      
                    
                    
                      
                        
                          [
                          
                            Λ
                            
                              (
                              2
                              )
                            
                          
                          ]
                        
                        
                          -
                          1
                        
                      
                    
                    
                      
                        
                      
                    
                    
                      
                        
                      
                    
                    
                      
                        
                      
                    
                  
                  
                    
                      
                        
                      
                    
                    
                      
                        
                      
                    
                    
                      
                        
                          [
                          
                            Λ
                            
                              (
                              3
                              )
                            
                          
                          ]
                        
                        
                          -
                          1
                        
                      
                    
                    
                      
                        
                      
                    
                    
                      
                        
                      
                    
                  
                  
                    
                      
                        
                      
                    
                    
                      
                        
                      
                    
                    
                      
                        
                      
                    
                    
                      ⋰
                    
                    
                      
                        
                      
                    
                  
                  
                    
                      
                        
                      
                    
                    
                      
                        
                      
                    
                    
                      
                        
                      
                    
                    
                      
                        
                      
                    
                    
                      
                        
                          [
                          
                            Λ
                            
                              (
                              
                                N
                                s
                              
                              )
                            
                          
                          ]
                        
                        
                          -
                          1
                        
                      
                    
                  
                
                ]
              
            
          
        
      
    
    
      
        Equation
        ⁢
        
          
        
        ⁢
        33
      
    
  




The inversion requires an inversion of the K by K matrices Λ(k).

As a result, the data vector d is determined per Equation 34.

[F(d)]k=[Λ(k)]−1[F(AHr)]k  Equation 34

Equation 34 is applicable to both receivers which sample the received signal at the chip rate and at a multiple of the chip rate, such as twice the chip rate. For multiple chip rate receivers, the R matrix corresponding to the multiple chip rate is of the same form as Equation 9, being approximately block circulant.

To reduce the complexity in determining F(AHr), an FFT approach taking advantage of the structure of A may be used. A has an approximately block-circulant structure. However, it is a non-square matrix, being of size (NsSF) by (NsK). An illustration of a matrix A is per Equation 35.




  
    
      
        A
        =
        
          [
          
            
              
                
                  [
                  
                    
                      
                        
                          
                            b
                            1
                            
                              (
                              1
                              )
                            
                          
                          ⁡
                          
                            (
                            0
                            )
                          
                        
                      
                      
                        
                          
                            b
                            1
                            K
                          
                          ⁡
                          
                            (
                            0
                            )
                          
                        
                      
                    
                    
                      
                        
                          
                            b
                            SF
                            
                              (
                              1
                              )
                            
                          
                          ⁡
                          
                            (
                            0
                            )
                          
                        
                      
                      
                        
                          
                            b
                            SF
                            K
                          
                          ⁡
                          
                            (
                            0
                            )
                          
                        
                      
                    
                  
                  ]
                
              
              
                O
              
              
                O
              
              
                ...
              
            
            
              
                
                  [
                  
                    
                      
                        
                          
                            b
                            1
                            
                              (
                              1
                              )
                            
                          
                          ⁡
                          
                            (
                            1
                            )
                          
                        
                      
                      
                        
                          
                            b
                            1
                            K
                          
                          ⁡
                          
                            (
                            1
                            )
                          
                        
                      
                    
                    
                      
                        
                          
                            b
                            SF
                            
                              (
                              1
                              )
                            
                          
                          ⁡
                          
                            (
                            1
                            )
                          
                        
                      
                      
                        
                          
                            b
                            SF
                            K
                          
                          ⁡
                          
                            (
                            1
                            )
                          
                        
                      
                    
                  
                  ]
                
              
              
                
                  [
                  
                    
                      
                        
                          
                            b
                            1
                            
                              (
                              1
                              )
                            
                          
                          ⁡
                          
                            (
                            0
                            )
                          
                        
                      
                      
                        
                          
                            b
                            1
                            K
                          
                          ⁡
                          
                            (
                            0
                            )
                          
                        
                      
                    
                    
                      
                        
                          
                            b
                            SF
                            
                              (
                              1
                              )
                            
                          
                          ⁡
                          
                            (
                            0
                            )
                          
                        
                      
                      
                        
                          
                            b
                            SF
                            K
                          
                          ⁡
                          
                            (
                            0
                            )
                          
                        
                      
                    
                  
                  ]
                
              
              
                O
              
              
                ...
              
            
            
              
                
                  [
                  
                    
                      
                        
                          
                            b
                            1
                            
                              (
                              1
                              )
                            
                          
                          ⁡
                          
                            (
                            2
                            )
                          
                        
                      
                      
                        
                          
                            b
                            1
                            K
                          
                          ⁡
                          
                            (
                            2
                            )
                          
                        
                      
                    
                    
                      
                        
                          
                            b
                            SF
                            
                              (
                              1
                              )
                            
                          
                          ⁡
                          
                            (
                            2
                            )
                          
                        
                      
                      
                        
                          
                            b
                            SF
                            K
                          
                          ⁡
                          
                            (
                            2
                            )
                          
                        
                      
                    
                  
                  ]
                
              
              
                
                  [
                  
                    
                      
                        
                          
                            b
                            1
                            
                              (
                              1
                              )
                            
                          
                          ⁡
                          
                            (
                            1
                            )
                          
                        
                      
                      
                        
                          
                            b
                            1
                            K
                          
                          ⁡
                          
                            (
                            1
                            )
                          
                        
                      
                    
                    
                      
                        
                          
                            b
                            SF
                            
                              (
                              1
                              )
                            
                          
                          ⁡
                          
                            (
                            1
                            )
                          
                        
                      
                      
                        
                          
                            b
                            SF
                            K
                          
                          ⁡
                          
                            (
                            1
                            )
                          
                        
                      
                    
                  
                  ]
                
              
              
                
                  [
                  
                    
                      
                        
                          
                            b
                            1
                            
                              (
                              1
                              )
                            
                          
                          ⁡
                          
                            (
                            0
                            )
                          
                        
                      
                      
                        
                          
                            b
                            1
                            K
                          
                          ⁡
                          
                            (
                            0
                            )
                          
                        
                      
                    
                    
                      
                        
                          
                            b
                            SF
                            
                              (
                              1
                              )
                            
                          
                          ⁡
                          
                            (
                            0
                            )
                          
                        
                      
                      
                        
                          
                            b
                            SF
                            K
                          
                          ⁡
                          
                            (
                            0
                            )
                          
                        
                      
                    
                  
                  ]
                
              
              
                ...
              
            
            
              
                ⋮
              
              
                ⋮
              
              
                ⋮
              
              
                ⋮
              
            
          
          ]
        
      
    
    
      
        Equation
        ⁢
        
          
        
        ⁢
        35
      
    
  




Each bj(k)(i) is the convolution of the channel response h(k) and the spreading code c(k), for the kth user at the jth chip interval of the ith symbol interval.

Using blocks B (•), where each block is indicated by bracketing in Equation 35, Equation 35 becomes Equation 36.




  
    
      
        A
        =
        
          [
          
            
              
                
                  B
                  ⁡
                  
                    (
                    0
                    )
                  
                
              
              
                0
              
              
                0
              
              
                0
              
              
                ...
              
              
                0
              
            
            
              
                
                  B
                  ⁡
                  
                    (
                    1
                    )
                  
                
              
              
                
                  B
                  ⁡
                  
                    (
                    0
                    )
                  
                
              
              
                0
              
              
                0
              
              
                ...
              
              
                0
              
            
            
              
                
                  B
                  ⁡
                  
                    (
                    2
                    )
                  
                
              
              
                
                  B
                  ⁡
                  
                    (
                    1
                    )
                  
                
              
              
                
                  B
                  ⁡
                  
                    (
                    0
                    )
                  
                
              
              
                0
              
              
                ...
              
              
                0
              
            
            
              
                ⋮
              
              
                ⋮
              
              
                ⋮
              
              
                ⋮
              
              
                ⋮
              
              
                ⋮
              
            
            
              
                0
              
              
                0
              
              
                ...
              
              
                
                  B
                  ⁡
                  
                    (
                    2
                    )
                  
                
              
              
                
                  B
                  ⁡
                  
                    (
                    1
                    )
                  
                
              
              
                
                  B
                  ⁡
                  
                    (
                    0
                    )
                  
                
              
            
            
              
                ⋮
              
              
                ⋮
              
              
                
                  
                
              
              
                ⋮
              
              
                ⋮
              
              
                ⋮
              
            
          
          ]
        
      
    
    
      
        Equation
        ⁢
        
          
        
        ⁢
        36
      
    
  




As shown, a portion of A is block-circulant. A circulant extension of A is denoted as Ac.
A can be broken into three matrices per Equation 37.

A=D1Λ1D2H  Equation 37

D1 is a (NsSF) by (NsSF) matrix. D2 is a (NsK) by (NsK) matrix and Λ1 is a block-diagonal matrix of size (NsSF) by (NsK).

The block diagonal matrix Λ1 has the same form as Λ of Equation 14. However, each of its entries Λ1(i) is a SF by K block per Equation 38.




  
    
      
        
          Λ
          l
          
            (
            i
            )
          
        
        =
        
          
            [
            
              
                
                  
                    λ
                    
                      1
                      ,
                      1
                    
                    
                      (
                      i
                      )
                    
                  
                
                
                  ...
                
                
                  
                    λ
                    
                      1
                      ,
                      K
                    
                    
                      (
                      i
                      )
                    
                  
                
              
              
                
                  ⋮
                
                
                  
                    
                  
                
                
                  ⋮
                
              
              
                
                  
                    λ
                    
                      SF
                      ,
                      1
                    
                    
                      (
                      i
                      )
                    
                  
                
                
                  ...
                
                
                  
                    λ
                    
                      SF
                      ,
                      K
                    
                    
                      (
                      i
                      )
                    
                  
                
              
            
            ]
          
          .
        
      
    
    
      
        Equation
        ⁢
        
          
        
        ⁢
        38
      
    
  




D2 is the same form as that of D in Equation 11. D1 is of the form of Equation 39.




  
    
      
        
          D
          1
        
        =
        
          [
          
            
              
                I
              
              
                
                  
                    e
                    
                      
                        j
                        ⁢
                        
                          
                        
                        ⁢
                        2
                        ⁢
                        
                          
                        
                        ⁢
                        π
                      
                      
                        N
                        s
                      
                    
                  
                  ⁢
                  
                    I
                    SF
                  
                
              
              
                
                  
                    e
                    
                      
                        j
                        ⁢
                        
                          
                        
                        ⁢
                        2
                        ⁢
                        
                          
                        
                        ⁢
                        π
                      
                      
                        N
                        s
                      
                    
                  
                  ⁢
                  
                    I
                    SF
                  
                
              
              
                ...
              
              
                ...
              
              
                
                  
                    e
                    
                      
                        j
                        ⁢
                        
                          
                        
                        ⁢
                        18
                        ⁢
                        
                          
                        
                        ⁢
                        π
                      
                      
                        N
                        s
                      
                    
                  
                  ⁢
                  
                    I
                    SF
                  
                
              
            
            
              
                I
              
              
                
                  
                    e
                    
                      
                        j
                        ⁢
                        
                          
                        
                        ⁢
                        4
                        ⁢
                        
                          
                        
                        ⁢
                        π
                      
                      
                        N
                        s
                      
                    
                  
                  ⁢
                  
                    I
                    SF
                  
                
              
              
                
                  
                    e
                    
                      
                        j
                        ⁢
                        
                          
                        
                        ⁢
                        8
                        ⁢
                        
                          
                        
                        ⁢
                        π
                      
                      
                        N
                        s
                      
                    
                  
                  ⁢
                  
                    I
                    SF
                  
                
              
              
                ...
              
              
                ...
              
              
                
                  
                    e
                    
                      
                        j
                        ⁢
                        
                          
                        
                        ⁢
                        36
                        ⁢
                        
                          
                        
                        ⁢
                        π
                      
                      
                        N
                        s
                      
                    
                  
                  ⁢
                  
                    I
                    SF
                  
                
              
            
            
              
                ⋮
              
              
                ⋮
              
              
                ⋮
              
              
                
                  
                
              
              
                
                  
                
              
              
                ⋮
              
            
            
              
                I
              
              
                
                  
                    e
                    
                      
                        j
                        ⁢
                        
                          
                        
                        ⁢
                        18
                        ⁢
                        
                          
                        
                        ⁢
                        π
                      
                      
                        N
                        s
                      
                    
                  
                  ⁢
                  
                    I
                    SF
                  
                
              
              
                
                  
                    e
                    
                      
                        j
                        ⁢
                        
                          
                        
                        ⁢
                        36
                        ⁢
                        
                          
                        
                        ⁢
                        π
                      
                      
                        N
                        s
                      
                    
                  
                  ⁢
                  
                    I
                    SF
                  
                
              
              
                ...
              
              
                ...
              
              
                
                  
                    e
                    
                      
                        j
                        ⁢
                        
                          
                        
                        ⁢
                        162
                        ⁢
                        
                          
                        
                        ⁢
                        π
                      
                      
                        N
                        s
                      
                    
                  
                  ⁢
                  
                    I
                    SF
                  
                
              
            
            
              
                I
              
              
                
                  
                    e
                    
                      
                        j
                        ⁢
                        
                          
                        
                        ⁢
                        20
                        ⁢
                        
                          
                        
                        ⁢
                        π
                      
                      
                        N
                        s
                      
                    
                  
                  ⁢
                  
                    I
                    SF
                  
                
              
              
                
                  
                    e
                    
                      
                        j
                        ⁢
                        
                          
                        
                        ⁢
                        40
                        ⁢
                        
                          
                        
                        ⁢
                        π
                      
                      
                        N
                        s
                      
                    
                  
                  ⁢
                  
                    I
                    SF
                  
                
              
              
                ...
              
              
                ...
              
              
                
                  
                    e
                    
                      
                        j
                        ⁢
                        
                          
                        
                        ⁢
                        180
                        ⁢
                        
                          
                        
                        ⁢
                        π
                      
                      
                        N
                        s
                      
                    
                  
                  ⁢
                  
                    I
                    SF
                  
                
              
            
          
          ]
        
      
    
    
      
        Equation
        ⁢
        
          
        
        ⁢
        39
      
    
  




ISF is a SF by SF identity matrix.

In multiplying AC and D2, products of the form, B(i) and




  
    
      e
      
        
          j
          ⁢
          
            
          
          ⁢
          2
          ⁢
          
            
          
          ⁢
          π
        
        
          N
          s
        
      
    
    ⁢
    
      I
      K
    
  
  ,




are formed per Equation 40.





  
    
      
        
          
            A
            c
          
          ⁢
          
            D
            2
          
        
        =
        
          [
          
            
              
                
                  [
                  
                    
                      
                        
                          
                            B
                            ⁢
                            
                              (
                              0
                              )
                            
                          
                          +
                          
                            B
                            ⁢
                            
                              (
                              1
                              )
                            
                          
                          +
                        
                      
                    
                    
                      
                        
                          B
                          ⁡
                          
                            (
                            2
                            )
                          
                        
                      
                    
                  
                  ]
                
              
              
                
                  [
                  
                    
                      
                        
                          
                            B
                            ⁢
                            
                              (
                              0
                              )
                            
                            ⁢
                            
                              e
                              
                                
                                  j
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  2
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  π
                                
                                
                                  N
                                  s
                                
                              
                            
                          
                          +
                          
                            
                              B
                              ⁡
                              
                                (
                                2
                                )
                              
                            
                            ⁢
                            
                              e
                              
                                
                                  j
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  18
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  π
                                
                                
                                  N
                                  s
                                
                              
                            
                          
                          +
                        
                      
                    
                    
                      
                        
                          
                            B
                            ⁡
                            
                              (
                              1
                              )
                            
                          
                          ⁢
                          
                            e
                            
                              
                                j
                                ⁢
                                
                                  
                                
                                ⁢
                                20
                                ⁢
                                
                                  
                                
                                ⁢
                                π
                              
                              
                                N
                                s
                              
                            
                          
                        
                      
                    
                  
                  ]
                
              
              
                ...
              
              
                
                  [
                  
                    
                      
                        
                          
                            B
                            ⁢
                            
                              (
                              0
                              )
                            
                            ⁢
                            
                              e
                              
                                
                                  j
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  18
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  π
                                
                                
                                  N
                                  s
                                
                              
                            
                          
                          +
                          
                            
                              B
                              ⁡
                              
                                (
                                2
                                )
                              
                            
                            ⁢
                            
                              e
                              
                                
                                  j
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  162
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  π
                                
                                
                                  N
                                  s
                                
                              
                            
                          
                          +
                        
                      
                    
                    
                      
                        
                          
                            B
                            ⁡
                            
                              (
                              1
                              )
                            
                          
                          ⁢
                          
                            e
                            
                              
                                j
                                ⁢
                                
                                  
                                
                                ⁢
                                180
                                ⁢
                                
                                  
                                
                                ⁢
                                π
                              
                              
                                N
                                s
                              
                            
                          
                        
                      
                    
                  
                  ]
                
              
            
            
              
                
                  [
                  
                    
                      
                        
                          
                            B
                            ⁢
                            
                              (
                              0
                              )
                            
                          
                          +
                          
                            B
                            ⁢
                            
                              (
                              1
                              )
                            
                          
                          +
                        
                      
                    
                    
                      
                        
                          B
                          ⁡
                          
                            (
                            2
                            )
                          
                        
                      
                    
                  
                  ]
                
              
              
                
                  [
                  
                    
                      
                        
                          
                            
                              (
                              1
                              )
                            
                            ⁢
                            
                              e
                              
                                
                                  j
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  2
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  π
                                
                                
                                  N
                                  s
                                
                              
                            
                          
                          +
                          
                            
                              B
                              ⁡
                              
                                (
                                0
                                )
                              
                            
                            ⁢
                            
                              e
                              
                                
                                  j
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  4
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  π
                                
                                
                                  N
                                  s
                                
                              
                            
                          
                          +
                        
                      
                    
                    
                      
                        
                          B
                          ⁢
                          
                            (
                            2
                            )
                          
                          ⁢
                          
                            e
                            
                              
                                j
                                ⁢
                                
                                  
                                
                                ⁢
                                20
                                ⁢
                                
                                  
                                
                                ⁢
                                π
                              
                              
                                N
                                s
                              
                            
                          
                        
                      
                    
                  
                  ]
                
              
              
                ...
              
              
                
                  [
                  
                    
                      
                        
                          
                            
                              B
                              ⁡
                              
                                (
                                1
                                )
                              
                            
                            ⁢
                            
                              e
                              
                                
                                  j
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  18
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  π
                                
                                
                                  N
                                  s
                                
                              
                            
                          
                          +
                          
                            
                              B
                              ⁡
                              
                                (
                                0
                                )
                              
                            
                            ⁢
                            
                              e
                              
                                
                                  j
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  36
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  π
                                
                                
                                  N
                                  s
                                
                              
                            
                          
                          +
                        
                      
                    
                    
                      
                        
                          
                            B
                            ⁡
                            
                              (
                              2
                              )
                            
                          
                          ⁢
                          
                            e
                            
                              
                                j
                                ⁢
                                
                                  
                                
                                ⁢
                                180
                                ⁢
                                
                                  
                                
                                ⁢
                                π
                              
                              
                                N
                                s
                              
                            
                          
                        
                      
                    
                  
                  ]
                
              
            
            
              
                ⋮
              
              
                ⋮
              
              
                
                  
                
              
              
                ⋮
              
            
            
              
                
                  [
                  
                    
                      
                        
                          
                            B
                            ⁢
                            
                              (
                              0
                              )
                            
                          
                          +
                          
                            B
                            ⁢
                            
                              (
                              1
                              )
                            
                          
                          +
                        
                      
                    
                    
                      
                        
                          B
                          ⁡
                          
                            (
                            2
                            )
                          
                        
                      
                    
                  
                  ]
                
              
              
                
                  [
                  
                    
                      
                        
                          
                            B
                            ⁢
                            
                              (
                              2
                              )
                            
                            ⁢
                            
                              e
                              
                                
                                  j
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  16
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  π
                                
                                
                                  N
                                  s
                                
                              
                            
                          
                          +
                          
                            
                              B
                              ⁡
                              
                                (
                                1
                                )
                              
                            
                            ⁢
                            
                              e
                              
                                
                                  j
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  18
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  π
                                
                                
                                  N
                                  s
                                
                              
                            
                          
                          +
                        
                      
                    
                    
                      
                        
                          
                            B
                            ⁡
                            
                              (
                              0
                              )
                            
                          
                          ⁢
                          
                            e
                            
                              
                                j
                                ⁢
                                
                                  
                                
                                ⁢
                                20
                                ⁢
                                
                                  
                                
                                ⁢
                                π
                              
                              
                                N
                                s
                              
                            
                          
                        
                      
                    
                  
                  ]
                
              
              
                ...
              
              
                
                  [
                  
                    
                      
                        
                          
                            
                              B
                              ⁡
                              
                                (
                                2
                                )
                              
                            
                            ⁢
                            
                              e
                              
                                
                                  j
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  144
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  π
                                
                                
                                  N
                                  s
                                
                              
                            
                          
                          +
                          
                            
                              B
                              ⁡
                              
                                (
                                1
                                )
                              
                            
                            ⁢
                            
                              e
                              
                                
                                  j
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  162
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  π
                                
                                
                                  N
                                  s
                                
                              
                            
                          
                          +
                        
                      
                    
                    
                      
                        
                          
                            B
                            ⁡
                            
                              (
                              0
                              )
                            
                          
                          ⁢
                          
                            e
                            
                              
                                j
                                ⁢
                                
                                  
                                
                                ⁢
                                180
                                ⁢
                                
                                  
                                
                                ⁢
                                π
                              
                              
                                N
                                s
                              
                            
                          
                        
                      
                    
                  
                  ]
                
              
            
            
              
                ⋮
              
              
                ⋮
              
              
                
                  
                
              
              
                ⋮
              
            
          
          ]
        
      
    
    
      
        Equation
        ⁢
        
          
        
        ⁢
        40
      
    
  




AcD2 is of size (NsSF) by (NsK) and each block is a size SF by K.

In multiplying D1 and Λ1, products of the form,




  
    e
    
      
        j
        ⁢
        
          
        
        ⁢
        2
        ⁢
        
          
        
        ⁢
        π
      
      
        N
        s
      
    
  
  ⁢
  
    I
    SF
  




and Λ1(i), are formed. D1Λ1 is of size (NsSF) by (NsK) and each block is of size SF by K. Comparing any row of AcD2 with the same row of D1Λ1, Equation 41 results.





  
    
      
        
          
            
              Λ
              1
              
                (
                1
                )
              
            
            =
            
              [
              
                
                  B
                  ⁡
                  
                    (
                    0
                    )
                  
                
                +
                
                  B
                  ⁡
                  
                    (
                    1
                    )
                  
                
                +
                
                  B
                  ⁡
                  
                    (
                    2
                    )
                  
                
              
              ]
            
          
          ,
          
            

          
          ⁢
          
            
              Λ
              1
              
                (
                2
                )
              
            
            =
            
              [
              
                
                  B
                  ⁡
                  
                    (
                    0
                    )
                  
                
                +
                
                  
                    B
                    ⁡
                    
                      (
                      1
                      )
                    
                  
                  ⁢
                  
                    e
                    
                      
                        
                          -
                          j
                        
                        ⁢
                        
                          
                        
                        ⁢
                        2
                        ⁢
                        
                          
                        
                        ⁢
                        π
                      
                      
                        N
                        s
                      
                    
                  
                
                +
                
                  
                    B
                    ⁡
                    
                      (
                      2
                      )
                    
                  
                  ⁢
                  
                    e
                    
                      
                        
                          -
                          j
                        
                        ⁢
                        
                          
                        
                        ⁢
                        4
                        ⁢
                        
                          
                        
                        ⁢
                        π
                      
                      
                        N
                        s
                      
                    
                  
                
              
              ]
            
          
          ,
          
            

          
          ⁢
          ⋮
        
        ⁢
        
          

        
        ⁢
        
          
            
              Λ
              1
              
                (
                
                  
                    N
                    s
                  
                  -
                  1
                
                )
              
            
            =
            
            ⁢
            
              [
              
                
                  
                    
                      
                        B
                        ⁢
                        
                          (
                          0
                          )
                        
                      
                      +
                      
                        
                          B
                          ⁡
                          
                            (
                            1
                            )
                          
                        
                        ⁢
                        
                          e
                          
                            
                              
                                -
                                j
                              
                              ⁢
                              
                                
                              
                              ⁢
                              2
                              ⁢
                              
                                (
                                
                                  
                                    N
                                    s
                                  
                                  -
                                  2
                                
                                )
                              
                              ⁢
                              π
                            
                            
                              N
                              s
                            
                          
                        
                      
                      +
                    
                  
                
                
                  
                    
                      
                        B
                        ⁡
                        
                          (
                          2
                          )
                        
                      
                      ⁢
                      
                        e
                        
                          
                            
                              -
                              j
                            
                            ⁢
                            
                              
                            
                            ⁢
                            2
                            ⁢
                            
                              (
                              
                                
                                  N
                                  s
                                
                                -
                                2
                              
                              )
                            
                            ⁢
                            π
                          
                          
                            N
                            s
                          
                        
                      
                    
                  
                
              
              ]
            
          
          ,
          
            

          
          ⁢
          
            
              Λ
              1
              
                (
                
                  N
                  s
                
                )
              
            
            =
            
            ⁢
            
              
                [
                
                  
                    
                      
                        
                          B
                          ⁢
                          
                            (
                            0
                            )
                          
                        
                        +
                        
                          
                            B
                            ⁡
                            
                              (
                              1
                              )
                            
                          
                          ⁢
                          
                            e
                            
                              
                                
                                  -
                                  j
                                
                                ⁢
                                
                                  
                                
                                ⁢
                                2
                                ⁢
                                
                                  (
                                  
                                    
                                      N
                                      s
                                    
                                    -
                                    1
                                  
                                  )
                                
                                ⁢
                                π
                              
                              
                                N
                                s
                              
                            
                          
                        
                        +
                      
                    
                  
                  
                    
                      
                        
                          B
                          ⁡
                          
                            (
                            2
                            )
                          
                        
                        ⁢
                        
                          e
                          
                            
                              
                                -
                                j
                              
                              ⁢
                              
                                
                              
                              ⁢
                              4
                              ⁢
                              
                                (
                                
                                  
                                    N
                                    s
                                  
                                  -
                                  1
                                
                                )
                              
                              ⁢
                              π
                            
                            
                              N
                              s
                            
                          
                        
                      
                    
                  
                
                ]
              
              .
            
          
        
      
    
    
      
        Equation
        ⁢
        
          
        
        ⁢
        41
      
    
  




As a result, each Λ1(k) can be determined using the FFT of a one-sided sequence of (SF by K) blocks. Using Equation 38 and D2HD2=NsIKNs, Equations 42, 43 and 44 result.

A=D1Λ1D2H,  Equation 42

AHr=D2Λ1H(D1Hr)  Equation 43

D2H(AHr)=Ns·[Λ1H(D1Hr)]  Equation 44

Accordingly, [F(AHr)]k is determined using FFTs per Equation 45.

[F(AHr)]k=Ns·[Λ1(k)]H[F(r)]k  Equation 45

Similarly, since the matrix A is approximately block-circulant, R=AHA+σ2I can also be computed using FFTs using Λ1.

To reduce complexity, the inversion of each Λ(i), [Λ(i)]−1, can be performed using LU decomposition. Each [Λi] is a (K by K) matrix whose LU decomposition is per Equation 46.

Λ(i)=LU  Equation 46

L is a lower triangular matrix and U is an upper triangular matrix. Equation 7 is solved using forward and backward substitution per Equations 47 and 48.

[Λg(k)]y=[F(AHr)]k  Equation 47

y=[Λg(k)]H[F(d)]k  Equation 48

Preferably, to improve the bit error rate (BER) for data symbols at the ends of each data fields 22, 24, samples from the midamble portion 20 and guard period 18 are used in the data detection as shown in FIG. 5. To collect all the samples of the last symbols in the data fields, the samples used to determine r are extended by W−1 chips (the length of the impulse response) into the midamble 20 or guard period 18. This extension allows for substantially all the multipath components of the last data symbols of the field to be used for data detection. As shown for data field 1 22, the samples are extended into the midamble by W−1 chips. The midamble sequences are cancelled from the samples taken from the midamble 20 prior to data detection processing. For data field 2 24, the samples are extended into the guard period 18 by W−1 chips.
Certain FFT implementations required a certain field length for analysis. One of these FFT implementations is a prime factor algorithm (PFA). The PFA implementation requires the field length to be a prime number, such as 61. To facilitate PFA FFT implementation, the samples used to determine r are preferably extended to a desired PFA length. As shown in FIG. 5, data field 1 or data field 2 are extended by P chips to the desired PFA length. Alternately, block FFTs of 61 symbols are extended to block FFTs of length 64, which requires 2n FFT calculations. Since the approximation of R to a block circulant matrix is reduced, the performance typically improves.
An analysis of the computational complexity of fast joint detection is as follows. The computational complexity of calculating A is K·SF·W. The computational complexity of calculating AHA is per Equation 49.




  
    
      
        
          
            
              
                
                  
                    (
                    
                      
                        K
                        2
                      
                      +
                      K
                    
                    )
                  
                  2
                
                ⁡
                
                  [
                  
                    
                      2
                      ⁢
                      
                        (
                        
                          SF
                          +
                          W
                          -
                          1
                        
                        )
                      
                    
                    -
                    
                      (
                      
                        
                          n
                          max
                        
                        -
                        1
                      
                      )
                    
                  
                  ]
                
              
              ⁢
              
                
                  n
                  max
                
                2
              
            
            -
            
              
                
                  (
                  
                    
                      K
                      2
                    
                    -
                    K
                  
                  )
                
                2
              
              ⁢
              
                (
                
                  SF
                  +
                  W
                  -
                  1
                
                )
              
              ⁢
              
                
              
              ⁢
              where
              ⁢
              
                
              
              ⁢
              
                n
                max
              
            
          
          =
          
            
              min
              ⁡
              
                (
                
                  
                    N
                    s
                  
                  ,
                  
                    
                      (
                      
                        SF
                        +
                        W
                        -
                        1
                      
                      )
                    
                    /
                    SF
                  
                
                )
              
            
            +
            1
          
        
        )
      
    
    
      
        Equation
        ⁢
        
          
        
        ⁢
        49
      
    
  




Calculating (AHr) A as a matrix-vector multiplication has a computational complexity of K Ns (SF+W−1). Calculating the FFT of a jth column-block of R requires K2·(Ns log2 Ns) calculations. Calculating the Fourier transform of AHr requires K(Ns log 2 Ns) calculations. The inversion of each matrix [Λ(k)], without Cholesky decomposition, requires K3 calculations. For Ns frequency points, the total number of calculations is NsK3. Calculating [F(d)]k=[Λ(k)]−1[F(AHr)]k requires (K2) multiplications for Ns frequency points. Accordingly, the total number of calculations is NsK2. The Inverse FFT of [F(d)] requires K(Ns log 2 Ns) calculations.
To illustrate the complexity for fast joint detection, the million real operations per second (MROPS) for processing a TDD Burst Type I with Nc=976, SF=16, K=8, Ns=61 and W=57 chips is determined. The calculations A, (AHA), a column-block of R, [Λ(k)]−1 are performed once per burst, i.e. 100 times per second. The calculations AHr, F [AHr], computing [F(d)]k and the inverse FFT of [F(d)] are performed twice per burst, i.e. 200 times per second. Four calculations are required to convert a complex operation into a real operation. The results are illustrated in Table 1.









TABLE 1







MROPS
















Functions executed once per burst








Calculating A
3.0


Calculating AHA
4.4


Calculating F([R]j]
9.2614


Calculating [Λ(k)]−1
12.4928







Functions executed twice per burst








Calculating AHr
28.11


Calculating F [AHr]
2.3154


Calculating [F(d{circumflex over ( )})]k = [Λ(k)]−1[F(AHr)]k
3.1232


Inverse FFT of [F(d{circumflex over ( )})]
2.3154


Total number of MROPS required for fast joint detection
65.0182





Note:


in Table 1, (AHr) was calculated directly as a matrix-vector multiplication.






If LU decomposition is used to determine [Λ(k)]−1, the complexity reduces to 54.8678 MROPS. If FFTs are used to determine (AHr), the complexity reduces from 65.0182 MROPS to 63.9928 MROPS.
A comparison of the complexity of fast joint detection and other detection techniques is as follows. The complexity of the following three techniques for a TDD Burst Type I with SF=16 and K=8 is per Table 2.








TABLE 2





Technique
MROPS
















Approximate Cholesky based Joint Detection, (JDChol)
82.7


Single User Detection: Approximate Cholesky based
205.2276


Equalization followed by a Hadamard Transform based


Despreading (SDChol)


Fast Joint Detection (JDFFT)
65.0182









The performance of the three detection techniques and a reference matched filtering (MF) data detection technique were compared by simulation over 800 timeslots. The simulations used the precision provided by Matlab, i.e. no finite precision effects were considered. The simulations used channels specified by WCDMA TDD WG4; SF=16 and K=8 and 12 and were performed for the downlink with no transmit diversity to facilitate comparison to SUD.
As shown in FIGS. 6 and 7, respectively, for cases 1 and 3, the performance of fast joint detection, JDFFT, is very close to that of the Cholesky based Joint Detection, JDChol. The other data detection approaches did not perform as well as JDChol or JDFFT. For the tddWg4 Case2 channel as shown in FIG. 8. JDFFT shows some degradation compared to JDChol. It also performs similarly to the SUD based Cholesky algorithm, SDChol. For a high data rate service, such as a 2 Mbps service, as shown in FIGS. 9-11. JDFFT performs close to or slightly worse than JDChol and better than the other approaches.

## Claims

1. A method for code division multiple access communication comprising:
sampling a combined signal having K data signals received over a shared spectrum to produce combined signal samples;
producing a combined channel response matrix using codes and impulse responses of the K data signals;
determining a block column of a cross correlation matrix using the combined channel response matrix;
taking a Fourier transform of a complex conjugate transpose of the combined channel response matrix multiplied to the combined signal samples;
multiplying an inverse of a Fourier transform of each block entry to a result of the Fourier transform to produce a data vector Fourier transform; and
taking an inverse Fourier transform of the data vector Fourier transform to produce data of the K data signals.

2. The method of claim 1 wherein the taking a Fourier transform is by multiplying the conjugate transpose of the combined channel response matrix to the combined signal samples and taking the Fourier transform of a result of the conjugate transpose multiplication.

3. The method of claim 1 including using a Cholesky decomposition of the block entries of the diagonal matrix to determine the data.

4. The method of claim 1 including determining the data over a data field time period of a time division duplex communication burst where the combined signal samples extend beyond the data field time period.

5. The method 4 wherein the determining the data uses extended samples of the combined signal samples that extend beyond the data field time period for a length of an estimated impulse response.

6. The method of claim 4 wherein the determining the data uses combined signal samples that extend beyond the data field time period so that a length of the combined signals is a length compatible with a prime factor algorithm fast Fourier transform.

7. An apparatus for code division multiple access communication comprising:
a receiving device configured to receive a plurality of K data signals over a shared spectrum;
a sampling device configured to sample the combined signal to produce combined signal samples;
a channel estimator configured to estimate impulse responses of the K data signals;
a data detection device configured to produce a combined channel response matrix using codes and estimated impulse responses of the K data signals;
the data detection device configured to determine a block column of a cross correlation matrix using the combined channel response matrix;
the data detection device configured to take a Fourier transform of a complex conjugate transpose of the combined channel response matrix multiplied to the combined signal samples;
the data detection device configured to multiply an inverse of a Fourier transform of each block entry to a result of the Fourier transform to produce a data vector Fourier transform; and
the data detection device configured to take an inverse Fourier transform of the data vector Fourier transform to produce data of the K data signals.

8. The apparatus of claim 7 wherein the data detection device is configured to take the Fourier transform by multiplying the conjugate transpose of the combined channel response matrix to the combined signal samples and to take the Fourier transform of a result of the conjugate transpose multiplication.

9. The apparatus of claim 7 wherein the data detection device is configured to use a Cholesky decomposition of the block entries of the diagonal matrix to determine the data.

10. The apparatus of claim 7 wherein the data detection device is configured to determine the data over a data field time period of a time division duplex communication burst where the combined signal samples extend beyond the data field time period.

11. The apparatus of claim 10 wherein the data detection device is configured to use extended samples of the combined signal samples that extend beyond the data field time period for a length of an estimated impulse response.

12. The apparatus of claim 7 wherein the data detection device is configured to use combined signal samples that extend beyond the data field time period so that a length of the combined signals is a length compatible with a prime factor algorithm fast Fourier transform.

13. The apparatus of claim 7 configured as a User Equipment.

14. The apparatus of claim 7 configured as a base station.