16 Optical Coding Theory with Prime
It is foun d that the determinant of a triangular matrix is the product of all elements
on the main diagonal. So, the determinant of a square matrix can be readily obtained
by first transforming it into a triangular matrix.
An n ×n square matrix has a nonzero determinant if and only if its n rows (or
columns) are linearly independent. It is because linear indep en dency implies that no
matrix row-wise (or column-wise) transformation, such as the sum of scalar products
of rows (or columns), can produce a row (or column) with all zero elements, except
when the scalars in the scalar products are all 0s.
This prop erty supports the com p utation of a matrix inverse bymeansofadeter-
minant. For an n ×n square matrix A,thesubstitutionofa
ij
with a
kj
in the Laplace
expansion formula results in
n
∑
j=1
(−1)
i+ j
a
kj
|M
ij
| =
,
|A| for i = k
0otherwise
If B =[b
ij
] is the inverse of A,thentheelementintheith row and j th column of B
can be readily computed by the cofactor of a
ji
as
b
ij
=
(−1)
i+ j
|M
ji
|
|A|
where |A|&= 0.
1.3.4 Eigenvalues and Eigenvectors
An eigenvector of a square matrix is a nonzero vector that maintains in the same
direction but is scaled by a fixed value, called an eigenvalue,afterbeingmultiplied
by the matrix. Eigenvalues and eigenvectors find applications in linear algebra, such
as matrix factorization into canonical form [4, 5].
Definition 1.12
Anonzerovectorv is an eigenvector of a square matrix A if there exists a scalar c,
called an eigenvalue of A,suchthatAv = cv or (A −cI)v = 0.
By definition, the eigenvalues of A are f o und by calculating the roots of |A−cI|=
0. The eigenvector v associated with an eigenvalue is co mputed by substituting the
eigenvalue b ack into (A −c I)v = 0andthensolvingfortheelementsofv.
For example, the eigenvalues of matrix
A =
'
34
21
(
are found by evaluating the determinant
|A −c I|=
+
+
+
+
3 −c 4
21−c
+
+
+
+
= 0
Fundamental Materials and Tools 17
and then solving (3 −c)(1 −c) −2 ×4 = c
2
−4c −5 = 0. The eigenvalues of A are
found to be “−1” and “5.” The eigenvectors associated with the eigenvalue “ −1” is
computed by further solving
[A −(−1)I]v =
'
44
22
('
v
1
v
2
(
=
'
0
0
(
and, in turn , 4 v
1
+ 4v
2
= 0and2v
1
+ 2v
2
= 0. A nontrivial solution to these two
equations is v
2
= −v
1
.Theeigenvectorsoftheeigenvalue“−1” are then given by
v
1
(1,−1)
t
with v
1
being arbitrary. For instance, by setting v
1
= 1, (1,−1)
t
becomes
an eigenvector associated with the eigenvalue “−1.” Similarly, (2, 1)
t
is an eigenvec-
tor associated with the eigenvalue “5” if v
1
= 1isalsoassumed.
If c is an eigenvalue of A,
α
c is the eigenvalue of
α
A for a scalar
α
.
If c is an eigenvalue of a nonsingular matrix A,1/c is the eigenvalue of A
−1
.
The eigenvalues of an upper or lower triangular matrix are theelementsonthe
main diagonal.
If the eigenvalues of a nonsingular matrix A are all distinct, the associated eigen-
vectors are all linearly independent, as implied in the following theorem.
Theorem 1.6
If A is an n ×n nonsingular matrix with n distinct eigenvalues, there exists an n ×n
nonsingular matrix B such that B
−1
AB is a diagonal matrix. A is said to be diago-
nalizable.
Proof Let A be an n ×n matrix with eigenvectors {b
1
,b
2
,...,b
n
} associated with
n distinct eigenvalues {c
1
,c
2
,...,c
n
},respectively.Assumethattheseeigenvec-
tors are linearly dependent. Hence, there exists an integer k ∈ [1,n −1] such that
{b
1
,b
2
,...,b
k
} are linearly ind ependent but {b
1
,b
2
,...,b
k+1
} are linearly d ep en-
dent. This gives
α
1
b
1
+
α
2
b
2
+ ··· +
α
k+1
b
k+1
= 0forsomescalars{
α
1
,
α
2
, ...,
α
k+1
} not all equal to 0. Multiplying by A on both sides results in
α
1
Ab
1
+
α
2
Ab
2
+
···+
α
k+1
Ab
k+1
= 0. By definition, Ab
i
= c
i
b
i
for all i ∈ [1, n].So,theequation
can be further written as
α
1
c
1
b
1
+
α
2
c
2
b
2
+ ··· +
α
k+1
c
k+1
b
k+1
= 0. Subtracting
it from the original equation and then multiplying c
k+1
on both sides of the dif-
ference results in
α
1
(c
1
−c
k+1
)b
1
+
α
2
(c
2
−c
k+1
)b
2
+ ··· +
α
k
(c
k
−c
k+1
)b
k
= 0.
Because {b
1
, b
2
, ..., b
k
} are assumed linearly independent, it can be concluded that
α
i
(c
i
−c
k+1
)b
i
= 0foralli ∈ [1, k].Astheseeigenvaluesarealldistinct,thisgives
c
i
−c
k+1
&= 0and
α
i
must be zero for all i ∈ [1,k + 1],whichcontradictsthenot-all-
zero-scalar and linear-dependen t assumptions. So, the n eigenvectors associated with
the n distinct eigenvalues must be linearly independent.
Assume that these n linear-independent eigenvectors form the columns of an n×n
matrix B.Bydefinition,thereexistsB
−1
.IfAb
i
= c
i
b
i
for i ∈[1, n] are expressed in
18 Optical Coding Theory with Prime
matrix form as AB = BC,then
C =
c
1
0 ··· 0
0 c
2
··· 0
.
.
.
.
.
.
.
.
.
.
.
.
00··· c
n
is an n ×n diagonal matrix containing all n distinct eigenvalues of A.Themultipli-
cation of B
−1
on both sides results in B
−1
AB = C,adiagonalmatrix.
While direct multiplication is a straightforward method of calculating small pow-
ers of a square matrix, the task becomes difficult for large powers. If the square ma-
trix has all distinct eigenvalues, Theorem 1.6 makes large-power calculations easier
by computing the powers of a diagonal matrix as
A
k
=
-
BCB
−1
.
k
=(BCB
−1
)(BCB
−1
)···(BCB
−1
)
= BCIC ···ICB
−1
= BC
k
B
−1
in which C
k
is simply given by
C
k
=
c
k
1
0 ··· 0
0 c
k
2
··· 0
.
.
.
.
.
.
.
.
.
.
.
.
00··· c
k
n
1.4 HAMMING DISTANCE AND WEIGHT
Hamming weight and distance are two important p a rameters in characterizing an
optical code that consists of a collection of codewords.
The Hamming weight,commonlycalledcodeweight,ofacodeisthenumberof
nonzero elements in each of its codewords.
The Hamming distance between two codewords that have the same number of
code elements is the number of positions in which the respective elements of the two
codewords differ.
Their Hamming distance is also the Hamming weight on the difference of two
codewords. So, the Ham m ing weight of a codeword is the Ham m ingdistancebe-
tween the codeword and the all-zero codeword.
For example, the Hamming weights of the codewords 1010010010and
0100011001 are both 4 and their Hamming distance is 6.
The minimum distance of a code is the smallest Hamming distance that can be
found between any pair of codewords in the code set.
Fundamental Materials and Tools 19
1.5 CORRELATION FUNCTIONS
Autocorrelation and cross-correlation functions are impo rtant parameters in charac-
terizing optical codes [17,18,21,22,27]. Because some optical codes are constructed
in vector form and some are in matrix form, these correlation functions are here
defined as one-dimensional (1-D) and two-dimensional (2-D).Theautocorrelation
function consists of two parts—the p eak and sidelobes—and isusefulforinitialcode
acquisition and synchr o nization between th e transmitter-receiver pair. The autocor-
relation peak is usually equal to the Hamming (or code) weightanddetermineshow
well an optical codeword is detected at its receiver in the presence of mutual interfer-
ence caused by interfering co d ewords. It is desirable to design optical codes with the
autocorrelation sidelobes as low as possible for minimizing self-interference.The
cross-correlation function represents the degree of mutualinterferencecausedby
interfering codewords and can be defined as aperiodic, periodic,orin-phase,de-
pending on the coding schemes in use (e.g., see Chapter 2). Theaperiodiccross-
correlation function measures the strength of m utual interference as a function of
the amount of (code-element) shifts applied to one of the two correlating codewords.
The periodic cross-correlation function is defined similar to the aperiodic one, except
that the shifts are performed cyclically—as if the shifted codeword is concatenated
once—so that the correlation process does not involve any null caused by the “shift-
out” of the shifted codeword. The in-phase cross-correlation function assumes that
the two correlating codewords are aligned accordingly during the correlation process.
So, in-phase cross-correlation results in just a value, not afunctionofanyshift.Op-
tical codes are traditionally designed with these cross-correlation fu nctions as close
to zero as possible for minimizing mutual interference.
1.5.1 1-D Auto- and Cross-Correlation Functions
The 1-D correlation functions are defined for optical codes that use one coding fea-
ture (e.g., time or wavelength) to convey information. For example, 1-D unipolar
temporal-amplitude codes convey nonzero code elements withopticalpulsesintime.
Definition 1.13
For two distinct 1-D codewords (or N-tuples) C =(c
0
,c
1
,...,c
i
,...,c
N−1
) and C
$
=
(c
$
0
,c
$
1
,...,c
$
i
,...,c
$
N−1
) an d an integer
τ
∈[0,N −1],the1-Dperiodicdiscretecross-
correlation function between C an d C
$
at a given
τ
-shift is defined as
Θ
C,C
$
(
τ
)=
N−1
∑
i=0
c
i
c
$
i⊕
τ
where c
i
and c
$
i
represent the code elements in the ith positions of C and C
$
,respec-
tively, and “⊕”denotesamodulo-N addition.
20 Optical Coding Theory with Prime
For the 1-D in-phase cross-correlation function,
τ
is set to a fixed value, such as
τ
= 0.
For the 1-D aperiodic cross-correlation function, the modulo-N ad dition is re-
placed by an ordinary addition so that the shifts are noncyclic.
Setting C = C
$
, Θ
C,C
(
τ
) defines the 1-D discrete autocorrelation function of C.
When
τ
= 0, this function gives the autocorrelation peak, which is equal to the Ham-
ming (or code) weight. Otherwise, it gives the autocorrelation sidelobe at a
τ
-shift.
The maximum cross-co rrelation function is the largest cross-correlation value that
can be obtained between any two correlating N-tuples, say C and C
$
,inthecodeset
and defined as
Θ
max
= max{Θ
C,C
$
(
τ
),for all
τ
∈ [0,N −1 ]}
The average cross-correlation function between two N-tuples is taken by averag-
ing the sum of their cross-correlation values from all N
τ
-shifts and given by
Θ
C,C
$
=
1
N
N−1
∑
τ
=0
Θ
C,C
$
(
τ
)
The 1-D p eriodic cross-correlation function between any two N-tuples (i.e., code-
words) counts the number of positions where both N-tuples have the same nonzero
code elements at any
τ
cyclic-shift. For example, if the code set contains binary (0, 1)
N-tuples, the nonzero code elements are simply binary 1s. The ap er io d ic definition
implies that the
τ
-shift is noncyclic. In these 1-D definitions,
τ
is referred to as only
one kind of shift in either time or wavelength, depending on which coding feature is
used. The in-phase cross-correlation function is just one value because it is ju st one
case, usually
τ
= 0, in the periodic cross-correlation function.
1.5.2 2-D Auto- and Cross-Correlation Functions
The 2-D correlation functions are defined fo r o p tical cod es that use two coding fea-
tures (e.g., time and wavelength) to convey information. Forexample,2-Dunipo-
lar spectral-temporal-amplitude codes convey nonzero codeelementsbymultiwave-
length optical pulses in time.
Definition 1.14
For any two distinct 2-D codewords (or L ×N matrices) C =[c
i, j
] and C
$
=[c
i, j
]
and two integers
τ
1
∈ [0,L −1] and
τ
2
∈ [0, N −1],the2-Dperiodicdiscretecross-
correlation function between C and C
$
at given
τ
1
-and
τ
2
-shifts is defined as
Θ
C,C
$
(
τ
1
,
τ
2
)=
L−1
∑
i=0
N−1
∑
j=0
c
i, j
c
$
i
ˆ
⊕
τ
1
, j ⊕
τ
2
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.