比特交織編碼調制(迭代譯碼)系統標識映射的對稱性研究與應用

張建勇 延鳳平

?

比特交織編碼調制(迭代譯碼)系統標識映射的對稱性研究與應用

張建勇*延鳳平

①(北京交通大學全光網絡與現代通信網教育部重點實驗室 北京 100044)②(北京交通大學光波技術研究所 北京 100044)

該文從群論的角度分析了比特交織編碼調制(迭代譯碼)(BICM(-ID))系統中標識映射的對稱性。首先給出了標識映射對稱性的定義，并指出，二進制標識映射的對稱性是BICM(-ID)系統的固有特性，該對稱性同構于階超立方的對稱群。然后基于BICM(-ID)的對稱性，提出一種改進的二進制交換算法(IBSA)。該算法的搜索空間為標識映射對稱群陪集的代表系。因此，與傳統的二進制算法相比，IBSA的搜索效率得到了提高。最后，2維16階星座圖的仿真結果表明，在40000次的運行過程中，IBSA能提高4%的搜索效率；32階相移鍵控星座圖的仿真結果表明，該算法至少可提高3.5%的搜索效率，單個映射的計算時間縮短了約4000倍。

無線通信；比特交織編碼調制；標識映射；群理論；對稱性；二進制交換算法

1 引言

2 BICM(-ID)系統的對稱性

2.1 BICM(-ID)系統的結構

圖1 BICM(-ID)的系統結構

2.2 m階漢明超立方與二進制標識的對稱性

根據文獻[7,8,12]可知，BICM(-ID)系統性能取決于式(1)表示的代價函數：

定義1 設系統的兩個標識映射規則為1和2，若有一個雙向單射函數:{0,1}?{0,1}，滿足，且使得對于所有的x,保持不變，則稱系統的標識映射規則關于對稱。

在數學中，群的概念常常用來描述對稱性。從二進制標識映射的定義可知，所有標識映射的集合構成了一個置換群Sym(2)，其階為2!。因而，符合定義1的所有雙向單射函數的集合構成了Sym(2)的一個子群，而該子群的陪集的指數則是BICM(-ID)系統非重復映射的個數。

圖2 8階星座圖及其映射

基于以上分析，本文將該例推廣到2階星座圖。2階星座圖的二進制標識可以看作是維漢明超立方體的頂點。維超立方體具有旋轉及鏡像對稱性，即對于所有頂點，任意交換多個比特的位置或對其中的多個比特取非，仍會得到維漢明超立方，但頂點的排列順序發生了改變，即得到了不同的映射。維超立方的所有對稱性也構成一個群，該群一般表示為BC=Sym(2)Sym()，其中為群的圈積，該群的階數為2m!。因此，關于標識映射的對稱性，有如下結論成立：

定理1 對于任意星座圖，任意一個標識映射是關于BC中所有的元素對稱的。

2.3 星座圖的對稱性

圖3 相互對稱的兩個8-PSK映射

定義2設系統的兩個標識映射規則為1和2，若有一個雙向單射函數:{0,1}?{0,1}，滿足，且使得對于所有的x，多重集保持不變，則稱系統的標識映射規則關于對稱。

根據定義2，很容易驗證3及4是滿足定義2的，同時也可以驗證1及2也同樣滿足定義2。從本文給出的對稱性的定義可以看出，符合定義1的映射必然關于定義2對稱，反之則不一定成立。

3 一種改進的二進制交換算法(IBSA)

3.1偽代碼實現

傳統的BSA算法在尋找最優映射的過程中，常常隨機選取一個初始映射，通過標識交換來不斷地降低代價函數值。一般而言，單次BSA算法只能得到局部最優解，通常需多次隨機運行BSA算法才能得到近似全局最優解[12]。由于相互對稱的映射具有相同的性能，傳統的BSA算法在運行過程中將會計算大量的對稱映射，從而影響BSA算法的隨機搜索效率，且該搜索效率常常隨運行次數的增加而下降。因此，本文給出了一種改進的二進制交換算法(IBSA)，即通過避免搜索相互對稱的映射，以提高BSA算法的運行效率，其單次搜索的步驟如表1所示。

假定具有對稱關系的映射群為()，其階數為。該群可由二進制標識對稱性構成，也可以包含全部或部分的星座圖對稱性。根據群論可知，通過()能將對稱群Sym(2)分解為多個互不相交的右陪集，Sym(2)=()1()2()ü，其指數=(2!)/，其中，{ü:=1,,(2!)/}為Sym(2)的右陪集代表系。在表1中，u為隨機生成的唯一代表映射；利用傳統BSA算法經過一次標識交換得到的映射為，即表示為；函數：Sym(2)?Sym(2)將映射轉換為其對應的唯一代表映射，即；已經搜索過的唯一代表映射集合為。

表1 IBSA算法的偽代碼

從表1中可以看出，該算法將原BSA算法每次交換得到的映射轉化為唯一代表映射，由于代表系{ü}是互不對稱的，這種做法的實質是將BSA的搜索空間從原來的對稱群Sym(2)縮小為某個代表系{ü}。因此，IBSA算法能保證相互對稱的映射只被搜索一次。由于代表系的大小通常遠小于對稱群Sym(2)，與傳統的BSA算法相比，該算法通常能大大提高搜索效率。

3.2 基于指示函數的代表映射

根據表1可知，改進算法的關鍵問題是尋找代表系{ü}。相比群的表示問題，代表系{ü}是很容易求出的，其表示方式也是多種多樣的。因此，需要找到一個函數，使得ü=對于所有?()ü都成立。由于代表系{ü}及的引入，增大了算法的復雜度及搜索壓力。為了簡化搜索及代表系的計算過程，本文提出了一種基于指示函數的代表系。

其中min:*?*是求取極小值的函數，*是非負整數集。從式(2)可以看出，由于指示函數采用整數表示，且所有的運算都是整數運算，對于高階系統來說，該函數可極大地簡化{ü}的計算復雜度。

其中u是經過次序交換后的函數；?[0,2!-1];是對稱群()中的一個元素，代表一種交換次序；交換前和交換后的映射滿足。

同時，定義排序函數Sort為

本文將以8-PSK為例詳細說明唯一代表映射的提取過程。BC3和8的一部分如表2所示。取映射5= (0,4,1,6,2,3,7,5)，則關于5對稱的部分映射如表2所示，通過計算可以得到，其基于指數函數的代表映射為(0,1,2,5,4,6,7,3)。

表2關于5對稱的部分映射

hBC?BC3hz?Z8Sort((Sort(ul), hBC))(Sort((Sort(ul), hBC)), hz) 0,4,2,6,1,5,3,70,1,2,3,4,5,6,70,1,4,3,2,6,7,50,1,4,3,2,6,7,5 1,5,3,7,0,4,2,67,0,1,2,3,4,5,64,5,0,7,6,2,3,11,4,5,0,7,6,2,3 2,6,0,4,3,7,1,56,7,0,1,2,3,4,52,3,6,1,0,4,5,75,7,2,3,6,1,0,4 3,7,1,5,2,6,0,45,6,7,0,1,2,3,46,7,2,5,4,0,1,3,0,1,3,6,7,2,5,4

4 實驗結果及分析

本文所有實驗在4個臺式機上完成，臺式機配置為intel i5 CPU, 32 G 內存，Debian 64位操作系統，數值計算主要采用Matlab 2011b軟件，采用SQLite數據庫實現大數據量的存儲與讀寫，4.2節的數值計算采用Matlab和C程序混合編程實現。

4.1 運行速度測試與分析

如第3節所述，IBSA算法增加了算法的復雜度，且需要搜索集合，代表映射的求解時間是影響到算法實現的重要因素。為此，本文以BICM-ID系統為研究對象，選取=3,4,5,6等2-PSK星座圖，同時考慮了二進制標識的對稱性和星座圖的旋轉對稱性，給出利用Matlab程序計算唯一代表映射所需要的時間，如表3所示。

