GEK1505/GEH1036: Chapter 4 – Coding

Chapter 4 – Coding 1 / 85
Overview

1 Coding information
Binary Representation
Octal Representation
Hexadecimal Representation
Error-detecting Codes
ISBN

2 Hamming (7, 4) Codes

3 Hamming (8, 4) Codes

Chapter 4 – Coding 2 / 85
Coding Information

How is information transmitted electronically?

(1) An information source

This provides messages or information to be sent.

(2) An encoding of the information source

Words and images are converted (encoded) into numbers by some

standard convention. Machine transmits this encoded form.

Chapter 4 – Coding 3 / 85
Coding Information

(3) Information channel

Information (signal) is sent through a channel (machine) such as a
computer, telephone, fax machine.

(4) A noise or error source

Unwanted “noise” (distortion) added to the signal in the channel.
Usually random in nature and often unavoidable. Caused by nature
(cosmic rays, lightning) or by man (human error) or by machine
(defective or worn out parts).

Chapter 4 – Coding 4 / 85
Coding Information

(5) A decoding of signal received

This recovers and restores the original signal (message) from the
signal received, which is sometimes distorted or partially lost during
transmission because of the noise in (4).

(6) Sink for the information

The final outcome - on TV screen, telephone, in the hard disk, etc.

Chapter 4 – Coding 5 / 85
Coding Information

Chapter 4 – Coding 6 / 85
Binary Representation

Most electronic devices can be one of two states:

“ON” or “OFF” (switch)

“punched” or “not punched” (card)

“open” or “closed” (relay)

Chapter 4 – Coding 7 / 85
Binary Representation

Convenient to represent a state of ONE device by

“0” or “1”

TWO devices can be used to represent 4 distinct states:

00, 01, 10, 11

In general, with k devices, we have a total of 2k states.

Chapter 4 – Coding 8 / 85
Binary Representation

Decimal system:
Historically (and physically), counting is usually done in groups of tens.
Hence positive numbers are encoded by ten basic symbols (digits):

0, 1, 2, 3, 4, 5, 6, 7, 8, 9

Example 4.1
2014 = 2 × 103 + 0 × 102 + 1 × 101 + 4 × 100 .

Chapter 4 – Coding 9 / 85
Binary Representation

Binary system:
Counting can also be done in groups of twos. Positive numbers may be
coded by using only two basic symbols: 0, 1.

Example 4.2
0 = 000 4 = 100
1 = 001 5 = 101
2 = 010 6 = 110
3 = 011 7 = 111

Chapter 4 – Coding 10 / 85
Binary Representation

How to express a positive integer N in binary form?

Divide the number N (in decimal form) by 2 repeatedly to get all the
possible successive remainders r1 , r2 , ..., rk . Then

N = rk × 2k−1 + · · · + r2 × 21 + r1 × 20

Chapter 4 – Coding 11 / 85
Binary Representation

The binary representation of a positive integer N is

(rk rk−1 . . . r2 r1 )2

Note. The subscript 2 is to emphasise the so-called “base” of the

representation is 2. It may be omitted if there is no ambiguity. When in
doubt, write it in. Each of the digit in the binary representation is called a
bit.

Chapter 4 – Coding 12 / 85
Binary Representation

Example 4.3
Covert 235 into binary representation.

Solution:
235 ÷ 2 = 117 . . . 1
117 ÷ 2 = 58 . . . 1
58 ÷ 2 = 29 . . . 0
29 ÷ 2 = 14 . . . 1
14 ÷ 2 = 7 . . . 0
7 ÷ 2 = 3...1
3 ÷ 2 = 1...1
1 ÷ 2 = 0...1
Therefore 235 = (11101011)2 .
Chapter 4 – Coding 13 / 85
Binary Representation

Example 4.4

43 = 1 × 25 + 0 × 24 + 1 × 23 + 0 × 22 + 1 × 21 + 1 × 20
= (101011)2

43 ÷ 2 = 21 . . . 1
21 ÷ 2 = 10 . . . 1
10 ÷ 2 = 5 . . . 0
5 ÷ 2 = 2...1
2 ÷ 2 = 1...0
1 ÷ 2 = 0...1

