Results 1 to 2 of 2

Math Help - [SOLVED] don't understand the hamming code

  1. #1
    Member
    Joined
    Nov 2009
    Posts
    80

    [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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    5
    An Hamming code is the set of binary vectors of dimension n satisfying the condition...

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

    ... where...

    \overrightarrow{w} is a n bit word

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

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

    \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 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 \overrightarrow {w_{r}} will be...

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

    At this point we compute...

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

    If \overrightarrow {s} = \overrightarrow {0} we can 'hope' that no trasmission errors have occurred and we can recovery the [uncurrupted] 'information bits'. If \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 \overrightarrow {e}. An example will be useful...

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

    H = <br />
\left[\begin{array}[pos]{ccccccc}1 & 1 & 1 & 0 & 1 & 0 & 0\\<br />
0 & 1 & 1 & 1 & 0 & 1 & 0\\ <br />
1 & 1 & 0 & 1 & 0 & 0 & 1\end{array}\right] (4)

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

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

    Let's suppose now to receive...

    \overrightarrow {w_{r}} = 1 1 1 0 0 1 1 (6)

    ... that has been corrupted in position 2. Using (3) we compute...

    \overrightarrow {s} = \overrightarrow {w_{r}} \cdot H = <br />
\left[\begin{array}[pos]{c}1 \\ 1 \\ 1\end{array}\right] (7)

    ... that is the 'column vector' in position 2, where the error occurred...

    Kind regards

    \chi \sigma
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Hamming Codes
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: January 16th 2012, 02:52 PM
  2. Hamming Code, Parity Matrix
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 28th 2010, 06:03 AM
  3. correcting an isbn number (maybe with hamming code?)
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 15th 2009, 03:37 AM

Search Tags


/mathhelpforum @mathhelpforum