Homework: Exercise 3

Theory: How to Approach These

Recording codes (3.2): write the bits in cells, then apply each code’s flip rule. Dashed lines in the drawings are cell boundaries, dotted lines are cell middles.
CRC (3.3): key of $n + 1$ bits, append $n$ zeros, XOR long division, remainder replaces the zeros.
Minimum Hamming distance: XOR every pair, count 1s, take the smallest.
Hamming code (3.4): smallest $r$ with $m + r + 1 \le 2^r$ , check bits at powers of 2, even parity.
Correcting an error (3.4): recompute each parity group; the failing groups add up (1, 2, 4, 8) to the wrong position.

Jump to: Q1 · Q2 · Q3 · Q4 · Q5

Homework Solutions

Exercise Q1

Write the 7-bit ASCII code for the character 4 using the following encoding: c. Manchester Code d. Frequency modulation e. Modified frequency modulation

Hint: assume 1 is “high,” and 0 is “low.” You may find the ASCII code of “4” using Excel.

Part	Detail
Asks	Find the 7 ASCII bits of “4”, then draw the signal for those bits in three recording codes.
Needs	ASCII digit: $30_{16} + n$ . Manchester, FM and MFM rules.
Look at	“7-bit” (no parity bit), the character 4 (not the number), “1 is high, 0 is low”.
If it changes	Only the bit string changes; every rule stays. Another character: look up its hex code first.

Show solution ↓

Solution

How to solve

Get the bits: $34_{16} = 011\ 0100_2$ . Put the 7 bits above 7 empty cells.
Manchester: 1 = low to high mid-cell, 0 = high to low; add a boundary flip between equal neighbours.
FM: flip at every cell boundary (clock) and mid-cell for each 1.
MFM: flip mid-cell for each 1; boundary flip only between two 0s.

Cell	1	2	3	4	5	6	7
Bit
Manchester
FM
MFM

Sample answer

The digit “4” is $30_{16} + 4 = 34_{16} = 52_{10}$ , so the 7 bits are 0 1 1 0 1 0 0.

c. Manchester (7 mid-cell plus 2 boundary flips between equal neighbours, cells 2-3 and 6-7 = 9 transitions):

d. FM, starting low (3 data flips plus 7 clock flips = 10 transitions):

e. MFM, starting low (3 mid-cell flips plus 1 boundary flip between the 0s in cells 6-7 = 4 transitions):

Level in the first and second half of each cell:

Cell	1	2	3	4	5	6	7
Bit	0	1	1	0	1	0	0
Manchester	HL	LH	LH	HL	LH	HL	HL
FM	LL	HL	HL	HH	LH	LL	HH
MFM	LL	LH	HL	LL	LH	HH	LL

Code	Manchester	FM	MFM
Transitions	9	10	4

Watch out: “4” is ASCII 011 0100, not binary 100. In Manchester add the boundary flips between equal neighbours (cells 2-3, 6-7). In MFM, cells 1 and 4 are single 0s next to 1s, so they get no boundary flip.

Exercise Q2

Using the CRC polynomial 1101, compute the CRC code word for the information word, 01001101. Check the division performed at the receiver.

Part	Detail
Asks	Find the CRC bits and the code word sent, then show the receiver’s division leaves remainder 0.
Needs	Mod-2 (XOR) long division. Key of $n + 1$ bits gives an $n$ -bit CRC.
Look at	Key `1101` has 4 bits, so append 3 zeros. Keep the leading 0 of the data.
If it changes	Longer key means more zeros and a longer remainder; different data gives a different remainder. The steps stay.

Show solution ↓

Solution

How to solve

Key 1101 has 4 bits, so append 3 zeros: 01001101 becomes 01001101000.
Find the leftmost 1, write the key under it, XOR. Repeat until fewer than 4 bits remain after the last 1.
The last 3 bits are the remainder; put them in place of the zeros to get the code word.
Receiver: divide the whole code word by the key (no zeros added). Remainder 000 means accept.

Item	Value
Key (length)
Zeros appended
Dividend
Remainder (last bits)
Code word = data + remainder
Receiver remainder

Sample answer

Sender, dividend 01001101000:

01001101000
 1101            (step 1)
00100101000
   1101          (step 2)
00010001000
    1101         (step 3)
00001011000
     1101        (step 4)
00000110000
      1101       (step 5)
00000000100  -> remainder 100

Code word = 01001101 + 100 = 01001101100.

Receiver, dividing 01001101100 by 1101:

01001101100
 1101
00100101100
   1101
00010001100
    1101
00001011100
     1101
00000110100
      1101
00000000000  -> remainder 000

Remainder 000, so no error is detected and the word is accepted ✓ (the quotient 1111100 is the same as at the sender).

Watch out: do not drop the leading 0 of the data. Place the key under the leftmost 1, not the leftmost bit. Mod 2 has no borrowing: $1 - 1 = 0$ , $0 - 1 = 1$ .

