# Construction of Optimal Sets of Frequency Hopping Sequences

Authors: Bin Wen
Journal: ISRN Combinatorics
 (2013)

---

## Abstract

Frequency hopping spread spectrum and direct sequence spread spectrum are two main spread coding technologies. Frequency hopping sequences are needed in FH-CDMA systems. In this paper, a construction of optimal sets of frequency hopping sequences is presented. The construction is based on the set-theoretic characterization of an optimal set of FH sequences.


---

## Body

## 1. Introduction

Frequency hopping spread spectrum and direct sequence spread spectrum are two main spread coding technologies. Frequency hopping sequences are an integral part of spread-spectrum communication systems such as FH-CDMA systems (for a description of such systems, see [1]). In modern radar and communication systems, frequency-hopping (FH) spread-spectrum techniques have become popular (see [2], for example).Assume thatF={f0,f1,…,fm-1} is a set of available frequencies, called an alphabet. Let 𝒳(v;F) be the set of all sequences of length v over F. Any element of 𝒳(v;F) is called a frequency hopping sequence (FHS) of length v over F. Given two FH sequences, X=(x0,x1,…,xv-1) and Y=(y0,y1,…,yv-1), we define their Hamming correlation HX,Y(w) to be
(1)HX,Y(w)=∑0≤i≤v-1h[xi,yi+w],
where 0≤w<v if X≠Y and 0<w<v if X=Y, and where
(2)h[x,y]={1,ifx=y,0,otherwise,
and all operations among position indices are performed modulo v. If X=Y, HX,Y(w) is the Hamming autocorrelation. If X≠Y, HX,Y(w) is the Hamming cross correlation.


## 2. Lower Bounds on the Correlations of FHSs

FH sequences for FH-CDMA systems are required to have good Hamming correlations and large linear span [3]; the linear span is defined to be the length of the shortest linear feedback shift register that can produce the sequence. FH sequences’ design normally involves six parameters: the size m of the frequency library F, the sequence length v, the family size N of the subset 𝒮⊂𝒳(v;F), the maximum out-of-phase Hamming autocorrelations Ha, the maximum Hamming cross correlations Hc, and the linear span. It is generally desired that the family 𝒮 of FH sequences has the following properties: (1)
the maximum out-of-phase Hamming autocorrelationsHa should be as small as possible,(2)
the maximum Hamming cross correlationsHc should be as small as possible,(3)
the family sizeN=|𝒮| for given Ha, Hc, M, and v should be as large as possible,(4)
the linear span should be as large as possible.In order to evaluate the theoretical performance of the FH sequences, it is important to find some theoretical bounds for these parameters. Givenm, v, and N of 𝒮, Lempel and Greenberger [4] and Peng and Fan [5] derived lower bounds on Ha and Hc of FH sequences in 𝒳(v;F). We restate their results in this section, which will be used later as the criteria to determine whether the new FH sequences constructed in this paper are optimal or not.For any single FH sequenceX∈𝒳(v;F), let Ha(X)=max1≤t≤v-1{HX,X(t)} be the maximum out-of-phase value of HX,X(t). If Ha(X*)≤Ha(X) for all X∈𝒳(v;F), that is, if the value Ha(X*) is the least among all FH sequences of the same length v and over the same frequency library F, X* is called an optimal FH sequence. Lempel and Greenberger [4] developed the following lower bound for Ha(X).Lemma 1 (see [4]).
For every FH sequenceX of length v over a frequency alphabet F of size m. One has
(3)Ha(X)≥(v-ϵ)(v+ϵ-m)m(v-1),
where ϵ is the least nonnegative residue of v modulo m.Corollary 2.
For every FH sequenceX of length v over a frequency alphabet F of size m. One has
(4)Ha(X)≥{k,ifm≠v,0,ifm=v,
where v=km+ε with 0≤ε≤m-1.For any given subset𝒮 of 𝒳(v;F) containing N FH sequences, any two X,Y∈𝒮, X≠Y, we write Hc(X,Y)=max0≤t≤v-1{HX,Y(t)}. We define the maximum out-of-phase Hamming autocorrelations Ha(𝒮) and the maximum Hamming cross correlations Hc(𝒮) as
(5)Ha(𝒮)=max{Ha(X):X∈𝒮},Hc(𝒮)=max{Hc(X,Y):X,Y∈𝒮,X≠Y},M(𝒮)=max{Ha(𝒮),Hc(𝒮)}.Peng and Fan [5] developed the following bounds on M(𝒮), which take into consideration the number of FH sequences in the set.Lemma 3 (see [5]).
Let𝒮⊆𝒳(v;F) be a set of N sequences of length v over an alphabet of size m. Define I=⌊vN/m⌋. Then
(6)M(𝒮)≥⌈(vN-m)v(vN-1)m⌉,(7)M(𝒮)≥⌈2IvN-(I+1)mI(vN-1)N⌉.A family𝒮⊆𝒳(v;F) is an optimal set if the Peng-Fan lower bound (2) or (3) in Lemma 3 is met. Let N=m, and we have the following corollary which is a useful tool to check the bound in Lemma 3.Corollary 4 (see [6]).
Let𝒮⊆𝒳(v;F) be a set of m sequences of length v over an alphabet of size m. Then
(8)M(𝒮)≥{a,ifm∣v,a+1,ifm∤v,
where v=am+b with 0≤b≤m-1.A number of authors have made contributions to the construction of optimal FH sequences. Both algebraic and combinatorial constructions of optimal FH sequences have been given (see, for example, [3, 4, 7–11]). Most of them are concentrated on single optimal FH sequences. The purpose of this paper is to present a construction of optimal sets of FH sequences based on the set-theoretic characterization of an optimal set of FH sequences. Throughout what follows, we use (v,m,λ)-FHS to denote an FH sequence X of length v over an alphabet of size m whose Hamming autocorrelation Ha(X)=λ. We also call a set 𝒮 of N FH sequences in 𝒳(v;F) a (v,N,λ;m) set of FH sequences, where λ=M(𝒮).


## 3. Mixed Difference Functions

Fuji-Hara et al. [9] characterized a (v,m,λ)-FHS in terms of partition-type cyclic difference packings. Given a partition 𝒟={D0,D1,…,Dm-1} of Zv into m subsets (called base blocks), we can define a difference function on ℤv*=ℤv∖{0} given by Γ𝒟(w)=∑i=0m-1‍|(Di+w)∩Di|. Let max{Γ𝒟(w)|w∈ℤv∖{0}}=λ. Then 𝒟 is called a (v,K,λ)m-PCDP (partition-type cyclic difference packing). Here, m is used in the notation to indicate the number of base blocks, and K={|Di|:0≤i≤m-1} is the list of the sizes of base blocks. This is to say that a (v,K,λ)m-PCDP is a partition of ℤv into m base blocks which satisfies the following property. For any fixed nonzero residue w∈ℤv, the equation x-y=w has at most λ solutions (x,y) in the multiset union ⋃D∈𝒟‍(D×D).If we label the positions of a(v,m,λ)-FHS X by the elements of ℤv, then, by the above definition, the sets of position indices of m frequencies in X form a (v,K,λ)m-PCDP 𝒟 with Γ𝒟(w)=HX,X(w) for any nonzero w∈ℤv. Conversely, if we label the m base blocks of a (v,K,λ)m-PCDP by the elements of ℤm and identify the frequency alphabet F with ℤm, then the PCDP gives a (v,m,λ)-FHS in 𝒳(v;F).This fact reveals that a single FHS can be constructed by a PCDP. Apparently, the smaller the indexλ of a PCDP the lower the Hamming autocorrelation Ha(X) of its corresponding FH sequence. For an optimal FH sequence, we need to construct a (v,K,λ)m-PCDP so that its index λ is as small as possible for any given value of v and m. Based on Lempel-Greenberger bound on Ha(X) in Lemma 1, Fuji-Hara et al. [9] proved the following result.Lemma 5 (see [9]).
There exists a(v,m,λ)-FHS over the alphabet F=ℤm if and only if there exists a (v,K,λ)m-PCDP in ℤv. Furthermore, this FH sequence is optimal if λ=⌊v/m⌋ for v>m and if λ=0 for v=m.The correspondence between an individual FH sequence and a PCDP can be naturally extended to give a set-theoretic interpretation of a set of FH sequences. LetN be a positive integer. Let 𝒞={𝒟(0),𝒟(1),…,𝒟(N-1)} be a collection of partitions of ℤv into m subsets (called base blocks). Write 𝒟(r)={D0(r),D1(r),…,Dm-1(r)}, 0≤r≤N-1. For any ordered pair (i,j) with 0≤i<j≤N-1, we define a difference function on ℤv given by Γ𝒞(i,j)(w)=∑k=0m-1|(Dk(i)+w)⋂Dk(j)|. For any integer r with 0≤r≤N-1, we define a difference function on ℤv∖{0}, as before, given by Γ𝒞(r,r)(w)=Γ𝒟(r)(w)=∑k=0m-1|(Dk(r)+w)∩Dk(r)|. We refer to these N(N+1)/2 difference functions defined above as mixed difference functions with respect to the given collection 𝒞. Since each partition in 𝒞 determines uniquely an FH sequence, the collection 𝒞 gives a set of N FH sequences in 𝒳(v;F), and vice versa, where the alphabet is regarded as ℤm. For the optimality of the derived set of FH sequences from 𝒞, we define λ(r)=max1≤w<v{Γ𝒞(r,r)(w)}, 0≤r≤N-1, λ(i,j)=max0≤w<v{Γ𝒞(i,j)(w)}, 0≤i<j≤N-1, μ(i,j)=max{λ(i),λ(j),λ(i,j)}, 0≤i<j≤N-1, λ=max{max0≤r≤N-1λ(r),max0≤i<j≤N-1λ(i,j)}. Then 𝒟(r) is a (v,Kr,λr)m-PCDP, according to the previous definition. We say that 𝒞 is a (v,{K0,K1,…,KN-1},{λ0,λ1,…,λN-1};λ)m collection of N PCDPs. It turns out that there exists a (v,N,λ;m) set of FH sequences in 𝒳(v;F) if and only if there exists a (v,{K0,K1,…,KN-1},{λ0,λ1,…,λN-1};λ)m collection of N PCDPs in Zv under our notations. This gives us an interpretation for a set of FH sequences from set-theoretic perspective. As with individual optimal FH sequence, for an optimal (v,N,λ;m) set of FH sequences, we are required to construct a (v,{K0,K1,…,KN-1},{λ0,λ1,…,λN-1};λ)m collection 𝒞 of N PCDPs so that its index λ is as small as possible. Since the index λ of 𝒞 is the same as the Hamming correlation M(𝒮), the Peng-Fan bounds in Lemma 3 can be employed as our benchmarks. As noted in [12], a set of FH sequences meeting one of the Peng-Fan bounds must be optimal. We have the following theorem.Theorem 6 (see [13]).
LetN≥2 be an integer. Then there exists a (v,N,λ;m) set of FH sequences in 𝒳(v;F) if and only if there exists a (v,{K0,K1,…,KN-1},{λ0,λ1,…,λN-1};λ)m collection of N PCDPs in ℤv. Furthermore, this set is optimal if λ meets one of the Peng-Fan lower bounds given in Lemma 3.


## 4. The Construction of Optimal Sets of FH Sequences

To begin with, we state some preparatory knowledge that will be used in our constructions.Letq=ps be a power of prime p, where s is an arbitrary positive integer. Write Trq/p for the absolute trace function from 𝔽q to 𝔽p defined by
(9)Trq/p(x)=x+xp+xp2+⋯+xps-1.We will use the following known result.Lemma 7 (see [14, Corollary 7.17]).
For anya∈𝔽q the number of elements α∈𝔽qm such that Trqm/q(α)=a is qm-1.With the previous preparations, we are now ready to describe our construction of optimal sets of FH sequences.Theorem 8.
Letp be an odd prime and m a positive integer. Define f:ℤpm-1→ℤp by f(x)=Trpm/p(αx), where Trpm/p is the trace function from 𝔽pm to 𝔽p, α is a generator of 𝔽pm*. Define
(10)Dj=f-1(j)={x∈ℤpm-1:f(x)=j},0≤j≤p-1,Dj(r)=Dj+r,0≤j≤p-1,0≤r≤p-1,𝒟(r)={D0(r),D1(r),…,Dp-1(r)},0≤r≤p-1,
where all operations among the subscripts are performed modulo p. Then 𝒞={𝒟(0),𝒟(1),…,𝒟(p-1)} is an optimal (pm-1,p,pm-1;p) set of FH sequences over ℤp of length pm-1. Furthermore, each sequence of the set 𝒞 is optimal with respect to the bound of Lemma 1.Proof.
For anyr with 0≤r≤e-1 and any w∈ℤpm-1*, we have
(11)Γ𝒞(r,r)(w)=∑k=0p-1‍|(Dk(r)+w)⋂Dk(r)|=|⋃k=0p-1‍((Dk+r+w)⋂Dk+r)|=|⋃k=0p-1‍((Dk+w)⋂Dk)|=|{x∈ℤpm-1∣f(x+w)-f(x)=0}|=|{x∈ℤpm-1∣Trpm/p[(αw-1)αx]=0}|=pm-1-1,
where the last equality follows from Lemma 7. Next we will show that Γ𝒞(i,j)(w)=pm-1 for any i,j with 0≤i<j≤p-1 and any w∈ℤpm-1*. For any i,j with 0≤i<j≤e-1 and any w∈ℤpm-1*, we have
(12)Γ𝒞(i,j)(w)=∑k=0e-1‍|(Dk(i)+w)⋂‍Dk(j)|=∑k=0e-1‍|(Dk+i+w)⋂‍Dk+j|=∑k=0e-1‍|(Dk+i+w)⋂‍D(k+i)+(j-i)|=∑k=0e-1‍|(Dk+w)⋂‍Dk+(j-i)|=∑k=0e-1‍|(Dk+w)⋂‍Dk+b|,b=j-i=|{x∈ℤpm-1∣f(x+w)-f(x)=b}|=|{x∈ℤpm-1∣Trpm/p[(αw-1)αx]=b}|=pm-1,
where the last equality follows from Lemma 7. It follows that 𝒞 is a (pm-1,{K0,K1,…,Kp-1},{λ0,λ1,…,λp-1};pm-1)p collection of p PCDPs in ℤp, where λ0=λ1=⋯=λm-1=pm-1-1. By Theorem 6, it derives a (pm-1,p,pm-1;p) set of FH sequences in 𝒳(v;F). For this set, we have N=p and both lower bounds in Lemma 3 are equal to pm-1 by Corollary 4. Hence, it is optimal. Furthermore, each sequence of the set 𝒞 is optimal with respect to the bound of Lemma 1. The proof is then complete.Example 9.
Takep=3 and m=2. It is readily calculated that
(13)D0={2,6},D1={1,3,4},D2={0,5,7}.
We then have
(14)𝒟(0)={D0(0)={2,6},D1(0)={1,3,4},D2(0)={0,5,7}},𝒟(1)={D0(1)={1,3,4},D1(1)={0,5,7},D2(1)={2,6}},𝒟(2)={D0(2)={0,5,7},D1(2)={2,6},D2(2)={1,3,4}},The family𝒞={𝒟(0),𝒟(1),𝒟(2)} is a (v,m,{K0,K1,K2};{λ0,λ1,λ2})3 collection of 3 PCDPs in Z9, where K0={2,3,3}, K1={3,3,2}, K2={3,2,3}, and λ0=λ1=λ2=2. By Theorem 6, it corresponds a (8,3,3;3) set 𝒮 consisting of the following 3 FH sequences over Z3:
(15)X=(2,1,0,1,1,2,0,2),Y=(1,0,2,0,0,1,2,1),Z=(0,2,1,2,2,0,1,0),
with M(𝒞)=3. It is optimal meeting the lower bounds in Lemma 3.



---

*Source: 479408-2013-01-30.xml*