Turbo碼并行無沖突交織器設計﹡

丘選鋒， 趙宏宇

（西南交通大學信息編碼與傳輸省重點實驗室，四川 成都 610031）

0 引言

1993年出現的Turbo碼，以接近香農限的性能證明了信道編碼定理的正確性[1]。采用迭代譯碼是Turbo碼優異性能的重要原因。但迭代譯碼的時延較大。并行譯碼方案則能夠顯著地降低時延，但交織器的隨機置換可能引起存儲器的地址爭用問題[2]。對此，提出了并行交織器。現有的并行交織器主要有：二次置換多項式交織器(QPP)[3]，行列 S交織器[4-5]。3GPP則采用在短交織塊時有較好性能的QPP交織器[6]。但QPP交織器的系數選擇有嚴格的限制[3]。行列S型交織器則是通過行和列的S交織產生的，對整個交織器，其S值不固定且偏小。對此，文中提出了一種新的并行交織器設計方案，S值是基于整個交織長度設定的。

1 無沖突限制和S型交織器

1.1 并行無沖突限制

設 X={x1,x2,…,xN}為交織器的輸入比特序列，xi∈{0,1}，1≤i≤N。經過交織器置換后輸出Y={y1,y2,…,yN}, yi∈{0,1}, 1≤j≤N。Y 包含了 X 的所有元素，但排列順序不同。X與Y之間存在一一對應關系。定義集合ZN={1,2,…,N}，則可用一個下標映射函數π()i來定義交織器π()i：,ij→ ,ij∈ZN。

考慮交織器π(),i并行度為M，分塊長W。并行譯碼時，M個外信息被要求同時寫入存儲陣列中，定義函數 ()Mi表示存儲陣列中存儲器的位置， ()Si表示存儲器中的位置，則π(i)=(M(i), S(i)) →{1,2,…,M}×{1,2,…,W}具有以下含義：第i個外信息被寫入到存儲陣列中第 ()Mi個存儲器中 S(i)的位置上，并行無沖突表現為對 ()Mi的限制；

第 j個時序，寫入存儲陣列中的 K個外信息K = j, j + W ,… , j + ( M - 1)W 若滿足：

則存儲器爭用問題可避免。

1.2 S型交織器

設π(i)表示ZN上的一個交織函數，若π(i)滿足：

對 任 意 的 i,j∈ZN且0＜|i - j |≤ S ， 有|π(i) - π (j) |≥ S[7]。則 π(i)為 S型交織器。參數 S稱為延展因子。對比均勻交織器，由于S參數約束的引入，S型交織器獲得了更好的性能。S值越大，性能越好， S值上限近似為[8]。

2 并行S型交織器設計

2.1 生成算法

長度為 N的交織器π(i)，分 M 塊，每塊長為W=N/M。首先生成一個M×W的矩陣，矩陣的每列元素均為{1,2,…,M}的隨機排列，表示同一時刻信息映射到存儲陣列中的不同存儲器位置。而存儲器中的具體位置用隨機方法產生。選擇 S ＜N/2, 設NB=2N表示對序列 St(1), St(2),…, St(W)進行循環左移的最大次數，NR=N表示生成數組M[N]和隨機序列St(W)的最大次數。具體生成算法如下：

1)初始化變量Nr=0,Nb=0。

2) Nr=Nr+1，如果Nr=NR，令S=S-1，返回1)；如果Nr

3)生成 M 組隨機排列，第 t組 St的元素為{(t-1)×W+1,(t-1)×W+2,…,(t-1)×W+W}的隨機排列，初始化nt=1，St[nt]表示第t組隨機排列St中的第nt個元素，t={1,2,…,M}。

4)當 i =1，在產生最終交織映射地址 π[1]前，判斷 M[1]的值，假如 M[1]=t，t∈{1,2,…,M}，則令π[1]= St[nt]，nt=nt+1；當i >1時，判斷M[i]的值，假如 M[i]=t，t∈{1,2,…,M}，則令 π[i]= St[nt]，判斷 π[i]是否滿足以下條件：

若滿足，令i=i+1，nt=nt+1；若不滿足，則交換St[nt]和 St[k]，k>nt，若所有的 k=nt+1,nt+2,…,W 都不滿足上述條件，則轉到5)。

5) Nb= Nb+1；如果Nb= NB，令Nb=0，返回步驟2)；如果Nb

