一種基于LTE -A的偽隨機(jī)序列生成的改進(jìn)算法
相關(guān)鏈接： 中國(guó)安全網(wǎng) 中國(guó)質(zhì)量網(wǎng) 中國(guó)論文網(wǎng) 中國(guó)資訊網(wǎng)
作者；張毅
偽隨機(jī)序列具有以下特征：一方面它是可以預(yù)先確定的，并且可以重復(fù)地生產(chǎn)和復(fù)制；另一方面它又具有某種隨機(jī)序列的隨機(jī)特性（即統(tǒng)計(jì)特性）。隨機(jī)噪聲的存在會(huì)對(duì)輸出信號(hào)進(jìn)行干擾，使信號(hào)產(chǎn)生失真。然而，人們?cè)谠噲D消除和減少通信系統(tǒng)中的隨機(jī)噪聲的同時(shí)也希望獲得隨機(jī)噪聲并充分利用它，用于更為有效的通信。目前先進(jìn)長(zhǎng)期演進(jìn)(long time evolution advance，LTE -A)正是利用偽隨機(jī)序列來(lái)對(duì)有用信號(hào)進(jìn)行加擾以提高在無(wú)線通信環(huán)境中的性能。它是利用一對(duì)周期和速率均相同的m序列優(yōu)選對(duì)異或后得到的。
在實(shí)際的項(xiàng)目工程中，不僅要求能夠快速準(zhǔn)確地實(shí)現(xiàn)通信，還要求盡量減少?gòu)?fù)雜度和內(nèi)存占用量。筆者主要從LTE -A中的Gold序列生成過(guò)程中內(nèi)存占用和執(zhí)行時(shí)間兩個(gè)方面來(lái)進(jìn)行研究�；谒龅腖TE -A綜測(cè)儀項(xiàng)目，本文提出一種循環(huán)替換算法。與常規(guī)算法相比，該算法可以大大減少內(nèi)存，提高執(zhí)行速度。
1 Gold序列生成算法
1.1 LTE -A系統(tǒng)偽隨機(jī)序列的生成
在LTE -A協(xié)議中，偽隨機(jī)序列是由長(zhǎng)度為31位的Gold序列生成的，用c(n)表示最后輸出的偽隨機(jī)序列，其中n=1，2，3，…，M，M為c(n)的長(zhǎng)度。用x1(n)和X2(n)表示兩個(gè)m序列，且x1(n)和x2(n)滿足下面的初始化：
不同的場(chǎng)合Ciru．的值不同。例如在LTE -A物理廣播信道( physical broadcast channel channel, PBCH)中，c；。。= NIcD'I（小區(qū)ID）；在下行共享信道中(physicaldownlink shared channel,PDSCH):
式中：n。為時(shí)隙號(hào)；nRNTI與無(wú)線網(wǎng)絡(luò)臨時(shí)鑒定(radionetwork temporary identifier,RNTI)有關(guān)。
x1(n)和X2(n)的遞推公式為：
偽隨機(jī)序列由下式?jīng)Q定：
式中：N。=1 600，N。是為了保證不同序列之間的非相關(guān)性而特意增加的狀態(tài)偏移量。
1.2偽隨機(jī)序列的常規(guī)算法
偽隨機(jī)序列c(n)生成過(guò)程中，兩個(gè)m序列分別由31個(gè)帶有反饋的線性移位寄存器移位產(chǎn)生。從上面的式子可以看出，正是Nc的存在使得兩個(gè)m序列x1(n)和x2(n)在普通算法中各自都要首先迭代Ne次，而且Gold序列作為偽隨機(jī)序列運(yùn)用在多種場(chǎng)合，并且有些應(yīng)用場(chǎng)合系統(tǒng)所需要生成的偽隨機(jī)序列非常短。例如，偽隨機(jī)序列作為PBCH的RS序列時(shí)，所需序列的長(zhǎng)度為48 bits，利用常規(guī)算法生成RS序列時(shí)需要移位l648次，而生成的序列長(zhǎng)度為48 bit，導(dǎo)致序列生成時(shí)間較長(zhǎng)，且浪費(fèi)了大量的系統(tǒng)資源。由式(5)可知，c(n)序列只與x1(n)和X2(n)的后M個(gè)值有直接關(guān)系，如果將x1(n)和X2(n)的全部值都保存起來(lái)會(huì)浪費(fèi)大量的內(nèi)存，在大的項(xiàng)目工程中則會(huì)影響系統(tǒng)的健壯性。正是基于這一點(diǎn)，提出了一種新的實(shí)現(xiàn)方法，可以節(jié)省大量?jī)?nèi)存，提高隨機(jī)序列生成的速度。
1.3算法優(yōu)化
目前，很多人對(duì)隨機(jī)序列生成中面臨的問題進(jìn)行了研究，也提出了很多的算法來(lái)優(yōu)化隨機(jī)序列的生成。例如，在文獻(xiàn)[3]中，提出利用狀態(tài)轉(zhuǎn)移矩陣和初始向量來(lái)減少兩個(gè)m序列x1(n)和X2(n)生成時(shí)的多次移位迭代。x1(n)定義公式寫成：
根據(jù)式(3)可知，ho =1，h。=0，n=1，2，3，…，30。定義初始狀態(tài)向量：
根據(jù)式(3)可知，移位反饋寄存器移位一次后的初始狀態(tài)向量變?yōu)椋?
式中：x．(31)是由式(3)計(jì)算出來(lái)的；x1(1)，x1(2)，…，x1(30)是由向量vo左移一位得到的。
則初始狀態(tài)向量左移k次得到中間向量Vk：
根據(jù)上面的分析可以得到31×31的狀態(tài)轉(zhuǎn)移矩陣M，其中矩陣的初始值和式(3)中的系數(shù)h。(n=0，1，2，3，…，30)有關(guān)：
利用狀態(tài)轉(zhuǎn)移矩陣，可得中間向量vl的計(jì)算公式為：
則移位反饋寄存器任意移動(dòng)K次得到的中間向量為：
式中：l，。向量為序列的第k位與第h+30位之間的值。
在式(12)中，根據(jù)狀態(tài)轉(zhuǎn)移矩陣M的初始狀態(tài)值可以計(jì)算出矩陣Mk，利用序列初始狀態(tài)值與矩陣M的乘積一次完成K次序列移位。該方法確實(shí)可以一次得到移位寄存器K次移位，節(jié)省很多中間值存儲(chǔ)所占用的資源，對(duì)節(jié)省內(nèi)存起到一定的作用。但是文獻(xiàn)[4]沒有考慮矩陣Mk的計(jì)算復(fù)雜度。在單個(gè)DSP中，矩陣的乘法是利用多層次的循環(huán)來(lái)實(shí)現(xiàn)的。如果不使用并行優(yōu)化，對(duì)兩個(gè)4x4的矩陣相乘所需要的行周期為3 963，至于維數(shù)為31×31的兩個(gè)矩陣的乘法，運(yùn)行時(shí)間將會(huì)大大增加，這在實(shí)際項(xiàng)目工程中是不適用的。因此，提出了一種新的算法，不僅可以節(jié)省內(nèi)存，還可以減少運(yùn)行時(shí)間。
文獻(xiàn)[4]將分段思想應(yīng)用到偽隨機(jī)序列的生成中。在此啟發(fā)下，將循環(huán)替換思想應(yīng)用到偽隨機(jī)序列的常規(guī)生成算法中。循環(huán)替換算法示意圖如圖1所示。
從圖1可以看到，內(nèi)存分配只需要36個(gè)單元，每次迭代后的新一輪數(shù)據(jù)被放到與前一輪中對(duì)應(yīng)的單元中，對(duì)應(yīng)圖中為x1(32n)放在了x1(0)單元中。這樣僅占用36 x2個(gè)單元就完成了x1(n)和X2(n)各自的前1 600個(gè)數(shù)據(jù)的獲取。
本例中，根據(jù)N=1 600來(lái)選擇前部分的長(zhǎng)度為32，后半部分的數(shù)據(jù)與隨機(jī)序列的生成機(jī)制有關(guān)，在本例中是必須的。該方法可應(yīng)用到類似的算法中（即中間值在之后計(jì)算中不需要時(shí)），可以省去大量不必要的中間值存儲(chǔ)，節(jié)省了內(nèi)存資源。
2 DSP實(shí)現(xiàn)及仿真分析
2.1 DSP實(shí)現(xiàn)流程
改進(jìn)算法在DSP中實(shí)現(xiàn)的流程圖如圖2所示。
本文采用TI公司的C64x系列實(shí)現(xiàn)DSP。該系列DSP采用了取指令和執(zhí)行指令可并行運(yùn)行的哈佛結(jié)構(gòu)，程序總線和數(shù)據(jù)總線也是獨(dú)立運(yùn)行的。其中，程序總線有256 bit，內(nèi)存單次操作取8條指令，達(dá)到了高度運(yùn)行的目的。由于C64芯片具有高容量、運(yùn)行速度快的特征，其被應(yīng)用于綜合測(cè)試儀表的開發(fā)中。
2.2仿真分析
為比較常規(guī)算法、M（矩陣）算法和循環(huán)替換算法的優(yōu)劣，從時(shí)間復(fù)雜度和所占用的內(nèi)存兩個(gè)方面進(jìn)行仿真分析�？紤]下面幾種情形下3種算法的時(shí)間復(fù)雜度和內(nèi)存占用量：
RS序列，帶寬為6RB，序列長(zhǎng)度為24 bit；
RS序列，帶寬為6RB，序列長(zhǎng)度為120 bit；
RS序列，帶寬為50RB，序列長(zhǎng)度為200 bit；
RS序列，帶寬為100RB，序列長(zhǎng)度為400 bit；
擾碼序列，帶寬為50RB，序列長(zhǎng)度為l 920 bit；
擾碼序列，帶寬為50RB，序列長(zhǎng)度為2 300 bit。
用這6組數(shù)據(jù)進(jìn)行仿真，結(jié)果如圖3所示。
為了清楚地表示3種算法的執(zhí)行效率，圖3中橫坐標(biāo)采用對(duì)數(shù)形式。
從圖3可以看到，與傳統(tǒng)算法相比，M算法有比較好的性能，隨著隨機(jī)序列長(zhǎng)度的增加，M算法所執(zhí)行的周期數(shù)和常規(guī)算法的執(zhí)行時(shí)間差距呈線性增加。與M算法相比，循環(huán)替換算法可以更快地實(shí)現(xiàn)隨機(jī)序列的生成，當(dāng)序列的長(zhǎng)度很大時(shí)，它們之間的時(shí)間差變化不大。在時(shí)間要求不是很嚴(yán)格的場(chǎng)景，m序列也有比較好的性能。圖4給出了3種算法占用內(nèi)存的性能比較。
從圖4可以看出，3種算法所占用的內(nèi)存隨著序列長(zhǎng)度的增長(zhǎng)而線性增長(zhǎng)，且隨著序列長(zhǎng)度的增長(zhǎng)，循環(huán)替換算法和M算法所占內(nèi)存差是常數(shù)，這兩種算法和常規(guī)算法所占用的內(nèi)存差隨著序列長(zhǎng)度的增加而線性增加。其中，循環(huán)替換算法所占用的內(nèi)存幾乎為常規(guī)算法所占內(nèi)存的三分之一。
3結(jié)束語(yǔ)
針對(duì)偽隨機(jī)序列生成過(guò)程中大量中間值的不必要的內(nèi)存占用問題，提出了應(yīng)用循環(huán)替換思想來(lái)實(shí)現(xiàn)LTE -A系統(tǒng)中偽隨機(jī)序列的生成。通過(guò)將常規(guī)算法、M算法和循環(huán)替換算法在時(shí)間復(fù)雜度和占用內(nèi)存兩個(gè)方面進(jìn)行比較可知，M算法和循環(huán)替換算法要優(yōu)于常規(guī)算法，尤其是循環(huán)替換算法可以節(jié)省常規(guī)算法三分之一的時(shí)間和幾乎一半以上的內(nèi)存使用量。循環(huán)替換算法和M算法相比，循環(huán)替換算法優(yōu)于M算法。該算法的可行性和實(shí)時(shí)性使其能夠很好地應(yīng)用到作者參與的實(shí)驗(yàn)室項(xiàng)目工程中。通過(guò)詳細(xì)介紹循環(huán)替換算法的執(zhí)行過(guò)程，說(shuō)明了該算法可以推廣到類似的計(jì)算過(guò)程中，可以節(jié)省時(shí)間并占用少量的內(nèi)存。
4摘要：在先進(jìn)長(zhǎng)期演進(jìn)( LTE - A)系統(tǒng)中，偽隨機(jī)序列生成時(shí)內(nèi)存占用量和執(zhí)行時(shí)間會(huì)隨著序列長(zhǎng)度的增加而顯著增加。針對(duì)該問題，提出了一種循環(huán)替換算法，即在3CPP LTE -A系統(tǒng)中的低消耗（內(nèi)存）、低復(fù)雜度的偽隨機(jī)序列生成算法。此外，對(duì)傳統(tǒng)偽隨機(jī)序列生成算法進(jìn)行了改進(jìn)，使得偽隨機(jī)序列生成過(guò)程中的內(nèi)存占用量和執(zhí)行時(shí)間大大縮短。仿真結(jié)果證明了所提出算法的高效性和低消耗性。該算法對(duì)提高整個(gè)系統(tǒng)的性能有一定的意義。
