Exercise 1
(a)
Ci = {00000,11100, OHIO, 00111,10011,11001} No, it's not a cyclic code, because it's not a linear code. 11100 + OHIO = 10110 ^ Ci
(b) C2 = C U (1... 1 + C), where C is binary cyclic code and 1... 1 is all 1 codeword,
Yes. Ikt;liisc il      lineal rule:
for any ci, C2 € C and c\, c!| € (1... 1 + £7), where c'i = Ci + 1... 1 and Cg = C2 + 1... 1
• + 4 = (Cl + 1... 1) + {a + 1... 1) = Ci +   + 2 • 1... 1 = d + a and {Ci + a) € C
• Cj + C2 = (ci + 1... 1) + C2 = (ci + C2) + 1... 1 and (ci + C2) € C and therefore (ci +c2 + 1...1) € (C + 1...1)
• ci + c2 € C
unci because operation +1...1 just. Hips all bits independently on their po.sit.iou, Following holds: <r(c) + 1... 1 = <?{c + 1... 1)
and therefore if c, <r(c) S C then (c + 1... 1), <?{c 4- 1... 1) € (C 4- 1... 1) Exercise 2
Let er denote a circular right shift operation. Find all binary words w
(a) of length n such that a(w) = w\
for W = Wl . . . MJfi, WnWl . . . WJn-l = «J1 «J2 ■ ■ ■ U»n
therefore lUi = Wi-i ,„,„1 „ and that holds only for 0" and 1"
(b) of length (i such that (T2(w) — u>\
for III = WJl . . . tUn, Wn-lWnWl . . . tilTt-2 = . ..11%
therefore Wi = Wi-2 modn and that holds only for 000000,111111,010101,101010
(c) of length 6 such that cr*{itf) = w. for w = w\... 1%, tUj = ii)j-3 modn must hold and that holds only for 000000, 001001,010010,011011,100100,101101,110110,111111
Exercise 3
1. (a) This is a straightforward use of the definition from the slides. Codes from Rj have length and since deg{l + x2 + x3) = 3, the dimension of the code is n — '& = 4. We need to write four cyclic shifts of 1011000 as rows of the matrix:
/l 0  1   1   0  0 0\
0 10   110 0
' =    0 0  10 110
\(i 0 0   1   0   1 1;
(b) According to slides x7 — 1 = (1 + x2 + x3) - h(x) and the dual code of C is generated by reciprocal h(x) of h{x). We thus need to find h(x) first. This is done by polynomial division. We get that h(x) — 1 + x2 + x3 + x4 and thus h(x) — 1 + x + x2 + x4. Since dual of C has dimension 3, three cyclic shifts of 1110100 are rows of H. Thus:
(1 1 1 0 1 0 0\ 0 1110 10] 0  0   1110 1/
(c) In order to encode with the use of polynomials we need to make an identity between the message m = 1010 and a polynomial message m (x) = 1 + x2. Now
c{x) — m(x)g(x)   mod X — 1 = (l+x2)(l + x2 + i3) = 1 + x2 + xA + x2 + x4 + x5 = 1 + X* + x4 + x5.
Exercise 4
3.4   (a) How Niiiny binary cyclic codes of lengl h !> Fire Iheic?
Solution: We sin- in >Y I'iisi of fill we have lo facloriw z° — 1 = ;r' 4 I into a irreducible polynomials over F^.
ifl + 1 = (a: + l)(a^ - x + l)(z6 - a:3 + 1) All binary cyclic codes are in form:
(i + l)0,(i2 - i + 1)oj(i6 - i3 + l)01;Vi € {1,2,3},« € {0,1} We have 2'' possibilit ies, | liereforethere are 8 binary cyclic codes of length 9,
□
(l>) How iiiiiity ternary cyclic codes of length 9 are there?
ShIilI ii hi:  Wc .in' in  ■      In si ill .ill ivi' Iliivi- In l.n'11 n i/i- .1 "      ]      .1 " I '2 ml .1 a ......Lur il 1 lr | n ilv 11.....nK
over F;i,
a;9 + 2 = (a; + 2)°
All binary cyclic codes are in form:
(x + 2)"\a) <= {0,9}
We haw 10 ]k)k.sil)iliiic.s, therefore (here are 10 ternary cyclic codes of length 9, □
{<■) How many ternary cyclic codes of length 9 have dimension 77
Solution: We have to faetoriae ,r' - I over Fn, As above we have ,r' + 2 = (,r4- 2)''. We have [9, 7]-code, therefore we have to iind fin-tors of decree:
dtg{f{x)) = n-fc = 9-7=2.
Therefore we have only 1 code of degree 2 with generator polynomial (x + 2)2. □
Exercise 5
Let Ci and C2 be cyclic codes with generator polynomials gi(x) and f)2{£)- Then Ci C C2 iff ^(a;) divides gi(x)
Since we know from slides that C is generated by hi'x), we obtain the proof by setting C\ — C and C2 — C1- in the above theorem. The nice proof is as follows. Essentially we want to prove the following:
(ffl) Q {92) 02I01
If #2|#it there exists /1, such that pi = /i^2- Since by definition O2 — {92) = {/(^Js^f^) mod      — £ ^u}, it in particular
contains all elements in {hg2) = {f(x}h(x)g2{x) mod a:" — l\f{x) € i?TJ} = C\. Since {#1} C {#2)> for each /(a;) 6      there exists
such that fgi = /?,#2-   111 particular this holds for f(x) — 1. meaning there exists h(x) such that pi = hg2> in other words ^Ifli-
Proof. C is self-orlhogonal if and only if I he reciprocal polynomial h(x) divides g{x).
we know that C C C' y(x) is divisible by g'{x)
and we know that generator polynomial of C1" is h(x)
i [in r[in f ht know i    (' ■ c   < •■ <i(x) i,s divisible by g {z}
Exercise 6
Let g(x) = gcd(gi(x), ^a(x)}, where gcd is the polynomial greatest (highest degree) common divisor of the two polynomials and let C be the code generated by g{x).
First we show that a code generated by g(x) contains C\ U CV if a codeword is in this union then clearly it is a multiple of g\{x) or Now since g{x) is a divisor of both gi(x) and (^(x) the codeword is also a multiple of g(x) and thus Ls in a code generated by g(x).
Now we know by definition of gcd (using the extended euclidean algorithm that
g(x) = a(x)gl(x) + b(x)g2{x)   mod {xn - 1),
for some polynomials a(x), b(x) and where n is the code block length. Now a(x}gi(x) € C\ and b(x}g2(x) € Ca. From this we can see that g(x) is just a sum of two codewords from Ci and C2 respectively. Any cyclic (and thus linear) code containing C\ U C2 (and thus a(x)gi(x) and b(x)g2(x}} must also contain this sum of the two code words and t hus must contain g(x) and all its multiples, thus C C C and with the previous result we obtain C = C and g(x) is our desired polynomial. (The polynomial gcd is unique up to a multiplication by a constant but this constant doesn't change the code C.)
Exercise 7 (a) RM(1,3) =
{00000000, 00001111, 00110011, 00111100, 01010101, 01011010, 01100110, 01101001, 10010110, 10011001, 10100101, 10101010, 11000011, 11001100, 11110000, 11111111 }
AM (1,4) =
{0000000000000000, IWOOOOOOllllllll,0000111100001111,0000111111110000, 0011001100110011, 0011001111001100, 0011110000111100, 0011110011000011, 0101010101010101, 0101010110101010, 0101101001011010, 0101101010100101, 0110011001100110, 0110011010011001, 0110100101101001, 0110100110010110, 1001011001101001,1001011010010110,1001100101100110,1001100110011001, 1010010101011010, lOlOOlOllOlOOlOl, 1010101001010101,1010101010101010,1100001100111100, 1100001111000011, 1100110000110011,11()()11()()11(M)11()(), 1111000000001111,1111000011110000, 1111111100000000,1111111111111111 }
(b) Prom the construction, we can sec that if we find a base generating the (u,u) part of the code, then we can get (w, u + 1 ) with the help of one vector that is ( 0 , 1 ), where | 0 | = | 1 |. So all we need to solve is the remaining vectors. The idea of the code is repetition, so the new base words will be repetitions of all the old, this gives us the construct
G(l,m-1)  G(l,m-1) ' If f
(7(1,0) = [1] and (7(1,71.) = f *   J j and (7(1, m) =
(c) We can show that the parameter with an induction like proof on m.
Base case: R{1, 1)[2, 2,1] is clearly an [2m, m + 1, 2™"1] code.
Induction hypothesis: We assume that R.{l,ni - 1) is a [2m_\ m,2"l~'2] code.
Induction Step: The repetition always doubles the length so n — 2 x. 2m_1 = 2m.
Also we see that repetition itself does not add a new base word, only the "reversed" repetition needs lo be handled, mid that is done by out' wort! ( 0 . 1 ) so A     in I J For d, we need to check two options:
1. By only repeating, the smallest distance {we ig lit) will double, what gives
2 x 2"
-2 _      i\m— 1
2. if we do the "reversed" repetition, {and the base contains x 1-bits) we are adding 2m_1 — x to the weight, which in total results in
im-1      ....   i   .... _       nm— 1
x + x = 2"
And (/ is the minimum of the two, which is 2'" 1.
—» —»
For the weights, if for the simple repetition case r = («., m), and u is I) or 1 , than r will also
be 1? or T*. Every other word will have 2 x 2"1-2 = 2m_1 weight(as seen in the induction
—*
above). For the case r = (u,u+ 1 ) there are :i eases: —» —V —*
1. u — 0 , then we get (0,1) where clearly half of the bits is 1, what gives weight
2m -s- 2 = 2m_1
—^ —^ —^
2. ii = 1 , the ease is the same as in point 1 above, just with (1,0).
3. l-ni every othel u. as showed in t he induct ion step above (point 2). the weight will In-ball' of the length, which is 2'" '.