Y v7
`
`CALIFORNIA INSTITUTE OF TECHNOLOGY
`JET PROPULSION LABORATORY
`
`New Technology Reporting Form
`
`NTR Number: 44810
`
`Title: New Constellations for Communications Signalling: Design Methodolgy and Method and
`Apparatusfor the New Signalling Scheme
`
`New Technology Description
`
`Novelty - Describe what is new anddifferent about your work. Attach supporting material
`if necessary.
`
`Wepropose newconstellations to be used with capacity approaching codes such as LDPC or
`Turbo Codes. The new constellations are unequally spaced, and are designed to target a
`specific user data rate in contrast to traditional constellations. The new constellations are
`designed to maximize either the joint capacity or the parallel decoding capacity at a target user
`data rate. These constallations achieve a smaller gap to the ultimate Shannon limit. Simulations
`results have shown gains of more than 1dB comparedtotraditional constellations.
`
`Technical Disclosure
`Problem - Motivation that led to developmentor problem that was solved.
`
`Theintroduction of Turbo Codes and LDPC codesin the nineties allowed for very powerful
`coding schemesachieving near Shannon capacity performance for BPSK/ QPSK. However,
`the gap to capacity increases with bandwidth efficiency (ie as more bits are packed per
`transmitted symbol) when using traditional constellations with modern codes. While the modern
`codesare highly optimized, the traditional constellations aren't.
`
`Solution
`
`Wedeveloped new constellations that are:
`1) unequally spaced
`2) jointly optimized for location and bit labels
`3) designed to target a specific user data rate
`4) are designed to maximize either the joint capacity or parallel decoding capacity.
`5) achieve a smaller gap to the Shannonlimit
`
`Description
`
`As per the attached document, using numerical optimization we designed PAM constellations
`for different bandwidth efficiencies and different user data rates. We also give a sample
`optimized PSK constellation. Tables of these constellations can be provided upon requestfor a
`patent application or any other purpose. QAM constellations can be constructed using the
`optimized PAM constellations.
`
`Page1 “Proprietary Information
`
`LGE 1010
`
`LGE 1010
`
`1
`
`

