ELEC1010 Tutorial 9

Channel Coding
 Error Detection

 Error Correction

Channel Capacity

Raymundo TANG TANG, Dept. Of Electronic and Computer Eng., HKUST

Channel Coding
 Adds redundant bits for protection.
 Creates systematic redundancy.

 Helps receivers to detect and possibly recover bit errors.

 Bit stream is encoded before transmission.

 Two purpose of channel coding:

 Error detection
 Error correction

2 Raymundo TANG TANG, Dept. of Electronic and Computer Eng., HKUST

Channel Coding
Error detection

Allows a receiver to identify transmission errors and take

actions:
 Ignore the received signal and reconstruct from other signals
 Request re-transmission

 How to detect errors?

 Use only a subset of possible binary sequences.
 Anything that is outside that set is an error.

3 Raymundo TANG TANG, Dept. of Electronic and Computer Eng., HKUST

Channel Coding
Error detection – Parity Check
 Add an extra bit (parity bit or check bit) to the stream.
 Even parity: the binary code to be sent should have an

even number of “1”.

Odd parity, the binary code to be sent should have an odd
number of “1”.
Input Codeword
0000 Even parity
000
0001 Odd parity
1100 Even parity
110
1101 Odd parity
4 Raymundo TANG TANG, Dept. of Electronic and Computer Eng., HKUST
Channel Coding
Error detection – Block Code

 Divide the input into blocks.

 Encode one block at a time
A (n, k) code: k is the number of information, n is the total
number of bits to be transmitted, n – k is the number of
check bits.
 Code Rate: R = k/n 𝑁𝑜. 𝑜𝑓 𝐷𝑎𝑡𝑎 𝐵𝑖𝑡𝑠
𝐶𝑜𝑑𝑒 𝑅𝑎𝑡𝑒 𝑅 =
𝑁𝑜. 𝑜𝑓 𝐷𝑎𝑡𝑎 𝐵𝑖𝑡𝑠 + 𝑁𝑜. 𝑜𝑓 𝐸𝑥𝑡𝑟𝑎 𝐵𝑖𝑡𝑠

Note: This formula will be given during the final exam.

5 Raymundo TANG TANG, Dept. of Electronic and Computer Eng., HKUST

Channel Coding – Block Code Exercise 1
The input data stream is 00011011, use a (3, 2) block code, suppose
even parity is used, what is the encoded bit sequence?
Answer: (3,2) means: 3 bits are transmitted for every 2 bits data.
00011011=>00 01 10 11=>000 011 101 110
Input Codeword
00 000
01 011
valid codewords
10 101
11 110

001, 010, 100, 111 are invalid codewords!

If you receive 001010101110 =>errors occur in first and second block
Any single bit error can be detected.
6 Raymundo TANG TANG, Dept. of Electronic and Computer Eng., HKUST
Channel Coding – Block Code Exercise 2

How many valid codewords are there in a (4, 3) block code?

A. 4
B. 5
C. 8
D. 16
E. 32

Answer: C
23=8 codewords: 0000, 0011,…1111

7 Raymundo TANG TANG, Dept. of Electronic and Computer Eng., HKUST

Parity Check Detects All Errors with Odd Number of bit Errors

• Suppose we use even parity, and an “e” (= 110 0101) is keyed in. The “e”
is then encoded as “0110 0101” to be sent out.
• Now, if the code is received as “0110 1101”, which consists of 5 “1”s, we
immediately know that it is an invalid code. The sender will be
requested to resend the data.
• Clearly, if two errors occur, for example, the intended “e” is received
as “0100 1101”, then we may incorrectly decode it as an “M”.
• Parity check achieves error detection of all odd number of errors.

11 Raymundo TANG TANG, Dept. of Electronic and Computer Eng., HKUST

Channel Coding

Error Correction
 If you receive 001 in even parity
 There is an error.

 Possible correct codewords are: 000, 011, 110, 101

 What should one do when 100% correct decoding of the

original data is necessary?
 Retransmission
 Automatic correction

12 Raymundo TANG TANG, Dept. of Electronic and Computer Eng., HKUST

Channel Coding
Error Correction – Repetition Code
 Each bit is repeated at least twice.
 e.g. 0 is encoded as 000
1 is encoded as 111
1001 is encoded as 111000000111
If I receive 110100010011, the sequence being send
is 1001
 It decodes incorrectly for 2-bit or 3-bit errors
 Not efficient
