第5章Turbo碼并行譯碼器VLSI結構設計5.1Turbo碼的并行譯碼方法5.2Turbo碼子塊并行譯碼器VLSI結構設計5.3Turbo碼并行譯碼QPP交織器VLSI結構設計5.4并行QPP交織器的硬件設計5.5理論分析與硬件測試本章小結

5.1Turbo碼的并行譯碼方法

LTE系統(tǒng)turbo碼編譯碼器的原理框圖如圖5.1所示，在發(fā)送端，turbo碼編碼器由兩個卷積碼編碼單元和一個交織器組成。包含K個信息比特的數據塊xk,k=0,1,L,K-1，輸入turbo碼編碼器后一方面作為輸出系統(tǒng)比特（SystematicBits），另一方面通過編碼單元來產生相應的校驗比特（ParityBits）。

圖5.1Turbo碼編譯碼器原理框圖

卷積碼編碼單元1接收正常次序的信息比特序列{xk}并輸出相應的校驗比特序列

，類似地編碼單元2接收交織次序的信息比特序列

并輸出

，其中

表示交織函數。編碼后的turbo碼具有固定的

碼率，可以通過打孔等操作來實現碼率變換。經過符號映射、調制并通過無線信道傳輸后，接收端利用軟檢測器來得到

的對數似然比（Log-LikelihoodRatio，LLR），它們分別記作

與

。以

為例，其具體形式為

它代表了相應的比特取1或

的概率大小，故LLR也被稱為比特軟信息。

5.1.1基于符號的MAP譯碼算法

為了便于討論，我們將SISO譯碼單元輸入的系統(tǒng)位與校驗位軟信息分別記作Lsk與Lpk，類似于卷積碼的Viterbi譯碼算法，SISO譯碼單元運行的Log-MAP算法和max-log-MAP算法可以利用卷積碼網格進行遞歸運算。令ak(s)和βk(s)

分別表示網格第k級狀態(tài)

的前向狀態(tài)度量與反向狀態(tài)度量；定義

為連接網格第k-1級狀態(tài)s?與第k級狀態(tài)s的分支所對應的分支度量，其計算方式如下：

(5.1)

利用(5.1)-(5.6)，SISO譯碼單元實現了對系統(tǒng)位軟信息

Lsk、校驗位軟信息Lpk以及先驗信息LAk的處理來得到判決軟信息LDk和外信息LEk。具體到turbo碼譯碼器中，如圖5.1所示，分量譯碼單元1利用Lsk，

以及先驗信息

來計算判決軟信息

和外信息

。類似地分量譯碼單元2利用

以及先驗信息

來計算判決軟信息

和外信息

。迭代譯碼操作表現為SISO譯碼單元之間的外信息交互，即

(5.7)

這里

表示解交織函數。

5.1.2子塊并行譯碼與塊交織流水線策略

子塊并行譯碼方法將長度為

的turbo碼碼塊劃分為P個長度為S=K/P的子塊并對每個子塊進行獨立處理，圖5.2(a)以P=2為例對子塊并行譯碼器結構進行說明。在執(zhí)行子塊并行譯碼算法時，需要對每個子塊左側邊界的前向狀態(tài)度量和右側邊界的反向狀態(tài)度量進行有效估計。

圖5.2子塊并行譯碼結構與基于塊交織流水線方式的SISO譯碼策略

圖5.2子塊并行譯碼結構與基于塊交織流水線方式的SISO譯碼策略

5.1.3滑動窗譯碼與前后向交叉譯碼方式

在SISO譯碼過程中，狀態(tài)度量和分支度量需要在計算判決軟信息之前進行緩存。盡管子塊并行譯碼方法以及塊交織流水線策略的使用能夠實現譯碼器吞吐量與計算資源使用效率的提升，每個子塊內仍然需要存儲全部狀態(tài)度量與分支度量，從這一點來看譯碼器的數據存儲開銷并未減小?；瑒哟白g碼和前后向交叉譯碼方法旨在對SISO譯碼算法的前向狀態(tài)遞推、反向狀態(tài)遞推以及軟信息計算操作進行合理調度來避免譯碼過程中大量的數據緩存。

