# [SOLVED] don't understand the hamming code

• Dec 1st 2009, 10:46 PM
jmedsy
[SOLVED] don't understand the hamming code
We've gone over it in class, but its purpose and application are still completely a mystery to me (probably because of the language barrier between me and my professor). This might belong in the linear algebra section as we are dealing with matrices. Could somebody please provide me with a brief explanation and sample problem?
• Dec 3rd 2009, 06:39 AM
chisigma
An Hamming code is the set of binary vectors of dimension n satisfying the condition...

$\displaystyle \overrightarrow{w} \cdot H = \overrightarrow{0}$ (1)

... where...

$\displaystyle \overrightarrow{w}$ is a n bit word

$\displaystyle H = \left[\begin{array}[pos]{cccc} h_{12} & h_{12} & \dots & h_{1n} \\ h_{21} & h_{22} & \dots & h_{2n} \\ \dots \\ h_{m1} & h_{m2} &\dots & h_{mn}\\ \end{array}\right]$ (2)

... is the m x n 'parity matrix' of the code...

$\displaystyle \overrightarrow{0}$ is the m bit nul word...

An Hamming code allows You to detect 2 errors or correct 1 error in a received n bit word. Each word has length $\displaystyle n=2^m-1$ and is composed by n-m 'information bits' and m 'redundancy bits'. Given the 'information bits' the 'redundancy bits' are computed sao that the relation (1) is satisfied, and the the n bits word is trasmitted. Because the transmission channel is 'noisy' , each received word $\displaystyle \overrightarrow {w_{r}}$ will be...

$\displaystyle \overrightarrow {w_{r}}= \overrightarrow {w} + \overrightarrow{e}$ (2)

At this point we compute...

$\displaystyle \overrightarrow {s} = \overrightarrow {w_{r}} \cdot H = \overrightarrow {e} \cdot H$ (3)

If $\displaystyle \overrightarrow {s} = \overrightarrow {0}$ we can 'hope' that no trasmission errors have occurred and we can recovery the [uncurrupted] 'information bits'. If $\displaystyle \overrightarrow {s} \ne \overrightarrow {0}$ that some errors have occurred and we have two possibilities...

a) to require the retransmission of the corrupted word...

b) try to correct the transmission error...

Under the hypothesis than no more then 1 error has occured, the 'position' of the error can be detected... it corresponds to the column vector of H equal to $\displaystyle \overrightarrow {e}$. An example will be useful...

Let’s have an Hamming 4-7 code with parity matrix…

$\displaystyle H =$$\displaystyle \left[\begin{array}[pos]{ccccccc}1 & 1 & 1 & 0 & 1 & 0 & 0\\ 0 & 1 & 1 & 1 & 0 & 1 & 0\\ 1 & 1 & 0 & 1 & 0 & 0 & 1\end{array}\right]$ (4)

... and suppose to have to trasmit the 'information bits' $\displaystyle 1 0 1 0$. Using (1) we construct $\displaystyle \overrightarrow {w}$ as...

$\displaystyle \overrightarrow {w} = 1 0 1 0 0 1 1$ (5)

$\displaystyle \overrightarrow {w_{r}} = 1 1 1 0 0 1 1$ (6)
$\displaystyle \overrightarrow {s} = \overrightarrow {w_{r}} \cdot H = \left[\begin{array}[pos]{c}1 \\ 1 \\ 1\end{array}\right]$ (7)
$\displaystyle \chi$ $\displaystyle \sigma$