Question 1. (a) 1000 € Ci, but 1000 + 1000 = 0000 and 0000 £ Ci. Therefore Ci is not linear code. (b) Let's consider w\ = xix2X3Xax$,W2 = yiyiyzyiyz £ Ci.w = w\ +W2- Symbol at position i in codeword w can be written as x( + j/s and number of ones in to can be written as 5Zi=i xt + t/j. There can happen two cases when adding Xi and jr: (a.) and are different values. Then there is only one symbol of one among them, which is odd. and result of addition is one, which is also odd. (b) Xi and t/j are same values. Then number of ones among them is even, and result is zero, which is also even. Because sum of number of ones in w\ and wi is even, the resulting number of ones in w is also even. Therefore w £ C2. Now, let's consider g £ Ci and fc £ 0,1. During k ■ g, two cases can happen: (a) fc is 1. Then k ■ g = g, which belongs in C%. (b) fc is 0. Then fc ■ g = 00000, which belongs in C2. This all means, that Vtoi,^ £ C2 : ii>i + w2 £ C2 and Vui £ C2, Vfc £ 0,1 : k ■ w £ C2. Therefore is linear code. (c) 021 £ C3, but 2 ■ 021 = 012 and 012 £ C3. Therefore C3 is not linear code. 1 Question 2. By the definition of hamming codes the parity cheek matrix H has to be of size r x 2r — 1 where columns are all non-zero distinct words from F£. (a) First we calculate parity matrix Hi from generator matrix G\. is d n íl 0 (1 1\ ľ i d i |~ 0 1 (1 1 = is i ' \o 0 1 1/ Hi = :i i 1 1)=[- A lh\A\ From there H\ has r = 1 rows. For code generated by generator matrix G\ to be equivalent with hamming code, matrix H\ has to have 2T — 1 columns, but 21 generated by G\ is not equivalent with hamming code. ■ 1 7^ 4 and therefore code (b) First we calculate parity matrix ffj from generator matrix G-2 Cl /l 0 0 1 1 0 1\ /l 0 0 1 1 0 1\ 0110010 0110010 1010011 ~ 0011110 \1 0 0 1 0 1 0/ \0 0 0 0 1 1 1/ (I 0 0 1 1 0 1\ 0 110 0 10 0 0 10 111 \o 0 0 1 1 1 0/ 1 IV054 2019 Zoltan Fridrich (445620) Homework 2 H2 has r = 3 rows and 23 /l 0 0 0 0 1 1\ 0 10 0 10 1 0 0 10 111 \0 0 0 1 1 1 0/ 0 11110 ()' 10 110 10 1 1 1 0 0 0 1 lh\A] l-AT\ln-k] 7 columns where each column contains non-zero distinct word. Therefore code generated by G-i is equivalent with hamming code. 2 Question 3. By definition, all Hamming codes have minimum distance 3. [n, k]-Hamming code is thus a (n = ^zr> M = -">'" + n(q-l)) 1 D (i 1 (1 -1 il 0 1 11 1 (1 0 1 11 1 (1 0 1 0 1 1 (i (1 1 H = [AT\h] G = [I2\A] G = "1 0 0 1 1 0 1 1 0 1 (b) Let C be a linear code and let weight of C, notation w(C), be the smallest of the weights of non-zero code words of C. Then h[C) = w(C). C = {00000,10011,01101,11110} h(C) = w(C) = 3 («0 coset leadeis (l(z)) syndromes (z) 00000 000 10000 101 01000 010 00100 100 00010 011 00001 110 11000 111 10100 001 v 10111 Step 1: Given y compute S(y) = yHT [10 111] 0 110 0 10 0 10 110 0 1 [1 0 0] Step 2: Locate z = S(y) in the syndrome column Z(100) = 00100 Step 3: Decode y as y — l(z) y - l(z) = 10111 - 00100 = 10011 4 Question 5. Binary code C is self-dual iS C = C±. G=[Ik\A] => H = [AT\(for binary code). (a) (exchanging second and third row) 10 0 10 0 0 0 10 10 0 1 0 0 0 1 10 0 10 0 0 1 0 0 0 1 0 0 10 10 10 0 10 0 0 0 10 10 0 1 0 0 0 1 Definition from lecture 2. slide 32: A parity check matrix H for an [n, fc]-code C is any generator matrix of C^. We can see that Gi = Hi and therefore, code generated by G\ is self-dual. (b) Matrix G2 generates a [5,2]-code. Let's assume it is self-dual. Then, according to the theorem in lecture 2, slide 32, it is a [5,3]-code. We have reached a contradiction, therefore the initial assumption was false and that means code generated by Gi is not self-dual. Question 6. To prove (C+D)1- = C±nD± it is necessary to prove (C+D)-1 C C±r\D± and C±r\D± C (C+D)1 I. (c-1-D)L c^nc1 Let x £ (C + D)1- and x-y = 0. for all y £ (C + D). Let c £ C and then for all c £ C, c = c + 0 £ (C + D), so x ■ c = 0, which means that x £ Let d £ D and then Vd £ D. d = 0 + d £ (C + £1), so x • d = 0. which means that x £ £>-*-. II. C±C\D± C (C + D)1 For all jf £ (C-1 n Dx) : y ■ c = 0 and ■ d = 0, which means that v • (c. + d) = 0, so v £ (C + D)1. 5 Question 7. Let the code be C an [n, k, d] linear code, then we know Bin, d) = qk. We want to get an [n— 1, k*, d] code, what we can achieve with code shortening. If we have a full 0 column (special case, this position is useless), we can shorten the code without loosing any base code words, and we get an [n — 1, k.d] code, and the equality clearly holds (this gives the most possible k). More generally (no all 0 column), we can transform the codes generator matrix to have only one lbit in its last column. With shortening we receive an [n — l.k — 1, > rf] code, which has qk~l code words. Substituting into the non-equivalence we get: Bq(n,d) < gBq(n - l.d) k ~- k—1 gk