15 Cyclic codes

Question 1

Def cyclic code

Answer 1

A code C ⊆ Fⁿ is cyclic if it is linear and any cyclic shift of a codeword is also a codeword,

LINEAR (0) +INVARIANT UNDER SHIFT MAP
Sh : (a₀, . . . , aₙ₋₁,) → (aₙ₋₁, a₀, . . . , aₙ ₋₂) : Fⁿ → Fⁿ

Question 2

is 2-ary code C = {000, 101, 011, 110} cyclic

Answer 2

YES

Question 3

POLYNOMIALS IN A FIELD F
F[X]

MONIC POLYNOMIALS

Answer 3

set of all polynomials
a(x) = a_0 + a_1x+a_2x_2 +…..

A MONIC polynomial has degree m with a_m=1
biggest degree has coeff 1
​
F[x] is a ring, but not a field.

Question 4

the evaluation function for polynomials

Answer 4

Associated to anypolynomial a(x) ∈ F[x] there is a function:
α → a(α) : F → F (the evaluation function).

Question 5

the evaluation function for finite fields

Answer 5

There are 4 distinct functions from Z₂ → Z₂.

But there are infinitely many different polynomials in Z₂[x]. E.g.
a(x) = x5 + x2 + x + 1,
b(x) = x^17 + 1, both have the same
function associated to them :

they produce same outputs as powers of x can be reduced mod 2
x^17=x mod 2
b(x)=x+1 and is the same

Question 6

The remainder thm

Answer 6

For every pair a(x), b(x) ∈ F[x] with b(x) ̸= 0, there exists a unique pair q(x) (the quotient) and r(x) (the remainder) in F[x]

such that deg(r(x)) < deg(b(x)) and

a(x) = q(x)b(x) + r(x).

Proof: We can compute q(x), r(x) by the usual long-division
algorithm.

Question 7

15.6. Exercise. Divide
a(x) = x³ + 3x² + 4
by
b(x) = 2x² + 3 in Z₅[x].

Answer 7

x³ + 3x² + 4
= (3x + 4)(2x² + 3) + (x + 2)

Question 8

using the remainder thm to rewrite polynomials

equivalence relation

a(x) ≡ b(x) mod f (x)) when

Answer 8

For a fixed poly f(x) in F[x]
polynomials a(x), b(x) ∈ F[x]
a(x) ≡ b(x) mod f (x))

if a(x) − b(x) is divisible by f (x)

(meaning a(x) − b(x) = q(x)f (x) for some q(x) ∈ F[x], with no remainder)

Question 9

denote equivalence (congruence) class of a(x) by

[a(x)] = {b(x) ∈ F[x] | b(x) ≡ a(x) mod.f (x)}

Let F[x]/f (x) denote the set of such classes.

ADDITION AND MULTIPLICATION ON F[x]/f (x)

Answer 9

[a(x)] + [b(x)] = [a(x) + b(x)]

[a(x)][b(x)] = [a(x)b(x)]

By these operations F[x]/f (x) is a ring.

Question 10

15.8. Lemma.
[a(x)] = [a′(x)] IFF

Answer 10

[a(x)] = [a′(x)]

**iff a(x) ≡ a′(x) mod f (x) **

iff the remainders r(x),r′(x) of a(x) and a′(x) under division by f (x) are
equal

ie we can identify [a(x)] by looking at remainders r(x)

Question 11

15.9. Example.
R = Z₂[x]/(x² + x + 1)
(f (x) degree 2),

R ≡

Answer 11

gives R ≡ {0, 1, x, 1 + x}
= polynomials of degree < 2.

*working with polynomials in x over Z₂ , and you’re identifying any two polynomials that have the same remainder when divided by (x² + x + 1)

• we can express them as polynomials of degree less than f(x)’s that have a different remainder to each other

Question 12

15.9. Example.
R = Z₂[x]/(x² + x + 1)
(f (x) degree 2),

gives R ≡ {0, 1, x, 1 + x}
= polynomials of degree < 2.

Compute the addition and multiplication tables. Can you compute inverses too?

Answer 12

R is a field in this case: every non-zero element has an inverse
+ | 0 1 x 1 + x
————————-
0 | 0 1 x 1 + x
1 | 1 0 1 + x x
x | x 1 + x 0 1
1 + x | 1 + x x 1 0

