程序代写代做代考 information theory algorithm COMP2610/6261 – Information Theory – Lecture 21: Hamming Codes & Coding Review

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