# Patent

## Title
System and method for designing constellations and use thereof

## Abstract

A method for operating a transmitting device includes mapping data to a transmission symbol in accordance with a constellation map assigned to a receiving device, wherein the constellation map is designed in accordance with a posteriori error rate derived from a transmitted signal, and transmitting the transmission symbol.

## Background
TECHNICAL FIELD
The present disclosure relates generally to digital communications, and more particularly to a system and method for designing constellations and use thereof.
BACKGROUND
Generally, a constellation includes a plurality of constellation points arranged in a particular configuration. The constellation represents a mapping of digital data to a carrier signal or carrier wave and vice versa. For example, in quadrature amplitude modulation, the amplitudes of two waves that are 90 degrees out-of-phase with each other are modulated to represent the digital data.
SUMMARY OF THE DISCLOSURE
Example embodiments of the present disclosure which provide a system and method for designing constellations and use thereof.
In accordance with an example embodiment of the present disclosure, a method for operating a transmitting device is provided. The method includes mapping, by the transmitting device, data to a transmission symbol in accordance with a constellation map assigned to a receiving device, wherein the constellation map is designed in accordance with a posteriori error rate derived from a transmitted signal, and transmitting, by the transmitting device, the transmission symbol.
In accordance with another example embodiment of the present disclosure, a method for operating a receiving device is provided. The method includes receiving, by the receiving device, a transmission symbol from a transmitting device, de-mapping, by the receiving device, the transmission symbol in accordance with a constellation map thereby producing received data, wherein the constellation map is designed in accordance with a posteriori error rate derived from a transmitted signal, and processing, by the receiving device, the received data.
In accordance with another example embodiment of the present disclosure, a transmitting device is provided. The transmitting device includes a processor, and a non-transitory computer readable storage medium storing programming for execution by the processor. The programming including instructions to map data to a transmission symbol in accordance with a constellation map assigned to a receiving device, wherein the constellation map is designed in accordance with a posteriori error rate derived from a transmitted signal, and transmit the transmission symbol.
In accordance with another example embodiment of the present disclosure, a receiving device is provided. The receiving device includes a processor, and a non-transitory computer readable storage medium storing programming for execution by the processor. The programming including instructions to receive a transmission symbol from a transmitting device, de-map the transmission symbol in accordance with a constellation map thereby producing received data, wherein the constellation map is designed in accordance with a posteriori error rate derived from a transmitted signal, and process the received data.
One advantage of an embodiment is that the techniques presented herein are operable in lower signal to noise ratio (SNR) environments.



BRIEF DESCRIPTION OF THE DRAWINGS
For a more complete understanding of the present disclosure, and the advantages thereof, reference is now made to the following descriptions taken in conjunction with the accompanying drawing, in which:
FIG. 1 illustrates an example communications system according to example embodiments described herein;
FIG. 2a illustrates a flow diagram of example operations occurring in a transmitting device when making a transmission according to example embodiments described herein;
FIG. 2b illustrates a flow diagram of example operations occurring in a receiving device when receiving a transmission according to example embodiments described herein;
FIG. 3 illustrates a flow diagram of example operations in a designing device according to example embodiments described herein;
FIG. 4 illustrates a flow diagram of operations in a receiving device participating in constellation design according to example embodiments described herein;
FIGS. 5a and 5b illustrate diagrams of dimensions 1 and 2 of a 2-dimensional constellation according to example embodiments described herein;
FIGS. 6a-6c illustrate diagrams of dimensions 1, 2, and 3 of a 3-dimensional constellation according to example embodiments described herein;
FIG. 7 illustrates an example first communications device according to example embodiments described herein;
FIG. 8 illustrates an example second communications device according to example embodiments described herein; and
FIG. 9 is a block diagram of a processing system that may be used for implementing the devices and methods disclosed herein



