1492
IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 44, NO. 4, JULY 1998
Optimal Large Linear Complexity Frequency Hopping Patterns Derived from Polynomial Residue Class Rings P. Udaya and M. U. Siddiqi
Abstract—We construct new sequences over finite rings having optimal Hamming correlation properties. These sequences are useful in frequency hopping multiple-access (FHMA) spreadspectrum communication systems. Our constructions can be classified into linear and nonlinear categories, both giving optimal Hamming correlations according to Lempel–Greenberger bound. The nonlinear sequences have large linear complexity and can be seen as a generalized version of GMW sequences over fields. Index Terms—Frequency hopping patterns, GGMW sequences, linear complexity, nonlinear sequences, sequences over finite rings.
I. INTRODUCTION
W
E are concerned with frequency hopping multipleaccess (FHMA) communication systems, employing multiple frequency shift keying (MFSK) as data modulation technique. Such systems require large sets of hopping patterns of large period and linear complexity (LC) over an alphabet of large size having good Hamming correlation properties. Most of the existing frequency hopping patterns are derived from sequences over finite fields [10], [13], [18]. In this paper, we generalize the structure of the sequence alphabet to a residue , for , be class polynomial ring over GF . Let over GF the th power of an irreducible polynomial of degree . Then, the residue class ring is defined as GF This generalization provides a large choice of rings to construct frequency hopping sequences. The idea of considering polynomial finite rings to construct frequency hopping patterns stems from a recent success in using ring , the integer ring modulo , to construct optimal sequences [5], [18]–[20]. All quadriphase constructions obtained from finite fields which have appeared in the literature are always suboptimal. The theory developed in this paper is analogous to the one described in [5] and [18]–[20]. We hope the generalization considered in this paper will pave the way for many more good frequency hopping sequence designs. Manuscript received July 18, 1995; revised January 13, 1998. The material in this paper was presented at the Recent Results session of the IEEE International Symposium on Information Theory, Budapest, Hungary, June 23–29, 1991. P. Udaya is with the Department of Mathematics, RMIT University, Melbourne VIC–3001, Australia (e-mail:
[email protected]). M. U. Siddiqi is with the Department of Electrical Engineering, Indian Institute of Techanology, Kanpur, India (e-mail:
[email protected]). Publisher Item Identifier S 0018-9448(98)03751-1.
The frequency hopping patterns are obtained by associating in the ring a distinct frequency with each symbol belonging to the frequency library. These patterns could be used in FHMA communication systems, employing MFSK as data modulation technique. In such systems, each of the users is provided with a distinct frequency hopping pattern of period . Each symbol in a hopping pattern determines the frequency band within which transmission will take place for a finite duration. The usefulness of these sequences depends on their properties with respect to Hamming correlation and linear complexity functions [10]. The Hamming crosscorrelation between two sequences of period over function , , and , is given by
(1) where is a binary Hamming function given by if and if . The LC of a sequence is the shortest length linear feedback shift register which generates the sequence. The design of frequency hopping patterns for such systems should address the following criteria [10]. , , • The Hamming autocorrelation function for all sequences should be as small as possible. • The Hamming crosscorrelation between any sequence in a set with all phase shifts of other sequences in the set should be as small as possible. • The sequences should be of large period and linear complexity. The first and second criteria minimizes interference due to presence of other users in the communication and also helps the system to have self-synchronizing capability. Whereas the third criterion prevents an intelligent jammer from jamming the communication by duplicating the sequence generation mechanism. This paper addresses constructions of frequency hopping pattern sets meeting the above criteria. Recently Komo and Liu [9] have described frequency hopping patterns from maximal-length sequences ( -sequences) . In [9], the authors make note of a sequence over GF , which is constructed by grouping two binary over GF -sequences, sharing many properties of -sequences, and . It is indeed an yet not an -sequence over GF GF and rightly not an sequence over
0018–9448/98$10.00 1998 IEEE
UDAYA AND SIDDIQI: FREQUENCY HOPPING PATTERNS DERIVED FROM POLYNOMIAL RESIDUE CLASS RINGS
sequence over GF . Our approach characterizes all such obtainable sequences by appropriately grouping -sequences over finite fields. A summary of major results obtained in this paper is presented briefly in the following subsection. In Section II, and its Galois relevant properties of a polynomial ring extension ring are given. In subsequent sections we describe the families of sequences defined in Section I-A in detail and compute their correlation and linear complexity properties. A. Major Results We develop the Galois ring theory for local polynomial residue class rings and use the properties of them to construct sequences. We restrict our attention only to local rings, since in general, any semilocal ring can be expressed as direct sum of local rings. Moreover, elements of the local rings considered in this paper have a representation analogous to -adic type representation which is central in defining sequences (refer to (5)). The results of the paper can be conveniently classified into linear and nonlinear constructions. 1) Linear Constructions: We generalize construction of (maximal length)-sequences over GF to the ring by making use of trace functions defined over Galois rings of . for greater than . The period of these sequences is These sequences are then used to construct optimal families of frequency hopping patterns. The optimality here refers to [11] (See the the Lempel and Greenberger bound on Appendix). These constructions are analogous to those given in [11] for -sequences over finite field GF . The size of , where . When is equal the alphabet can be to , we obtain one-coincidence sequences. We consider only sequences which are not always zero divisors since they are isomorphic to some -sequences which are not always zero divisors. We find weight distributions of -sequences which are not always zero divisors. 2) Nonlinear Constructions: These sequences are nonlinear in the sense that sequences in a family are not closed under pointwise ring addition. This implies that the LC of sequences derived from an th-degree Galois extension ring (corresponding linear sequences is always greater than have LC less than or equal to ). These sequences are of prime importance in secure communications where low LC of sequences renders the system vulnerable to jamming attacks. In this paper, we generalize the algebraic construction of binary GMW sequences given by Scholtz and Welch [16]. The GMW sequences are equivalent to cyclic difference sets of Gordon, Mills, and Welch [2]. We follow the approach of Siegenthaler and Forre [17] to generalize the GMW sequences. In [17], a generalized linear complexity enhancement procedure for constructing field sequences using permutation polynomials is given. When the permutation polynomial used is a monomial an integer, we get as a special-case binary GMW sequences of [16]. We generalize the procedure of Siegenthaler and Forre to rings by using a generalized permutation mono. The generalized permutation polynomial mial over GR , where is an integer such that is will be denoted as . We call our sequences Generalized relatively prime to
1493
GMW (GGMW) sequences. For every family of -sequences, we define a family of GGMW sequences. The properties of GGMW sequences are then related to their corresponding -sequences. A subset of GGMW sequences is identified meeting the Lempel–Greenberger bound on Hamming correlations [11]. The linear complexity of these sequences is shown to be equal to their corresponding residue GMW sequences. The computations of field GMW sequences are considered in [16] and [17]. The LC of field GMW sequences depends on the type of monomial permutation used in constructions [16], [17]. In general, we can obtain large LC using these constructions [16], [17]. After preparation of the initial draft of this paper, we become aware of the work in [1] where GMW sequences over GF , a prime, is considered. In [1] it is shown that will result in large LC. All GMW constructions over GF these GMW sequences when defined over appropriate rings considered in this paper, will also lead to large LC sequences. The comparison of various frequency hopping constructions is given in Table I. II. RING PRELIMINARIES In this section, we give necessary mathematical results and its Galois extension ring. These concerning the ring rings are analoguous to Galois extension of integer rings studied in [5], [18], and [19], and they share many of the properties of integer rings. Since integer rings are discussed in the literature extensively, we here concentrate only on essential , which is a module of properties. Unlike the integer ring , here is a vector space of dimension dimension over over GF [7], [15]. The vector space structure of these rings plays a vital role in lifting irreducible polynomials from their ground field. Definition 1: Let GF over GF , a prime, and of degree over GF , in GF generated by
be the ring of all polynomials be an irreducible polynomial . Then is defined as quotient ,
GF Alternatively, is the set of all polynomials of degree closed under polynomial addition and multi. As the elements of the ring are plication modulo polynomials, the ring admits the standard basis representation is a basis). ( GF Note that rings do not admit this kind of representation. We give now representations equivalent of -adic represenelements [6]. We have a natural homomorphic tation of . mapping, from to its residue field RF GF RF by . It is easy to verify Define that the elements in the set are linearly independent over RF and hence constitute a basis. can be represented uniquely as Thus any element RF
1494
IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 44, NO. 4, JULY 1998
PROPERTIES
OF
TABLE I FREQUENCY HOPPING SEQUENCE CONSTRUCTIONS
The ’s in the above representation are obtained from recursively by Euclid’s algorithm
Notice that in the case of , the cyclic component of the group of units is not closed under the addition operation of . Here, we have the following important lemma.
and
is isomorphic to residue field Lemma 1: The set RF and is also a subspace of . Thus the set is a subring over . is cyclic, the set satisfies Proof: Since, the multiplicative axiom of a field. For every , since the characterisic of is . This and . Thus implies is closed under addition which proves the lemma.
for We give one more representation by making use of the structure of group of units and properties of ideals in . This representation aids us to define a Galois extension ring by lifting an irreducible polynomial over RF to the ring. Since is a power of an irreducible the modulus polynomial polynomial, it is also easy to see that is a local ring [4], [7]. are generated by elements , Hence all the ideals of , and they are denoted by . They are of the . The ideals satisfy the form chain property whenever
(2)
represents set theoretic inclusion. The ideal where is the maximal ideal and gives all the zero divisors of the ring. can be represented as Hence, any zero divisor
where
is a unit element of
(5) . We shall denote (5) as the ideal basis where representation. From now on, we will omit the indeterminate from the representation. Thus any element is simply expressed as
(3)
of is given by the direct product of The group of units and ; , where two groups is a cyclic group of order and is an [7]. In view of the above, any Abelian group of order unit element can be written as a product of two elements, one and the other from . drawn from for any
We refer to the subring isomorphic to GF as throughout the paper. We are ready to give another using the subfield which is also a representation of and a basis . subspace of can be expressed as Any element
(4)
(6) Thus
can be written as (7)
Note that the above representations are due to the fact that are subspaces of . both RF and
UDAYA AND SIDDIQI: FREQUENCY HOPPING PATTERNS DERIVED FROM POLYNOMIAL RESIDUE CLASS RINGS
ELEMENTS
1495
Definition 2: The Galois ring of denoted as GR is defined as , where is a basic monic irreducible polynomial of degree over
TABLE II OF R IN EXAMPLE 2
The basic monic irreducible polynomial of degree over can be lifted from a monic irreducible polynomial over RF . The trick is to consider a which is isomorphic to GF instead of RF. Since monic irreducible polynomial over is a subring, any irreducible polynomial over the subring is obviously irreducible over the ring. Thus the lift can be to . Then obtained by defining a mapping from GF under the mapping a monic irreducible polynomial becomes a basic monic irreducible over . Example 3. Irreducible polynomial over GF Polynomial where GF
is a primitive irreducible over , . In this case the set is the subfield isomorphic to GF . , applied on the coefficients Then a mapping from yields a corresponding irreducible polynomial over . Thus is a primitive irreducible polynomial over . Hence, the set of elements
is isomorphic to GF
Example 1: The ring GF . The zero divisors of
, where are
where is primitive in ; . The set is GF GF . The basis elements the subfield are given by . of the subfield , where Example 2. Representations of : Elements of RF and of the ring are given by the sets and respectively. The elements of the ring in all the three representations are given in Table II. The ideal basis . is given by the set A. Galois Extension Rings of The method of constructing Galois ring of runs similar to . Let be the ring the construction of Galois rings over of polynomials over . We extend the homomorphic mapping on to polynomial reduction mapping in the obvious way (8)
. Similarly, the polynomial is a monic basic primitive irreducible
. over GF is a module over . Like Galois fields GR GR is unique for a given [15]. When , GR is equal and when it is GF . to to define nonWe need the subring structure of GR resemble Galois linear sequences. In this respect GR fields. For every positive integer , there is a natural inclusion into GR . In other words, every subring of GR is of the form GR for some divisor of . of GR Conversely, for every divisor of , there is a unique subring . The group of units of which is isomorphic to GR denoted by GR is given by a direct product GR of two groups GR where is a cyclic group of order and is an [7]. On the lines of Lemma 1, Abelian group of order is a field of order . it is easy to show that the set . Thus like the representation (7) This is denoted by GF for , we have for GR GR GF
GF
Hence, any element as
GF GR
GF can be uniquely expressed (9)
A polynomial irreducible in
is a basic irreducible if is ; it is monic if its leading coefficient is .
are of the form The elements of GR . From (9), the elements of
, where are given by
1496
IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 44, NO. 4, JULY 1998
the set (10) over its interThe Galois automorphism group of GR , where divides is cyclic of order mediate subring GR generated by the Frobenius map defined by
where is as in (9). When , the above Frobenius map generates Galois group over [15]. Using the automorphisms given above, we define below generalized trace functions to its intermediate subrings which map elements of GR where divides . They are given by GR
Moreover, because of the chain property of the ideals in (refer to (2)), the ideals are isomorphic to GF Thus in this paper, we deal with only -sequences in . A. Trace Representations of
-Sequences over
From the previous section we know that GR is , where is a primitive basic generated as irreducible polynomial over . Let be a primitive generator present in GR . of has a unique trace Theorem 1: Every -sequence over , where representation given by GR and is a primitive root of and belongs to . Proof: Direct substitution shows that all sequences of this form satisfy the linear recurrence (16). A simple counting then shows that all these sequences in fact exhaust the family.
(11) GR . The above trace function is the generalwhere ization of trace function defined in [16] for finite fields. Like their counterparts in finite fields, the trace functions satisfy the following properties:
GR For any fixed
of GR
has exactly
for all
(12)
GR
(13)
and
From the trace description, it follows that the -sequences equal to the multiplicative are periodic with period . When is a unit, the corresponding sequences order of can be partioned into cyclically distinct equivalent classes in GR . By using the according to cosets of and (10), structure of group of units GR are given by the set . all -sequences in are given by the Hence from (10), all -sequences in set
, the equation
where
solutions in
(14) (15)
III. LINEAR CONSTRUCTIONS: FAMILIES MAXIMAL LENGTH SEQUENCES OVER
(17)
From the above decomposition, the number of sequences in is given by order of which is equal to . , an -sequence , using ideal Thus for basis can be written as
OF
In this section, we generalize the construction of (Maxto the ring . We imal length)-sequences over GF consider basic irreducible primitive polynomials over whose homormorphic projections under the mapping (refer (8)) are also primitive irreducible polynomials over the residue field . Specifically, let RF which is isomorphic to GF
be a primitive basic irreducible polynomial of degree in . Consider th-degree linear recurrence over having characteristic polynomial (16) as the set of all We define an -sequence family over satisfying (16) with the polynomial sequences dividing . We shall denote as the set of sequences which contains not all zero divisors. From (3), containing only zero divisors can be a sequence , where a sequence in . expressed as
We identify sequences as component sequences of the the component sequences,
with
-sequence
and
over GF . By using (13), are given by
are as in (17)
(18)
We require the following definition. as in (9) be equal to GF . Then, let be a formed by placing together matrix over of dimension elements as columns of . Then the rank of is defined as the rank of matrix over . number Definition 3: Let
Let
, where
GR
as in (17). Then, we can identify independent positions in
UDAYA AND SIDDIQI: FREQUENCY HOPPING PATTERNS DERIVED FROM POLYNOMIAL RESIDUE CLASS RINGS
1497
We need the following two properties of finite field -sequences. be an -sequence over Lemma 3: Let of period , and let , be GF , then the set of all an -tuple given by -tuples are distinct and the set accounts for barring an all-zero tuple. all -tuples over GF
TABLE III
m-SEQUENCES OF S 3 (f ); f = 1 + x + x3 , OVER R = GF (2)[ ]=(1 + )2
shifts of -sequences are closed Lemma 4: All shift under point-wise addition, i.e., the set of all sequences and an all-zero sequence forms an Abelian group under point-wise addition. To compute Hamming autocorrelation properties of sequences, we use the fact that component sequences over are -sequences over subfield GF and the linear property of -sequences over . Lemmas 5–8 establish autocorrelation properties of -sequences over and we can relate the rest of the dependent positions as
,
(19) is a zero divisor, then can be written When for some nonzero element in . Then, from (13), as is given by
which is isomorphic to a field -sequence as . Thus it is clear that the number of distinct versions of -sequence families is equal to the number of distinct -sequences over the field . The number of distinct is given by [13] , sequences over of order is the number of integers where is Euler’s function; less than and relatively prime to . Hence, the number of is given by distinct -sequence families over (20) , over All -sequences of GF are given in Table III. In the trace represenof GR tation they are generated by belonging to such that . The elements of are represented by -tuples over GF . For example, the symbol (11) represents of . B. Hamming Correlation Properties Definition 4: Given a sequence and an element of , as the number of occurences of the element we define in within its one period length. The following lemma is a direct consequence of Definition 4 and 1. and be two sequences over , then Lemma 2: Let is given the Hamming correlation between them, , where and by represents pointwise subtraction of component sequences in
Lemma 5: Lemma 4 is true even for -sequences over Proof: The th shift an -sequence is given . Since the set is closed under addition, by is shift of with the point-wise difference which belongs to . Hence all shifts of form an Abelian group under point-wise subtraction. Lemma 6: Let be an -sequence over , and , , the set of column vectors derived then for each from component sequences of
has a column rank . Proof: Since
is , the ideal basis components of have a rank over (17). to , the column Since the trace function is linear from . The rank cannot be less than , otherwise, rank has to be using (19) and (18) would amount to expressing is less than . saying Lemma 7: For any -sequence over of period , , with , we have are linearly a) Component sequences independent over . is identically equal to zero. b) No element are distinct and appear only c) All the elements of for all nonzero . once in one period, i.e., , ; d) The set of -tuples accounts for all -tuples over . Proof: The result a) follows from Lemma 6. The result implies the vectors b) is true, otherwise,
have rank , contradicting Lemma 6. If any two elements are identical, say and , then from Lemma 5 of and , the pointwise difference of two sequences , yield an -sequence which has a zero element thus contradicting b). Hence, c) is true. The result is and there d) follows from c) since the period of nonzero -tuples over . are only
1498
Lemma 8: Let
IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 44, NO. 4, JULY 1998
be an
-sequence with , and
. Then, , for
. Proof: Consider ideal basis representation of elements , then for , where of . From Lemma 6, we know that column rank of is and let be linearly independent component sequences over . Then , since the rest of the bits in are linearly . The rank number cannot related to satisfies a linear recurrence of order . exceed since with whose Now consider a sequence are the same component sequences in positions . Then there as those of ; tuples in such that are exactly . We have from Lemma if and if . 7 (Part d) if and Hence, if . Theorem 2: Let , Then
be an
-sequence over
, with
if if Proof: The case of is obvious. The case of follows from Lemmas 2 and 8. C. Optimal Families of Sequences over Associated with every -sequence , we construct a family of sequences which can be used to construct frequency hopping patterns. The number of sequences in a family deoccurring in pends on the number of distinct elements of . Families are optimal in the sense that they meet Lempel (see the Appendix). We give and Greenberger bound on a definition for the number of distinct elements in Definition 5: The Trace Image of an defined as the set of distinct elements in
-sequence, .
is
By using (9) and (19) we can give characterization of Trace in terms of representation of . Let be as given Image of , then the Trace Image of in (17) and (19) with is given by the set
where each
takes all values from and are linearly related to as in . (19). Hence, the cardinality of the set is given by be an -sequence, then for every Let belonging to Trace Image of , we define a sequence given by , . Since the cardinality of Trace is , we have such sequences. Then a Image of sequences associated with is given by the family of , Trace Image of . We denote set of sequences . such a family by
Theorem 3: Hamming correlation between any two sequences and belonging to the family , is given by whenever whenever whenever whenever
and and
Proof: The first two results follow from Theorem 2. Let . If , then from Lemma 2 is given , where and—represents by is poinwise subtraction. From the definition of sequences, which is not equal to . a sequence with entries only is . Similarly, if , is given Hence, , where . The weight by is the same as , where which is an -sequence. Then the result follows from Lemma 8. From the Appendix, the correlation parameters are indeed optimal. Corresponding to each -sequence , we have a family of . From the construction of hopping patterns derived from it is clear that the size and properties of depend . Thus the number of frequency hopping families of on any specified size depends on rank number distribution of be the number of -sequences in sequences in . Let such that is equal to . All these sequences, result in . From (20), we know a frequency hopping family of size number of distinct families of period that there is an ; . Thus the number of families derived from of frequency hopping patterns of size is given by . Lemmas 9 and sequences in . 10 gives an expression for computing is equal to the number of matrices Lemma 9: of rank with a condition that the first column over GF , where stands for transpose. is given by and Proof: The proof follows from the definitions of the rank number. Lemma 10:
where
is given by
are chosen positions and are non chosen positions in th combination of and is the number of chosen positions such that . , , and be assumed as in the Proof: Let statement of the Lemma. We count distinct matrices of rank with the first column given by by giving a method of constructing such matrices. Since the first column of the matrix is fixed, each matrix is formed by selecting other linearly independent column positions among remaining columns to make a matrix of rank . This choice ways. of linearly independent positions can be done in . We select independent Consider a th combination of
UDAYA AND SIDDIQI: FREQUENCY HOPPING PATTERNS DERIVED FROM POLYNOMIAL RESIDUE CLASS RINGS
TABLE IV WEIGHT DISTRIBUTION OF m-SEQUENCES IN
S 3 (f )
1499
TABLE V
#(r; ) FOR r = 2; 3; 4; 5; 6
TABLE VI FREQUENCY PATTERNS OF FAMILY
column positions as chosen positions and dependent column positions as nonchosen positions . These independent column positions in can be filled by vectors over different ways. For each such configuration, dependent columns are filled with vectors as follows. Each is filled by taking linear dependent column position, combinations of vectors in independent column positions such that . This way, we avoid taking linear sums such that . This will of independent columns not affect the counting of distinct matrices because, if in a is formed as a linear sum of chosen position, say matrix, , such that , then this matrix is also counted whose chosen positions include in th combination of and all chosen positions of the th combination except . Thus with the method above we would be counting only distinct matrices. Hence, the number of dependent vectors is . Repeating this for all possible for column nonchosen positions, for th combination, dependent positions different ways. Thus for th can be filled up in combination the number of matrices possible is
Summing over all the combinations yields the result. Weight distribution of -sequences in is computed from rank number distributions since weight structure of an -sequence is completely determined from (refer to Lemma 8). Table IV gives the weight distribution. When , , and , Table V lists for different values of . Example 4: A family of frequency hopping patterns of GF . length derived from -sequences over such that , Sequences are generated by GR . Patterns are constructed from an -sequence ; is given by
S (
= (1) + (2 ) + () 2 )
Patterns of the family are given in Table VI. Pattern symbols are represented by decimal numbers of is represented by . in the range – ; IV. NONLINEAR CONSTRUCTIONS: LARGE LINEAR COMPLEXITY SEQUENCES OVER In this section, we generalize the algebraic construction of binary GMW sequences [16] by following the approach of Siegenthaler and Forre [17]. We generalize the procedure of Siegenthaler and Forre to rings by using general. We call our ized permutation monomials over GR sequences Generalized GMW (GGMW) sequences. For every -sequence family, we define a family of GGMW sequences. The properties of GGMW sequences are then related to their corresponding -sequences. A subset of GGMW sequences is identified meeting Lempel–Greenberger bound on Hamming correlations. The linear complexity of these sequences is shown to be equal to their corresponding residue GMW sequences. A. Permutation Monomials over GR Permutations on finite fields have polynomial representations while the same is not true in the case of finite residue , class rings [8], [12]. The polynomial substitution,
1500
IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 44, NO. 4, JULY 1998
where is a polynomial of degree greater than , cannot be a permutation on Galois rings due to the presence of zero divisors. Using the ideal basis representation, we generalize the permutation monomials. For any GR we define the permutation
as (21)
. The permutation over GR where collapses to permutation monomial over the subring . on elements of Throughout this section, when applying GR , we write instead of Lemma 11: A generalized monomial is a permutation on GR if and only . if (21) Proof: The result follows from the definition of which is a cyclic group of and the structure of units in order
Proof: Consider the elements of intermediate sequence of the -sequence given by , for all . The monomial permutation permutes these . This implies that ’s of (23) are some elements of . Hence, permutation of elements of -sequence is equal to . From Lemma 12, it is clear that weight distribution of a family of GGMW sequences is the same as that of sequences. But, the Hamming autocorrelation properties of GGMW sequences are not related to the weight distribution is a nonlinear permutation on alone in view of the fact that . We consider a subset of GGMW sequences having GR optimal Hamming autocorrelation properties. and be the Abelian and cyclic component Let groups of the group of units of subring GR GR . Let , a subset of GGMW sequences, be given , . Using (10), can be written by , where . as Then from (21) and the trace property (13), the th-component , , sequence of is given by
B. GGMW Sequences be the Galois extension ring of obtained Let GR , where by the primitive basic irreducible polynomial . Let be a primitive element in of GR . We define GGMW sequences as set of sequences having the following trace representation:
(24) and , are as in (22). where In the the next section we compute autocorrelation properties of sequences in . C. Correlation Computation
where GR . As in the case of -sequences, we deal with only the set of sequences not always containing zero divisors, GGMW . Any sequence which has entries only from zero divisors is isomorphic to some sequence in GGMW . It is easy to verify cyclically inequivalent sequences of that there are in GGMW . We consider indices of period . Using the same arguments sequences to be from as given for -sequences, sequences in GGMW are given . By using the ideal representation of by the set the above set is given by
where Thus associated with every a GGMW sequence
’s
, of GR given by
where
, and
,
by
be a GGMW sequence in . Let , be decimated sequences of given ; , where
Lemma 13: Each decimated sequence is an -sequence of period given by where Proof: Follows from the definition of and Let from
of
,
,
be the point wise subtraction of th shift , then decimated sequences of are given by
(22) , we have (23)
As in the case of sequences
Let
-sequences, we associate component over given by
are as in (22).
be a GGMW sequence over . Then Lemma 12: Let is equal to , the number of occurrences of symbol in the -sequence
where Lemma 14: The decimated sequence , of is given by an -sequence of period , where
Proof: From the definition of
and
Lemma 15: is the point-wise subtraction of from th shift of .
;
. , where -sequence
UDAYA AND SIDDIQI: FREQUENCY HOPPING PATTERNS DERIVED FROM POLYNOMIAL RESIDUE CLASS RINGS
Proof: When , the result is trivially true since both and are all-zero sequences. Let . From the , definition of -sequences, th decimated sequence of , is given by , where
The expression and are simultaneously zero or which is the order nonzero since is relatively prime to . Thus is a some permutation of . of the The result then follows immediately. Thus of has been related to weight properties of -sequences which have been computed in Theorem 2. The following lemma is an immediate consequence of this relation. , then
Lemma 16: Let given by
is for for
Theorem 4: Let
be in
, with
, Then
1501
sequences is constructed and the correlation properties depend on the rank number of . Hence, corresponding to a distinct different frequency hopping families family there are . Since the monomial defined is the simple of size , the vector extension of monomials over residue field number of distinct GGMW families is equal to the number of distinct GMW sequences over subfield . By following arguments similar to those given in [16], the number of distinct GGMW families can be shown to be equal to . Thus the number of frequency hopping , , is given by sets of size
E. Linear Complexity of GGMW Sequences Definition 6: The linear complexity (LC) of a sequence of period over , is defined as the least number of stages required to generate the sequence using a linear feedback shift register (LFSR). with initial loading An LFSR of length generates if it follows a linear recursion
if
(25)
if Proof: From Lemma 16 and Lemma 2. D. Optimal Families of Sequences from GGMW Sequences Associated with every sequence in , we construct a family of sequences which can be used to construct frequency be a GGMW in , then for hopping patterns. Let every belonging to Trace Image of , we define a sequence given by , . Since the cardinality is , we have such sequences. of Trace Image of sequences associated with is given Then a family of , Trace Image of . We by the set of sequences . denote such a family by Theorem 5: The Hamming correlation between any two and belonging to the family , sequences is given by whenever whenever whenever whenever
and and
Thus the family is optimal. Proof: The first two results follow from Theorem 4. , is given by which When is the all-zero sequence. For , is zero, since is given by , where from Lemma 2, . can be written as , where . The result then follows is From Lemma 16. From the Appendix, the family optimal according to the Lempel and Greenberger bound. Now it remains to compute the number of families. , here also corresponding to each GGMWSimilar to belonging to , a family of frequency hopping sequence
are the tap coefficients of the LFSR. where given by The associated connection polynomial is . Let
be a polynomial associated with the sequence . Then it is easy to verify that an LFSR with connection polynomial generates periodic extension if and only if (26) For sequences over a field of characteristic , Blahut’s theorem greatly facilitates the computation of the LC [14]. It states that the LC of a sequence is equal to the number of nonzero terms in the discrete Fourier transform representation of the sequence. We give an extension of the Blahut’s theorem to be a primitive compute LC of sequences over . Let belonging to unit element of multiplicative order ; there always exists such an (see Sectiion II). GR of period can Then any sequence be represented as (27) where
’s are given by (28)
and may be recognized as Fourier transform coefficents of . The representation (27) is unique for sequences over since is relatively prime to characteristic of equal to .
1502
IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 44, NO. 4, JULY 1998
TABLE VII
FREQUENCY PATTERNS
OF
G ;
Theorem 6: The LC of a sequence over is equal to a number of nonzero terms appearing in the Fourier transform representation of in (27), i.e., LC
cardinality of
Proof: Let be nonzero positions in the Fourier representation of . This means that are nonzero. Now choose
Then from (26) this implies that LFSR with and consequently LC of is
generates
Theorem 7: Let be a GGMW sequence associGR . Then the LC of is equal to the ated with LC of its corresponding sequence over residue field (sequence by taking modulo on each symbol of ). obtained from is determined by Proof: From Theorem 6, the LC of expanding as in (27) and counting nonzero coefficents in the expansion. Now consider the th-component sequence of and its generalized Fourier transform. From (28), is nonzero is nonzero, . The nonzero if and only if one of transform coefficient positions for all component sequences are the same since the same monomial is used to permute intermediate ring elements. Thus the number of nonzero is equal to its residue sequence. transform values of Theorem 7 only says that the LC of GGMW sequences is the same as their corresponding GMW sequences over the field. The computations of field GMW sequences are considered in [16] and [17]. The LC depends on the type of monomial permutation used to permute the intermediate field [16], [17]. of period For example, GMW sequences over GF require a permutation monomial over GF given by , is relatively prime to . Then, the LC is given by , where is the number of ’s present in a binary representation of [16], [17]. By using appropriate choices of the intermediate subfield and permutation monomials, the LC of GMW sequences can be significantly enhanced. As a consequence of Theorem 7, the LC of GGMW sequences over GF of period is given by LC where of
is number of ’s present in binary representation
+ () 2 + () 3
= (1) + ( )
Remark: After the preparation of the initial draft of the paper, we become aware of the work in [1], where the GMW sequences over GF , a prime, are considered. In [1] it will result is shown that GMW constructions over GF in large LC. All these GMW sequences when defined over appropriate rings considered in this paper, will also lead to large LC sequences. GF ; Example 5: A GGMW sequence over GR ; , , , such generated by . The vectors over GF in simple brackets that represents symbols from . A GGMW sequence associated GR , is given by with
The LC of the above sequence is
.
Example 6: A family of frequency hopping patterns of derived from a GGMW sequence over length GF . The GGMW sequence is generated by such that , GR . A permutation is polynomial used to permute the intermediate ring GR . Patterns are constructed from a GGMW a monomial , . is sequence . The number of patterns in the family is 4. The elements of are represented by -tuples over GF , for example, represents . The GGMW sequence is given by
Patterns of the family GGMW are given in Table VII. Pattern elements are repre; of is represented using decimal numbers . sented by decimal number
UDAYA AND SIDDIQI: FREQUENCY HOPPING PATTERNS DERIVED FROM POLYNOMIAL RESIDUE CLASS RINGS
V. CONCLUSION Since the first version of the paper in 1993, many results have appeared. Galois rings concerning Galois rings of considered in this paper are Galois extensions of polynomial residue class rings. They form another class which provides a general setting to construct sequences or codes. We have extended to rings two important field sequence constructions (namely, - and GMW-sequences). We believe the rich structure of these Galois rings may lead to many new constructions. have been introduced to conRecently, codes over struct lattices [3]. This ring is a particular case of polynomial residue class rings introduced in this paper. Our theory can also . be applied to study codes over This ring plays the role of the -adic ring considered in [6].
For become [11]
and
1503
, the above ineqalities
(30) (31) ACKNOWLEDGMENT The first author wishes to thank Prof. Kathy Horadam, Dr. Alexis Bonnecaze, and anonymous referees for their useful comments which significantly changed the presentation and structure of the paper. REFERENCES
APPENDIX
M
LEMPEL–GREENBERGER BOUNDS ON HAMMING CORRELATIONS Let be a family of sequences of period defined over . The Hamming correlation an arbitrary alphabet of size is as given in (1). We have between any two sequences following two parameters concerning Hamming correlations:
, either
or
A good sequence design is the one which minimizes . be a sequence over of period and Let be the weight vector associated with , where is the number of th symbol of appearing in . Theorem (Lempel and Greenberger [11]): Let and be , and two sequences of period over an alphabet of size and be their corresponding weight vectors. let Then for a family of sequences
where
is the least nonnegative residue of
mod
, and (29)
where
Note that we may assume . Furthermore, the right-hand side of (29) is minimized whenever the following conditions are satisfied. . • ’s are in increasing order • . . •
[1] M. Antweiler and L. Bomer, “Complex optimal sequences over GF (P ) with a two-level autocorrelation function and a large linear span,” IEEE Trans. Inform. Theory, vol. 38, pp. 120–130, 1992. [2] W. H. Mills, B. Gordon, and L. R. Welch, “Some new difference sets,” Canadian J. Math., vol. 14, pp. 614–625, 1962. [3] C. Bachoc, “Application of coding theory to the construction of modular lattices,” J. Comb. Theory, Ser. A, 1997. [4] H. Bhat, “Linear sequential systems over residue class polynomial rings: Theory and applications,” Indian Inst. Technol., Kanpur, India, Ph.D. dissertation, 1985. [5] S. Boztas, R. Hammons, and P. V. Kumar, “4-phase sequences with near-optimum correlation properties,” IEEE Trans. Inform. Theory, vol. 38, pp. 1101–1113, 1992. [6] A. R. Calderbank and N. J. A. Sloane, “Modular and p-adic cyclic codes,” Des., Codes Cryptogr., vol. 6, pp. 21–35, 1995. [7] H. L. Clasen, “Studies of the multiplications in GF (q )[x]=(a(x)),” Delft Univ. Technol., Delft, The Netherlands, Ph.D. dissertation, 1978. [8] A. J. Kempner, “Polynomials and their residue systems,” Trans. Amer. Math. Soc., vol. 22, pp. 240–266, 267–288, 1921. [9] J. J. Komo and S. C. Liu, “Maximal length sequences for frequency hopping,” IEEE J. Select. Areas Commun., vol. 5, pp. 819–822, 1990. [10] P. V. Kumar, “Frequency hopping code sequence designs having large linear span,” IEEE Trans. Inform. Theory, vol. 34, pp. 146–151, 1988. [11] A. Lempel and H. Greenberger, “Families of sequences with optimal hamming correlation properties,” IEEE Trans. Inform. Theory, vol. IT20, pp. 90–94, 1974. [12] R. Lidl and H. Niederreiter, Finite Fields (Encyclopedia of Mathematics and its Applications), vol. 20. Cambridge, U.K.: Cambridge Univ. Press, 1984. [13] R. A. Scholtz, M. K. Simon, J. K. Omura, and B. K. Levit, Spread Spectrum Communications, vol. 1. Computer Sci., 1985. [14] J. L. Massey and T. Schaub, “Linear complexity in coding theory,” Coding Theory and Applications, Lecture Notes in Computer Science, vol. 311. Berlin, Germany: Springer-Verlag, 1988. [15] B. R. McDonald, “Finite rings with identity,” in Pure and Applied Mathematics. New York: Marcel Dekker, 1974. [16] R. A. Scholtz and L. R. Welch, “GMW sequences,” IEEE Trans. Inform. Theory, vol. IT-30, pp. 548–553, 1984. [17] T. Siegenthaler and R. Forre, “Generation of binary sequences with controllable complexity and ideal r -tuple distribution,” EUROCRYPT85, Lecture Notes in Computer Science, vol. 219. Berlin, Germany: Springer-Verlag, 1985, pp. 15–23. [18] P. Udaya, “Polyphase and frequency hopping sequences obtained from finite rings,” Indian Inst. Technol., Kanpur, India, Ph.D. dissertation, 1992. [19] P. Udaya and M. U. Siddiqi, “Optimal quadrphase sequences derived from maximal length sequences over Z4 ,” submitted to J. Appl. Algebra Engg. Commn. Comput. New York: Springer-Verlag, 1995. [20] , “Optimal biphase sequences with large linear complexity derived from sequences over Z4 ,” IEEE Trans. Inform. Theory, vol. 42, pp. 206–216, 1996.