表3給出了BSA一次交換的計算時間，可以看出，對于較高階數的星座圖(=5,6)，唯一代表映射的計算時間比BSA一次交換的計算時間要長，一般是4~10倍左右；對于=3,4，計算時間基本上與一次交換時間相當。但由于IBSA算法采用唯一代表映射表示相互對稱的映射，相當于擴大了BSA算法的搜索空間，一次交換可搜索的映射個數為=2′!′，且隨的增大呈指數增加趨勢。由于傳統的BSA算法一次交換只能搜索一個映射，因此，IBSA算法單個映射的搜索時間是急劇減少的，如表3所示。與傳統的BSA算法相比，當=6時，單次映射的計算時間0最多可縮短約2.6萬倍，因此，從計算時間與已搜索過的映射個數綜合考慮，IBSA算法能大幅提高計算效率。

從表1可知，IBSA算法還需要判斷唯一代表映射是否被搜索。本文選用32-PSK，通過運行IBSA算法，最終得到了大約1′108個映射，平均搜索一次數據為所需大約為60 s左右。但由于該數據庫存儲在硬盤上，其速度受限于SQLite的存儲格式及硬盤運轉速度，并非理論上的極限。若不考慮存儲問題，可表示為數據結構中的樹模型，該樹每個節點最多有32個分支，該樹的深度為32，理論上只需最多32次比較及查找運算，即可以完成搜索。因此，該算法從理論上來說，搜索壓力并不是制約算法運行速度的主要因素。

4.2 效率分析

從表1可以看出，若在傳統BSA算法搜索過程中，相互對稱的映射比例越高，則說明IBSA算法越有效，越能提高搜索效率。本文給出了兩個例子來說明對稱性對傳統BSA算法的影響。由于傳統的BSA算法常常多次隨機運行，因此每次BSA算法所計算的映射也是隨機的。為加快BSA算法的運行速度，以下兩個例子僅選取BICM-ID系統作為研究對象。為方便統計，本文統計了次(>>1)傳統BSA算法中對稱映射的比例，即假設已搜索的映射集為，其代表系為B，第次BSA算法計算的所有映射為B，其中，第次BSA算法中與B對稱的映射為B，則對稱映射所占的比例為|B|/|B|。

首先，本文僅考察二進制標識的對稱性對BSA算法的影響。在該例中，選用文獻[17]給出的2維16階星座圖，整個標識映射的搜索空間為16!?2.09′1013個映射，而二進制標識總共有244!=384種對稱性，因此，對稱性僅能使搜索空間減小300多倍，與巨大的搜索空間相比似乎看起微不足道。在傳統的BSA算法中，隨機選取初始映射，共運行BSA算法40,000次，搜索了430,042個映射，平均運行一次BSA算法約搜索10.75次映射。同時，根據二進制標識映射的對稱關系，取=1000，得到對稱映射的比例如圖4所示。從圖中可以看出，具有對稱關系的映射隨BSA算法的運行次數直線上升，最高比例約達4%。

表3唯一代表映射的計算時間(s)

m=3m=4m=5m=6 唯一代表映射的計算時間tr0.00160.00260.05300.8600 BSA算法一次交換的計算時間ts0.00340.00440.01400.0900 IBSA算法單個映射的計算時間t0=(tr+ts)/(2m′m!′m)

但此時已搜索的映射個數才接近整個映射空間的兩億分之一。利用圖4數據進行外插擬合可知，當對稱映射的比例為90%時，此時的BSA的計算次數為1.26′106次，根據4.2節的計算結果，共有1.35′107個映射得到了計算，與巨大的搜索空間相比，只占據了搜索空間的極小部分。因此，從該仿真結果可以看出，由于具有對稱關系的映射一直在線性增加，BSA算法將浪費越來越多的運行次數在已知的映射上，其效率持續降低。對于較低階星座圖(階數小于等于16)，僅利用二進制標識的對稱性已可大大提高IBSA算法的搜索效率。

