The Error Correcting Codes

Coding Theory
R1 =(10101 110110 11100)
10101=1+x2 +x3 +x5
110110=1+x+x3 + x5 +
11100=1 + x + x2
R1 is a cyclic [3,5] over the polynomial g(x)=x3 + x4 + x5 +x6
R2 =( 11000 01110 10011)
11000=1 +x
01110=x +x2 + x3
10011=1 + x3 + x4
R2 is a cyclic [3,5]-order over polynomial g(x)=x3 + x4 + x5 +x6
R3 =(01000 00010 11111)
01000 =x
00010 =x4
11111=1 + x + x2 + x3 + x4
R3 is a cyclic [3,5] –order over polynomial (x)=x3 + x4 + x5 +x6
Problem 2
Part a
Let y=x
If g(y) is a generator polynomial of a cyclic code C,then you will have F(y)=yn-1 =h(y)g(y) +p(y)
where;
deg.p(ydegg(y)

Thus, p(y)=-g(y)h(y)mod(yn-1), hence p(y) ∈C
But;
P(x)∈is not possible unless p(y)=0
Assume that g(y) can divide xn-1 in regard g(y) is ideal and all multiples of g(x) are reduced to
modulo (yn-1)
Let there be a polynomial b(y) which is ideal and has got a smaller degree.
There is enough evidence to show that there is no such b(x) that would exist and g(x) is the
smallest degree polynomial, hence it is ideal and a generator.
For Instance;
Consider V[7,2] and g(y)h(y)=y7-1
To completely factorize g(x)h(x) over GF(2),you get;
y7-1=(y+1)(y3+y2+1)(y3 + y + 1)
And you can get the monic divisors to be ;
g 1(y) =1
g 2(y) =y+1
g 3(y)=y3 +y2 +1
g 4(y) = y3 +y +1
g 5(y)=(y +1)(y3 + y2 + 1)
g 6(y)=(y + 1)(y3 +y+1)
g 7(y)=(y3 +y2 +1)(y3 + y2 +1)
Assume that h(y) = F 2( y )
y n−1
You can see that C is a cyclic code and a polynomial g(y) is such that h(y) is in a way that C=g(y)
Assume C1 is a subcode of the codomain hence deg(y) generates [n,k-1]code
Because C1 is cyclic,C1=g(y) for certain g(y) ∈ h[y]

Therefore, degg(y) =(n-k)=n-k+1
As a result,we get;
C⊂C1 and f(y) divides g(y) in F 2( y )
y n−1 .This makes g(y)=(y-a)f(y)
When y-a ∈h(y) ,a=1 or a=0
As g(y) can divide yn-1 and y does not divide yn-1 in spite of being y-1 does, you get a=1.
This may mean that y-1 is a divisor of g(h) and h(y).
However,g(y) is a generating polynomial of C1 and therefore, for all h(y) ∈C,you will realize that
h(1) =0.
This is the roots of all codes in C1 and might be an indication that all codewords in C1 are even in
weight of vector C.
Because n is odd,yn-1 is a seperable polynomial and as g(h) divides yn-1 ,g(y) is also seperable.
Thus,from the realization,you can note that y-1 is not a divisor of the function.
As a result,it proves that f(1)≠0,hence f(y) is odd in weight.
And C contains both odd and even vectors .in addition,a set of vect C is a subcode of C1 with
one as the dimension.
Consequently,C1 is precisely a set of all the even weight vectors in C.
You can confirm that :
g(y) would generate the full space of V[7,2]
g 8(y) would generate the trivial cyclic subspace {(0000000)}
g6(y) generates the cyclic code {(0000000),(1011100),(0101110),(0010111),(1001011),
(1100101),(1110010),(0111001)}
g 7(y) generate the cyclic code {(0000000),(1111111)}
V[7,2] precisely contains 8 cyclic codes

You can therefore conclude that code C with the polynomial g(y) is self-orthogonal if and only if
h*(y) divides g(y).
Part b
Consider a linear cyclic code over GF(4) to be of length n (4m-1) and assume the polynomial
generator g(x) to be self-orthogonal on condition that :
h (x)g(x) =0mod(xn-1)
Take h(x)=∑
0
n −1
gr Xr
Thus g(x)=GCD(gn-rxr,xn-1)
Understand that the polynomial generator of the cyclic codes are expressed in the form of their
zeros in GF(n).
Assume that ʎ∈GF(4m) to be a primitive unity root.
Suppose g(x) has got a root of ʎ2
Then ,
g (ʎz)=g0+g1 ʎz +g2 ʎz +…………+gr ʎ(n-1)z=0
= g0+g1 ʎ2z + g2 ʎ4z +…………+gn-1 ʎ(n-1)2z=0
=
= g0+g1 ( ʎ-2z )+ g2 (ʎ-2z)n-2 +…………+gn-1 (ʎ-2z)=0
And therefore ,a polynomial g0+g1 xn-2 + +…………+gn-1x=0 has got ʎ-2z as the root.
Because the root xn-1 is ʎ-2z ,you can also confirm it to be the root of g(x)
It also follows that Z ⊂{0,1,2,3,……….,n-1} is a set of zeros of g(x) and this may also mean that
Z1={-2zmod n|z∈ Z} is a set of g(x)
Supposing that n=15,the cyclotomic consent modulo of n when multiplied by 4 gives {0},{1,4},
{2,8},{3,12},{5},{6,9},{7,13},{10},{11,14}.
Thus (15,6) is a cyclic code over GF(4) where z is a zero set with z ={0,5,10,1,4,11,14,3,12}

You will realize that Zeros in GF(16) are self-orthogonal because, the non-zero elements like
S={7,13,2,8,6,9} are such that -2S and n⊂Z .
S has got only 4 consecutive integral hence we you can conclude that d=S is the minimum
distance of the dual code.
Consequently,[15,3,5] is a quantum code obtained from from self-orthogonal cyclic code.
You can also Consider the polynomial g(y)h(y)= y15- 1.
To completely factorize g(x)h(x) over GF(2) ,you get:
y7-1 =(y+1)(y2 + y+1 )(y4 +y + 1)(y4 + y3 + 1)(y4+y3 +1)(y4 +y3 +y2 +y + 1)
Assume C to be the [15,k] binary cycle code of length 15 generated by:
g(x)=(y+1)(y4 +y +1)
Hence
g 14(x) generates a cyclic code {(000000000000000),(010000000000000)}
V[15,2] precisely contains 16 cyclic codes.
Problem 3
Assume that r =(r0,r1,……..rn-1) is the received vector .
For each vector y=(y1,y2,…..yn-1),define [y]k to be k-tupple (y0,y1,,,…..yk-1)
Suppose that M is the generator matrix for C that is written in standard form.
You can consider the decoding algorithm below.
For I,0 ≤i≤ n−1,try to;
i)Compute ci =[xir]kG
ii) Compute d(cir]kG
But if d(ci r]≤ t the you are to decode r to x-ici
QUESTION 4 (a)

