MATH3411 INFORMATION, CODES & CIPHERS Test 2 2018 S2 SOLUTIONS
Multiple choice: b, c, a, e, c, c, d, b, b, a
1. (b): This is the only codeword which has 1221 in the information positions.
2. (c): Ifthesentcodewordisx,theny=x+aei forsomea∈Z3 andi∈{1,…,7}. Since S(y) = HyT = 022T = 2HeT5 , twice the 5th column of H, and that S(y) = aHeTi , weseethata=2andi=5,sox=y−2e5 =0021010,som=1010.
Copyright By PowCoder代写 加微信 powcoder
3. (a): 1001 and 0121 are the only codewords and, of these, only 1001 can encode 10.
4. (e): By trial and error, we see that none of the four words for c4 are suitable:
(a) c4c4 = c2 (b) c4 = c1c2 (c) c4 = c1c1c1 (d) c4c2c4 = c1c3c3c1
5. (c): The Kraft-McMillan number K = 1 must be at most 1 for UD codes.
Testing values of l = 1, 2, 3, . . . gives us that l = 4 is the minimum length that satisfies this.
You can also draw a decision tree. 6. (c): Encode the message ba• :
subinterval start
0 0.4 0.4 0.4+0.7×0.12=0.484
1 0.3 0.4×0.3 = 0.12 0.3×0.12=0.036
so the message encodes as a number in the interval [0.484, 0.52).
7.(d):1.b 2.a 3.aa 4.aab 5.aaa
8. (b): Use one dummy symbol (and Knuth’s Theorem to save time). L(n)
9. (b): lim 3 =H3(S)=−0.4log30.4−0.3log30.3−0.3log30.3−0.3log30.3≈1.16. n→∞ n
So, the message m = s1s4s2 is encoded as 00101001.
pi p1 li code i
0.42.52 00 0.33.32 01 0.2 5 3 100 0.1 10 4 1010
Let us now calculate the Huffman codes HuffE, Huff(1), Huff(2), Huff(3):
Source pi HuffE Source pi Huff(1) Source pi Huff(2) Source pi Huff(3)
s1 6 00 s1 0.7 0 s1 0.2 10 s1 0.1 01 17
s2 7 1 s2 0.2 10 s2 0.6 0 s2 0.4 00 17
s3 4 01 s3 0.1 11 s3 0.2 11 s3 0.5 1 17
(b) The average lengths of these codes
LE = 27 ≈1.59 L(1) =1.3 L(2) =1.4 L(3) =1.5 17
The Markov Huffman code has average length
LM = 6L(1)+ 7L(2)+ 4L(3) = 61.3+ 71.4+ 41.5≈1.39 17 17 17 17 17 17
c) We encode s1s3s2s1:
so this is encoded as
s1 HuffE 00 s3 Huff(1) 11 s2 Huff(3) 00 s1 Huff(2) 10
00110010 .
code to use encoded symbol
Multiple choice: a, d, d, d, b, b, e, a, a, c
1. (a): This is the only codeword which has 1221 in the information positions.
2. (d): Ifthesentcodewordisx,theny=x+aei forsomea∈Z3 andi∈{1,…,7}. SinceS(y)=HyT =002T =HeT3,the3rdcolumnofH,andS(y)=aHeTi , weseethata=1andi=3,sox=y−e3 =1101111,som=1101.
3. (d): 1201 is the only codeword here that can encode 10.
4. (d): This choice of c4 gives an I-code and thus a UD-code.
5. (b): The Kraft-McMillan number K = 1 must be at most 1 for UD codes. 2li
Testing values of l = 1, 2, 3, . . . gives us that l = 3 is the minimum length that satisfies this. You can also draw a decision tree.
6. (b): Encode the message ab• :
subinterval start
begin 0 a 0 b 0+0.4∗0.4 = 0.16 • 0.16+0.8×0.16 = 0.288
1 0.4 0.4×0.4 = 0.16 0.2×0.16 = 0.032
so the message encodes as a number in the interval [0.288, 0.32).
7.(e):1.b 2.ba 3.baa 4.baab 5.baaa
8. (a): Use one dummy symbol (and Knuth’s Theorem to save time).
L(n) lim 4
= H4(S) = −0.4log4 0.4−0.2log4 0.2−0.2log4 0.2−0.1log4 0.1−0.1log4 0.1 ≈ 1.06. pi p1 li code
0.42.52 00 0.2 5 3 010 0.2 5 3 011 0.1 10 4 1000 0.1 10 4 1001
So, the message m = s1s4s2 is encoded as 001000010.
Let us now calculate the Huffman codes HuffE, Huff(1), Huff(2), Huff(3):
Source pi HuffE Source pi Huff(1) Source pi Huff(2) Source pi Huff(3)
10 00 s1 1 10 s1 1 1 s1 1 00 27 4 2 4
13 1 s2 2 0 s2 1 00 s2 1 1 27 3 3 2
4 01 s3 1 11 s3 1 01 s3 1 01 27 12 6 4
(b) The average lengths of these codes are
L(1) = 43 L(2) =1.5 L(3) =1.5 The Markov Huffman code has average length
27 c) We encode s1s3s2s1:
so this is encoded as
27 27 273 27 27 162
LM =10L(1)+13L(2)+ 4L(3)=104+131.5+ 41.5=233≈1.44
s1 s3 s2 s1
code to use encoded symbol
Huff(1) 11 Huff(3) 1 Huff(2) 1
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com