DETAILED DESCRIPTION OF ILLUSTRATIVE EMBODIMENTS
The operating of the current example embodiments and the structure thereof are discussed in detail below. It should be appreciated, however, that the present disclosure provides many applicable inventive concepts that can be embodied in a wide variety of specific contexts. The specific embodiments discussed are merely illustrative of specific structures of the disclosure and ways to operate the disclosure, and do not limit the scope of the disclosure.
One embodiment of the disclosure relates to designing constellations and use thereof. For example, a device designs a constellation map in accordance with a posteriori error rate derived from a signal, and prompts the constellation map to be used for communicating signals in a communications system.
The present disclosure will be described with respect to example embodiments in a specific context, namely communications systems that use constellations. The disclosure may be applied to standards compliant communications systems, such as those that are compliant with Third Generation Partnership Project (3GPP), IEEE 802.11, and the like, technical standards, and non-standards compliant communications systems, that use constellations.
FIG. 1 illustrates an example communications system 100. Communications system 100 includes an evolved NodeB (eNB) 105 serving a plurality of user equipments (UEs). In general, transmissions to and from UEs may go through eNB 105 using resources allocated by eNB 105. However, in an alternative communications mode, communications between two UEs may be made without having eNB 105 serve as an intermediary. eNBs may also be commonly referred to as NodeBs, base stations, access points, controllers, base terminal stations, and the like, while UEs may also be commonly referred to as mobiles, mobile stations, stations, terminals, subscribers, users, and the like.
While it is understood that communications systems may employ multiple eNBs capable of communicating with a number of UEs, only one eNB, and a number of UEs are illustrated for simplicity.
In a communications system that utilizes constellations, digital data is mapped onto a carrier waveform or carrier signal (and vice versa) using a constellation map. The constellation map may be a one-dimensional constellation map or a multi-dimensional constellation map. Communications system 100 also includes a designing device 130. Designing device 130 designs constellations (such as one-dimensional constellations, and multi-dimensional constellations) for devices in communications system 100. Designing device 130 may design the constellations in accordance with the example embodiments described herein. Designing device 130 may provide the constellations to the devices in communications system 100. Designing device 130 may store the constellations in a memory or a database.
FIG. 2a illustrates a flow diagram of example operations 200 occurring in a transmitting device when making a transmission. Operations 200 may be indicative of operations occurring in a transmitting device, such as an eNB in a downlink transmission or a UE in an uplink transmission.
Operations 200 may begin with the transmitting device determining a constellation map (one-dimensional or multi-dimensional) for a receiving device (block 205). Without loss of generality, the terms constellation and constellation map may be used interchangeably. The transmitting device may assign a constellation map to the receiving device, retrieve a constellation map assignment for the receiving device from memory (remote or local), retrieve a constellation map assignment for the receiving device from a server (remote or local), the transmitting device may generate the constellation map for the receiving device, and the like. The transmitting device may receive data intended for the receiving device (block 210). The transmitting device may encode and modulate the received data in accordance with the constellation map (block 215). The encoding and modulating of the received data produces one or more QAM symbols. The transmitting device may transmit the one or more QAM symbols (block 220).
FIG. 2b illustrates a flow diagram of example operations 250 occurring in a receiving device when receiving a transmission. Operations 250 may be indicative of operations occurring in a receiving device, such as a UE in a downlink transmission or an eNB in an uplink transmission.
Operations 250 may begin with the receiving device determining a constellation map (one-dimensional or multi-dimensional) (block 255). The receiving device may be assigned a constellation map that is signaled to it in a message, retrieve a constellation map assignment from memory (remote or local), retrieve a constellation map assignment from a server (remote or local), the receiving device may assign itself a constellation map, and the like. The receiving device may receive a QAM symbol (block 260). The receiving device may de-map the QAM symbol in accordance with the constellation map to produce coded data (block 265). The receiving device may decode the coded data to produce data (block 270). The receiving device may process the data (block 275).
It is possible to design constellation maps using Euclidean distance between points of the constellation maps as a design criterion. The use of Euclidean distance to place an upper bound on a metric, such as bit error rate (BER), may yield a tight bound in high signal to noise ratio (SNR) environments. However, communications systems that use coded transmission typically operate in low SNR environments. Hence, a different design criterion may be needed to accommodate requirements of coded transmissions in a low SNR environment.
According to an example embodiment, optimization of an a posteriori error rate, such as a posteriori bit error rate (BER), a posteriori packet error rate (PER), a posteriori frame error rate (FER), and the like, is used as a design criterion for constellation design.
For discussion purposes, consider a design criterion of minimizing the a posteriori bit error rate




  
    
      
        
          P
          
            
              err
              ⁢
              _
              ⁢
              bi
              ⁢
              t
            
            ,
            ps
          
        
        =
        
          
            
              1
              K
            
            ⁢
            
              
                ∑
                
                  i
                  =
                  1
                
                K
              
              ⁢
              
                
              
              ⁢
              
                (
                
                  1
                  -
                  
                    
                      Pr
                      ⁢
                      
                        {
                        
                          
                            θ
                            i
                          
                          =
                          
                            
                              θ
                              ^
                            
                            i
                          
                        
                        }
                      
                    
                    _
                  
                
                )
              
            
          
          =
          
            
              
                1
                K
              
              ⁢
              
                
                  ∑
                  
                    i
                    =
                    1
                  
                  K
                
                ⁢
                
                  (
                  
                    1
                    -
                    
                      
                        1
                        2
                      
                      ⁢
                      
                        
                          (
                          
                            1
                            +
                            
                              
                                θ
                                i
                              
                              ⁢
                              
                                tanh
                                ⁡
                                
                                  (
                                  
                                    
                                      LLR
                                      i
                                    
                                    2
                                  
                                  )
                                
                              
                            
                          
                          )
                        
                        _
                      
                    
                  
                  )
                
              
            
            =
            
              
                1
                K
              
              ⁢
              
                
                  ∑
                  
                    i
                    =
                    1
                  
                  K
                
                ⁢
                
                  
                
                ⁢
                
                  
                    1
                    2
                  
                  ⁢
                  
                    (
                    
                      1
                      -
                      
                        
                          
                            θ
                            i
                          
                          ⁢
                          
                            tanh
                            ⁡
                            
                              (
                              
                                
                                  LLR
                                  i
                                
                                2
                              
                              )
                            
                          
                        
                        _
                      
                    
                    )
                  
                
              
            
          
        
      
    
    
      
        (
        1
        )
      
    
  




where





  
    LLR
    i
  
  =
  
    log
    ⁡
    
      (
      
        
          
            P
            ps
          
          ⁡
          
            (
            
              
                θ
                i
              
              =
              1
            
            )
          
        
        
          
            P
            ps
          
          ⁡
          
            (
            
              
                θ
                i
              
              =
              
                -
                1
              
            
            )
          
        
      
      )
    
  




is the logarithmic likelihood ratio for the i-th bit, included in the K bit constellation.

Let S=[s1, s2, . . . sM]T be an M dimensional vector of modulated symbols, where each modulated symbol sm being dependent on the same K dimensioned vector of binary symbols Θ=[θ1, θ2, . . . θK], where θkε{−1;1}. In other words, vector S is the function of the binary vector, i.e., S (Θ) has 2K possible values among the whole set of the multi-dimensional constellation.
Let S (Θ) be the vector being observed in Gaussian background noise:

Y=S(Θ)+η,

where η is an M dimensioned vector of samples of complex Gaussian noise with zero mean and covariance matrix Rη=2ση2IM, where IM is an M-by-M identity matrix, ση2 is the variance of either the I or Q component of noise.

All available information about transmitted combination Θ is contained in the following posteriori distribution:

