CT 2

V.J.T.
I
B.Tech.(ExTc)
Sub: Coding Theory
Sem-VIII
Course Instructor
Dr. D. P. Rathod
PhD(Technology)Electronics Engg.
Dept. of Electronics Engineering
[email protected]
Mob-9819003515
Error Correcting Codes
➢ Block diagram of modern digital communication
system
➢ Error correcting codes/coding theory/ Channel
coding
➢ Hamming code(n, k)/Cyclic code(n,k)
➢ Code rate and valid code set
➢ Properties of matrix
➢ Modern linear abstract Algebra-
➢ Groups
➢ Fields
➢ Vector spaces
Code rate and code word set
➢ Code rate r = k/n
➢ Valid code word set C
➢ For (n, k) linear block code,

2k , are the set of valid code word of length n bits
➢ These 2k Code words are obtained by taking linear

combination of rows of a G matrix and mod-2
operation
➢ Rows of G matrix should be linearly independent

Properties of Matrices
➢ Design of (n, k) code requires generator matrix
G or generator polynomial for encoding at
transmitter side
➢ Parity check Matrix H or parity check polynomial

at receiver side in order to decode/ recover the
original data
➢ The required matrices and polynomials should

have important properties as follows-
Matrix properties
➢The rows and columns of both matrices
should be linearly independent
➢No two or more number of columns or rows

should be equal
➢Both Matrices should be in systematic form
➢No rows or columns should have all elements

zero’s
Modern Linear Abstract Algebra
➢ Much of this work for ECC is mathematics in nature, requires an
extensive background in modern algebra theory to understand.
➢ Brief Introduction of Modern linear abstract algebra
➢ Group
➢ Fields
➢ Vector Spaces
➢ Irreducible polynomial P(X) of degree m
➢ Primitive Polynomial P(X) of degree m
➢ Extension of Field GF( 2m )
➢ factorization of Xn + 1 over GF(2) 6

➢ Cyclic codes are constructed using polynomial form
hence easy to implement using simple shift registers
and logic gates, switches etc.
➢ In cyclic codes generator polynomial of degree (n-k )

is required to construct a code (channel Encoding)
➢ The generator polynomial is a factor of Xn + 1 over

GF(2)={0,1}
➢ Where, n=2m -1 and m is degree of irreducible

polynomial
Systematic structure of G and H
Generator matrix ‘G’ is
Gk x n = [Ik P k x (n-k)]
where,
G is a generator matrix of size k×n
I is a identity matrix of size k×k
P is a parity bit matrix of size k×(n-k)
The ‘G’ matrix is derived from Parity Check matrix ‘H’,
where ,
H(n-k)x n = [PT In-k ]
Relation between matrix G and H is such that
H.GT = 0
➢As relation between matrix G and H is such
that
H.GT = 0 …….1
➢All code words C are generated by using G
matrix, hence G can be replaced by C in eq.1
➢H.CT =0 mod-2 operation
➢Let c = r
➢ r.HT =0 or H.rT = 0 mod-2 operation,
➢ This is the condition to check validity of
received code words
➢ Groups G
➢Let G be a set of elements.
➢A binary operation * on G is rule that assigns to

each pair of elements a and b , third element
c = a* b in G.
➢Then we say that G is closed under *.
➢Hence, the set of integer is closed under real

addition.
10
➢ Groups :
➢ Example
➢ The set of all integer is a commutative group under real addition.
➢ In this case, the integer 0 is the identity element, & the integer –i is the
inverse of integer i.
➢ The set of all rational numbers excluding zero is a commutative group under
real multiplication.
➢ The integer 1 is the identity element with respect to real multiplication, & the
rational number 𝑏Τ𝑎 is the multiplicative inverse of 𝑎Τ𝑏.
➢ Groups with finite numbers of elements do exist, as we shall in the next
example.
➢ The number of elements in a group is called as order of the group.
➢ A group of finite order is called a finite group.
12
➢ Group:
➢ Example :
Consider the set of two integers 𝐺 = 0,1 . Let us define a binary
operation, denoted by ⊕, on G as follows
➢ Solution
0 ⊕ 0 = 0. 0⊕1 = 1 1⊕0 = 1 1⊕1 = 0
This binary operation is called modulo-2 addition. The set 𝐺 = 0,1 is a

