\( \newcommand{\matr}[1] {\mathbf{#1}} \newcommand{\vertbar} {\rule[-1ex]{0.5pt}{2.5ex}} \newcommand{\horzbar} {\rule[.5ex]{2.5ex}{0.5pt}} \newcommand{\E} {\mathrm{E}} \)
abstract banner
Show Question
\( \newcommand{\cat}[1] {\mathrm{#1}} \newcommand{\catobj}[1] {\operatorname{Obj}(\mathrm{#1})} \newcommand{\cathom}[1] {\operatorname{Hom}_{\cat{#1}}} \newcommand{\multiBetaReduction}[0] {\twoheadrightarrow_{\beta}} \newcommand{\betaReduction}[0] {\rightarrow_{\beta}} \newcommand{\betaEq}[0] {=_{\beta}} \newcommand{\string}[1] {\texttt{"}\mathtt{#1}\texttt{"}} \newcommand{\symbolq}[1] {\texttt{`}\mathtt{#1}\texttt{'}} \newcommand{\groupMul}[1] { \cdot_{\small{#1}}} \newcommand{\groupAdd}[1] { +_{\small{#1}}} \newcommand{\inv}[1] {#1^{-1} } \newcommand{\bm}[1] { \boldsymbol{#1} } \newcommand{\qed} { {\scriptstyle \Box} } \require{physics} \require{ams} \require{mathtools} \)
Math and science::INF ML AI

Hamming codes

Linear codes can be understood as using a matrix \( G \) to encode a message vector \( s \) into the transmitted vector \( t \), \( t = G^T s \). The transmitted \( t \) may be corrupted and reach the received as vector \( r \). The receiver uses the parity-check matrix \( H \) to calculate the syndrome vector \( z \), \( z = Hr \).

In (n, k) Hamming such as (7, 4) Hamming, there are 4 data bits and 3 parity bits. Each parity bit is responsible for half the total 8 bits (1 bit is dropped unless "extended" Hamming codes are used). 3 bits can form an address for 8 bits, and so the 3 parity bits act to pinpoint the exact location of a single bit-flip error.

Generator matrix and parity-check matrix

Each row of the generator matrix \( G \) (or column of \( G^{T} \) is a codeword that can be transmitted.

For (7, 4) Hamming, \(G^{T} \) is:

\[ \mathbf{G}^\mathrm{T} = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \hline 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \end{bmatrix} \]

The last 3 store how each piece of data (the first 4 rows) "trigger" each of the 3 parity bits.

\( G^T \) can be expressed as

\[ G^T = \begin{bmatrix} I_4 \\ P \end{bmatrix} \]

where \( I_4 \) is the 4x4 identity matrix, and \( P \) is the parity matrix.

For decoding, the parity-check matrix is determined from \( G \):

\[ P = \begin{bmatrix} P, I_3 \end{bmatrix} \]

Which is:

\[ H=\begin{bmatrix} 1 & 1 & 1 & 0 & \big| & 1 & 0 & 0\\ 0 & 1 & 1 & 1 & \big| & 0 & 1 & 0\\ 1 & 0 & 1 & 1 & \big| & 0 & 0 & 1 \end{bmatrix}. \]

The rows of \( P \) when used in \( Pr \) can be understood as counting up the 1s that each of the 3 parity bits are responsible for, 1 row for each of the 3 parity bits. The identity appears at the end of \( P \) as each parity bit is not included in the responsibility of the other parity bits.

It is true that for any codeword \( t = G^Ts \):

\[ Ht = \begin{bmatrix} 0 \\ 0 \\ 0 \end{bmatrix} \]

The syndrome vector \( z \) is defined by \( z = Hr \). In the event that \( z \neq 0 \), the syndrome-decoding problem is to consider \( r = G^Ts + n \), where the vector \( n \) is the distortion, and determine the most likely value for \( n \). As all codewords are in the null-space of the parity-check matrix, \( H(G^Ts) = 0 \), the problem is to find \( n \) such that \( Hn = z \).