Undetected Errors in 2 Dimensional Parity

Question

Given a two dimensional parity with a data block of two rows and two columns what is the probability that a four bit error goes undetected?

The naive method would be to look at all ways in which an error could go undetected. For example:

1 0 | 1   could be received as 0 1 | 1
0 1 | 1                        1 0 | 1
-------                        -------
1 1 | 0                        1 1 | 0

And then divide this by the number different messages that could be received with four bit errors. However, that is incredibly slow and error prone. Is there an easier way to calculate the probability of a k bit error going undetected in two dimensional parity?

Answer 1

Hint: Prove that if

$$n = \begin{array}{cc|c} n_1 & n_2 & n_3 \\ n_4 & n_5 & n_6 \\ \hline n_7 & n_8 & n_9 \end{array}$$

passes the parity check and has weight 4 (i.e., 4 nonzero entries) then $n$ has exactly one row of $0$s, one column of $0$s, and all other entries $1$. For example,

$$n = \begin{array}{cc|c} 1 & 0 & 1 \\ 1 & 0 & 1 \\ \hline 0 & 0 & 0 \end{array}.$$

Count the number of such $n$, then divide by the total number of $n$ of weight 4 (including those that don't pass the parity check; use the binomial coefficent to count them).

Answer:

9/(9 choose 4) = 9/126