# systematic way to determine best bit mapping policy

So in class, we've been asked to find the best bit mapping policy for QAM modulation schemes (4-QAM, 8-QAM, 128-QAM, etc). Best meaning the one that will provide the lowest bit error Probability ($P_{be}$). I think I understand the concept, which is for each point closest to a given point, try to change the fewest number of bits. The absolute best case is gray coding, but that would only be possible for 4-QAM.

For example, I can come up with the best bit mapping policy for the star 8-QAM constellation below. ( the points are numbered in red)

for outside points (points 1,3,5, and 7) I'm making sure that the two closest points to each only 1 bit changes. So point 1 = 000, and point 2 = 100 (only the Most significant bit changed) and points 8 = 001 (only the least significant bit changed). For the 8-QAM, it's small enough that Just pick a random bit combination for the outside points, and then try to only change 1 bit to get to the center, but for a 16-QAM, for even a 256-QAM this starts getting difficult to just go about picking at random.

So my question is this; Is there a systematic way to go about selecting the bit mapping for these larger constellations?

Also, once we find the bit mapping policy, how can we calculate the bit error probability $P_{be}$? I know how to find the symbol error probability $P_{es}$, and i know for gray coding $P_{be} = \frac{P_{es}}{log_2 M}$ where $M$ is the number of symbols (for 8-QAM $M = 8$). but since everything higher than 4-QAM can only be partial gray coding, how do we determine $P_{be}$ in terms of $P_{es}$?

• Note that Gray coding is possible beyond 4-QAM. – MBaz Mar 19 '16 at 23:29
• just a dumb question: why are Gray codes useful here? is this like Offset QPSK where only one bit is expected to flip at a time? – robert bristow-johnson Mar 20 '16 at 1:43
• and it seems to me that if you want like codes to be closer together, you might want to swap points 6 (010) and 7 (011) in your constellation. in fact, whatever you do with the 111 point (and those closest to it, 110, 101, 011) and the 000 point (and those closest to it, 001, 010, 100), i would treat those two sets as a sorta mirror image of each other. so i would also swap points 1 and 8. – robert bristow-johnson Mar 20 '16 at 1:53
• @robertbristow-johnson ahh, yeah that would make a lot more sense! thanks! I tried to make points 1 and 5 have opposite bits, but I was having trouble. but if i saw points 1 and 8, and points 2 and 3 then everything would be symmetric. Thanks for pointing that out! it was bugging me that things weren't symmetric! – gerrgheiser Mar 20 '16 at 3:07
• @MBaz can full gray coding be used beyond 4-QAM? I just looked a couple different mapping schemes up, and I think that makes sense. I guess you can use gray coding on anything 64-QAM and beyond, is that right? because on point will never have more than 4 "closest" neighbors. Does that sound correct? – gerrgheiser Mar 20 '16 at 3:11

In general, the method to follow is:

• Find the distance between each pair of points.
• Select one point and assign it a label (a set of bits).
• Then, put its closest neighbors in set A, its second closest in set B, and so on.
• Label (assign bits to) points in set A so that only one bit is different from the starting point, label points in set B so that two bits are different, and so on.
• Verify that the labeling works for all points.

It make take several tries before you find a good labeling scheme. As far as I know, there is no general algorithm guaranteed to work for any constellations, but Gray labelings are known for all the main constellations.

Note that in the example you posted, your proposed labeling is not necessarily correct. For example, the labeling might change depending on whether the distance between 2 and 4 is longer or shorter than the distance between 5 and 4. That is why you need to find the distances before you start labeling.

For $2^{2n}$-QAM, Gray code labeling often assigns the odd-numbered bits to one axis (I or Q) and the even-numbered bits to the other axis (Q or I) and uses $n$-bit Gray code labeling along each axis. Alternatively, the first $n$ bits could be assigned to I (or Q) and the last $n$ bits to Q (or I). Depending on the structure of the modulator (e.g. 8 bits entering the modulator on a serial line versus 8 bits entering the modulator simultaneously on a 8-bit-wide bus), one method might be preferable over the other. It is important to note that it is not necessary to convert the data into Gray code; just to use the Gray code labeling. An extensive discussion of this last point can be found here on Google Groups.