13 Raymundo TANG TANG, Dept. of Electronic and Computer Eng., HKUST
Channel Coding – Repetition Code Exercise

What is the maximum number of bit(s) error that a (5, 1) repetition

code can correct in a block of 5 bits?

A. 5
B. 4
C. 3
D. 2
E. 1

Answer: D
eg. 0 -> 00000, 1->11111 (max = 2 errors)

14 Raymundo TANG TANG, Dept. of Electronic and Computer Eng., HKUST

Channel Coding
Error Correction – Two-Dimension Parity Code
 Arrange data in a N×N block.
 Add a parity bit (even parity) for each column.
 Add a parity bit (even parity) for each row.
 Can correct all 1-bit errors in a data block of N×N bits.
 The efficiency (code rate)= N×N/(N×N+2N).
1 0 0 1 1 1 1 0 0 1 1 1
1 0 1 0 0 0 1 0 1 0 0 0
1 0 1 0 1 1 0 0 1 0 1 1
0 1 0 1 1 1 0 1 0 1 1 1
0 1 0 0 1 0 0 1 0 0 1 0
1 0 0 0 0 1 0 0 0 0

15 Raymundo TANG TANG, Dept. of Electronic and Computer Eng., HKUST

Channel Coding – Two-Dimension Parity Code Exercise
Two dimensional parity checking involves arranging the data in a N x
N block, with a parity bit added to each column and each row of the
block. A two dimensional parity checking table is shown below:

Assume that even parity is used and there

1 0 0 0 1
is no error in the block. Which of the
1 (i) 1 0 1 following is correct?
1 1 (ii) 0 0
A. (i)=0, (ii)=0, (iii)=0
1 0 1 (iii) 1
B. (i)=1, (ii)=1, (iii)=1
0 0 0 1 C. (i)=1, (ii)=0, (iii)=1
D. (i)=0, (ii)=1, (iii)=0
E. (i)=1, (ii)=0, (iii)=0

Answer: C
16 Raymundo TANG TANG, Dept. of Electronic and Computer Eng., HKUST
More on Logic Gates
XOR Gate
X⨁𝑌 = 𝑋. 𝑌 + 𝑋. 𝑌
o Notice that an XOR gate can have two or more inputs.