Chapter 4 – Coding 14 / 85
Binary Representation

One of the earliest examples of binary symbols is the ancient Chinese

“ba-gua” symbols used in divination.

It consists of juxtapositions of short and long line segments.

The symbol “− − ” represents “female” (0) and the symbol “ − ” (long

dash) represents “male” (1).

Chapter 4 – Coding 15 / 85
Binary Representation

Chapter 4 – Coding 16 / 85
Octal Representation

Octal representation:
A representation of positive integers using the following 8 digits:

0, 1, 2, 3, 4, 5, 6, 7

Chapter 4 – Coding 17 / 85
Octal Representation

How to express a positive integer N in octal representation?

Divide the number N by 8 repeatedly to get all the possible successive
remainders r1 , r2 , ..., rk . Then

N = rk × 8k−1 + · · · + r2 × 81 + r1 × 80

The octal representation of N is

(rk rk−1 . . . r2 r1 )8

Chapter 4 – Coding 18 / 85
Octal Representation

Example 4.5
Find the octal representation of 106.

Solution.

106 ÷ 8 = 13 . . . 2
13 ÷ 8 = 1 . . . 5
1 ÷ 8 = 0...1
So 106 = (152)8 .

Chapter 4 – Coding 19 / 85
Hexadecimal Representation

Hexadecimal representation:
A representation of positive integers using the following 16 symbols:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C , D, E , F

where A, B, C , D, E , F represent 10, 11, . . . , 15, respectively.

Chapter 4 – Coding 20 / 85
Hexadecimal Representation

How to express a positive integer N in hexadecimal

representation?
Divide the number N by 16 repeatedly to get all the possible successive
remainders r1 , r2 , ..., rk . Then

N = rk × 16k−1 + · · · + r2 × 161 + r1 × 160

The hexadecimal representation of N is

(rk rk−1 . . . r2 r1 )16

Chapter 4 – Coding 21 / 85
Hexadecimal Representation

Example 4.6
Find the hexadecimal form of 3436.

Solution.
3436 ÷ 16 = 214 . . . 12
214 ÷ 16 = 13 . . . 6
13 ÷ 16 = 0 . . . 13
Thus,
3436 = (D6C )16 .

Chapter 4 – Coding 22 / 85
Error-detecting Codes

Errors can occur in transmitted codes.

Example: send 11111, receive 11011.
If errors occur only at few bits, how can we detect them?

Chapter 4 – Coding 23 / 85
Error-detecting Codes

Some common errors in writing a number sequence

interchanging two adjacent digits (Transposition error).

making an error in one digit (Single error).

Chapter 4 – Coding 24 / 85
Error-detecting Codes

Have you ever wondered why there is a letter at the end of

car registration numbers? E.g. SCF 9710H
identity card numbers? E.g. S7769624E

These letters can detect simple errors in writing the numbers and can
prevent forgery.

In “Monday, 01-10-2001”, the day of the week (in this case, Monday)
can also serve as a “check symbol”. For instance, it cannot be 10 Jan
2001, which is a Wednesday. Inconsistency will also show up for certain
errors in the day, month or year.

Chapter 4 – Coding 25 / 85
Encoding
Information contains letters, blank space, and digits
Each symbol is given the corresponding numerical value:
Symbol 0 1 2 3 4 5 6 7 8 9
Numerical 0 1 2 3 4 5 6 7 8 9
Symbol A B C D E F G H I J
Numerical 10 11 12 13 14 15 16 17 18 19
Symbol K L M N O P Q R S T
Numerical 20 21 22 23 24 25 26 27 28 29
Symbol U V W X Y Z blank
Numerical 30 31 32 33 34 35 36

Sometimes, to avoid confusion, the blank space is denoted by the

underscore “ ”.
Chapter 4 – Coding 26 / 85
Weighted sum

Definition 4.7 (Weighted sum)

Given the sequence (or word) Sn Sn−1 · · · S2 S1 , its weighted sum is the
sum
nen + (n − 1)en−1 + · · · + 2e2 + e1
where ei is the numerical value which corresponds to the symbol Si ,
1 ≤ i ≤ n.

