We want to design a Hamming Code for single error correction where the size of the dataword $d_1{d}_2{d}_3{d}_4$ is $k=4.$

$1+1+{0\mathrm{.}5}^{**}16+(3+3+4)=20$

$($a$)$ Show that we need $r=3$ parity bits for the code. Let these bits be $p_1{p}_2{p}_3.$

$($b$)$ Now we need to have a $H(7,4).$ Show the placement of the $d\text{'}$s and $p\text{'}$s over the $7-$bits of $H(7,4).$

$($c$)$ Construct the parity$-$encoded codewords for the datawords. That is$,$ fill up the codewords in the table below. $($You may write a program to fill up the table if you want.$)$

$\backslash$table$[[$Dataword$,$Codeword$],[0000,],[0001,],[0010,],[0011,],[0100,],[0101,],[0110,],[0111,],[1000,],[1001,],[1010,],[1011,],[1100,],[1101,],[1110,],[1111,]]$

Hint: Outline of Hamming Coding Algorithm:

The idea is to add a set of new bits, also called parity bits, to detect and correct errors in the data.

Each parity bit covers a specific set of data bits. The $i^{th}$ parity bit covers bit positions in the following way $($denote $k=2^{i-1})$

Start from position $k$

Include $k$ consecutive bits

Skip the next $k$ consecutive bits

Repeat steps $2$ and $3$ until the end of the string is reached

$($d$)$ We now need to communicate the string: $x=$ aaabaaaadaaaaaaaafaaaaabaaacaa

Show the output after every action below:

i$.$ Using the Huffman Code designed in Q $1,$ source encode the string

ii$.$ Group the bits of the encoded string in blocks of size $4($at the end, pad $0\text{'}$s or $1\text{'}$s as appropriate$)$ and Channel encode the blocks using the Hamming Code designed above.

iii. During transmission, every $5^{th}$ bit of the stream gets flipped. Use Hamming error$-$correcting decoding of the blocks and show that $x$ is correctly received.