滑動窗譯碼方法將長度為S的子塊進一步劃分為L個長度為W=S/L的窗口，并按照圖5.3所示的方式將不同SISO譯碼操作分布在不同的窗口上執(zhí)行，這樣每個子塊內只需要對用于初始化反向狀態(tài)度量的窗口存儲分支度量以及對執(zhí)行反向狀態(tài)遞推的窗口存儲分支度量與狀態(tài)度量。

圖5.3基于滑動窗譯碼與前后向交叉譯碼方式的子塊并行譯碼方法

前后向交叉譯碼在一定程度上克服了滑動窗譯碼所面臨的計算與控制復雜度高的問題，它對SISO譯碼操作的調度方法在圖5.3上半部分給出。不難發(fā)現前后向交叉譯碼不涉及到子塊數據的分窗口操作，也不需要在子塊并行譯碼執(zhí)行前預估各子塊邊界處的度量值。不過以前后向交叉譯碼方式工作的SISO譯碼單元在存儲開銷的降低幅度上不及滑動窗譯碼方法，因為每個子塊在處理中至少需要存儲1/2個子塊長度的狀態(tài)度量和分支度量；另一方面，前后向交叉譯碼使得SISO譯碼單元不能以恒定速率向外輸出判決軟信息與外信息，這給外信息的存儲和交織器設計帶來一定挑戰(zhàn)。

5.2Turbo碼子塊并行譯碼器VLSI結構設計

綜合上一節(jié)討論的并行譯碼方法，我們可以得到如圖5.4(a)所示的turbo碼子塊并行譯碼器頂層框圖，其中接收碼塊被劃分為P個子塊，譯碼器中配置了N=P/λ個SISO譯碼單元，這里假設第n個SISO譯碼單元采用塊交織流水線策略來處理第P(n-1)/N+1至第pn/N個子塊。每輪迭代譯碼通過兩個半輪來完成，N個SISO譯碼單元在這兩個半輪中分別作為分量譯碼器1和分量譯碼器2來處理譯碼輸入。

在譯碼器中實現(5.7)所描述的外信息交互有兩種方法：

非平衡式調度：如圖5.4(b)所示，在前半輪迭代并行SISO譯碼單元以自然序讀取先驗信息和存儲外信息；在后半輪迭代并行SISO譯碼單元以交織次序讀取先驗信息，并以解交織次序存儲外信息；

平衡式調度：如圖5.4(c)所示，在前半輪迭代并行SISO譯碼單元以自然序讀取先驗信息，并以解交織次序存儲外信息；在后半輪迭代并行SISO譯碼單元以自然序讀取先驗信息，并以交織次序存儲外信息。

圖5.4Turbo碼子塊并行譯碼器頂層結構與迭代調度方案

圖5.4Turbo碼子塊并行譯碼器頂層結構與迭代調度方案

基于塊交織流水線策略的SISO譯碼單元VLSI實現結構如圖5.5所示。圖5.5基于塊交織流水線策略的SISO譯碼單元設計方案

需要指出的是，

在turbo碼譯碼器中塊交織流水線因子為

的SISO譯碼單元并非僅能處理λ個子塊，通過調整輸入數據讀取方式，可支持任意M個子塊的分時處理，其中對各個子塊數據的讀取以max{M,λ}個時鐘周期為單位循環(huán)執(zhí)行：

如果M<λ，此時讀取操作的循環(huán)周期為λ個時鐘周期，并將其中第

時鐘周期作為第i個子塊的操作時隙。具體的數據讀取方式為：在第1個時隙更新讀地址并讀取第1個子塊的數據，在第2至第M個時隙內用同樣的地址依次讀取第2至第M個子塊的數據，將第M+1個時隙至第4個時隙作為空閑時隙；

如果

，此時讀取操作的循環(huán)周期為M個時鐘周期，并將其中第

時鐘周期分配給第i個子塊作為操作時隙；此時的數據讀取方式為：在第1個時隙更新讀地址并對讀取第1個子塊的數據，在隨后的M-1個時隙內用同樣的地址依次讀取第2至第M個子塊的數據。

利用硬件電路實現狀態(tài)度量遞推時，考慮到狀態(tài)度量值均采用了定點表示形式，為了避免數據的溢出，需要對每次遞推得到的狀態(tài)度量進行歸一化處理。根據Max-log-MAP算法的原理，進行歸一化之前首先應求出當前狀態(tài)度量中的最大值，再從其他狀態(tài)度量中減去這一最大值，即可實現狀態(tài)度量的歸一化。當采用radix-2v譯碼算法時，在(5.4)的基礎上歸一化過程可以表示為：