• ## | 0 1 x 1 + x0 | 0 0 0 0
  1 | 0 1 x 1 + x
  x | 0 x 1 + x 1
  1 + x | 0 1 + x 1 x

Inverse of 0 is itself (0 * 0 ≡ 0)
Inverse of 1 is itself (1 * 1 ≡ 1)
Inverse of x is 1 + x (x * (1 + x) ≡ 1)
Inverse of 1 + x is x ((1 + x) * x ≡ 1)

Question 13

f (x) ∈ F[x] is reducible if

Answer 13

there exist
a(x), b(x) ∈ F[x]
with degrees less than f (x), such that
f (x) = a(x)b(x).

FACT: F[x]/f (x) is a field iff f (x) is not reducible (irreducible).

Question 14

15.11. Lemma.
for degrees and factors of f(x) polynomials

Answer 14

(i) f (x) ∈ F[x] has a degree 1 factor (x − a) iff
f (a) = 0.

(ii) If degree f (x) =2 or 3 then f (x) is irreducible iff for all a ∈ F, f (a) ̸= 0.

** (iii) Over any field F,
xⁿ− 1 = (x − 1)(xⁿ⁻¹ + xⁿ⁻² + … + x + 1)**

Proof: (i) Use Theorem 15.5. (iii) by induction on n.

Question 15

Completely factorise
x⁴ − 1 ∈ Z₅[x].

Answer 15

(x-1)(x^3+x^2+x+1)

(x − 1)(x+1)(x^2+1)
=(x-1)(x+1)(x-2)(x-3)
found by trying all 0,1,2,3,4 in to see x^2+1≡ 0

= (x + 4)(x + 3)(x + 2)(x + 1)

Question 16

for cyclic codes we use the ring R_n

Answer 16

R_n =
F[x]/(xⁿ − 1)

For given finite field F

Question 17

facts about R_n

Answer 17

(xⁿ − 1) ALWAYS IRREDUCIBLE R_n never a field

xⁿ ≡ 1 mod (xⁿ − 1)
so
xᵐ⁺ⁿ =xᵐ for any m
.No need to use
remainder theorem to compute products

Question 18

E.g. in R_5 = Z_3[x]/(x^5 − 1)

(x^2 +x)(x^4 + 2) =

Answer 18

= x^6 + 2x^2 +x^5 + 2x
≡ x + 2x^2 + 1 + 2x (since x^5=1 sub)
= 2x^2 + 1 (3x =0 in Z_3)

Question 19

fact about R_n

Answer 19

(c) Since deg(xⁿ − 1) = n we can identify R_n with polynomials of degree less than n, and hence with Fⁿ: a_0 + a_1x + … + a_{n−1}x^{n−1} ↔
(a_0, a_1, .., a_{n−1})

addition of polys ↔ vector addition
multiplication by constant ↔ scalar multiplication
multiplication by x ↔ cyclic shift.

Question 20

We can think of a q-ary code of block-length n as a subset of Rn
(with F = Fq). Then:
Theorem 15.14.
WHEN IS C A CYCLIC CODE THM

Answer 20

A code C ⊆ Rₙ is a cyclic code iff

(i) a(x), b(x) ∈ C implies a(x) + b(x) ∈ C;

(ii) a(x) ∈ C, r(x) ∈ Rn implies r(x)a(x) ∈ C.

(NB (ii) is more than closure of C under multiplication!)

Question 21

for f(x) in R_n

ring span
<f(x)>

Answer 21

⟨f (x)⟩ = {r(x)f (x) | r(x) ∈ Rn}

this satisfies properties thm hence IT IS A CYCLIC CODE OVER F_q

Question 22

the cyclic code generated by f (x)

Answer 22

⟨f (x)⟩ = {r(x)f (x) | r(x) ∈ R_n}

Question 23

Give the cyclic code generated by:
F_q = Z_2, C = ⟨1 + x^2⟩ ⊂ R_3 = Z_2[x]/(x^3 − 1)

Answer 23

Coefficients in Z_2 which are divided by (x^3 − 1)
R_3=
{0, 1, x, 1 + x, x², 1 + x², x + x², 1 + x + x²}

C= {r(x)f (x) | r(x) ∈ R_3}
C = {0, 1+x², x+1, x²+x, x²+x, 1+x, x+x²+x³+x⁴, 1+x+x²+x²+x³+x⁴}
= {0, 1 + x², 1 + x, x + x²} ↔ {000, 101, 110, 011} ⊂ Z₂³