In coding hypothesis, a polynomial code is a kind of straight code whose
arrangement of legitimate code words comprises of those polynomials
(typically of some fixed length) can be divided by a given fixed polynomial
(of shorter length, called the generator polynomial).
For the reasons for building polynomial codes, we distinguish a string of n
images a n-1 - a0 with the polynomial a n-1 xn +-- - ax1 + a0
Fixed numbers m less or equivalent to n and let g(x) be some fixed
polynomial of degree m, called the generator polynomial. The polynomial
code created by g(x) is the code whose code words are absolutely the
polynomials of degree not as much as n that are separable (without leftover
portion) by g(x).
Since C (n k) is a cyclic code over F
C= g*(x) = a0 + a1x + a2x2 + ... + an-k xn-k
C’=g’(x) = a0 + a1x + a2x2 + ... + an-k xn-k
Therefore, C produces a generator which is k x n matrix
Based on the generator matrix above, the vector g(x), vector xg(x), vector
x2g(x), ..., vector x k-1 g(x) are linear and independent.
QUSTION 4 (b)

C is equal to g*(x) = a0 + a1x + a2x2 + … + a n-k x n-k+1
C’ is equal to G’(x) = 1 + a1x + a2x2 + ... + a n-k x n-k
= g*(x) divided by g’(x) =X
Hence C*≤ C’.
QUESTION 4 (c)
In coding hypothesis, a cyclic code is a square code, where the circular
movements of each codeword gives another word that has a place with the
code. They are mistake remedying codes that have logarithmic properties
that are advantageous for effective blunder discovery and rectification.
From question 4(ii) it follows
= g*(x) divided by g’(x) =X
Hence C*≤ C’.
C is equal to g*b0g(x) + b1xg(x) + b2 x2 g(x) + ... + b k-1 x k-1 g(x) = 0,
C’ is equal to (b0 + b1x + b2x2 + ... + b k-1 x k-1) g(x) = 0.
But this product has degree k - 1 + n - k = n - 1 < n, so it cannot be = 0 mod
(xn - 1) unless all the bi = 0.
Now since the c(x) exists in C, then c(x) = b(x) g(x) and we, therefore,
assume that b(x) has degree <= k - 1 (if not so, the product would have a
degree greater than n - 1 and we would reduce modulo (x n - 1) to get a b'(x)
which satisfies this degree constraint). Therefore, c(x) can be written as a
linear combination of the xi g(x).
The set of [xi g(x)], 0 <= i <= k - 1 which is thus a basis for C and therefore
this cyclic code has dimension k.