Chapter 4 – Coding 27 / 85
Weighted sum

Example 4.8
Find the weighted sum of the sequence NO FOOD.

Solution. Note that N = 23, O = 24, blank = 36, F = 15, D = 13. So

the weighted sum is

7(23) + 6(24) + 5(36) + 4(15) + 3(24) + 2(24) + 1(13) = 678.

Chapter 4 – Coding 28 / 85
Encoding
Encoding procedure modulo 37:

Input: A sequence S = Sn Sn−1 · · · S2 , n ≤ 35.

(1) Find the check digit c such that

w (en en−1 · · · e2 c) ≡ 0 (mod 37).

Here ei is the numerical value of the symbol Si , w (en en−1 · · · e2 c) is

the weighted sum of the sequence en en−1 · · · e2 c.
(2) Find the symbol S1 that corresponds to c.

Output: The encoded sequence is

Sn Sn−1 · · · S2 S1 .

Chapter 4 – Coding 29 / 85
Encoding

Remark
More generally, the number 37 can be replaced by any prime number p.
Then we’ll need to have n ≤ p − 1 so that after the check digit has been
appended, the length is ≤ p − 1. For the time being, we shall keep to 37.

Chapter 4 – Coding 30 / 85
Encoding
Example 4.9
Encode A6 7 modulo 37.

Solution. Note that

A = 10, 6 = 6, blank = 36, 7 = 7.
Let c be the check digit. Then
5(10) + 4(6) + 3(36) + 2(7) + 1(c) ≡ 0 (mod 37).
∴ 196 + c ≡ 0 (mod 37).
∴ 11 + c ≡ 0 (mod 37).
∴ c ≡ 26 (mod 37).
The letter Q corresponds to 26, so the encoded sequence is
A6 7Q.

Chapter 4 – Coding 31 / 85
Error detection

Definition 4.10
A word is said to contain k errors if k of its letters are erroneous.

Chapter 4 – Coding 32 / 85
Error detection

Remark
If A is a correctly encoded word, then its weighted sum W (A) ≡ 0
(mod 37).

If W (A) 6≡ 0 (mod 37), then it contains one or more errors.

However, an erroneous word A may still have W (A) ≡ 0 (mod 37). We

say that the errors are not detected.

Chapter 4 – Coding 33 / 85
Error detection

Error detection
If A is a correctly encoded word, and during transmission, some errors
occur and the word A0 is received. The errors in A0 is said to be detected if
its weighted sum
W (A0 ) 6≡ 0 (mod 37).

Chapter 4 – Coding 34 / 85
Error detection

Example 4.11
Suppose the encded word A6 7Q is received as C 6 7Q, then the error is
detected as the weighted sum

5(12) + 4(6) + 3(36) + 2(7) + 1(c) 6≡ 0 (mod 37).

Chapter 4 – Coding 35 / 85
Error detection

Theorem 4.12
In weighted sum encoding modulo 37, if a single error occurs, then it can
be detected.
Proof:
Suppose A = Sn . . . S1 is the correct word and a single error error occurs at
position i, changing Si to x and the word A to A0 . Then

W (A) − W (A0 ) = iSi − ix = i(Si − x).

Since 0 < i < 37 and 0 < |Si − x| < 37, the product i(Si − x) cannot be a
multiple of 37. Thus W (A) − W (A0 ) 6≡ 0 (mod 37). But W (A) ≡ 0
(mod 37). Therefore W (A0 ) 6≡ 0 (mod 37) and the error is detected.

Note: The result holds if 37 is replaced by any prime number p.

Chapter 4 – Coding 36 / 85
Transposition error

Example 4.13
Suppose an encoded word is wxyz, where x and y are distinct symbols and
z is the check symbol.

Show that if the original symbol x and y were interchanged during

transmission (so the received word is wyxz), then the error can be
detected.
Note: This is an example of a transposition error. In general, a
transposition error is said to have occurred if the letters in two positions
are interchanged.

Chapter 4 – Coding 37 / 85
Transposition error

Solution. Let A = wxyz, B = wyxz and let W (A) and W (B) denote
their respective weighted sum.