Question 24

Exercise. Show that ⟨1 + x²⟩ = ⟨1 + x⟩ = ⟨x + x²⟩ in this
case.

Answer 24

..

So more than one polynomial can generate a given cyclic code. However, there is a canonical choice of generating polynomial:

Question 25

Theorem 15.18.
GENERATOR POLYNOMIAL OF C

Answer 25

Let C be a non-zero cyclic code in R_n.

Then there is a monic polynomial g(x) in C which has all the following properties and is unique with any one of them:

(i) g(x) of least degree in C.

(ii) Every codeword a(x) ∈ C is a strict multiple of g(x):
a(x) = b(x)g(x)
(not just congruent mod. xⁿ − 1).

(iii) C = ⟨g(x)⟩ and g(x) is a factor of xⁿ − 1.

Question 26

generator polynomial for
C={0}

Answer 26

For C = {0} we take xⁿ − 1. as the
generator polynomial, although it is not of degree < n and can therefore not really be considered to be an element of C.

Question 27

generator polynomial for

{000, 101, 110, 011} ⊂ Z₂³

prevuously shown

Answer 27

g(x) = 1 + x

Question 28

generator polynomals: cyclic codes

Answer 28

Since the gen. poly. is unique, cyclic codes of length n are in 1-to-1 correspondence with monic factors of xⁿ − 1. This
completely characterises all cyclic codes!

Question 29

Example. Find all cyclic codes over Z_2 of length 3.

C ⊂ R_3 = Z_2[x]/(x³ − 1).

Answer 29

x³ − 1=
= (x − 1)(x² + x + 1) = (x + 1)(x² + x + 1)

and
R_3=
{0, 1, x, 1 + x, x², 1 + x², x + x², 1 + x + x²}

Therefore, the cyclic codes of length 3 are generated by polynomials that divide x³ − 1

so there are four such codes:
⟨1⟩ = R_3 = Z₂³
⟨1 + x⟩ = {0, 1 + x, 1 + x², x + x²} = {000, 110, 101, 011}
⟨1 + x + x²⟩ = {0, 1 + x + x²} = {000, 111}
⟨(1 + x)(1 + x + x²)⟩ = {0} = {000}

Question 30

15.21. Example. How many cyclic codes of length 4 over Z_5 are there?

Answer 30

Answer: same as number of monic factors of x^4 − 1 ∈ Z_5[x].
x^4 − 1 = (x + 4)(x + 3)(x + 2)(x + 1) over
Z_5, so the general monic factor is
g(x) = (x + 4)^p4(x + 3)^p3(x + 2)^p2(x + 1)^p1
where each pi can be either 0 or 1.

Since there are 2^4 choices 16 cyclic codes.

For example p1 = p4 = 1, p2 = p3 = 0 gives code
⟨(x + 1)(x + 4)⟩ = ⟨x^2 − 1⟩

Question 31

code
⟨(x + 1)(x + 4)⟩ = ⟨x^2 − 1⟩
is

Answer 31

as there are two distinct nonzero polynomials in
⟨x^2−1⟩ = {0, x^2-1}

a cyclic code
generated by the polynomial

dimension=#distincy non zero elements in the set= 2

Question 32

GENERATOR MATRIX FROM THE GEN POLY

Answer 32

for cyclic code C
G=
[g0 g1 g2 .. gr 0 .. 0]
[0 g0 g1 g2 .. gr.. 0]
.
.
.
[0 … 0 g0 g1 g2 .. gr]

where g_r are the coefficients for the gen poly
for ASCENDING DEGREE ORDER
as its monic g_r=1

G is a (n − r) × n matrix.

Question 33

dimensions of a cyclic code

Answer 33

A cyclic code C ⊂ R_n whose gen. poly. has
degree r has dim.
k = n − r and has redundancy r.

Question 34

HOW WOULD WE GO ABOUT CONSTRUCTING A GEN MATRIX FOR EACH 3 -ARY CYCLIC CODE LENGTH 4

Answer 34

R_4= Z_3[x]/ (x^4-1)
factorise x^4-1
=(x+1)(x+2)*(x^2+1)
the monic factors will make up the gen poly

the gen poly is made by combinations of these factors multiplied together
for 3 factors we have
2 x 2 x2 possible cyclic codes

their dimension k=n-r
r is the degree of the gen poly= redudancy

Matrix is ascending order degree of coeffs,ending in 1, then 0’s
shifted until the end