Pps(Θ|Y)=CΛ(Y|Θ)Ppr(Θ),

where Ppr (Θ) is an a priori distribution of the vector of binary variables, Λ(Y|Θ) is a likelihood function, C is a normalizing constant, which does not depend on Θ.

A likelihood function may be expressed as:




  
    
      Λ
      ⁡
      
        (
        
          Y
          ❘
          Θ
        
        )
      
    
    =
    
      
        C
        2
      
      ⁢
      
        exp
        ⁡
        
          (
          
            
              -
              
                1
                
                  2
                  ⁢
                  
                    σ
                    η
                    2
                  
                
              
            
            ⁢
            
              
                (
                
                  Y
                  -
                  
                    S
                    ⁡
                    
                      (
                      Θ
                      )
                    
                  
                
                )
              
              H
            
            ⁢
            
              (
              
                Y
                -
                
                  S
                  ⁡
                  
                    (
                    Θ
                    )
                  
                
              
              )
            
          
          )
        
      
    
  
  ,




where ( )H is a conjugate transpose operation.

For equiprobable combinations of vector Θ,




  
    
      P
      pr
    
    ⁡
    
      (
      Θ
      )
    
  
  =
  
    
      1
      
        2
        K
      
    
    .
  




Therefore, a posteriori distribution is determined only by the likelihood function. The logarithm of the likelihood ratio expressible as





  
    λ
    k
  
  =
  
    
      LLR
      k
    
    =
    
      log
      ⁢
      
        
          
            P
            ps
          
          ⁡
          
            (
            
              
                θ
                k
              
              =
              
                1
                ❘
                Y
              
            
            )
          
        
        
          
            P
            ps
          
          ⁡
          
            (
            
              
                θ
                k
              
              =
              
                
                  -
                  1
                
                ❘
                Y
              
            
            )
          
        
      
    
  




is often used for calculating soft estimates, where





  
    
      P
      ps
    
    ⁡
    
      (
      
        
          θ
          k
        
        ❘
        Y
      
      )
    
  
  =
  
    
      ∑
      
        
          
            θ
            i
          
          ∈
          
            {
            
              
                -
                1
              
              ;
              1
            
            }
          
        
        
          
            i
            =
            
              
                1
                ,
                K
              
              _
            
          
          ,
          
            i
            ≠
            k
          
        
      
    
    ⁢
    
      
    
    ⁢
    
      
        P
        ps
      
      ⁡
      
        (
        
          Θ
          ❘
          Y
        
        )
      
    
  




is marginal distribution of the k-th binary random value θk.

It is possible to show that a marginal distribution of binary random value θkε{−1;1} is completely defined by the λk parameter and is expressible as




  
    
      P
      ps
    
    ⁡
    
      (
      
        
          θ
          k
        
        ❘
        Y
      
      )
    
  
  =
  
    
      1
      2
    
    ⁢
    
      
        (
        
          1
          +
          
            
              θ
              k
            
            ⁢
            
              tanh
              ⁡
              
                (
                
                  
                    λ
                    k
                  
                  2
                
                )
              
            
          
        
        )
      
      .
    
  




A hard estimate (based on maximum a posteriori probability) of a transmitted binary symbol is expressible as





  
    
      θ
      ^
    
    k
  
  =
  
    
      
        argmax
        ⁢
        
          {
          
            
              P
              ps
            
            ⁡
            
              (
              
                
                  θ
                  k
                
                ❘
                Y
              
              )
            
          
          }
        
      
      ⁢
      
        ❘
        
          
            θ
            k
          
          ∈
          
            {
            
              
                -
                1
              
              ;
              1
            
            }
          
        
      
    
    =
    
      
        sgn
        ⁡
        
          (
          
            tanh
            ⁡
            
              (
              
                
                  λ
                  k
                
                2
              
              )
            
          
          )
        
      
      =
      
        
          sgn
          ⁡
          
            (
            
              λ
              k
            
            )
          
        
        .
      
    
  




Let binary symbol υk be transmitted and its estimate denoted {circumflex over (θ)}k be calculable. The binary symbol comprising εk={circumflex over (θ)}kυk describes the bit error, i.e., if εk=−1 then this bit is received in error. It is also possible to express the a posteriori distribution for εk as




  
    
      
        P
        ps
      
      ⁡
      
        (
        
          
            
              ɛ
              k
            
            ❘
            Θ
          
          ,
          η
        
        )
      
    
    =
    
      
        
          1
          2
        
        ⁢
        
          (
          
            1
            +
            
              
                ɛ
                k
              
              ⁢
              
                θ
                k
              
              ⁢
              
                tanh
                ⁡
                
                  (
                  
                    
                      
                        λ
                        k
                      
                      ⁡
                      
                        (
                        
                          Ξ
                          ,
                          η
                        
                        )
                      
                    
                    2
                  
                  )
                
              
            
          
          )
        
      
      =
      
        
          1
          2
        
        ⁢
        
          (
          
            1
            +
            
              
                ɛ
                k
              
              ⁢
              
                tanh
                ⁡
                
                  (
                  
                    
                      
                        θ
                        k
                      
                      ⁢
                      
                        
                          λ
                          k
                        
                        ⁡
                        
                          (
                          
                            Ξ
                            ,
                            η
                          
                          )
                        
                      
                    
                    2
                  
                  )
                
              
            
          
          )
        
      
    
  
  ,




where Ξ=[υ1, υ2, . . . υK] is a vector of transmitted binary symbols.

