Abstract:
Embodiments of the invention provide a method of decoding of hexagonal constellations. The decoding methods exploit the inherent structure of the hexagonal grid to eliminate/minimize the requirements for distance computations. A constellation which has unused constellation points is received. A plurality of lookup tables is used for indicating whether a particular constellation point is used. The lookup tables are indexed using the two integers u and v. An initial estimate ū and  v  is found. The euclidean distance to the immediate neighbors resulting in the immediate upper and lower integers for ū and  v  is computed. From the distance to the nearest neighbor, the log-likelihood ratio value is computed.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
       [0001]    This application claims priority to U.S. Provisional Application 61/712,077 filed Oct. 10, 2012. Said application incorporated herein by reference 
     
    
     STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT 
       [0002]    Not applicable. 
       BACKGROUND 
       [0003]    Embodiments of the invention are directed, in general, to communication systems and, more specifically, decoding hexagonal constellations. 
     
    
     
       BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWING 
         [0004]      FIG. 1  is a diagram of an example of codeword assignment for constellation order 32-HEX. 
           [0005]      FIG. 2A  is a diagram showing 16-HEX constellation. 
           [0006]      FIG. 2B  is a diagram of an example of codeword assignment for constellation order 16-HEX as shown in  FIG. 2A . 
           [0007]      FIG. 3  is a diagram showing original and punctured 128-HEX constellations with 20 punctured constellation points. 
           [0008]      FIG. 4  is an electrical diagram, in block form, of the construction of an implementation of a receiver system. 
       
    
    
     DETAILED DESCRIPTION 
       [0009]    The invention now will be described more fully hereinafter with reference to the accompanying drawings. This invention may, however, be embodied in many different forms and should not be construed as limited to the embodiments set forth herein. Rather, these embodiments are provided so that this disclosure will be thorough and complete, and will fully convey the scope of the invention to those skilled in the art. One skilled in the art may be able to use the various embodiments of the invention. 
         [0010]    The decoding of hexagonal constellations is done over the two-dimensional grids (rather than two distinct 1-D decoding QAM constellations). The hexagonal constellation points are in general parameterized by two integers u and v, and the (x, y) coordinate of the i-th constellation point could be expressed as: 
         [0000]    
       
         
           
             
                 
             
              
             
               
                 ( 
                 
                   
                     x 
                     i 
                   
                   , 
                   
                     y 
                     i 
                   
                 
                 ) 
               
               = 
               
                 
                   
                     ? 
                   
                 
                  
                 
                   ( 
                   
                     
                       ( 
                       
                         
                           x 
                           0 
                         
                         , 
                         
                           y 
                           0 
                         
                       
                       ) 
                     
                     + 
                     
                       
                         u 
                         i 
                       
                        
                       
                         ( 
                         
                           1 
                           , 
                           0 
                         
                         ) 
                       
                     
                     + 
                     
                       
                         
                           v 
                           0 
                         
                         2 
                       
                        
                       
                         ( 
                         
                           1 
                           , 
                           
                             3 
                           
                         
                         ) 
                       
                     
                   
                   ) 
                 
               
             
           
         
       
       
         
           
             
               ? 
             
              
             
               indicates text missing or illegible when filed 
             
           
         
       
     
         [0000]    where (x 0 , y 0 ) is a fixed perturbation that could be used to minimize the maximum energy. 
         [0011]    Unlike regular QAM constellations where all constellation points within a given span are occupied, the hexagonal constellation has \emph{unused} constellation points. This necessitates the use of a lookup table for decoding to indicate whether a particular constellation point is used, and store the corresponding codeword of the used constellation points. To simplify the decoding process, the indexing in the lookup tables uses the two integers u and v. 
         [0012]    The structure of the hexagonal constellation provides a straightforward procedure for finding the nearest neighbor. If the normalized received symbol 
         [0000]    
       
         
           
             
                 
             
              
             
               
                 
                   r 
                   
                     
                       ? 
                     
                   
                 
                 = 
                 
                   ( 
                   
                     x 
                     , 
                     y 
                   
                   ) 
                 
               
               , 
               
                 
 
               
                
               
                 
                   ? 
                 
                  
                 
                   indicates text missing or illegible when filed 
                 
               
             
           
         
       
     
         [0000]    then the initial estimate of u and v could be computed as: 
         [0000]    
       
         
           
             
                 
             
              
             
               
                 u 
                 _ 
               
               = 
               
                 2 
                  
                 
                   
                     ( 
                     
                       y 
                       - 
                       
                         y 
                         0 
                       
                     
                     ) 
                   
                   / 
                   
                     3 
                   
                 
               
             
           
         
       
       
         
           
             
                 
             
              
             
               
                 v 
                 _ 
               
               = 
               
                 x 
                 - 
                 
                   x 
                   0 
                 
                 - 
                 
                   
                     ( 
                     
                       y 
                       - 
                       
                         ? 
                       
                     
                     ) 
                   
                   / 
                   
                     3 
                   
                 
               
             
           
         
       
       
         
           
             
               ? 
             
              
             
               indicates text missing or illegible when filed 
             
           
         
       
     
         [0000]    which are in general non-integer. To get the nearest neighbor we compute the Euclidean distance to the immediate neighbors, which correspond to the integer approximations of ū,  v , and pick the one that corresponds to the smallest distance (provided it is used in the constellation). 
         [0013]    Note that, computing the distances to the all neighbors could be implemented such that no multiplication is required. For example, let d f   2  denotes the square of the Euclidean distance between the received symbol and to the constellation point with (└ū┘, └  v ┘), i.e., 
         [0000]    
       
         
           
             
               d 
               f 
               2 
             
             = 
             
               
                  
                 
                   ( 
                   
                     
                       
                         Δ 
                         u 
                       
                       + 
                       
                         0.5 
                          
                         
                             
                         
                          
                         
                           Δ 
                           u 
                         
                       
                     
                     , 
                     
                       
                         
                           Δ 
                           u 
                         
                          
                         
                           √ 
                           3 
                         
                       
                       2 
                     
                   
                   ) 
                 
                  
               
               2 
             
           
         
       
     
         [0000]    where Δ u =ū−└u┘ and Δ v =  v −└v┘. Then the distance to the constellation point with (└ū┘±1, └  v ┘), becomes 
         [0000]    
       
         
           
             
                 
             
              
             
               
                 d 
                 1 
                 2 
               
               = 
               
                 
                   d 
                   f 
                   2 
                 
                 + 
                 
                   1 
                   ± 
                   
                     ( 
                     
                       
                         2 
                          
                         
                           Δ 
                           u 
                         
                       
                       + 
                       
                         ? 
                       
                     
                     ) 
                   
                 
               
             
           
         
       
       
         
           
             
               ? 
             
              
             
               indicates text missing or illegible when filed 
             
           
         
       
     
         [0000]    which does not require any multiplication. and for the other neighbors (ū  v ±1), to have 
         [0000]    
       
         
           
             
                 
             
              
             
               
                 d 
                 2 
                 2 
               
               = 
               
                 
                   d 
                   f 
                   2 
                 
                 + 
                 
                   1 
                   ± 
                   
                     ( 
                     
                       
                         2 
                          
                         
                           ? 
                         
                       
                       + 
                       
                         ? 
                       
                     
                     ) 
                   
                 
               
             
           
         
       
       
         
           
             
               ? 
             
              
             
               indicates text missing or illegible when filed 
             
           
         
       
     
         [0000]    All other immediate neighbors could be computed similarly. In the above relations d f   2  is a common term, therefore it may be ignored.
 
