一類新零差分平衡函數(shù)的構(gòu)造及應(yīng)用

(1.福建船政交通職業(yè)學院公共教學部, 福建 福州 350007; 2.福建工貿(mào)學校, 福建 福州 350002)

設(shè)A和B分別是階為n和l的兩個加法群。令f是從A到B的一個映射, 定義Da(x)=f(x+a)-f(x)。若存在一個非負整數(shù)λ，使得對每個非零a∈A有|x∈A:Da(x)=0|=λ成立, 則稱f是一個零差分平衡函數(shù)(簡記，ZDB函數(shù))。 函數(shù)f亦稱作是一個(n,l,λ)-ZDB函數(shù), 其中l(wèi)表示f的象集的大小。

2013年蔡晗等人基于Zeng-Cai-Tang分圓構(gòu)造出參數(shù)為(n,(n+e-1)∕e,e-1)的ZDB函數(shù), 其中n是大于3的奇數(shù)并設(shè)n=pm11pm22…pmkk[1]。 最近, 蔡晗在之前工作的基礎(chǔ)上, 巧妙地運用中國剩余定理又構(gòu)造出一類新的ZDB函數(shù)[2]。 2013年, 丁存生等人構(gòu)造出三類新的ZDB函數(shù)[3]。 基于丁存生教授在二階分圓陪集的這個想法, 查正邦和胡磊給出ZDB函數(shù)的一些分圓構(gòu)造[4]。 2015年, 柯品惠和葉智釩等人基于費馬商給出p2到p的ZDB函數(shù)一般構(gòu)造[5-6]。 2017年, Su從差平衡函數(shù)和最佳三元序列構(gòu)造出兩類具有新參數(shù)ZDB函數(shù)[7]。

1 分圓類

1.1 二階分圓類

設(shè)m=2e-1。存在一個最小正整數(shù)la使得a≡a2la(modm), 記

A(a,la)={a,a×2(modm),a×22(modm),…,a×2la-1(modm)}?m

則A(a,la)是模m包含a的一個二階分圓陪集。其中最小的正整數(shù)la和陪集A(a,la)里的最小正整數(shù)分別稱作這個分圓陪集的大小和陪集首。

若e是一個素數(shù), 則模m的每個非零二階分圓陪集的大小為e, 即la=e。 令A(yù)(a,2e)={A(a,e)∪-A(a,e)}, 其中-A(a,e)={m-1|i∈A(a,e)}, 且A(a,2e)的個數(shù)為(2e-1-1)/e。 不妨把A(a,2e)最小的正整數(shù)仍稱為陪集首, 且陪集首a是唯一的。設(shè)A0={0}, 把所有A(a,2e)排成一行放置, 第j個陪集記為A(a,2e)j,1≤j≤(2e-1-1)/e。對任意1≤j≠j′≤(2e-1-1)/e, 有下列劃分:

(1)

引理1[3]對任意元素τ∈2e-1{0}, 那么有

1.2 Zeng-Cai-Tang廣義分圓類

對于元素a和*n的子集D, 定義a+D和aD如下:a+D={a+d|d∈D},aD={ad|d∈D}, 其中加法和乘法運算是在模n下進行的。

對任意給定一個奇數(shù)n≥3, 由唯一分解定理,n能表示成pm11pm22…pmkk的形式, 其中pi是奇素數(shù)且mi是正整數(shù)對任意1≤i≤k。 在本文中對任意1≤i≠j≤k, 總是令pi≠pj。對每個整數(shù)1≤i≤k, 存在gi使得gi是模pmii的一個本原根對所有mi≥1。 記φ(x)為歐拉函數(shù)表示小于等于x并與x互素的個數(shù), 則gi模pmii的乘法階為φ(pmii)=pmi-1i(pi-1)。對任意1≤i≤k, 設(shè)2e|pi-1, 即存在k個fi使得pi-1=2efi。由中國剩余定理, 對每個1≤j≤k和1≤i≤k, 都存在唯一hj∈*n使得

(2)

設(shè)n1≥3是n的一個因子且記π(n1)表示n1的不同素因子的個數(shù), 則存在π(n1)個數(shù)t1,t1,…,tπ(n1)∈{1,2,…,k}和π(n1)個數(shù)m′t1,m′t2,…,m′tπ(n1)使得

n1=pm′t1t1pm′t2t2…pm′tπ(n1)tπ(n1),

