Gray Coding

The defining property of Gray coding is that any two constellation points sharing a Voronoi region boundary differ in exactly one bit position. This is not a natural binary sequence but a re-mapped ordering. For example, in standard binary, the transition from 3 (011) to 4 (100) flips three bits, but in Gray code, the sequence is 3 (010) to 4 (110), flipping only the most significant bit. This geometric constraint ensures that when additive white Gaussian noise (AWGN) pushes a received symbol across a decision boundary into an adjacent region, only a single bit error occurs.

In high signal-to-noise ratio (SNR) regimes, symbol errors are dominated by nearest-neighbor misclassifications. Gray coding directly minimizes the Bit Error Rate (BER) by ensuring each dominant symbol error event causes only one bit flip. The theoretical approximation for Gray-coded M-ary modulation is:

• BER ≈ Symbol Error Rate / log2(M) This relationship holds because each symbol carries log2(M) bits, and a single symbol error corrupts exactly one bit. Without Gray coding, a single symbol error could corrupt multiple bits, degrading BER performance by up to a factor of log2(M).

The Hamming distance between the bit labels of any two adjacent constellation points is exactly 1. This is the fundamental algebraic property that distinguishes Gray coding from arbitrary symbol mappings. Key implications:

• The mapping is an isometry between the geometric adjacency graph of the constellation and the hypercube graph of the binary labels.
• For Quadrature Amplitude Modulation (QAM) constellations, perfect Gray coding exists only when the constellation forms a rectangular grid where each dimension's pulse amplitude modulation (PAM) levels can be independently Gray-coded.
• For non-rectangular constellations like Amplitude Phase Shift Keying (APSK) or cross-QAM, true Gray coding may not exist, requiring approximate or quasi-Gray mappings.

Gray code for one-dimensional PAM, which extends to two-dimensional QAM, is generated using the reflected binary code algorithm:

• Start with a 1-bit code: [0, 1]
• To generate n+1 bits, reflect the n-bit code (reverse the list) and prefix the original half with 0 and the reflected half with 1.
• Example: 2-bit code = [00, 01, 11, 10]; 3-bit code = [000, 001, 011, 010, 110, 111, 101, 100]. For M-QAM, the in-phase and quadrature components are independently mapped using this PAM Gray code, producing a two-dimensional labeling where both horizontal and vertical neighbors differ by one bit.

Gray coding significantly improves the performance of soft-decision forward error correction (FEC) decoders, such as low-density parity-check (LDPC) and turbo codes. The mechanism:

• Soft demappers compute log-likelihood ratios (LLRs) for each bit based on the received symbol's position relative to all constellation points.
• Under Gray mapping, the LLR for a given bit depends primarily on the nearest decision boundary for that bit position, simplifying computation and reducing correlation between bit LLRs.
• This near-independence of bit LLRs aligns with the assumption of most binary FEC decoders, preventing the iterative decoding process from being misled by correlated bit error patterns that occur with non-Gray mappings.

Perfect Gray coding is not universally achievable:

• Cross-QAM constellations (e.g., 32-QAM, 128-QAM) have non-rectangular shapes where corner points have fewer than four neighbors, breaking the perfect grid adjacency required for true Gray coding.
• APSK constellations with multiple concentric rings create adjacency patterns where a point may have more neighbors than available single-bit-difference labels.
• In these cases, quasi-Gray mapping algorithms minimize the average Hamming distance between adjacent points using search heuristics or integer programming. The result is a mapping where most, but not all, adjacent pairs differ by one bit, with the remaining pairs differing by two bits.