MATH3411 INFORMATION, CODES & CIPHERS Test 1 2016 S2 SOLUTIONS
Multiple Choice: d, a, e, c, d, b, e, b, e, c
1. (d): One or two errors.
2. (a): Test the words with x1 = 1, x2 = 0 to see whether they are codewords.
Copyright By PowCoder代写 加微信 powcoder
3. (e): There are 34 = 81 codewords: the 81 linear combinations of the rows of G.
4. (c): There is just one codeword starting with 1021, namely the sum of rows 1, 3 (twice) and 4 of G.
5. (d): By the Sphere-Packing Theorem with t = 1, 2k ×(1+7) ≤ 27, so k ≤ 4, and indeed, the binary Hamming (7, 4) code has these parametres.
7. (e): None since the message 11 cannot be decoded unambiguously.
8. (b): The Kraft-McMillan number K = 1 must be at most 1 for UD codes. rli
Testing values of r = 2, 3, . . . gives us that r = 3 is the minimum radix that satisfies this. (You could also draw a decision tree.)
9. (e): Draw a decision tree in the standard way.
10. (c): One dummy symbol is needed.
11. (a) The Kraft-McMillan number is
K = 1 + 1 + 1 + 3 = 17 > 1 2 22 23 24 16
so there is no UD-code.
(b) We find that s1s1 → 0, s1s2 → 11, s2s1 → 100, s2s2 → 101. The average length per original source symbol is
15 9 39
2 25+25+1 =50byKnuth’sLemma.
Multiple choice: b, d/e, c, a, b, b, e, c, b, c
2. (d/e): None of the three words containing 10 (in correct order) are codewords. However, you could argue that we could be allowed to specify a different order for the message digits, in which case, (d) is valid.
3. (c): There are 24 = 16 codewords: the 16 linear combinations of the rows of G.
4. (a): There is just one codeword starting with 1011, namely the sum of the first and
last rows G.
5. (b): By the Sphere-Packing Theorem with t = 2, 2k ×(1+8+36) ≤ 28, so k ≤ 2,
and indeed, the code with basis {11111000, 00000111} has these parametres.
8. (c): The Kraft-McMillan number K = 1 must be at most 1 for UD codes. Testing
The Kraft-McMillan number is
K = 2 + 3 + 1 = 28 > 1
so there is no UD-code.
values of r = 2,3,… gives us that r = 4 is the minimum radix that satisfies this.
(You could also draw a decision tree.)
9. (b): The codewords are 00, 01, 100, 101, 1100, 1101.
10. (c): One dummy symbol is needed.
(b) We find that s1s1 → 0, s1s2 → 11, s2s1 → 100, s2s2 → 101. The average length per original source symbol is
16 11 53
2 36+36+1 =72byKnuth’sLemma.
3 32 33 27
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com