比特交織編碼調(diào)制(迭代譯碼)系統(tǒng)標(biāo)識映射的對稱性研究與應(yīng)用

張建勇 延鳳平

?

比特交織編碼調(diào)制(迭代譯碼)系統(tǒng)標(biāo)識映射的對稱性研究與應(yīng)用

張建勇*延鳳平

①(北京交通大學(xué)全光網(wǎng)絡(luò)與現(xiàn)代通信網(wǎng)教育部重點(diǎn)實(shí)驗(yàn)室 北京 100044)②(北京交通大學(xué)光波技術(shù)研究所 北京 100044)

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

無線通信；比特交織編碼調(diào)制；標(biāo)識映射；群理論；對稱性；二進(jìn)制交換算法

1 引言

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

2.1 BICM(-ID)系統(tǒng)的結(jié)構(gòu)

圖1 BICM(-ID)的系統(tǒng)結(jié)構(gòu)

2.2 m階漢明超立方與二進(jìn)制標(biāo)識的對稱性

根據(jù)文獻(xiàn)[7,8,12]可知，BICM(-ID)系統(tǒng)性能取決于式(1)表示的代價函數(shù)：

定義1 設(shè)系統(tǒng)的兩個標(biāo)識映射規(guī)則為1和2，若有一個雙向單射函數(shù):{0,1}?{0,1}，滿足，且使得對于所有的x,保持不變，則稱系統(tǒng)的標(biāo)識映射規(guī)則關(guān)于對稱。

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

圖2 8階星座圖及其映射

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

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

2.3 星座圖的對稱性

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

定義2設(shè)系統(tǒng)的兩個標(biāo)識映射規(guī)則為1和2，若有一個雙向單射函數(shù):{0,1}?{0,1}，滿足，且使得對于所有的x，多重集保持不變，則稱系統(tǒng)的標(biāo)識映射規(guī)則關(guān)于對稱。

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

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

3.1偽代碼實(shí)現(xiàn)

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

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

表1 IBSA算法的偽代碼

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

3.2 基于指示函數(shù)的代表映射

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

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

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

同時，定義排序函數(shù)Sort為

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

表2關(guān)于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 實(shí)驗(yàn)結(jié)果及分析

本文所有實(shí)驗(yàn)在4個臺式機(jī)上完成，臺式機(jī)配置為intel i5 CPU, 32 G 內(nèi)存，Debian 64位操作系統(tǒng)，數(shù)值計算主要采用Matlab 2011b軟件，采用SQLite數(shù)據(jù)庫實(shí)現(xiàn)大數(shù)據(jù)量的存儲與讀寫，4.2節(jié)的數(shù)值計算采用Matlab和C程序混合編程實(shí)現(xiàn)。

4.1 運(yùn)行速度測試與分析

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

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

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

4.2 效率分析

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

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

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

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

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

5 結(jié)束語

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

圖4 對稱映射的比例與BSA算法運(yùn)行次數(shù)的關(guān)系

圖5 對稱映射的比例與BSA算法運(yùn)行次數(shù)的關(guān)系

[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年生，副教授，研究方向?yàn)樾诺览碚摗⒎蔷€性光纖信道、光纖通信、信道編碼等.

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

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改回

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

張建勇 jyzhang@bjtu.edu.cn