其中

和

分別表示歸一化后的前向和反向狀態(tài)度量。為了縮短狀態(tài)度量的更新周期，可以將上述歸一化方式改進為：利用前一組狀態(tài)度量的最大值對當前的狀態(tài)度量進行歸一化，即：

基于以上延遲歸一化方案，歸一化因子的確定與新狀態(tài)度量的計算可以并行執(zhí)行，從而加速狀態(tài)度量的更新周期。

表5.1以raidx-4譯碼算法中，第2k時刻的狀態(tài)度量計算過程為例描述了各時鐘周期下ACS單元在計算某一前向狀態(tài)度量

的詳細操作，其中的CLK#1、CLK#2、CLK#3和CLK#4用于指代譯碼過程中連續(xù)的4個時鐘周期，狀態(tài)度量總數假定為8個，且每一級的狀態(tài)與前一級的4個狀態(tài)相連接。

5.3Turbo碼并行譯碼QPP交織器VLSI結構設計

5.3.1外信息存儲模式與QPP交織器的數學表示

我們定義

的矩陣M來表示外信息LEk的存儲模式，在物理上它對應于由多個存儲器組成的存儲陣列。參數ρ表示SISO譯碼單元在同一時刻輸出的外信息或者讀取的先驗信息個數，則在滑動窗譯碼和前后向交叉譯碼方式下分別有ρ=v和ρ=2v

。將M中的相鄰ρ行聚合為一個子矩陣，這樣它可以重新表示為分塊矩陣的形式，即

(5.8)

定理5.1：對于(5.10)所定義的QPP交織器，假設參數S滿足S|K，那么對于

，

其中

表示下取整運算。

5.3.2支持無沖突訪問的外信息存儲模式

為了設計合理的外信息存儲模式M以支持數據的無沖突存取，需要首先準確描述外信息送入存儲陣列以及先驗信息離開存儲陣列的數據次序而這一點與SISO譯碼單元的工作方式密切相關。具體來講，第n+1個執(zhí)行radix-2v算法的譯碼單元在時刻t會處理網格中連續(xù)ρ級的譯碼數據，這些網格級數可以表示為

，其中對于以滑動窗譯碼方式工作的SISO譯碼單元，

具有如下的形式：

(5.11)

當SISO譯碼單元以前后向交叉譯碼方式工作時，wi(t)則應當寫作：

類似于先驗信息的邏輯讀地址ai,n(t)，這里定義外信息的邏輯寫地址為

ei,n(t)同樣描述了外信息寫入存儲陣列的次序。

要避免發(fā)生數據訪問沖突，應當保證寫入存儲陣列或者從存儲陣列中讀出的數據都對應于不同的存儲器。也就是說，需要設計存儲模式M以保證對于i=0,L,ρ-1以及n=0,L,N-1，Nρ

個邏輯讀地址

與邏輯寫地址

都能映射到M的不同的行上。下面我們首先在算法5.1中給出存儲模式M的具體形式，然后在證明M能夠支持無沖突的數據訪問。

圖5.6以K=16,f1=3,f2=8的QPP交織器為例給出了不同情形下存儲模式M的形式。對于兩個邏輯寫地址

，由算法5.1可知它們對應的存儲器組序號分別為n1和n2，而在各自存儲器組內所對應的存儲器標號分別為

與

。

圖5.6不同turbo碼譯碼器中存儲模式

實例

圖5.6不同turbo碼譯碼器中存儲模式

實例（QPP交織器參數K=16,f1=3,f2=8

）

引理5.1：設c1,c2是正整數，a,b為任意整數，那么.

與此同時，文獻[33]對QPP函數參數

和

的數學性質進行了深入研究，并得出如下結論：

基于上述討論和理論準備，我們給出如下定理：

定理5.2：對于采用QPP交織器的turbo碼，如果碼塊長度

是4的倍數，即

，那么算法4.1定義的存儲模式M能夠支持先驗信息無沖突訪問的充要條件是

滿足

(5.15)

5.4并行QPP交織器的硬件設計