`

`Constellation Design via Capacity Maximization
`
`Maged F. Barsoum
`Jet Propulsion Laboratory
`California Institute of Technology
`Pasadena, CA 91109
`mbarsoum @jpl.nasa.gov
`
`Christopher Jones
`Jet Propulsion Laboratory
`California Institute of Technology
`Pasadena, CA 91109
`crjones @jpl.nasa.gov
`
`Abstract— Traditional constellations are uniformally spaced.
`By giving up uniform spacing, constellations can be designed to
`have larger joint (i.e. overall) capacity or parallel decoding ca-
`pacity. In this paper non-uniformally spaced (i.e. ’geometrically’
`shaped) constellations are designed to maximize either of these
`quantities. By way of numerical capacity computations we show
`that except
`in special cases, there are no universally optimal
`geometrically shaped constellations across all code rates, and
`that the optimization of a constellation has to target a specific
`code rate. Unlike joint capacity, optimizing for parallel decoding
`capacity is label dependent. For PAM and PSKconstellations, we
`found the maximum parallel decoding capacity to be achieved
`using gray labels. However, for PAM constellations, not all gray
`labels can yield the highest parallel decoding capacity. The
`conventional wisdom of using a (log2(M1) —1)/loga(M) code rate
`with an M points constellation for bandwidth efficient commu-
`nications, could be re-evaluated in light of the newly developed
`constellations. An optimized constellation is used with a state-
`of-the-art LDPC code and simulation results are presented. This
`paper also draws a distinction between the practically complex
`probabilistic shaping and geometric shaping and in fact proves
`under broad conditions, that any gain in capacity which can be
`found via probabilistic shaping can also be achieved or exceeded
`solely through geometric shaping.
`
`I.
`
`INTRODUCTION
`
`Constellation design has not traditionally been parameter-
`ized by the target code rate. This: paper, however, argues by
`way of mutual information computations, that there is nearly
`always link margin to be gained through tailoring the design
`of a constellation for a specific coderate.
`Although the minimum distance between constellation
`points is indicative of the capacity of a constellation at
`relatively high SNR’s only, historically, constellations have
`most often been designed to maximize such minimum distance
`[6]. Because it had been noted,
`that
`increasing the dimen-
`sionality of a constellation allowed for a larger minimum
`distance for the same constellation energy per dimension,
`several researchers addressed the problem of designing multi-
`dimensional constellations with good minimum distance prop-
`erties e.g. [9][10][11][12][7][8]. Multi-dimensional constella-
`tions were often useful in the contextof set-partitioning [5], for
`trellis-coded modulation systems. However,in all these efforts
`the fundamental capacity of the constellation remained limited
`by a design that targeted the minimum distance, a measure that
`is more indicative of the performance of an ucoded system,
`but not well indicative of the capacity of a constellation at the
`
`SNR’s of actual operation particularly with today’s modern
`codes,
`
`Shaping techniques provide an alternative approach for
`improving energy efficiency. The term shaping is traditionally
`applied to techniques that attempt to approximate the capacity
`achieving Gaussian input distribution by transmitting some
`constellation points with greater frequency than others, an op-
`eration which poses several practical difficulties. An example
`of a more practical shaping mechanism is given by Raphaeli
`in [1]. In section V, we show under broad conditions that any
`gain in capacity that can be achieved by probabilistic shaping
`can also be achieved by equiprobable but non-uniformally
`spaced signaling i.e. geometrical shaping.
`Sun et al. [13] showed that with asymptotically large M,
`equiprobable, but non-uniformly spaced signaling can achieve
`the Gaussian input distribution. This approach can be ap-
`proximated for finite M in an attempt
`to mimic Gaussian
`disitrbutions as, for example, in [3][4]. However, approaches
`that mimic the Gaussian inputdistribution do not parameterize
`designs based on the code rate, and are also limited to the
`design of PAM constellations only. In this paper, we show that
`one can do muchbetter if the target code rate is parameterized
`in the optimization, and the location of constellation points
`allowed to be optimized further. For example, Sommer and
`Fettweis [3] achieve a 0.8 dB gain in parallel decoding ca-
`pacity for PAM-32 at rate-1/2, while an optimization targeting
`rate-1/2 for PAM-32 can achieve a 1.5 dB gain over standard
`PAM-32, as will be shown here.
`
`II. DESIGN METHODOLOGY
`
`A multi-dimensional constellation can be parameterized by
`the number of dimensions and the number of constellation
`points. As will be seen, the optimal design of a constellation
`dependsonthe target code rate to be used with it. The number
`of user bits per dimension, 7, is related to code rate, R, and the
`total numberof real signaling dimensions, Naim, as follows:
`_ R (logs (M))
`Nadim
`0
`Modern systems employing LDPC or turbo codes can
`operate near channel capacity. In systems where there are
`no belief propagation iterations between the decoder and the
`constellation demapper,
`the constellation demapper can be
`thought of as part of the channel. Since modern codes operate
`
`2
`
`

`