The a posteriori bit error rate may be defined as an average probability of event εk=−1, i.e.,




  
    
      BER
      k
    
    =
    
      
        〈
        
          Pr
          ⁢
          
            {
            
              
                ɛ
                k
              
              =
              
                -
                1
              
            
            }
          
        
        〉
      
      =
      
        
          1
          2
        
        ⁢
        
          (
          
            1
            -
            
              〈
              
                tanh
                ⁡
                
                  (
                  
                    
                      
                        θ
                        k
                      
                      ⁢
                      
                        
                          λ
                          k
                        
                        ⁡
                        
                          (
                          
                            Ξ
                            ,
                            η
                          
                          )
                        
                      
                    
                    2
                  
                  )
                
              
              〉
            
          
          )
        
      
    
  
  ,




where  is an averaging operation on both noise η and all possible choices of Ξ. The average a posteriori error rate on all bits may be expressible as





  BER
  =
  
    
      
        1
        K
      
      ⁢
      
        
          ∑
          
            k
            =
            1
          
          K
        
        ⁢
        
          
        
        ⁢
        
          BER
          k
        
      
    
    =
    
      
        1
        2
      
      -
      
        
          1
          
            2
            ⁢
            K
          
        
        ⁢
        
          
            ∑
            
              k
              =
              1
            
            K
          
          ⁢
          
            
          
          ⁢
          
            
              〈
              
                tanh
                ⁡
                
                  (
                  
                    
                      
                        θ
                        k
                      
                      ⁢
                      
                        
                          λ
                          k
                        
                        ⁡
                        
                          (
                          
                            Ξ
                            ,
                            η
                          
                          )
                        
                      
                    
                    2
                  
                  )
                
              
              〉
            
            .
          
        
      
    
  




It is possible to simplify the a posteriori error rate by eliminating the noise component, i.e., η=0. The average a posteriori error rate on all bits may then be expressible as




  
    BER
    _
  
  =
  
    
      1
      2
    
    -
    
      
        1
        
          2
          ⁢
          K
        
      
      ⁢
      
        
          ∑
          
            k
            =
            1
          
          K
        
        ⁢
        
          
            〈
            
              tanh
              ⁡
              
                (
                
                  
                    
                      θ
                      k
                    
                    ⁢
                    
                      
                        λ
                        k
                      
                      ⁡
                      
                        (
                        
                          Ξ
                          ,
                          
                            η
                            =
                            0
                          
                        
                        )
                      
                    
                  
                  2
                
                )
              
            
            〉
          
          .
        
      
    
  




It is possible to use a maximum a posteriori (MAP) demodulation algorithm to determine the λk parameter, as an example





  
    
      λ
      k
    
    ⁡
    
      (
      Ξ
      )
    
  
  =
  
    log
    ⁢
    
      
        
          
            ∑
            
              
                
                  θ
                  i
                
                ∈
                
                  {
                  
                    
                      -
                      1
                    
                    ;
                    1
                  
                  }
                
              
              
                
                  i
                  =
                  
                    
                      1
                      ,
                      K
                    
                    _
                  
                
                ,
                
                  i
                  ≠
                  k
                
              
            
          
          ⁢
          
            exp
            ⁡
            
              (
              
                
                  
                    
                      
                        -
                        
                          1
                          
                            2
                            ⁢
                            
                              σ
                              η
                              2
                            
                          
                        
                      
                      ⁢
                      
                        
                          (
                          
                            
                              S
                              ⁡
                              
                                (
                                Ξ
                                )
                              
                            
                            -
                            
                              S
                              ⁡
                              
                                (
                                
                                  
                                    θ
                                    1
                                  
                                  ,
                                  
                                    
                                      ...
                                      ⁢
                                      
                                        
                                      
                                      ⁢
                                      
                                        θ
                                        k
                                      
                                    
                                    =
                                    1
                                  
                                  ,
                                  
                                    ...
                                    ⁢
                                    
                                      
                                    
                                    ⁢
                                    
                                      θ
                                      K
                                    
                                  
                                
                                )
                              
                            
                          
                          )
                        
                        H
                      
                    
                  
                
                
                  
                    
                      (
                      
                        
                          S
                          ⁡
                          
                            (
                            Ξ
                            )
                          
                        
                        -
                        
                          S
                          ⁡
                          
                            (
                            
                              
                                θ
                                1
                              
                              ,
                              
                                
                                  ...
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  
                                    θ
                                    k
                                  
                                
                                =
                                1
                              
                              ,
                              
                                ...
                                ⁢
                                
                                  
                                
                                ⁢
                                
                                  θ
                                  K
                                
                              
                            
                            )
                          
                        
                      
                      )
                    
                  
                
              
              )
            
          
        
        
          
            ∑
            
              
                
                  θ
                  i
                
                ∈
                
                  {
                  
                    
                      -
                      1
                    
                    ;
                    1
                  
                  }
                
              
              
                
                  i
                  =
                  
                    
                      1
                      ,
                      K
                    
                    _
                  
                
                ,
                
                  i
                  ≠
                  k
                
              
            
          
          ⁢
          
            exp
            ⁡
            
              (
              
                
                  
                    
                      
                        -
                        
                          1
                          
                            2
                            ⁢
                            
                              σ
                              η
                              2
                            
                          
                        
                      
                      ⁢
                      
                        
                          (
                          
                            
                              S
                              ⁡
                              
                                (
                                Ξ
                                )
                              
                            
                            -
                            
                              S
                              ⁡
                              
                                (
                                
                                  
                                    θ
                                    1
                                  
                                  ,
                                  
                                    
                                      ...
                                      ⁢
                                      
                                        
                                      
                                      ⁢
                                      
                                        θ
                                        k
                                      
                                    
                                    =
                                    
                                      -
                                      1
                                    
                                  
                                  ,
                                  
                                    ...
                                    ⁢
                                    
                                      
                                    
                                    ⁢
                                    
                                      θ
                                      K
                                    
                                  
                                
                                )
                              
                            
                          
                          )
                        
                        H
                      
                    
                  
                
                
                  
                    
                      (
                      
                        
                          S
                          ⁡
                          
                            (
                            Ξ
                            )
                          
                        
                        -
                        
                          S
                          ⁡
                          
                            (
                            
                              
                                θ
                                1
                              
                              ,
                              
                                
                                  ...
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  
                                    θ
                                    k
                                  
                                
                                =
                                
                                  -
                                  1
                                
                              
                              ,
                              
                                ...
                                ⁢
                                
                                  
                                
                                ⁢
                                
                                  θ
                                  K
                                
                              
                            
                            )
                          
                        
                      
                      )
                    
                  
                
              
              )
            
          
        
      
      .
    
  




