Turbo碼中基4并行QPP交織器算法研究

史宜巧，李 叢

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

0 引 言

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

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

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

1 QPP交織器原理

3GPP在LTE標準中采用了二次置換多項式（QPP）交織器作為Turbo碼的內交織器，通過二次多項式推導計算交織地址，最終轉換為遞推計算。

1.1 QPP交織器遞推運算

QPP交織器中，輸出的下標和輸入下標∏（）的關系滿足如下二次方程式：

其中，和取決于塊的大小，在文獻［11］中，3GPP一共規定了188種不同長度的。

文獻［12］對∏（）求解做進一步推導，如下：

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

1.2 并行QPP交織器設計

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

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

由文獻［13］可知，QPP交織器是一個無競爭交織器，即：

其中，＝｛0，1，2，3｝，表示塊編號。先假設0，由于交織分塊進行，可以重新表示為：

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

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

為簡化運算，使硬件實現中不出現求余運算，令g（）（）mod，代入式（6），再結合式（5）性質可得：

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

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

上述求解僅僅是針對（），而（）（｛1，2，3｝）可以根據（）求解，推導公式如下：

2 基4并行QPP交織器算法設計

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

圖2 基4并行QPP交織器結構示意圖Fig.2 Schematic diagram of radix-4 parallel QPP interleaver

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

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

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

算法：計算Π（2）與Π（2+1）

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

可以看出通過本文設計，能夠實現利用單個輸入計算輸出多個地址，即單輸入多輸出（SIMO）。

3 FPGA設計與仿真分析

為了證明本文設計可行性，對以上提出的算法使用FPGA實現，驗證仿真結果，并與已有方案進行對比，實現語言采用Verilog。

3.1 FPGA設計與硬件復雜度

交織器的頂層電路如圖4所示，主要包括查找表模塊與交織模塊兩部分，其中后者主要為前者計算交織地址提供輸入。這是因為交織地址的計算是遞推過程，需要提供初始值與必要的參數。

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

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

圖5 交織模塊實現Fig.5 Interleaver module

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

表1 硬件開銷對比Tab.1 Hardware overhead comparison

3.2 仿真分析

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

在交織模塊的輸出結果基礎上，根據式（4）可以計算最終的交織地址，并且將包含正確交織地址Matlab仿真結果讀入，仿真結果如圖7所示。與FPGA仿真結果進行比對，如果有錯誤地址輸出，則令計數加1。從圖7可以看出，每個時鐘輸出了8路地址，并且沒有發生錯誤，說明本設計可以高效、正確地實現地址交織功能。

圖7 仿真結果Fig.7 The simulation results

4 結束語

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