MATH3411 INFORMATION, CODES & CIPHERS Test 1 2017 S2 SOLUTIONS
Multiple choice: b, b, c, c, a, e, e, c, c, b
2. (b): Calculate the Hamming distance between the 4 = 6 pairs of codewords:
2,2,3,3,3,4. The smallest of these is 2.
Copyright By PowCoder代写 加微信 powcoder
3. (c): There are 22 = 4 codewords, there being 2 information bits.
4. (c): The codeword is 10101; it has weight 3.
5. (a): The two rows of this matrix form a basis for C (they are codewords, linearly independent, and there are k = 2 of them).
6. (e): We can only correct up to t = 3 errors.
7. (d): Ruleoutcases: (a)100=c1c4 =c3;(b)11=c2 =c4c4;(c)10011=c1c4 =
c3c2; (d) 111111 = c2c2c2 = c4c4.
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 l = 1, 2, 3, . . . gives us that l = 3 is the minimum length that satisfies this.
You can also draw a decision tree.
9. (c): The codewords are 0, 100, 101, 102, 110; that last one is c5.
10. (b): s2s3s3s1s1. Start with HuffE and recognise the codeword c2 = 00; therefore, next use HuffE and so on.
3 32 33 27
(b) Using [and drawing the steps of] the Huffman algorithm, 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: c, d, e, d, d, d, e, b, e, e
The error lies in the 3rd row and 5th column of the block
10101010 10010110 11001101 00111010 11000011
1, 2, or 3 errors, and 12 = 220. 3
33 = 27 linear combinations of the rows and thus that many codewords. 1st row + twice 2nd row + 3rd row = 1112001
asserts that |C| n ≤ 2n, which here implies that 2k(1 + 7) ≤ 27, or in other
Since d = 2t + 2, we see that t = 1. The (binary) Sphere-Packing Theorem i=0 i
words, 2k+3 ≤ 27. The largest value of k which satisfies this inequality is k = 4, and indeed, the code with basis {1000111, 0100111, 0010110, 0001101} is such a code.
7. (e): Trial and error. None of the four words are suitable: 101 = c1c3 = c2c1.
8. (b): 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 = 3 is the minimum length that
satisfies this. You could also draw a decision tree.
10. (e): Ternary, one dummy symbol, divide by 2.
11. (a)p=Mp
(b) Draw Huffman algorithm decision tree. L = 75
(c) 01101100
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com