Gray Coding

In order to reduce the number of bit errors in a digital modem, all symbols are automatically Gray encoded such that adjacent symbols in a constellation differ by only one bit. For example, the binary-coded decimal (BCD) value of 183 is 10110111. It has adjacent symbol 184 (10111000) which differs by 4 bits. Assume the transmitter sends 183 without encoding. If noise at the receiver were to cause it to demodulate the nearby symbol 184, the result would be 4 bit errors. Gray encoding is computed to the binary-coded decimal symbol by applying an exclusive OR bitmask of itself shifted to the right by a single bit.

        10110111    bcd_in (183)        10111000    bcd_in (184)
        .1011011    bcd_in >> 1         .1011100    bcd_in >> 1
xor :   --------                        --------
        11101100    gray_out (236)      11100100    gray_out (228)

Notice that the two encoded symbols 236 (11101100) and 228 (11100100) differ by only one bit. Now if noise caused the receiver were to demodulate a symbol error, it would result in only a single bit error instead of 4 without Gray coding.

Reversing the process (decoding) is similar to encoding but slightly more involved. Gray decoding is computed on an encoded input symbol by adding to it (modulo 2) as many shifted versions of itself as it has bits. In our previous example the receiver needs to map the received encoded symbol back to the original symbol before encoding:

        11101100    gray_in (236)       11100100    gray_in (228)
        .1110110    gray_in >> 1        .1110010    gray_in >> 1
        ..111011    gray_in >> 2        ..111001    gray_in >> 2
        ...11101    gray_in >> 3        ...11100    gray_in >> 3
        ....1110    gray_in >> 4        ....1110    gray_in >> 4
        .....111    gray_in >> 5        .....111    gray_in >> 5
        ......11    gray_in >> 6        ......11    gray_in >> 6
        .......1    gray_in >> 7        .......1    gray_in >> 7
xor :   --------                        --------
        10110111    gray_out (183)      10111000    gray_out (184)

There are a few interesting characteristics of Gray encoding:

• the first bit never changes in encoding/decoding

• there is a unique mapping between input and output symbols

It is also interesting to note that in linear modems (e.g. PSK), the decoder is actually applied to the symbol at the transmitter while the encoder is applied to the received symbol at the receiver. In liquid-dsp, Gray encoding and decoding are computed with the gray_encode() gray_decode() methods, respectively.

Attention

Add example and graphic here