The minimization of the BER function may be provided by selection of one-dimensional or multi-dimensional constellation points, as described by the S (Θ) function. An optimal constellation search may be utilized. The M values of elements of the S (Θ) function correspond to each combination of the Θ binary vector. Hence, the complex 2K×M dimensioned matrix S may be an optimization result, with each column of the matrix S representing one point of the M dimensioned constellation and each row representing one complex constellation. The matrix S provides the minimum of BER with a constraint on a constant average power of each constellation, i.e., for any m=1, . . . , M the condition




  
    
      1
      
        2
        K
      
    
    ⁢
    
      
        ∑
        
          i
          =
          1
        
        
          2
          K
        
      
      ⁢
      
        
      
      ⁢
      
        
          
          
            S
            
              (
              
                i
                ,
                m
              
              )
            
          
          
        
        2
      
    
  
  =
  1




is met.

According to an example embodiment, the minimization of the BER function may be performed using numerical methods for optimization. Gradient methods are generally effective in terms of convergence speed. The optimization algorithm may be iterative and may be described as

Sj=Sj−1−γ∇,

where γ is a weighting factor,





  
    
      ∇
      
        =
        
          
            d
            ⁢
            
              BER
              _
            
          
          
            d
            ⁢
            
              
            
            ⁢
            S
          
        
      
    
    
  
  
    S
    =
    
      S
      
        j
        -
        1
      
    
  




is a gradient of the BER function with respect to the matrix S in the points of S=Sj−1. Constraint normalization may be included with a normalization operation expressible as

.{tilde over (S)}j=Sj(diag(SjHSj))−1.

A simplifying step may include changing the gradient by its incremental ratio approximation, expressible as




  
    
      ∇
      
        (
        
          k
          ,
          m
        
        )
      
    
    ⁢
    
      =
      
        
          
            
              BER
              _
            
            ⁡
            
              (
              
                
                  S
                  
                    (
                    
                      k
                      ,
                      m
                    
                    )
                  
                
                +
                
                  Δ
                  ⁢
                  
                    
                  
                  ⁢
                  S
                
              
              )
            
          
          -
          
            
              BER
              _
            
            ⁡
            
              (
              
                
                  S
                  
                    (
                    
                      k
                      ,
                      m
                    
                    )
                  
                
                -
                
                  Δ
                  ⁢
                  
                    
                  
                  ⁢
                  S
                
              
              )
            
          
        
        
          2
          ⁢
          
            
          
          ⁢
          Δ
          ⁢
          
            
          
          ⁢
          S
        
      
    
  
  ,




where S(k,m) is a (k,m)-th element of matrix S, and ΔS is an increment of the argument (shift of the constellation point). Since the approximation of the gradient is being determined, the direction of the constellation correction may be incorrect. It is proposed to use a modified procedure with a built-in check. The modified optimization procedure may be described as, with other forms of corrections and stopping conditions being possible:

a. Determine shifted constellation points

Sj−1,+Δ(k,m)=Sj−1(k,m)+ΔS, Sj−1,−Δ(k,m)=Sj−1(k,m)−ΔS; 

b. Normalize constellations with shifted points




  
    
      
        S
        ~
      
      
        
          j
          -
          1
        
        ,
        
          +
          
            Δ
            km
          
        
      
      
        (
        
          :
          
            ,
            m
          
        
        )
      
    
    =
    
      
        S
        
          
            j
            -
            1
          
          ,
          
            +
            
              Δ
              km
            
          
        
        
          (
          
            :
            
              ,
              m
            
          
          )
        
      
      
        
          
            1
            
              2
              K
            
          
          ⁢
          
            
              ∑
              
                i
                =
                1
              
              
                2
                K
              
            
            ⁢
            
              
                
                
                  S
                  
                    
                      j
                      -
                      1
                    
                    ,
                    
                      +
                      
                        Δ
                        km
                      
                    
                  
                  
                    (
                    
                      i
                      ,
                      m
                    
                    )
                  
                
                
              
              2
            
          
        
      
    
  
  ,
  
    

  
  ⁢
  
    
      
        
          S
          ~
        
        
          
            j
            -
            1
          
          ,
          
            -
            
              Δ
              km
            
          
        
        
          (
          
            :
            
              ,
              m
            
          
          )
        
      
      =
      
        
          S
          
            
              j
              -
              1
            
            ,
            
              -
              
                Δ
                km
              
            
          
          
            (
            
              :
              
                ,
                m
              
            
            )
          
        
        
          
            
              1
              
                2
                K
              
            
            ⁢
            
              
                ∑
                
                  i
                  =
                  1
                
                
                  2
                  K
                
              
              ⁢
              
                
                  
                  
                    S
                    
                      
                        j
                        -
                        1
                      
                      ,
                      
                        -
                        
                          Δ
                          km
                        
                      
                    
                    
                      (
                      
                        i
                        ,
                        m
                      
                      )
                    
                  
                  
                
                2
              
            
          
        
      
    
    ;
  