`PAM 2
`
`- — - PAM 16
`PAM 32
`
`—s= PAM 4
`tenes PAM 8
`— — -PAM 16
`PAM 32
`=~ Gaussian Capacity
`
`Capacity
`
`inbits -5
`croton Gaussian Capacity PAM 2
`
`(b)
`(a) Parallel Decoding Capacity of PAM constellations together with the Gaussian Capacity curve. (b) Capacity of PAM constellations together with
`Fig. I.
`the Gaussian Capacity curve.
`
`0
`
`5
`
`10
`
`20
`15
`SNR in dB
`
`25
`
`30
`
`35
`
`40
`
`it would make sense to
`very close to the channel capacity,
`design constellations that maximize the channelcapacity, again
`viewing the channel to include the demapper. For decoders of
`modern codes operating onbit likelihoodratios, the capacity of
`the channel defined as such is the parallel decoding capacity,
`given by
`i-1
`Cpp = Yo 1(Xi,Y)
`i=0
`
`where X; is the é” bit of the i-bits transmitted symbol, and
`Y is the received symbol. With belief propagation iterations
`between the demapper and the decoder of a modern code,
`the demapper can no longer be viewed as part of the channel,
`and the joint capacity of the constellation becomesthe tightest
`known bound on the system performance. However, practical
`evidence shows that
`the performance gain due to iterating
`between the demapper and the decoderis not significant when
`the codeitself is a modern iterative code such as an LDPC or
`a turbo code. This phenomena can be seen in the simulation
`results of Section IV. Foriterative codes, the parallel decoding
`capacity therefore remains a very good indicator of the system
`performance even with iterations between the demapper and
`the decoder.
`
`While some researchers have previously attempted to opti-
`mize the bit labels of traditional constellations for one function
`or the other, the approach will take here is to jointly optimize
`the location of the constellation points and the labels. We do
`this by finding the optimal constellation points corresponding
`to the labels.
`
`Besides designing constellations that maximize the parallel
`decoding capacity, we also design other constellations to
`
`maximize the joint capacity. Besides the theoretical value of
`joint capacity maximizing constellations, in some systems the
`capacity of the channel as viewed by the decoderis the joint
`capacity of the constellation. One example of such systems, is
`systems based on non-binary codes such as non-binary LDPC
`codes, that operate directly on non-binary symbols rather than
`bits.
`
`In our optimization process, constellations were constrained
`using lower and upper bounds, with one constellation point
`fixed at the upper bound. This limits the search space with-
`out excluding the optimal solution. No additional constraints
`were placed on the energy of the constellation because the
`capacity computation kernel used signal-to-noise ratio, and
`adjusted the energy of the noise based on the energy of
`the constellation (the signal-to-noise ratio is defined in this
`paperasratio of the constellation energy per dimension to the
`noise energy per dimension). It can easily be shown that an
`optimal constellation will have the property that the mean of
`all the constellation points is exactly zero. As such, we found
`that adding a zero mean constraint helps the optimization
`routine converge faster. To optimize at a particular user data
`rate, the process is iterative because the optimal SNR is not
`known at the beginning. The constellation is optimized for
`an initial SNR guess. The SNR at which this constellation
`gives the required user date rate is then used for finding a new
`constellation. The process repeats and the SNR’s found every
`time converge. While there is no proofthat the solutions found
`are globally optimum, repeating the optimization process with
`different starting random points increases the confidencein the
`optimality of the solutions found.
`
`3
`
`

`

