MATH3411 INFORMATION, CODES & CIPHERS Test 1 Session 2 2014 SOLUTIONS
Multiple choice: c, b, a, c, b, c, b, d, e, a
Columns 2 and 3 are parallel (in fact, they are identical).
There must be exactly two 0s and two 1s – in other words, 2 errors.
Copyright By PowCoder代写 加微信 powcoder
Commacodehasc1 =0,c2 =10,andc4 =1110.
get 1 + 1 + 1 + 1 = 29 so we need 1 ≤ 3 , or in other words, l ≥ 4.
The Kraft-McMillan number must be at most 1 for UD codes. We
2 22 23 25 32 2l 32 9. (e):
10. (a): One dummy symbol is needed, so there is only one combination
step: combine the dummy, s2s2 and s2s1 with combination probability
0+1 +4 =1,sotheaveragelengthofthecodeis6,andtheper 25 25 5 5
original source symbol average length is 35 .
The Kraft-McMillan number is
K = 1 + 6 + 1 = 28 > 1
so there is no UD-code.
3 32 33 27
(b) We find that s1s1 → 0, s1s2 → 11, s2s1 → 100, s2s2 → 101. The average length per original source symbol is
114 24 87
2 49+49+1 =98byKnuth’sLemma.
Multiple Choice: a, c, a, c, d, d, e, c, c, e
4. (c): Columns 1 and 6 are parallel (in fact, they are identical).
5. (d): The Sphere Packing Bound is here |C|(1+n) ≤ 2n where |C| = 2k andn=m+k=3+k,sok≤23 −4=4.
7. (e): Thecommacodehasc1 =0,c2 =10,c3 =110,andc4 =1110.
8. (c): The Kraft-McMillan number is 1 for minimal codeword length binaryUDcodes,so 2 + 2 + 2 + 1 =1;inotherwords,l=3.
22 23 24 2l
9. (c): Last two codewords differ in their last bit only.
10. (e): By Knuth’s Lemma, the average length is 1 + 25 = 75 .
For instance:
C = {0, 10, 11, 12, 20, 210, 211, 2120}
(b) We find that s1s1 → 00, s1s2 → 01, s2s1 → 10, s2s2 → 11 (the
two middle codewords could be swapped). The average length per
original source symbol is 1 (1 + 15 + 10 ) = 2 = 1. 2 25 25 2
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com