5.4.1數據寫入電路結構

其中

?？梢钥吹?5.16)建立了SISO譯碼單元輸出的外信息和存儲器組內的v個存儲器之間的對應關系。值得注意的是，由于

與參數t無關，故該對應關系是時不變的。另一方面，物理地址

可以寫作

在前后向交叉譯碼模式下，數據存儲的物理地址ζi表示為

可以發(fā)現SISO譯碼單元輸出的2v個外信息在存儲時，前一半數據和后一半數據將分別用到的不同的物理地址。以前后向交叉譯碼方式工作的子塊并行譯碼器中數據寫入電路的設計框圖如圖5.7b所示，和滑動窗譯碼情形下的設計相比，地址產生單元需要在同一時刻產生兩個物理地址來分別完成每個SISO譯碼單元輸出的前v個和后v個外信息的存儲，并且在存儲器組內部署了一個蝶形換向器來改變數據流與存儲器的對應關系。蝶形換向器的控制邏輯

可以選取

與

的最后一個數據位經過同或運算得到。當c=0時，蝶形換向器不改變2v個外信息的次序；反之將前v個與后v個外信息進行對換。

圖5.7Turbo碼子塊并行譯碼器的外信息寫入電路設計框圖

圖5.7Turbo碼子塊并行譯碼器的外信息寫入電路設計框圖

5.4.2數據讀取電路的讀地址產生器

定理5.3：QPP交織地址

的v步遞歸計算方法如下：

其中

，參數v為正表示地址的前向遞歸生成，為負表示地址的反向遞歸生成。

當4|K時我們有f2mod2=0，此時QPP交織地址還滿足

上式表明一旦確定出連續(xù)的K|4個交織地址，其余3K|4個地址可以通過非遞歸的方式來確定。

為了充分利用定理5.4的數學性質，我們將Nρ個邏輯讀地址劃分為ρ個地址組，并用

來表示第i=1個地址組。可以看到，

的N個地址具有相同的下標i且下標n遍歷了

，因此它們滿足定理5.4中描述的數學特性。為了從存儲陣列中準確地讀取數據，需要利用

ai,n(t)的余項εi,n來進一步確定存儲器標號

和物理讀地址

。對于地址組

內包含的N個邏輯地址，

(1)可以利用前N/2個邏輯地址來確定出全部的N個存儲器組序號

，這是因為(5.24)和(5.25)表明同一地址組內的N個邏輯地址所對應的存儲器組序號具有較強的相關性；

(2)存儲器標號

和物理讀地址

可以通過任一邏輯地址來得到，這是因為

且

，而(5.23)表明

內的N個邏輯地址具有相同的余項εi,n?；谶@一點，在下面的討論中我們略去εi,n的下標n來使數學表達式得到簡化。

上述分析表明，通過每個地址組內的前N/2個地址將足以確定出該地址組內所有邏輯地址的存儲器組序號、存儲器標號以及物理讀地址。讀地址生成單元的頂層設計方案如圖5.8(a)所示，進一步在圖5.8(b)中，我們以配置兩個SISO譯碼單元的radix-2前后向交叉譯碼turbo碼譯碼器為例對讀地址生成單元中各模塊的功能進行說明，其中QPP交織器參數設置為K=16,f1=3,f2=8。一般地，讀地址單元內需要配置ρ個邏輯地址產生單元，其中第i個單元負責產生地址組

內的前N/2個交織地址。當

時，邏輯地址產生單元具有圖5.9所示的底層硬件結構，其中前N/4個地址按照定理5.3描述的遞歸方式產生，而另外N/2個地址則利用(5.22)描述的非遞歸方式獲得。

圖5.8讀地址生成單元頂層結構框圖及其工作方式說明

圖5.9邏輯讀地址產生單元的硬件結構

對于送入同一地址轉換器的N/2個交織地址，QPP交織器所具有的最大無沖突特性使得它們具有不同的存儲器組序號。不過在硬件實現中并不需要部署N/2條完整的q級流水線比較結構來獨立處理各交織地址。從(5.24)和(5.25)可以看出在二元域內存儲器組序號之間具有較強的相關性，從這一特性出發(fā)，我們只對前N/4條流水線裝配第2級比較結構，對前N/8條流水線裝配第3級比較結構并以此類推來構建出N/2條流水線。在上述分析的基礎上，圖5.10以N=8的情況為例給出了地址轉換器的硬件設計方案。

