Algebraic and Stochastic Coding Theory

7

Golay Codes

7.1    Perfect Codes

Perfect codes have been introduced in §6.5 in connection with the Hamming bound (6.5.1) which for a q-ary code C = (n,k,d) with d ≤ 2t + 1 implies that

$\left|C\right|{\displaystyle \sum _{i=0}^t\left(\begin{array}{l}n\\ i\end{array}\right){(q-1)}^i\le q^n,}$

(7.1.1)

where |C| (= M) denotes the size of the code C (see §6.1) A code is said to be perfect if equality holds in (7.1.1). Since a terror correcting code can correct up to t errors, a perfect t-error correcting code must be such that every codeword lies within a distance of t to exactly one codeword. In other words, if the code has d_min = 2t + 1 that covers radius t, where the covering radius has the smallest number, then every codeword lies within a distance of the Hamming radius t to a codeword. In the case of a perfect code, the ...