MATH3411 INFORMATION, CODES & CIPHERS Test 1 Session 2 2013 SOLUTIONS
Multiple choice: b, b, a, b, d, e, e, c, b, a.
8. (c): The Kraft-McMillan number must be ≤ 1 for UD codes. We get 1 +2 + 2 =7 soweneedl≥3.
9. (b): Last two codewords differ in their last bit only.
Copyright By PowCoder代写 加微信 powcoder
10. (a): One dummy symbol is needed, so there is only one combination
step: combine the dummy, s2s2 and s2s1 with combination probability
0+4 +6 =10 =2,sotheaveragelengthofthecodeis7,andthe 25 25 25 5 5
per original source symbol average length is 7 . 10
c5 = 1111.
The Kraft-McMillan number is
K=2×1+2×1+3× 1 + 1 >1 3 9 2781
The syndrome is a column of H.
Sphere packing bound is 37|C| ≤ 256, so |C| ≤ ⌊256⌋ = 6.
Wemusthavea+b≤d−1=6witha≤b. Commacodehasc1 =0,c2 =10,c3 =110,c4 =1110and
so there is no UD-code.
(b) We find s1s1 → 1, s1s2 → 01, s2s1 → 000, s2s2 → 001. Average
1 24 39 length per original source symbol is 2 64 + 64 + 1
= 128 from
9 127 thecodingprocess,or 2 64 +2× 64 +3× 64 +3× 64 = 128
from the definition.
1 25 15 15
Multiple Choice: b, e, a, c, d, d, a, a, e, c
1. (b): Columns 2 and 7 show errors, and a burst starting in the 7th column (in 10101011) and going to the 2nd in the next row (11001011) could produce this.
4. (c): The syndrome is not a column but is the sum of two columns.
5. (d): Sphere packing bound is 2k(1+k+3) ≤ 2k+3, so k+4 ≤ 23; therefore, k ≤ 4.
6. (d): Wemusthavea+b≤d−1=11witha≤b.
7.(a): Commacodehasc1 =0,c2 =10,c3 =110,c4 =1110and
c5 = 1111.
8. (a): The Kraft-McMillan number must be ≤ 1 for UD codes. We get
2×1 +1 +2× 1 =3 soweneedl≥2. 48 164
9. (e): Last two codewords differ in their last bit only.
10. (c): We need to introduce one dummy symbol. There is one combining
phase of the coding: combine the dummy, s6, s5 and s4 with a com-
bination probability of 0+ 1 + 1 + 2 = 4 , so the average length is
For instance:
17 17 17 17
C = {0, 10, 11, 12, 20, 2100, 2101, 2102}
(b) We find s1s1 → 1, s1s2 → 01, s2s1 → 000, s2s2 → 001 (mid- dle two could be swapped). Average length per original source
130 51 181
symbol is 2 100 + 100 + 1 = 200 from the coding process, or
1 49 21 21 9 181
2 100 +2× 100 +3× 100 +3× 100 = 200 from the defini-
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com