圖5.10地址轉換器的硬件結構（N=8

）

圖5.11物理地址提取與路由單元的硬件結構（ρ=8

）

5.4.3數據讀取電路中數據路由單元

上面介紹的讀地址產生單元將邏輯讀地址逐步轉化為存儲器組序號、存儲器標號以及物理地址來實現從存儲陣列中獲得所需的先驗信息數據。在數據讀取電路中，數據路由網絡的作用是將所讀取的先驗信息正確分發(fā)至各SISO譯碼單元，為此需要將每個先驗信息數據與其所對應的邏輯讀地址關聯(lián)起來。圖5.12(a)給出了數據路由網絡的頂層設計方案，進一步在圖5.12(b)中，我們以配置兩個SISO譯碼單元的radix-2前后向交叉譯碼器為例對數據路由網絡中各模塊的功能進行說明，其中QPP交織器參數為K=16,f1=3,f2=8。

圖5.12數據路由網絡頂層結構框圖及其工作方式說明

圖5.12數據路由網絡頂層結構框圖及其工作方式說明

在圖5.13中，我們以ρ=4為例對數據組排序單元的結構進行描述。圖5.13數據組排序單元的硬件結構（ρ=4

）

圖5.14利用反轉蝶形互聯(lián)網絡來實現數據組內先驗信息的排序（N=4

）

5.5理論分析與硬件測試

5.5.1不同QPP交織器設計方案的復雜度分析

由圖5.4(a)可以看出，交織器的數據讀取電路可以劃分為讀地址產生單元和數據路由網絡兩部分且兩者在一定程度上彼此關聯(lián)：讀地址產生單元在地址變換過程中要同時產生數據路由網絡的控制信號，而數據路由網絡的具體拓撲結構則同樣影響著讀地址產生單元的計算復雜度。

因此對于給定的存儲模式M，數據路由網絡拓撲結構的選擇將同時影響其自身以及讀地址產生單元的復雜度，進而決定整個數據讀取電路的硬件資源開銷。在硬件實現中，讀地址產生單元需要利用到數據選擇器和加法器，而數據路由網路則主要由數據選擇器構成。表5.2對基于不同網絡結構所設計的QPP交織器中數據讀取電路占用的數據選擇器和加法器數目進行估計，以此來衡量各方案的硬件復雜度。這里N表示子塊并行譯碼器中SISO譯碼單元的數目，ρ代表每個SISO譯碼單元在同一時刻讀取的先驗信息個數，對于radix-2v滑動窗譯碼方式有ρ=v

，而對于前后向交叉譯碼方式有ρ=2v

。

進一步在圖5.15和圖5.16中，我們取定參數ρ來衡量在不同子塊并行度下各類QPP交織器設計方案對數據選擇器和加法器的消耗。

圖5.15不同并行度下各QPP交織器設計方案對數據選擇器的消耗對比

圖5.16不同并行度下各QPP交織器設計方案對加法器的消耗對比

5.5.2QPP交織器的硬件實現與測試

對于交織器的數據讀取電路而言，其消耗的數據選擇器和加法器在FPGA內主要由sliceLUTs構成，因此我們首先關注QPP交織器的不同實現方案在這一指標上的表現。從表5.3和表5.4的統(tǒng)計數據來看，本章的設計方案所需的sliceLUTs資源與SISO譯碼單元數目N近似呈線性關系，這一趨勢與表5.2的理論估計一致。另一方面在N=8的情況下通過比較滑動窗譯碼和前后向交叉譯碼方式下三種設計方案對slice單元總的消耗可以發(fā)現，本章提出的基于蝶形互聯(lián)網絡的交織器在ρ=4時所占用的硬件資源大約是ρ=2情形下的2倍，而基于交叉開關網絡和主從Batcher網絡的兩種對比方案在ρ=2至ρ=4的變化過程中硬件資源消耗分別增加為原來的4倍和3倍左右。

進一步，將三種交織器的數據讀取電路內各模塊slice消耗情況以直方圖的形式展現在圖5.17中。由于本章的設計方案在同一時刻只產生和變換Nρ/2個交織地址，因而地址產生單元的硬