o The XOR function is an odd function, which has a value of 1 when the
combination of all the inputs have an odd number of 1s (1, 3, 5, . . .).
Observe in the table above that 01 and 10 have an odd number of 1s -
that is, one 1).
o FXOR = FODD for more than two inputs too
(e.g. For ABC=001 => A⨁𝐵⨁𝐶 = 1 (One 1).
For ABC=111 => A⨁𝐵⨁𝐶 = 1 (Three 1).
For ABC=110 => A⨁𝐵⨁𝐶 = 0 (Two 1).
17 Raymundo TANG TANG, Dept. of Electronic and Computer Eng., HKUST
Decoding using 2D parity code - 1
Noisy channel Block (8b) Even 2D parity code (8,4) ε = 0.1, BSC
10001100
(received)
10001100 d0 d1 p0 r0 1 0 1
11001100
d2 d3 p1 r1 0 0 1
10111001
01011110…
p2 p3 0 0
codewords
c0 c1
Key things: Our decoding scheme:
• We don’t know the original bit streams
• We only know the design of the codewords (r0, r1, c0, c1) Decoded bits
• We try to guess the original bits with the (0, 0, 0, 0) -> no error -> (d0,d1,d2,d3)
highest possibility (1, 0, 1, 0) -> d0 error -> (𝑑0,d1,d2,d3)
(1, 0, 0, 1) -> d1 error -> (d0, 𝑑1,d2,d3)
r0 = d0 ⨁ d1 ⨁ p0 (0, 1, 1, 0) -> d2 error -> (d0,d1, 𝑑2,d3)
r1 = d2 ⨁ d3 ⨁ p1 (0, 1, 0, 1) -> d3 error -> (d0,d1,d2, 𝑑3)
c0 = d0 ⨁ d2 ⨁ p2 (1, 0, 0, 0) -> p0 error -> (d0,d1,d2,d3)
c1 = d1 ⨁ d3 ⨁ p3 (0, 1, 0, 0) -> p1 error -> (d0,d1,d2,d3)
(0, 0, 1, 0) -> p2 error -> (d0,d1,d2,d3)
(r0, r1, c0, c1)
Aim: eliminate 1-bit errors (0, 0, 0, 1) -> p3 error -> (d0,d1,d2,d3)

18 Raymundo TANG TANG, Dept. of Electronic and Computer Eng., HKUST

Decoding using 2D parity code - 2
Noisy channel Block (8b) Even 2D parity code (8,4)
11001100
ε = 0.1, BSC
(received)
10001100 d0 d1 p0 r0 1 1 1
11001100
d2 d3 p1 r1 0 0 1
10111001
01011110…
p2 p3 0 0
codewords
c0 c1
Our complete and deterministic decoding scheme: Aim: detect 1-bit error
(r0, r1, c0, c1) Decoded bits
(0, 0, 0, 0) -> no error -> (d0,d1,d2,d3)
(1, 0, 1, 0) -> d0 error -> (𝑑0,d1,d2,d3) (r0, r1, c0, c1) Bits (decoded)
(1, 0, 0, 1) -> d1 error -> (d0, 𝑑1,d2,d3)
(0, 1, 1, 0) -> d2 error -> (d0,d1, 𝑑2,d3) (1, 1, 1, 1) 1100
(0, 1, 0, 1) -> d3 error -> (d0,d1,d2, 𝑑3)
(1, 0, 0, 0) -> p0 error -> (d0,d1,d2,d3) We keep the received bits unchanged (i.e. we
(0, 1, 0, 0) -> p1 error -> (d0,d1,d2,d3) are just guessing that the message received is
(0, 0, 1, 0) -> p2 error -> (d0,d1,d2,d3) correct). This may decode bits correctly (for
(0, 0, 0, 1) -> p3 error -> (d0,d1,d2,d3) example, 0011 for 4-bit error in p0-p3)
Others -> no idea -> (d0,d1,d2,d3)
19 Raymundo TANG TANG, Dept. of Electronic and Computer Eng., HKUST
 Decoding using 2D parity code - 3
Noisy channel ε = 0.1, BSC
Block (8b) Even 2D parity code (8,4)
(received) 10111001 01011110
10001100 d0 d1 p0 r 1 0 1 0 1 1
11001100
d2 d3 p1 0 1 1 0
10111001 0 1 1
01011110… r1
p2 p3 0 1 1 0
codewords
c0 c1
Our complete and deterministic decoding scheme: Aim: detect 1-bit error
(r0, r1, c0, c1) Decoded bits
(0, 0, 0, 0) -> no error -> (d0,d1,d2,d3)
(1, 0, 1, 0) -> d0 error -> (𝑑0,d1,d2,d3) (r0, r1, c0, c1) Bits (decoded)
(1, 0, 0, 1) -> d1 error -> (d0, 𝑑1,d2,d3)
(0, 1, 1, 0) -> d2 error -> (d0,d1, 𝑑2,d3) (0, 1, 1, 0) 1010
(1, 1, 1, 1)
(0, 1, 0, 1) -> d3 error -> (d0,d1,d2, 𝑑3) 1100
(0, 0, 0, 0)
(1, 0, 0, 0) -> p0 error -> (d0,d1,d2,d3) 1011
(0, 0, 1, 0) 0101
(0, 1, 0, 0) -> p1 error -> (d0,d1,d2,d3)
(0, 0, 1, 0) -> p2 error -> (d0,d1,d2,d3)
(0, 0, 0, 1) -> p3 error -> (d0,d1,d2,d3)
Others -> no idea -> (d0,d1,d2,d3)

20 Raymundo TANG TANG, Dept. of Electronic and Computer Eng., HKUST

Binary Symmetric Channel
• P(Y=0|X=0) = 1-ε (ε = error probability)
• P(Y=1|X=1) = 1-ε
1−ε
1 1
• P(Y=0|X=1) = ε ε

• P(Y=1|X=0) = ε ε
0 0
1−ε
• 0≤ε≤½

• P(Y=0) = P(Y=0|X=0) P(X=0) + P(Y=0|X=1) P(X=1)

= (1-ε) P(X=0) + ε P(X=1)
• P(Y=1) = P(Y=1|X=0) P(X=0) + P(Y=1|X=1) P(X=1)
= ε P(X=0) + (1-ε) P(X=1)
21
Symbol error

• Symbol error (1→0 or 0→1)

• Bit error rate (ε)
• Probability of r-bit error in an n-bit codeword

𝑛!
𝑝 𝑟 = 𝜀 (1 − 𝜀)
𝑛 − 𝑟 ! 𝑟!
Note: This formula will be given during the final exam.
𝑛 !
Binomial coefficient: =
𝑟 ( )! !

22
Symbol error
• …Things to remember:

𝑛! = n x (n-1) x (n-2)….x 1
5! = 5 x 4 x 3 x 2 x 1
1! = 0! = 1
𝑛 𝑛!
=
𝑟 (𝑛 − 𝑟)! 𝑟!

5 ! ! ! 5 ! !
= = = = 10 = = =5
3 ( )! ! ! ! ! ! 4 ! ! !
5 !
= =1
5 ! !
23
Repetition Code Example

• Assume Binary Symmetric Channel, ε = 0.1

• Use a (5,1) repetition block code
• Find the block error rate (probability of symbol error)

24
Answer

• A (5,1) repetition block code can correct up to 2-bit error.

• Therefore, we need to find:
• 𝑝 𝑒 = 𝑝 3 + 𝑝 4 + 𝑝(5)
5
•𝑝 3 = 0.1 (1 − 0.1) =0.0081
3
5
•𝑝 4 = 0.1 (1 − 0.1) =0.00045
4
5
•𝑝 5 = 0.1 (1 − 0.1) =0.00001
5
• 𝑝 𝑒 = 0.00856

25
Decoding using 2D parity code – 4 ε = 0.1, BSC
Noisy channel Even 2D parity code 10111001 01011110
Block (8b) (no error) (p2 error)
(8,4)
(received)
10001100 d0 d1 p0 1->0 0->1 1 0->1 1 1->0
11001100 1->0 1->0 0 0 1 1
10111001 d2 d3 p1
01011110…
p2 p3 0 1 1 0
codewords
Aim: detect 1-bit error
Our complete and deterministic decoding scheme:
Block (8b) Block (8b) Probability for this
(received) (sent) specific case only:
10111001 (0, 0, 0, 0) -> no error 10111001 0.98=0.43046721 (no error)
Another possibility:
4-bit error (d0-d3) 01001001 0.14*0.94=0.00006561
(for the system: no error) (for this specific 4 bit error)
01011110 (0, 0, 1, 0) -> p2 error 01011100 0.1*0.97=0.04782969
Another possibility:
11010110 0.12*0.96=0.00531441
2-bit error (d0, p0)
Features: (for this specific 2 bit error)
(for the system: no error)
• Not always decodes correctly
• Errors with more bits happen less frequently
4/10/2025
26 Raymundo TANG TANG, Dept. of Electronic and Computer Eng., HKUST
 Decoding using 2D parity code – 4 ε = 0.1, BSC
Noisy channel Even 2D parity code 10111001 01011110
Block (8b) (no error) (p2 error)
(8,4)
(received)
10001100 d0 d1 p0 1->0 0->1 1 0->1 1 1->0
11001100 1->0 1->0 0 0 1 1
10111001 d2 d3 p1
01011110…
p2 p3 0 1 1 0
codewords
Aim: detect 1-bit error
Our complete and deterministic decoding scheme:
Block (8b) Block (8b) Probability for this
(received) (sent) specific case only:
10111001 (0, 0, 0, 0) -> no error 10111001 0.98=0.43046721 (no error)
Another possibility:
4-bit error (d0-d3) 01001001 0.14*0.94=0.00006561
(for the system: no error) (for this specific 4 bit error)
01011110 (0, 0, 1, 0) -> p2 error 01011100 0.1*0.97=0.04782969
Another possibility:
11010110 0.12*0.96=0.00531441
2-bit error (d0, p0)
(for this specific 2 bit error)
(for the system: no error)
Note: This formula is assuming that there are “no restrictions” in the
block code sent, i.e. the parity check bits added to the original message
to form
P.27 a block can have any value, which is not true forRaymundo
2D parity code
TANG TANG, Dept. of Electronic and Computer Eng., HKUST
Decoding for 2D parity code - 4 ε = 0.1, BSC
Block (8b) (sent) Probability for this specific case:
Block (8b)
(received) i) no error 10111001 0.98=0.43046721
10111001 ii) 4-bit error (d0-d3) 01001001 0.14*0.94=0.00006561
Original Block Code Block Code Error bits Probability
message sent received
0000 00000000 10111001 5 e5(1-e)3 In reality there are only 16 possible block codes sent
0001 00010101 10111001 4 e4(1-e)4 (see table)
0010 00100110 10111001 6 e6(1-e)2
i) P (no error) = (1−)8
0011 00110011 10111001 3 e3(1-e)5
(1−)8+4×3(1−)5 +5×(1−)4
0100 01001001 10111001 4 e4(1-e)4
+4×(1−)3+2×(1−)2
0101 01011100 10111001 5 e5(1-e)3
0110 01101111 10111001 5 e5(1-e)3 .
0111 01111010 10111001 4 e4(1-e)4
P= = 0.9937
.
1000 10001010 10111001 4 e4(1-e)4
1001 10011111 10111001 3 e3(1-e)5
ii) P (original message is 0100) = P (this specific 4 bit error)
1010 10101100 10111001 3 e3(1-e)5 (1−)4
=
1011 10111001 10111001 0 (1-e)8 (1−)8+4×3(1−)5 +5×(1−)4
1100 11000011 10111001 5 e5(1-e)3 +4×(1−)3+2×(1−)2
1101 11010110 10111001 6 e6(1-e)2
.
1110 11100101 10111001 4 e4(1-e)4 P= = 0.0001515
.
1111 11110000 10111001 3 e3(1-e)5

