hamming code

The generator matrix is given by: \[G^T = \begin{pmatrix} 1 & 1 & 0 & 1\\ 1 & 0 & 1 & 1\\ 1 & 0 & 0 & 0\\ 0 & 1 & 1 & 1\\ 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1 \end{pmatrix}\]

What is the \((7,4)\) code? It takes a 4 bit message to a 7 bit code word. Of those 7 bits, 4 of those bits are just the message, and the other 3 bits are parity bits. Look at rows 1, 2,and 4 to see how these parity bits are computed. Each message bit is an input to at least two parity bits. So if a one bit error occurs on one of the message bits, we can always determine where the bit occurred by looking at which two parity bits do not match with the observed received parity of the message bits.

We can make a matrix that does this automatically for us: \[H = \begin{pmatrix} 1 & 0 & 1 & 0 & 1 & 0 & 1\\ 0 & 1 & 1 & 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 1 & 1 & 1 & 1\\ \end{pmatrix}\] Multiplying \(Hy\) where \(y\) is the received word will tell us, for each parity bit, whether the parity bit matches the computed parity of the observed message bits. Depending on which parity bits do not match, we can determine where the error is. And indeed, this matrix has been set up carefully so that the index of the bit with the error is output by the matrix.

• wikipedia

• quantum error correction