cyclic codes

Question 1

cyclic shift:

Answer 1

for a vector a=(a0, a1, …, an), we denote s(a)=(a(n-1), a0, …, a(n-2)), and we call this the cyclic shift - essentially this is shifting the vector one space to the right

Question 2

cyclic code:

Answer 2

a linear code such that for all a in C, s(a) in C, equivalent to s(C)=C

Question 3

ring:

Answer 3

a abelian group of numbers with 2 functions, one addition (cause it’s abelian, that means it’s associative, commutative (a+b=b+a), there’s an identity element, and an inverse (-a) and one multiplication where the multiplication is associative (ab)c=a(bc), distributive over the addition, and has an identity element for multiplication

Question 4

division theorem for polynomials:

Answer 4

for all f(x) in Fq[x] (the ring of polynomials) \0, there exists a unique Q(x), r(x) with f(x)=g(x)Q(x)+r(x) and deg r(x)<deg g(x) - Q(x) is the quotient, and r(x) is the remainder of f(x) when divided by g(x)

Question 5

long division of polynomials refresher:

Answer 5

denominator | numerator
divide the first term of the numerator by the first of the denom, write that on top
multiply the denom by that result, write that below the numerator
subtract the new result from the numerator for a new polynomial and repeat with that until you no longer can, then you have a quotient on top and the remainder at the bottom

Question 6

monic:

Answer 6

a polynomial is monic if the coefficient of the highest power is 1

Question 7

generator polynomial:

Answer 7

of a cyclic code C, C!={0}, is a monic polynomial of least degree in C - for the null code this is x^(n)-1, this is unique and every cyclic code has one

Question 8

properties of the generator polynomial:

Answer 8

deg g=n-k
C={u(x)g(x): u(x) in R} - the code polynomials of C are all possible multiples of g(x) of degree less than n
g(x) is a monic factor of the polynomial x^(n)-1 in Fq[x]

Question 9

check polynomial:

Answer 9

let g(x) be the generator polynomial of a cyclic code, the polynomial h(x) defined by g(x)h(x)=x^(n)-1 is the check polynomial of C

Question 10

generator matrix of a cyclic code with generator polynomial g(x):

Answer 10

the vector g and ixhets next k-1 shifts form a generator matrix for C, all spare spaces are 0

Question 11

check matrix of a cyclic code with check polynomial h(x):

Answer 11

reverse the order of the coefficients of h(x), and its next n-k-1 shifts form a check matrix, this will ensure the first number is always 1, all spare spaces are 0

Question 12

generator polynomial of C⊥:

Answer 12

(h0)^-1(<-)h(x) - the (<-) is over the h(x), the sign for reversed coefficients, we scale by (h0)^-1 cause the polynomial has to be monic