The error can be detected if we can show that W (B) 6≡ 0 (mod 37).

Chapter 4 – Coding 38 / 85
Transposition error

By definition,
W (A) = 4w + 3x + 2y + z,
W (B) = 4w + 3y + 2x + z.

∴ W (B) − W (A) ≡ y − x (mod 37).

We have W (A) ≡ 0 (mod 37),

∴ W (B) ≡ y − x (mod 37).

But y − x 6≡ 0 (mod 37) since 0 < |x − y | < 37.

∴ W (B) 6≡ 0 (mod 37).

Chapter 4 – Coding 39 / 85
Transposition error

Theorem 4.14
Weighted sum modulo 37 can detect a transposition error.

Proof: Suppose in the word A, the number at position i and j are a and b
respectively, and they have been interchanged to yield an incorrect word B.

A: ... a ... b ...

B: ... b ... a ...
Position: ... i ... j ...

Chapter 4 – Coding 40 / 85
Transposition error

Then

W (A) − W (B) = i(a − b) + j(b − a) = (i − j)(a − b).

Note that both |i − j| and |a − b| are < 37 and > 0.

∴ (i − j)(b − a) 6≡ 0 (mod 37).

Since W (A) ≡ 0,
W (B) 6≡ 0 (mod 37).
Thus B is an invalid word.

Note: The result is still true if 37 is replaced by any prime number p.

Chapter 4 – Coding 41 / 85
ISBN

Book publishers use a special code number known as International

Standard Book Number (ISBN) for a book published. It is on the
back cover of the book.

The ISBN is
13 digits long if assigned on or after 1 January 2007
10 digits long if assigned before 2007

Chapter 4 – Coding 42 / 85
ISBN

We will only focus on 10-digit ISBN in this course.

The digits are arranged in 4 groups, which are sometimes (but not always)
separated by hyphens.
Geographical grouping (country)
Publisher
Identification of the book (title)
Check digit

Chapter 4 – Coding 43 / 85
Chapter 4 – Coding 44 / 85
ISBN

The check digit is chosen so that the weighted sum of all the 10
digits is a multiple of 11.
The check digit could be

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, X

where X is used in the case the last digit is “10’.

Chapter 4 – Coding 45 / 85
ISBN

Example:
0 − 1321 − 2571 − 4

the hyphens are of no importance, and may appear in different

positions.
in this case, say,
0: country of publication (US)
13: publisher’s identification
212571: book’s identification
4: check digit

Chapter 4 – Coding 46 / 85
ISBN

Example 4.15
Check that the number 0 − 1315 − 2447 − X is a proper ISBN.

Solution. Need to show that the weighted sum is a multiple of 11.

Since X = 10, the weighted sum is

w = 10(0) + 9(1) + 8(3) + 7(1) + 6(5) + 5(2)

+4(4) + 3(4) + 2(7) + 1(10)
= 132
= 11 × 12 ≡ 0 (mod 11)

Chapter 4 – Coding 47 / 85
ISBN

Example 4.16
Suppose the ISBN 1 − 886544 − 45 − X is copied incorrectly with the digit
‘6’ replaced by ‘9’. How does this affect the weighted sum?

Solution. The incorrect ISBN is 1 − 889544 − 45 − X .

The weighted sum is

10(1) + 9(8) + 8(8) + 7(9) + 6(5) + 5(4) + 4(4) + 3(4) + 2(5) + 10

= 307 6≡ 0 (mod 11)

Hence there must be an error in given sequence.

Chapter 4 – Coding 48 / 85
ISBN

Why are ISBN numbers encoded modulo 11 and not 10?

11 is a prime BUT 10 is not a prime.

If 10 is used, some simple errors may not be detected.

Chapter 4 – Coding 49 / 85
ISBN

Example 4.17
Suppose we encode modulo 10 instead of 11.
If the original ISBN is 1 − 886544 − 45 − c. What is c?
Suppose the first digit of the ISBN above is copied wrongly as 5, and
the rest are copied correctly.
Show that this error cannot be detected.

Chapter 4 – Coding 50 / 85
ISBN

We first determine the check digit c.

Since the weighted sum is a multiple of 10, we have