其中1≤m′t≤mt對t∈T={t1,t1,…,tπ(n1)}?{1,2,…,k}。再次用中國剩余定理, 對每個t∈T, 可知存在唯一g(n1,2e)∈*n1有g(shù)(n1,2e)=gftpm′t-1tt(modpm′tt)。顯然地,g(n1,2e)模n1的乘法階為2e且集合D(n1,2e)={gi(n1,2e)|0≤i≤2e-1}是*n1的一個階為2e的循環(huán)子群[8]。

對每個t∈T, 設(shè)lt=φ(pm′tt)=pm′t-1t(pt-1)且定義一個集合ψ(2e)n1為ψ(2e)n1={j∈lt1|0≤j≤ftpm′t-1t-1}×lt2×…×ltπ(n1)。對任意In1=(i1,i2,,inπ(n1))∈ψ(2e)n1, 定義D(n1,2e)In1為D(n1,2e)In1=HIn1n1D(n1,2e), 其中Hn1=ht1ht2…h(huán)tπ(n1)且定義HIn1n1為

HIn1n1=hi1t1hi1t1…h(huán)iπ(n1)tπ(n1)(modn1)。

特別地,D(n1,2e)O=D(n1,2e), 這里O表示π(n1)維零向量。文獻[11]證明了{D(n1,2e)In1|In1∈ψ(2e)n1} 是*n1的一個劃分,D(n1,2e)In1被稱作階為關(guān)于n1的廣義分圓類。 那么, 可得到n的一個如下劃分：

2 ZDB 函數(shù)的新構(gòu)造

(3)

引理2對任意元素τ∈n{0}, 那么有

倒數(shù)第三個等式成立, 由于I跑遍所有ψ(2e)n1時, 有τ1D(n1,2e)I=τ1*n1=*n1。 最后一個等式成立, 因為在D(n1,2e)O中除了0, 其他2e-1個元素均屬于*n1。

下列定理可由引理2直接得到。

定理1函數(shù)χ2(·)是構(gòu)造1中定義的函數(shù), 那么它是從n到的一個函數(shù)。

θ(x)=(ix)2e,

(4)

其中, (ix)2e表示ix模2e同余的最小非負整數(shù), 則θ(x)是n{0}到集合{0,1,…,2e-1}的一個函數(shù)。

引理3[4]若任意給定正整數(shù)τ具有τ0=(τ)2e≠0且τ2=(τ)n≠0, 則有唯一的

使得τ0+θ((x+τ2)n)≡θ(x)(mod 2e), 其中θ(x)為式(4)所定義的函數(shù)。

若x∈A(a,2e)j, 定義

(5)

且

η(x)=(jx)2e,

(6)

其中,i≤j≤(2e-1-1)/e,a表示是在集合A(a,2e)中最小的正整數(shù)值且(jx)2e表示jx模2e同余的最小非負整數(shù), 則η(x)是2e-1到集合{0,1,…,2e-1}的一個函數(shù)。

引理4對任意給定整數(shù)τ1,τ2, 其中τ1∈2e-1τ2≤2e-1。 若x∈A(a,2e)j, 對每個jx, 0≤jx≤ 2e-1有唯一的(a,jx), 使得τ1+(jx+τ2)-1≡j-1x(mod2e-1)。

證明:因為e是一個素數(shù), 對任意1≤τ0≤e-1, 有g(shù)cd(2τ0-1,2e-1)=2gcd (τ0,e)-1=1。對任意陪集首a和1≤τ0≤e-1, 則有a2i-a2i+τ0∈2e-1{0}對0≤i≤e-1。另一方面, 若存在兩個二階分圓陪集首a,b和兩個整數(shù)0≤i1,i2≤e-1, 使得τ1±2i1+τ0≡±a2i1(mod 2e-1)且τ1±b2i2+τ0≡±a2i1(mod 2e-1),則有

τ1≡±a2i1(1-2τ0)(mod2e-1)≡±b2i2(1-2τ0)(mod2e-1)。

由gcd(2τ0-1,2e-1)=1, 可得a2i1≡±b2i2(mod 2e-1), 從而a=±b和i1=i2。因為陪集首的個數(shù)為(2e-1-1)/e且1≤jx≤2e-1, 因此τ1+(jx+τ2)-1≡j-1x(mod 2e-1)有唯一解(a,jx)。證畢。

下列推論可以直接從引理4得到。

推論1若任意給定正整數(shù)τ, 若τ0=(τ)2e≠0且τ1=(τ)2e-1≠0, 則有唯一的

使得τ0+η((x+τ1)2e-1)≡η(x)(mod 2e), 其中η(x)為式(6)所定義的函數(shù)。

以下介紹ZDB函數(shù)的構(gòu)造。

(7)

這里t1=(t)2e-1和t2=(t)n, 且χ1和χ2分別為式(1)和式(3)所定義。

