All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.

Information Report

Category:
## Documents

Published:

Views: 4 | Pages: 6

Extension: PDF | Download: 0

Share

Related documents

Description

j

Transcript

On the Construction of m-Sequences via PrimitivePolynomials with a Fast Identiﬁcation Method
Abhijit Mitra
Abstract
—The paper provides an in-depth tutorial of mathematicalconstruction of maximal length sequences (m-sequences) via prim-itive polynomials and how to map the same when implemented inshift registers. It is equally important to check whether a polynomialis primitive or not so as to get proper m-sequences. A fast method toidentify primitive polynomials over binary ﬁelds is proposed wherethe complexity is considerably less in comparison with the standardprocedures for the same purpose.
Keywords
—Finite ﬁeld, irreducible polynomial, primitive polyno-mial, maximal length sequence, additive shift register, multiplicativeshift register.
I. I
NTRODUCTION
F
INITE ﬁelds are ubiquitous in computer science andcommunications. They help form a foundation for suchareas as coding theory and cryptography, as well as theyare a fundamental building block in discrete mathematics[1]. Yet ﬁnite ﬁelds are often covered in EE or CS coursecurriculum only in brief for some speciﬁc purpose. Thispaper thus deals with a broad but gentle introduction toﬁnite ﬁelds, i.e., Galois ﬁelds. One signiﬁcant application of ﬁnite ﬁelds is to generate sequences: in particular, maximallength sequences (m-sequences, in short). Properties of ﬁniteﬁelds transfer readily to certain properties of m-sequences likecorrelation, span, linear complexity, and so forth. As a stan-dard tool for computer scientists and engineers, m-sequencesespecially have their roles as pseudo noise sequences witha thorough application in spread spectrum communications.Treatments of m-sequences are, however, often focused onlyon the generation of the sequence in terms of shift registerswhile leaving out the basic relationship of m-sequences andﬁnite ﬁelds that may be germane or even essential to anapplication. We focus on the relation in this paper and showthe instrumentality of primitive polynomials over a ﬁnite ﬁeldin generating m-sequences. Also, we propose a fast methodto identify primitive polynomials over binary ﬁelds wherethe complexity is signiﬁcantly less in comparison with thestandard procedures.The organization of the paper is as follows. In Section 2, wedeal with the fundamentals of algebraic operations to introducethe notion of Galois ﬁeld and primitive polynomials that isneeded for our purpose. Section 3 shows the constructionof m-sequences from primitive polynomials and how to mapthe same when implemented in shift registers. The standardmethod along with the proposed simpliﬁed approach for
Manuscript received August 01, 2008.A. Mitra is with the Department of Electronics and Communication Engi-neering, Indian Institute of Technology (IIT) Guwahati, Guwahati – 781039,India. E-mail: a.mitra@iitg.ernet.in.
identifying a primitive polynomial is given in Section 4. Thepaper is concluded in Section 5 by summarizing the importantconcepts discussed herein. An easy way of practically gener-ating Gaussian sequences from such m-sequences is discussedin the Appendix.II. F
UNDAMENTALS OF
A
LGEBRAIC
O
PERATIONS
We discuss here about ﬁnite ﬁelds, starting from the verybasic notion of ﬁelds, along with the construction of suchﬁelds with the help of primitive polynomials. As we explainlater, these primitive polynomials play an important role ingenerating m-sequences.
A. Fields
A ﬁeld is an algebraic structure [2] in which the operationsof addition, subtraction, multiplication, and division (exceptby zero) can be performed, and satisfy the usual rules. Moreprecisely, a ﬁeld is a set
F
with two binary operations
+
(addition) and
.
(multiplication) deﬁned on it, in which thefollowing laws hold.(A1)
a
+ (
b
+
c
) = (
a
+
b
) +
c
(associative law for addition)(A2)
a
+
b
=
b
+
a
(commutative law for addition)(A3) There is an element
0
(zero) such that
a
+ 0 =
a
∀
a
(A4)
∀
a
, there is an element
−
a
such that
a
+ (
−
a
) = 0
(M1)
a.
(
b.c
) = (
a.b
)
.c
(associative law for multiplication)(M2)
a.b
=
b.a
(commutative law for multiplication)(M3) There is an element
1
(
= 0
) such that
a.
1 =
a
∀
a
(M4)
∀
a
= 0
, there is an element
a
−
1
such that
a.a
−
1
= 1
(D)
a.
(
b
+
c
) = (
a.b
) + (
a.c
)
(distributive law)Using the notion of elementary group theory (i.e., anAbelian group is a commutative group; homomorphism isa function that maps the elements of one group to anothergroup with certain property; isomorphism is a homomorphismthat is also a bijection mapping; and, automorphism is anisomorphism that maps a group onto itself), we can condensethese nine axioms into just three [3]:(1) The elements of
F
form an Abelian group with theoperation
+
(called the additive group of
F
);(2) The non-zero elements of
F
form an Abelian group underthe operation
.
(called the multiplicative group of
F
);(3) Multiplication by any non-zero element is an automor-phism of the additive group.Depending upon the number of elements in it, a ﬁeld iscalled either a
ﬁnite
or an
inﬁnite
ﬁeld. The examples of
inﬁnite
ﬁeld include
Q
(set of all rational numbers),
R
(set of all realnumbers),
C
(set of all complex numbers) etc. On the otherhand, a ﬁeld with distinct
q
elements is called a ﬁnite ﬁeld,
World Academy of Science, Engineering and Technology 21 2008768
TABLE IA
DDITION AND
M
ULTIPLICATION
T
ABLES FOR
GF
(3)+
0 1 2
.
0 1 20 0 1 2 0 0 0 01 1 2 0 1 0 1 22 2 0 1 2 0 2 1
or,
Galois
1
ﬁeld
and is denoted by
GF
(
q
)
. We discuss aboutconstruction of such ﬁelds, which is of our interest of thisarticle, as well as the application of such ﬁelds below.
B. Galois Fields
Every
Galois
ﬁeld contains a subﬁeld that has a prime num-ber of elements and this ﬁeld is called the
prime subﬁeld
or the
baseﬁeld
. Mathematically, this can be represented as: assuming
q
to be a prime number, the integers modulo
q
(denoted by
Z
q
) form a
Galois
baseﬁeld
GF
(
q
)
, i.e., its elements are thecongruence classes of integers (mod
q
), with addition andmultiplication induced from the usual integer operations. Inother words, the elements of
GF
(
q
)
are
{
0
,
1
,
2
,...,q
−
1
} ∈
Z
q
and these integers follow all the nine properties (A1)-(D)as given above with respect to mod
q
. The simplest possibleexample is
GF
(2)
which is a binary baseﬁeld with elements
{
0
,
1
}
with
+
and
.
deﬁned on it as
0+0 = 0
,
0+1 = 1+0 = 1
,
1+1 = 2 = 0
(mod 2),
0
.
0 = 0
,
0
.
1 = 1
.
0 = 0
,
1
.
1 = 1
. Theexample of a ternary baseﬁeld
GF
(3)
is shown in Table 1 withaddition and multiplication tables with respect to mod
3
where
{
0
,
1
,
2
}
have been used as representatives of the congruenceclasses.With the above deﬁnition and examples of
Galois
ﬁeld, theimmediate question that comes into reader’s mind is, whethersuch a ﬁeld can exist for any general ﬁnite integer
t
, where
t
isnot a prime number. We deal with this answer in the following.The characteristic of a ﬁeld, not necessarily ﬁnite, is thevalue of prime
q
such that adding any element to itself
q
times results in 0. If no such
q
exists, then the ﬁeld is saidto be characteristic 0. For example,
Q
,
R
and
C
are allcharacteristic 0 ﬁelds. In fact, the set of numbers in
GF
(
q
)
generated by repeatedly adding 1 is closed under both addition,multiplication, subtraction and division, and is isomorphic to
Z
q
. This is not true for any
t
. For example,
Z
6
cannot be a
Galois
ﬁeld as in
Z
6
, we have
2
.
3 = 0
(mod 6) which showsthat neither 2 nor 3 can have inverses. However, followingsome elementary results in group theory, one can ﬁnd that if
a
= 0
(mod
q
), where
a
∈
GF
(
q
)
, then
a
q
−
1
= 1
. Multiplyingboth sides by
a
shows that
a
q
−
a
= 0
for
a
= 0
. Since this isalso true for
a
= 0
, we see that every element in
Z
q
satisﬁesthe following polynomial equation
x
q
−
x
= 0
(1)which has
q
roots with each root being exactly the elementsin
Z
q
. Putting
q
=
q
m
above yields the equation
x
q
m
−
x
= 0
.This, in turn, means construction of a
GF
(
t
)
is possible withthe above closure property, if and only if
t
=
q
m
where
m
isany positive integer. A
Galois
ﬁeld
GF
(
q
m
)
is therefore said
1
Evariste Galois, 1811-1832, who although dying young and only publish-ing a handful of papers, wrote seminal works in group and ﬁeld theory.TABLE IIT
HE
E
LEMENTS OF THE
F
IELD
GF
(2
4
)
AS
P
OWERS OF
u
AND AS
D
IFFERENT
P
OLYNOMIALS
u
3
u
2
u
1
1 Power of
u
0 0 0 1
u
0
0 0 1 0
u
1
0 1 0 0
u
2
1 0 0 0
u
3
0 0 1 1
u
4
0 1 1 0
u
5
1 1 0 0
u
6
1 0 1 1
u
7
0 1 0 1
u
8
1 0 1 0
u
9
0 1 1 1
u
10
1 1 1 0
u
11
1 1 1 1
u
12
1 1 0 1
u
13
1 0 0 1
u
14
0 0 0 1
u
15
=
u
0
= 1
to be an extension of baseﬁeld
GF
(
q
)
, with
q
m
elements andwith addition and multiplication done in the usual way withrespect to mod
q
. It then follows that
GF
(
q
m
)
has a
m
elementbasis over
GF
(
q
)
. That is, there exist
m
distinct elements
u
0
,...,u
m
−
1
∈
GF
(
q
m
)
such that each of the
q
m
elementsof
GF
(
q
m
)
can be expressed as
a
0
u
0
+
...
+
a
m
−
1
u
m
−
1
forsome (unique) coefﬁcient
a
i
∈
GF
(
q
)
. As
GF
(
q
m
)
is a primepower ﬁeld, let us assume for the moment that its elementsare generated by power addition and thus,
{
1
,u
1
,...,u
m
−
1
}
form the basis of
GF
(
q
m
)
for some
u
. Then,
u
m
−
a
m
−
1
u
m
−
1
−
...
−
a
0
= 0
(2)since
u
m
must be a linear combination on the basis. Thisshows that we can multiply two arbitrary elements in
GF
(
q
m
)
by expressing the elements in the basis, multiplying them aspolynomials in
u
and reducing the result by the relation in (2).As an illustration, let us see how to construct
GF
(2
4
)
suchthat
{
1
,u
1
,u
2
,u
3
}
is a basis over
GF
(2)
with the relationship
x
4
+
x
+ 1 = 0
.
(3)That is, letting
u
be a root of this equation, we get the basicrelationship
u
4
=
u
+1
with respect to mod 2. This means allthe
2
4
= 16
elements of
GF
(2
4
)
,
{
1
,u
1
,u
2
,...,u
15
}
, can beexpressed in terms of linear combinations of
{
1
,u
1
,u
2
,u
3
}
for some (unique)
a
i
∈
GF
(2)
using (3). For example,
u
5
=
u.u
4
=
u.
(
u
+ 1) =
u
2
+
u
. Similarly, all the other elementscan also be represented by a polynomial expression wherethe highest degree of the polynomial is 3. The polynomialexpressions, as the coefﬁcients of
{
1
,u
1
,u
2
,u
3
}
, are givenin Table 2 for this example. We observe from Table 2 thatbeyond
u
q
m
−
2
, the higher powers of
u
repeat the elements of
GF
(
q
m
)
which comes from the closure property as given in(1). It is also seen that all zero coefﬁcients cannot be a validexpression for any
u
i
.
C. Primitive Polynomials over
GF
(
q
n
)
It is shown in (1) that
Galois
ﬁeld elements can be expressedin terms of polynomials and more explicitly in (2) which also
World Academy of Science, Engineering and Technology 21 2008769
TABLE IIIA S
ET OF
P
RIMITIVE
P
OLYNOMIALS UP TO
D
EGREE
30
FOR
B
INARY
F
IELDS
degree
(
n
)
p
(
x
)
1
x
+ 1
2
x
2
+
x
+ 1
3
x
3
+
x
+ 1
4
x
4
+
x
+ 1
5
x
5
+
x
2
+ 1
6
x
6
+
x
+ 1
7
x
7
+
x
+ 1
8
x
8
+
x
6
+
x
5
+
x
+ 1
9
x
9
+
x
4
+ 1
10
x
10
+
x
3
+ 1
11
x
11
+
x
2
+ 1
12
x
12
+
x
7
+
x
4
+
x
3
+ 1
13
x
13
+
x
4
+
x
3
+
x
+ 1
14
x
14
+
x
12
+
x
11
+
x
+ 1
15
x
15
+
x
+ 1
16
x
16
+
x
5
+
x
3
+
x
2
+ 1
17
x
17
+
x
3
+ 1
18
x
18
+
x
7
+ 1
19
x
19
+
x
6
+
x
5
+
x
+ 1
20
x
20
+
x
3
+ 1
21
x
21
+
x
2
+ 1
22
x
22
+
x
+ 1
23
x
23
+
x
5
+ 1
24
x
24
+
x
4
+
x
3
+
x
+ 1
25
x
25
+
x
3
+ 1
26
x
26
+
x
8
+
x
7
+
x
+ 1
27
x
27
+
x
8
+
x
7
+
x
+ 1
28
x
28
+
x
3
+ 1
29
x
29
+
x
2
+ 1
30
x
30
+
x
16
+
x
15
+
x
+ 1
indicates that all the elements have different polynomial rep-resentations with respect to a basic relationship. We thus nowinvestigate more into the form of polynomials for generatingany
GF
(
q
n
)
. Analogous to expression (2), let us deﬁne ageneral polynomial
p
(
x
)
of order
n
over a
GF
(
q
n
)
as
p
(
x
) =
a
n
x
n
+
a
n
−
1
x
n
−
1
+
...
+
a
1
x
+
a
0
(4)where, as earlier, all the coefﬁcients
a
i
,
i
= 0
,
1
,...,n
aremembers of
GF
(
q
)
, i.e., integers ranging from
0
to
q
−
1
with
a
n
=
a
0
= 1
. The polynomial of (4) is called
irreducible
in
GF
(
q
n
)
if
p
(
x
)
cannot be factored into a product of lower-degree polynomials. An
irreducible
polynomial
p
(
x
)
∈
GF
(
q
n
)
of degree
n
is said to be
primitive
if the smallestpositive integer
l
for which
p
(
x
)
divides
h
(
x
) =
x
l
−
1
is
l
=
q
n
−
1
. For binary ﬁelds (
GF
(2
n
)
), a set of primitivepolynomials up to
n
= 30
is shown in Table 3, which is quitesufﬁcient for most of the purposes. Primitive polynomials of much higher degree can be found in [4].At this point, another question might come to reader’s mind:whether there exist irreducible and primitive polynomials of degree
n
for each
n
. The answer to this question is ‘Yes’. Notethat, not only one, there exist more than one irreducible andprimitive polynomials for any degree
n >
1
. These are usuallycalculated using Mobius functions and Euler
ϕ
functions,respectively. For example,
β
2
(
n
)
is deﬁned as the numberof primitive polynomials of degree
n
(
∈
GF
(2
n
)
) and themathematical relation of this with Euler function
ϕ
(2
n
−
1)
is
β
2
(
n
) =
ϕ
(2
n
−
1)
n
where
ϕ
(2
n
−
1)
is deﬁned as the numberof positive integers not exceeding
2
n
−
1
and coprime to
2
n
−
1
. However, discussion about this is beyond the scope of this article. Interested readers can ﬁnd the rather complicatedproofs on these in [5].With the help of primitive polynomials, we can construct aclass of linear recurring sequences, called m-sequence [6]-[7],which is highly important in a number of applications mainlyincluding spread spectrum communications. We describe be-low the generation process of such sequences by primitivepolynomials.III. C
ONSTRUCTION OF
M
AXIMAL
L
ENGTH
S
EQUENCES
Let us assume a class of ﬁnite length sequences that arerecurring and thus periodic in nature. By a periodic sequence,we mean a countably inﬁnite list of values
s
= (
s
0
,s
1
,...
)
such that
s
i
+
N
=
s
i
∀
N
≥
1
and
i
≥
0
, where
N
refersto the period of the sequence. Our aim is, however, to ﬁndout a relation between such linear recurrence and primitivepolynomials so as to generate m-sequences from primitivepolynomials.
A. Linear Recurrence
In general, any linear recurrence of order
n
is given by
s
i
+
n
=
n
−
1
k
=0
a
k
s
i
+
k
,
∀
i
≥
0
.
(5)Let us assume that
s
i
∈
GF
(2
n
)
for computational purposesand
a
k
∈
GF
(2)
, i.e., we are mainly interested in binary ﬁeldand its extensions. It is clear that in (5), specifying the initialvalues
(
s
n
−
1
,...,s
1
,s
0
)
completely speciﬁes the sequence.Indeed, specifying any
n
consecutive values speciﬁes allremaining values and, assuming
a
0
= 1
, all previous valuesdown to
s
0
. Since there is only a ﬁnite number of possiblecombinations of
s
n
−
1
,...,s
0
, or, ﬁnite states, any sequencesatisfying (5) must repeat and the period of such a nonzerosequence can be at most
2
n
−
1
as there are
2
n
possible states(the all-zeros state cannot occur unless the sequence is itself all-zeros).As an example, consider the relation
s
i
+4
=
s
i
+1
+
s
i
with the initial state
(0
,
0
,
0
,
1)
. The resulting sequence isbinary and has a period of 15 with the ﬁrst 15 values as
100010011010111
. The values repeat itself after this period.
B. Sequences via Characteristic Polynomials
Let us take a characteristic polynomial of the linear recur-rence (5) as
f
(
x
) =
x
n
−
n
−
1
k
=0
a
k
x
k
(6)by replacing
s
i
+
k
with
x
k
. The relation
f
(
x
) = 0
is called thecharacteristic equation of this. Let
u
be a root of this equation,meaning
u
n
=
n
−
1
k
=0
a
k
u
k
. Multiplying both sides by
u
i
, weget
u
i
+
n
=
n
−
1
k
=0
a
k
u
i
+
k
(7)
World Academy of Science, Engineering and Technology 21 2008770
Fig. 1. The additive shift register structure.
which shows that the sequence deﬁned by
s
i
=
u
i
satisﬁesthe recurrence in (5). Now, if we compare equation (6) and(4), we ﬁnd that they are equivalent as, in a characteristic 2ﬁeld, minus signs can be changed to plus signs. Therefore,if
f
(
x
)
is irreducible, then it will have
n
distinct roots:
{
1
,u
1
,u
2
,...,u
n
−
1
}
. Further, if
f
(
x
)
is a primitive polyno-mial, then, from the deﬁnition, the order of a root
u
mustbe
(2
n
−
1)
which is the maximum possible period of theoutput sequence given by the recurrence (5). In other words,if the characteristic equation of an order
n
linear recurrencesequence is the associated primitive polynomial, the sequenceperiod becomes maximum. Now if we look at the problemgiven by the recurring relation
s
i
+4
=
s
i
+1
+
s
i
, it refers tothe primitive polynomial of (3) and thus the sequence must bea maximum period sequence. If initial state is given by the ﬁrstrow of Table 2 (i.e.,
(0
,
0
,
0
,
1)
), the output binary sequencewill then be given by the ﬁrst 15 values of the correspondingfourth column of the same table, after which the sequencewill be repeated. With this knowledge, we can then deﬁne them-sequence as follows.
Deﬁnition 1:
A maximal length sequence is a
(2
n
−
1)
length sequence that satisﬁes a linear recurrence, deﬁned over
GF
(2)
, given by any corresponding primitive polynomial of degree
n
.
C. Generating M-Sequence
The goal up to now has been to give a mathematicalformula for m-sequences which we did via (5)-(7). In ac-tual applications, of course, m-sequences are generated viaprimitive polynomials (as given in Table 3 as an example)by the more familiar method of linear feedback shift registers(LFSRs), depending upon the nature of the application. Herewe present a brief account of two standard registers forgenerating m-sequences: the
additive form
which is related tolinear recurrences, and the
multiplicative form
which is relatedto linear functions of ﬁeld elements.
1) Additive shift register:
Recall that a state of any periodicsequence
s
satisfying the recurrence (5) is an
n
-tuple of
n
consecutive values of
s
. If we consider two consecutive states,say
(
s
i
,s
i
+1
,...,s
i
+
n
−
1
)
→
(
s
i
+1
,s
i
+2
,...,s
i
+
n
)
(8)then we see the second state is obtained by shifting all valuesto left by one bit and appending the value obtained from (5).This operation can be implemented in a LFSR which is shownin Fig. 1. Here
n
= 4
and the feedback is
s
i
+4
=
s
i
+1
+
Fig. 2. The multiplicative shift register structure.
s
i
. The type of shift register in Fig.1 is called an
additive
shift register. Its main characteristic is that it implements therecurrence exactly and the feedback bit is given by a linearcombination of some of the bits. In practice, however, if thereare a large number of taps, the fan-in to the additive functionmay be impractical. The multiplicative register alleviates thisproblem.
2) Multiplicative shift register:
The
multiplicative
form,used to generate m-sequences, is based on multiplication inthe ﬁnite ﬁeld. With the knowledge that any linear functionapplied to its elements, i.e., to the register state, must yieldan m-sequence, we get such a shift register as shown in Fig.2. The top portion of the register generates the ﬁeld elements(where we put in the initial element (0, 0, 0, 1)). These are thentransformed to the sequence bits by some linear function. Thisfunction is often called a mask. The multiplicative register maybe more practical, especially for simple linear functions, e.g.,reading only a few bits of the register state. If we look at Table2 again with initial state (0, 0, 0, 1) and
u
as the primitiveroot deﬁned by
x
4
+
x
+1
, then such a multiplicative registergives the successive states as sequential powers of
u
, i.e.,
u
i
for
i
= 0
,
1
,...,
14
, after which the states get repeated.IV. I
DENTIFICATION OF
P
RIMITIVE
P
OLYNOMIALS WITH
R
EDUCED
C
OMPLEXITY
As stated in the last section, it is necessary to check any polynomial whether it is a primitive one or not beforeemploying it for constructing m-sequence purpose. Althougha list is given in Table 3, it is, however, only one possiblesolution set and the reader should be reminded that there mayexist other primitive polynomials as well for any degree
n
.Below, we discuss about a standard procedure to check anypolynomial over binary ﬁelds whether it is a primitive one ornot, and subsequently we propose a simpliﬁed method whichwould be helpful for most of the practical cases.
A. Standard Identiﬁcation Procedure
To check whether any general polynomial
p
(
x
)
with order
n
, as given in (4), is a primitive polynomial or not over
GF
(2)
,we can follow the stepwise algorithm as given in [8].Step 1: To check whether
p
(
x
)
is irreducible.(Divide
p
(
x
)
by any polynomial over
GF
(2)
of order
1
<m
≤√
n
and check all divisions have non-zero remainders.)Step 2: To check whether irreducible
p
(
x
)
is primitive.
World Academy of Science, Engineering and Technology 21 2008771

Recommended

Related Search

We Need Your Support

Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks