史宜巧，李 叢

（1江蘇電子信息職業(yè)學(xué)院 智能制造學(xué)院，江蘇 淮安 223003；2南京理工大學(xué) 泰州科技學(xué)院，江蘇 泰州 225300）

0 引 言

信道編碼是提高信道可靠性的重要理論和方法，Turbo編碼就是其中之一。Turbo編碼應(yīng)用了隨機(jī)編譯碼條件，將卷積編碼與隨機(jī)交織器結(jié)合在一起，采用軟輸出迭代譯碼來逼近最大似然譯碼，從而獲得了接近Shannon理論極限的譯碼性能。

Turbo由分量碼和交織器級(jí)聯(lián)而成，因此，分量碼和交織器設(shè)計(jì)的優(yōu)劣直接影響著Turbo碼性能。其中，交織器主要功能是減小相鄰比特之間的相關(guān)性，針對(duì)其研究主要從交織算法以及交織結(jié)構(gòu)兩個(gè)角度進(jìn)行。文獻(xiàn)［6］提出一種利用內(nèi)存映射矩陣進(jìn)行地址交織的方法，將每一個(gè)譯碼器的輸出填充到標(biāo)記為（）的存儲(chǔ)器中，而這其中的映射關(guān)系由映射矩陣決定，但是矩陣需要使用退火算法逐級(jí)填充，求解過程較為復(fù)雜；文獻(xiàn)［7］基于通用處理器（GPP）架構(gòu)的實(shí)時(shí)信號(hào)處理技術(shù)，利用單指令多數(shù)據(jù)（SIMD）技術(shù)一條指令可以處理多個(gè)數(shù)據(jù)的特點(diǎn)，從指令級(jí)進(jìn)行優(yōu)化，提出一種高度并行的交織器，為DSP信號(hào)處理提供了良好的借鑒。為了消除并行交織譯碼過程中可能帶來的地址沖突，引入了二次置換多項(xiàng)式交織算法（QPP），該交織器具有2個(gè)特點(diǎn)，一是從個(gè)并行SISO計(jì)算出來的個(gè)外信息在解交織后，總能夠被存入到個(gè)不同的存儲(chǔ)器中；二是該交織器是個(gè)并行SISO所需要訪問的個(gè)交織地址總是指向個(gè)存儲(chǔ)器的同一個(gè)位置。文獻(xiàn)［9］提出一種基于置換模式的優(yōu)化交織器方案，該方案利用一個(gè)統(tǒng)一的交織硬件電路來計(jì)算所有并行的交織地址。其交織電路的設(shè)計(jì)雖然較優(yōu)，但由于需要保存不同配置下的初始交織模式，因而總體的硬件復(fù)雜度較高。文獻(xiàn)［10］針對(duì)實(shí)際譯碼過程中，為了滿足高階蝶形運(yùn)算需求，設(shè)計(jì)了一種基4蝶形交織器模型，通過奇偶地址分模塊并行計(jì)算實(shí)現(xiàn)，然而該模型中相鄰地址計(jì)算存在依賴，地址計(jì)算過程中遞推關(guān)系復(fù)雜。

為了更好地發(fā)揮交織器在Turbo譯碼中的作用，簡(jiǎn)化硬件實(shí)現(xiàn)，本文提出一種基4并行QPP交織器算法。文章內(nèi)容安排如下：首先介紹QPP交織器原理，并通過遞推簡(jiǎn)化交織地址在并行計(jì)算情況下存在的求余等復(fù)雜運(yùn)算；然后進(jìn)一步推導(dǎo)公式解除相鄰交織地址計(jì)算的依賴關(guān)系，從而提出本文的QPP基4交織器；最后對(duì)本文提出的算法使用Verilog語言設(shè)計(jì)實(shí)現(xiàn)，并借助FPGA仿真工具與Matlab仿真結(jié)果對(duì)比，結(jié)果表明本文算法用于FPGA實(shí)現(xiàn)交織輸出結(jié)果完全正確，并且通過相同工藝下的與其他方案對(duì)比，顯示本文設(shè)計(jì)綜合面積減小50%左右，證明硬件開銷更小。

1 QPP交織器原理

3GPP在LTE標(biāo)準(zhǔn)中采用了二次置換多項(xiàng)式（QPP）交織器作為Turbo碼的內(nèi)交織器，通過二次多項(xiàng)式推導(dǎo)計(jì)算交織地址，最終轉(zhuǎn)換為遞推計(jì)算。

