朱建鋒，安建平，王愛華

(北京理工大學 信息與電子學院，北京 100081)

一種基于迭代交織的任意長度擴頻碼生成器

朱建鋒，安建平，王愛華

(北京理工大學 信息與電子學院，北京 100081)

擴頻碼設計是北斗系統(tǒng)信號體制的重要內容，同時滿足碼長選擇靈活性和良好性能是擴頻碼設計中的難題，自主知識產(chǎn)權也是北斗信號設計的目標之一?；诮豢椷\算和反饋-迭代結構提出一種適合任意長度的擴頻碼生成器，利用交織運算的隨機化效應產(chǎn)生隨機序列，通過反饋-迭代運算產(chǎn)生擴頻碼候選集合，討論了交織運算器和種子序列的選擇準則。采用迭代交織生成器構造1 023、2 046、4 092、10 230比特擴頻碼方案，評估結果表明，迭代交織擴頻碼與全球定位系統(tǒng)、歐洲伽利略系統(tǒng)和中國北斗衛(wèi)星導航系統(tǒng)的擴頻碼方案相比性能相當或更優(yōu)。迭代交織生成器可以生成任意長度、性能良好的擴頻碼方案，同時具有完美平衡性和計算復雜度低的優(yōu)勢，為我國北斗系統(tǒng)信號設計提供了一種候選方案。

擴頻碼生成器；迭代交織；任意碼長；交織運算器

擴頻碼是任何基于擴頻通信體制的無線通信、測量系統(tǒng)信號體制設計所必需的，擴頻碼的碼長、碼相關性是影響信號抗干擾能力、多址能力和測量精度的重要因素[1]。移位寄存器法、數(shù)論法和計算機搜索法是三種主要的衛(wèi)星導航信號擴頻碼構造方法，線性移位寄存器法(linear feedback shift register，LFSR)的優(yōu)勢是碼相關性好、生成計算復雜度低[2]，但碼長受生成多項式周期制約；全球定位系統(tǒng)(global positioning system，GPS)L1C信號的Weil碼是基于數(shù)論方法設計的[3]，Weil碼顯著改善了碼自相關性能，設計Weil碼的前提是在碼長附近找到一個生成素數(shù)；歐洲伽利略系統(tǒng)(Galileo navigation satellite system，Galileo)的E1 OS信號擴頻碼使用遺傳算法通過計算機搜索實現(xiàn)[4]，計算機搜索可以得到一些有特色的碼字如零自相關旁瓣(autocorrelation side lobe zero，ASZ)，但是由于計算復雜度的限制只能用于較短的碼長如4 092、5 115比特?？梢钥闯?，現(xiàn)有的擴頻碼構造方法都不能滿足靈活選擇碼長的要求，而碼長靈活性是衛(wèi)星導航和擴頻通信信號體制設計者所期望的，一種適合任意碼長、性能良好、低復雜度的擴頻碼構造方法將極大地降低信號體制設計中平衡信號頻譜帶寬、信息速率和用戶數(shù)量的難度。

本文提出一種適合任意碼長、低復雜度的通用擴頻碼生成器，首次將迭代交織運算應用于擴頻碼構造。分析了交織運算的數(shù)學模型和隨機化效應，提出擴頻碼構造的迭代交織系統(tǒng)模型，擴頻碼生成只包含線性復雜度的位置交換運算。使用通用生成器設計4種不同碼長的擴頻碼，與現(xiàn)有11種不同生成方法、不同碼長的導航信號擴頻碼評估和對比表明：在主要性能測度上迭代交織碼(iterative interleaving code，IIC)與GPS、Galileo和我國北斗衛(wèi)星導航系統(tǒng)(BeiDou navigation satellite system，BDS)擴頻碼相當或更優(yōu)。迭代交織還能夠滿足BDS對自主知識產(chǎn)權的要求，為BDS信號體制設計提供一種候選方案。

1 迭代交織運算的數(shù)學模型

1.1 交織運算的兩種模型

