Gray Coding =========== .. author jgaeddert Joseph D. Gaeddert .. date January 1, 1975 .. location Boston, MA .. header /doc/cpfskmodem/banner.png .. keywords continuous phase, frequency shift keying, FSK, modem, Gauss, minimum shift keying, CPFSK, FSK, GMSK, MSK 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. .. code-block:: 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: .. code-block:: 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|, Gray encoding and decoding are computed with the ``gray_encode()`` ``gray_decode()`` methods, respectively. .. attention:: Add example and graphic here