c. Determine gradient




  
    
      ∇
      j
      
        (
        
          k
          ,
          m
        
        )
      
    
    ⁢
    
      =
      
        
          
            
              BER
              _
            
            ⁡
            
              (
              
                
                  S
                  ~
                
                
                  
                    j
                    -
                    1
                  
                  ,
                  
                    +
                    
                      Δ
                      km
                    
                  
                
              
              )
            
          
          -
          
            
              BER
              _
            
            ⁡
            
              (
              
                
                  S
                  ~
                
                
                  
                    j
                    -
                    1
                  
                  ,
                  
                    -
                    
                      Δ
                      km
                    
                  
                
              
              )
            
          
        
        
          2
          ⁢
          Δ
          ⁢
          
            
          
          ⁢
          S
        
      
    
  
  ,




where {tilde over (S)}j−1,+Δkm=[Sj−1(:,1), Sj−1(:,1), . . . , {tilde over (S)}j−1,−Δkm(:,m), . . . , Sj−1(:,M)];

d. Normalize gradient




  
    
      
        ∇
        ~
      
      j
    
    ⁢
    
      =
      
        
          ∇
          j
        
        
          
            
            
              ∇
              j
            
            
          
          2
        
      
    
  
  ;




e. Determine new constellation Sj=Sj−1−γ{tilde over (∇)}j;
f. Normalize constellation {tilde over (S)}j=Sj(diag(SjHSj))−1;
g. Determine current value of BER({tilde over (S)}j);
h. Constellation step is good if BER({tilde over (S)}j)<BER({tilde over (S)}j−1), return to (a);
i. Constellation step is bad if BER({tilde over (S)}j)≧BER({tilde over (S)}j−1), and reduce γ factor by a scaling factor (e.g., γ=0.1·γ) and return to (e) until γ≧γmin.
According to another example embodiment, the minimization of the BER function may be performed using numerical methods for optimization. Methods of random search (optimization) using stochastic approximation are used. An example method for minimizing the BER function is as follows:
1. Form a matrix of independent Gaussian random increments with zero mean and unit variance is formed ΔSj ̃N (O, I);
2. Determine two sets of constellations with opposite directions of change of shifted constellation points Sj+=Sj−1+βΔSj, and Sj−=Sj−1−βΔSj, where β is an algorithm parameter;
3. Normalize constellations with shifted points

{tilde over (S)}j+=Sj+(diag ((Sj+)HSj+))−1, {tilde over (S)}j−=Sj−(diag ((Sj−)HSj−))−1;

4. Determine values of posteriori probabilities

BER({tilde over (S)}j+) and BER({tilde over (S)}j−);

5. Determine new constellation

Sj=Sj−1−γjα sgn(BER({tilde over (S)}j+)−BER({tilde over (S)}j−))ΔSj where γj, α are algorithm parameters;