1.1 QPP交織器遞推運(yùn)算

QPP交織器中，輸出的下標(biāo)和輸入下標(biāo)∏（）的關(guān)系滿足如下二次方程式：

其中，和取決于塊的大小，在文獻(xiàn)［11］中，3GPP一共規(guī)定了188種不同長(zhǎng)度的。

文獻(xiàn)［12］對(duì)∏（）求解做進(jìn)一步推導(dǎo)，如下：

其中，（1）（2（1））mod，很容易得知∏（）可以根據(jù)∏（1）和（1）遞推獲得。

1.2 并行QPP交織器設(shè)計(jì)

考慮到高速Turbo碼并行譯碼設(shè)計(jì)的需要，交織器也需要并行設(shè)計(jì)，可以將均分為個(gè)子塊，一般{1，2，3，4}，以4為例，則每個(gè)子塊長(zhǎng)度4，分塊后交織過程如圖1所示。

圖1 交織器并行計(jì)算示例Fig.1 Example of interleaver parallel computation

由文獻(xiàn)［13］可知，QPP交織器是一個(gè)無競(jìng)爭(zhēng)交織器，即：

其中，＝｛0，1，2，3｝，表示塊編號(hào)。先假設(shè)0，由于交織分塊進(jìn)行，可以重新表示為：

由式（3）可知，第時(shí)刻并行輸出的4個(gè)交織地址塊內(nèi)偏移量∏（）是一致的，因此每次并行計(jì)算出4個(gè)交織地址，實(shí)際上只需要計(jì)算出一個(gè)偏移量（）。

首先是∏（），由于4·，那么可得（mod）modmod，已知求余運(yùn)算有以下性質(zhì)：

為簡(jiǎn)化運(yùn)算，使硬件實(shí)現(xiàn)中不出現(xiàn)求余運(yùn)算，令g（）（）mod，代入式（6），再結(jié)合式（5）性質(zhì)可得：

從式（9）可知，∏（）可以根據(jù)∏（-1）和g（-1）遞推得到。將g（）＝（）mod代入式（9）可得：

其中，＝（2）mod。由上式可知，g（）可以通過g（-1）遞推得到。參照∏（）推導(dǎo)過程，同樣有：

上述求解僅僅是針對(duì)（），而（）（｛1，2，3｝）可以根據(jù)（）求解，推導(dǎo)公式如下：

2 基4并行QPP交織器算法設(shè)計(jì)

每時(shí)刻每個(gè)子塊僅輸出一個(gè)地址，因此遞推關(guān)系也僅存在于相鄰2個(gè)地址間，而實(shí)際的Turbo譯碼系統(tǒng)需要面臨高階蝶形運(yùn)算需求，例如基4蝶形譯碼系統(tǒng)中需要交織器同時(shí)輸出奇偶地址，如圖2所示。因此本文考慮設(shè)計(jì)一種算法，通過初始地址一次性計(jì)算得到奇偶地址。

圖2 基4并行QPP交織器結(jié)構(gòu)示意圖Fig.2 Schematic diagram of radix-4 parallel QPP interleaver

圖3 交織器算法原理圖Fig.3 Schematic diagram of interleaver algorithm

由圖3可知，要同時(shí)計(jì)算出2與2+1兩處地址，需要推導(dǎo)兩者與2-1處地址的關(guān)系。根據(jù)上述分析，計(jì)算交織地址采用遞推的方式，2與2+1處的地址實(shí)際上是相鄰的，因此存在遞推關(guān)系，以g（）為例，根據(jù)式（10）有：

從式（16）和式（17）中可以看出，g（21）的計(jì)算依賴于g（2），這樣奇偶地址無法同時(shí)計(jì)算。為消除兩者之間的依賴關(guān)系，對(duì)式（15）作進(jìn)一步遞推，將式（16）代入式（17）可得：

算法：計(jì)算Π（2）與Π（2+1）

q（2）與q（21）以及（2）與（2+1）的計(jì)算類似，即通過往后遞推一步，解除時(shí)刻計(jì)算2與2+1兩處地址所需變量之間的依賴關(guān)系，保證奇偶地址可以同時(shí)輸出。

可以看出通過本文設(shè)計(jì)，能夠?qū)崿F(xiàn)利用單個(gè)輸入計(jì)算輸出多個(gè)地址，即單輸入多輸出（SIMO）。