交織運算的最初目的是為了提高突發(fā)錯誤信道中的糾錯能力[5]，通過位置置換可以將連續(xù)的突發(fā)錯誤轉換為隨機錯誤。在以誤碼率為測度的場景下，對于交織運算器的建模和研究側重于周期性、因果性、延時和內存占用[6-7]，典型的交織器包括分組交織器和卷積交織器，本文中應用的交織器限定于分組交織器。分組交織器包含3個要素：交織序列s={si}、輸入序列u={ui}、輸出序列v={vi}，i=1,2,...,N，N為序列長度，交織的數(shù)學含義是從u到v的一一映射，s則表示映射的實現(xiàn)方式，即

v=f(u,s)

(1)

交織器可以用位置置換和矩陣乘法兩種數(shù)學工具來分析。在位置置換模型中，交織序列s是正整數(shù)1，2，…，N的一個排列，交織器的輸入和輸出關系為

(2)

在矩陣乘法模型中，序列u、v、s可以用矢量U、V和矩陣S表示，其中U(i)=ui，V(i)=vi，1≤i≤N，交織矩陣S的元素為

(3)

其中1≤i≤N，1≤j≤N。則交織過程可以表示為矩陣乘積形式

V=U×S=US

(4)

比較兩種模型，矩陣乘法模型形式清晰簡潔，但實現(xiàn)復雜度為O(N2)，位置置換模型的物理意義清晰，實現(xiàn)復雜度為O(N)，更適合交織運算的工程實現(xiàn)。

1.2 隨機化效應和迭代交織模型

文獻[5]最早提出了交織運算的隨機化效應，指出隨機化效應是實現(xiàn)將突發(fā)錯誤轉化為隨機錯誤的關鍵，并以錯誤模式的概率分布作為隨機化測度。在早期以誤碼率為目標的應用中，考慮到交織和解交織的延時和存儲空間，這一階段以規(guī)則交織器為主。在提出近香農限的Turbo碼以后，交織器成為影響Turbo碼性能的關鍵因素之一，非規(guī)則、分組交織研究成為熱點，面向Turbo碼的交織器設計遵循兩項原則：長交織器和輸出序列盡可能隨機化[8]，隨機化效應是利用交織運算構造隨機擴頻碼的基礎。

迭代交織系統(tǒng)模型的提出借鑒了糾錯譯碼中的迭代譯碼思想(圖1)，系統(tǒng)由輸入序列、交織器和反饋回路組成，第一次使用的輸入序列也稱為種子序列，交織器則由交織序列描述，交織器的輸出通過反饋回路返回輸入端作為下一迭代的輸入序列?；诘豢椊Y構模型，多次迭代可以產(chǎn)生多個輸出序列，這些輸出序列構成了擴頻碼設計的候選集合。

圖1 迭代交織系統(tǒng)模型

以矩陣乘法模型作為工具分析迭代交織運算，第一次迭代的輸入序列U=U0，交織矩陣為S，第k次迭代的輸出序列為Vk，則有

(5)

迭代交織運算的實質是種子序列和交織矩陣的k次乘方的乘積，因此輸出序列Vk決定于三個因素：種子序列U0、交織矩陣S和迭代次數(shù)。

2 基于迭代交織的擴頻碼構造

基于迭代交織結構模型，通過若干次迭代交織可以生成擴頻碼的候選集合。交織矩陣和種子序列是產(chǎn)生具有良好性能擴頻碼的關鍵要素，二者需要進行優(yōu)選，優(yōu)選的目的是(1)產(chǎn)生具有期望特征的擴頻碼；(2)防止迭代交織結構進入病態(tài)。

2.1 交織器的選擇

交織器的選擇包括兩個問題：(1)選擇何種交織器；(2)交織序列的長度能否任意選擇。Turbo碼出現(xiàn)后，為優(yōu)化Turbo碼性能對交織器進行了大量研究工作[9]，出現(xiàn)了規(guī)則交織器和非規(guī)則交織器兩大類的多種交織器方案，其中非規(guī)則交織器具有較好的交織增益。雖然可選的交織器結構非常多，但是并非都可以用于構造擴頻碼，某些類型的交織器會導致迭代過程進入病態(tài)。例如自反交織器[10]，其設計目的是交織器和解交織器使用相同的交織序列以降低實現(xiàn)資源，其矩陣表示為S-1=S，那么S2n=E，采用這種交織器的迭代輸出為：

(6)

其結果是迭代交織結構無法生成隨機的輸出序列，迭代交織結構處于病態(tài)，用于迭代交織的交織器需要進行自反性檢驗。