6. Normalize the constellation {tilde over (S)}j=Sj(diag(SjHSj))−1;
7. Determine current value of BER({tilde over (S)}j);
8. Constellation step is good if BER({tilde over (S)}j)<BER({tilde over (S)}j−1), increase γj+1=Aγ,↑γj and return to (1) for next iteration;
9. Constellation step is bad if BER({tilde over (S)}j)≧BER({tilde over (S)}j−1), reduce factor γj+1=Aγ,↓γj and return to (5) until γj≧γmin. If γj<γmin and BER({tilde over (S)}j)≧BER({tilde over (S)}j−1), return to (1) without constellation correction (i.e., set Sj=Sj−1);
10. Iteration is over when the number of iteration reaches a threshold.
FIG. 3 illustrates a flow diagram of example operations 300 in a designing device. Operations 300 may be indicative of operations occurring in a designing device as the designing device designs a constellation with a posteriori error rate as a design criterion.
Operations 300 may begin with the designing device receiving performance parameters for a communications system (block 305). The performance parameters may be used by the designing device to design the constellation. Examples of performance parameters may include a number of bits, dimensions of the constellation, assumptions regarding the communications channels, and the like. The designing device may select a constellation (block 310). The constellation may be one-dimensional or multi-dimensional, with the dimension potentially being determined by the performance parameters, communications device capability, and the like. The constellation selected may contain randomly selected constellation points. The constellation selected may be selected from a plurality of candidate constellations. The constellation selected may be selected from constellations used in previous designs.
The designing device may send the selected constellation and a signal mapped using the selected constellation to a receiving device (block 315). The designing device may send an indicator of the selected constellation, as well as transmit a signal mapped using the selected constellation to the receiving device. The designing device may receive a posteriori error rate from the receiving device (block 320). The a posteriori error rate may be a BER, a PER, a FER, and the like, measured by the receiving device using the selected constellation and the signal transmitted by the designing device. The designing device may determine if the a posteriori error rate has converged (block 325). Determining if the a posteriori error rate has converged may be accomplished by comparing the a posteriori error rate with a threshold. Alternatively, successive a posteriori error rates may be compared with each other and if a threshold is met, it may be said that the a posteriori error rate has converged. If the a posteriori error rate has not converged, the designing device may adjust the constellation (block 330). As an illustrative example, the designing device may move one or more constellation points in the constellation. The designing device may return to block 315 to send the constellation as adjusted and a signal mapped using the constellation as adjusted to the receiving device. If the a posteriori error rate has converged, the designing device may prompt the constellation to the devices (block 335). The designing device may send the constellation to the devices. The designing device may save the constellation to a memory or a database. Collectively, blocks 310, 315, 320, 325, and 330 may be referred to as designing the constellation. Blocks 320, 325, and 330 may be collectively referred to as adjusting the constellation in accordance with a design criterion.
Although the discussion of operations 300 focuses on the designing device operating in conjunction with a receiving device to design the constellation, the designing device may operate by itself to design the constellation. Instead of transmitting the signal mapped using the constellation to the receiving device, the designing device may model the impact of a channel model, modeling channel noise and/or interference, on the signal and derive the a posteriori error rate by itself. In such a situation, the design of the constellation does not require the designing device to interact with the receiving device. Furthermore, communications system resources do not have to be dedicated to the constellation design process. When operating by itself, designing device may not need to perform blocks 315 and 320. Instead, designing device may derive the a posteriori error rate in accordance with the constellation. Other parts of operation 300 may remain the same.
FIG. 4 illustrates a flow diagram of operations 400 in a receiving device participating in constellation design. Operations 400 may be indicative of operations occurring in a receiving device as the receiving device participates in constellation design with a designing device.
Operations 400 may begin with the receiving device receiving a constellation and a signal mapped using the constellation (block 405). The receiving device may receive an indication of the constellation and a transmission including the signal mapped using the constellation. The receiving device may determine a posteriori error rate (block 410). The receiving device may feedback the a posteriori error rate to the designing device (block 415). The receiving device may feedback an indication of the a posteriori error rate.
FIGS. 5a and 5b illustrate diagrams of dimensions 1 and 2 of a 2-dimensional constellation with each dimension including 32 constellation points, where the multi-dimensional constellation is designed using techniques presented herein.
FIGS. 6a-6c illustrate diagrams of dimensions 1, 2, and 3 of a 3-dimensional constellation with each dimension including 128 constellation points, where the multi-dimensional constellation is designed using techniques presented herein.
FIG. 7 illustrates an example first communications device 700. Communications device 700 may be an implementation of a designing device. Communications device 700 may be implemented as an integrated circuit or a chipset. Communications device 700 may be used to implement various ones of the embodiments discussed herein. As shown in FIG. 7, a transmitter 705 is configured to transmit packets, constellations, constellation indicators, signals mapped using constellations, and the like. Communications device 700 also includes a receiver 710 that is configured to receive packets, a posteriori error rates, a posteriori error rate indicators, and the like.
A constellation design unit 720 is configured to design constellations to meet performance parameters of a communications system. Constellation design unit 720 is configured to design the constellations based on a design criterion, such as a posteriori error rate (e.g., BER, PER, FER, and the like). Constellation design unit 720 is configured to adjust constellation points. A posteriori error processing unit 722 is configured to process received a posteriori error rates or indicators thereof. An optimizing unit 724 is configured to determine convergence of the a posteriori error rates using optimization techniques such as gradient methods, random search techniques, stochastic approximations, and the like. A memory 730 is configured to store constellation maps, performance parameters, a posteriori error rates, convergence thresholds, and the like.
The elements of communications device 700 may be implemented as specific hardware logic blocks. In an alternative, the elements of communications device 700 may be implemented as software executing in a processor, controller, application specific integrated circuit, or so on. In yet another alternative, the elements of communications device 700 may be implemented as a combination of software and/or hardware.
As an example, receiver 710 and transmitter 705 may be implemented as a specific hardware block, while constellation designing unit 720, a posteriori error processing unit 722, and optimizing unit 724 may be software modules executing in a microprocessor (such as processor 715) or a custom circuit or a custom compiled logic array of a field programmable logic array. Constellation designing unit 720, a posteriori error processing unit 722, and optimizing unit 724 may be modules stored in memory 730.
FIG. 8 illustrates an example second communications device 800. Communications device 800 may be an implementation of a communications device, such as a transmitting device and/or a receiving device. Communications device 800 may be implemented as an integrated circuit or a chipset. Communications device 800 may be used to implement various ones of the embodiments discussed herein. As shown in FIG. 8, a transmitter 805 is configured to transmit packets, signals mapped using constellations, and the like. Communications device 800 also includes a receiver 810 that is configured to receive packets, signals mapped using constellations, and the like.
A constellation processing unit 820 is configured to determine a constellation for communications device 800. Constellation processing unit 820 is configured to determine the constellation from an indicator received by communications device 800. Constellation processing unit 820 is configured to retrieve the constellation from a memory or database. A mapping/de-mapping unit 822 is configured to map data for transmission using the constellation. Mapping/de-mapping unit 822 is configured to de-map received data using the constellation. A data processing unit 824 is configured to process data prior to mapping. Data processing unit 824 is configured to process data after de-mapping. A memory 830 is configured to store constellation maps, data, indicators, and the like.
The elements of communications device 800 may be implemented as specific hardware logic blocks. In an alternative, the elements of communications device 800 may be implemented as software executing in a processor, controller, application specific integrated circuit, or so on. In yet another alternative, the elements of communications device 800 may be implemented as a combination of software and/or hardware.
As an example, receiver 810 and transmitter 805 may be implemented as a specific hardware block, while constellation processing unit 820, mapping/de-mapping unit 822, and data processing unit 824 may be software modules executing in a microprocessor (such as processor 815) or a custom circuit or a custom compiled logic array of a field programmable logic array. Constellation processing unit 820, mapping/de-mapping unit 822, and data processing unit 824 may be modules stored in memory 830.
FIG. 9 is a block diagram of a processing system 900 that may be used for implementing the devices and methods disclosed herein. Specific devices may utilize all of the components shown, or only a subset of the components, and levels of integration may vary from device to device. Furthermore, a device may contain multiple instances of a component, such as multiple processing units, processors, memories, transmitters, receivers, etc. The processing system or a portion thereof may be implemented on an integrated circuit, or a plurality of integrated circuits. In other words, the processing system or a portion thereof may be implemented as a chipset. The processing system may comprise a processing unit 905 equipped with one or more input/output devices, such as a human interface 915 (including speaker, microphone, mouse, touchscreen, keypad, keyboard, printer, and the like), display 910, and so on. The processing unit may include a central processing unit (CPU) 920, memory 925, a mass storage device 930, a video adapter 935, and an I/O interface 940 connected to a bus 945.
The bus may be one or more of any type of several bus architectures including a memory bus or memory controller, a peripheral bus, video bus, or the like. The CPU may comprise any type of electronic data processor. The memory may comprise any type of system memory such as static random access memory (SRAM), dynamic random access memory (DRAM), synchronous DRAM (SDRAM), read-only memory (ROM), a combination thereof, or the like. In an embodiment, the memory may include ROM for use at boot-up, and DRAM for program and data storage for use while executing programs.
The mass storage device may comprise any type of storage device configured to store data, programs, and other information and to make the data, programs, and other information accessible via the bus. The mass storage device may comprise, for example, one or more of a solid state drive, hard disk drive, a magnetic disk drive, an optical disk drive, or the like.
The video adapter and the I/O interface provide interfaces to couple external input and output devices to the processing unit. As illustrated, examples of input and output devices include the display coupled to the video adapter and the mouse/keyboard/printer coupled to the I/O interface. Other devices may be coupled to the processing unit, and additional or fewer interface cards may be utilized. For example, a serial interface such as Universal Serial Bus (USB) (not shown) may be used to provide an interface for a printer.
The processing unit also includes one or more network interfaces 950, which may comprise wired links, such as an Ethernet cable or the like, and/or wireless links to access nodes or different networks 955. The network interface allows the processing unit to communicate with remote units via the networks. For example, the network interface may provide wireless communication via one or more transmitters/transmit antennas and one or more receivers/receive antennas. In an embodiment, the processing unit is coupled to a local-area network or a wide-area network for data processing and communications with remote devices, such as other processing units, the Internet, remote storage facilities, or the like.
Although the present disclosure and its advantages have been described in detail, it should be understood that various changes, substitutions and alterations can be made herein without departing from the spirit and scope of the disclosure as defined by the appended claims.