group under modulo-2 addition. It follows from the definition of
modulo-2 addition ⊕that G is closed under ⊕, & ⊕is commutative. The
inverse of 0 is itself, and the inverse of 1 is also itself, thus G together
with ⊕is a commutative group.
➢ For any positive integer m, it is possible to construct a group of order m
under a binary operation that is very similar to real addition.
13
➢ Fields:
➢ Let F be a set of elements on which two binary operations called addition
“+” & multiplication “.”are defined.
➢ The set F together with the two binary operations “+” & “.” ,Is a field if
the following conditions are satisfied:
i. F is commutative group under addition +.
ii. The identity element with respect to addition is called the zero
elements or
iii. The additive identity of F & is denoted by 0.
iv. The set of nonzero elements in F is a commutative group under
multiplicative identity of F and is denoted by 1.
v. Multiplication is distributive over addition; that is, for any three
elements a, b, & c in F
𝑎. 𝑏 + 𝑐 = 𝑎. 𝑏 + 𝑎. 𝑐
14
➢ Fields:
➢ Hence, a field consist of at least two elements, the

additive and multiplicative identity.
➢ The number of elements in field is called as order

of the field.
➢ A field with a finite number if elements is called a

finite field.
15
➢ Fields
➢ In a field the additive inverse of an element a is

denoted by –a, and the multiplicative inverse of a
is denoted by a-1.
➢ For Example:
➢ GF(2) = {0, 1} is the smallest field of Galois Field

of 2 element.
➢ Vector Spaces Vn : Let V be a set of elements on which a
binary operation called addition, +, is defined.
➢ Let F be a field. GF(2)={0,1}
➢ A multiplication operation by “.”, between the elements in

F and elements in V is also defined.
➢ The set V is called a vector space over the field F if it

satisfies the following conditions:
➢ V is Commutative under addition. (u+v = v+u)
➢ For any element a in F and any element v in V, a.v is an

element in V.
➢ Vector Spaces Vn :
➢ Let n =5. the vector space V5 of all 5-tuples over GF(2) consist of
the following set of 32 vectors which are distinct :
00000 00001 00010 00011
00100 00101 00110 00111
01000 01001 01010 01011
01100 01101 01110 01111
10000 10001 10010 10011
10100 10101 10110 10111
11000 11001 11010 11011
11100 11101 11110 11111
➢ These sets are linear combinations of basis vector or spanning

set ( 1 0 0 0 0, 0 1 0 0 0, 0 0 1 0 0,0 0 0 1 0, 0 0 0 0 1)
18
➢ Addition of Vectors, Let 𝒗𝟏 = (𝟏 𝟎 𝟏 𝟏 𝟏)& 𝒗𝟐 = (𝟏 𝟏 𝟎 𝟎 𝟏)
➢ The vector sum of 𝒗𝟏 &𝒗𝟐 is
10111 + 11001 = 1 + 1,0 + 1,1 + 0,1 + 1 = 01110 .
➢ Scalar multiplication with vectors, Let “0” & “1” are the scalar
0. 11010 = 0.1,0.1,0.0,0.1,0.0 = 00000 ,
1. 11010 = 1.1,1.1,1.0,1.1,1.0 = 11010 ,
➢ The vector space of all n-tuples over any field F constructed in a similar
manner.
➢ However, we are mostly concerned with the vector space of all n-
tuples over GF(2) or over an extension field of GF(2) [e.g. GF(2m)].
➢ Because V is a vector space over a field F, it may happen that subset S
of V is also a vector space over F.
➢ Such a subset is called a subspace of V.
19
➢ Let S be a nonempty subset of a vector space V over a field
F then, S is a subspace of V if the following conditions are
satisfied;
➢ For any two vectors u & v in S, u + v also a vector in S.
➢ For any element a in F & any vector u in S, a.u is also in S.
➢ Consider the vector space of all 5 tuple over GF(2) the set
00000 , 00111 , 11010 , 11101
20
➢ Linear Combination of vectors
➢ Let 𝑣1 , 𝑣2 , ⋯ , 𝑣𝑘 be k vectors in vector space V over a field F, let
𝑎1 , 𝑎2 , ⋯ , 𝑎𝑘 be k scalars from F. The sum of product of scalar and
vector that is
𝑎1 𝑣1 + 𝑎2 𝑣2 + ⋯ + 𝑎𝑘 𝑣𝑘
➢ Clearly, the sum of two linear combinations of 𝑣1 , 𝑣2 , ⋯ , 𝑣𝑘 .

