Two dimensional parity check

Question

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.

Answer 1

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.