Question 1 (Two-dimension Parity Check, 20%). Consider the following two-dimension parity check, with original data in a
4 × 4 matrix. For each row and column, we generate a parity bit, forming a 5 × 5 matrix. The parity bits are in the last column
and last row. Then, the 25 bits will be transmitted through a bit-flipping channel. For simplification, we assume that each original
bit is flipped with probability p independently; p is a small probability; the parity bits are not flipped at all.
(1) [3%] Assume the following bits are sent:
1 1 0 0 0
1 1 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
(1)
and the following bits are received
0 0 0 0 0
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0
(1)
Then, what does the receiver do and why?

(2) [3%] The example in (1) shows one case that the receiver believes there is one bit error and the error can be corrected, but
the fixed bits are still wrong. Please give another example: (a) there are 9 bits flipped; (b) the receiver believes there is one bit
error and the error can be corrected; and (c) the fixed bits are still wrong.
(3) [3%] If two original data bits are flipped, can the receive detect errors? can the receiver recover the errors? Why or why not.
(4) [3%] Give an example where there are bit error(s) but the receiver cannot even detect the error(s).
(5) [8%+ up to 4% bonus] Calculate the following probabilities (as a function of p): (a) The receiver believes there is one bit
error and the error can be corrected, and the fixed bits are correct. (b) The receiver believes there is one bit error and the error
can be corrected, but the fixed bits are wrong. For (b), you will get full mark if your answer is sufficiently close to the accurate
solution (i.e., consider those “common” error patterns but ignore those “rare” error patterns). Bonus marks will be given if your
answer is more accurate.

DETAILED ASSIGNMENT

20200917111615comp9121_assignment1_2020_part_1