𝑎1 𝑣1 + 𝑎2 𝑣2 + ⋯ + 𝑎𝑘 𝑣𝑘 + 𝑏1 𝑣1 + 𝑏2 𝑣2 + ⋯ + 𝑏𝑘 𝑣𝑘
= 𝑎1 + 𝑏1 𝑣1 + 𝑎2 + 𝑏2 𝑣2 + ⋯ + 𝑎𝑘 + 𝑏𝑘 𝑣𝑘
➢ Scalar Product :
➢ The product of scalar c in F & a linear combination of 𝑣1 , 𝑣2 , ⋯ , 𝑣𝑘 .
𝑐 . 𝑎1 𝑣1 + 𝑎2 𝑣2 + ⋯ + 𝑎𝑘 𝑣𝑘 = 𝑐. 𝑎1 𝑣1 + 𝑐. 𝑎2 𝑣2 + ⋯ + 𝑐. 𝑎𝑘 𝑣𝑘
21
➢ Statement:
➢ Let 𝑣1 , 𝑣2 , ⋯ , 𝑣𝑘 be k vectors in vector space over a field F. The set of

all linear combinations of 𝑣1 , 𝑣2 , ⋯ , 𝑣𝑘 forms a subspace of V.
➢ Proof:
➢ A set of vectors 𝑣1 , 𝑣2 , ⋯ , 𝑣𝑘 in a vector space V over a field F said to

be linearly dependent if and only if there exist k scalars 𝑎1 , 𝑎2 , ⋯ , 𝑎𝑘
from field F, not all zero, such that
𝑎𝑘 𝑣1 + 𝑎𝑘 𝑣2 + ⋯ + 𝑎𝑘 𝑣𝑘 = 0
➢ A set of vectors 𝑣1 , 𝑣2 , ⋯ , 𝑣𝑘 is said to be linearly independent if it

is not linearly dependent.
22
➢ That is 𝑣1 , 𝑣2 , ⋯ , 𝑣𝑘 are linearly independent. If and only if
𝑎𝑘 𝑣1 + 𝑎𝑘 𝑣2 + ⋯ + 𝑎𝑘 𝑣𝑘 ≠ 0
➢ Unless 𝑎1 = 𝑎2 = ⋯ = 𝑎𝑘 = 0.
➢ Example:
➢ Consider the vector space of all 5-tuple over GF(2) the linear
combinations of 00111 & 11101 are
0. 00111 + 0. 11101 = 00000

0. 00111 + 1. 11101 = 11101
1. 00111 + 0. 11101 = 00111
1. 00111 + 1. 11101 = 11010
Set of vectors are linearly independent 23
➢What is Basis vector for Vn?
➢ Basis Vector
➢ In any vector space or subspace there exist at least one set B of linearly
independent vectors that span the space.
➢ This is called as a basis (or base)of the vector space.
➢ The number of vectors in a basis of a vector space is called as the

dimension of the vector space.
➢ Consider a vector space Vn of all n-tuples over GF(2).
➢ Let us form the following n, n-tuples:

𝑒0 = 1, 0, 0, 0, ⋯ , 0, 0
𝑒1 = 0, 1, 0, 0, ⋯ , 0, 0
⋮
𝑒𝑛−1 = 0, 0, 0, 0, ⋯ , 0, 1 25
Linearly independent hence form all vectors in vector space Vn
➢ Where the n-tuple ei has only one nonzero component at the ith position.
➢ Then every n-tuple 𝑎0 , 𝑎1 , 𝑎2 , ⋯ , 𝑎𝑛−1 in Vn can be expressed as a linear

combination of 𝑒0 , 𝑒1 , ⋯ , 𝑒𝑛−1 as follows:
𝑎0 , 𝑎1 , 𝑎2 , ⋯ , 𝑎𝑛−1 = 𝑎0 𝑒0 + 𝑎1 𝑒1 + 𝑎2 𝑒2 + ⋯ + 𝑎𝑛−1 𝑒𝑛−1 .
➢ Therefore 𝑒0 , 𝑒1 , ⋯ , 𝑒𝑛−1 span the vector space Vn of n-tuple over GF(2).
➢ We also see that 𝑒0 , 𝑒1 , ⋯ , 𝑒𝑛−1 are linearly independent.
➢ Hence, they form a basis for Vn, & dimension of Vn is n.
➢ If k < n & 𝑣1 , 𝑣2 , ⋯ , 𝑣𝑘 are k linearly independent vectors in Vn, then all

