15 Cyclic codes Flashcards
Def cyclic code
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ⁿ
is 2-ary code C = {000, 101, 011, 110} cyclic
YES
POLYNOMIALS IN A FIELD F
F[X]
MONIC POLYNOMIALS
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.
the evaluation function for polynomials
Associated to anypolynomial a(x) ∈ F[x] there is a function:
α → a(α) : F → F (the evaluation function).
the evaluation function for finite fields
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
The remainder thm
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.
15.6. Exercise. Divide
a(x) = x³ + 3x² + 4
by
b(x) = 2x² + 3 in Z₅[x].
x³ + 3x² + 4
= (3x + 4)(2x² + 3) + (x + 2)
using the remainder thm to rewrite polynomials
equivalence relation
a(x) ≡ b(x) mod f (x)) when
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)
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)
[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.
15.8. Lemma.
[a(x)] = [a′(x)] IFF
[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)
15.9. Example.
R = Z₂[x]/(x² + x + 1)
(f (x) degree 2),
R ≡
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
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?
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)
f (x) ∈ F[x] is reducible if
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).
15.11. Lemma.
for degrees and factors of f(x) polynomials
(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.
Completely factorise
x⁴ − 1 ∈ Z₅[x].
(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)
for cyclic codes we use the ring R_n
R_n =
F[x]/(xⁿ − 1)
For given finite field F
facts about R_n
(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
E.g. in R_5 = Z_3[x]/(x^5 − 1)
(x^2 +x)(x^4 + 2) =
= 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)
fact about R_n
(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.
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
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!)
for f(x) in R_n
ring span
<f(x)>
⟨f (x)⟩ = {r(x)f (x) | r(x) ∈ Rn}
this satisfies properties thm hence IT IS A CYCLIC CODE OVER F_q
the cyclic code generated by f (x)
⟨f (x)⟩ = {r(x)f (x) | r(x) ∈ R_n}
Give the cyclic code generated by:
F_q = Z_2, C = ⟨1 + x^2⟩ ⊂ R_3 = Z_2[x]/(x^3 − 1)
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₂³
Exercise. Show that ⟨1 + x²⟩ = ⟨1 + x⟩ = ⟨x + x²⟩ in this
case.
..
So more than one polynomial can generate a given cyclic code. However, there is a canonical choice of generating polynomial:
Theorem 15.18.
GENERATOR POLYNOMIAL OF C
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.
generator polynomial for
C={0}
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.
generator polynomial for
{000, 101, 110, 011} ⊂ Z₂³
prevuously shown
g(x) = 1 + x
generator polynomals: cyclic codes
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!
Example. Find all cyclic codes over Z_2 of length 3.
C ⊂ R_3 = Z_2[x]/(x³ − 1).
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}
15.21. Example. How many cyclic codes of length 4 over Z_5 are there?
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⟩
code
⟨(x + 1)(x + 4)⟩ = ⟨x^2 − 1⟩
is
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
GENERATOR MATRIX FROM THE GEN POLY
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.
dimensions of a cyclic code
A cyclic code C ⊂ R_n whose gen. poly. has
degree r has dim.
k = n − r and has redundancy r.
HOW WOULD WE GO ABOUT CONSTRUCTING A GEN MATRIX FOR EACH 3 -ARY CYCLIC CODE LENGTH 4
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
dual of a cyclic code
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⊥.
CHECK POLYNOMIAL
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
<h(x)>
will the check poly generate the dual of C
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).
PCM OF A CYCLIC CODE
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
PCM for g(x) = x^2 + x + 3 is the gen. poly.
of a cyclic 5-ary [4,2]-code C
(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
HOW TO FIND THE GEN POLY FOR THE DUAL GIVEN THE CHECK POLY
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)
reciprocal of a poly
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] .
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
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
Construct a generator matrix for the binary
n = 7 cyclic code C with generator polynomial
1 + x + x^3
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
Construct a PCmatrix for the binary
n = 7 cyclic code C with generator polynomial
1 + x + x^3
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!
Let C, C′ be cyclic codes. What can you say
about their intersection?
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))
. If C is cyclic and C′ is an equivalent code, is C ′
necessarily cyclic?
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.