通過χ1和χ2的定義, 容易知道如下結(jié)論成立。

因此, 函數(shù)f的定義是合理的而且是從2e-1×n到的滿射。對任意和有|D(n,2e)i|=|A(a,2e)j|=2e。 因此f的原象分布為{1,2e,2e,…,2e}, 這里1對應(yīng)的情形。下列定理是本文的主要結(jié)果：

定理2函數(shù)f是構(gòu)造2中定義的函數(shù), 那么它是從2e-1×n到的一個函數(shù)。

證明: 對任意給定τ=(τ1,τ2)≠(0,0),τ1∈2e-1且τ2∈n, 定義

Δ1(τ)=|{t∈2e-1×n|f(t+τ)=f(t),t1≠0,t2=0}|

和

Δ2(τ)=|{t∈2e-1×n|f(t+τ)=f(t),t1≠0,t2≠0}|,

由文獻[9]的引理3.1.6和引理3.1.7可知

(8)

(9)

那么, 有|{t∈2e-1×n|f(t+τ)-f(t)=0}|=Δ1(τ)+Δ2(τ)+Δ3(τ),其中, 定義Δ3(τ)=|{t∈2e-1×n|f(t+τ)=f(t),t1≠0,t2≠0}|。類似文獻[8]引理3.1.8可證明

(10)

因此, 對τ≠(0,0), 有|{t∈(2e-1)n|f(t+τ)-f(t)=0}|=2e-1。證畢。

例子設(shè)n=p1=13,e=3,m=7且2是模13的本原元。 那么, 廣義分圓類如下：

D(13,6)1={1,4,3,12,9,10},D(13,6)2={2,8,6,11,5,7},D0={0}。

又模7的二階分圓陪集為A(1,6)1={1,2,4,6,5,3},A0={0}。

定義

和

通過構(gòu)造2, 能得到一個函數(shù)f(t)。 具體地,f(t)值如下

(f(0),f(1),…,f(90))=(15, 0, 7, 1, 3, 8, 11, 14, 7, 5, 4, 11, 1, 12, 13, 6, 3, 0, 6, 6, 8, 14,4, 0,8, 5, 12, 3, 14, 2, 2, 9, 10, 9, 10, 13, 5, 10, 2, 12, 4, 9, 13, 1, 11, 7, 7,11, 1,13, 9, 4, 12,2, 10, 5, 13, 10, 9, 10, 9, 2, 2, 14, 3, 12, 5, 8, 0, 4,14, 8, 6, 6, 0, 3, 6, 13, 12, 1, 11, 4, 5, 7, 14, 11, 8, 3, 1, 7, 0)。

由Magama, 容易驗證對任意1≤τ≤90, 有|{t|f(t+τ)=f(t)=0,1≤t≤90}|=5。因此,f是一個從91到91(91,16,5)-ZDB函數(shù)。

3 零查分平衡函數(shù)在最佳跳頻序列的應(yīng)用舉例

ZDB函數(shù)主要有三方面的應(yīng)用:常重復(fù)合碼(CCC), 集合差系統(tǒng)(DSS)和跳頻序列(FHS), 本文只給出該構(gòu)造在跳頻序列中的具體應(yīng)用。

例如，設(shè)F={f0,f0,…,fl-1}是一個頻率集, 亦稱其為字母表。若xt∈F對0≤t≤N-1, 則稱X={xt}N-1t=0為一個長度為N的跳頻序列(FHS)。

對一個F上長度N的跳頻序列X={xt}N-1t=0, 它的周期漢明自相關(guān)HX定義為

設(shè)|F|=l,F上的序列周期為N, 最大周期漢明自相關(guān)為λ, 記該跳頻序列為(N,l,λ)FHS. Lempel和Greenberger給出了如下關(guān)于最大周期漢明自相關(guān)的一個理論下界：

引理5[1](L-G界)設(shè)X是一個(N,l,λ)-FHS, 則有

(11)

其中,r是滿足N≡r(modl)最小的非負整數(shù), 且「t?表示大于或等于t的最小整數(shù)。

最近, 文獻[1]給出了FHS和ZDB函數(shù)之間的一個關(guān)系刻畫。

引理6若f是一個(N,l,λ)-ZDB函數(shù)從一個循環(huán)群A到阿貝爾群B,按如下方式定義一個長度N=|A|的跳頻序列S={si}N-1i=0, 其中si=f(αi), 對 0≤i≤N-1, 且α是A的一個生成元, 則S是在字母表F=Im(f)?B上的一個(N,l,λ)FHS。