Exercise Q3

Compute the minimum Hamming distance of the following code:

0000000101111111
0000001010111111
0000010011011111
0000100011101111
1001000011110111

Part	Detail
Asks	Compare every pair of code words, count differing bits, and give the smallest count, $D(\min)$ .
Needs	Distance = number of 1s in A XOR B. $n$ words give $n(n-1)/2$ pairs. Detect $D - 1$ , correct $\lfloor (D-1)/2 \rfloor$ .
Look at	W5 is the only word starting with 1, so it is far from the rest; the smallest distance is among the first four words.
If it changes	$n$ words give $n(n-1)/2$ pairs; the method is the same.

Show solution ↓

Solution

How to solve

Label the words $W_1$ to $W_5$ and note there are $\binom{5}{2} = 10$ pairs.
For each pair, XOR the words and count the 1s. The table is symmetric, so fill only the top half.
$D(\min)$ is the smallest entry; then state what the code can detect and correct.

	$W_2$	$W_3$	$W_4$
$W_1$
$W_2$	–
$W_3$	–	–
$W_4$	–	–	–

Sample answer

Pairs worked in full:

W1 = 0000000101111111
W2 = 0000001010111111
XOR  0000001111000000   -> 4 ones

W1 = 0000000101111111
W5 = 1001000011110111
XOR  1001000110001000   -> 5 ones

	$W_1$	$W_2$	$W_3$	$W_4$	$W_5$
$W_1$	–	4	4	4	5
$W_2$	4	–	4	4	5
$W_3$	4	4	–	4	5
$W_4$	4	4	4	–	5
$W_5$	5	5	5	5	–

The smallest entry is 4 (every pair among $W_1$ to $W_4$ ties; $W_5$ is 5 away from each):

$D(\min) = 4$

The code can detect $D(\min) - 1 =$ 3 errors and correct $\lfloor (4-1)/2 \rfloor =$ 1 error.

Watch out: check all 10 pairs, not just neighbours in the list, and line the 16 bits up in groups of 4 when counting.

Exercise Q4

Suppose we want an error-correcting code that will allow all single-bit errors to be corrected for memory words of length 10. a. How many parity bits are necessary? b. Assuming we are using the Hamming algorithm presented in this chapter to design our error-correcting code, find the code word to represent the 10-bit information word: 1001100110. Assume even parity.

Part	Detail
Asks	(a) The number of check bits $r$ for $m = 10$ . (b) Place data and check bits, compute each check bit, write the code word.
Needs	Smallest $r$ with $m + r + 1 \le 2^r$ . Positions numbered from the right; check bits at 1, 2, 4, 8; $P_c$ covers positions whose binary number contains $c$ .
Look at	$m = 10$ , “even parity”, and data order (first data bit goes to the highest position).
If it changes	Another $m$ changes $r$ , $n$ and the coverage lists. Odd parity: each check bit is the opposite value.

Show solution ↓

Solution

How to solve

(a) Try $r = 3$ : $14 > 8$ , no. $r = 4$ : $15 \le 16$ , yes. So $r = 4$ and $n = 14$ .
Write positions 14 down to 1; mark 8, 4, 2, 1 as check bits and fill the data into 14, 13, 12, 11, 10, 9, 7, 6, 5, 3.
Write each position in 4-bit binary; $P_c$ covers the positions with a 1 in the $c$ column. For each check bit, list its data positions and count the 1s: even count gives 0, odd gives 1.
Write the full word and check that every group has an even number of 1s.

Position	14	13	12	11	10	9	8	7	6	5	4	3	2	1
Binary (8 4 2 1)
Type	d	d	d	d	d	d	P8	d	d	d	P4	d	P2	P1
Bit

Check	Data positions	Bits there	1s	Value
P1	3, 5, 7, 9, 11, 13
P2	3, 6, 7, 10, 11, 14
P4	5, 6, 7, 12, 13, 14
P8	9, 10, 11, 12, 13, 14

Sample answer

(a) 4 parity bits (code word length 14).

(b)

Position	14	13	12	11	10	9	8	7	6	5	4	3	2	1
Binary (8 4 2 1)	1110	1101	1100	1011	1010	1001	1000	0111	0110	0101	0100	0011	0010	0001
Contents	1	0	0	1	1	0	P8	0	1	1	P4	0	P2	P1

Read the binary row to see which check bits cover a position: each 1 names one check bit. For example, 13 = 1101 has 1s in the 8, 4 and 1 columns, so 13 is covered by P8, P4 and P1. Going the other way, P1 covers every position whose last binary digit is 1, P2 every position with a 1 in the 2s column, and so on.