其次，本文選取32階相移鍵控信號(32-PSK)來考察二進制標識對稱性及星座圖對稱性對BSA算法的影響。在傳統的BSA算法中，隨機選取初始映射，共運行BSA算法3.32′106次，約搜索了1.2′108個映射，平均運行一次BSA算法約搜索33.1次映射。相比整個搜索空間而言，BSA算法的搜索空間更是微不足道的。取=5000，得到對稱映射的比例如圖5所示。標有方塊的曲線是只考慮二進制標識對稱的情況，從圖中可以看出，雖然對稱映射的比例隨BSA算法的運行次數直線上升，但上升緩慢，且其最高的比例約達1.5%。標有圓圈的曲線是同時考慮二進制標識對稱和星座圖旋轉對稱的情況，從圖中可以看出，對稱映射的比例隨BSA算法的運行次數直線上升，且其最高的比例約達6.3%。當BSA運行次數小于3.1′105時，對稱映射的比例快速上升，這也反映出盡管搜索次數較少，但由于代表系遠遠小于整個搜索空間，對稱性也能大大提高搜索效率。當運行次數較小時，由于樣本空間較少，此時并不能完全體現出旋轉對稱性對系統性能的影響。隨著BSA算法搜索次數的增加，對稱映射比例的斜率逐漸趨于一個穩定值，旋轉對稱性對系統統性能的提高也逐漸趨于穩定。

最后，從兩個不同階數的仿真結果可以看出，對于較高階星座圖(階數大于16)，不僅需利用二進制標識的對稱性，同時也要盡可能的利用星座圖的對稱性來提高IBSA算法的搜索效率。并且，若系統只存在二進制標識的對稱性，在有限的搜索空間下，該對稱性同樣可以提高IBSA算法的搜索效率。

5 結束語

本文研究了BICM或BICM-ID系統的對稱性，給出了對稱性的定義，并詳細研究了BICM(-ID)中的二進制標識映射，同時提出了一種IBSA算法，通過仿真表明，該算法能避免重復計算相互對稱的映射，可提高傳統BSA算法的效率。但BICM(-ID)的對稱性問題實質上是陪集代表系的表示問題，若能求解出該代表系，則排除了對稱性的因素，能更好的研究BICM(-ID)系統特性與代表系之間的函數關系；同時也能避免存儲和搜索已計算過的代表系，進一步提升改進BSA算法的運行速度。對于低階置換群，該問題可通過現有軟件解出，如GAP等[19]軟件，但對于高階復雜對稱性問題，求解該類問題是比較困難的，該類問題也是本研究的下一步工作。

圖4 對稱映射的比例與BSA算法運行次數的關系

圖5 對稱映射的比例與BSA算法運行次數的關系

[1] 3GPP TS 125.212, V7.11.0 Release 7. Universal mobile telecommunications system (UMTS); multiplexing and channel coding (FDD)[S]. Sept. 2009.

[2] IEEE 802.11n-2009. Part 11: wireless LAN medium access control (MAC) and physical layer (PHY) specifications. Amendment 5: Enhancements for higher throughout[S]. Oct. 2009.

[3] Douillard C and NourC A. The bit interleaved coded modulation module for DVB-NGH: enhanced features for mobile reception[C]. 2012 19th International Conference on Telecommunications (ICT), Jounieh, Lebano, April2012: 1-6.

[4] Agrell E and Alvarado A. Optimal alphabets and binary labelings for BICM at low SNR[J]., 2011, 57(10): 6650-6672.

[5] Agrell E and Alvarado A. First-order asymptotics of the BICM mutual information: uniform vs. nonuniform distributions[C].Proceedings of Information Theory and Applications Workshop (ITA) 2012, San Diego, USA, 2012: 306-310.

[6] Schenk A and FischerR F H. Capacity of BICM using (Bi-)orthogonal signal constellations in the wideband regime[C]. 2011 IEEE International Conference on Ultra-Wideband (ICUWB), Bologna, Italy, Sept. 2011: 595-599.

[7] Caire G, Taricco G, and Biglieri E. Bit-interleaved coded modulation[J]., 1998, 44(3): 927-946.