在使用迭代交織構造擴頻碼的過程中，輸出序列的隨機性是選擇交織器最重要的測度。在不同的交織器結構中，隨機交織器和S隨機交織器具有良好的隨機化效應。特別是S隨機交織器，輸入序列中的相鄰符號交織后的距離至少為

為交織序列長度，本文選擇S交織器作為構造擴頻碼的交織器。對于第二個問題，文獻[12]提出了構造任意長度S交織器的方法。

2.2 種子序列構造

在基于迭代交織的擴頻碼構造方法中，通過對種子序列的控制可以實現(xiàn)完美平衡性。由于在迭代交織運算中，輸出序列的01個數(shù)保持不變，因此只要種子序列U0的滿足完美平衡的條件，那么所有迭代交織后的序列都滿足完美平衡性。生成具有完美平衡性的種子序列可以采用兩種策略：(1)篩選法，任意生成01序列，拒絕所有不滿足01完美平衡性的序列，直至獲得一個滿足完美平衡性的序列；(2)規(guī)則構造法，按照某種規(guī)則構造01完美平衡性的序列，一種可行方案是采用0、1交替構造種子序列。

2.3 實現(xiàn)步驟

基于迭代交織方案構造擴頻碼的步驟如下，輸入條件為擴頻碼長度N，擴頻碼候選集合元素數(shù)M，種子序列為U0，交織序列為S，交織器為S隨機交織器，交織器通過自反性檢驗，生成過程采用矩陣表示。

步驟1.參數(shù)初始化。

采用規(guī)則構造方法種子序列U0，其中

(7)

將種子序列賦予輸入序列U=U0，迭代計數(shù)器k=1。

步驟2.交織生成擴頻碼。

輸入序列U通過交織器S產(chǎn)生輸出序列Vk，即

Vk=US

(8)

保存為擴頻候選集合中的第k個元素，Vk反饋回輸入端作為下一次的輸入序列U=Vk。

步驟3.迭代交織。

檢查迭代計數(shù)器，如果k=M停止迭代，否則計數(shù)器加1，返回步驟2進行下一次迭代。

至此，候選擴頻碼中已經(jīng)包含M個長度為N的擴頻碼序列，候選集合中碼序列是進行后續(xù)擴頻碼設計工作的基礎。

3 性能仿真與分析

為驗證使用迭代交織生成器生成擴頻碼的性能和復雜度，以GPS、Galileo和BDS的接口控制文件(interfacecontroldocument，ICD)中的擴頻碼作為比較對象，共選擇不同生成方法、不同的碼長的擴頻碼方案11種，碼長包括1 023、2 046、4 092、10 230比特，生成方法包括Gold序列、截斷m序列、Weil碼、隨機存儲碼等。使用迭代交織生成器構造4組同樣碼長的擴頻碼方案(IIC-1203、IIC-2046、IIC-4092、IIC-10230)，比較的性能測度包括：01個數(shù)差、偶自相關、奇自相關、偶互相關、奇自相關，性能比較如表1所示。

表1 擴頻碼性能比較

綜合分析表1中的擴頻碼方案和性能測度可知：

(1)迭代交織擴頻碼在所有長度上具有完美01平衡性；

(2)迭代交織擴頻碼具有良好的自相關性，奇偶自相關性能比較平衡，GPS L1C/A、L1C擴頻碼具有偶自相關優(yōu)勢，但奇自相關沒有優(yōu)勢；

(3)迭代交織擴頻碼具有良好的互相關性，奇偶互相關性能比較平衡，GPS L1C/A、L1C、Galileo E1信號具有互相關優(yōu)勢，但優(yōu)勢不顯著；

上述迭代交織擴頻碼生成使用Matlab語言編程實現(xiàn)，在個人計算機(person computer，PC)上的構造時間從20 s至2 h不等。如果增加迭代次數(shù)可以進一步改善自相關和互相關性能。當前實驗中使用的固定交織器并非必要條件，交織器動態(tài)更新也不存在技術障礙。

4 結束語

