1
Fundamental Materials
and Tools
Modern algebra [1–5] provides mathematical concepts and tools fundamental to the
study of Optical Codin g Theory.Thetheoryfindsapplicationsincoding-basedop-
tical systems and networks, for example, involving optical code-division multiple
access (O-CDMA) and multiplexing [6–22]. Var iou s families of the prime codes
studied in this book are based on the arithmetic of finite or Galois fields of some
prime numbers [1, 2, 21–23].
This chapter covers the essential co ncepts and algebraic tools that are useful for
understanding the subject matter in this book. It begins withareviewofGaloisfields,
followed by vector and matrix theories. Imp ortant code parameters, such as Ham-
ming weight and distance, correlation functions, and cardinality upper bound, that
characterize optical co d es are defined. Afterward, the concept of Markov ch ains is
studied [24,25]. Algebraic tools to analyze the performances of optical cod es are also
developed. In particular, Gaussian approximation is a quick, utilitarian tool for per-
formance analysis, especially in the absence of structural information of the optical
codes und er study [21 , 22 , 24 –26]. Mor e accurate combin atorial tools for analyzing
code per formances with soft-limiting and hard-limiting receivers, and with and with-
out the classical chip-synchronous assumption, are also formulated [27 –37]. Finally,
the definition of spectral efficiency, another figure of merit for comparing optical
codes, is introdu ced [38–43].
1.1 GALOIS FIELDS
Optical coding theory relies on modern algebra, which uses a different arithmetic
system, rather than the familiar real and complex number systems. A field in modern
algebra consists of elements defined with four mathematical operations: addition,
subtraction, multiplication, and division. If the number ofelementsinafieldisfinite,
this field is called a finite field or Ga lois field,inthememoryof
´
Evariste Galois
(1811–1832) [1–3]. Because optical coding theory, especially with prime codes, is
usually based on the principles of Galois fields of prime numbers, the fundamentals
of fields in modern algebra are first reviewed before proceeding with the rest of the
book.
Definition 1.1
AfieldF contains a set of elements and four op er ato r s—addition (+),subtraction
(−),multiplication(×),anddivision(÷)—defined with the following properties:
1
2 Optical Coding Theory with Prime
1.
Closure. If a and b are elements in F,thesuma + b and the product a ×b
are also elements in F.
2. Additive Identity and Inverse. If a is an element in F and
a + 0 = 0 + a = a
a +(−a)=(−a)+a = 0
then “0” is the unique additive identity element, called zero,inF,and−a
is its unique additive inverse in F.
3. Multiplicative Identity and Inverse. If a is a nonzero element in F and
a ×1 = 1 ×a = a
a ×a
−1
= a
−1
×a = 1
then “1” is the unique multiplicative identity element, called unity,inF,
and a
−1
is its unique multiplicative inverse in F.
4. Commutativity. If a and b ar e elemen ts in F,thecommutativelawimplies
that
a + b = b + a
a ×b = b ×a
5. Associativity. If a, b,andc are elements in F,theassociativelawimplies
that
a +(b + c)=(a + b)+c
a ×(b ×c)=(a ×b) ×c
6. Distributivity. If a, b ,andc are elements in F,thedistributivelawimplies
that
(a + b) ×c =(a ×c)+(b ×c)
7. Subtractibility. If a an d b are elements in F,thenthesubtractiona −b im-
plies that
a −b = a +(−b)
due to the existence of the additive inverse − b.
8. Divisibility. If a is an element in F and b is a nonzero element in F,then
the division a ÷b implies that
a ÷b = a ×b
−1
due to the existence of the multiplicative inverse b
−1
.
Fundamental Materials and Tools 3
Theorem 1.1
The additive and m u ltiplicative identity elements in a field F are b oth unique. The
additive inverse of any element in F is unique and the inverse of the additive inverse
gives back the element itself. The multiplicative inverse ofanynonzeroelementinF
is unique and the inverse of the multiplicative inverse givesbacktheelementitself.
Proof Assume that 0 and 0
$
are add itive identity elements in F.Alsoassumethat1
and 1
$
are multiplicative identity element in F.Theiruniquenessisprovedby
0 = 0 + 0
$
= 0
$
+ 0 = 0
$
1 = 1 ×1
$
= 1
$
×1 = 1
$
Assume that −a and −a
$
are additive inverses fo r an element a in F.Alsoassume
that b
−1
and b
$−1
are multiplicative inverses for a nonzer o element b in F.Their
uniqueness is proved by
−a =(−a)+[a +(−a
$
)] = [(−a)+a]+(−a
$
)=−a
$
b
−1
= b
−1
×(b ×b
$−1
)=(b
−1
×b) ×b
$−1
= b
$−1
Due to the properties of additive inverse: (−a)+a = a +(−a)=0, multiplicative
inverse: b
−1
×b = b ×b
−1
= 1, and the uniqueness of inverses, it can be shown
that −(−a)=a and (b
−1
)
−1
= b.So,a is an additive inverse of −a and b is a
multiplicative inverse of b
−1
.
Definition 1.2
The order of a field is the number of elements in the field. A field with a finite order
p is called a finite field or Galois field GF(p) for a p ositive integer p.Ifp is a prime
number, such a finite field is also called a prime field.
The order of a field can be finite or infinite. The set of all real numbers under
traditional arithmetic is a classical example of a field with an infinite order. The
set of all positive real numbers under traditional arithmetic is a counterexample be-
cause additive identity element “0” and additive inverses can not be found in the set.
Another counterexample is the set of all integers under ordinary arithmetic because
multiplicative inverses, except “1,” do not exist in the set.
In optical coding theory, finite (or Galois) fields with nonnegative integers under
modulo arithmetic are of primary interest. In particular, various families of the prime
codes in this boo k have optimal code properties when the codesareconstructedover
GF(p) of a prime p.Suchaprimefieldcanbecategorizedbythesetofallmodulo-p
4 Optical Coding Theory with Prime
integers with modulo-p additions and multiplications, whereas modulo-p subtrac-
tions and divisions are defined implicitly.
For example, the smallest finite field is GF(2)={0,1},whichisalsoaprimefield.
This field contains only the zero and unity elements, and the modulo-2 additions and
multiplications are summarized as
+
01 × 01
0 01 0 00
1
10 1 01
The next finite field is GF(3)={0, 1,2},whichisalsoaprimefield,withthe
modulo-3 additions and multiplications summarized as
+
012 × 012
0 012 0 000
1 120 1 012
2
201 2 021
The finite field GF(4)={0, 1,2,3} is not a prime field because its additions and
multiplications are not exactly modulo-4, as summarized below:
+
0123 × 0123
0 0123 0 0000
1 1032 1 0123
2
2301 2 0231
3 3210 3 0312
GF(4), also denoted as GF(2
2
),iscalledanextension field of GF(2) because elements
“0” and “1” in GF(4) operate the same way as those in GF(2). In fact, the two tables
of GF(4) are generated by applying the primitive polynomial x
2
+ x + 1overGF(2)
[1–5].
Definition 1.3
The order of a nonzero element a in a finite field GF(p) of a positive integer p is the
smallest positive integer i satisfying a
i
= 1 (mod p).
The o rd er of an element is no t the same as the order of a finite field. The latter
is the number of elements in a finite field and always equal to p in GF(p).Because
there are p −1nonzeroelementsinGF(p ),theorderofanelementcannotbegreater
than p −1. For example, the maximum order of a nonzero element in the prime field
GF(3)={0,1,2} is 2. By inspection, only the element “2” in GF(3) can reach the
maximum order because 2
1
= 2and2
2
= 1 (mod 3).
Fundamental Materials and Tools 5
Definition 1.4
AfieldF
$
is called a subfield of another field F if F contains all elements of F
$
and
these elements in F carry all of the pro perties of F
$
. F is then called an extension
field of F
$
.
Exemplified by GF(2) and GF(4), a prime field GF(p) is a subfield of GF(p
m
)
for a prime p and an integer m > 1. This is because GF(p
m
) contains all elements o f
GF(p),andtheseelementsoperatethesamewayasthoseinGF(p).
For example, GF(2) is also a subfield of GF(2
3
)=GF(8)={0, 1,2,3,4, 5,6,7}.
One example of the addition and multiplication tables of GF(8) is given by
+
01234567 × 01234567
0 01234567 0 00000000
1 10325476 1 01234567
2 23016745 2 02463175
3
32107654 3 03657412
4 45670123 4 04376251
5 54761032 5 05142736
6
67452301 6 06715324
7 76543210 7 07521643
For reference, the tables are generated by applying the primitive polynomial x
3
+
x + 1overGF(2)[1–5].Althoughitisbeyondthescopeofthisbook, a slightly
different multiplication table of GF(8) can also be generated with another primitive
polynomial x
3
+ x
2
+ 1overGF(2).
Definition 1.5
The characteristic of a field F is the smallest number of times for the multiplicative
identity element to add up to generate the additive identity element.
By the definition, the characteristics of GF(p) and GF(p
m
) of a prime p are both
equal to p.Forexample,thecharacteristicsofGF(2)andGF(4)areequal to 2 becau se
their additive identity element “1” can be obtained by addingupthemultiplicative
identity element two times such that 1+ 1 = 0 (mod 2) and 1 + 1 = 0 (mod 4).The
characteristic of GF(7) is 7 because 1 + 1 + 1 + 1 + 1 + 1 + 1 = 0 (mod 7).
1.1.1 Primitive Elements
An important category of elements in a finite field ar e primitive elements. These
elements are useful for constructing other elements in the finite field or extending
the finite field. Every finite field contains at least one primitive element.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.