An Improved Algorithm Based on LTE-A for Pseudo Random Sequence Generation

李小文　李淑娜　蘇建松

(重慶郵電大學通信與信息工程學院，重慶　400065)

?

基于LTE-A的偽隨機序列生成的改進算法

An Improved Algorithm Based on LTE-A for Pseudo Random Sequence Generation

李小文李淑娜蘇建松

(重慶郵電大學通信與信息工程學院，重慶400065)

摘要：在先進長期演進(LTE-A)系統(tǒng)中，偽隨機序列生成時內(nèi)存占用量和執(zhí)行時間會隨著序列長度的增加而顯著增加。針對該問題，提出了一種循環(huán)替換算法，即在3GPP LTE-A系統(tǒng)中的低消耗(內(nèi)存)、低復雜度的偽隨機序列生成算法。此外，對傳統(tǒng)偽隨機序列生成算法進行了改進，使得偽隨機序列生成過程中的內(nèi)存占用量和執(zhí)行時間大大縮短。仿真結(jié)果證明了所提出算法的高效性和低消耗性。該算法對提高整個系統(tǒng)的性能有一定的意義。

關鍵詞：隨機序列循環(huán)替換算法算法改進DSP實現(xiàn)信息通信

Abstract：In LTE-A system,memory usage and execution time for generating pseudo random sequence are significantly increasing with the increment of the sequence length.For solving this problem,the circularly replacement algorithm is proposed.This generation algorithm features low memory consumption and low complexity in 3GPP LTE-A system.In addition,the traditional pseudo random sequence generation algorithm is improved.The memory usage and execution time in pseudo random sequence generation is greatly reduced.The simulation results verify the high efficiency and low consumption of the proposed algorithm.This algorithm possesses certain significance for enhancing the performance of entire system.

Keywords:Random sequenceCircularly replacement algorithmAlgorithm improvementDSP implementationInformation communication

0引言

通信現(xiàn)代化是人類社會進入信息時代的重要標志，怎樣在惡劣的環(huán)境條件下保證通信有效地、迅速地進行是當今擺在通信工作者面前的一大課題。偽隨機序列具有以下特征：一方面它是可以預先確定的，并且可以重復地生產(chǎn)和復制；另一方面它又具有某種隨機序列的隨機特性(即統(tǒng)計特性)。隨機噪聲的存在會對輸出信號進行干擾，使信號產(chǎn)生失真。然而，人們在試圖消除和減少通信系統(tǒng)中的隨機噪聲的同時也希望獲得隨機噪聲并充分利用它，用于更為有效的通信。目前先進長期演進(long time evolution advance,LTE-A)[1]正是利用偽隨機序列來對有用信號進行加擾以提高在無線通信環(huán)境中的性能。它是利用一對周期和速率均相同的m序列優(yōu)選對異或后得到的。

在實際的項目工程中，不僅要求能夠快速準確地實現(xiàn)通信，還要求盡量減少復雜度和內(nèi)存占用量。筆者主要從LTE-A中的Gold序列生成過程中內(nèi)存占用和執(zhí)行時間兩個方面來進行研究。基于所做的LTE-A綜測儀項目，本文提出一種循環(huán)替換算法。與常規(guī)算法相比，該算法可以大大減少內(nèi)存，提高執(zhí)行速度。

1Gold序列生成算法

1.1LTE-A系統(tǒng)偽隨機序列的生成

在LTE-A協(xié)議[1]中，偽隨機序列是由長度為31位的Gold序列生成的，用c(n)表示最后輸出的偽隨機序列，其中n=1,2,3,…，M，M為c(n)的長度。用x1(n)和x2(n)表示兩個m序列，且x1(n)和x2(n)滿足下面的初始化：

(1)

(2)

式中：ns為時隙號;nRNTI與無線網(wǎng)絡臨時鑒定 (radio network temporary identifier,RNTI)有關。

x1(n)和x2(n)的遞推公式為：

x1(n+31)=[x1(n+3)+x1(n)]mod2

(3)

x2(n+31)=[x2(n+3)+x2(n+2)+

x2(n+1)+x2(n)]mod2

(4)

偽隨機序列由下式?jīng)Q定：

c(n)=[x1(n+Nc)+x2(n+Nc)]mod2

(5)

式中：Nc=1 600，Nc是為了保證不同序列之間的非相關性而特意增加的狀態(tài)偏移量。

1.2偽隨機序列的常規(guī)算法

