基于一類2對1映射的序列的自相關性質

揣立娟

(湖北大學 數學與計算機科學學院，湖北 武漢 430062)

偽隨機序列在密碼學和通信等領域有著廣泛的應用.周期的大小、平衡性和自相關性質是評價周期序列隨機性的幾個重要指標[1]，因此對具有較大周期和理想自相關性的序列的研究成為了密碼學和通信學的一個重要研究領域.經過多年的努力，人們已經發現了許多理想自相關序列，如m-序列[2]，GMW序列[3]和具有梅森素數周期的勒讓得序列[4]等等.利用有限域上的2對1映射構造理想自相關序列是最近提出的一種有效途徑.本文中討論了由有限域F22m上的一類2對1映射構造的二元序列的性質. 給出了這些序列的周期為2m-1且滿足平衡性.基于Walsh變換技巧，本文中還證明了這些序列具有理想自相關性質.但是我們不知道它們是否為新的理想自相關序列，這個問題有待進一步研究.

1 預備知識

本節介紹了相關概念、性質及公式.

偽隨機序列b={b(t)∶t∈Z},是指序列元素間有確定關系存在，但具有與隨機序列類似性質的離散信號形式，可表示為…，b(-1),b(0),b(1),…,其中b(t)可取0,1;也可取有限域Fq中的元素，q為奇素數或素數的方冪.前者稱為二元序列，后者稱為q元序列.序列的長度可為有限，也可為無窮.人們常關注的是無窮序列中的周期序列.已知序列b={b(t)∶t∈Z},如果對任意整數t,存在一個最小的正整數N，使得b(t)=b(t+N)成立，則稱N是b的周期，b為周期序列，記為b={b(t)∶t=0,1,…,N-1}.

文中的序列均為偽隨機二元序列，簡稱二元序列.文中用到的記號有：

(1)F2n:表示含有2n個元素的有限域，其中n為正整數.n=1時，F2={0，1}；

(2)a:表示周期為N的二元序列a={a(t)∶a(t)∈F2,t=0,1,…,N-1};

(3)⊕:表示模2相加；

(4)+：表示整數相加.

(1)

其中τ∈{0,1,…,N-1},且t+τ是模N計算的.

(2)

把具有理想自相關性質的序列稱為理想自相關序列.

在第2節自相關值的計算過程中用到了跡函數的性質和Parseval等式，下面將介紹跡函數的定義、相關性質和Parseval等式.

其中x∈F2n.

Parseval等式[1]：

文中還用到的定義如下.

定義1 稱φ:A→B是2對1映射，如果Imφ中任一元素有且只有兩個原象，其中Imφ表示φ的象.

(3)

2 主要結果

這一節討論了由有限域上一類2對1映射構造的二元序列的性質.這些序列的周期為2m-1，且具有平衡性.利用Walsh變換技巧，證明了這些序列還具有理想自相關性.

首先給出序列的構造過程.

序列構造：已知有限域F2n,n=2m,其中m為任意正整數.令q=2m,記 U={x∈F2n|xq+1=1}.

(4)

(5)

由s的構造方法知，它的周期為q-1，即2m-1.根據有限域[5]的性質，可得下面引理.

引理1 由方程(4)定義的映射是2對1的.

由引理1及序列平衡性定義，可得s是平衡的.

(6)

由以上引理以及Walsh變換技巧，有如下結果.

定理1 由等式(5)構造的序列s={s(αt)∶t=0,1,…,2m-2}具有理想自相關性質.

定理1的證明令f(x)∶F2n→F2是集合D=Imφ的特征函數，則

由Parseval等式有：

(7)

3 結論

參考文獻：

[1] Golomb S W.Sequences with randomness properties[R].Baltimore:Glenn L Martin Company,1995.

[2] Golomb S W.Shift register sequences[M].San Francisco, CA:Holden-day,1967;Laguna Hills,CA:Aegean Park,1982.

[3] Scholtz R, Welch L.GMW sequences[J]. Tran Information Theory,1984,30(5):548-553.

[4] Baumert L D.Cyclic difference sets[M]. Berlin:Springer-Verlag,1971.

[5] Lidl R,Niederreiter H.Finite fields[M].Cambridge:Cambridge University Press,1983.

[6] Rosendahl P.Niho type cross-correlation functions and related equations[D].University of Turku,Finland:Genealogy Project,2004.