Abstract:
Improved techniques are disclosed for quantizing complex vectors in communication systems. For example, a method includes the following steps. At least one complex vector representative of at least one element of a communication system is obtained. A codeword that approximates the complex vector is identified. The identified codeword is a codeword, from a set of codewords, wherein a real part of a product of the codeword and a scaled version of the complex vector is about maximal over the set of codewords. The scaled version of the complex vector is the product of the complex vector and a constant from a set of constants. In one embodiment, the element of the communication system that the complex vector represents is a channel between a base station and a user terminal in the communication system.

Description:
FIELD OF THE INVENTION  
       [0001]    The present invention generally relates to communication systems and, more particularly, to techniques for quantizing complex vectors in such communication systems. 
       BACKGROUND OF THE INVENTION  
       [0002]    Quantizers of complex vectors find numerous applications in communication systems. A typical example is a multiple-input, multiple-output (MIMO) communication system. In a typical MIMO communication system, a multi-antenna array in a base station sends multiple data streams selectively and simultaneously to autonomous single-antenna terminals, also referred to as “users,” thereby achieving throughput gains relative to a set of single-antenna links. Multi-user systems of this type are sometimes referred to as MIMO broadcast systems. 
         [0003]    One drawback of multi-user MIMO systems is that the base station has to know the propagation characteristics of the forward channel. The process through which the base station obtains this information is generally referred to as training. See, for example, U.S. Patent Application Publication No. 2005/0265290 to Hochwald et al. entitled “Feedback Method for Channel State Information of a Wireless Link,” which is commonly assigned herewith and incorporated by reference herein. 
         [0004]    Each of the single-antenna terminals may generate forward channel state information in the form of a corresponding channel vector which characterizes the channel between the base station and that terminal. The channel vectors may be based on measurements made by the terminals using pilot signals transmitted by the base station over the forward channel. Each terminal actually identifies a code vector (or codeword) from a predefined codebook that maximizes a product of the code vector and the channel vector which characterizes the channel between the base station and that terminal. The codeword is thus considered a quantization (approximation) of the channel vector. The terminals transmit their identified code vectors back to the base station over the reverse channel. 
         [0005]    The base station uses the identities of the code vectors received from the terminals to precode data in order to improve MIMO data transmissions. However, when components of the code vectors are complex, such measurements require extensive receiver overhead in hardware, software, and/or processing time. 
         [0006]    Accordingly, a need exists for improved techniques for quantizing complex vectors in communication systems such as MIMO broadcast systems. 
       SUMMARY OF THE INVENTION  
       [0007]    Principles of the invention provide improved techniques for quantizing complex vectors in communication systems. 
         [0008]    For example, in one aspect of the invention, a method includes the following steps. At least one complex vector representative of at least one element of a communication system is obtained. A codeword that approximates the complex vector is identified. The identified codeword is a codeword, from a set of codewords, wherein a real part of a product of the codeword and a scaled version of the complex vector is about maximal over the set of codewords. The scaled version of the complex vector is the product of the complex vector and a constant from a set of constants. 
         [0009]    Further, the identifying step may further include the following steps. For each constant in the set of constants, a vector is computed as a product of the constant and the complex vector. For each computed vector, input values to a selected decoding algorithm are computed, wherein the computed input values are real. For each set of input values, the selected decoding algorithm is executed to generate a decoding result. A maximal decoding result is determined from decoding results of each of the sets of input values, wherein the codeword that approximates the complex vector is identified as the codeword associated with the maximal decoding result. 
         [0010]    In one embodiment, the element of the communication system that the complex vector represents is a channel between a base station and a user terminal in the communication system. Thus, the user terminal performs the complex vector obtaining step and the codeword identification step, and may then transmit an index corresponding to the identified codeword to the base station. The base station may then utilize the index to reconstruct the complex vector representative of the channel between the base station and the user terminal such that an information transmission rate between the base station and the user terminal is increased. In one embodiment, the communication system is a multiple-input, multiple-output (MIMO) broadcast system. 
         [0011]    In another aspect of the invention, a method includes generating a codebook including codewords, wherein a codeword in the codebook is identifiable as an approximation of a complex vector representative of at least one element of a communication system when a real part of a product of the codeword and a scaled version of the complex vector is about maximal over the codebook, wherein the scaled version of the complex vector is the product of the complex vector and a constant from a set of constants. 
         [0012]    These and other objects, features and advantages of the present invention will become apparent from the following detailed description of illustrative embodiments thereof, which is to be read in connection with the accompanying drawings. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS  
         [0013]      FIG. 1  shows a multiple-input, multiple-output communication system for implementing an embodiment of the invention. 
           [0014]      FIG. 2  shows a methodology for quantizing a complex vector according to an embodiment of the invention. 
           [0015]      FIG. 3  shows a processing architecture for implementing a methodology for quantizing a complex vector according to an embodiment of the invention. 
       
    
    
     DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS  
       [0016]    Principles of the present invention will be illustrated below in conjunction with exemplary multi-user MIMO systems and associated techniques for quantizing complex channel vectors. It should be understood, however, that the invention is not limited to use with any particular type of communication system or type of complex vector. The disclosed techniques are suitable for use with a wide variety of other communication systems which utilize various types of complex vectors, and in numerous alternative applications. By way of example only, in some relay assisted communication systems, a relay quantizes vectors transmitted by the source and then transmits the quantized version of the vectors to the destination. 
         [0017]    Aspects of the present invention may be implemented in otherwise conventional wireless networks such as cellular, Wi-Fi or WiMax networks, or in a wide variety of other types of wireless communication systems. The term “base station” as used herein is therefore intended to be construed broadly so as to encompass, by way of example, an access point of a wireless network, or any other type of wireless communication system entity which utilizes MIMO techniques to communicate with multiple users. 
         [0018]      FIG. 1  shows a MIMO broadcast communication system with feedback. In MIMO system  100 , base station  102  is equipped with M transmitting antennas. The base station transmits independent messages to K terminals (receivers or mobiles), denoted as  104 - 1  through  104 -K. Each of the K terminals is equipped with one antenna. 
         [0019]    Base station  102  transmits signal x j εC from the j-th antenna. So it can be stated that the base station transmits a vector x=(x 1 , . . . , x M )εC M . During transmission from the i-th antenna to the m-th terminal, the signal x j  is multiplied by the channel coefficient h m,j . Thus, the terminal m receives the signal y m =h m x † +w m , where h m =(h m,1 , . . . ,h m,M )εC M  is the channel vector of the m-th terminal and z m  is an additive noise. It is to be understood that row vectors are denoted herein by boldface letters, and transposition and complex conjugation of complex vectors by †. The entries of h m ,m=1,K, and w m ,m=1,K, are independent complex Gaussian variables CN(0, 1). The power of the transmitted vector x can not exceed P, i.e., E[∥x∥ 2 ]≦P. 
         [0020]    In the beginning of each communication session, the base station sends pilot signals to the terminals. Again, this is referred to as training. The terminals use the pilot signals to estimate their channel vectors h m . The m-th terminal decodes its channel vector h m  using a predefined codebook C={c 1 ,c 2 , . . . ,c r },c i εC M . That is, the m-th terminal computes: 
         [0000]    
       
         
           
             
               
                 
                   
                     t 
                     m 
                   
                   = 
                   
                     arg 
                      
                     
                         
                     
                      
                     
                       
                         max 
                         
                           
                             c 
                             i 
                           
                           ∈ 
                           C 
                         
                       
                        
                       
                         
                           
                              
                             
                               
                                 h 
                                 m 
                               
                                
                               
                                 c 
                                 i 
                                 † 
                               
                             
                              
                           
                           2 
                         
                         . 
                       
                     
                   
                 
               
               
                 
                   ( 
                   1 
                   ) 
                 
               
             
           
         
       
     
         [0000]    The code vector c t     m    is a quantized (approximated) version of the channel vector h m . Note that the decoding rule defined in equation (1) is a maximum likelihood decoding. 
         [0021]    Next the m-th terminal transmits the index t m  to the base station. The indices t m ,m=1, . . . ,K allow the base station to reconstruct the quantized versions c t     1   , . . . ,c t     K    of the channel vectors h 1 , . . . , h K  respectively. The base station uses the knowledge of the quantized versions of the channel vectors to increase information transmission rate. 
         [0022]    It is well known and intuitively clear that, for achieving sufficient quantization (approximation) quality, the codebook C={c 1 ,c 2 , . . . c r } has to have many code vectors, in other words r should be large. One of the main problems that prevents one from using codebooks of large sizes is that the maximum likelihood decoding defined in equation (1) becomes prohibitively complex as r grows. 
         [0023]    It is well known that in the case of information transmission (not quantization) some codes, including codes of very large sizes, can be decoded very efficiently. Typical communication scenario in this case is the following. Let V={v 1 , . . . , v r } be a code over a finite alphabet A={a 1 ,a 2 , . . . a q }, that is entries v j  of any code vector v=(v 1 , . . . ,v M ) belong to A. Assume that we want to transmit a code vector v=(v 1 , . . . ,v M )εV. To do this we replace elements {a 1 ,a 2 , . . . , a q } of A with signals that can be physically transmitted via a given channel media. For example, in the case of wireless transmission, we replace a 1 , . . . ,a q εA with complex signals s 1 , . . . ,s q εC, and in the case of fiber optical transmission, we replace a 1 , . . . ,a q εA by real signals s 1 , . . . ,s q εR. As a result of this replacement, we obtain the codebook C=(c 1 , . . . ,c r }. We will assume that c i  is obtained from v i . 
         [0024]    Example 1. Let A={0,1,2,3} and 
         [0000]      V={(0,0,0),(1,2,3),(2,3,1),(3,1,2)}. 
         [0000]    If we replace elements of A with the complex signals s 1 =1, s 2 =i, s 3 =−1, s 4 =−i (here i=√{square root over (−1)}), then we obtain: 
         [0000]      C{(1,1,1),(i,−1,−i),(−1,−i,i),(−i,i,−1)}. 
         [0000]    If we want to transmit a code vector v=(v 1 , . . . ,v M )εV, we find the corresponding code vector c=(c 1 , . . . ,c M ) in C and transmit it via a noisy channel. On the other end of the channel, we receive a vector h=(h 1 , . . . ,h M ). To decode h, we compute the input values of the decoder: 
         [0000]        z   i,j =log  Pr ( c   j   =s   i   |h   j )=log  Pr ( v   j   =a   i   |h   j ), 
         [0000]      i=1, . . . ,q; j=1, . . . ,M, 
         [0000]    and apply any decoding algorithm applicable for the code V. An advantage of codes over finite alphabets is that there exist many efficient algorithms for their decoding. For instance, if elements a 1 , . . . ,a q  form a finite field GF(q), or more generally an additive group G, we can build a code trellis for V and conduct an ML (Maximum-Likelihood) decoding using the Viterbi algorithm (see, e.g., J. K. Wolf, “Efficient Maximum-Likelihood Decoding of Linear Block Codes Using Trellis,” IEEE Trans. Inform. Theory, vol. 24, pp. 7680, 1978) using values z i,j  as the trellis branch metrics. The complexity of this decoding is proportional to q M−k ,k=log q  r, which can be significantly smaller than the straightforward approach, whose complexity is proportional to r. Another possibility is to use the Chase decoding (see, e.g., D. Chase, “A Class of Algorithms for Decoding Block Codes with Channel Measured Information,” IEEE Trans. Inform. Theory, vol. 18, pp. 170-182, 1972). There are many other efficient decoding techniques for codes over finite alphabets. 
         [0025]    Let us consider now the quantization scenario. Similar to the information transmission case, we use a codebook V=(v 1 , . . . ,v r ) over a finite alphabet A={a q , . . . ,a q }. We replace elements of A with complex signals s 1 , . . . ,s q  and obtain the codebook C={c 1 , . . . ,c r }. We assume that the code vector of c i  is obtained from v i . 
         [0026]    According to the decoding rule expressed above in equation (1), for a given complex vector h, a decoder is supposed to find the code vector cεC that gives the largest (or at least large) value |hc † |. Unfortunately, the known efficient decoding algorithms of V are not immediately applicable in this case. The reason for this is that, unlike the information transmission scenario, we can not compute the probabilities log Pr(c j =s i |h j ), instead, according to equation (1), we must work with complex values h 1 , . . . ,h M . 
         [0027]    To show that this is indeed a problem, let us consider the Viterbi decoding. One possible approach is to form the input values of the decoder as z i,j =h j ·s i   † . The problem is that values z i,j  are not real, but complex. Let two codewords c=(c 1 ,c 2 , . . . ,c M ) and c′=(c′ 1 ,c′ 2 , . . . ,c′ M ) belong to trellis paths that go through the same trellis node at time t. Define S p =Σ j=1   t h j ·c j   †  and S′ p =Σ j=1   t h j c′ j   \ . Then, unlike the standard case, the fact that |S p | is bigger than |S′ p | does not necessarily mean that |hc † |&gt;h c ′ † |, as the value of |hc † | depends also on the phase of S p  and on the phase of S f =Σ i=t+1   M h i c i   \ . 
         [0028]    Principles of the invention provide a solution to this problem in the following manner: 
         [0029]    For any codebook C, we have: 
         [0000]    
       
         
           
             
               
                 arg 
                 C 
               
                
               
                 
                   max 
                   
                     
                       c 
                       i 
                     
                     ∈ 
                     C 
                   
                 
                  
                 
                    
                   
                     hc 
                     i 
                     † 
                   
                    
                 
               
             
             = 
             
               
                 arg 
                 C 
               
                
               
                 
                   max 
                   
                     α 
                     ∈ 
                     
                       [ 
                       
                         0 
                         , 
                         
                           2 
                            
                           π 
                         
                       
                       ] 
                     
                   
                 
                  
                 
                     
                 
                  
                 
                   
                     max 
                     
                       
                         c 
                         i 
                       
                       ∈ 
                       C 
                     
                   
                    
                   
                      
                     
                        
                       
                         ( 
                         
                           ( 
                           
                             
                                
                               α 
                             
                              
                             
                               hc 
                               i 
                               † 
                             
                           
                           ) 
                         
                         ) 
                       
                     
                      
                   
                 
               
             
           
         
       
     
         [0000]    Let c R  and c I  be the real and imaginary parts of cεC. It is easy to see that: 
         [0000]    
       
         
           
             
                
               
                 ( 
                 
                   hc 
                   † 
                 
                 ) 
               
             
             = 
             
               
                 
                   ∑ 
                   
                     j 
                     = 
                     1 
                   
                   m 
                 
                  
                 
                   
                     h 
                     j 
                     R 
                   
                    
                   
                     c 
                     j 
                     R 
                   
                 
               
               + 
               
                 
                   h 
                   j 
                   I 
                 
                  
                 
                   
                     c 
                     j 
                     I 
                   
                   . 
                 
               
             
           
         
       
     
         [0030]    Thus, a decoding of h can be organized as follows. First, for all αε[0,2π], we compute vectors q=e iα h, where e iα  is an infinite set of constants since there are theoretically infinite many α in αε[0,2π]. Second, for each q, we compute the input values of the decoder: 
         [0000]        z   i,j   =s   i   R   q   j   R   +s   i   I   q   j   I , 
         [0000]      i=1, . . . ,q; j=1, . . . ,M. 
         [0000]    Third, we use any decoding algorithm of the code V with the decoder&#39;s input values z i,j . Note advantageously that z i,j  are real and therefore we do not have any problems with using any decoder of the code V. Finally, we choose the best result among all the decodings. 
         [0031]    Note that if we use an ML decoding algorithm of the code V at the third step, this procedure becomes equivalent to the decoding defined in equation (1) and thus it is an ML decoding of the complex vector h. 
         [0032]    The above-described procedure may not be the easiest to implement under all conditions since it calls for computing and decoding of infinitely many vectors q=e iα h, αε[0,2π] since, as explained above, there is theoretically an infinite number of α&#39;s between 0 and 2π. Accordingly, below we describe an embodiment that may be implemented more easily in practice by using a finite set of constants. 
         [0033]    Let D be a decoding algorithm of V that works with real input values of the decoder. For example, D could be the Viterbi decoding or Chase decoding. 
         [0034]      FIG. 2  shows a rotate and quantize decoding algorithm according to an embodiment of the invention. Decoding algorithm  200  is performed by each of the terminals ( 104 - 1  through  104 -K in  FIG. 1 ).
       Step  201 : Form the finite set α p =2π/n p, p=0, . . . ,n−1.   Step  202 : For p from 0 to n do steps  203 - 206 .   Step  203 : Form the vector q=e iα     p   h (where q may be considered a scaled version of h).   Step  204 : Compute the decoder&#39;s input values:         
         [0000]    
       
      
       z 
       i,j 
       =s 
       i 
       R 
       q 
       j 
       R 
       +s 
       i 
       I 
       q 
       j 
       I  
      
     
         [0000]      i=1, . . . ,q; j=1, . . . ,M.       Step  205 : Decode q using D with the decoder&#39;s input values z i,j  and let t p  (or equivalently c t     p   εC) be the decoding result.   Step  206 : Compute d p =|         (qc t     p     † )|.   Step  207 : Determine the decoding result t b  where b=argmax 0≦p≦n−1 d p .         
         [0042]    The value n is a decoding parameter. The larger n, the closer decoding algorithm  200  is to the ML decoding represented by equation (1). 
         [0043]    Note that if D is the Viterbi algorithm, then at step  205 , we conduct the Viterbi decoding with the trellis branch metrics z i,j . 
         [0044]    Let us consider an example. 
         [0045]    Example 2. Let V and C be the same as in Example 1. Let h=(1,i,2), n=4, and let D be any ML decoding of V. Then for p=0, . . . ,3 we have the following values at steps  203 - 206  of algorithm  200 : 
         [0000]    
       
         
           
             
               p 
               = 
               
                 
                   0 
                    
                   
                     : 
                   
                    
                   q 
                 
                 = 
                 
                   ( 
                   
                     1 
                     , 
                     i 
                     , 
                     2 
                   
                   ) 
                 
               
             
             , 
             
               values 
                
               
                   
               
                
               
                 z 
                 
                   i 
                   , 
                   j 
                 
               
                
               
                   
               
                
               are 
                
               
                   
               
                
               
                 
                   
                     1 
                   
                   
                     0 
                   
                   
                     2 
                   
                 
                 
                   
                     0 
                   
                   
                     1 
                   
                   
                     0 
                   
                 
                 
                   
                     
                       - 
                       1 
                     
                   
                   
                     0 
                   
                   
                     
                       - 
                       2 
                     
                   
                 
                 
                   
                     0 
                   
                   
                     
                       - 
                       1 
                     
                   
                   
                     0 
                   
                 
               
             
           
         
       
       
         
           
             
               
                 t 
                 0 
               
               = 
               1 
             
             , 
             
               
                 d 
                 0 
               
               = 
               3 
             
           
         
       
       
         
           
             
               p 
               = 
               
                 
                   1 
                    
                   
                     : 
                   
                    
                   q 
                 
                 = 
                 
                   ( 
                   
                     i 
                     , 
                     
                       - 
                       1 
                     
                     , 
                     
                       2 
                        
                       i 
                     
                   
                   ) 
                 
               
             
             , 
             
               values 
                
               
                   
               
                
               
                 z 
                 
                   i 
                   , 
                   j 
                 
               
                
               
                   
               
                
               are 
                
               
                   
               
                
               
                 
                   
                     0 
                   
                   
                     
                       - 
                       1 
                     
                   
                   
                     0 
                   
                 
                 
                   
                     1 
                   
                   
                     0 
                   
                   
                     2 
                   
                 
                 
                   
                     0 
                   
                   
                     1 
                   
                   
                     0 
                   
                 
                 
                   
                     
                       - 
                       1 
                     
                   
                   
                     0 
                   
                   
                     
                       - 
                       2 
                     
                   
                 
               
             
           
         
       
       
         
           
             
               
                 t 
                 1 
               
               = 
               3 
             
             , 
             
               
                 d 
                 1 
               
               = 
               2 
             
           
         
       
       
         
           
             
               p 
               = 
               
                 
                   2 
                    
                   
                     : 
                   
                    
                   q 
                 
                 = 
                 
                   ( 
                   
                     1 
                     , 
                     
                       - 
                       1 
                     
                     , 
                     
                       - 
                       2 
                     
                   
                   ) 
                 
               
             
             , 
             
               values 
                
               
                   
               
                
               
                 z 
                 
                   i 
                   , 
                   j 
                 
               
                
               
                   
               
                
               are 
                
               
                   
               
                
               
                 
                   
                     1 
                   
                   
                     0 
                   
                   
                     
                       - 
                       2 
                     
                   
                 
                 
                   
                     0 
                   
                   
                     
                       - 
                       1 
                     
                   
                   
                     0 
                   
                 
                 
                   
                     1 
                   
                   
                     0 
                   
                   
                     2 
                   
                 
                 
                   
                     0 
                   
                   
                     1 
                   
                   
                     0 
                   
                 
               
             
           
         
       
       
         
           
             
               
                 t 
                 2 
               
               = 
               1 
             
             , 
             
               
                 d 
                 2 
               
               = 
               3 
             
           
         
       
       
         
           
             
               p 
               = 
               
                 
                   1 
                    
                   
                     : 
                   
                    
                   q 
                 
                 = 
                 
                   ( 
                   
                     
                       - 
                       i 
                     
                     , 
                     1 
                     , 
                     
                       2 
                        
                       i 
                     
                   
                   ) 
                 
               
             
             , 
             
               values 
                
               
                   
               
                
               
                 z 
                 
                   i 
                   , 
                   j 
                 
               
                
               
                   
               
                
               are 
                
               
                   
               
                
               
                 
                   
                     0 
                   
                   
                     1 
                   
                   
                     2 
                   
                 
                 
                   
                     1 
                   
                   
                     0 
                   
                   
                     
                       - 
                       2 
                     
                   
                 
                 
                   
                     0 
                   
                   
                     
                       - 
                       1 
                     
                   
                   
                     0 
                   
                 
                 
                   
                     1 
                   
                   
                     0 
                   
                   
                     2 
                   
                 
               
             
           
         
       
       
         
           
             
               
                 t 
                 3 
               
               = 
               3 
             
             , 
             
               
                 d 
                 3 
               
               = 
               2 
             
           
         
       
     
         [0046]    Thus, at step  207  of the algorithm, we have b=0 and t 0 =1. 
         [0047]    Note that computations according to equation (1) give the same results. 
         [0048]      FIG. 3  shows a processing architecture for implementing a methodology for quantizing a complex vector according to an embodiment of the invention. More particularly,  FIG. 3  shows a more detailed view of one possible configuration of MIMO broadcast system  300  including terminal  310  and base station  320 . Note that only one terminal is shown for the sake of simplicity. Terminal  310  corresponds to one of terminals  104 - 1  through  104 -K in  FIG. 1 , while base station  320  corresponds to base station  102  in  FIG. 1 . In this embodiment, terminal  310  includes processor  312  and memory  314 , while base station  320  includes processor  322  and memory  324 . Omitted from the figure for clarity of illustration are transceiver circuitry and antennas. 
         [0049]    One or more software programs for implementing complex vector decoding as described herein may be stored in memory  314  and executed by processor  312 . Memory  314  may therefore be considered a processor-readable storage medium. Processor  312  may include multiple integrated circuits, digital signal processors or other types of processing devices, and associated supporting circuitry, in any combination. Of course, numerous alternative arrangements of hardware, software or firmware in any combination may be utilized in implementing terminal  310  or particular elements thereof. Similarly, processor  322  and memory  324  may be implemented as described above in order to perform the functions of the base station. 
         [0050]    Although illustrative embodiments of the present invention have been described herein with reference to the accompanying drawings, it is to be understood that the invention is not limited to those precise embodiments, and that various other changes and modifications may be made by one skilled in the art without departing from the scope or spirit of the invention.