①t[1]～t[W-nt+1]= St[nt]～ St[W];

②t[W-nt+2]～t[W]= St[1]～ St[nt-1];

③St[1]～ St[W]=t[1]～t[W];

且令 i=1，n1～nW=1，返回步驟 4)。

6)重復以上步驟，直到N個交織輸出都獲得。

2.2 性能驗證

在信噪比較大時，誤碼率由最小重量碼字決定。因此可用自由距離來估計和比較不同交織器的性能。在計算不同交織塊長的turbo碼自由距離時， 采用3GPP標準turbo碼，碼率為1/3。對每個交織塊長，各生成100個行列S隨機交織器，S隨機交織器和文中建議的交織器。通過約束字碼算法[9]計算使用每一個交織所生成的turbo碼自由距離，然后求出3種類型交織器的平均自由距離和100個交織器中的最大自由距離。結果列在表1中。從表1中可以看到，使用S型交織器的turbo碼字具有較大的自由距離，其次是采用文中方案交織器的turbo碼。而采用行列S型交織器的turbo碼的自由距離最小。這是因為它的S值偏小。并行度為4時，從表中可以看到文中給出的交織器S值接近 /2N 。

表1 交織器和相應的turbo碼自由距離

3 仿真結果及分析

仿真使用生成多項式為(1,13/15)octal的8狀態編碼器，碼率1/3；采用BPSK調制和高斯信道。譯碼用Max-Log-Map算法，迭代次數為4。仿真對比采用S型、行列S型、QPP和文中方案交織器的turbo碼譯碼性能。仿真結果如圖1和圖2所示。仿真中使用的3種交織器都是從100個相同類型交織器中選出的具有最大自由距離的交織器。從圖 1和圖 2可以看到S隨機交織器性能最佳，但它不具備并行特征。其次就是文中建議的交織器，而最佳Ω'參數的QPP和行列S隨機交織器性能則相對偏差。

圖1 誤碼率（M=4）

圖2 誤碼率（M=8）

4 結語

S隨機交織器是一種性能優異的交織器，但它不具備無沖突特性。而把S型交織設計成具有無沖突的特性是一種相對較好和靈活的路線。文中設計方案延續了以往的并行S隨機交織器設計方法并且針對現有的并行S隨機交織器S參數值較小的缺點，提出了一種新的并行S隨機交織器算法。由于S參數的改進，使用文中交織器的turbo碼有較大自由距離和較好的誤碼率并且能夠明顯地降低譯碼時延。

[1] 孫麗楠,王學東.Turbo乘積碼快速編碼 FPGA實現[J].信息安全與通信保密,2007(04):44-46.

[2] 黃卉,王輝.高速并行 Turbo譯碼中的交織器技術研究[J].通信技術,2008,41(06):83-85.

[3] RYU J,TAKESHITA O Y.On Quadratic Inverses for Quadratic Permutation Polynomials over Integer Rings[J]. IEEE Trans. Inf. Theory, 2006, 52(03):1255-1257.

[4] GAZI O,YILMAZ O.Collision Free Row Column S-random Interleaver[J]. IEEE Commun.lett., 2009,13 (04):257-259.

[5] 史堯,李博.Turbo碼并行譯碼中無沖突交織設計方案[J].通信技術,2010,43(08):137-139.

[6] European Telecommunications Standards Institute 2013. LTE; Evolved Universal Terrestrial Radio Access (E-UTRA); Multiplexing and channel coding(3GPP TS 36.212 version 10.6.0 Release 10)[S]. ETSI TS 136 212 v10.7.0(2013-02), Sophia Antipolis Cedex - FRANCE: ETSI 3rd Generation Partnership Project (3GPP), 2013:11-16.

[7] 郭璐,薛敏彪,黃鶯,等.Turbo碼中交織器的綜合性能分析與設計[J].信息安全與保密,2006(09):72-74.

[8] DIVSALAR D,POLLARA F.Turbo Codes for PCS Applications[C]//IEEE Int. Conf. on Commun. (ICC’95).Seattle: IEEE Conference Publications, 1995:54-59.

[9] GARELLO R, PIERLEONI P,BENEDETTO S. Computing the Free Distance of Turbo Codes and Serially Concatenated Codes with Interleavers: Algorithms and Application[J]. IEEE.J.Select. Areas Commun.,2001,19(05):800-812.