QUESTION 5 (a)
Vector space is a space comprising of vectors, together with the acquainted
and commutative activity of expansion of vectors, and the cooperative and
distributive activity of increase of vectors by scalars.
The Number of cyclic spaces is calculated as follows
V = V15(Z7).
G(x)= 1 + x1 + x2 + x4 + x5 + x8 + x10
which generates a distance 7 binary code of length 15
QUESTION 5 (b)
For values k, 1≤k≤15
GF (24) is generated by alpha of
f(x) =1 + x + x4
m1(x) = 1 + x + x4
m2(x) = 1 + x2 + x3 + x4
m5(x) = 1 + x + x2 and
g(x) m1(x)m2(x)m5(x)
QUESTION 5(c)
primitive root mod n is a whole number g with the end goal that each
number moderately prime to n is consistent to the power of g mod n.

From question (5b), the α is a primitive root of unity and α1 α2 α3 α4 α5 α6 are
among the roots of g(x).
Now,
The cyclic spaces of V
R=1 0 0 1 1 1 1 1 1 0 0 0 1 1 0
QUESTION 6 (a)
Arithmetic modulo
x 2 + x + 1 is equal to replacing the existing multiples of x 2 + x + 1 by Zero
GF (4) therefore is a linear combination of basis vectors 1 and α
GF (4) = {0, 1, α, α + 1
Therefore,
GF (4) = Z2[0] = (02 + 0 + 1). =1
QUESTION 6 (b)
Neither 0 nor 1 is a root of the polynomial G(z) = z2 + z + α,
Therefore, it has no factors of degree 1 in GF(4)[X].
Again, for a similar reason, if it had a factor of degree 2 in GF(4)[X] the factor
would or must had to be irreducible. The only existing irreducible polynomial
of degree 2 in GF(2)[X] is X2 + X + 1.
Further, If this was a factor of z2 + z + α in GF(2)[X], it would also
automatically be a factor of z2 + z + α in GF(4)[X], which mean that α, any

primitive element of GF(4)[X] with minimal polynomial X2 + X + 1, and
would be a root of X5 + X3 + 1 in GF(4)[X].
However, α
5 + α
3 + 1 = α
2 6= 0 in GF (4).
Thus
z2 + z + α do not have any factors of degree 2 in GF(4)[X]. It, therefore,
follows that this polynomial is irreducible in GF(4)[X] because if it were
reducible it would have to have a factor of degree 1 or a factor of degree 2.
QUESTION 6(c)
GF (42) = {0, 1, β, δ}. 0, 1 are additive and multiplicative identities.
Therefore,
GF (42) = GF (4) [z]/ (z2 + z + α).
GF(4)[z] =z2 + z + α
Since factor of degree 2 in GF (42)[z], it is an irreducible
Therefore,
GF (4) *[z] =z2 + z + α = GF (42) Thereby the generator
QUESTION 6 (d)
G(z) = z2 + z + α
Factoring y15 - 1 over GF (4) becomes
Y2 + y3 + y5 = y2G(y)

Code (0 0 1 1 0 1 0)
REFERENCE
1.Abrahamson,N.(2002).Information Theory and Coding.New York:MacGraw-Hill
2.BerleKamp,E.R.(2010).Algebraic Coding.New York:MacGraw-Hill.
3.Blake,I.F and Mullin,R.C.(2011).Mathematical Theory of Coding.New York:Academic Press.
4.Peterson ,W,w and Weldon,E.J.Error Correcting Codes.Cambridge:M.I.T Press.