Abstract:
Disclosed is a method of communicating a complex vector, using one or more index bits, the method comprising quantizing the complex vector using a codebook, the codebook comprising a plurality of complex vectors mapped from real vectors that lie on a reflected simplex where the simplex is of dimension one less than twice the length of the complex vector; indexing the quantized vector to form the one or more index bits; and transmitting the index bits to the transmitter, thereby communicating the complex vector.

Description:
TECHNICAL FIELD 
       [0001]    The present invention relates generally to wireless communication and, in particular, to vector quantization for limited feedback from receiver to transmitter. 
       BACKGROUND 
       [0002]    Multiple-input multiple-output (MIMO) systems can provide increased reliability in wireless communication links by exploiting the spatial diversity due to the increased number of transmit-receive paths. A simple technique to obtain the highest possible diversity order is to employ transmit beamforming and receive combining, which also improves the array gain. This technique requires that the transmitter has channel state information in the form of a transmit beamforming vector. It is often impractical to have a full reciprocal channel from receiver to transmitter to enable the transmitter to estimate the forward channel state information. Instead, the receiver estimates the channel state information, computes the corresponding beamforming vector, and encodes the beamforming vector in a small number of bits. These bits are sent via a feedback path to enable the transmitter to generate the beamforming vector. Such systems are known as limited feedback systems. 
         [0003]    The most straightforward approach to designing a limited feedback system is to employ scalar quantization, where each component of the beamforming vector is quantized and encoded separately. In more advanced limited feedback systems, the transmitter and receiver share a codebook of possible beamforming vectors indexed by a number of bits. The receiver chooses a beamforming vector from the codebook on the basis of maximizing the effective signal-to-noise ratio (SNR) after combining, and sends the corresponding bits to the transmitter. 
         [0004]    Beamforming vector codebooks are conventionally designed using the minimum number of feedback bits possible for a given effective SNR after combining, i.e. neglecting the search and storage requirements for the codebook. Codebook design strategies generally use numerical optimization techniques, or for larger systems, the codebooks can be randomly generated (i.e. random vector quantization, or RVQ). Such random codebooks have been shown to be asymptotically optimal as the number of bits and transmit antennas increase. 
         [0005]    Unfortunately, the codebook size increases exponentially with the number of transmit antennas to maintain a given effective SNR or capacity loss with respect to the optimal unquantized system. Since RVQ codebooks have no structure, an exhaustive search is usually required to find the bits encoding a given beamforming vector, or vice versa. For time-varying channels, the resulting delay due to the excessive search time reduces the effectiveness of the beamforming vector when employed at the transmitter. The computation required for such an exhaustive search also consumes power, which is undesirable for low-power mobile wireless devices. Non-exhaustive methods for searching unstructured codebooks at the expense of increased memory requirements have been documented. One of these methods is a tree-search, where storage of the tree and codebook is required. An additional consequence of the exponential growth in codebook size with antenna number is that storage of the codebook may be infeasible for large numbers of antennas. 
         [0006]    The problem of codebook search time and storage requirements is of particular importance to multiuser systems, where quantization errors increase the interference between users. 
       SUMMARY 
       [0007]    Disclosed are arrangements which seek to ameliorate the disadvantages of existing methods by using Reflected Simplex codebooks in beamforming vector quantization for limited feedback MIMO systems. The disclosed Reflected Simplex codebooks adhere to a geometric construction, consisting of integer coordinates that lie within the original and reflected images about the axes of a (2N T −1)-dimensional simplex, where N T  is the number of transmit antennas. Also disclosed is a method of indexing the Reflected Simplex codebook with low time and storage requirements. Also disclosed is an efficient method of searching through the codebook for the optimal quantized beamforming vector. 
         [0008]    According to a first aspect of the present invention, there is provided a method of communicating a complex vector, using one or more index bits, the method comprising: quantizing the complex vector using a codebook, the codebook comprising a plurality of complex vectors mapped from real vectors that lie on a reflected simplex where the simplex is of dimension one less than twice the length of the complex vector; indexing the quantized vector to form the one or more index bits; and transmitting the index bits to the transmitter, thereby communicating the complex vector. 
         [0009]    According to a second aspect of the present invention, there is provided a method of wireless communication between a transmitter comprising a plurality of transmit antennas and a receiver over a channel, the method comprising: estimating channel state information for the channel; computing an optimal beamforming vector for the plurality of transmit antennas from the channel state information; quantizing the optimal beamforming vector using a codebook, the codebook comprising a plurality of complex vectors mapped from real vectors that lie on a reflected simplex where the simplex is of dimension one less than twice the length of the optimal beamforming vector; indexing the quantized vector to form one or more index bits; and transmitting the index bits to the transmitter. 
         [0010]    According to a third aspect of the present invention, there is provided a receiver for implementing the method according to the second aspect. 
         [0011]    According to a fourth aspect of the present invention, there is provided a system for wireless communication over a channel, the system comprising: a transmitter comprising a plurality of transmit antennas; and a receiver adapted to: estimate channel state information for the channel; compute an optimal beamforming vector for the plurality of transmit antennas from the channel state information; quantize the optimal beamforming vector using a codebook, the codebook comprising a plurality of complex vectors mapped from real vectors that lie on a reflected simplex where the simplex is of dimension one less than twice the length of the optimal beamforming vector; index the quantized vector to form one or more index bits; and transmit the index bits to the transmitter. 
         [0012]    Other aspects of the invention are also disclosed. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0013]    Embodiments of the present invention are described hereinafter with reference to the drawings, in which: 
           [0014]      FIG. 1  is a block diagram showing a limited feedback MIMO wireless communication system on which the embodiments of the present invention may be practiced; 
           [0015]      FIG. 2  is a plot of the vectors in the PVQ codebook D(2, 2); 
           [0016]      FIG. 3  is a flowchart illustrating a method of limited feedback wireless communication carried out by the system of  FIG. 1 ; 
           [0017]      FIG. 4  is a flowchart illustrating a method of obtaining an index for a complex vector in the Reflected Simplex codebook, as used in the method of  FIG. 3 ; 
           [0018]      FIG. 5  is a plot illustrating the zigzag ordering of complex values used in the indexing method of  FIG. 4 ; 
           [0019]      FIG. 6  is a flowchart illustrating a method of searching the Reflected Simplex codebook, as used in the method of  FIG. 7 ; and 
           [0020]      FIG. 7  is a flowchart illustrating a method of encoding a real vector to index bits, as used in the method of  FIG. 3 . 
       
    
    
     DETAILED DESCRIPTION 
       [0021]    Where reference is made in any one or more of the accompanying drawings to steps and/or features, which have the same reference numerals, those steps and/or features have for the purposes of this description the same function(s) or operation(s), unless the contrary intention appears. 
         [0022]      FIG. 1  is a block diagram showing a limited feedback MIMO wireless communication system  100  on which the embodiments of the present invention may be practiced. The system  100  comprises a transmitter  110 , which transmits data symbols wirelessly over a narrow-band channel  125  through N T  transmit antennas  120 - 1  to  120 -N T . The data symbols are received by a receiver  130  through N R  receive antennas  140 - 1  to  140 -N R . The system  100  also comprises a low-rate feedback link  150  (indicated by a broken line) through which the receiver sends state information about the channel  125  to the transmitter  110 . The transmitter  110  uses the state information to maximise the performance of the transmission to the receiver  130 . 
         [0023]    Since the channel  125  is narrow-band, a complex transmitted symbol x is transformed to a complex received symbol y as follows: 
         [0000]        y=z   T   Hwx+z   T   n,   (1)
 
         [0024]    where w is the unit magnitude complex beamforming vector (of length N T ) applied at the transmitter  110 , H is a N R -by-N T  complex-valued matrix representing the effect of the channel  125 , z is the unit magnitude complex combining vector (of length N R ) applied at the receiver  130 , and n is the complex noise vector (of length N R ) at the receiver  130 . Assuming the noise is independent, identically distributed (i.i.d), circularly symmetric complex Gaussian with variance N 0 , the signal-to-noise ratio (SNR) ρ at the receiver  130  is given by: 
         [0000]    
       
         
           
             
               
                 
                   
                     ρ 
                     = 
                     
                       
                         
                           E 
                           x 
                         
                          
                         
                           Γ 
                            
                           
                             ( 
                             H 
                             ) 
                           
                         
                       
                       
                         N 
                         0 
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
           
         
       
     
         [0025]    where E x  is the average transmitted symbol power and 
         [0000]      Γ( H )=| z   T   Hw|   2   (3)
 
         [0026]    is the effective channel gain. 
         [0027]    Given w and H, the (unit magnitude) combining vector z that maximises the received SNR is given by the Maximum Ratio Combining (MRC) formula: 
         [0000]    
       
         
           
             
               
                 
                   
                     z 
                     MRC 
                   
                   = 
                   
                     
                       Hw 
                       
                          
                         Hw 
                          
                       
                     
                     . 
                   
                 
               
               
                 
                   ( 
                   4 
                   ) 
                 
               
             
           
         
       
     
         [0028]    From equation (3), the resulting effective channel gain (the MRC gain) is: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       Γ 
                       MRC 
                     
                      
                     
                       ( 
                       H 
                       ) 
                     
                   
                   = 
                   
                     
                       
                          
                         Hw 
                          
                       
                       2 
                     
                     . 
                   
                 
               
               
                 
                   ( 
                   5 
                   ) 
                 
               
             
           
         
       
     
         [0029]    The optimal infinite-precision (unquantized) beamforming vector w opt  that maximises the MRC gain is given by the right-singular unit vector of H corresponding to the largest singular value of H. The beamforming scheme utilising w opt  is known as maximum ratio transmission (MRT). The effective channel gain when using MRT and MRC is denoted Γ MRT,MRC (H) and is given by the square of the largest singular value of H. 
         [0030]    In the limited feedback system  100  of  FIG. 1 , the receiver  130  and the transmitter  110  share a codebook C of possible beamforming vectors, which are indexed by ceil(log 2 (|C|)) bits. The optimal quantized beamforming vector ŵ opt  in the codebook C may be computed as: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       w 
                       ^ 
                     
                     opt 
                   
                   = 
                   
                     
                       argmax 
                       
                         v 
                         ∈ 
                         C 
                       
                     
                      
                     
                       
                         
                           
                              
                             Hv 
                              
                           
                           2 
                         
                         
                           
                              
                             v 
                              
                           
                           2 
                         
                       
                       . 
                     
                   
                 
               
               
                 
                   ( 
                   6 
                   ) 
                 
               
             
           
         
       
     
         [0031]    The denominator is present in equation (6) to ensure the average transmitted signal power E x  is constant. 
         [0032]    Because in general ŵ opt ≠w opt , the effective channel gain using ŵ opt  (computable using equation (5)) is less than the MRC-MRT gain Γ MRT,MRC (H), by an amount depending on the granularity or quantization step size of the codebook C. The design of the codebook C is therefore critical for the performance of the system  100 . 
         [0033]      FIG. 3  is a flowchart illustrating a method  300  of limited feedback wireless communication carried out by the system  100  of  FIG. 1 . The steps on the left of the dotted line  305  are carried out by the receiver  130 , while the steps on the right are carried out by the transmitter  110 . The method  300  starts at the step  310 , where the receiver  130  estimates the channel matrix H using known methods, for example from the characteristics of a known training sequence transmitted by the transmitter  110 . In step  320 , the receiver  130  computes the optimal (unquantized) beamforming vector w opt . This is done using the singular value decomposition of the channel matrix H as described above. In the next step  330 , the receiver  130  finds the index bits encoding the optimal beamforming vector w opt , as described in more detail below. Step  330  involves quantization of w opt  and indexing of the quantized vector. Next, the receiver  130  in step  340  transmits the index bits to the transmitter  110  (indicated in  FIG. 3  by the broken line arrow from the receiver side to the transmitter side) over the feedback link  150  of  FIG. 1  (which is assumed to be error-free). At step  350  the receiver  130  computes the (unit magnitude) MRC combining vector z MRC  from the channel H and the optimal quantized beamforming vector using equation (4). Meanwhile, the transmitter  110  receives at step  360  the index bits from the receiver  130  over the feedback link  150 . In step  370 , the transmitter  110  decodes the index bits to find the optimal quantized beamforming vector, which the transmitter  110  normalises to unit magnitude. In steps  380  and  390 , the transmitter  110  and the receiver  130  apply the normalised beamforming vector and the combining vector z MRC  to transmitted and received data symbols respectively. 
         [0034]    The channel  125  could be one of the subchannels in a wideband (e.g. Orthogonal Frequency Division Multiplexing, or OFDM) system, such as 3G LTE and 802.11a/g WLAN. In such a case, the method  300  could be performed independently for each subchannel of the OFDM channel, or could be performed for only a subset of the OFDM subchannels, and the resulting beamforming and combining vectors could be used to transmit and receive symbols in the respective neighbouring OFDM subchannels. 
       Design of the Reflected Simplex Codebook 
       [0035]    One known codebook uses square lattice angular quantization (SLAQ) to reduce both the search and storage complexity of limited feedback MIMO systems. In SLAQ, the components of codebook vectors are complex integers and can be considered as points of a Quadrature Amplitude Modulation (QAM) constellation. As in QAM, SLAQ codebooks have simple bit-to-symbol indexing algorithms, so codebook storage is not required at either the transmitter or receiver. The problem of searching SLAQ codebooks to estimate the optimal quantized beamforming vector is similar to the problem of noncoherent sequence detection, and fast noncoherent sequence detection algorithms can be utilized to achieve reduction in search complexity orders of magnitude smaller than an exhaustive search. Significantly, the SNR performance of SLAQ codebooks is similar to that of conventional (RVQ) codebooks for the same number of feedback bits, but with much lower computational complexity. 
         [0036]    Like SLAQ codebooks, Reflected Simplex codebooks adhere to a geometrically regular construction. Reflected Simplex codebook construction is based on a codebook known as Pyramid Vector Quantization (PVQ) that has been used in the context of audio quantization, as part of a very low-delay high-quality speech and audio codec. A Reflected Simplex codebook consists of complex integer vectors mapped from real integer vectors that lie on the original and reflected images about the axes of a (2N T −1)-dimensional simplex. Reflected Simplex codebooks can be indexed with low time and storage requirements and efficiently searched to estimate the optimal quantized beamforming vector, as described below. 
         [0037]    A PVQ codebook D(N,K) consists of real integer vectors of length N, where K is a parameter that determines the granularity or coarseness of the quantization. The PVQ codebook D(N,K) is constructed from a base set of all real integer vectors that lie on a segment of the hyperplane {Ke 1 ; . . . ; Ke N } that is bounded by the convex hull of the vectors Ke i  (the vectors e 1  are the columns of the N by N identity matrix I N ). The hyperplane segment is an (N−1)-simplex. The parameter K is the height of the simplex, and the length of its edges is K√{square root over (2)}. Note that a 1-simplex is a line segment, a 2-simplex is an equilateral triangle, and a 3-simplex is a regular tetrahedron. 
         [0038]    More precisely, the base set is defined by: 
         [0000]    
       
         
           
             
               
                 
                   
                     { 
                     
                       
                         
                           v 
                           ∈ 
                           
                             
                               Z 
                               N 
                             
                              
                             
                               : 
                             
                              
                             
                               
                                 
                                   
                                       
                                   
                                   ∑ 
                                 
                                 
                                   i 
                                   = 
                                   1 
                                 
                                 N 
                               
                                
                               
                                 v 
                                 t 
                               
                             
                           
                         
                         = 
                         K 
                       
                       , 
                       
                         
                           v 
                           t 
                         
                         ≥ 
                         0 
                       
                     
                     } 
                   
                   . 
                 
               
               
                 
                   ( 
                   7 
                   ) 
                 
               
             
           
         
       
     
         [0039]    In addition, the codebook D(N,K) contains all of the 2 N −1 images obtained by reflecting the set (7) about the N axes of R N . The codebook D(N,K) is therefore defined by 
         [0000]    
       
         
           
             
               
                 
                   
                     D 
                      
                     
                       ( 
                       
                         N 
                         , 
                         K 
                       
                       ) 
                     
                   
                   = 
                   
                     { 
                     
                       
                         v 
                         ∈ 
                         
                           
                             Z 
                             N 
                           
                            
                           
                             : 
                           
                            
                           
                             
                               
                                 
                                     
                                 
                                 ∑ 
                               
                               
                                 
                                     
                                 
                                  
                                 
                                   i 
                                   = 
                                   1 
                                 
                               
                               
                                 
                                     
                                 
                                  
                                 N 
                               
                             
                              
                             
                                
                               
                                 v 
                                 t 
                               
                                
                             
                           
                         
                       
                       = 
                       K 
                     
                     } 
                   
                 
               
               
                 
                   ( 
                   8 
                   ) 
                 
               
             
           
         
       
     
         [0040]      FIG. 2  is a plot  200  of the vectors in the PVQ codebook D(N,K), with N=2 and K=2. The vectors  210  and  220  are the vectors Ke 1  and Ke 2 . The hyperplane segment  230  is the 1-simplex. The points (2, 0)  240 , (1, 1)  250 , and (0, 2)  260  make up the base set (7). 
         [0041]    The reflections  270 ,  280 , and  290  of the base set {(2, 0), (1, 1), (0, 2)} about the two axes complete the PVQ codebook D(2, 2). 
         [0042]    The number of codewords (vectors) in the codebook D(N,K) is denoted as V(N,K). It can be shown that: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       V 
                        
                       
                         ( 
                         
                           N 
                           , 
                           K 
                         
                         ) 
                       
                     
                     = 
                     
                       
                         ∑ 
                         
                           L 
                           = 
                           0 
                         
                         
                           min 
                           ( 
                           
                             N 
                             , 
                             K 
                           
                           ) 
                         
                       
                        
                       
                         
                           2 
                           L 
                         
                          
                         
                           ( 
                           
                             
                               
                                 N 
                               
                             
                             
                               
                                 L 
                               
                             
                           
                           ) 
                         
                          
                         
                           ( 
                           
                             
                               
                                 
                                   K 
                                   - 
                                   1 
                                 
                               
                             
                             
                               
                                 
                                   L 
                                   - 
                                   1 
                                 
                               
                             
                           
                           ) 
                         
                       
                     
                   
                   , 
                   
                       
                   
                    
                   
                     = 
                     
                       2 
                        
                       
                         N 
                         2 
                       
                        
                       
                         
                           F 
                           1 
                         
                          
                         
                           ( 
                           
                             
                               1 
                               - 
                               K 
                             
                             , 
                             
                               
                                 1 
                                 - 
                                 N 
                               
                               ; 
                               2 
                               ; 
                               2 
                             
                           
                           ) 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   9 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where  2 F 1  is Gauss&#39; hypergeometric function. V(N,K) can also be computed using the following recurrence relation: 
         [0000]        V ( N,K )= V ( N,K− 1)+ V ( K,N− 1)+ V ( N− 1, K− 1)  (10)
 
         [0000]    with V(1,K)=2 for all K and V(N,1)=2N. The recurrence relation of equation (10) provides a O(NK) method for computationally efficient calculation of V(N,K) by storing the intermediate values in matrix form, avoiding the multiplications or the complexity of evaluating the hypergeometric function in equation (9). The total number of bits required to transmit a vector in the PVQ codebook is given by ceil(log 2 (V(N,K)). 
         [0043]    For the case of low-rate quantization, i.e. N&gt;&gt;K, it can be shown that 
         [0000]      log 2   V ( N,K )→ K  log 2 (2 N )−log 2    K!,   (11)
 
         [0044]    while for the case of high-rate quantization, i.e. K&gt;&gt;N, 
         [0000]      log 2    V ( N,K )→( N− 1)log 2 (2( K− 1))+1−log 2 ( N− 1)!.  (12)
 
         [0000]      More generally, 
         [0000]      log 2 V(N,K)≈(N−1)log 2 (2(K−1))−log 2 (N−1)!.  (13)
 
         [0045]    In what follows, the underline notation denotes a bidirectional mapping between a complex vector u of length N T  and a real-valued vector  u  of length N=2 N T  defined as follows: 
         [0000]        u   2t-1 =         {u t }, u   2t =ℑ{u t   },t= 1, . . . , N T   (14)
 
         [0046]    The PVQ codebook is modified to form the Reflected Simplex codebook as follows. First, construct a modified PVQ codebook C R (N T , K) of real integer vectors from the PVQ codebook D(N,K) as follows: 
         [0000]        C   R ( N   T   ,K )={   v εD ( N,K ), ν   2r-1 &gt;0, ν   2r ≧0},  (15)
 
         [0047]    where r=ceil(l/2), and l is the index of the first nonzero component of  v . 
         [0048]    A Reflected Simplex codebook C(N T , K) is constructed as complex vectors of length N T , derived from the real vectors in C R (N T , K) using the mapping in equation (14): 
         [0000]        C ( N   T   K )={ v: v εC   R ( N   T   ,K )}  (16)
 
         [0049]    The effect of the condition  ν   2r-1 &gt;0, ν   2r ≧0 in the definition of C R (N T , K) (equation (15)) is to remove from C(N T , K) complex vectors that are phase ambiguous. For example, the effect of the condition on C R (1, 2) is to leave only the first quadrant vectors in D(2,2), namely (2,0) and (1,1) (see  FIG. 2 ). Two complex vectors v 1 , v 2  are phase ambiguous if there exists a complex scalar γ of unit modulus such that v 1 =γv 2 . This relation implies that the channel gain (see equation (5)) is the same for both vectors, so one of the vectors is redundant. 
         [0050]    If the condition  ν   2r-1 &gt;0, ν   2r ≧0 were not applied to modify the PVQ codebook, for every v in the Reflected Simplex codebook, there would also be three phase ambiguous vectors −v, jv and −jv. On removing these redundant vectors, the size of the Reflected Simplex codebook becomes V(N, K)/4, and thus the number of bits required to encode the Reflected Simplex codebook is ceil(log 2 (V(N,K))−2. This saving of 2 feedback bits is a significant amount for small codebooks suited to limited feedback beamforming. 
         [0051]      FIG. 7  is a flowchart illustrating a method  700  of encoding a real vector of length N to index bits. The method  700  is used at step  330  of the method  300 , with its input vector being the real-valued mapping  w   opt  according to (14) of the optimal beamforming vector w opt  computed at step  320 . The method  700  starts at step  710  where the input vector is quantized to the Reflected Simplex codebook C(N T , K), where N T  is N/2, i.e. half the length of the real input vector, and K is the granularity parameter. The step  710 , described in more detail below, may alternatively be termed locating the quantized version of an input vector in the Reflected Simplex codebook C(N T , K). The result is a complex vector from the codebook C(N T , K). At the next step  720 , the method  700  indexes the complex codebook vector to obtain one or more index bits as described in detail below. The method  700  then concludes. 
       Indexing the Reflected Simplex Codebook 
       [0052]      FIG. 4  is a flowchart illustrates a method  400  of obtaining an index for a complex vector v in the Reflected Simplex codebook C(N T , K), carried out by the receiver  130  at step  720  of the method  700  of  FIG. 7  when invoked at step  330  of the method  300  of  FIG. 3 . The indexing method  400  is based on the indexing of the PVQ codebook D(N,K), and has a complexity of O(NK), mostly avoiding multiplications and divisions (although some operations involve division or multiplication by two, which can be implemented using less complex bit shift operations). 
         [0053]    The method  400  begins at decision step  410  where a check is made to determine whether N T =0. If so (Yes), the method  400  at step  420  returns an index of zero. If not (No), the method  400  proceeds to step  430 , where the components ν t  of v are examined in order of ascending t. The value of t is set to the index of the first non-zero component ν t . The value of t indexes a disjoint partition I t  of the codebook C(N T , K) in which v lies. The partition I t  is in turn made up of K(K+1)/2 disjoint subsets I r,t , where all the vectors v in I r,t  have the same, unique (non-zero) value of ν t , namely ν r . The subsets I r,t  of I t  are ordered according to their common ν t  values according to the zigzag pattern illustrated in  FIG. 5 . That is, L l,t  contains all the vectors v in I t  with ν t =1+0j, while I 2,t  contains all the vectors v in I t  with ν t =1+1j, and so on. 
         [0054]    The size of the subset I r,t  is given by 
         [0000]    
       
         
           
             
               
                 
                   
                      
                     
                       I 
                       
                         r 
                         , 
                         t 
                       
                     
                      
                   
                   = 
                   
                     
                       V 
                        
                       
                         ( 
                         
                           
                             2 
                              
                             
                               ( 
                               
                                 
                                   N 
                                   T 
                                 
                                 - 
                                 t 
                                 + 
                                 1 
                               
                               ) 
                             
                           
                           , 
                           
                             K 
                             - 
                             
                               ⌈ 
                               
                                 
                                   
                                     1 
                                     2 
                                   
                                    
                                   
                                     
                                       
                                         8 
                                          
                                         r 
                                       
                                       + 
                                       1 
                                     
                                   
                                 
                                 - 
                                 1 
                               
                               ⌉ 
                             
                           
                         
                         ) 
                       
                     
                     . 
                   
                 
               
               
                 
                   ( 
                   17 
                   ) 
                 
               
             
           
         
       
     
         [0055]    At step  440  the index c is set to the sum of the sizes of each partition I q  for q=1, . . . t−1, which is given by: 
         [0000]    
       
         
           
             
               
                 
                   c 
                   = 
                   
                     
                       
                         ∑ 
                         
                           q 
                           = 
                           1 
                         
                         
                           t 
                           - 
                           1 
                         
                       
                        
                       
                          
                         
                           I 
                           q 
                         
                          
                       
                     
                     = 
                     
                       
                         ∑ 
                         
                           q 
                           = 
                           1 
                         
                         
                           t 
                           - 
                           1 
                         
                       
                        
                       
                         
                           ∑ 
                           
                             r 
                             = 
                             1 
                           
                           
                             
                               K 
                                
                               
                                 ( 
                                 
                                   K 
                                   + 
                                   1 
                                 
                                 ) 
                               
                             
                             / 
                             2 
                           
                         
                          
                         
                           
                              
                             
                               I 
                               
                                 r 
                                 , 
                                 t 
                               
                             
                              
                           
                           . 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   18 
                   ) 
                 
               
             
           
         
       
     
         [0056]    To identify the ordinate l of the subset I l,t  of I t  within which v lies, the method  400  at step  450  sets 
         [0000]        K   l =         (ν t )+ℑ(ν t )−1.  (19)
 
         [0057]    The method  400  at step  460  then sets/to: 
         [0000]    
       
         
           
             
               
                 
                   l 
                   = 
                   
                     
                       
                         
                           K 
                           l 
                         
                          
                         
                           ( 
                           
                             
                               K 
                               l 
                             
                             + 
                             1 
                           
                           ) 
                         
                       
                       2 
                     
                     + 
                     
                       
                          
                          
                         
                           ( 
                           
                             v 
                             t 
                           
                           ) 
                         
                       
                       . 
                     
                   
                 
               
               
                 
                   ( 
                   20 
                   ) 
                 
               
             
           
         
       
     
         [0058]    In step  470 , the method  400  increments the index c by the sum of the sizes of each subset I r,t  for r=1 to l−1 using equation (17) for |I r,t |. In step  480 , the method  400  increments the index c. This is done by recursively invoking the method  400  on the new vector v′ that is obtained from v by removing the components ν q  for q=1 to t, also reducing N T  by t and K by K l , and adding the result to the index c. The method  400  returns the value of c at step  490 . 
         [0059]    The method for decoding the index bits to a beamforming vector in C(N T , K), carried out by the transmitter  110  in the step  370  of the method  300  is a straightforward inversion of the indexing method  400 . The resulting decoding method also has a complexity of O(NK). 
         [0060]    Another form of redundancy arises in the Reflected Simplex codebook between a pair of codebook vectors related by v 1 =γv 2  for |γ|≠1, referred to as a divisor ambiguity. Beamforming vectors with divisor ambiguity yield the same effective channel gain (equation (5)) after normalisation to unit magnitude. For example, if N=2N T =4 and K=4, the vectors [2+j0 2+j0] and [1+j1 1+j1] exhibit divisor ambiguity, with γ=1−j. The simplex-based domain of the PVQ codebook allows calculation of the number of redundant vectors in the Reflected Simplex codebook due to divisor ambiguities. First, divisor ambiguities only occur if K is even. Secondly, if K is even, divisor ambiguity only occurs when γ=±1±j, μ t =±a±ja; and ν t =±2a±j2a for all t=1, . . . N. Finally, the number of redundant vectors due to divisor ambiguity is upper bounded by 
         [0000]    
       
         
           
             
               
                 
                   
                     ∑ 
                     
                       L 
                       = 
                       0 
                     
                     
                       min 
                        
                       
                         ( 
                         
                           
                             N 
                             T 
                           
                           , 
                           
                             K 
                             / 
                             2 
                           
                         
                         ) 
                       
                     
                   
                    
                   
                     
                       4 
                       L 
                     
                      
                     
                       ( 
                       
                         
                           
                             
                               N 
                               T 
                             
                           
                         
                         
                           
                             L 
                           
                         
                       
                       ) 
                     
                      
                     
                       
                         ( 
                         
                           
                             
                               
                                 
                                   K 
                                   2 
                                 
                                 - 
                                 1 
                               
                             
                           
                           
                             
                               
                                 L 
                                 - 
                                 1 
                               
                             
                           
                         
                         ) 
                       
                       . 
                     
                   
                 
               
               
                 
                   ( 
                   21 
                   ) 
                 
               
             
           
         
       
     
         [0061]    This formula may be applied to calculate the number of bits required to index the Reflected Simplex codebook with divisor ambiguities removed. For a large range of N and K, there is no (N, K) pair where removing divisor ambiguities would reduce the integer number of bits. However, for some small K values, a small fraction of a bit is saved, which may provide some efficiencies when a number of vectors are encoded together. A consequence would be more complex index encoding and decoding methods than those described above with reference to  FIG. 4 , but for small codebooks a lookup table may be used rather than indexing methods. 
       Searching the Reflected Simplex Codebook 
       [0062]    The method performed by the receiver  130  in step  710  of the method  700 , when invoked at step  330  of the method  300 , to locate the optimal quantized beamforming vector in the Reflected Simplex codebook is described hereinafter. A simple exhaustive search over the entire Reflected Simplex codebook can be carried out as in equation (6), but this is prohibitively expensive in terms of computation. Instead, the locating is performed with complexity O(N T  logN T ) by observing an equivalence with noncoherent sequence detection. 
         [0063]    For the case N R ≦2, the exhaustive codebook search of equation (6) is equivalent to finding the closest codebook vector in angle to the optimal unquantized beamforming vector w opt : 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         
                           w 
                           ^ 
                         
                         opt 
                       
                       = 
                       
                         
                           
                             arg 
                              
                             
                                 
                             
                              
                             max 
                           
                           
                             v 
                             ∈ 
                             
                               C 
                                
                               
                                 ( 
                                 
                                   
                                     N 
                                     T 
                                   
                                   , 
                                   K 
                                 
                                 ) 
                               
                             
                           
                         
                          
                         
                           cos 
                           2 
                         
                          
                         
                           ϑ 
                            
                           
                             ( 
                             
                               v 
                               , 
                               
                                 w 
                                 opt 
                               
                             
                             ) 
                           
                         
                       
                     
                     , 
                     
                       
 
                     
                      
                     where 
                   
                    
                   
                     
 
                   
                    
                   
                     
                       
                         
                           cos 
                           2 
                         
                          
                         
                           ϑ 
                            
                           
                             ( 
                             
                               v 
                               , 
                               u 
                             
                             ) 
                           
                         
                       
                       = 
                       
                         
                           
                              
                             
                               
                                 v 
                                 T 
                               
                                
                               u 
                             
                              
                           
                           2 
                         
                         
                           
                             
                                
                               v 
                                
                             
                             2 
                           
                            
                           
                             
                                
                               u 
                                
                             
                             2 
                           
                         
                       
                     
                     , 
                   
                 
               
               
                 
                   ( 
                   22 
                   ) 
                 
               
             
           
         
       
     
         [0064]    When N R &gt;2, equation (22) is also a good first-order approximation. Equation (22) is denoted singular vector quantization (SVQ), because equation (22) is equivalent to quantizing w opt  (the right-singular unit vector associated with the largest singular value of the channel matrix H) using an angular metric. 
         [0065]    An equivalence relationship exists between SVQ using an angular metric (equation (22)) and the problem of sequence detection over unknown deterministic flat-fading channels. The equivalence can be seen by noting that equation (22) is equivalent to noncoherent detection using the generalized likelihood ratio test (GLRT). Specifically, consider the detection of a complex input vector x, drawn in an i.i.d. manner from a discrete constellation X, given an output vector y: 
         [0000]        y=hx+n,   (23)
 
         [0066]    where n is a vector of i.i.d. white Gaussian noise and h is an unknown complex channel parameter assumed constant over the period of the input vector x. The GLRT-optimal estimate {circumflex over (x)} GLRT  of the input vector x is obtained from the received data y by solving 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         x 
                         ^ 
                       
                       GLRT 
                     
                     = 
                     
                       
                         
                           arg 
                            
                           
                               
                           
                            
                           min 
                         
                         
                           x 
                           ∈ 
                           X 
                         
                       
                        
                       
                         
                           min 
                           h 
                         
                          
                         
                           
                              
                             
                               y 
                               - 
                               hx 
                             
                              
                           
                           2 
                         
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   24 
                   ) 
                 
               
             
           
         
       
     
         [0067]    which becomes, on setting λ=h −1 , 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       x 
                       ^ 
                     
                     GLRT 
                   
                   = 
                   
                     
                       
                         arg 
                          
                         
                             
                         
                          
                         min 
                       
                       
                         x 
                         ∈ 
                         X 
                       
                     
                      
                     
                       
                         min 
                         λ 
                       
                        
                       
                         
                           1 
                           
                             
                                
                               λ 
                                
                             
                             2 
                           
                         
                          
                         
                           
                             
                                
                               
                                 
                                   λ 
                                    
                                   
                                       
                                   
                                    
                                   y 
                                 
                                 - 
                                 x 
                               
                                
                             
                             2 
                           
                           . 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   25 
                   ) 
                 
               
             
           
         
       
     
         [0068]    Algorithms are known for computing {circumflex over (x)} GLRT  according to equation (25) for any λ over specific constellations X efficiently, i.e. in polynomial time. 
         [0069]    To show the equivalence to equation (22), consider the real-valued mapping  w   opt  according to (14) of the optimal beamforming vector w opt . Denote  z  as the vector in the direction of  w   opt  such that the sum of the absolute values of the components of  z  is K, i.e. 
         [0000]    
       
         
           
             
               
                 
                   
                     z 
                     _ 
                   
                   = 
                   
                     
                       
                         K 
                          
                         
                           
                             w 
                             _ 
                           
                           opt 
                         
                       
                       
                         
                           ∑ 
                           
                             n 
                             = 
                             I 
                           
                           N 
                         
                          
                         
                            
                           
                             
                               w 
                               _ 
                             
                             n 
                             opt 
                           
                            
                         
                       
                     
                     . 
                   
                 
               
               
                 
                   ( 
                   26 
                   ) 
                 
               
             
           
         
       
     
         [0070]    In other words,  z  is the projection of  w   opt  onto the reflected simplex that is the domain of C R (N T , K). 
         [0071]    Instead of performing the SVQ of equation (22), the following equivalent search is performed: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         w 
                         _ 
                         ^ 
                       
                       opt 
                     
                     = 
                     
                       
                         
                           arg 
                            
                           
                               
                           
                            
                           min 
                         
                         
                           
                             v 
                             _ 
                           
                           ∈ 
                           
                             
                               C 
                               R 
                             
                              
                             
                               ( 
                               
                                 N 
                                 , 
                                 K 
                               
                               ) 
                             
                           
                         
                       
                        
                       
                         
                            
                           
                             
                               z 
                               _ 
                             
                             - 
                             
                               v 
                               _ 
                             
                           
                            
                         
                         2 
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   27 
                   ) 
                 
               
             
           
         
       
     
         [0072]    which in turn is equivalent to the GLRT estimation of equation (25), with 
         [0000]    
       
         
           
             λ 
             = 
             
               K 
               
                 
                   ∑ 
                   
                     n 
                     = 
                     I 
                   
                   N 
                 
                  
                 
                    
                   
                     
                       w 
                       _ 
                     
                     n 
                     opt 
                   
                    
                 
               
             
           
         
       
     
         [0073]    and X=C R (N T , K). 
         [0074]    Without loss of generality, all the components of  z  may be converted to be non-negative. That is, assign 
         [0000]        z   + = s ∘ z   (28)
 
         [0000]    where  s   n =sgn( z   n ) for all n and o denotes the Hadamard product. In other words,  z   +  is the reflection of  z  onto the simplex on which C R (N T , K) is based, i.e. the hyperplane segment defined by 
         [0000]    
       
         
           
             
               { 
               
                 
                   
                     u 
                     ∷ 
                     
                       
                         ∑ 
                         
                           n 
                           = 
                           I 
                         
                         N 
                       
                        
                       
                         u 
                         n 
                       
                     
                   
                   = 
                   K 
                 
                 , 
                 
                     
                 
                  
                 
                   
                     u 
                     n 
                   
                   ≥ 
                   0 
                 
               
               } 
             
             . 
           
         
       
     
         [0075]    All the codebook vectors in C R (N T , K) with non-negative components exist on this simplex. The non-negative portion of the codebook C R (N T , K) is a subset of a translated A N-1  lattice, which is defined as: 
         [0000]    
       
         
           
             
               A 
               
                 N 
                 - 
                 1 
               
             
             = 
             
               
                 { 
                 
                   
                     
                       a 
                       _ 
                     
                     ∷ 
                     
                       
                         a 
                         _ 
                       
                       ∈ 
                       
                         Z 
                         N 
                       
                     
                   
                   , 
                   
                       
                   
                    
                   
                     
                       
                         ∑ 
                         
                           n 
                           = 
                           1 
                         
                         N 
                       
                        
                       
                         
                           a 
                           _ 
                         
                         n 
                       
                     
                     = 
                     0 
                   
                 
                 } 
               
               . 
             
           
         
       
     
         [0076]    In other words, if  v εC R (N,K), then  v   + −Ke 1 εA N-1 . The codebook search of equation (27) is therefore equivalent to 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       w 
                       _ 
                       ^ 
                     
                     opt 
                   
                   = 
                   
                     
                       
                         
                           s 
                           _ 
                         
                         ∘ 
                         
                           
                             arg 
                              
                             
                                 
                             
                              
                             min 
                           
                           
                             
                               a 
                               _ 
                             
                             ∈ 
                             
                               A 
                               
                                 N 
                                 - 
                                 1 
                               
                             
                           
                         
                       
                        
                       
                         
                            
                           
                             
                               ( 
                               
                                 
                                   
                                     z 
                                     _ 
                                   
                                   + 
                                 
                                 - 
                                 
                                   K 
                                    
                                   
                                       
                                   
                                    
                                   
                                     e 
                                     1 
                                   
                                 
                               
                               ) 
                             
                             - 
                             
                               a 
                               _ 
                             
                           
                            
                         
                         2 
                       
                     
                     + 
                     
                       K 
                        
                       
                           
                       
                        
                       
                         
                           e 
                           1 
                         
                         . 
                       
                     
                   
                 
               
               
                 
                   ( 
                   29 
                   ) 
                 
               
             
           
         
       
     
         [0077]    Equation (29) corresponds to a search for the closest point in Euclidean distance to the vector  z   + −Ke 1  over the lattice A N-1 . A method described below with a complexity of O(N log N) for performing the search of equation (29) over the lattice A N-1  is used. The resulting real vector  ŵ   opt  is mapped using equation (14) to become the optimal quantized beamforming vector ŵ opt . 
         [0078]      FIG. 6  is a flowchart illustrating a method  600  of searching the Reflected Simplex codebook to locate the optimal quantized beamforming vector from the optimal beamforming vector w opt , as used in step  710  of the method  700  of  FIG. 7  when invoked at step  330  of the method  300  of  FIG. 3 . The method  600  begins at step  605 , where the real vector  w   opt  is projected onto the reflected simplex using equation (26) to form a projection  z . At step  610 , the projection  z  is reflected onto the non-negative portion of the reflected simplex using equation (28) to form the vector  z   + . At the next step  615 , the sum s of the components of  z   + −Ke 1  is computed, and a new vector  z ′ is computed as: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       z 
                       _ 
                     
                     ′ 
                   
                   = 
                   
                     
                       ( 
                       
                         
                           
                             z 
                             _ 
                           
                           + 
                         
                         - 
                         
                           K 
                            
                           
                               
                           
                            
                           
                             e 
                             1 
                           
                         
                       
                       ) 
                     
                     - 
                     
                       
                         
                           s 
                           N 
                         
                          
                         
                           [ 
                           
                             
                               
                                 1 
                               
                               
                                 … 
                               
                               
                                 1 
                               
                             
                           
                           ] 
                         
                       
                       T 
                     
                   
                 
               
               
                 
                   ( 
                   30 
                   ) 
                 
               
             
           
         
       
     
         [0079]    At the next step  620 , the vector  z ′ is rounded to the integer vector  f , and the components of  f  are summed to form the integer variable Δ. At the following step  630 , the method  600  computes the difference vector d between  z ′ and its rounded version  f . A vector t of indices in the range {1, . . . N} is then formed from d such that t n  is the index of the n-th most positive component of d. 
         [0080]    The method  600  then at step  640  determines whether Δ&gt;0. If so, step  650  decrements by 1 all the components of  f  indexed by t n , for n=1 to Δ. (These are the indices of the Δ most positive differences between  z ′ and its integer rounded version  f .) If not, step  660  increments by 1 all the components of  f  indexed by t n , for n=N+Δ+1 to N. (These are the indices of the −Δ most negative differences between  z ′ and its integer rounded version  f .) After both steps  650  and  660 , the method  600  returns the complex mapping f of the updated vector  f  at step  670 . 
         [0081]    An alternative embodiment of step  710  is to perform the method  600  a number (L) of times for different rotations of the vector w opt . The values of the rotations correspond to phase rotations uniformly spaced between 0 and π/2. This is achieved by performing the method  600  L times, on w opt   l , for l=0, . . . L−1, where: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       w 
                       opt 
                       l 
                     
                     = 
                     
                       
                         w 
                         opt 
                       
                        
                       
                         exp 
                         ( 
                         
                           
                             jπ 
                              
                             
                                 
                             
                              
                             l 
                           
                           
                             2 
                              
                             L 
                           
                         
                         ) 
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   31 
                   ) 
                 
               
             
           
         
       
     
         [0082]    The result is L candidate beamforming vectors ŵ opt   l . The candidate beamforming vector that maximises the metric in equation (6) is then chosen for indexing. 
         [0083]    In addition to its application in beamforming for MIMO systems, the encoding method  700  may also be applied to any system where a vector needs to be efficiently encoded in a low number of bits. The method  700 , for a general input vector, may include the preliminary step of normalizing the vector to be of unit magnitude. The scaling factor is scalar quantized and encoded separately. If the input vector is complex, the mapping of equation (14) should be applied first. 
         [0084]    Particular examples include point-to-point precoding such as unitary, linear, and SVD precoding for MIMO systems, where the rows or columns of the channel matrix or precoding matrix need to be sent to the transmitter. Other example systems include multi-user precoding such as zero forcing beamforming and vector perturbation precoding, where the channel vectors for each user need to be sent to the transmitter. 
         [0085]    The transmitter  110  and receiver  130  are preferably implemented in dedicated hardware or modules such as embedded integrated circuits performing the functions or sub functions of  FIGS. 3 ,  4 ,  6 , and  7 , e.g. a PHY/MAC layer chip, or part of a transmitter or receiver chip. The receiver could be a 3G or 4G cellular handset or enabled PC, or a WLAN enabled handset or PC. Such modules may also comprise graphic processors, digital signal processors, or microprocessors and associated memories. 
         [0086]    The arrangements described are applicable to the wireless communication industries. 
         [0087]    The foregoing describes only some embodiments of the present invention, and modifications and/or changes can be made thereto without departing from the scope and spirit of the invention, the embodiments being illustrative and not restrictive.