Question 1. (a) Find generator matrix G. From the given information we can deduce n — 7 and k — 4. So, we have a (7,3) code, so we are looking for matrix of size (3;c7). We also know that g(x) = 1 + x1 4- x3 + r4. From this, we can construct a generator matrix G using steps described in the tutorial video. 10 1110 0' 0 10 1110 0 0 10 111 (b) Find parity check matrix H, To find the parity-check matrix, I need to divide x1 — 1 by g(x). When using only binary alphabet I can calculate (x7 + 1) : {x4 + x3 + x2 + 1). This gives me h(x). which is h(x) = x3+x2 + l. From this we can construct a parity-check matrix H, again using steps from tutorial. "1 1 0 1 0 0 0" 0 110 10 0 "0011010 0 0 0 1 1 0 1 _ (c) Using polynomials encode the message 101. To encode the message m — 101 I calculate the respresentation of m in polynomial, giving me m(x) — 1 + x2. Then 1 multiply m(x) * g{x) to get the encoded polynomial codeword c(x) and then turn it into binary representation c. c{x) = mix} * g(x) = x6 4 x5 4 2a-4 4- a:3 + 2i2 + 1 c(x) = xG 4- jts + a:3 + 1 c= 1001011. Question 2. (a) First we have to factorize xG + 1 as the length is 6 and we are in Fa. zG+l = (x + lf{x2 + x + l)2 All binary cyclic codes are in form: (x + l)ai(z2 + z + l)^,ai E {0,1,2}, 02 E {0,1,2} We have 33 possibilities, therefore there are 9 binary cyclic codes of length 6. (b) First we have to factorize xQ + 4 as the length is 6 and we are in F2. 26 + 4 = (x+ l)(x + 4}(x2 + Ax + l)(x2 + x + l) All quinary cyclic codes are in form: (x + ]_)ai(x + 4)a*{x2 + 4x + l)a3(x2 + x + lJ«,Vi€ {l,2,3,4},Oi e {0,1} We have 21 possibilities, therefore there are 16 quinary cyclic codes of length 6. Question 3. The code is not equivalent to a cyclic code. Proof. A binary cyclic code on most be generated by a factor of xs — 1. Is - 1 = (x + l)s =► there are 8 factors of Xs - 1 (mod 2): (x + l}1 for i e {0, -.., 7}. The degree of the i-th factor is i, therefore the only factor which generates an [8,4]-code is (x+ l}d. fc = n - deg g(x) 4 = 8 — deg g(x) deg{g(x)) = 4 The generator matrix of {(x + is: 1 0 0 0 1 0 0 0" „,_01000 100 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 As G' generates a linear code, the Hamming distance of the generated code is the minimal of G' row weights (number of Is). Hamming distance of code generated by G is also the minimal weight of a raw in G: Bam{Cc") = 2 Hnm(CG) = 4 The code generated by G cannot be equivalent to the only possible [8, 4] cyclic code generated by ff, as the Hamming distance is preserved between equivalent codes. Thus, the [8, 4] extended binary Hamming code is not equivalent to a cyclic code. Question 4. We can write every code polynomial generated by g(x) as w(x) = u(x)g(x). Since x+ 1 is a factor of g(x) and g(x),u(x) are not factors of each other, x + 1 is also a factor of every code polynomial w{x). Hence w(l) = 0. It also holds that = 0 -s=^ wa + wi + ... + ur„_i = 0. And thus has even weight. That means that if 1 + x\g(x); then every w generated by g{x) has even weight. Question 5. n For the polynomial g(x) = Yl x^ tD De a generating polynomial of a q-ary cyclic code of length i=0 2n + 2 for any integer n and prime q. the g{x) needs to divide the polynomial x2n+^ — 1 in ¥q. Therefore we have to find a polynomial k(x) such that x2n+^ — 1 = g(x) ■ h(x) (mod q) for any integer n and prime q. The polynomial fi{x) we are looking for is h(x) = x^ — 1 (mod q). Let us write the polynomial g{x) in the following form: g(x) = i2i = 1 + r2 + i4 + ... + x^~2 + x2n (mod q) Then obviously for any integer n and prime q the following product holds: x2n+ X2n~2 + ...+ XA + X2 + 1 x2-l - x*1- x*1-2- ... - xA- X2 - 1 + r3n+ j,an-2+ _ _ _ + XA+ ^2 Therefore g{x) \ x2n+2 — 1 for any integer n and prime n + b\a + &12 * c= 100101001010100000000101 (b) * s = w - HT = (110100110100010111100000) - [I\B]T = 110100010001 * W(S) ^ 3 * w(s + bi) ^ 2, Vie (1,....12) * s ■ G = 010101000000 * u?(010101000000) = 3 < 3 * e = [000000000000.010101000000] =000000000000010101000000 * c = w + e= 1101O01101O0OO0OI01O0O00, ci.. .c12 = &5 + h * c = 110100110100000010100000