4/10/2025
28 Raymundo TANG TANG, Dept. of Electronic and Computer Eng., HKUST
 Block error rate and bit error rate
1−ε Even 2D parity code (8,4)
1 1
ε d0 d1 p0
ε d2 d3 p1
0 0
1−ε p2 p3
Channel Channel
encoding
Noisy
decoding
Block (8b) channel Block (8b) Decoded message bits
Bits (sent) (sent) (received) (received)
1010 10101100 10001100 (1 bit error) 1010
1010 10101100 11001100 (2 bits error) 1100
1011 10111001 10111001 (no error) 1011
0101 01011100 01011110 (1 bit error) 0101
Codeword=message codewords codewords
block(4b)+parity block(4b)
number of erroneous
message blocks For the above 16 message bits, we have 4
Block error rate = message blocks:
number of message blocks
Block error rate = 1/4 = 0.25
number of erroneous message bits
Bit error rate = number of message bits Bit error rate = 2/16 = 0.125
Accurate estimations of block error rate and bit error rate require simulation using lots of
random inputs and channel errors according to the channel properties.
29 Raymundo TANG TANG, Dept. of Electronic and Computer Eng., HKUST
Shannon’s Channel Capacity
 Assume a Binary Symmetric Channel (BSC) with a bit error rate ɛ.