BDS的成功需要具有自主知識產(chǎn)權、高性能的信號體制方案，本文提出的迭代交織碼可以同時滿足靈活選擇碼長和性能良好的要求。以GPS、Galileo和BDS系統(tǒng)ICD中11種不同構造方法、不同碼長的擴頻碼為對象進行性能評估和比較，迭代交織碼在主要性能測度上與現(xiàn)有ICD方案相比相當或更優(yōu)，迭代交織碼為BDS信號體制設計提供了一種候選方案。基于迭代交織的擴頻碼生成器不僅適用于衛(wèi)星導航系統(tǒng)，而且可用于任意使用二進制序列作為擴頻碼的無線擴頻通信、測量系統(tǒng)。

[1] ZEPERNICK H J，F(xiàn)INGER A.Pseudo Random Signal Processing Theory and Application[M].Chichester：John Wiley & Sons Ltd，2005：225-227.

[2] IS-GPS-200F，Navstar GPS Space Segment/Navigation User Interfaces[S].

[3] IS-GPS-800B，Navstar GPS Spaces Segment/User Segment L1C Interfaces[S].

[4] OS SIS ICD Issue 1，European GNSS(Galileo)Open Service Signal In Space Interface Control Document[S].

[5] BRAYER K，CARDINALE O.Evaluation of Error Correction Block Encoding for High-speed HF Data[J].IEEE Transactions on Communication Technology，1967，15(3)：371-382.

[6] ANDREWS K，HEEGARD C，KOZEN D.A Theory of Interleavers[EB/OL].[2014-09-21].www.cs.cornell.edu/～kozen/papers/interl.pdf.

[7] GARELLO R，MONTORSI G，BENEDETTO S，et al.Interleaver Properties and Their Applications to the Trellis Complexity Analysis of Turbo Codes[J].IEEE Transactions on Communication Technology，1967，15(3)：371-382.

[8] BERROU C，GLAVIEUX A.Near Optimum Error Correcting Coding and Decoding：Turbo-Codes[J]. IEEE Transactions on Communication Technology，1996，44(10)：1261-1271.

[9] ANDREWS K.Turbo Codes and Interleaver Design[D].New York：Cornell University，1999.

[10] HO M S C，PIETROBON S S，GILES T.Interleavers for Punctured Turbo Codes[C]//Proceedings of IEEE Asia-Pacific Conference on Communications.Singapore：IEEE，1998：520-524.

[11] DOLINAR S，DIVSALAR D.Weight Distributions for Turbo Codes Using Random and Nonrandom Permutation：TDA Progress Report 42-122s[R].Pasadena，California：Jet Propulsion Laboratory Pasadena California，1995.

[12] LI Xiao-wen，CHEN Zhen-dong.A Design of Improved Flexible-length S-random Interleaver[C]//Proceedings of the 3rd International Conference on Computer Research and Development(ICCRD).Shanghai：IEEE，2011：391-394.

[13] MENEZES A J，OORSCHOT PC，VANSTONE S A.Handbook of Applied Cryptography[M].Boca Raton：CRC Press，1997：181-182.

A Flexible-Length Spreading Code Generator Based on Iterative Interleaving

ZHU Jian-feng，AN Jian-ping，WANG Ai-hua

(School of Information and Electronics，Beijing Institute of Technology，Beijing 100081，China)

Spreading code design is an important item of China BDS signal structure.It is difficult to meet the requirements of flexible code length and good performance in spreading code design at the same time.Independent intellectual property right is another goal of BDS signal structure.A flexible-length spreading code generator based on interleaving operation and feedback-iterate structure is proposed in this paper.Random sequence is build by the random effect of interleaving operation.The output sequences of iterative operations forms the candidate set of spreading codes.The critical of interleaving operator and seed sequence selection are discussed also.Four spreading codes families with 1023，2046，4092，10230 bits length are designed by using iterative interleaving generator.The result of evaluation shows that the performance of new code families is equivalent or better than spreading codes of GPS，Galileo and BDS.The new generator can used to design spreading codes with flexible code length and good performance.The iterative interleaving code has the benefit of perfect code balance，low generation complexity and provides a candidate for BDS signal design.

spreading code generator；iterative interleaving；flexible code length；interleaving operator

2014-10-14

國家高技術研究(863)發(fā)展計劃(2011AA120502)。

朱建鋒(1977)，男，河南封丘縣人，博士生，研究方向為衛(wèi)星導航信號設計與評估理論。

P

A

2095-4999(2015)-01-0023-04