the linear combinations of 𝑣1 , 𝑣2 , ⋯ , 𝑣𝑘 of the form, 𝒖 = 𝑐1 𝒗1 + 𝑐2 𝒗2 +
⋯ + 𝑐𝑛 𝒗𝑛 form a k- dimensional subspace S of Vn.
26
27
➢ Statement:
➢ Let S be a k-dimensional subspace of the vector space Vn of n-tuple
over GF(2).
➢ The dimension of its null space Sd is in n-k. in other words ,
𝑑𝑖𝑚 𝑆 + dim 𝑆𝑑 = 𝑛
➢ Irreducible polynomial:
➢ For a polynomial 𝑓(𝑋) over 𝐺𝐹(2), if polynomial has an even number
of terms, it is devisable by 𝑋 + 1.
➢ A polynomial 𝑝(𝑋) over 𝐺𝐹(2) of degree m is said to be irreducible
over 𝑝(𝑋). If it is not divisible by any polynomial over 𝐺𝐹(2) of degree
less than m but greater than zero.
28
Modern Abstract linear Algebra
➢Irreducible polynomial P(X) of degree m, over GF={0,1}
➢Primitive elements
➢Primitive Polynomial P(X) of degree m
➢Extension of Field GF( 2m ) over GF={0,1}
➢ factorization of Xn + 1 over GF(2)
➢ n = 2m - 1
Modern Abstract linear Algebra
➢ What is irreducible polynomial P(X) of degree m,

over GF={0,1}
➢ What is Primitive element
➢ What is Primitive Polynomial P(X) of degree m
➢ What is Extension of Field GF( 2m ) over GF={0,1}
➢ what is factorization of Xn + 1 over GF(2)
➢ where, n = 2m - 1
Irreducible Polynomial P(X) of degree
m, over GF={0,1}
➢Example 1, P(X)=X3 + X + 1 over GF(2)={0,1}
➢P(0)=03 + 0 + 1
=1
➢P(1)=13 + 1 + 1
=1
Example 2
Primitive element α and Primitive
Polynomial P(X) of degree m
➢ Theorems:
➢ 1.If using powers of a single element α , all elements
of the set are obtained except zero element then a
element α is called as primitive elements
➢ 2. An irreducible Polynomial P(X) of degree m is said to
be primitive, if it divides the polynomial Xn + 1 over
GF(2), where n is the smallest integer value and
➢ where, n = 2m – 1
➢ Check whether polynomial P(X)=X3 + X + 1 over GF(2)={0,1} is
primitive or not
➢ Verify whether the set G ={0,1,2,3,4} under mod
5 operation is a group or not
➢ Give any one example of finite group
➢ Verify whether the set F ={0,1,2,3,4,5,6} under
mod-7 is a field or not
➢ Give one example of finite field
➢ Write the basis vector for the vector space V4
over GF(2)
➢ Verify P(X)=X4 + X + 1 is primitive or not over
GF(2)
what is Xn + 1 over GF(2)
➢Xn + 1 over GF(2) is a product of all n elements

from extension field GF(2m)
➢After factorization of polynomial Xn + 1 over
GF(2)
➢The degree n-k polynomial is called as
generator polynomial
➢The degree k polynomial is called as parity
check polynomial
➢Hence Xn + 1 = g(x).h(X)
➢Verify whether the set of vectors given below
are linearly dependent or independent
➢1. (10110) , (01001), & (11111)
➢2. (10110) , (01001), & (11011)
➢Write the program to verify whether given set
of vectors are linearly dependent
Modern Algebra…
➢ Example:
➢ The vectors (10110) , (01001), & (11111) are linearly dependent. Since
1 . 10110 + 1. 01001 + 1. 11111 = (00000);
➢ However, (10110) , (01001), & (11111) are linearly independent.
➢ All eight combinations of these vectors are given here:

0. 10110 + 0. 01001 + 0. 11111 = 00000 ,
0. 10110 + 0. 01001 + 1. 11111 = 11011 ,
0. 10110 + 1. 01001 + 0. 11111 = 01001 ,
0. 10110 + 1. 01001 + 1. 11111 = 10010 ,
1. 10110 + 0. 01001 + 0. 11111 = 10110 ,
1. 10110 + 0. 01001 + 1. 11111 = 01101 ,
1. 10110 + 1. 01001 + 0. 11111 = 11111 ,
1. 10110 + 1. 01001 + 1. 11111 = 00100 ,
A set of vectors is said to span a vector space V if every vector in V is a linear combination of
vectors in set .
36
➢ Irreducible polynomial P(X):

