Patent Publication Number: US-2003223516-A1

Title: Sequential bezout space-time equalizers for MIMO systems

Description:
FIELD OF INVENTION  
       [0001] The present invention relates generally to communications systems, and more particularly to interference cancellation and signal recovery in wireless multiple-input-multiple-output communications systems.  
       BACKGROUND OF THE INVENTION  
       [0002] Multiple-input-multiple-output (MIMO) systems have the potential to greatly increase the capacity of wireless communications systems where there are multiple antennas in both the transmitter and the receiver.  
       [0003] A MIMO system has p transmitters and q receivers. If s j (k) is a coded input sequence at transmitters j=1, . . . , p, h ij (k) is a channel impulse response from transmitter j to receiver i=1, . . . , q, and d is a maximum length of the channel impulse response among all of the channels, then an output x i (k) at receiver i can be expressed as a convolutional product  
                 x   i          (   k   )       =         ∑     j   =   1     p            ∑     l   =   0     d              h   ij          (   l   )              s   j          (     k   -   l     )             +       n   i          (   k   )                 (   1   )                       
 
       [0004] where n i (k) denotes additive-white-Gaussian-noise (AWGN) at the receiver i.  
       [0005] An equivalent expression of equation (1) in the frequency domain is  
         x ( D )= H ( D ) s ( D )+ n ( D )   (2)  
       [0006] where s(D)=[s 1 (D) s 2 (D) . . . s p (D)] T , x(D)=[x 1 (D) x 2 (D) . . . x q (D)] T , H(D)={H 1j (D)} 1,j , and n(D)=[n 1 (D) n 2 (D) . . . n q (D)] T  are the z-transform vectors (or matrix), and D=z −1  denotes a unit delay of corresponding sequences or impulse responses.  
       [0007] The q×p polynomial matrix H(D) is referred to as the transfer function of the MIMO system, and the polynomial vector h j (D)=[h 1j (D) h 2j (D) . . . h qj (D)] T  (j=1, . . . p) is the channel response from j th  transmitter antenna to all receive antennas.  
       [0008] In such a wireless system, transmitted signal sequences are subject to time-domain inter-symbol interference (ISI) and space-domain inter-channel-interference (ICI) from other signals. This makes it difficult to correctly retrieve the transmitted sequences. In addition, for most practical channels, the frequency-response characteristics are time-variant. This makes it more difficult to design an optimum filter and demodulator.  
       [0009] A Bezout equalizer offers an effective tool to reduce ISI and ICI in MIMO systems. The Bezout equalizer uses an array of linear finite-impulse response (FIR) filters. To retrieve the input sequences  
         {       s   j          (   k   )       }       j   =   1     p                 
 
       [0010] from noise-corrupted observations  
           {       x   i          (   k   )       }       i   =   1     q     ,                 
 
       [0011] the FIR filter can be applied at the receiver, see Ding et al., “ Blind Equalization and Identification,”  Marcel Dekker, Inc., New York, 2001. With appropriate parameters, a linear combination of the q filtered receiver streams can reconstruct an individual input stream while reducing both ISI and ICI.  
       [0012] The following definitions are used for the Bezout inverse theory, set out below.  
       [0013] Definition 1—Perfect Recoverability  
       [0014] Given a MIMO channel with transfer function H(D), the j th  input is perfectly recoverable (PR) of order ρ if and only if there exist a nonnegative integer k j  and a 1×q polynomial vector g(D) with deg g(D)&lt;ρ such that  
                 g        (   D   )            H        (   D   )         =       D     k   j            e   j               (   3   )                       
 
       [0015] where e j  is a unit (row) vector with all elements zero except 1 at position j. The FIR filter array corresponding to g(D) in equation (3) is referred to as a (j, ρ, k) Bezout equalizer. The MIMO system is said to be PR if and only if all the p inputs are PR of a finite order.  
       [0016] An expresion  
           g        (   D   )       ×     (   D   )       =         s   j          (   D   )            D     k   j                       
 
       [0017] +noise term is obtained when g(D) in equation (3) is applied on the receiver data yields, i.e. s j (k) is reconstructed with noise and delay k j . It is known that the condition of PR for a MIMO system hinges upon the notion of coprimeness of the transfer function H(D), see Kailath et al., “ Linear Systems,”  Prentice-Hall, Englewood Cli., NJ, 1980, and Kung et al., “ An Associative Memory Approach to Blind Signal Recovery for SIMO/MIMO Systems,”  IEEE Workshop on Neural Network for Signal Processing, September 2001.  
       [0018] Definition 2—Coprime Polynomial Matrices  
       [0019] A p×p polynomial matrix R(D) is said to be a right common divisor of the rows in H(D) if H(D)=H′(D)R(D), where H′(D) is itself a polynomial matrix. Furthermore, R(D) is called a greatest right common divisor (grcd) if for any other right common divisor R′(D) there exists a polynomial matrix C(D) such that R(D)=C(D)R′(D). A polynomial matrix is delay-permissive right coprime if the determinant of its grcd has the form of a pure delay:  
         det                   R        (   D   )         =       D     k   0       .                   
 
       [0020] Theorem 1—PR Condition of MIMO System  
       [0021] A p-in-q-out MIMO system with transfer function H(D) is PR if and only if H(D) is delay-permissive right coprime.  
       [0022] It is assumed that the channel transfer function is available at the receiver end via some estimation procedure. For perfect recovery in general, the coprime condition in Theorem 1 requires more receivers than transmitters, i.e., q&gt;p.  
       [0023]FIG. 1 shows a prior art parallel architecture of a MIMO system  100 . The system  100  includes transmitters  110 , MIMO channel  120  subject to noise  130 , receivers  140 , and Bezout equalizers  200 . Here, s j (k)  111  are the inputs at the transmitters  110 , x i (k)  141  are the outputs at the receivers  140 , and ŝ j (k)  201  are the recovered inputs after equalization 200. Under PR condition  
           G        (   D   )            H        (   D   )         =     Diag          {     D     k   j       }     .                     
 
       [0024]FIG. 2 shows the prior art Bezout equalizer  200  with FIRs  210 . The design of the Bezout equalizer can be decoupled into a task of separately designing individual equalizers for each input.  
       [0025] One prior art technique, which theoretically achieves channel capacity in flat-fading MIMO systems, is called BLAST, see Foschini, “ Layered Space - time Architecture for Wireless Communication in Fading Environments When Using Multiple Antennas ,” Bell Labs Technical Journal, Vol. 1, pp.41-59, Autumn 1996. BLAST recognizes that flat-fading MIMO channels, i.e., channels with multiple transmit and receive antennas, have enormous capacity. Capacity grows linearly with the number of transmit antennas as long as the number of receiving antennas is greater than the number of transmitting antennas. The original BLAST used a cyclic association of data streams, called layers, with transmit antennas, thereby producing an “averaged” channel which is the same for all layers. Difficulties in the realization of the original BLAST led to a modified architecture where each layer is associated with a certain transmit antenna.  
       [0026] However, in order to achieve the full capacity of the MIMO channel, long data blocks, powerful channel coding, and perfect detection of each layer are required. In addition, in practical systems, the problem of error propagation limits the performance. Particularly, the overall diversity level is limited by the diversity level obtained in the layer which is detected first. Most important, BLAST is only valid for flat-fading channels, which limits its applicability to frequency-selective channels in broadband communication.  
       [0027] Therefore, there is a need for a receiver in MIMO systems that improve upon the prior art.  
       SUMMARY OF THE INVENTION  
       [0028] The invention provides a system and method that combines Bezout space-time equalizers with sequential detection and decoding techniques for multiple-input-multiple-output (MIMO) communications systems. With a sequential space-time equalizer, previously detected transmitting streams are used to reduce interference in subsequent detected input stream. The sequential equalization and detection/decoding according to the invention successively reduces the number of unknown input streams of the MIMO system. Excess dimensionality offered by the increasing asymmetry between the transmitted and received signal spaces provides the necessary flexibility that improves the capacity of the system.  
       [0029] More particularly, the invention provides a method and system for equalizing signals transmitted over a multi-path channel and canceling the interference from the data streams sequentially. An input data stream with a highest post-processing signal-to-noise ratio (SNR) is recovered first. The interference generated by this stream is then cancelled before detecting the stream with the next highest SNR. This procedure is recursively executed until all the data streams have been recovered.  
       [0030] Furthermore, the invention provides a system and method that processes the input sequences via a layered and pipeline architecture.  
       [0031] In the system and method according to the invention, two additional parameters are used: equalizer order and equalization delay. By selecting appropriate equalizer order and equalization delay parameters, the overall performance of the system can be optimized. 
     
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
     [0032]FIG. 1 is a block diagram of a prior art parallel architecture of a MIMO system;  
     [0033]FIG. 2 is a block diagram of a prior art Bezout equalizer;  
     [0034]FIG. 3 is a block diagram of a receiver according to the invention;  
     [0035]FIG. 4 is a block diagram of sequential equalization, detection/decoding and cancellation according to the invention;  
     [0036]FIG. 5 is a block block diagram of a pipelined sequential Bezout equalizer according to the invention; and  
     [0037]FIG. 6 is a block diagram of a layered pipeline sequential Bezout equalizer according to the invention. 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT OF THE INVENTION  
     [0038]FIG. 3 shows components of a receiver  300  in a MIMO system that uses the invention. The components include a pre-processor  310 , a channel estimator  320 , and a sequential Bezout equalizer, detector/decoder, and interference canceller  400 . The receiver  100  takes as input  301  signals received at multiple antennas, and produces as output  309  decoded data streams.  
     [0039] The operation of the receiver  300  is as follows. During the pre-processing  310 , the input signals are filtered and time synchronized to produce data streams for the Bezout Space-Time Equalizer. Channel impulse response estimation is performed in block  320  to provide the H(D)  321  to the Bezout space-time equalizer  400 . The functions of block  400  are described in greater detail below.  
     [0040]FIG. 4 shows sequential equalization, detection/decoding and cancellation  400  according to the invention. This method yields a better SNR or capacity in a MIMO system than obtainable with prior art techniques.  
     [0041] First, select  405  a next input stream, of the j=1, . . . , p data streams  401  stored in a memory  402 , that has a highest post-processing signal-to-noise ratio (SNR). Then, equalize  410  the selected data stream with the Bezout FIR filter, the signal is then detected and decoded  420  using an error-correction decoder. Next, cancel  430  the contribution of the detected stream  403  from the received data stored in the memory  402  via a successive interference cancellation strategy as is commonly known in signal processing. In essence, the cancellation  430  can be performed by subtracting the decoded signal from the received signal.  
     [0042] Repeat  440  the above steps of equalizing, detecting/decoding, and cancellation for a next input stream using the interference-reduced received signal  401 , until all streams {s j (k)} j    409  have been detected  450 . Such a recursive method leads to a sequential Bezout equalization strategy according to the invention.  
     [0043] Initially, we set H (1) (D)=H(D), x (1) (D)=x(D) and k 0 =0. At step j, (j−1) input streams from transmitters have already been equalized, detected/decoded, and their interferences have been cancelled (subtracted)  430  from the receiver observation x(D) to obtain a new data vector, denoted as x (j) (D). The operations in the j th  recursive step are then: design an individual Bezout equalizer for stream j so that  
                   g   j          (   D   )              H     (   j   )            (   D   )         =       D     k   j            [     1                 0                 …                 0     ]               (   4   )                       
 
     [0044] and apply the equalizer on the recursively updated received data x (j) (D)  401 :  
                       y   i          (   D   )       =         g   j          (   D   )              x     (   j   )            (   D   )                     =         D       k   1     +     k   2     +   …   +     k   j                s   j          (   D   )         +     noise                 term                     (   5   )                       
 
     [0045] Then, detect and decode the j th  selected stream with error-correcting decoding  420  on y j (D). Provided the coding scheme has sufficient error-correction ability, we obtain a correct reconstruction of the input sequence: ŝ j (D)=s j (D), with delay  
         ∑     i   =   1     j            k   j     .                   
 
     [0046] Cancel  430  the ICI generated by j th  input stream from the received observation vector based on the following recursive formula which basically is a subtraction:  
       x   (j+1) ( D )= D   k     j     x   (j) ( D )− D   k     1     + . . . +k     j     h   j ( D ) ŝ   j ( D )   (6)  
     [0047] Equation (6) represents a virtually truncated MIMO system x (j+1) (D)=D k     1     + . . . +     j   H (j+1) (D)s (j+1) (D) with  
       H   (j+1) ( D )=[ h   j+1 ( D ) . . .  h   p ( D )] 
       s   (j+1) ( D )=[ s   j+1 ( D ) . . .  s   p ( D )] T    (7)  
     [0048] The reduced transfer function H (j+1) (D) is the last (p−j) columns of H(D).  
     [0049] This procedure is recursively applied  440  until all the p input sequences are decoded at the end  450 . Each recursion results in a size-reduced MIMO system with one less input.  
     [0050]FIG. 5 shows a pipelined implementation  500  for realization of the sequential Bezout equalizer  400  according to the invention. There are p layers  501  in the pipeline  500  for recovering p data streams. Each layer  501  includes the steps of equalization  410 , detecting and decoding  420 , and interference cancellation  430 .  
     [0051] The layered and pipelined architecture  600  is shown in FIG. 6. The processing steps in each stage proceed from left to right. In the first stage, an individual input sequence is equalized  410  sequentially one block after the other with the temporal range of detected input symbols denoted by the labels on the blocks, e.g., N+1˜2N. Each equalized block is then forwarded to the detector/decoder stage  420 . Finally, the error-corrected sequence is used by the interference canceller (IC) stage  430  to cancel the interference contributed by the detected sequence(s) from the receiver data. The interference-reduced data are now ready to be processed in the next stage, as indicated by the down arrows.  
     [0052] Each pipeline stage incurs an equalization delay of k j  for j=1, . . . , p together with a processing delay generated by the decoder and IC stages. The overall effect of these delays is depicted by the inter-layer block shifts with respect to processing time.  
     [0053] For two blocks with the same labeling, i.e., data blocks of two input streams within the same time interval, the block associated with the lower stage is processed later time. In particular, the equalization delay generated by each individual Bezout equalizer is propagated to the next stage through the decoder and IC stages, as shown by the inter-stage arrows  601 . The interference-reduced received data at the bottom of j th  layer arrive at the (j+1) th  stage in the previous data block, labeled by N+1˜2N, with exactly k j  symbols preceding the beginning of the current block, labeled by 2N+1˜3N.  
     [0054] Although the lower (later) stages have a larger processing delay, they have a greater amount of estimated inputs obtained from the higher (earlier) stages. Consequently, assuming no error propagation, a larger amount of interference is cancelled from the received data by the later stages. This, in turn, implies that the later stages are able to deliver a higher SNR gain over the parallel scheme of the prior art.  
     [0055] Optimal Order of Signal Detection  
     [0056] To prevent error propagation in this sequential architecture, it is preferred to first recover the j* th  input stream whose individual Bezout equalizer yields a highest post-processing  310  SNR. The detection order in the subsequent stages can then be determined in the same manner.  
     [0057] The following process can be used for determining the order for detecting the input streams.  
     [0058] Initially, set H (1) (D)=H(D), and an input j* th  stream with a highest SNR after pre-processing  310 , see equation (12) below, is selected. Then, remove the j* th  column from H (1) (D) to form a truncated system H (2) (D). This corresponds to the cancellation  430  of interference contributed by the j* th  input stream from the receiver data. With the truncated transfer function H (2) (D), and its corresponding individual Bezout equalizer design, the second stream is selected according to the same SNR criterion. This procedure is recursively performed until all of the p data streams  409  have been decoded.  
     [0059] A qρ×p(d+ρ) block Toeplitz resultant matrix is given below:  
                 Γ   ρ          [   H   ]       =     [           H   0           H   1         …         H   d         0       …       0           0         H   0         …         H     d   -   1             H   d         …       0           ⋮       ⋮       ⋰       ⋰       ⋰       ⋰       ⋮           0       0       …         H   0           H   1         …         H   d           ]             (   8   )                       
 
     [0060] where H i  denotes the i th  order coefficient matrix of the transfer function H(D), i.e.,  
         H        (   D   )       =       ∑     i   =   0     d            H   i            D   i                .                       
 
     [0061] Due to the presence of the left null-space of H(D), there may exist non-unique (j, ρ, k) Bezout equalizers satisfying equation (3). At the output of any equalizer g(D), the recovered signal preserves the power of the j th  transmitting stream.  
     [0062] However, the i.i.d. AWGN in the receiver is filtered by g(D), leading to a post-processing noise power of  
             N   0     2                 g   -&gt;          2                  ,                 
 
     [0063] where N 0  is the noise spectral density and {right arrow over (g)}=└g 0  g 1  . . . g ρ−1 ┘ denotes the 1×qρ coefficient vector of equalizer g(D). In order to maximize the post-processing SNR, one design criterion minimizes the 2-norm of {right arrow over (g)}.  
     [0064] According to equation (3), an optimal (j, ρ, k) Bezout equalizer, if it exists, can be equivalently derived in a resultant matrix notation as:  
                 g   -&gt;     *     =     arg                     min     g   -&gt;            {                g   -&gt;          2     |       g   -&gt;                       Γ   ρ          [   H   ]           =       e   -&gt;     r       }                 (   9   )                       
 
     [0065] where {right arrow over (e)} r  is a row vector with all elements zero except 1 at r=j+pk j .  
     [0066] Given the transfer function H(D), equation (9) can be solved by taking a singular value decomposition (SVD) on Γ ρ [H]:  
     Γ ρ [H]=UΣV   (10)  
     [0067] where Σ is a square diagonal matrix of positive singular values. Then, the solution to equation (9) is  
       {right arrow over (g)}*={right arrow over (e)}   r   V   H Σ −1   U   H    (11)  
     [0068] if and only if {right arrow over (e)} r ε row span(Γ ρ[H]).    
     [0069] Determination of j*. and k j *  
     [0070] Given a predetermined equalizer order, the input stream associated with the first stage can be selected via a joint optimization of ∥{right arrow over (g)}*∥ 2  in equation (11) over both the stream index j and the equalization delay k j . As the pair (i, k j ) has a one-to-one correspondence with r=j+pk j , see equation (9), the same goal can be achieved by minimizing ∥{right arrow over (g)}*∥ 2  over r:  
                     r   *     =     arg                     min   r          {         (       V   H          Σ     -   2          V     )     rr     |         e   -&gt;     r     ∈     Row                 Span        {   V   }           }                       j   *     =       [       (       r   *     -   1     )                   mod                 p     ]     +   1                   k   j   *     =     d   +   ρ   -   1   -         r   *     -     j   *       p                     (   12   )                       
 
     [0071] Thus equation (12) provides the optimal order for signal detection. The same equation is used to determine the best recovery stream and equalization delay for every recursion or stage of the pipeline, upon replacement of H(D)in equation (9) and (10) by H (l) (D) and p by p−l+1 in recursion l.  
     [0072] In the receiver according to the invention, each recursion reduces the dimension of the updated transfer function H (i) (D) by one. This implies a reduced virtual MIMO channel with one less input stream. Following the same idea as in equation (9), with the layered detection procedure with ordering 1, 2, . . . p, the optimal individual Bezout equalizer to recover input stream j is  
                 g   -&gt;     *     =     arg                     min     g   -&gt;            {                g   -&gt;          2     |       g   -&gt;                       Γ   ρ          [     H     (   j   )       ]           =       e   -&gt;     r       }                 (   13   )                       
 
     [0073] Because H (j) (D) is a size-reduced version of H(D), all the null-space solutions associated with the latter are also valid solutions for the former, but not vice versa. This means the post-processing SNR corresponding to H (j) (D) is equal or superior to H(D). In short, the SNR or capacity associated with the remaining source signals is significantly enhanced.  
     [0074] Effect of the Invention  
     [0075] The receiver with the sequential Bezout equalizers according to the invention has about double the SNR gain as that obtained by a parallel architecture of equal order. In addition, the receiver is less sensitive to variations of equalization delay, which provides more flexibility for recovery. For a fixed equalizer order, the sequential architecture according to the invention has a much wider range with reasonable performance, while the parallel architecture degenerates more noticeably around the optimal delay point.  
     [0076] This invention is described using specific terms and examples. It is to be understood that various other adaptations and modifications may be made within the spirit and scope of the invention. Therefore, it is the object of the appended claims to cover all such variations and modifications as come within the true spirit and scope of the invention.