Shannon defines the entropy and capacity of the channel as follow:
Entropy = H(channel) = ɛ x log2 1/ ɛ + (1- ɛ) x log2 1/(1- ɛ)
Capacity = 1 – H(channel)
C = 1 + e log2 e + (1-e) log2 (1-e)
Note: This formula will be given during the final exam.

 Channel capacity is the tightest upper bound on

the amount of information that can be reliably
transmitted over a communication channel.
 If code rate R < Capacity, theoretically it is

possible to correct all error bits with certainty

when there is a large number of bit to transmit. ε
30 Raymundo TANG TANG, Dept. of Electronic and Computer Eng., HKUST
Shannon’s Channel Capacity
Given a BSC channel that transmits at 1000 bits per second at a bit
error rate = 0.4, what is the maximum number of information bits per
second that we can transmit through the channel if we want to be
able to transmit the information bits reliably?

A. 512
B. 28
C. 111
D. 972
E. 9

Answer: B

31 Raymundo TANG TANG, Dept. of Electronic and Computer Eng., HKUST

Shannon’s Channel Capacity
Answer:
• H(channel) = 0.4 log2 + 0.6 log2 = 0.9710 (ε = 0.4 )
. .

• C = 1 – H(channel) = 0.029

• If the BSB channel transmits at 1000 bits/sec:

0.029 x 1000 = 29 bits/sec
R< C: Answer B

• Reflection: How to interpret C=0.029?

“For every bit transmitted through the channel, the max. number of
information bits we can transmit reliably is C=0.029 bits, and there
will be at least 0.971 protection bits (reliably means that we can
decode & correct all the errors with almost certainty)
32 Raymundo TANG TANG, Dept. of Electronic and Computer Eng., HKUST