[8] Schreckenbach F, Gortz N, Hagenauer J,..Optimization of symbol mappings for bit-interleaved coded modulation with iterative decoding[J]., 2003, 7(12): 593-595.

[9] Jun Tan and Stuber G L. Analysis and design of symbol mappers for iteratively decoded BICM[J].,2005, 4(2): 662-672.

[10] Li Xiao-dong, Chindapol A, and Ritcey J A. Bit-interleaved coded modulation with iterative decoding and 8 PSK signaling[J]., 2002, 50(8): 1250-1257.

[11] Yu Tsang-wei, Wang Chu-yan, Wang Chung-hsuan,..EXIT-chartbased labeling design for bit-interleaved coded modulation with iterativedecoding[C].Proceedings of IEEE International Symposium on Information Theory (ISIT 2007), Nice, France,Jun.2007: 56-60.

[12] Schreckenbach F. Iterative decoding of bit-interleaved coded modulation[D].[Ph.D. dissertation], Munich University of Technology, Germany,2007.

[13] Brannstrom F and Rasmussen L K. Classification of unique mappings for 8PSK based on bit-wise distance spectra[J].

, 2009, 55(3):

1131-1145.

[14] Agrell E and Alvarado A. Achieving the Shannon limit with probabilistically shaped BICM[C].Proceedings of IEEE International Symposium on Information Theory Proceedings(ISIT 2012),Cambridge, Massachusetts, USA, July 2012: 2421-2425.

[15] Chindapol A and Ritcey J A. Design, analysis, and performance evaluation for BICM-ID with square QAM constellations in Rayleigh fading channels[J]., 2001, 19(5): 944-957.

[16] Tran N H and Nguyen H H. Design and performance of BICM-ID systems with hypercube constellations[J]., 2006, 5(5): 1169-1179.

[17] Beko M and Dinis R. Designing good multi-dimensional constellations[J]., 2012, 1(3): 221-224.

[18] Forney G D, Jr.. Multidimensional constellations. II. Voronoi constellations[J]., 1989, 7(6): 941-958.

張建勇： 男，1977年生，副教授，研究方向為信道理論、非線性光纖信道、光纖通信、信道編碼等.

延鳳平： 男，1966年生，教授，博士生導師，主要從事光通信、 全光網絡、新型特種光纖及光纖器件、光纖傳感及無線通信的研究.

The Symmetries of Mappings of Bit-interleaved Coded Modulation (with Iterative Decoding) Systems and Its Applications

Zhang Jian-yong Yan Feng-ping

①(&’,,100044,)②(,,100044,)

Based on the group theory, the symmetries of mappings of Bit-Interleaved Coded Modulation (or with Iterative Decoding) systems (BICM(-ID)) are studied. Firstly, the definitions of the symmetries of mappings for BICM (-ID) are given. The symmetries of binary labels of a mapping are the intrinsic properties of BICM(-ID), which are isomorphic to the symmetry group of a hypercube of order. According to the symmetries of BICM (-ID), an Improved Binary Switch Algorithm (IBSA) is proposed. The search space of IBSA is a transversal of the symmetry group of mappings. Consequently, the efficiency of IBSA is improved compared to the traditional BSA. Finally, Simulation results of a 16-ary two dimensional constellation show that the search efficiency of IBSA can be improved about 4% during 40000 trials. For 32-PSK, the results show that the search efficiency can be improved at least 3.5% and the time required to calculate a single mapping is shorten about 4000 times.

Wireless communication; Bit-Interleaved Coded Modulation (BICM); Mapping; Group theory; Symmetries; Binary Switch Algorithm (BSA)

TN92

A

1009-5896(2014)01-0048-07

10.3724/SP.J.1146.2013.00382

2013-03-26收到，2013-06-13改回

國家自然科學基金(61102048)，國家自然科學基金重點項目(60837002)，國家973計劃項目(2010CB328206)，中央高校基本科研業務費專項資金(2011JBM208)和北京交通大學人才基金(2006RC022)資助課題

張建勇 jyzhang@bjtu.edu.cn