Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I need to prove the following:

Let C be a binary cyclic Hamming code; we add a parity check at the end of every code word and get an extended (not necessarily cyclic) code.

We need to prove that this code (the extended one) can fix any single error, and any double error occurring in two adjacent position, excluding the final (parity) digit.

I've been trying to prove it for a long time but i couldn't find the solution, and my problem here is that the extended code is not cyclic at all, so I can't talk about its generator polynomial. I found a similar proof, which can show that if hamming code is generated by polynomial $g(x)$, than the code $<(x+1)g(x)>$ is double adjacent ( fix any single error, and any double error occurring in two adjacent position, excluding the final (parity) digit), but I can't use this proof here because the proof rely on the fact that there is no vector in the code in the form of: $$ (x^i + x^{i+1})+(x^j+x^{j+1})=(x+1)(x^i+x^j) $$ And if there is, so this polynomial is multiple of $(x+1)g(x)$, meaning that $(x^i+x^j)$ is multiple of $g(x)$, meaning $(x^i+x^j)$ is in the code $<g(x)>$, contradicting the hamming code minimal distance 3.

Obviously this kind of proof won't work here. What other way should I use to prove it? Thanks.

share|improve this question
add comment

1 Answer 1

up vote 2 down vote accepted

Let $c(x) = \sum_{i=0}^{N-1} c_i x^i$ denote the polynomial corresponding to the codeword $\mathbf c = [c_0, c_1, \ldots, c_{N-1}]$ of a cyclic binary Hamming code with generator polynomial $g(x)$. Note that $N = 2^m-1$ for some positive integer $m$ and that $g(x)$ is a primitive polynomial of degree $m$. Let $\alpha \in \mathbb F_{2^m}$ be a root of $g(x)$ and note that $\alpha$ has order $2^m-1$.

The parity check matrix $H$ of this cyclic binary Hamming code can be viewed as $[1, \alpha, \cdots, \alpha^{N-1}]$. If you are unfamiliar with this notion, then express each $\alpha^i$ as a column vector to get the usual binary representation. But, with this formulation, $H\mathbf c^T = \mathbf0$ is equivalent to $c(\alpha) = 0$ which is exactly what the polynomial formulation says in other terms: each codeword polynomial is a multiple of $g(x)$ which happens to have $\alpha$ as a root, and so $c(\alpha) = 0$.

Let $\mathbf c$ be transmitted and $\mathbf r = \mathbf c + \mathbf e$ denote the received word. In terms of polynomials, $r(x) = \sum_i r_ix^i$ is the received word polynomial where $r_i = c_i + e_i$ with $e(x)$ denoting the error word polynomial corresponding to the error word $\mathbf e$. Note that $r(x) = c(x) + e(x)$. The receiver computes $$H\mathbf r^T = H(\mathbf c + \mathbf e)^T = H\mathbf c^T + H\mathbf e^T = \mathbf 0 + H\mathbf e^T = H\mathbf e^T.$$ In terms of polynomials, computing $H\mathbf r^T$ is the same as evaluating $r(x)$ at $\alpha$, andso the above equation can be expressed as $$r(\alpha) = c(\alpha) + e(\alpha) = 0 + e(\alpha) = e(\alpha).$$

If a single error has occurred, then $\mathbf e$ has Hamming weight $1$, and $e(x)$ is a monomial $x^i$ for some $i$, $0 \leq i \leq N-1$. Thus, the bit in the $i$-th position has been received incorrectly. In terms of polynomials, the syndrome is $e(\alpha) = x^i\bigr |_{x=\alpha^i} = \alpha^i$. If two errors have occurred, the syndrome is $\alpha^i + \alpha^{i^\prime} = \alpha^j$. The decoder for the cyclic Hamming code cannot tell whether one or two errors have occurred: if the symdrome equals $\alpha^\ell$, it simply inverts $r_\ell$ to correct the error.

The extended Hamming code has an overall parity bit $c_N$ whose value is chosen to ensure that the extended codeword $\hat{\mathbf c} = (\mathbf c, c_N)$ has even Hamming weight. Suppose that an extended Hamming code is being used and it is known that if there are two channel errors, then they are adjacent errors not involving the overall parity bit. Let $\hat{\mathbf r} = (\mathbf r, r_N)$ be the received word for the extended Hamming code. If $\hat{\mathbf r}$ has odd Hamming weight, then the decoder assumes that a single error has occurred, and if $r(\alpha) = \alpha^\ell$, the decoder inverts $r_\ell$. But if $\hat{\mathbf r}$ has even Hamming weight and $r(\alpha) = \alpha^\ell \neq 0$, then the decoder assumes that $e(x) = x^i + x^{i+1}$ (double adjacent error) and so $r(\alpha) = e(\alpha) = \alpha^i + \alpha^{i+1} = \alpha^\ell.$ Since $\alpha^i = \alpha^\ell(1+\alpha)^{-1}$, the decoder can find the value of $i$ and then invert $r_i$ and $r_{i+1}$. In this way, single errors and double adjacent errors not involving the overall parity bit can be corrected with an extended Hamming code.

share|improve this answer
    
Thanks for the quick answer, but I haven't quite understand your explanation. I have learned in the book "A First Course in Coding Theory" by Raymond Hill, that if we take $a$ as a primitive element of the field $F2[x]/p(x)$ for some ireducible polynomial $p(x)$, than the matrix you show is indeed a parity check matrix for the cyclic hamming code. I don't understand how do you know where is the error - what is the connection between $a^N$ and $c_N$? –  or523 Sep 2 '13 at 15:34
    
I'm sorry, but what R, C and E stand for? Which matrices? And what is supposed to be $e(a)$, are you reffering to the error vectors? I understood how you've understand what type of error there is, butt still, the correction of it is not well understood to me. –  or523 Sep 2 '13 at 16:32
    
See edited answer. –  Dilip Sarwate Sep 2 '13 at 19:22
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.