`A. PAM Constellations
`
`III. EXAMPLES
`
`In this section, we will present different PAM constellations
`optimized for several user data rates. We start by presenting
`the joint capacity and the parallel decoding capacity for classic
`constellations at different SNR’s. Figure 1 (b) showsthe joint
`capacity for the classic PAM 2, 4, 8, 16 and 32,
`together
`with the Gaussian capacity. Figure 1
`(a) shows the parallel
`decoding capacity for the same constellations together with
`‘the Gaussian capacity. To better view the differences between
`these curves at points close to the Gaussian capacity, we will
`instead plot the SNR gap to Gaussian capacity for different
`values of capacity for each constellation as shown in Fig.2.
`It is interesting to note that unlike the joint capacity, at the
`same SNR,theparallel decoding capacity does not necessarily
`increase with the number of constellation points for classic
`constellations. Hereinafter, we will present the results of our
`optimized constellations using plots of SNR gap to capacity
`
`span.
`ratioofouterinter-pointdistancetooverall
`
`
`
`0.25
`
`0.2
`
`0.15
`
`0.1
`
`0.05
`
`SNR in dB
`
`
`
`
`
`~~} Naralle! decoding capacity-exhaustive search
`©
`parallel decoding capacity—optimization
`——%*—— joint capacity-exhaustive search
`1
`joint capacity-optimization
`
`r versus SNR for PAM 4 constellations optimized for joint
`Fig. 3.
`capacity/parallel decoding capacity
`
`as donein figure 2.
`
`
`SNRgaptoGaussianCapacityindB
`
`
`
`2) PAM 4: We have designed 4 PAM constellations using
`two approaches. The first
`is an exhaustive search with a
`resolution of 0.002 with -1 and 1 as the lower and upper
`bounds on all
`the constellation points. The second is the
`optimization technique described earlier. The results agree.
`At all user data rates, we found the optimized PAM 4
`constellations to be symmetric around the origin. We will
`denote the location of the 4 points on the real line as —a,
`—b, b, a, from left to right. The constellation can therefore be
`fully described by the ratio
`Parallel Decoding Capacity
`1 &
`
`/& :|= — Joint Capacity
`_a—b
`= 2*a
`
`005 175 2
`25
`3
`35
`4
`45
`5
`Figure 3 shows r for constellations optimized for joint ca-
`Capacity
`pacity/ parallel decoding capacity at different SNR’s. As seen
`in the figure, at low SNR’s PAM 4 constellations optimized
`for joint capacity are very different from those optimized for
`parallel decoding capacity. A constellation optimized for joint
`capacity will have b = 0 i.e. it will look like a 3 points equally
`spaced constellation with two of the four symbols mapped
`to the same constellation point located at 0. A constellation
`optimized for parallel decoding capacity will have b = a i.e.
`it will look like a BPSK constellation with two of the four
`symbols mapped to a and the other two mapped to —a.
`Asseen also in Fig. 3, at high SNR’s it makes negligible
`difference whether a PAM 4 constellation is optimized for joint
`capacity or parallel decoding capacity. As the SNRincreases, r
`approaches 1/3,i.e. the constellation becomes equally spaced.
`This illustrates that constellations designed to maximize the
`
`SNR gap to Gaussian Capacity for the Joint Capacity and Parallel
`Fig. 2.
`Decoding Capacity of 2,4,8,16 and 32 PAM constellations
`
`1) PAM 2: For PAM 2,it is clear that the joint capacity
`will always be equal to the parallel decoding capacity, since
`there is only one bit
`to be transmitted. At any code rate,
`it
`is straightforward to show analytically that any optimal
`constellation will always have a mean of zero. For PAM 2,
`satisfying this condition implies that if one point is placed at
`zx, the other one has to be placed at —z. The value of « can be
`viewed as a scaling factor that only changes the power of the
`constellation, but clearly won’t changed the performance of
`the constellation at any fixed SNR. As such, the classic PAM
`2 (or rather BPSK), is optimal at all coderates.
`
`4
`
`

`