## Claims

1. A method for operating a transmitting device, the method comprising:
mapping, by the transmitting device, data to a transmission symbol in accordance with a constellation map assigned to a receiving device, wherein the constellation map is designed in accordance with a posteriori error rate derived from a transmitted signal; and
transmitting, by the transmitting device, the transmission symbol.

2. The method of claim 1, further comprising determining the constellation map associated with the receiving device.

3. The method of claim 2, wherein determining the constellation map comprises receiving a first indicator of the constellation map assigned to the receiving device.

4. The method of claim 2, wherein determining the constellation map comprises assigning the constellation map to the receiving device.

5. The method of claim 1, further comprising signaling a second indicator of the constellation map to the receiving device.

6. The method of claim 1, wherein the transmitted signal is transmitted by the transmitting device, and wherein the method further comprises:
selecting an initial constellation map;
determining the a posteriori error rate of a transmission symbol mapped using the initial constellation map; and
iteratively adjusting the initial constellation map until the a posteriori error rate meets a threshold, thereby obtaining the constellation map.

7. The method of claim 6, wherein determining the a posteriori error rate comprises:
transmitting the transmission symbol and an indicator of the initial constellation map to a second device; and
receiving the a posteriori error rate from the second device.

8. The method of claim 6, wherein determining the a posteriori error rate comprises:
modeling a received version of the transmission symbol in accordance with a channel model; and
deriving the a posteriori error rate from the received version of the transmission symbol.

9. The method of claim 1, wherein the constellation map comprises a multi-dimensional constellation map.

10. A method for operating a receiving device, the method comprising:
receiving, by the receiving device, a transmission symbol from a transmitting device;
de-mapping, by the receiving device, the transmission symbol in accordance with a constellation map thereby producing received data, wherein the constellation map is designed in accordance with a posteriori error rate derived from a transmitted signal; and
processing, by the receiving device, the received data.

11. The method of claim 10, further comprising:
determining an assignment of the constellation map; and
retrieving the constellation map from a memory in accordance with the assignment.

12. The method of claim 11, wherein determining the assignment comprises one of receiving the assignment in a message, retrieving the assignment from the memory, retrieving the assignment from a server, and assigning the constellation map to itself.

13. The method of claim 10, wherein processing the received data comprises:
decoding the received data, thereby producing decoded data; and
processing the decoded data.

14. A transmitting device comprising:
a processor; and
a non-transitory computer readable storage medium storing programming for execution by the processor, the programming including instructions to:
map data to a transmission symbol in accordance with a constellation map assigned to a receiving device, wherein the constellation map is designed in accordance with a posteriori error rate derived from a transmitted signal, and
transmit the transmission symbol.

15. The transmitting device of claim 14, wherein the programming includes instructions to determine the constellation map associated with the receiving device.

16. The transmitting device of claim 15, wherein the programming includes instructions to one of receive a first indicator of the constellation map assigned to the receiving device, and assign the constellation map to the receiving device.

17. The transmitting device of claim 14, wherein the programming includes instructions to signal a second indicator of the constellation map to the receiving device.

18. The transmitting device of claim 14, wherein the transmitted signal is transmitted by the transmitting device, and wherein the programming includes instructions to select an initial constellation map, determine the a posteriori error rate of a transmission symbol mapped using the initial constellation map, and iteratively adjust the initial constellation map until the a posteriori error rate meets a threshold, thereby obtaining the constellation map.

19. A receiving device comprising:
a processor; and
a non-transitory computer readable storage medium storing programming for execution by the processor, the programming including instructions to:
receive a transmission symbol from a transmitting device,
de-map the transmission symbol in accordance with a constellation map thereby producing received data, wherein the constellation map is designed in accordance with a posteriori error rate derived from a transmitted signal, and
process the received data.

20. The receiving device of claim 19, wherein the programming includes instructions to determine an assignment of the constellation map, and retrieve the constellation map from a memory in accordance with the assignment.

21. The receiving device of claim 19, wherein the programming includes instructions to decode the received data, thereby producing decoded data, and process the decoded data.