朱建鋒，安建平，王愛華

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

一種基于迭代交織的任意長(zhǎng)度擴(kuò)頻碼生成器

朱建鋒，安建平，王愛華

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

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

擴(kuò)頻碼生成器；迭代交織；任意碼長(zhǎng)；交織運(yùn)算器

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

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

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

1.1 交織運(yùn)算的兩種模型

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

v=f(u,s)

(1)

交織器可以用位置置換和矩陣乘法兩種數(shù)學(xué)工具來(lái)分析。在位置置換模型中，交織序列s是正整數(shù)1，2，…，N的一個(gè)排列，交織器的輸入和輸出關(guā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。則交織過(guò)程可以表示為矩陣乘積形式

V=U×S=US

(4)

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

1.2 隨機(jī)化效應(yīng)和迭代交織模型

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

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

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

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

(5)

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

2 基于迭代交織的擴(kuò)頻碼構(gòu)造

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

2.1 交織器的選擇

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

(6)

其結(jié)果是迭代交織結(jié)構(gòu)無(wú)法生成隨機(jī)的輸出序列，迭代交織結(jié)構(gòu)處于病態(tài)，用于迭代交織的交織器需要進(jìn)行自反性檢驗(yàn)。

在使用迭代交織構(gòu)造擴(kuò)頻碼的過(guò)程中，輸出序列的隨機(jī)性是選擇交織器最重要的測(cè)度。在不同的交織器結(jié)構(gòu)中，隨機(jī)交織器和S隨機(jī)交織器具有良好的隨機(jī)化效應(yīng)。特別是S隨機(jī)交織器，輸入序列中的相鄰符號(hào)交織后的距離至少為

為交織序列長(zhǎng)度，本文選擇S交織器作為構(gòu)造擴(kuò)頻碼的交織器。對(duì)于第二個(gè)問(wèn)題，文獻(xiàn)[12]提出了構(gòu)造任意長(zhǎng)度S交織器的方法。

2.2 種子序列構(gòu)造

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

2.3 實(shí)現(xiàn)步驟

基于迭代交織方案構(gòu)造擴(kuò)頻碼的步驟如下，輸入條件為擴(kuò)頻碼長(zhǎng)度N，擴(kuò)頻碼候選集合元素?cái)?shù)M，種子序列為U0，交織序列為S，交織器為S隨機(jī)交織器，交織器通過(guò)自反性檢驗(yàn)，生成過(guò)程采用矩陣表示。

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

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

(7)

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

步驟2.交織生成擴(kuò)頻碼。

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

Vk=US

(8)

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

步驟3.迭代交織。

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

至此，候選擴(kuò)頻碼中已經(jīng)包含M個(gè)長(zhǎng)度為N的擴(kuò)頻碼序列，候選集合中碼序列是進(jìn)行后續(xù)擴(kuò)頻碼設(shè)計(jì)工作的基礎(chǔ)。

3 性能仿真與分析

為驗(yàn)證使用迭代交織生成器生成擴(kuò)頻碼的性能和復(fù)雜度，以GPS、Galileo和BDS的接口控制文件(interfacecontroldocument，ICD)中的擴(kuò)頻碼作為比較對(duì)象，共選擇不同生成方法、不同的碼長(zhǎng)的擴(kuò)頻碼方案11種，碼長(zhǎng)包括1 023、2 046、4 092、10 230比特，生成方法包括Gold序列、截?cái)鄊序列、Weil碼、隨機(jī)存儲(chǔ)碼等。使用迭代交織生成器構(gòu)造4組同樣碼長(zhǎng)的擴(kuò)頻碼方案(IIC-1203、IIC-2046、IIC-4092、IIC-10230)，比較的性能測(cè)度包括：01個(gè)數(shù)差、偶自相關(guān)、奇自相關(guān)、偶互相關(guān)、奇自相關(guān)，性能比較如表1所示。

表1 擴(kuò)頻碼性能比較

綜合分析表1中的擴(kuò)頻碼方案和性能測(cè)度可知：

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

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

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

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

4 結(jié)束語(yǔ)

BDS的成功需要具有自主知識(shí)產(chǎn)權(quán)、高性能的信號(hào)體制方案，本文提出的迭代交織碼可以同時(shí)滿足靈活選擇碼長(zhǎng)和性能良好的要求。以GPS、Galileo和BDS系統(tǒng)ICD中11種不同構(gòu)造方法、不同碼長(zhǎng)的擴(kuò)頻碼為對(duì)象進(jìn)行性能評(píng)估和比較，迭代交織碼在主要性能測(cè)度上與現(xiàn)有ICD方案相比相當(dāng)或更優(yōu)，迭代交織碼為BDS信號(hào)體制設(shè)計(jì)提供了一種候選方案?；诘豢椀臄U(kuò)頻碼生成器不僅適用于衛(wèi)星導(dǎo)航系統(tǒng)，而且可用于任意使用二進(jìn)制序列作為擴(kuò)頻碼的無(wú)線擴(kuò)頻通信、測(cè)量系統(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

國(guó)家高技術(shù)研究(863)發(fā)展計(jì)劃(2011AA120502)。

朱建鋒(1977)，男，河南封丘縣人，博士生，研究方向?yàn)樾l(wèi)星導(dǎo)航信號(hào)設(shè)計(jì)與評(píng)估理論。

P

A

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