10(1)+9(8)+8(8)+7(6)+6(5)+5(4)+4(4)+3(4)+2(5)+c ≡ 0 (mod 10)

276 + c ≡ 0 (mod 10)

c ≡ −6 (mod 10)
c = 4.

Chapter 4 – Coding 51 / 85
ISBN

The incorrect ISBN is

5 − 886544 − 45 − 4
The weighted sum is

5(10) + 9(8) + 8(8) + 7(6) + 6(5) + 5(4) + 4(4) + 3(4) + 2(5) + 4

= 320 ≡ 0 (mod 10)

Since the weighted sum does not violate the congruence condition, the
error cannot be detected.

Chapter 4 – Coding 52 / 85
ISBN

Theorem 4.18
ISBN can detect a single error and a transposition eror.

Proof: Follows from previous theorems with the prime number 11.

Chapter 4 – Coding 53 / 85
ISBN

What it can do
The two most common errors in handling an ISBN (e.g., typing or writing
it) are a single altered digit or the transposition of adjacent digits. ISBN
can detect these errors.
In other words, if such an error is committed, the result will be an invalid
ISBN.

Chapter 4 – Coding 54 / 85
ISBN

Example 4.19
The ISBN 0 − 1321 − 2571 − 4 is wrongly recorded as 0 − 1321 − 1572 − 4.

The error will be detected as the latter is not a valid ISBN as the weighted
sum is NOT 0 mod 11.

10 · 0 + 9 · 1 + 8 · 3 + 7 · 2 + 6 · 1 + 5 · 1 + 4 · 5 + 3 · 7 + 2 · 2 + 1 · 4 ≡ 4 (mod 11)

Chapter 4 – Coding 55 / 85
ISBN

What it can’t do
It is possible for other types of error, such as two altered non-transposed
digits, or three altered digits, to result in a valid ISBN number (although it
is still unlikely).

Chapter 4 – Coding 56 / 85
Error-correcting codes

Earlier, we see that check digits can be used to detect errors.

Very often, it is desirable to not only detect errors, but also to pinpoint
the errors and correct them.

Assuming not too many errors occur, it is possible to recover the original
message. Here, we see how this can be done using
Hamming (7, 4) Codeword
Hamming (8, 4) Codeword

Chapter 4 – Coding 57 / 85
Richard Hamming

Richard Hamming
Born: February 11, 1915, Chicago, Illinois
Died: January 7, 1998 (aged 82) Monterey, California
Hamming code was discovered in 1948 while he was at Bell Labs.

Chapter 4 – Coding 58 / 85
Hamming (7, 4) Codes

Hamming (7, 4) codes:

• encodes 4 bits (0 or 1) of data into 7 bits by adding 3 parity bits.

• can detect and correct any single-bit error.
• can detect but not correct a 2-bit error.

Chapter 4 – Coding 59 / 85
Hamming (7, 4) Codes

Construction of Hamming code:

Input: 4-bit message w = s1 s2 s3 s4 .

Output: 7-bit code h = s1 s2 s3 s4 s5 s6 s7

where s5 , s6 , s7 are parity (check) bits (0 or 1) defined as follows:

s1 + s3 + s4 + s5 ≡ 0 (mod 2)
s1 + s2 + s4 + s6 ≡ 0 (mod 2)
s1 + s2 + s3 + s7 ≡ 0 (mod 2)

Chapter 4 – Coding 60 / 85
Hamming (7, 4) Codes

The following diagram helps remember the construction:

The parity bits are defined in such a way that the total number of 1’s in
each of the circles A, B and C must be even.

Chapter 4 – Coding 61 / 85
Hamming (7, 4) Codes

Example 4.20
Find the Hamming (7, 4) codeword for the given word w = 0100.

Solution:

The Hamming (7, 4) codeword is 0100011.

Chapter 4 – Coding 62 / 85
Hamming (7, 4) Codes: 1-bit error

Theorem 4.21
Hamming (7, 4) Codes can correct a 1-bit error.

Chapter 4 – Coding 63 / 85
Hamming (7, 4) Codes: 1-bit error

Suppose a Hamming (7, 4) codeword s1 s2 s3 s4 s5 s6 s7 was sent and the