3 FPGA設(shè)計(jì)與仿真分析

為了證明本文設(shè)計(jì)可行性，對(duì)以上提出的算法使用FPGA實(shí)現(xiàn)，驗(yàn)證仿真結(jié)果，并與已有方案進(jìn)行對(duì)比，實(shí)現(xiàn)語言采用Verilog。

3.1 FPGA設(shè)計(jì)與硬件復(fù)雜度

交織器的頂層電路如圖4所示，主要包括查找表模塊與交織模塊兩部分，其中后者主要為前者計(jì)算交織地址提供輸入。這是因?yàn)榻豢椀刂返挠?jì)算是遞推過程，需要提供初始值與必要的參數(shù)。

圖4 頂層模塊圖Fig.4 Top module diagram

其中，交織模塊的內(nèi)部實(shí)現(xiàn)如圖5所示，可以看到整個(gè)模塊都被簡(jiǎn)化成了判決單元與一些計(jì)算單元，而根據(jù)第2節(jié)代碼可以知道這些計(jì)算單元只包括加減運(yùn)算，因此綜合出來的電路非常簡(jiǎn)單。另外可以看出上一輪計(jì)算得到的g（）、∏（）以 及q（）都要作為返回值參與下一輪計(jì)算。

圖5 交織模塊實(shí)現(xiàn)Fig.5 Interleaver module

將所設(shè)計(jì)的交織器的硬件復(fù)雜度與已有的技術(shù)方案進(jìn)行對(duì)比，在SMIC40 nm工藝下對(duì)本文設(shè)計(jì)進(jìn)行綜合，并與文獻(xiàn)［9］和文獻(xiàn)［16］所提出的方案進(jìn)行了對(duì)比，見表1。表1中，文獻(xiàn)［9］采用radix-4，每個(gè)時(shí)鐘通過8個(gè)SISO并行的方式輸出8個(gè)地址。文獻(xiàn)［16］采用radix-2，最高4個(gè)SISO同時(shí)運(yùn)行，也就是每個(gè)時(shí)鐘輸出4個(gè)地址，并且硬件實(shí)現(xiàn)包含了除法器。而本文的設(shè)計(jì)通過4個(gè)SIMO并行運(yùn)行每個(gè)時(shí)鐘輸出8個(gè)地址。本文設(shè)計(jì)的綜合面積僅有0.032 nm，通過歸一化面積比可以看出，本文方案相對(duì)于另外2種方案硬件開銷很小。

表1 硬件開銷對(duì)比Tab.1 Hardware overhead comparison

3.2 仿真分析

圖6 交織地址計(jì)算模塊輸出Fig.6 Interleaved address calculation module output

在交織模塊的輸出結(jié)果基礎(chǔ)上，根據(jù)式（4）可以計(jì)算最終的交織地址，并且將包含正確交織地址Matlab仿真結(jié)果讀入，仿真結(jié)果如圖7所示。與FPGA仿真結(jié)果進(jìn)行比對(duì)，如果有錯(cuò)誤地址輸出，則令計(jì)數(shù)加1。從圖7可以看出，每個(gè)時(shí)鐘輸出了8路地址，并且沒有發(fā)生錯(cuò)誤，說明本設(shè)計(jì)可以高效、正確地實(shí)現(xiàn)地址交織功能。

圖7 仿真結(jié)果Fig.7 The simulation results

4 結(jié)束語

本文提出了一種硬件優(yōu)化的基4四路并行QPP交織器，針對(duì)并行計(jì)算場(chǎng)景，簡(jiǎn)化地址遞推計(jì)算，并消除相鄰地址計(jì)算的依賴關(guān)系，最終可以每個(gè)時(shí)鐘并行輸出8路奇偶地址，不僅降低了硬件實(shí)現(xiàn)復(fù)雜度，也大大提高了地址計(jì)算的效率。仿真結(jié)果表明本設(shè)計(jì)硬件開銷較小，能夠正確地輸出交織地址，充分證明了本設(shè)計(jì)具有可行性。需要指明的是，為了方便QPP交織多項(xiàng)式的遞推計(jì)算，本文在分塊并行譯碼時(shí)，并行塊數(shù)必須滿足＝2，后續(xù)可以做進(jìn)一步優(yōu)化，將這種并行譯碼下的遞推關(guān)系一般化，以方便該并行交織器更好地滿足不同場(chǎng)景需求。