有限域上基于深度和交織技術(shù)的序列研究.pdf

1、偽隨機(jī)序列在通信系統(tǒng)中起著極其重要的作用。所謂偽隨機(jī)序列是指具有某些隨機(jī)特性且結(jié)構(gòu)又是可以預(yù)先確定，能重復(fù)產(chǎn)生和復(fù)制的序列。例如，在CDMA（Code Division Multiple Access）系統(tǒng)中，就需要大量具有良好相關(guān)性（即：序列集的自相關(guān)和互相關(guān)值與序列的周期之比越小越好）的序列集。近三十年來，尋找具有良好相關(guān)性的序列及序列集一直是通信領(lǐng)域廣泛研究的問題之一。如何基于短序列，利用輕量級算法產(chǎn)生這樣具有良好相關(guān)性的長序列是

2、本文的研究重點。
　　本文從研究向量深度（復(fù)雜度）出發(fā)，首先利用循環(huán)矩陣討論了有限域Fq上n維向量s的深度分布，構(gòu)造了一類終歸周期序列{(L?1)i(s)}i≥0（其中，L是向量的循環(huán)左移算子）；其次通過研究此類序列的終歸周期的界以及最小終歸周期分布，提出了一個在n維向量空間中以很高的概率，通過循環(huán)差分算子，基于n長短序列（即：n維向量）生成長序列的輕量級算法；進(jìn)而利用交織技術(shù)，得到了大量具有良好相關(guān)性的序列。主要創(chuàng)新之處有以下三

3、點：
　　第一，有限域上的向量導(dǎo)數(shù)是關(guān)于序列運算的一個著名算子，在博弈論、通信理論和密碼學(xué)中，被廣泛用于研究序列的復(fù)雜度。Etzion[29,46]利用向量導(dǎo)數(shù)研究了序列的線性復(fù)雜度，開創(chuàng)性地提出了向量深度的概念，認(rèn)為一個長度為2r的二元向量的深度等于其對應(yīng)周期序列的線性復(fù)雜度。本文稱此深度為“第一類深度”。Luo、Fu和Wei[88]深入研究了線性碼的第一類深度分布。文獻(xiàn)[46]提到Roth利用序列生成多項式的因式分解也研究了序

4、列的線性復(fù)雜度，對于長度為2r的二元向量的深度提出了一個與Etzion的深度概念等價的描述。本文稱之為“第二類深度”。隨后，Mitchell[92]利用循環(huán)差分算子(L?1)將Etzion的向量深度概念推廣到無限序列，指出具有有限深度的無限長二元序列之集等于周期形如2i(i為任意非負(fù)整數(shù))的序列之集。本文稱之為“第三類深度”。對于一個有限域Fq上周期為n的序列來說，當(dāng)n=pr時，其中p是有限域Fq的特征，此序列的上述三類深度都等于它的線

5、性復(fù)雜度[20]。本文給出了有限域上n維向量空間的第二類深度和第三類深度分布，詳見第三章。
　　第二，在通信系統(tǒng)的相關(guān)應(yīng)用中，有兩個普遍關(guān)心的問題，一是如何利用輕量級計算生成長周期序列，二是如何完成序列盲周期檢測同步。首先，生成長周期序列的方法有很多，除了基于LFSR（Left Feedback Shift Register）的構(gòu)造方法外[63]，還有大量基于不同數(shù)學(xué)理論的構(gòu)造方法，如基于割園[36,38–40]、有限域[30,5

6、4,76,96,103,111]和函數(shù)域[124–126,128]等的構(gòu)造方法。這兩類方法各有優(yōu)缺點。一般來說，前者易于實現(xiàn)但不易分析序列的性質(zhì)；后者則相反。綜合兩者的優(yōu)勢構(gòu)造隨機(jī)序列的方法是實際應(yīng)用中所需要的[57–59,62]。本文首次從高概率生成序列的角度，基于有限域上具有無限第三類深度的向量，通過輕量級的循環(huán)差分算子，給出了一個生成長周期序列的解決方案。當(dāng)q=2且n=2r?1時，此解決方案的計算復(fù)雜度為Θ(n2)，且LFSR的G

7、E（GateEquipments）個數(shù)為n。其次，在通信實踐中，序列的盲同步是必須的但卻不易實現(xiàn)。特別是，周期序列有可能因為設(shè)備切換和噪音干擾，變成了終歸周期序列，這就更加大了同步的困難。本文給出了一類循環(huán)差分序列{(L?1)i(s)}i≥0作為此問題的一個解決方案，不僅詳細(xì)研究了此類序列的終歸周期的上界和最小終歸周期的計算公式，而且對于周期為pr?1的基序列s，還給出了基于其循環(huán)差分序列最小終歸周期的分布。詳見第四章。
　　第三

8、，構(gòu)造具有良好相關(guān)性的序列是通信領(lǐng)域近30年來一直關(guān)心的問題之一。許多學(xué)者提出了大量基于m-序列及其采樣序列的構(gòu)造方法[78,82,86,112,116]。Gong[57,62]首次利用交織技術(shù)基于兩個2級自相關(guān)序列構(gòu)造了低相關(guān)性的序列及序列集。本文通過刻畫循環(huán)差分算子(L?1)i(i≥0)的矩陣結(jié)構(gòu)，利用交織技術(shù)基于一個2級自相關(guān)序列s的循環(huán)差分序列{(L?1)i(s)}i≥0構(gòu)造了一類具有良好相關(guān)性的序列。其構(gòu)造方法只使用了邏輯異或