COMP2610/6261 – Information Theory – Lecture 21: Hamming Codes & Coding Review
COMP2610/6261 – Information Theory
Lecture 21: Hamming Codes & Coding Review
Robert C. Williamson
Research School of Computer Science
1 L O G O U S E G U I D E L I N E S T H E A U S T R A L I A N N A T I O N A L U N I V E R S I T Y
ANU Logo Use Guidelines
Deep Gold
C30 M50 Y70 K40
PMS Metallic 8620
PMS 463
Black
C0 M0 Y0 K100
PMS Process Black
Preferred logo Black version
Reverse version
Any application of the ANU logo on a coloured
background is subject to approval by the Marketing
Office, contact
brand@anu.edu.au
The ANU logo is a contemporary
reflection of our heritage.
It clearly presents our name,
our shield and our motto:
First to learn the nature of things.
To preserve the authenticity of our brand identity, there are
rules that govern how our logo is used.
Preferred logo – horizontal logo
The preferred logo should be used on a white background.
This version includes black text with the crest in Deep Gold in
either PMS or CMYK.
Black
Where colour printing is not available, the black logo can
be used on a white background.
Reverse
The logo can be used white reversed out of a black
background, or occasionally a neutral dark background.
16 October, 2018
1 / 44
Today’s plan
Noisy Channel Coding Theorem proves there exists codes with rate
R < C with arbitrarily low probability of error.
But proof was non-constructive — we used a random code in order to be
able to actually calculate error probability.
What about constructive codes?
We will focus on linear codes amd look at two simple linear codes:
repetition codes
Hamming codes
We will sketch what can be said about the rate and reliability of the latter
2 / 44
Today’s plan
Noisy Channel Coding Theorem proves there exists codes with rate
R < C with arbitrarily low probability of error.
But proof was non-constructive — we used a random code in order to be
able to actually calculate error probability.
What about constructive codes?
We will focus on linear codes amd look at two simple linear codes:
repetition codes
Hamming codes
We will sketch what can be said about the rate and reliability of the latter
2 / 44
Today’s plan
Noisy Channel Coding Theorem proves there exists codes with rate
R < C with arbitrarily low probability of error.
But proof was non-constructive — we used a random code in order to be
able to actually calculate error probability.
What about constructive codes?
We will focus on linear codes amd look at two simple linear codes:
repetition codes
Hamming codes
We will sketch what can be said about the rate and reliability of the latter
2 / 44
Today’s plan
Noisy Channel Coding Theorem proves there exists codes with rate
R < C with arbitrarily low probability of error.
But proof was non-constructive — we used a random code in order to be
able to actually calculate error probability.
What about constructive codes?
We will focus on linear codes amd look at two simple linear codes:
repetition codes
Hamming codes
We will sketch what can be said about the rate and reliability of the latter
2 / 44
1 Repetition Codes
2 The (7,4) Hamming code
Coding
Decoding
Syndrome Decoding
Multiple errors
Error Probabilities
3 Coding: Review
3 / 44
Repetition Codes
Simplest channel code: add redundancy by repeating every bit of the
message (say) 3 times:
Source sequence Transmitted sequence
s t
0 0 0 0
1 1 1 1
This repetition code is called R3.
4 / 44
Repetition Codes for the BSC
Example
On a binary symmetric channel with flip probability f , receiver sees
r = t + η
where η is a noise vector
p(ηi = 1) = f
Example setting of η, and resulting message r :
s 0 0 1 0 1 1 0
t
︷ ︸︸ ︷
0 0 0
︷ ︸︸ ︷
0 0 0
︷ ︸︸ ︷
1 1 1
︷ ︸︸ ︷
0 0 0
︷ ︸︸ ︷
1 1 1
︷ ︸︸ ︷
1 1 1
︷ ︸︸ ︷
0 0 0
η 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0
r 0 0 0 0 0 1 1 1 1 0 0 0 0 1 0 1 1 1 0 0 0
Note that elements of η are not replicated like those of t
noise acts independently on every bit
5 / 44
Repetition Codes for the BSC
Example
On a binary symmetric channel with flip probability f , receiver sees
r = t + η
where η is a noise vector
p(ηi = 1) = f
Example setting of η, and resulting message r :
s 0 0 1 0 1 1 0
t
︷ ︸︸ ︷
0 0 0
︷ ︸︸ ︷
0 0 0
︷ ︸︸ ︷
1 1 1
︷ ︸︸ ︷
0 0 0
︷ ︸︸ ︷
1 1 1
︷ ︸︸ ︷
1 1 1
︷ ︸︸ ︷
0 0 0
η 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0
r 0 0 0 0 0 1 1 1 1 0 0 0 0 1 0 1 1 1 0 0 0
Note that elements of η are not replicated like those of t
noise acts independently on every bit
5 / 44
Beyond Repetition Codes
Goal: Communication with small probability of error and high rate:
Repetition codes introduce redundancy on a per-bit basis
Can we improve on this?
Idea: Introduce redundancy to blocks of data instead
Block Code
A block code is a rule for encoding a length-K sequence of source bits s
into a length-N sequence of transmitted bits t.
Introduce redundancy: N > K
Focus on Linear codes
We will introduce a simple type of block code called
the (7,4) Hamming code
6 / 44
Beyond Repetition Codes
Goal: Communication with small probability of error and high rate:
Repetition codes introduce redundancy on a per-bit basis
Can we improve on this?
Idea: Introduce redundancy to blocks of data instead
Block Code
A block code is a rule for encoding a length-K sequence of source bits s
into a length-N sequence of transmitted bits t.
Introduce redundancy: N > K
Focus on Linear codes
We will introduce a simple type of block code called
the (7,4) Hamming code
6 / 44
Beyond Repetition Codes
Goal: Communication with small probability of error and high rate:
Repetition codes introduce redundancy on a per-bit basis
Can we improve on this?
Idea: Introduce redundancy to blocks of data instead
Block Code
A block code is a rule for encoding a length-K sequence of source bits s
into a length-N sequence of transmitted bits t.
Introduce redundancy: N > K
Focus on Linear codes
We will introduce a simple type of block code called
the (7,4) Hamming code
6 / 44
Beyond Repetition Codes
Goal: Communication with small probability of error and high rate:
Repetition codes introduce redundancy on a per-bit basis
Can we improve on this?
Idea: Introduce redundancy to blocks of data instead
Block Code
A block code is a rule for encoding a length-K sequence of source bits s
into a length-N sequence of transmitted bits t.
Introduce redundancy: N > K
Focus on Linear codes
We will introduce a simple type of block code called
the (7,4) Hamming code
6 / 44
An Example
The (7, 4) Hamming Code
Consider K = 4, and a source message s = 1 0 0 0
The repetition code R2 produces
t = 1 1 0 0 0 0 0 0
The (7,4) Hamming code produces
t = 1 0 0 0 1 0 1
Redundancy, but not repetition
How are these magic bits computed?
7 / 44
1 Repetition Codes
2 The (7,4) Hamming code
Coding
Decoding
Syndrome Decoding
Multiple errors
Error Probabilities
3 Coding: Review
8 / 44
The (7,4) Hamming code
Coding
Consider K = 4, N = 7 and s = 1 0 0 0
9 / 44
The (7,4) Hamming code
Coding
Consider K = 4, N = 7 and s = 1 0 0 0
9 / 44
The (7,4) Hamming code
Coding
Copy the source bits into the the first 4 target bits:
10 / 44
The (7,4) Hamming code
Coding
Set parity-check bits so that the number of ones within each circle is even:
So we have s = 1 0 0 0
encoder−→ t = 1 0 0 0 1 0 1
11 / 44
The (7,4) Hamming code
Coding
Algebraically, we have set:
ti = si for i = 1, . . . , 4
t5 = s1 ⊕ s2 ⊕ s3
t6 = s2 ⊕ s3 ⊕ s4
t7 = s1 ⊕ s3 ⊕ s4
where we use modulo-2 arithmetic
12 / 44
The (7,4) Hamming code
Coding
In matrix form:
t = GT s with GT =
[
I4
P
]
=
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
1 1 1 0
0 1 1 1
1 0 1 1
,
where s =
[
s1 s2 s3 s4
]T
G is called the Generator matrix of the code.
The Hamming code is linear!
13 / 44
The (7,4) Hamming code:
Codewords
Each (unique) sequence that can be transmitted is called a codeword.
Codeword examples:
s Codeword (t)
0010 0010111
0110 0110001
1010 1010010
1110 ?
For the (7,4) Hamming code we have a total of 16 codewords
14 / 44
The (7,4) Hamming code
Codewords
Write
GT =
[
G1· G2· G3· G4·
]
where each Gi· is a 7 dimensional bit vector
Then, the transmitted message is
t = GT s
=
[
G1· G2· G3· G4·
]
s
= s1G1· + . . .+ s4G4·
15 / 44
The (7,4) Hamming code:
Codewords
There are 27 possible transmitted bit strings
There are 27 − 24 other bit strings that immediately imply corruption
If we see a codeword, does that imply no corruption?
Any two codewords differ in at least three bits
Each original bit belongs to at least two circles
Useful in constructing reliable decoders
16 / 44
1 Repetition Codes
2 The (7,4) Hamming code
Coding
Decoding
Syndrome Decoding
Multiple errors
Error Probabilities
3 Coding: Review
17 / 44
The (7,4) Hamming code:
Decoding
We can encode a length-4 sequence s into a length-7 sequence t using 3
parity check bits
t can be corrupted by noise which can flip any of the 7 bits (including the
parity check bits):
s 1 0 0 0
t
︷ ︸︸ ︷
1 0 0 0 1 0 1
η 0 1 0 0 0 0 0
r 1 1 0 0 1 0 1
How should we decode r?
We could do this exhaustively using the 16 codewords
Assuming BSC, uniform p(s): Get the most probable explanation
Find s such that ‖t(s) r‖1 is minimum
We can get the most probable source vector in an more efficient way.
18 / 44
The (7,4) Hamming code:
Decoding
We can encode a length-4 sequence s into a length-7 sequence t using 3
parity check bits
t can be corrupted by noise which can flip any of the 7 bits (including the
parity check bits):
s 1 0 0 0
t
︷ ︸︸ ︷
1 0 0 0 1 0 1
η 0 1 0 0 0 0 0
r 1 1 0 0 1 0 1
How should we decode r?
We could do this exhaustively using the 16 codewords
Assuming BSC, uniform p(s): Get the most probable explanation
Find s such that ‖t(s) r‖1 is minimum
We can get the most probable source vector in an more efficient way.
18 / 44
The (7,4) Hamming code:
Decoding
We can encode a length-4 sequence s into a length-7 sequence t using 3
parity check bits
t can be corrupted by noise which can flip any of the 7 bits (including the
parity check bits):
s 1 0 0 0
t
︷ ︸︸ ︷
1 0 0 0 1 0 1
η 0 1 0 0 0 0 0
r 1 1 0 0 1 0 1
How should we decode r?
We could do this exhaustively using the 16 codewords
Assuming BSC, uniform p(s): Get the most probable explanation
Find s such that ‖t(s) r‖1 is minimum
We can get the most probable source vector in an more efficient way.
18 / 44
The (7,4) Hamming code:
Decoding
We can encode a length-4 sequence s into a length-7 sequence t using 3
parity check bits
t can be corrupted by noise which can flip any of the 7 bits (including the
parity check bits):
s 1 0 0 0
t
︷ ︸︸ ︷
1 0 0 0 1 0 1
η 0 1 0 0 0 0 0
r 1 1 0 0 1 0 1
How should we decode r?
We could do this exhaustively using the 16 codewords
Assuming BSC, uniform p(s): Get the most probable explanation
Find s such that ‖t(s) r‖1 is minimum
We can get the most probable source vector in an more efficient way.
18 / 44
The (7,4) Hamming code:
Decoding Example 1
We have s = 1 0 0 0
encoder−→ t = 1 0 0 0 1 0 1 noise−→ r = 1 1 0 0 1 0 1:
(1) Detect circles with wrong (odd) parity
I What bit is responsible for this?
19 / 44
The (7,4) Hamming code:
Decoding Example 1
We have s = 1 0 0 0
encoder−→ t = 1 0 0 0 1 0 1 noise−→ r = 1 1 0 0 1 0 1:
(2) Detect culprit bit and flip it
The decoded sequence is ŝ = 1 0 0 0
20 / 44
The (7,4) Hamming code:
Decoding Example 2
We have s = 1 0 0 0
encoder−→ t = 1 0 0 0 1 0 1 noise−→ r = 1 0 0 0 0 0 1:
(1) Detect circles with wrong (odd) parity
I What bit is responsible for this?
21 / 44
The (7,4) Hamming code:
Decoding Example 2
We have s = 1 0 0 0
encoder−→ t = 1 0 0 0 1 0 1 noise−→ r = 1 0 0 0 0 0 1:
(2) Detect culprit bit and flip it
The decoded sequence is ŝ = 1 0 0 0
22 / 44
The (7,4) Hamming code:
Decoding Example 3
We have s = 1 0 0 0
encoder−→ t = 1 0 0 0 1 0 1 noise−→ r = 1 0 1 0 1 0 1:
(1) Detect circles with wrong (odd) parity
I What bit is responsible for this?
23 / 44
The (7,4) Hamming code:
Decoding Example 3
We have s = 1 0 0 0
encoder−→ t = 1 0 0 0 1 0 1 noise−→ r = 1 0 1 0 1 0 1:
(2) Detect culprit bit and flip it
The decoded sequence is ŝ = 1 0 0 0
24 / 44
1 Repetition Codes
2 The (7,4) Hamming code
Coding
Decoding
Syndrome Decoding
Multiple errors
Error Probabilities
3 Coding: Review
25 / 44
The (7,4) Hamming code:
Optimal Decoding Algorithm: Syndrome Decoding
Given r = r1, . . . , r7, assume BSC with small noise level f :
1 Define the syndrome as the length-3 vector z that describes the
pattern of violations of the parity bits r5, r6, r7.
I zi = 1 when the i th parity bit does not match the parity of r
I Flipping a single bit leads to a different syndrome
2 Check parity bits r5, r6, r7 and identify the syndrome
3 Unflip the single bit responsible for this pattern of violation
I This syndrome could have been caused by other noise patterns
z 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1
Flip bit none r7 r6 r4 r5 r1 r2 r3
The optimal decoding algorithm unflips at most one bit
26 / 44
The (7,4) Hamming code:
Optimal Decoding Algorithm: Syndrome Decoding
Given r = r1, . . . , r7, assume BSC with small noise level f :
1 Define the syndrome as the length-3 vector z that describes the
pattern of violations of the parity bits r5, r6, r7.
I zi = 1 when the i th parity bit does not match the parity of r
I Flipping a single bit leads to a different syndrome
2 Check parity bits r5, r6, r7 and identify the syndrome
3 Unflip the single bit responsible for this pattern of violation
I This syndrome could have been caused by other noise patterns
z 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1
Flip bit none r7 r6 r4 r5 r1 r2 r3
The optimal decoding algorithm unflips at most one bit
26 / 44
The (7,4) Hamming code:
Optimal Decoding Algorithm: Syndrome Decoding
Given r = r1, . . . , r7, assume BSC with small noise level f :
1 Define the syndrome as the length-3 vector z that describes the
pattern of violations of the parity bits r5, r6, r7.
I zi = 1 when the i th parity bit does not match the parity of r
I Flipping a single bit leads to a different syndrome
2 Check parity bits r5, r6, r7 and identify the syndrome
3 Unflip the single bit responsible for this pattern of violation
I This syndrome could have been caused by other noise patterns
z 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1
Flip bit none r7 r6 r4 r5 r1 r2 r3
The optimal decoding algorithm unflips at most one bit
26 / 44
The (7,4) Hamming code:
Optimal Decoding Algorithm: Syndrome Decoding
Given r = r1, . . . , r7, assume BSC with small noise level f :
1 Define the syndrome as the length-3 vector z that describes the
pattern of violations of the parity bits r5, r6, r7.
I zi = 1 when the i th parity bit does not match the parity of r
I Flipping a single bit leads to a different syndrome
2 Check parity bits r5, r6, r7 and identify the syndrome
3 Unflip the single bit responsible for this pattern of violation
I This syndrome could have been caused by other noise patterns
z 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1
Flip bit none r7 r6 r4 r5 r1 r2 r3
The optimal decoding algorithm unflips at most one bit
26 / 44
The (7,4) Hamming code:
Optimal Decoding Algorithm: Syndrome Decoding
Given r = r1, . . . , r7, assume BSC with small noise level f :
1 Define the syndrome as the length-3 vector z that describes the
pattern of violations of the parity bits r5, r6, r7.
I zi = 1 when the i th parity bit does not match the parity of r
I Flipping a single bit leads to a different syndrome
2 Check parity bits r5, r6, r7 and identify the syndrome
3 Unflip the single bit responsible for this pattern of violation
I This syndrome could have been caused by other noise patterns
z 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1
Flip bit none r7 r6 r4 r5 r1 r2 r3
The optimal decoding algorithm unflips at most one bit
26 / 44
The (7,4) Hamming code:
Syndrome Decoding: Matrix Form
Recall that we just need to compare the expected parity bits with the
actual ones we received:
z1 = r1 ⊕ r2 ⊕ r3 r5
z2 = r2 ⊕ r3 ⊕ r4 r6
z3 = r1 ⊕ r3 ⊕ r4 r7,
but in modulo-2 arithmetic −1 ≡ 1 so we can replace with ⊕ so we
have:
z = Hr with H =
[
P I3
]
=
1 1 1 0 1 0 00 1 1 1 0 1 0
1 0 1 1 0 0 1
Homework: What is the syndrome for a codeword?
27 / 44
The (7,4) Hamming code:
Syndrome Decoding: Matrix Form
Recall that we just need to compare the expected parity bits with the
actual ones we received:
z1 = r1 ⊕ r2 ⊕ r3 r5
z2 = r2 ⊕ r3 ⊕ r4 r6
z3 = r1 ⊕ r3 ⊕ r4 r7,
but in modulo-2 arithmetic −1 ≡ 1 so we can replace with ⊕ so we
have:
z = Hr with H =
[
P I3
]
=
1 1 1 0 1 0 00 1 1 1 0 1 0
1 0 1 1 0 0 1
Homework: What is the syndrome for a codeword?
27 / 44
The (7,4) Hamming code:
Syndrome Decoding: Matrix Form
Recall that we just need to compare the expected parity bits with the
actual ones we received:
z1 = r1 ⊕ r2 ⊕ r3 r5
z2 = r2 ⊕ r3 ⊕ r4 r6
z3 = r1 ⊕ r3 ⊕ r4 r7,
but in modulo-2 arithmetic −1 ≡ 1 so we can replace with ⊕ so we
have:
z = Hr with H =
[
P I3
]
=
1 1 1 0 1 0 00 1 1 1 0 1 0
1 0 1 1 0 0 1
Homework: What is the syndrome for a codeword?
27 / 44
1 Repetition Codes
2 The (7,4) Hamming code
Coding
Decoding
Syndrome Decoding
Multiple errors
Error Probabilities
3 Coding: Review
28 / 44
The (7,4) Hamming code:
Optimal Decoding Algorithm: Syndrome Decoding
When the noise level f on the BSC is small, it may be reasonable that we
see only a single bit flip in a sequence of 4 bits
The syndrome decoding method exactly recovers the source message in
this case
c.f. Noise flipping one bit in the repetition code R3
But what happens if the noise flips more than one bit?
29 / 44
The (7,4) Hamming code:
Decoding Example 4: Flipping 2 Bits
We have s = 1 0 0 0
encoder−→ t = 1 0 0 0 1 0 1 noise−→ r = 1 0 1 0 1 0 0:
(1) Detect circles with wrong (odd) parity
I What bit is responsible for this?
30 / 44
The (7,4) Hamming code:
Decoding Example 4: Flipping 2 Bits
We have s = 1 0 0 0
encoder−→ t = 1 0 0 0 1 0 1 noise−→ r = 1 0 1 0 1 0 0:
(2) Detect culprit bit and flip it
The decoded sequence is ŝ = 1 1 1 0
I We have made 3 errors but only 2 involve the actual message
31 / 44
The (7,4) Hamming code:
Decoding Exercises
[Mackay, Ex 1.5]: Decode the following sequences using the syndrome
decoding for the (7,4) Hamming code:
(a) r = 1101011→ ŝ =??
(b) r = 0110110→ ŝ =??
(c) r = 0100111→ ŝ =??
(d) r = 1111111→ ŝ =??
Work out the answers on your own.
32 / 44
The (7,4) Hamming code: Solution
For each exercise we simply compute the syndrome and use the optimal
decoding algorithm (Table above) to determine which bit we should unflip.
(a) r = 1101011→: z1 = r1 ⊕ r2 ⊕ r3 ⊕ r5 = 0 z2 = r2 ⊕ r3 ⊕ r4 ⊕ r6 =
1 z3 = r1 ⊕ r3 ⊕ r4 ⊕ r7 = 1 Therefore z = 011, we unflip r4,
ŝ = 1100
(b) r = 0110110→ z = 111, we unflip r3, ŝ = 0100
(c) r = 0100111→ z = 001, we unflip r7, ŝ = 0100
(d) r = 1111111→ z = 000, we don’t unflip any bit, ŝ = 1111
33 / 44
The (7,4) Hamming code:
Zero-Syndrome Noise Vectors
[Mackay, Ex 1.7] Find some noise vectors that give the all-zero syndrome
(so that the optimal decoding algorithm will not correct them). How many
of these vectors are there?
34 / 44
Solution
By definition we have that the all-zero syndrome implies that the
corresponding noise components should cancel out. For example for the
first component we have:
z1 = r1 ⊕ r2 ⊕ r3 ⊕ r5 = t1 ⊕ t2 ⊕ t3 ⊕ t5 ⊕ η1 ⊕ η2 ⊕ η3 ⊕ η5. But ti = si for
i = 1, . . . , 4 and t5 = s1 ⊕ s2 ⊕ s3. Therefore
z1 = 2s1 ⊕ 2s2 ⊕ 2s3 ⊕ η1 ⊕ η2 ⊕ η3 ⊕ η5 = η1 ⊕ η2 ⊕ η3 ⊕ η5. Thus, we
have:
z1 = η1 ⊕ η2 ⊕ η3 ⊕ η5 = 0
z2 = η2 ⊕ η3 ⊕ η4 ⊕ η6 = 0
z3 = η1 ⊕ η3 ⊕ η4 ⊕ η7 = 0
which is equivalent to:
η5 = η1 ⊕ η2 ⊕ η3
η6 = η2 ⊕ η3 ⊕ η4
η7 = η1 ⊕ η3 ⊕ η4
35 / 44
Solution (cont.)
As η5 is determined by η1, η2, η3 we have 23 = 8 possibilities here.
Now, for fixed η1, η2 (and η3) in the previous step we only have two
possibilities for η4, which determines η6.
We have now that all the variables are set and η7 is fully determined by
their values.
Thus, we have 8× 2× 1 possible noise vectors that yield the all-zero
syndrome.
The trivial noise vectors that yield this syndrome are: η = 0000000 and
η = 1111111.
However, we can follow the above procedure and set the corresponding
variables.
This is equivalent to having arbitrary settings for η1, η2, η3 and η4 which
gives us 16 possible noise vectors which exactly correspond to the 16
codewords of the (7,4) Hamming code.
36 / 44
1 Repetition Codes
2 The (7,4) Hamming code
Coding
Decoding
Syndrome Decoding
Multiple errors
Error Probabilities
3 Coding: Review
37 / 44
The (7,4) Hamming code:
Error Probabilities
Decoding Error : Occurs if at least one of the decoded bits ŝi does not
match the corresponding source bit si for i = 1, . . . 4
p(Block Error) : pB = p(ŝ 6= s)
p(Bit Error) : pb =
1
K
K∑
k=1
p(ŝk 6= sk)
Rate : R =
K
N
=
4
7
What is the probability of block error for the (7,4) Hamming code with
f = 0.1?
38 / 44
The (7,4) Hamming code:
Error Probabilities
Decoding Error : Occurs if at least one of the decoded bits ŝi does not
match the corresponding source bit si for i = 1, . . . 4
p(Block Error) : pB = p(ŝ 6= s)
p(Bit Error) : pb =
1
K
K∑
k=1
p(ŝk 6= sk)
Rate : R =
K
N
=
4
7
What is the probability of block error for the (7,4) Hamming code with
f = 0.1?
38 / 44
The (7,4) Hamming code:
Error Probabilities
Decoding Error : Occurs if at least one of the decoded bits ŝi does not
match the corresponding source bit si for i = 1, . . . 4
p(Block Error) : pB = p(ŝ 6= s)
p(Bit Error) : pb =
1
K
K∑
k=1
p(ŝk 6= sk)
Rate : R =
K
N
=
4
7
What is the probability of block error for the (7,4) Hamming code with
f = 0.1?
38 / 44
The (7,4) Hamming code:
Error Probabilities
Decoding Error : Occurs if at least one of the decoded bits ŝi does not
match the corresponding source bit si for i = 1, . . . 4
p(Block Error) : pB = p(ŝ 6= s)
p(Bit Error) : pb =
1
K
K∑
k=1
p(ŝk 6= sk)
Rate : R =
K
N
=
4
7
What is the probability of block error for the (7,4) Hamming code with
f = 0.1?
38 / 44
The (7,4) Hamming code:
Error Probabilities
Decoding Error : Occurs if at least one of the decoded bits ŝi does not
match the corresponding source bit si for i = 1, . . . 4
p(Block Error) : pB = p(ŝ 6= s)
p(Bit Error) : pb =
1
K
K∑
k=1
p(ŝk 6= sk)
Rate : R =
K
N
=
4
7
What is the probability of block error for the (7,4) Hamming code with
f = 0.1?
38 / 44
The (7,4) Hamming code:
Leading-Term Error Probabilities
Block Error: This occurs when 2 or more bits in the block of 7 are flipped
We can approximate pB to the leading term:
pB =
7∑
m=2
(
7
m
)
f m(1− f )7−m
≈
(
7
2
)
f 2 = 21f 2.
39 / 44
The (7,4) Hamming code:
Leading-Term Error Probabilities
Bit Error: Given that a block error occurs, the noise must corrupt 2 or more
bits
The most probable case is when the noise corrupts 2 bits, which induces 3
errors in the decoded vector:
p(ŝi 6= si) ≈
3
7
pB for i = 1, . . . , 7
All bits are equally likely to be corrupted (due to symmetry)
pb ≈
3
7
pB ≈ 9f 2
40 / 44
The (7,4) Hamming code:
Leading-Term Error Probabilities
Bit Error: Given that a block error occurs, the noise must corrupt 2 or more
bits
The most probable case is when the noise corrupts 2 bits, which induces 3
errors in the decoded vector:
p(ŝi 6= si) ≈
3
7
pB for i = 1, . . . , 7
All bits are equally likely to be corrupted (due to symmetry)
pb ≈
3
7
pB ≈ 9f 2
40 / 44
The (7,4) Hamming code:
Leading-Term Error Probabilities
Bit Error: Given that a block error occurs, the noise must corrupt 2 or more
bits
The most probable case is when the noise corrupts 2 bits, which induces 3
errors in the decoded vector:
p(ŝi 6= si) ≈
3
7
pB for i = 1, . . . , 7
All bits are equally likely to be corrupted (due to symmetry)
pb ≈
3
7
pB ≈ 9f 2
40 / 44
The (7,4) Hamming code:
Leading-Term Error Probabilities
Bit Error: Given that a block error occurs, the noise must corrupt 2 or more
bits
The most probable case is when the noise corrupts 2 bits, which induces 3
errors in the decoded vector:
p(ŝi 6= si) ≈
3
7
pB for i = 1, . . . , 7
All bits are equally likely to be corrupted (due to symmetry)
pb ≈
3
7
pB ≈ 9f 2
40 / 44
What Can Be Achieved with Hamming Codes?
0
0.02
0.04
0.06
0.08
0.1
0 0.2 0.4 0.6 0.8 1
Rate
H(7,4)
more useful codesR5
R3
BCH(31,16)
R1
BCH(15,7)
pb 0.10.011e-05
1e-10
1e-15
0 0.2 0.4 0.6 0.8 1
Rate
H(7,4)
more useful codes
R5
BCH(511,76)
BCH(1023,101)
R1
H(7,4) improves pb at a moderate rate R = 4/7
BCH are a generalization of Hamming codes.
41 / 44
1 Repetition Codes
2 The (7,4) Hamming code
Coding
Decoding
Syndrome Decoding
Multiple errors
Error Probabilities
3 Coding: Review
42 / 44
Coding: Review
The Big Picture
Copyright Cambridge University Press 2003. On-screen viewing permitted. Printing not permitted. http://www.cambridge.org/0521642981
You can buy this book for 30 pounds or $50. See http://www.inference.phy.cam.ac.uk/mackay/itila/ for links.
9
Communication over a Noisy Channel
9.1 The big picture
Noisy
channel
Encoder Decoder
Compressor Decompressor
Source
coding
Channel
coding
Source
!
”
”
”
#
#
In Chapters 4–6, we discussed source coding with block codes, symbol codes
and stream codes. We implicitly assumed that the channel from the compres-
sor to the decompressor was noise-free. Real channels are noisy. We will now
spend two chapters on the subject of noisy-channel coding – the fundamen-
tal possibilities and limitations of error-free communication through a noisy
channel. The aim of channel coding is to make the noisy channel behave like
a noiseless channel. We will assume that the data to be transmitted has been
through a good compressor, so the bit stream has no obvious redundancy. The
channel code, which makes the transmission, will put back redundancy of a
special sort, designed to make the noisy received signal decodeable.
Suppose we transmit 1000 bits per second with p0 = p1 = 1/2 over a
noisy channel that flips bits with probability f = 0.1. What is the rate of
transmission of information? We might guess that the rate is 900 bits per
second by subtracting the expected number of errors per second. But this is
not correct, because the recipient does not know where the errors occurred.
Consider the case where the noise is so great that the received symbols are
independent of the transmitted symbols. This corresponds to a noise level of
f = 0.5, since half of the received symbols are correct due to chance alone.
But when f = 0.5, no information is transmitted at all.
Given what we have learnt about entropy, it seems reasonable that a mea-
sure of the information transmitted is given by the mutual information between
the source and the received signal, that is, the entropy of the source minus the
conditional entropy of the source given the received signal.
We will now review the definition of conditional entropy and mutual in-
formation. Then we will examine whether it is possible to use such a noisy
channel to communicate reliably. We will show that for any channel Q there
is a non-zero rate, the capacity C(Q), up to which information can be sent
146
Source Coding for Compression
Shrink sequences
Identify and remove redundancy
Size limited by entropy
Source Coding Theorems
(Block & Variable Length)
Channel Coding for Reliability
Protect sequences
Add known form of redundancy
Rate limited by capacity
Noisy-Channel Coding Theorem
43 / 44
Repetition Codes
The (7,4) Hamming code
Coding
Decoding
Syndrome Decoding
Multiple errors
Error Probabilities
Coding: Review