MATH3411 2018S2 Exam
Solutions
Thomas Britz
QUESTION 1
1. i) a) True: 1 · 0 + 2 · 7 + 3 · 3 + 4 · 9 + 5 · 4 + 6 · 5 + 7 · 2 + 8 · 1 + 9 · 0 + 10 · 10 ≡ 0 (mod 11)
b) False: L = 1.9
c) True: H(S) = 1.75
d) False: s2s1s1• → [.4336, 0.448). Another approach is to decode 0.5 to s2s1•.
e) True: |C|/|Z152 | = 211/215 = 1/16. Or, notice that there are 4 check bits which must each be
correct.
ii) a) Here, C is the 5-repetition code, so we are talking about the probability of either one or two
errors: 5p1(1− p)4 + 10p2(1− p)3.
b) This is the probability of five errors: p5.
iii) a)
Source pi HuffE
s1
4
16 01
s2
7
16 1
s3
5
16 00
Source pi Huff(1)
s1
7
10 0
s2
1
5 10
s3
1
10 11
Source pi Huff(2)
s1
1
10 11
s2
3
5 0
s3
3
10 10
Source pi Huff(3)
s1
1
10 01
s2
2
5 00
s3
1
2 1
c) We encode s1s3s2s2s1:
symbol code to use encoded symbol
s1 HuffE 01
s3 Huff(1) 11
s2 Huff(3) 00
s2 Huff(2) 0
s1 Huff(2) 11
so this is encoded as 011100011 .
d) P (m2 = 0) =
3∑
i=1
P (m1 = si)P (m2 = 0|m1 = si) = 4
16
7
10
+
7
16
3
5
+ 0 =
7
16
= 0.4375
1
QUESTION 2
2. i) a) To find the radix 3 Huffman code, we must add 0 dummy elements since 5 ≡ 1 (mod 2):
Source Step 0 Step 1 Step 2
s1 p1 = 0.4 1 p345 = 0.4 0 p34512 = 1 ∅
s2 p2 = 0.2 2 p1 = 0.4 1
s3 p3 = 0.2 00 p2 = 0.2 2
s4 p4 = 0.1 01
s5 p5 = 0.1 02
In other words, the radix r = 3 Huffman code is 1, 2, 00, 01, 02 resp.
By Knuth’s theorem, the expected codeword length is L = 0.4 + 1 = 1.4.
b)
pi
1
pi
ℓi
0.4 2.5 2
0.2 5 3
0.2 5 3
0.1 10 4
0.1 10 4
The codeword lengths are thus 2,3,3,4,4 and the average codeword length is
LSF = 0.4× 2 + 0.2× 3 + 0.2× 3 + 0.1× 4 + 0.1× 4 = 2.8 .
c) lim
n→∞
L
(n)
SF (S)
n
= H3(S) = −0.4 log3 0.4− 2× 0.2 log3 0.2− 2× 0.1 log3 0.1 ≈ 1.339
a) n = 97× 151.
b) ϕ(n) = 96× 150 = 14400.
c) Use the Euclidean Algorithm:
14400 = 12343 + 2057
12343 = 6× 2057 + 1
so
1 = 12343− 6× 2057
= 12343− 6× (14400− 12343)
= 7× 12343− 6× 14400
≡ 7× 12343 (mod 14400)
Hence, d ≡ e−1 ≡ 12343−1 ≡ 7 (mod 14400).
d) We decipher:
cd ≡ 47297 ≡ 11683 (mod 14647)
so
c = 4729→ 11683 = 22× 232 + 1× 23 + 22→ (22, 1, 22)→ YAY
iii) a) H(A) = H(x) and H(B|A) = P (a1)H(B|a1)+P (a2)H(B|a2) = xH( 15 )+(1−x)H( 15 ) = H( 15 )
b) P (b1) = P (b1|a1)P (a1) + P (b1|a2)P (a2) = 45 x+ 15 (1− x) = 15 + 35 x, so H(B) = H
(
1
5 +
3
5 x
)
.
Also, I(A,B) = H(B)−H(B|A) = H( 15 + 35 x)−H( 15 )
c) To find C(A,B), solve ddxI(A,B) = 0; that is,
3
5
log2
( 1
1
5 +
3
5 x
− 1
)
= 0 .
The solution is x = 12 , so
C(A,B) = max
x
I(A,B) = H
(1
5
+
3
5
1
2
)−H(1
5
) = 1−H(1
5
)(≈ 0.278) .
2
QUESTION 3
3. i) We can test the possibilities for c4:
0, 1, 00, 11, 000, 010, 100, 011, 101, 110, 111
Of these, 0, 1, 011, 100, 101 are ruled out since C is uniquely decodable. The rest, except 11, are
ruled out since they do not allow C to encode the given message. This leaves the (valid) solution
c4 = 11.
ii) See Lecture 29.
iii) a) |K| = 26!9!
b) n0 =
⌈ log2 |K|
3.2
⌉
≈ 33.4
c) Yes: 50 is somewhat bigger than 33.4.
iv) a) If there are at most two errors, then we can rotate the cube in at some way so that each layer
has at most one error which can then be found by the row and column parity check bit errors
in that layer.
b) Assuming the pure-error detection strategy: 7
In particular, we cannot detect 8 errors if they form the corners of a box;
conversely, it is not hard to see that up to 7 errors will always give at least one check bit error.
(Assuming other strategies lead to other valid answers – as long as they come with valid
explanations.)