偽隨機序列c(n)生成過程中，兩個m序列分別由31個帶有反饋的線性移位寄存器移位產(chǎn)生。從上面的式子可以看出，正是Nc的存在使得兩個m序列x1(n)和x2(n)在普通算法中各自都要首先迭代Nc次，而且Gold序列作為偽隨機序列運用在多種場合[2]，并且有些應用場合系統(tǒng)所需要生成的偽隨機序列非常短。例如，偽隨機序列作為PBCH的RS序列時，所需序列的長度為48 bits，利用常規(guī)算法生成RS序列時需要移位1 648次，而生成的序列長度為48 bit，導致序列生成時間較長，且浪費了大量的系統(tǒng)資源。由式(5)可知，c(n)序列只與x1(n)和x2(n)的后M個值有直接關系，如果將x1(n)和x2(n)的全部值都保存起來會浪費大量的內(nèi)存，在大的項目工程中則會影響系統(tǒng)的健壯性。正是基于這一點，提出了一種新的實現(xiàn)方法，可以節(jié)省大量內(nèi)存，提高隨機序列生成的速度。

1.3算法優(yōu)化

目前，很多人對隨機序列生成中面臨的問題進行了研究，也提出了很多的算法來優(yōu)化隨機序列的生成。例如，在文獻[3]中，提出利用狀態(tài)轉(zhuǎn)移矩陣和初始向量來減少兩個m序列x1(n)和x2(n)生成時的多次移位迭代。x1(n)定義公式寫成：

x1(n+31)=h30x1(n+30)+h29x1(n+29)+

h28x1(n+28)+…+h0x1(n)

(6)

根據(jù)式(3)可知，h0=1，hn=0，n=1,2,3,…,30。定義初始狀態(tài)向量：

v0=[x1(0),x1(1),…,x1(30)]

(7)

根據(jù)式(3)可知，移位反饋寄存器移位一次后的初始狀態(tài)向量變?yōu)椋?/p>

v1=[x1(1),x1(2),…,x1(31)]

(8)

式中：x1(31)是由式(3)計算出來的；x1(1),x1(2),…,x1(30)是由向量v0左移一位得到的。

則初始狀態(tài)向量左移k次得到中間向量vk：

vk=[x1(1+k),x1(2+k),…,x1(31+k)]

(9)

根據(jù)上面的分析可以得到31×31的狀態(tài)轉(zhuǎn)移矩陣M，其中矩陣的初始值和式(3)中的系數(shù)hn(n=0,1,2,3,…,30)有關：

(10)

利用狀態(tài)轉(zhuǎn)移矩陣，可得中間向量v1的計算公式為：

v1=v0M

(11)

則移位反饋寄存器任意移動K次得到的中間向量為：

(12)

式中：vk向量為序列的第k位與第k+30位之間的值。

在式(12)中，根據(jù)狀態(tài)轉(zhuǎn)移矩陣M的初始狀態(tài)值可以計算出矩陣Mk，利用序列初始狀態(tài)值與矩陣Mk的乘積一次完成K次序列移位。該方法確實可以一次得到移位寄存器K次移位，節(jié)省很多中間值存儲所占用的資源，對節(jié)省內(nèi)存起到一定的作用。但是文獻[4]沒有考慮矩陣Mk的計算復雜度。在單個DSP中，矩陣的乘法是利用多層次的循環(huán)來實現(xiàn)的。如果不使用并行優(yōu)化，對兩個4×4的矩陣相乘所需要的運行周期為3 963，至于維數(shù)為31×31的兩個矩陣的乘法，運行時間將會大大增加，這在實際項目工程中是不適用的。因此，提出了一種新的算法，不僅可以節(jié)省內(nèi)存，還可以減少運行時間。

文獻[4]將分段思想應用到偽隨機序列的生成中。在此啟發(fā)下，將循環(huán)替換思想應用到偽隨機序列的常規(guī)生成算法中。循環(huán)替換算法示意圖如圖1所示。

從圖1可以看到，內(nèi)存分配只需要36個單元，每次迭代后的新一輪數(shù)據(jù)被放到與前一輪中對應的單元中，對應圖中為x1(32n)放在了x1(0)單元中。這樣僅占用36×2個單元就完成了x1(n)和x2(n)各自的前1 600個數(shù)據(jù)的獲取。

本例中，根據(jù)Nc=1 600來選擇前部分的長度為32，后半部分的數(shù)據(jù)與隨機序列的生成機制有關，在本例中是必須的。該方法可應用到類似的算法中(即中間值在之后計算中不需要時)，可以省去大量不必要的中間值存儲，節(jié)省了內(nèi)存資源。

圖1　循環(huán)替換算法示意圖

2DSP實現(xiàn)及仿真分析

2.1DSP實現(xiàn)流程

改進算法在DSP中實現(xiàn)的流程圖如圖2所示。

圖2　DSP實現(xiàn)流程圖

