Extended binary Golay code G24

Equations

• n = 24, k = 12, d = 8, t = 3
• G23: 2^12 * sum_{i=0}^{3} C(23,i) = 2^23 (perfect)
• A(x) = 1 + 759 x^8 + 2576 x^12 + 759 x^16 + x^24

Quantities

Definitions

• G24 is a binary linear code of length 24, dimension 12, minimum Hamming distance 8.
• It is obtained by adding an overall parity bit to the perfect cyclic Golay code G23 = [23, 12, 7].
• Weight enumerator: 1 + 759 x^8 + 2576 x^12 + 759 x^16 + x^24. It is self-dual and Type II.
• Any 3 bit flips are uniquely correctable (t = floor((d-1)/2) = 3). Covering radius is 4; the code is not perfect.

Assumptions

• · Alphabet F_2. Hamming metric.
• · The generator polynomial of the underlying cyclic G23 is 1+x+x^5+x^6+x^7+x^9+x^11, extended by an overall parity bit.

Mechanism

A 12-bit message is multiplied by the G23 generator polynomial and given a 24th parity bit. Nearest-codeword decoding restores any pattern of at most three bit flips.

Evidence

• theorem

  Pless, On the uniqueness of the Golay codes

• calculation

  UPI software enumerator: 4096 codewords, declared weights, minimum distance 8

Primary sources

• Golay, Notes on digital coding (1949)
• MacWilliams & Sloane, The Theory of Error-Correcting Codes

Predictions

• Every pattern of at most three bit flips on a codeword decodes uniquely to that codeword.
• No linear binary [24, 12] code has distance greater than 8.

Falsification

• A software codeword of weight other than 0, 8, 12, 16, 24.
• A received word at distance ≤ 3 from two distinct codewords.

Key concepts

Tags

Bridges

• in · DERIVED_FROMLeech lattice Λ24
• in · DERIVED_FROME8 root lattice
• in · DERIVED_FROMQuantum error correction as syndrome measurement