Question 35

dual of a cyclic code

Answer 35

THM
If C is cyclic so is C⊥

Proof. For x, y ∈ F^n we have
Sh(x) · Sh(y) = x · y and therefore

Sh(x) · y = x · Sh−1(y).

So if C is cyclic and x ∈ C⊥, then

Sh(x) · y = x · Sh−1(y) = 0 for all y ∈ C,
i.e. Sh(x) ∈ C⊥.

Question 36

CHECK POLYNOMIAL

Answer 36

for CYCLIC C⊂R_n with gen poly g(x)
h(x) is the check poly of C
xⁿ − 1 = g(x)h(x)

h(x) is unique

Question 37

<h(x)>
will the check poly generate the dual of C

Answer 37

It is not true in general that C ⊥ = ⟨h(x)⟩, but we can construct the parity check matrix of C and the gen. poly. for C ⊥ from h(x).

Question 38

PCM OF A CYCLIC CODE

Answer 38

Given gen poly we find check poly

h(x)=
h_k =1 is monic so start with 1
LEADING DIAGONAL 1a

DESCENDING DEGREE COEFFICIENTS
H
=
[h_k h_{k−1} .. h_0 0 .. 0]
[0 h_k hk−1 hk−2 .. h0 .. 0]
.
.
.
0 … 0 hk hk−1 hk−2 .. h0]

r x n = degree of gen x n
THIS IS PCM
as dims match

Question 39

PCM for g(x) = x^2 + x + 3 is the gen. poly.
of a cyclic 5-ary [4,2]-code C

Answer 39

(x^2 + x + 3)(x^2 + 4x + 3) ≡
x^4 − 1

h(x) = (x^2 + 4x + 3).

H=
1 4 3 0
0 1 4 3 is a pcm for C

degree of g =2 =r k=n-r=2
2 x 4

Question 40

HOW TO FIND THE GEN POLY FOR THE DUAL GIVEN THE CHECK POLY

Answer 40

Let C ⊂ Rn be a cyclic code with check poly.
h(x). Then C⊥ is the cyclic code with gen poly.
g⊥(x) = h^{−1}_0h~(x)

where h~(0) is the reciprocal of h(0)

Question 41

reciprocal of a poly

Answer 41

Given p(x) = p0 + p1x + … + pk x^k ∈ F[x]
(pk ̸= 0) the reciprocal of p(x) is
p~(x) =
x^kp(1/x) = pk + pk−1x + …. + p_0x^k ∈ F[x] .

Question 42

C = ⟨x^2 + x + 3⟩ ⊂ R4 = Z5[x]/(x^4 − 1)
has
check poly h(x) = 3 + 4x + x^2
.
FIND THE GEN POLY FOR THE DUAL OF C

Answer 42

g⊥ = h_0^{−1}h(x) = 3^{−1}(1+4x+3x^2
) = 2(1+4x+3x^2) = 2+3x+x^2

if we divide every row of H by h_0 then we have a generator matrix as required

Question 43

Construct a generator matrix for the binary
n = 7 cyclic code C with generator polynomial
1 + x + x^3

Answer 43

1 1 0 1 0 0 0
0 1 1 0 1 0 0
0 0 1 1 0 1 0
0 0 0 1 1 0 1
r=3
k=7-3=4
4 x 7 matrix

Question 44

Construct a PCmatrix for the binary
n = 7 cyclic code C with generator polynomial
1 + x + x^3

Answer 44

h(x) is s.t xⁿ − 1 = g(x)h(x)
xⁿ − 1 = (1 + x + x^3)h(x) n=7
h(x) = (1 + x + x^2 + x^4)

H=
1 0 1 1 1 0 0
0 1 0 1 1 1 0
0 0 1 0 1 1 1

also d(C) = 3. This is a Hamming code!

Question 45

Let C, C′ be cyclic codes. What can you say
about their intersection?

Answer 45

CYCLIC
if C is generated by g(x) and C ′ is generated by g ′ (x), then
C∩C is generated by LCM (g(x),g′(x))

Question 46

. If C is cyclic and C′ is an equivalent code, is C ′
necessarily cyclic?

Answer 46

Two codes are considered equivalent if one can be obtained from the other by a combination of operations such as permutation of coordinates, adding or deleting coordinates, and/or adding a fixed vector to each codeword.

Cyclic codes are invariant under such operations.