6 Optical Coding Theory with Prime
Definition 1.6
Aprimitiveelement
α
is an element in a finite field that can generate every element,
except zero, in the finite field by successive powers of
α
.
Theorem 1.2
The first p −1successivepowersofaprimitiveelementofGF(p) generate all the
p −1nonzeroelementsofGF(p) for a positive integer p.Eachprimitiveelementis
an element of maximum order, which is equal to p −1inGF(p).
Proof Assume that
α
is a primitive element of GF(p) and has an order of p −1. Let
α
i
=
α
j
and 0 < j < i < p.Dividing
α
j
on both sides results in
α
i−j
= 1 (mod p),
which violates the assumption of
α
having the order of p −1becausei − j is always
less than p −1. So,
α
i
must all be distinct for all i ∈ [1, p −1].Tomaintaintheorder
of p −1,
α
i
&= 0 (mod p) is needed for all i ∈ [1, p −1].Otherwise,thesuccessive
powers {
α
i+1
,
α
i+2
,...,
α
p−1
} will b e all 0s. So, the smallest nonz ero power of
α
that gives
α
i
= 1mustbei = p −1. Because p −1isalsothenumberofnonzero
elements in GF(p),
α
has the maximum order.
By observation, the possible orders of nonzero elements in GF(p) are th e diviso r s
of p −1. For example, as p −1 = 6inGF(7),thepossibleordersoftheelementsin
GF(7) are 1, 2, 3, and 6. Of cour se, the elemen t “1” always has order 1 . The suc-
cessive powers of the element “2” ar e 2
1
= 2, 2
2
= 4, and 2
3
= 2 ×4 = 1 (mod 7).
So, “2” has the order of 3 and is not a primitive element of GF(7). The element “3”
is a primitive element of GF(7) because it has the order of 6 as 3
1
= 3, 3
2
= 2,
3
3
= 3 ×2 = 6, 3
4
= 3 ×6 = 4, 3
5
= 3 ×4 = 5, and 3
6
= 3 ×5 = 1 (mod 7).Ap-
plying a similar successive-power test to the elements “4,” “5,” and “6,” the orders of
3, 6, and 2 are obtained, respectively. So, “3” and “5” are the primitive elements of
GF(7).
Theorem 1.3
For a given positive integer i,thep −1productsof
α
i
α
j
are all distinct in GF(p) for
all j ∈ [1, p −1],wherep is a positive integer.
Proof Accord ing to Theorem 1.2, every
α
p
can be factorized out of the pr oduct
Fundamental Materials and Tools 7
α
i
α
j
because
α
p
=
α
0
= 1. This factorization is equivalent to the application of a
modulo-p addition onto the exponent of
α
i+ j
and leaves the same set of exponents
of
α
as that in Theorem 1.2.
TABLE 1.1
Multiplication Table of GF(
(
(p)
)
),WrittenintheFormofaPrimitiveElement
α
α
α
× 0
α
0
α
1
α
2
···
α
p−1
00000··· 0
α
0
0
α
0
α
1
α
2
···
α
p−1
α
1
0
α
1
α
2
α
3
···
α
0
α
2
0
α
2
α
3
α
4
···
α
1
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
α
p−1
0
α
p−1
α
0
α
1
···
α
p−2
According to Theorems 1.2 and 1.3, a p rimitive element
α
of GF(p) can be used
to construct a multiplication table of GF(p),asshowninTable1.1.Forexample,by
substituting
α
in the table with a primitive element “2” of GF(5), a multiplication
table of GF(5) is constructed as
× 01234
0 00000
1 01234
2 02413
3
03142
4 04321
after some row- and column-rearrangement.
1.2 VECTOR SPACE
A vector space,animportantconceptcloselyrelatedtolinearalgebraandmatrix
theory, is a collection of vectors that carry the same but certain properties [4,5]. Two
classical examples of vector space are the two-dimensional and three-dimensional
Euclidean spaces in geometry, in which a vector v is interpreted as a directed line and
written as an ordered set of Cartesian coordinates (v
x
,v
y
) and (v
x
,v
y
,v
z
),respectively.
The coordinates are ob tained from the projections of v onto the x, y,andz axes.
The concept of vector space over a finite field under modulo addition and multi-
plication is of particular interest in optical coding theorybecauseone-dimensional
optical codes can be represented as vectors over a finite field.
8 Optical Coding Theory with Prime
Definition 1.7
AvectorspaceV over a field F contains a set of elements, called vectors,inwhich
each vector consists o f an or d er ed set of elements in F,calledscalars,andtwo
operators—vector ad d ition and scalar multiplication—defined with the following
properties:
1. Closure. If v
1
and v
2
are vectors in V and c is a scalar in F,thesumv
1
+ v
2
and the product c v
1
are also vectors in V .
2. Additive Identity and Inverse. If v is a vector in V and
v + 0 = 0 + v = v
v +(−v)=(−v)+v = 0
then “0”istheuniqueadditiveidentityvector,calledzerovector,inV ,and
−v is its unique additive inverse vector in V .
3. Commutativity. If v
1
and v
2
are vectors in V ,thecommutativelawimplies
that
v
1
+ v
2
= v
2
+ v
1
4. Associativity. If v is a vector in V ,andc
1
and c
2
are scalars in F,theasso-
ciative law implies that
(c
1
c
2
)v = c
1
(c
2
v)
5. Distributivity. If v
1
and v
2
are vectors in V ,andc
1
and c
2
are scalars in F,
the distributive law implies that
c
1
(v
1
+ v
2
)=c
1
v
1
+ c
1
v
2
(c
1
+ c
2
)v
1
= c
1
v
1
+ c
2
v
1
6. Multiplicativity. If v is a vector in V , c is a scalar in F,and“0”and“1”
are the add itive and multiplicative identity elements in F,respectively,then
c0 = 0 ,0v = 0,and1v = v.
Definition 1.8
An n-tuple over a field F is an ordered set of n elemen ts, denoted by
(v
1
,v
2
,...,v
i
,...,v
n
),wherev
i
is an element in F.Thecollectionofthesen-tuples
forms a vector space F
n
.
Fundamental Materials and Tools 9
If (u
1
,u
2
,...,u
i
,...,u
n
) an d (v
1
,v
2
,...,v
i
,...,v
n
) are n-tuples over a field F and
c is a scalar of F,theirvectoradditionproduces
(u
1
,u
2
,...,u
i
,...,u
n
)+(v
1
,v
2
,...,v
i
,...,v
n
)
=(u
1
+ v
1
,u
2
+ v
2
,...,u
i
+ v
i
,...,u
n
+ v
n
)
and their scalar multiplication produces
c(u
1
,u
2
,...,u
i
,...,u
n
)=(cu
1
,cu
2
,...,cu
i
,...,cu
n
)
whereas u
i
+ v
i
and cu
i
are also elements in F.
Definition 1.9
The inner product of n-tuples u =(u
1
,u
2
,..., u
i
,...,u
n
) and v =(v
1
,v
2
,...,v
i
,...,v
n
)
over a field F is defined as
u ·v =(u
1
,u
2
,...,u
i
,...,u
n
) ·(v
1
,v
2
,...,v
i
,...,v
n
)
= u
1
v
1
+ u
2
v
2
+ ···+ u
i
v
i
+ ···+ u
n
v
n
which results in a scalar in F,whereu
i
, v
i
,andu
i
v
i
are elements in F.
In addition, the inner products of n-tuples u, v,andw over F produce
u ·v = v ·u
(cu)·v = c(u ·v)
w·(u + v )=(w ·u)+(w ·v)
for a scalar c in F,duetothepropertiesofvectorspaceinDefinition1.7.
Two n-tuples over F are said to be orthogonal if their inner product is 0. A nonzero
n-tuple over F can be or tho gonal to itself.
1.2.1 Linear Operations in Vector Space over a Field
To construct and study the properties of one-dimensional optical codes, linear oper-
ations in vector space over a finite field are needed. Such linear oper ations resemble
the usual operations in solving simultaneous linear equations, but are now performed
in a finite field.
Definition 1.10
If {v
1
,v
2
,...,v
i
,...,v
m
} are vectors in a vector space V over a field F and
{a
1
,a
2
,...,a
i
,...,a
m
} are scalars in F,theform
a
1
v
1
+ a
2
v
2
+ ···+ a
i
v
i
+ ···+ a
m
v
m
10 Optical Coding Theory with Prime
is called a linear combination of these vectors.
These vectors are said to be linearly dependent if
a
1
v
1
+ a
2
v
2
+ ···+ a
i
v
i
+ ···+ a
m
v
m
= 0
for {a
1
,a
2
,...,a
i
,...,a
m
} not all equal to 0s; otherwise, they are said to be linearly
independent.
If there exists a set of linearly independent vectors that cangenerateeveryvector
in V by means of linear combinations, these linearly independentvectorsaresaidto
span V and f o r m a basis of V .Ifthenumberoftheselinearlyindependentvectorsis
finite, V is called a finite-dimensional vector space and its dimension is also equal to
this number.
By definition, any set of linearly independent vectors that span V cannot contain
the zero vector 0 ;otherwise,theyarelinearlydependent.Also,linearlyindependent
vectors cannot be obtained by any linear combination of othervectorsinV .
There exists at least o ne set of linearly independent vectorsthatcanformabasis
of a vector space. For example, a set of linearly independent vectors, in which each
vector contains a single 1 as one element and 0s as the remaining elements, is a
natural choice for a basis. These vectors are called unit vectors and ther e ar e n of
them for an n-dimensional vector space.
For example, the two unit vectors (0,1) and (1,0),whichresemblethetwoCarte-
sian coordinate axes in two-dimensional Euclidean space, form a basis of a two-
dimensional vector space V
2
over GF(2) with four distinct vectors:
(0,0)=0(0,1)+0(1, 0)
(0,1)=1(0,1)+0(1, 0)
(1,0)=0(0,1)+1(1, 0)
(1,1)=1(0,1)+1(1, 0)
Unit vectors are not the only basis vectors for a vector space.Forexample,(0,1)
and (1,1) can also form a basis of V
2
.Nevertheless,abasisconsistingofunitvectors
only is called a normal orthogonal or orthonormal basis.
Definition 1.11
AvectorspaceV
$
is called a subspace of another vector space V if V contains all
vectors of V
$
and these vectors follow the vector-addition and scalar-multiplication
properties of V .
By definition, it is only necessary to show closure under vector addition and scalar
multiplication in order to verify the existence of a subspace, whereas other properties
of a vector space are implied. Closure under scalar multiplication gu ar an tees that the
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.