Check	Data bits at its positions	1s	Value
P1	pos 3, 5, 7, 9, 11, 13 = 0, 1, 0, 0, 1, 0	2	0
P2	pos 3, 6, 7, 10, 11, 14 = 0, 1, 0, 1, 1, 1	4	0
P4	pos 5, 6, 7, 12, 13, 14 = 1, 1, 0, 0, 0, 1	3	1
P8	pos 9, 10, 11, 12, 13, 14 = 0, 1, 1, 0, 0, 1	3	1

position : 14 13 12 11 10  9  8  7  6  5  4  3  2  1
bit      :  1  0  0  1  1  0  1  0  1  1  1  0  0  0

Code word: 10011010111000

Check (each group including its check bit has an even number of 1s):

Group 1 (1, 3, 5, 7, 9, 11, 13): 0, 0, 1, 0, 0, 1, 0, two 1s ✓
Group 2 (2, 3, 6, 7, 10, 11, 14): 0, 0, 1, 0, 1, 1, 1, four ✓
Group 4 (4, 5, 6, 7, 12, 13, 14): 1, 1, 1, 0, 0, 0, 1, four ✓
Group 8 (8, 9, 10, 11, 12, 13, 14): 1, 0, 1, 1, 0, 0, 1, four ✓

Watch out: number positions from the right. $P_1$ covers 13 (odd positions); 14 = 8 + 4 + 2, so $P_2$ , $P_4$ and $P_8$ all cover it. Count only data bits, not check positions.

Exercise Q5

Suppose we have retrieved a message and check bits out of the hard disk as 01000011 1010. Find the error bit and correct it using the Hamming code method.

Note: the position of the message is (M8 M7 M6 … M1) and of the check bits (C4 C3 C2 C1).

Part	Detail
Asks	Find which single bit of the 12 read is wrong and give the corrected word.
Needs	$m = 8$ , $r = 4$ , $n = 12$ . Check bits at positions 1, 2, 4, 8 ( $C_1$ to $C_4$ ); message bits fill 3, 5, 6, 7, 9, 10, 11, 12 ( $M_1$ to $M_8$ ). Even parity; the syndrome is the position of the error.
Look at	The labels run from the right: $M_1$ is the rightmost message bit and goes to position 3, $C_1$ is the rightmost check bit and goes to position 1.
If it changes	Another word: same placement and four parity checks. Syndrome 0 means no error.

Show solution ↓

Solution

How to solve

Split the word: $M_8 \ldots M_1 = 01000011$ and $C_4 C_3 C_2 C_1 = 1010$ .
Place the bits at positions 12 down to 1.
For each check bit, add up the 1s in its group including the check bit itself. An odd count means that check fails (1), an even count passes (0).
Read the four results as a binary number $s_8 s_4 s_2 s_1$ . That number is the wrong position. Flip that bit.

Position	12	11	10	9	8	7	6	5	4	3	2	1
Label	$M_8$	$M_7$	$M_6$	$M_5$	$C_4$	$M_4$	$M_3$	$M_2$	$C_3$	$M_1$	$C_2$	$C_1$
Bit

Group	Positions	Bits	1s	Fails?
1	1, 3, 5, 7, 9, 11
2	2, 3, 6, 7, 10, 11
4	4, 5, 6, 7, 12
8	8, 9, 10, 11, 12

Sample answer

The message $M_8 \ldots M_1 = 0\,1\,0\,0\,0\,0\,1\,1$ and the check bits $C_4 C_3 C_2 C_1 = 1\,0\,1\,0$ give:

Position	12	11	10	9	8	7	6	5	4	3	2	1
Label	$M_8$	$M_7$	$M_6$	$M_5$	$C_4$	$M_4$	$M_3$	$M_2$	$C_3$	$M_1$	$C_2$	$C_1$
Bit	0	1	0	0	1	0	0	1	0	1	1	0

Group	Positions	Bits	1s	Fails?
1	1, 3, 5, 7, 9, 11	0, 1, 1, 0, 0, 1	3	1
2	2, 3, 6, 7, 10, 11	1, 1, 0, 0, 0, 1	3	1
4	4, 5, 6, 7, 12	0, 1, 0, 0, 0	1	1
8	8, 9, 10, 11, 12	1, 0, 0, 1, 0	2	0

Syndrome $s_8 s_4 s_2 s_1 = 0111_2 = 7$ , so position 7 is wrong. Position 7 is $M_4$ (a message bit, not a check bit). Flip it from 0 to 1.

Corrected message: 01001011 $(M_8 \ldots M_1)$ with check bits 1010. Corrected word, positions 12 to 1: 0100 1101 0110.

Check: with position 7 = 1 the groups hold 4, 4, 2 and 2 ones, all even ✓.

Watch out: the syndrome position counts from the right and includes the check-bit positions. Position 7 is $M_4$ , not the 7th message bit from the left. A syndrome that is a power of 2 would mean a check bit itself is wrong.