A parity check code has the parity check matrix H 1 0 0 0 1

A parity check code has the parity check matrix H = [1 0 0 0 1 1 1 0 1 0 1 0 1 1 0 0 1 1 1 0 1] Determine the generator matrix and find all possible codewords. A codeword corresponding to the message [1 0 1 1] was sent, and the 6th bit was received error. Illustrate the decoding process.

Solution

a)

Genrator Matrix:

Input:H matrix

1       0       0       0       1       1       1      

0       1       0       1       0       1       1      

0       0       1       1       1       0       1      

--

Transforming 3 x 7 parity-check matrix H over GF(2) into standard form...

n=7 k=4 q=2

Start [0,4] = 1

Pivot [0,4] = 1

r_3 --> r_3 - r_1

1       0       0       0       1       1       1      

0       1       0       1       0       1       1      

1       0       1       1       0       1       0      

--

Start [1,5] = 1

Pivot [1,5] = 1

r_1 --> r_1 - r_2

r_3 --> r_3 - r_2

1       1       0       1       1       0       0      

0       1       0       1       0       1       1      

1       1       1       0       0       0       1      

--

Start [2,6] = 1

Pivot [2,6] = 1

r_2 --> r_2 - r_3

1       1       0       1       1       0       0      

1       0       1       1       0       1       0      

1       1       1       0       0       0       1      

--

We are done. H\' = [B | I_3] =

1       1       0       1       1       0       0      

1       0       1       1       0       1       0      

1       1       1       0       0       0       1      

--

Hence G = [I_4 | -B^T] =

1       0       0       0       1       1       1      

0       1       0       0       1       0       1      

0       0       1       0       0       1       1      

0 0 0     1 1 1 0