➢ Among the four polynomials of degree 2, 𝑋 2 , 𝑋 2 +1, & 𝑋 2 + 𝑋 are
not irreducible, since they are divisible by X or X + 1;
➢ However, 𝑋 2 + 𝑋 + 1 does not have either 0 or 1 as a root & so is not

divisible by any polynomial of degree 1.
➢ Therefore 𝑋 3 + 𝑋 + 1 is not divisible by 𝑋 𝑜𝑟 𝑋 + 1.

➢ Therefore, 𝑋 2 + 𝑋 + 1 is an irreducible polynomial of degree 2.
➢ The polynomial 𝑋 3 + 𝑋 + 1 is an irreducible polynomial of degree 3.
➢ 𝑋 3 + 𝑋 + 1 is neither divisible by any polynomial of degree 1, nor any

polynomial of degree 2 or higher except itself
37
Primitive polynomial
➢ An irreducible polynomial P(X) of degree m is said to be primitive if the
smallest positive integer n for which p(X) divides Xn+1 where, n=2m-1
➢ For Example Consider P(X)= 𝑋 3 + 𝑋 + 1 is irreducible polynomial over
GF(2)
➢ Primitive Polynomial help us to construct the Extension field of irreducible

polynomial P(X) where its roots exist.
38
Primitive Polynomial
➢Verify whether irreducible polynomial

P(X)= X4 + X3 + X2 + X + 1 over GF(2)={0,1} is
primitive or not
➢ P(X), must divide X15 + 1 over GF(2)={0,1}

➢Verify whether irreducible polynomial

P(X)= X4 + X3 + X2 + X + 1 over GF(2)={0,1} is
primitive or not
➢ P(X), must divide X15 + 1 over GF(2)={0,1}
➢ Also, check whether P(X) divides X 5 + 1