codeword received is t1 t2 t3 t4 t5 t6 t7 .

Assume: There is at most one single-bit error.

This single-bit error can be detected and corrected based on the parity
check on the circles A, B, C : Recall
A passes the check: s1 + s3 + s4 + s5 ≡ 0 (mod 2)
B passes the check: s1 + s2 + s4 + s6 ≡ 0 (mod 2)
C passes the check: s1 + s2 + s3 + s7 ≡ 0 (mod 2)

Chapter 4 – Coding 64 / 85
Hamming (7, 4) Codes: 1-bit error
The indicated bit is the bit that is not correct.

A .......................................................B A .......................................................B A .......................................................B

..... . ..... ..... . ..... ..... . .....
.... ......... ... .... ......... ... .... ......... ...
... ... .... ...
... ... ... .... ...
... ... s5 ...... ...... ...
...
..... ...................... . .... ...................... . .... ........................ .
... ..
... .. . ...
.. .. ... ..
. .... . ...
.. .. ... ..
. .. . ..
... ....... ....s1... ........ .. ... ....... .... ... ........ .. ... ....... .... ... ........ ..
... ... ... ... ... .... ... ... ... ... ... .... ... ... ... ... ... ....
..... .. ........ ... ...... ..... .. ........ s2 .. ..... ..... .. ........ ... ......
........ .
. . .
.. .
. ........ .
. . .
.. . .
.. ........ .
. . .
.. .
.
.................... ......................... ..................... ......................... ..................... .........................
... ... ... ... ... ...
... ... ...
.... ... .... ... .... ...
.... .... ....
.......................... C ......................... C ......................... C
...... ...... ......

All fail B,C fail A fails

Chapter 4 – Coding 65 / 85
Hamming (7, 4) Codes: 1-bit error

Error bit Parity check

s1 All circles A, B and C fail the parity check
s2 Only B and C fail the parity check
s3 Only A and C fail the parity check
s4 Only A and B fail the parity check
s5 Only A fails the parity check
s6 Only B fails the parity check
s7 Only C fails the parity check
no error All A, B and C pass the parity check
From the table we see that a 1-bit error can be detected and corrected.

Chapter 4 – Coding 66 / 85
Hamming (7, 4) Code: 1-bit error

Example 4.22
Assuming at most one error, find the original codeword of the following
Hamming (7, 4) codewords received.
(a) 1010101
(b) 0101000

Solution.
(a) 0010101 (All A, B, C fail the parity check – error in bit 1)
(b) 0111000 (Only A and C fail the parity check) – error in bit 3)

Chapter 4 – Coding 67 / 85
Hamming (7, 4) Codes: 2-bit error

Theorem 4.23
Hamming (7, 4) Codes can detect a 2 bit-error.

Chapter 4 – Coding 68 / 85
Hamming (7, 4) Codes: 2-bit error

There are 5 possible scenarios:

1. Error in s1 and one of s2 , s3 , s4 .

2. Error in s1 and one of s5 , s6 , s7 .
3. Error in 2 of s2 , s3 , s4 .
4. Error in 2 of s5 , s6 , s7 .
5. One error in s2 , s3 , s4 and one error in s5 , s6 , s7 . There are two typical
cases: (i) s2 , s5 and (ii) s2 , s6 .

In each of these, at least one circle fails.

Chapter 4 – Coding 69 / 85
Hamming (7, 4) Codes: 2-bit error

A ........... ........... ........... ........... ........... ...........

........ ...................... ........B A ........ ...................... ........B A ........ ...................... ........B
..... .. ..... ..... ... ...
..... ..... .. .....
... ... .... ...
... ... .. .....
...
... ... ... .... ...
...
.... .... ..... ... .... s 5 .. .. ... ... .... .... ..... ...
.... ..................
. . .... . . .... ..................
. .
... ......... ......... ... ... .................................. ... ... ......... ......... ...
. . .
... ..... .....s1... ......
. ... ... ...... .....s1... ...... ... ... ...... ..... ... ...... ...
.... ... ......... s ... ..... .... ... ......... ... ....
. .... ...s ......... s ... .....
...... .. .. .... ...... .. ...... .. 3 .........
...........................................2 .............. ............................................................. ...................... ............2 .. ....
..............
... ... . ...
... .. ... .. ... .
... .... ... ..... ... ....
.
..... . ..... . ..... .
....... .... C ....... .... C ....... .... C
..................... ..................... .....................
1. A fails 2. B,C fail 3. A,B fail

