3
$\begingroup$

Firstly, I would like to apologize if I misplaced this topic / i think the theory of coding is close to CS /

I am little bit confused right now, in the school we were learning about Hamming's code, Block codes etc.

I was given a homework, in which I should explain how does the two dimensional parity check finds 3-bit errors. I think the two-dimensional parity check does finds 3-bit erros, but it can't (in every case) correct it.

The second thing is, we were learning about hamming distance and there is a rule, which says that block code finds t-bit error when this equation is right:

t < d (and d stands for hamming distance, its minimum distance between the 2 code words / t stands for t-bit errors).

So for example: a = 110, b = 101, c = 100

1 1 0 | 0
1 0 1 | 0
1 0 0 | 1
_ _ __
1 1 1   1

The numbers behind the 'bars/underscores' are the parity-check bits, it means that in each column/row is even count of number 1.

So the minimum distance equals to 2. That means according to the rule t < d, that this code can detect only a t-bit error, which means 1 ( but that's not true, because it can detect 3 bit erros).

How should I explain that?.

Thanks.

$\endgroup$
  • $\begingroup$ I'm having a hard time understanding what your question is. Can you edit your question to try to explain more clearly what your question is? This site is intended for specific focused questions, rather than an open-ended prompt to discussion. 1. I don't know what "How should I explain that?" is asking -- what do you mean by "that", why do you want to explain it, what is giving you difficulty, what are your thoughts? 2. Can you define what a two dimensional parity check is? $\endgroup$ – D.W. Oct 26 '15 at 0:27
  • $\begingroup$ 3. I'm a bit confused about what's going on with "First thing", "second thing" -- how do they relate to your question? (For reference: you should ask only one question per question.) $\endgroup$ – D.W. Oct 26 '15 at 0:27
1
$\begingroup$

Firstly the $t<d$ condition, applies to either the row or the column codes on their own. So you know that a single error in each row or column can be detected since $d=2$.

Given 3 errors overall for the array, consider the decompositions of errors into distinct rows. Clearly

  1. $3=3$,
  2. $3=2+1$, or
  3. $3=1+1+1$

are the only possibilities.

In case 3 the column parity checks can correct these errors separately so we're done.

In case 2 the single error can be corrected on its row, and the remaining two errors on a single row, can be corrected by the parity check in the corresponding column.

In case 1 all 3 errors are on one row, so by definition they are on 3 distinct columns and can be corrected by the parity check in the corresponding column.

So the array code can correct 3 errors.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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