X4+X3+X2+X+1) X15 + 1 ( X11 + X10 ...

X15 + X14 + X13 + X12 + X11
------------------------------------
X14 + X13 + X12 + X11 +1
.
.
--------------------------------
0
➢ X4+X3+X2+X+1) X5 + 1 (X + 1
- X5 + X4 + X 3 + X2 + X
-----------------------------
X4+ X3+ X2 + X +1
- X4+ X3+ X2 + X +1
----------------------------
0
Hence, P(X)= X4 + X3 + X2 + X + 1 is irreducible
polynomial over GF(2) but not primitive
Primitive elements
➢ Find the primitive elements from the set
G={0,1,2,3,4} mod 5 operation
➢ Let consider α=2
➢ 20 = 1 mod 5 operation
➢ 21 = 2
➢ 22 = 4
➢ 23 = 8 mod5=3
➢ 24 = 16 mod 5=1 (repeating)
➢ All elements except zero are obtained using
powers of element 2
➢ Hence element 2 from set is primitive
Primitive elements
➢ 31 =3
➢ 32 = 9 mod5=4
➢ 33 = 27 mod5= 2
➢ All elements except zero are not obtained using
powers of element 3
➢ Hence element 3 from set is not primitive
Primitive elements
➢ 41 = 4
➢ 42 = 16 mod5 = 1
➢ 43 = 64 mod5=4
➢ All elements except zero are obtained using
powers of element 4
➢ Hence element 4 from set is primitive
Multiplicative Inverse
➢What is additive identity
➢What is multiplicative identity
➢What is order of element
➢Find the multiplicative inverse of each
element except zero from the set
G={0,1,2,3,4} under mod 5 operation
➢Find the additive inverse of each elements
from the set G={0,1,2,3,4} under mod 5
operation
➢ Additive identity is 0
➢ Multiplicative identity is 1
➢ Order of element 2 is 4 ( 24 = mod 5 =1)(i.e.2n = mod n =1)
➢ Find the multiplicative inverse of each element except zero
from the set G={0,1,2,3,4} under mod 5 operation
➢ 2.3= 6 mod 5 =1
➢ Hence 2 is multiplicative inverse of 3 and vice versa
➢ 4.4=16 mod 5=1
➢ Hence 4 is multiplicative inverse of 4
➢ 1.1=1
➢ Hence 1is multiplicative inverse of 1
➢ Multiplicative inverses of each elements except zero are
obtained
➢ Find the Additive inverse of each element from
the set G={0,1,2,3,4} under mod 5 operation
➢ 0+0= 0 mod 5 =0
➢ Hence 0 is additive inverse of 0 and vice versa
➢ 1+4=mod 5=0
➢ 2+3=5 mod 5=0
➢ Additive inverses of each elements are obtained

CT 2

Uploaded by

Copyright:

Available Formats

CT 2

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

CT 2

Uploaded by

Copyright:

Available Formats

V.J.T.

➢ Valid code word set C

➢ For (n, k) linear block code,

➢ These 2k Code words are obtained by taking linear

➢ Rows of G matrix should be linearly independent

➢ Parity check Matrix H or parity check polynomial

➢ The required matrices and polynomials should

➢No two or more number of columns or rows

➢Both Matrices should be in systematic form

➢No rows or columns should have all elements

➢ Brief Introduction of Modern linear abstract algebra

➢ Irreducible polynomial P(X) of degree m

➢ Primitive Polynomial P(X) of degree m

➢ Extension of Field GF( 2m )

➢ factorization of Xn + 1 over GF(2) 6

➢ In cyclic codes generator polynomial of degree (n-k )

➢ The generator polynomial is a factor of Xn + 1 over

➢ Where, n=2m -1 and m is degree of irreducible

➢A binary operation * on G is rule that assigns to

➢Then we say that G is closed under *.

➢Hence, the set of integer is closed under real

This binary operation is called modulo-2 addition. The set 𝐺 = 0,1 is a

➢ Hence, a field consist of at least two elements, the

➢ The number of elements in field is called as order

➢ A field with a finite number if elements is called a

➢ In a field the additive inverse of an element a is

➢ GF(2) = {0, 1} is the smallest field of Galois Field

➢ Let F be a field. GF(2)={0,1}

➢ A multiplication operation by “.”, between the elements in

➢ The set V is called a vector space over the field F if it

➢ V is Commutative under addition. (u+v = v+u)

➢ For any element a in F and any element v in V, a.v is an

➢ These sets are linear combinations of basis vector or spanning

➢ For any two vectors u & v in S, u + v also a vector in S.

➢ For any element a in F & any vector u in S, a.u is also in S.

➢ Clearly, the sum of two linear combinations of 𝑣1 , 𝑣2 , ⋯ , 𝑣𝑘 .

➢ Let 𝑣1 , 𝑣2 , ⋯ , 𝑣𝑘 be k vectors in vector space over a field F. The set of

➢ A set of vectors 𝑣1 , 𝑣2 , ⋯ , 𝑣𝑘 in a vector space V over a field F said to

➢ A set of vectors 𝑣1 , 𝑣2 , ⋯ , 𝑣𝑘 is said to be linearly independent if it

0. 00111 + 0. 11101 = 00000

➢ This is called as a basis (or base)of the vector space.

➢ The number of vectors in a basis of a vector space is called as the

➢ Consider a vector space Vn of all n-tuples over GF(2).

➢ Let us form the following n, n-tuples:

➢ Then every n-tuple 𝑎0 , 𝑎1 , 𝑎2 , ⋯ , 𝑎𝑛−1 in Vn can be expressed as a linear

➢ We also see that 𝑒0 , 𝑒1 , ⋯ , 𝑒𝑛−1 are linearly independent.

➢ Hence, they form a basis for Vn, & dimension of Vn is n.

➢ If k < n & 𝑣1 , 𝑣2 , ⋯ , 𝑣𝑘 are k linearly independent vectors in Vn, then all

➢Irreducible polynomial P(X) of degree m, over GF={0,1}

➢Primitive Polynomial P(X) of degree m

➢Extension of Field GF( 2m ) over GF={0,1}

➢ factorization of Xn + 1 over GF(2)

➢ What is irreducible polynomial P(X) of degree m,

➢Xn + 1 over GF(2) is a product of all n elements

➢ However, (10110) , (01001), & (11111) are linearly independent.

➢ All eight combinations of these vectors are given here:

➢ Irreducible polynomial P(X):

➢ However, 𝑋 2 + 𝑋 + 1 does not have either 0 or 1 as a root & so is not

➢ Therefore 𝑋 3 + 𝑋 + 1 is not divisible by 𝑋 𝑜𝑟 𝑋 + 1.