A ...................... ............................B A ...................... ............................B A ...................... ............................B

....... .... ..... ....... .... ..... ....... ........ .....
..... ......... ... ..... ......... ... ..... ... .. ...
... s5 ...... ...... s6 ... ... s5 ...... ...... ... ... .. .... s ...
.... .
... ..... .
... ..... .... ... ... 6 ...
... . ... .. . .
....
. .
. . ... . ... .. . .
....
. .
. . ... . ..... .
....
........ .
... .
............ .........
.. .. ... .
............ .........
.. .. ... .
........... . .. ..
... ..
.
... .... ... ..... . .
.
... ... ..
.
... .... ... ..... . .
.
... ... ..
.
... .... ... ..... . .
.
...
.... ..
...... .. ......... ... ...
.. .... .. ......... s ... ..... .... .. ......... s ... .....
...... . . ...... . .
........................................................... ..........................................2
.. ....
............ ..........................................2
.. ....
............
... ... ...
... ... ... .. ... ..
... ... ... ..
... ... ..
...
..... ... ..... . ..... .
....... ....
..... C ....... ....
. ..
.. C ....... ....
. ..
.. C
................ . ............... . ............... .
4. A,B fail 5(i). All fail 5(ii). C fails

Chapter 4 – Coding 70 / 85
Hamming (7, 4) Codes: 2-bit error

Example 4.24
Suppose there are exactly two error bits in the word t1 t2 t3 t4 t5 t6 t7
received using the Hamming (7, 4) code.

Is it possible for us to correct the errors?

Solution. NO. Here is one example: The diagram shows three instances
in which a 2-bit error occurs, with the “crosses” representing the positions
of the error bits in the received word.

Chapter 4 – Coding 71 / 85
Hamming (7, 4) Codes: 2-bit error

In all cases, only A fails the check. At the receiving end, we will not be
able to tell which pairs of errors actually occurred and thus will be unable
to correct the error..

Chapter 4 – Coding 72 / 85
Hamming (7, 4) Codes: erasure error

Example 4.25
Suppose a Hamming (7, 4) codeword was sent and the word received is
1?1?001. Assuming there is no error in the transmitted word, except that
the second and the forth bit were unrecognizable. Such a fault is called an
erasure.
What was the transmitted word?

Chapter 4 – Coding 73 / 85
Hamming (7, 4) Codes: erasure error

Theorem 4.26
Erasure error involving at most 2 bits can always be corrected.

Proof: The given figure shows the 6 typical cases where a • indicates an
erased bit. In all cases, the erased bits can be recovered.

Chapter 4 – Coding 74 / 85
Hamming (7, 4) Codes: erasure error

A ........... ........... ........... ........... ........... ...........

........ ...................... ........B A ........ ...................... ........B A ........ ...................... ........B
..... . .. .....
... ..... . .. .....
... ..... . .. .....
...
... ... .... ... ... ... .... ... ... ... .... ...
..... .... .... ... .... • .... .... ... .... .... .... ...
... .
. ....... . . .... .
. .. ..... . . .... .
. .. ..... . .
... ............. ............... ... ... ............. ............... ... ... ............. ............... ...
... .
.
.... .....• ... ...... .... ... .
.
.... .....• ... ...... .... ... .
.
.... ..... ... ...... ....
.... ... . .. . .. .... ... ......... . .. .... ... ......... . ..
...... . ...... • .
............................................................
... ...... .. ..
.........................................................
... ...... .. • ......... • ... .....
..................... ....................
. ...
... ... ...
... ... ...
... ...
...
... ... ... ..
.. ... ...
..... ... ..... .
. ..... ...
....... .
....... C
. ....... .
.... .
... C ....... .
....... C
.
................ ................ ................

A ........................................................B A ........................................................B A ........................................................B