本文采用TI公司的C64x系列實現(xiàn)DSP。該系列DSP采用了取指令和執(zhí)行指令可并行運行的哈佛結(jié)構(gòu)，程序總線和數(shù)據(jù)總線也是獨立運行的。其中，程序總線有256 bit，內(nèi)存單次操作取8條指令，達到了高度運行的目的。由于C64芯片具有高容量、運行速度快的特征，其被應用于綜合測試儀表的開發(fā)中。

2.2仿真分析

為比較常規(guī)算法、M(矩陣)算法和循環(huán)替換算法的優(yōu)劣，從時間復雜度和所占用的內(nèi)存兩個方面進行仿真分析?？紤]下面幾種情形下3種算法的時間復雜度和內(nèi)存占用量：

RS序列，帶寬為6RB，序列長度為24 bit；

RS序列，帶寬為6RB，序列長度為120 bit；

RS序列，帶寬為50RB，序列長度為200 bit；

RS序列，帶寬為100RB，序列長度為400 bit；

擾碼序列，帶寬為50RB，序列長度為1 920 bit；

擾碼序列，帶寬為50RB，序列長度為2 300 bit。

用這6組數(shù)據(jù)進行仿真，結(jié)果如圖3所示。

圖3　時間復雜度比較示意圖

為了清楚地表示3種算法的執(zhí)行效率，圖3中橫坐標采用對數(shù)形式。

從圖3可以看到， 與傳統(tǒng)算法相比，M算法有比較好的性能，隨著隨機序列長度的增加，M算法所執(zhí)行的周期數(shù)和常規(guī)算法的執(zhí)行時間差距呈線性增加。與M算法相比，循環(huán)替換算法可以更快地實現(xiàn)隨機序列的生成，當序列的長度很大時，它們之間的時間差變化不大。在時間要求不是很嚴格的場景，m序列也有比較好的性能。圖4給出了3種算法占用內(nèi)存的性能比較。

圖4　占用內(nèi)存比較圖示意圖

從圖4可以看出，3種算法所占用的內(nèi)存隨著序列長度的增長而線性增長，且隨著序列長度的增長，循環(huán)替換算法和M算法所占內(nèi)存差是常數(shù)，這兩種算法和常規(guī)算法所占用的內(nèi)存差隨著序列長度的增加而線性增加。其中，循環(huán)替換算法所占用的內(nèi)存幾乎為常規(guī)算法所占內(nèi)存的三分之一。

3結(jié)束語

針對偽隨機序列生成過程中大量中間值的不必要的內(nèi)存占用問題，提出了應用循環(huán)替換思想來實現(xiàn)LTE-A系統(tǒng)中偽隨機序列的生成。通過將常規(guī)算法、M算法和循環(huán)替換算法在時間復雜度和占用內(nèi)存兩個方面進行比較可知，M算法和循環(huán)替換算法要優(yōu)于常規(guī)算法，尤其是循環(huán)替換算法可以節(jié)省常規(guī)算法三分之一的時間和幾乎一半以上的內(nèi)存使用量。循環(huán)替換算法和M算法相比，循環(huán)替換算法優(yōu)于M算法。

該算法的可行性和實時性使其能夠很好地應用到作者參與的實驗室項目工程中。通過詳細介紹循環(huán)替換算法的執(zhí)行過程，說明了該算法可以推廣到類似的計算過程中，可以節(jié)省時間并占用少量的內(nèi)存。

參考文獻

[1] 3GPP TS 36.211v9.1.0,3rd Generation Partnership Project；Technical Specification Group Ration Access Network；Evolued Universal Terrestrial Radios Access(E-UTRA);Physical Channels and Modulation(Release 9)[S].2010.

[2] Divyanjali A,Pareek V.A new approach to pseudo random number generation[C]// International Conference on Advanced Computing & Communication Technologies,2014.

[3] 周孝忠，閔子健，袁慧梅.一種3GPP LTE偽隨機序列生成優(yōu)化算法[J].電視技術,2009,49(9):15-23.

[4] Min Lequan,Hu Kexin,Zhang Lijiao,et al.Study on Pseudo randomness of Some Pseudo random Number Generators with Application[C]//Ninth International Conference on Computational Intelligence and Security, 2013.

中圖分類號：TH86;TP301+.6

文獻標志碼：A

DOI:10.16086/j.cnki.issn1000-0380.201602005

國家重大科技專項基金資助項目(編號：2011ZX03001-003-01、2012ZX03001009-004)。

修改稿收到日期：2015-05-20。

第一作者李小文(1955-)，男,1988年畢業(yè)于重慶大學信號與系統(tǒng)專業(yè)，獲碩士學位，高級工程師；主要研究方向為無線移動通信系統(tǒng)協(xié)議。