Moreover, the computation of d f   2  is not necessary as it is a common term in the distances of all other neighbors and could be ignored in computing the nearest neighbor. Therefore, we end up with a multiplierless hard decoding.
 
         [0014]    Soft decoding is done similarly. Let b, denote i-th bit in the symbol. Define Σ i   1  as the set of immediate neighbors to (└ū┘, └  v ┘) with b i =1 in the corresponding codeword, and similarly Σ i   0  for b i =0. Then the likelihood ratio (LLR) of b i  is (assuming equiprobable codewords) 
         [0000]    
       
         
           
             
               L 
                
               
                 ( 
                 
                   b 
                   i 
                 
                 ) 
               
             
             = 
             
               
                 
                   
                     
                       ∑ 
                       
                         c 
                         ∈ 
                         
                           ∑ 
                           i 
                           1 
                         
                       
                     
                      
                     
                       p 
                        
                       
                         ( 
                         
                           r 
                           | 
                           c 
                         
                         ) 
                       
                     
                   
                 
               
               
                 
                   
                     
                       ∑ 
                       
                         c 
                         ∈ 
                         
                           ∑ 
                           i 
                           0 
                         
                       
                     
                      
                     
                       p 
                        
                       
                         ( 
                         
                           r 
                           | 
                           c 
                         
                         ) 
                       
                     
                   
                 
               
             
           
         
       
     
         [0015]    For numerical tractability, the LLR is clipped if it is larger or smaller than predefined thresholds ±η. If all the surrounding neighbors have the same value for b i  then L(b i ) is set to ±η. depending on the value of b i . For AWGN channels, the above likelihood could be simplified to 
         [0000]    
       
         
           
             
                 
             
              
             
               
                 L 
                  
                 
                   ( 
                   
                     ? 
                   
                   ) 
                 
               
               ≈ 
               
                 
                   ? 
                 
                  
                 
                   
                      
                     
                       r 
                       - 
                       
                         ? 
                       
                     
                      
                   
                   2 
                 
                  
                 
                   ? 
                 
                  
                 
                   
                      
                     
                       r 
                       - 
                       
                         ? 
                       
                     
                      
                   
                   2 
                 
               
             
           
         
       
       
         
           
             
               ? 
             
              
             
               indicates text missing or illegible when filed 
             
           
         
       
     
         [0000]    Note that, the term d f   2  is cancelled out and we also end up with a multiplierless soft decoding. 
         [0016]    Any signal constellation for communication and/or coding is characterized by three parameters:
       1. The constellation size M.   2. The position of each constellation point (in the complex plane).   3. The codeword associated with each constellation point.       
 
         [0020]    Therefore, any constellation (regardless of its shape) could be represented by a lookup table of size M, whose entries are the position and the associated codeword for each constellation point. For example assume M=2         , then the i-th entry in the lookup table has the location s i =x i +jy i  as the position and the codeword c i −[b q−1            . . . b 1           b 0           ]. 
         [0021]    If a symbol r=x+jy is received, then the objective of a hard decoder is to find the closest constellation point (in some sense), and output the corresponding codeword. In the simplest case, we use the Euclidean distance as the metric. In this case, we compute for each constellation point 
         [0000]    
       
         
           
             
                 
             
              
             
               
                 ? 
               
               = 
               
                 
                   
                     
                       ( 
                       
                         x 
                         - 
                         
                           ? 
                         
                       
                       ) 
                     
                     2 
                   
                   + 
                   
                     
                       ( 
                       
                         y 
                         - 
                         
                           ? 
                         
                       
                       ) 
                     
                     2 
                   
                 
               
             
           
         
       
       
         
           
             
               ? 
             
              
             
               indicates text missing or illegible when filed 
             
           
         
       
     
         [0000]    and the decoded point is the one that corresponds to the minimum distance, i.e., 
         [0000]    
       
         
           
             
                 
             
              
             
               
                 ? 
               
               = 
               
                 argmin 
                  
                 
                   { 
                   
                     ? 
                   
                   } 
                 
               
             
           
         
       
       
         
           
             
               ? 
             
              
             
               indicates text missing or illegible when filed 
             
           
         
       
     
         [0000]    and the decoded codeword becomes c i . 
         [0022]      FIG. 4  is illustrative of the construction of a transceiver system in which an embodiment of the invention may operate. Of course, it is contemplated that other architectures and approaches to realizing this transceiver system may also be used, as will be apparent to those skilled in the art having reference to this specification. Transceiver  45  according to this embodiment of the invention, illustrated in  FIG. 4 , includes the circuitry and functionality necessary and appropriate for carrying out the functions of receiver  20 . 
         [0023]    In  FIG. 4 , receiver also known as transceiver  45  is coupled to host system  50  by way of a corresponding bus B. Host system  50  corresponds to a personal computer, a laptop computer, or any sort of computing device capable of wireless broadband communications, in the context of a wireless local area network (LAN), wide area network (WAN), or “metro” area network (MAN); of course, the particulars of host system  50  will vary with the particular application. 
         [0024]    Transceiver  45  in this example includes modem processor  51 , which is bidirectionally coupled to bus B on one side, and to radio frequency (RF) circuitry  53  on its other side. RF circuitry  53 , which may be realized by conventional RF circuitry known in the art, performs the analog demodulation, amplification, and filtering of RF signals received over the wireless channel and the analog modulation, amplification, and filtering of RF signals to be transmitted by transceiver  45  over the wireless channel, one or more antennae A 1  and A 2 . RF circuitry  53  includes front end functions. The architecture of modem processor  51  into which this embodiment of the invention may be implemented follows that of a conventional single-chip media access controller (MAC) and a baseband processor. It is contemplated that the architecture of other transceiver installations, including for wireless broadband communications, whether on the network or client side, may follow a similar generic approach, as modified for the particular application location, as known in the art. This exemplary architecture includes embedded central processing unit (CPU)  56 , for example realized as a reduced instruction set (RISC) processor, for managing high level control functions within modem processor  51 . For example, embedded CPU  56  manages host interface  54  to directly support the appropriate physical interface to bus B and host system  50 . Local RAM  52  is available to embedded CPU  56  and other functions in modem processor  51  for code execution and data buffering. Medium access controller (MAC)  57  and baseband processor  59  are also implemented within modem processor  51  according to the preferred embodiments of the invention, for generating the appropriate packets for wireless communication, and providing encryption, decryption, and wired equivalent privacy (WEP) functionality. It is contemplated that baseband processor  59  may be realized by way of a digital signal processor (DSP) “core”, for example having the computational capacity of a modern DSP integrated circuit such as one of the TMS320C64x family of digital signal processors available from Texas Instruments Incorporated (Dallas Tex.). Program memory  55  is provided within transceiver  45 , for example in the form of electrically erasable/programmable read-only memory (EEPROM), to store the sequences of operating instructions executable by modem processor  51 , including control instructions for carrying out the decoding sequences according to the preferred embodiment of the invention. Also included within transceiver  45 , in the form of a wireless adapter, are other typical support circuitry and functions that are not shown, but that are useful in connection with the particular operation of transceiver  45 . 
         [0025]    Many modifications and other embodiments of the invention will come to mind to one skilled in the art to which this invention pertains having the benefit of the teachings presented in the foregoing descriptions, and the associated drawings. Therefore, it is to be understood that the invention is not to be limited to the specific embodiments disclosed. Although specific terms are employed herein, they are used in a generic and descriptive sense only and not for purposes of limitation.