3a5f96dc78799db71f05cedd3e52cc90e39f | Field (Mathematics) | Group (Mathematics)

Please download to get full document.

View again

of 6
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 Identification 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 fields is proposed wherethe complexity is considerably less in comparison with the standardprocedures for the same purpose.  Keywords —Finite field, irreducible polynomial, primitive polyno-mial, maximal length sequence, additive shift register, multiplicativeshift register. I. I NTRODUCTION F INITE fields 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 finite fields are often covered in EE or CS coursecurriculum only in brief for some specific purpose. Thispaper thus deals with a broad but gentle introduction tofinite fields, i.e., Galois fields. One significant application of finite fields is to generate sequences: in particular, maximallength sequences (m-sequences, in short). Properties of finitefields 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 andfinite fields 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 finite fieldin generating m-sequences. Also, we propose a fast methodto identify primitive polynomials over binary fields wherethe complexity is significantly 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 field 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 simplified 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 finite fields, starting from the verybasic notion of fields, along with the construction of suchfields with the help of primitive polynomials. As we explainlater, these primitive polynomials play an important role ingenerating m-sequences.  A. Fields A field 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 field is a set  F   with two binary operations  + (addition) and  .  (multiplication) defined 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 field iscalled either a  finite  or an  infinite  field. The examples of   infinite field include  Q  (set of all rational numbers),  R  (set of all realnumbers),  C  (set of all complex numbers) etc. On the otherhand, a field with distinct  q   elements is called a finite field, 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  field   and is denoted by  GF  ( q  ) . We discuss aboutconstruction of such fields, which is of our interest of thisarticle, as well as the application of such fields below.  B. Galois Fields Every  Galois  field contains a subfield that has a prime num-ber of elements and this field is called the  prime subfield   or the basefield  . Mathematically, this can be represented as: assuming q   to be a prime number, the integers modulo  q   (denoted by Z q ) form a  Galois  basefield  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 basefield with elements { 0 , 1 } with  +  and  .  defined 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 basefield  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 definition and examples of   Galois  field, theimmediate question that comes into reader’s mind is, whethersuch a field can exist for any general finite integer  t , where  t  isnot a prime number. We deal with this answer in the following.The characteristic of a field, not necessarily finite, is thevalue of prime  q   such that adding any element to itself   q  times results in 0. If no such  q   exists, then the field is saidto be characteristic 0. For example,  Q ,  R  and  C  are allcharacteristic 0 fields. 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  field 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 find 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  satisfiesthe 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  field  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 field 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 basefield  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) coefficient  a i  ∈ GF  ( q  ) . As  GF  ( q  m )  is a primepower field, 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 coefficients 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 coefficients cannot be a validexpression for any  u i . C. Primitive Polynomials over   GF  ( q  n ) It is shown in (1) that  Galois  field 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 define 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 coefficients  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 fields ( GF  (2 n ) ), a set of primitivepolynomials up to  n  = 30  is shown in Table 3, which is quitesufficient 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 defined 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 defined 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 find 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 finite length sequences that arerecurring and thus periodic in nature. By a periodic sequence,we mean a countably infinite 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 findout 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 fieldand its extensions. It is clear that in (5), specifying the initialvalues  ( s n − 1 ,...,s 1 ,s 0 )  completely specifies the sequence.Indeed, specifying any  n  consecutive values specifies allremaining values and, assuming  a 0  = 1 , all previous valuesdown to  s 0 . Since there is only a finite number of possiblecombinations of   s n − 1 ,...,s 0 , or, finite 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 first 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 defined by  s i  =  u i satisfiesthe recurrence in (5). Now, if we compare equation (6) and(4), we find that they are equivalent as, in a characteristic 2field, 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 definition, 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 firstrow of Table 2 (i.e.,  (0 , 0 , 0 , 1) ), the output binary sequencewill then be given by the first 15 values of the correspondingfourth column of the same table, after which the sequencewill be repeated. With this knowledge, we can then define them-sequence as follows.  Definition 1:  A maximal length sequence is a  (2 n −  1) length sequence that satisfies a linear recurrence, defined 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 field 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 finite field. 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 field 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 defined 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 fields whether it is a primitive one ornot, and subsequently we propose a simplified method whichwould be helpful for most of the practical cases.  A. Standard Identification 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
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