...... ..... ..... ...... ..... ..... ...... .......
.....
.... ... ... ... .... ... ... ... .... ... ...
...
... • ..... ...... • ... ... • ...... ...... ... ... .. ... • ...
.... ......................
... ..... . .. . . ....
... ..... ......................
.
...
... ... .. ... . ..
...... .
...
. . .. ... . ..
. .. ..
... .
...... ... .. .......
. .. ... .
...... .... .... ......... .. ... .
...... .... .... ......... ..
... ..
.
.. .... .... .... . .
....
. ... ..
.
.. .... .... ... ....
. ... ..
.
.. .... .... ... .....
..... .. ....... ... .... ..... .. ......... • ... ..... ..... .. ......... • ... .....
......... .... . .. ........ . . .. . ........ . . .. .
...................... ............................ ..
...................... ...........................
..
...................... ...........................
...
... ... ... .. ... ..
.. ... .. ... ..
.... .
... .... ...
. .... .
...
......................... C ........................ C ........................ C
...... .. ...... .. ...... .
.

Chapter 4 – Coding 75 / 85
Hamming (8, 4) Codes

The Hamming (8, 4) codeword:

(a) First, take a Hamming (7, 4) codeword s1 s2 s3 s4 s5 s6 s7 .
(b) Next, add the extra bit s8 so that the total number of 1’s in
A ∪ B ∪ C is even, i.e.

s1 + s2 + s3 + s4 + s5 + s6 + s7 + s8 ≡ 0 (mod 2).

The above requirement is known as the overall parity check. It means that
the number of ‘1’ bits is even.

Chapter 4 – Coding 76 / 85
Hamming (8, 4) Codes

Example:

Hamming (8, 4) code for the message 0111 is 01110001. We put the
eighth digit outside of A ∪ B ∪ C .

Chapter 4 – Coding 77 / 85
Hamming (8, 4) Codes

Theorem 4.27
If the overall parity check fails, then there is an odd number of errors.

If the overall parity check passes, then there is an even number (including
0) of errors.

Chapter 4 – Coding 78 / 85
Hamming (8, 4) Codes

Proof. We only need to note that every error causes an odd number of
changes in the number of ‘1’ bits. Thus if the overall parity fails, there
must be an odd number of errors and if it passes, then there must an even
number of errors.

Chapter 4 – Coding 79 / 85
Hamming Codes: summary

(7, 4) codes
If there is at most 1 error, the code can correct the error if it exists.
If there are two errors, the code can detect but not correct the error.

Chapter 4 – Coding 80 / 85
Hamming Codes: summary

(8, 4) codes
The overall parity check can detect an odd number of errors.
Suppose it is known that the number of errors is at most 2.
If the overall parity check fails, then there is exactly one error and it can
be corrected.
If the overall parity passes and the parity check fails for at least one of the
circles, then there are two errors, but they cannot be corrected.
If all the parity checks pass, then there is no error.

Chapter 4 – Coding 81 / 85
Hamming (8, 4) Codes

Example 4.28
The following Hamming (8, 4) codeword is received:

00110001.

(a) How many possible errors can there be?

(b) Is it possible to detect the error and correct it if there is at most one
error?

Chapter 4 – Coding 82 / 85
Hamming (8, 4) Codes
(a) The overall parity check fails. So there must be odd number of errors.

(b) So there is exactly one error.

B, C and Overall parity fail the check.

A pass the check
Chapter 4 – Coding 83 / 85
Hamming (8, 4) Codes

Error bit Parity check

s1 All circles A, B and C fail the parity check
s2 Only B and C fail the parity check
s3 Only A and C fail the parity check
s4 Only A and B fail the parity check
s5 Only A fails the parity check
s6 Only B fails the parity check
s7 Only C fails the parity check
no error All A, B and C pass the parity check

From the table, we see that the error is in bit 2.

After correcting the error, the original message (prior to encoding) should
be 0111.

Chapter 4 – Coding 84 / 85
Hamming (8, 4) Codes

Question
What advantage does Hamming (8, 4) codes have over Hamming (7, 4)
codes?

Chapter 4 – Coding 85 / 85