`°
`
`e
`
`minimum distance between constellation points are well suited
`for high SNR’s (as may be used, for example,
`in uncoded
`systems).
`3) Other PAM constellations: After examining the design
`on PAM 4 constellations in detail in the previous section, we
`will now present a summary of the results for the design of
`PAM 8, 16, and 32. We have optimized the constellations
`for joint capacity and parallel decoding capacity for different
`target user bits per dimension (i.e. code rates). As already seen
`for PAM 4, optimized constellations are different depending
`on the target user bits per dimension and also depending
`on whether they have been designed to maximize the joint
`capacity or the parallel decoding capacity. For all the PAM
`constellations examined and at all code rates, we found that
`the labels that maximize the parallel decoding capacity are
`gray. However, not all gray labels can achieve the maximum
`possible decoding capacity even with the freedom to place
`the constellation points anywhere on the real
`line. Figure
`4 (a) shows the SNR gap to Gaussian capacity for each
`constellation we optimized for joint capacity. Figure 4 (b)
`shows the SNR gap for each constellation we optimized for
`parallel decoding capacity. Again,it should be emphasized that
`each ’+’ on the plot represents a different constellation. Tables
`showing the optimized constellations could be given upon
`request for a patent application or any other purposes. While
`we have so far optimized PAM constellations and some PSK
`constellations only, the optimized constellations may include
`QAM, PSK, Multi-dimesional, as well as multi-dimensional
`spherical constellations.
`
`B. PSK Constellations
`
`In this section we will show sample results for PSK con-
`stellations. Figure 5 shows a 16 points PSK constellation
`optimized for joint capacity and another one optimized for
`parallel decoding capacity at SNR=8.87 dB. The constellation
`optimized for joint capacity is equally spaced while the one
`optimized for parallel decoding capacity isn’t. However,it is
`gray labelled and hasinteresting symmetry properties. We con-
`jecture that all PSK or even multi-dimensional spherical(i.e.
`equal magnitude) constellations optimized for joint capacity
`will always be uniformally spaced regardless of the coderate,
`they are optimized for.
`
`IV. PERFORMANCE WITH MODERN CODES
`
`In this section, sample simulation results of BICM systems
`using LDPC codesare presented. We compare the performance
`of two BICM systems, one using the classic 32 points PAM
`constellation and the other using our optimized 32 points PAM
`constellation. A rate 1/2 AR4A LDPC code is used with a
`codeword size of 8 kbits and 16 kbits. Simulation results are
`presented in Fig. 6. As seen in the figure there is a significant
`SNRgap between the two systems (around 1.2 dB). It is also
`clear that performance does not improve muchbyiterating
`between the demapper and the decoder as pointed outearlier.
`
`0110
`
`1
`
`-0.5
`
`0
`
`0.5
`
`+
`*
`
`Optimized for Parallel Decoding Capacity
`Optimized for Joint Capacity
`
`A labelled 16 PSK constellation optimized for Parallel Decoding
`Fig. 5.
`Capacity at SNR=8.87 dB along with a non-labelled constellation optimized
`for Joint Capacity at the same SNR
`
`+0111 -1
`FER ~ © ~ PID Opt PAM32 w/iter, k=4096
`
`
`~ & ~ PAM32 w/iter, k=4096
`
`
`~~-— PID Opt PAM32, k=4096
`
`
`——~&— PAM32, k=4096
`--@-- PID Opt PAM32, k=16384
`
`~—-@-— PAM32, k=16384
`
`Simulation results for a BICM system using a rate 1/2 LDPC code
`Fig. 6.
`for the classic and the optimized PAM 32 constellation
`
`VY. GEOMETRIC SHAPING VERSUS PROBABILISTIC SHAPING
`
`Using the notation of [14] we compare the mutual informa-
`tion of systems with input alphabets 1 and S with elements z
`and s drawn from random variables X and S that exist in R”
`and have equal powerconstraints EX? = ES? = P. Symbols
`from one or the other alphabet are used to communicate
`across a channel
`that is specified only in so much that its
`output alphabetis given by Y. Furthermore, the probability of
`symbols x € % are constrained to be uniform p(z) = p>
`while the probability of symbols s
`S form any vai
`
`5
`
`€
`

`

`= a
`
`SNRgaptoGaussian
`
`capacity 0.5
`
`classic constellations
`
`~~ -k ~ optimized constellations
`
`
`
`
`0
`
`3
`25
`05 4145 2
`Capacity in bits
`
`classic constellations
`— + ~ optimized constellations
`
`35
`
`indB
`
`SNRgaptoGaussianCapacity
`
`4
`
`45
`
`§
`
`(b)
`Fig. 4.
`(a) SNR gap to Gaussian Capacity for the joint capacity of the classic and the optimized PAM 2,4,8,16 and 32 constellations (from left to right
`respectively). (b) Gap between the Parallel Decoding Capacity and Gaussian Capacity for the optimized and the classic constellations.
`
`(a)
`
`probability density function. Based on the above,the following
`propositions describes probabilistic shaping as a special case
`of geometric shaping,
`Proposition 1 (Shaping): For any given alphabet S with
`rational p(s)Vs € S there exists an alphabet V with p(x) =
`Tay such that I(X;Y) > I(S;Y).
`Proof: Allow |4| > |S|. Define |S| subgroups G; € ”
`and let 9; = s; fori =1,...,|S|. Map elements from ¥ into
`G such that the i‘ subgroup has Zl = p(s,). This yields
`I(X;Y) = 1(G;Y) = I(S;Y). Releasing the constraint that
`elements in 4 precisely map to {S| possible elements in G
`permits the inequality.
`a
`Corollary 2: The cardinality, |4’], of the set of equiprobable
`points 7 is no less than the lowest common multiple of the
`denominators of the rational fractions that define p(s;) for
`t=1,..., |S].
`
`VI. CONCLUSION
`
`In this paper we have shownthat constellations should be
`designed to target a specific rate in to achieve a smaller gap
`to the ultimate Shannon limit.
`
`ACKNOWLEDGMENTS
`
`This research in part was carried out at the Jet Propulsion
`Laboratory, California Institute of Technology, under a con-
`tract with NASA.
`
`REFERENCES
`
`({1] D. Raphaeli and A. Gurevitz, “Constellation shaping for pragmatic turb-
`coded modulation with high spectral efficiency,” JEEE Trans. on Comm.,
`vol. 52, pp. 341~345, March 2004.
`[2] G. Foschini, R. D. Gitlin, and S. B. Weinstein, “Optimization of two-
`dimensional signal constellations in the presence of gaussian noise,” IEEE
`Trans. on Comm., vol. 22, pp. 28-38, Jan. 1974.
`
`{8]
`
`(9]
`
`[4]
`
`[5]
`
`[6]
`
`(7=
`
`[3] D. SommerandG.P. Feitweis, “Signal shaping by non-uniform QAM for
`AWGNchannels and applications using turbo coding,” ITG Conference
`on Source and Channel Coding, pp. 81-86, Jan. 2000.
`C. Fragouli, R. D. Wesel, D. Sommer, and G. P. Fettweis, “Turbo
`codes with non-uniform constellations,” /EEE International Conference
`on Communications, pp. 70-73, June 2001.
`G. Ungerboeck, “Channel coding with multilevel/phase signals,” IEEE
`Trans. on Info. Theory, vol. 28, pp. 55-67, Sept. 1981.
`D. Forney, R. Gallager, G. R. Lang, F. M. Longstaff, and S. U. Qureshi,
`“Efficient modulation for band-limited channels,” JEEE Journal on Sel.
`Areas in Comm., vol. 2, pp. 632-647, Sept. 1984.
`J. Conway and N. J. A. Sloane, “A fast encoding method forlattice codes
`and quantizers,” IEEE Trans. on Info. Theory, vol. 29, pp. 820-824, Nov,
`1983.
`K. Ruotsalainen, “On the construction of the higher dimensional constel-
`lations,” IEEE International Conference on Info. Theory, pp. 490, July
`2002.
`D. Forney, L. -F. Wei, “Multidimensional constellations - part I : introduc-
`tion, figures of merit, and generalized cross constellations,” IEEE Journal
`on Sel. Areas in Comm., vol. 7, pp. 877-892, Aug. 1989.
`[10} D. Forney, “Multidimensional constellations - part II : voronoi constel-
`lations,” IEEE Journal on Sel. Areas in Comm., vol. 7, pp. 941-958, Aug.
`1989.
`[11] J. Hamkins and K. Zeger, “Asymptotically dense spherical codes- part I :
`wrapped spherical codes,” IEEE Trans. on Info. Theory, vol. 43, pp. 1774~
`1785, Nov. 1997.
`[12] J. Hamkins and K. Zeger, “Asymptotically dense spherical codes - part
`II: laminated spherical codes,” IEEE Trans. on Info. Theory, vol. 43,
`pp. 1786-1798, Nov. 1997.
`[13] F. -W. Sun, H.C. A. van Tilborg, “Approaching capacity by equiprobably
`signaling on the Gaussian channel,” IEEE Trans. on Info. Theory, vol. 39,
`pp. 1741-1716, Sept. 1993.
`[14] T. Cover and J. Thomas, “Elements of information theory,” John Wiley
`and Sons, 1991.
`
`6
`
`