RS碼編碼參數(shù)的盲識別*

張立民，劉 杰

(1.海軍航空工程學(xué)院 信息融合研究所，山東 煙臺 264001；2.解放軍91640部隊，廣東 湛江 524054;3.航天恒星科技有限公司，北京 100086)

?

RS碼編碼參數(shù)的盲識別*

張立民1，劉 杰**

(1.海軍航空工程學(xué)院 信息融合研究所，山東 煙臺 264001；2.解放軍91640部隊，廣東 湛江 524054;3.航天恒星科技有限公司，北京 100086)

針對現(xiàn)有的RS(Reed-Solomon)碼盲識別計算復(fù)雜度較大的問題，提出了一種新的識別方法。首先統(tǒng)計不同碼長分組時的碼重分布，并定義與理論碼重分布之間的相似度系數(shù)，通過計算找出最相似的一組即對應(yīng)正確的碼長；然后建立二元假設(shè)，并確定判決門限對碼根進行判定；通過遍歷域內(nèi)所有的本原多項式，找出完整的連續(xù)碼根分布，進而完成生成多項式的識別。仿真結(jié)果表明，所提方法的計算量較其他方法明顯減少，并能有效完成碼長和生成多項式的識別，在誤碼率小于10-3時，對常用RS碼的識別率能達到90%以上。

信道編碼；RS碼；盲識別；碼重分布；連續(xù)碼根

1 引 言

信道編碼是為了抵抗信息傳輸過程中的干擾和噪聲而人為加入的冗余。隨著現(xiàn)代數(shù)字通信系統(tǒng)的發(fā)展，信道編碼盲識別在自適應(yīng)調(diào)制編碼(Adaptive Modulation and Coding，AMC)技術(shù)和非協(xié)作條件下的通信偵察領(lǐng)域應(yīng)用廣泛，并迅速成為了一個新的研究熱點[1-3]。

RS碼是多進制BCH(Bose-Chaudhuri-Hocquenghem)碼的一個重要子類，它具有糾錯能力強、編碼結(jié)構(gòu)簡單等特點，被廣泛應(yīng)用于各種通信系統(tǒng)中[4]。因此，對RS 碼的盲識別進行研究具有重要意義。目前，見于文獻的相關(guān)方法主要有矩陣分析法、碼根統(tǒng)計法和基于伽羅華域傅里葉變換(Galois Field Fourier Transform，GFFT)的方法。文獻[5]利用矩陣秩差識別碼長，并引入熵函數(shù)差值識別本原多項式。文獻[6]利用矩陣秩函數(shù)識別 RS 碼的二進制衍生碼長，采用碼根統(tǒng)計完成生成多項式的識別。文獻[7]將GFFT用于域的本原多項式求解，在此基礎(chǔ)上，文獻[8]提出了在GFFT后進行頻譜累積量統(tǒng)計的檢測方法。文獻[9]使用非線性變換和中值濾波來充分利用頻譜的統(tǒng)計信息，文獻[10]引入了衡量譜分量概率分布差異性的歐幾里德距離測度。以上方法均需要對碼長和本原多項式進行驗證，當碼長較大時，運算量也隨之增大。

針對以上存在的不足，本文提出了一種新的RS碼盲識別方法：首先根據(jù)RS碼的碼字重量滿足固定分布這一特性，對碼長進行識別；然后建立二元假設(shè)對碼根和本原多項式進行判定，進而完成對生成多項式的識別。

2 問題描述

定義1[11]GF(q)上(q≠2)碼長n=q-1的本原 BCH碼稱為RS碼。

在RS碼作為差錯控制的所有實際應(yīng)用中，q都設(shè)置為2m，并且碼符號均取自伽羅華域GF(2m)。對符號取自GF(2m)、信息位長度為k且糾t個錯誤的RS碼，其滿足n-k=2t，碼最小距離d=2t+1。令α為GF(2m)中的本原元，則其生成多項式g(X)以α,α2,…,α2t為其全部根。由于αi是GF(2m)中的元素，因此其最小多項式即為X-αi。于是，

g(X)=(X-α)(X-α2)…(X-α2t)=g0+g1X+g2X2+…+g2t-1X2t-1+X2t。

(1)

其中:gi∈GF(2m)，0≤i<2t，且gi≠0。其奇偶校驗矩陣具有如下形式:

(2)

在實際應(yīng)用中，通過幀同步分析，可以很容易確定RS碼的碼字起點。在此條件下，需要識別的參數(shù)包括碼長，編碼域?qū)?yīng)的本原多項式及生成多項式。

3 RS碼盲識別實現(xiàn)

3.1 基于碼重統(tǒng)計的碼長識別

RS碼在實際數(shù)字通信系統(tǒng)中以二進制形式進行傳輸，接收的序列為GF(2m)碼元在GF(2)上映射得到的二進制準循環(huán)碼，其碼長為(2m-1)m，碼元之間的映射關(guān)系由選取的本原多項式?jīng)Q定。以GF(8)為例，表1給出了p1(X)=1+X+X3和p2(X)=1+X2+X3兩種情況下GF(8)到GF(2)映射情況?？梢钥闯?，GF(2)中“00…0”始終對應(yīng)GF(2m)中“0”，因此在統(tǒng)計碼重時，并不需要考慮實際采用的本原多項式和映射情況，只需以長度(2m-1)×m劃分碼字，每個碼字內(nèi)按m位比特進行遍歷，只要不出現(xiàn)連續(xù)全零狀態(tài)，則碼重加1。

表1 GF(8)到GF(2)映射關(guān)系Tab.1 Mapping relation from GF(8) to GF(2)

距離比奇偶校驗符號數(shù)多1的編碼稱為極大最小距離可分(Maximum Distance Separable,MDS)碼。MDS碼的碼重量分布有如下定理:

定理1[12]GF(q)上[n,k,d=n-k+1]MDS碼中重量為i的碼字個數(shù)為

(3)

RS碼構(gòu)成最重要的一類MDS碼，顯然其碼重量分布也滿足上述關(guān)系。因此，按可能的碼長逆映射得到RS碼序列并統(tǒng)計其碼重分布，然后根據(jù)統(tǒng)計結(jié)果估計合適的糾錯個數(shù)t，由式(3)得到理論碼重分布。兩者進行對比，符合度最高的則對應(yīng)正確碼長。

(4)

式中：Cov()表示協(xié)方差，D()表示方差。定義相似度系數(shù)

(5)

當γ最小時，即對應(yīng)正確碼長。

3.2 基于連續(xù)碼根判定的生成多項式識別

識別出碼長后，需要在不同本原多項式下逆映射得到可能的RS編碼序列，然后以每個碼字為一行，分別建立碼字矩陣。設(shè)建立的M行n列碼字矩陣為V，根據(jù)校驗關(guān)系，有

V·HT=0。

(6)

令vj=(vj,0,vj,1,…,vj,n-1)是矩陣V第j行，hi=(1,αi,α2i,…,α(n-1)i)是矩陣H第i行，由vj·(hi)T=0得

vj(αi)=vj,0+vj,1αi+vj,2α2i+…+vj,n-1α(n-1)i=0,

(7)

可知αi是碼多項式

vj(X)=vj,0+vj,1X+vj,2X2+…+vj,n-1Xn-1

(8)

的根。因此，定義二元假設(shè)

(9)

然后建立關(guān)于αi的統(tǒng)計量，并確定其在兩種假設(shè)下的概率分布，設(shè)定相應(yīng)判決門限。當統(tǒng)計量大于該門限時，αi為矩陣V中碼字的公共根，也即生成多項式g(X)的根。

根據(jù)文獻[13]，GF(2m)上首系數(shù)為1的m次本原多項式個數(shù)可以由公式c=φ(2m-1)/m求得，其中φ()為歐拉函數(shù)。找出所有碼字連續(xù)偶數(shù)個公共碼根最多時的情形，即對應(yīng)正確的本原多項式。

令Mz為矩陣V中滿足v(αi)=0的碼字個數(shù)。在本原多項式p(X)下，若αi不是生成多項式g(X)的根，則根據(jù)文獻[14]，v(αi)=0的概率為pi,1=1/2m，此時Mz服從伯努利分布B(M,pi,1)。令h=Mz/M，當M足夠大時，h趨于高斯分布，其概率密度函數(shù)為

(10)

(11)

根據(jù)最小錯誤概率準則，定義最優(yōu)判決門限

(12)則當計算出的h滿足h>ηopt時，可以判定αi是所有碼字多項式的公共根。經(jīng)計算可得到ηopt的解析值為

(13)

其中:

a=(1-pi,1)(1-pe)n·[2pi,1+(1-pi,1)(1-pe)n-1]/M,

(14)

b=-2pi,1(1-pi,1)(1-pe)n·[(1-pi,1)(1-pe)n+pi,1]/M,

(15)

(16)

對于本原多項式p(X)，設(shè)對應(yīng)本原元為α，若α不滿足判決門限，則說明該本原多項式不符合要求，需要選取新的本原多項式重復(fù)驗證步驟；反之，若α是生成多項式g(X)的根,則對αi(i=2,3,…)依次進行驗證。如果某個本原多項式從α開始存在的連續(xù)偶數(shù)個根最多，則該多項式對應(yīng)正確的編碼域。在確定生成多項式的連續(xù)碼根分布及本原多項式后，按式(1)即可得到g(X)。

完整識別過程的流程如圖1所示。

圖1 識別流程圖

4 仿真驗證

仿真分為三部分，首先對所提方法的可行性進行研究，分別對碼長和生成多項式的識別進行仿真驗證，然后分析了在不同碼長下的識別性能，并與其他文獻中的方法進行了對比。由于RS碼的性能隨碼長的增加而降低，實際一般使用中短碼，m取3～8；同時，實際通信系統(tǒng)中誤碼率一般為10-6～10-2。因此，進行仿真時采用的編碼參數(shù)、誤碼率均在此范圍內(nèi)選取。

4.1 碼長識別仿真

以(31,21)RS碼為研究對象，選取本原多項式為p(X)=1+X2+X5。首先隨機生成0、1隨機序列，然后以上述編碼參數(shù)進行編碼，按pe=0.001加入誤碼，最后得到長度為2.04×106的編碼序列。在m為3～8下，按(2m-1)m進行分組，取N=1 000，并選擇任意的本原多項式將二元碼字映射為GF(2m)中的碼字，然后對碼字的重量分布進行統(tǒng)計，結(jié)果如表2所示(由于篇幅所限，僅列出重量分布中不為0的最后幾位)。

表2 不同m值下碼重分布統(tǒng)計結(jié)果Tab.2 Statistic result of code weight under different m

利用式(5)對相似度系數(shù)進行計算，結(jié)果如圖2所示。

圖2 碼長識別結(jié)果

由圖2可以看出，當m為3、4、6、7和8時，由于編碼域錯誤，所得到的碼組并不是真實碼字，因此其重量分布與理論值相差較大，造成相似系數(shù)偏大。當m=5、對應(yīng)碼長n=31時相似度系數(shù)最小，因此該處即為正確碼長，與實際情況相符。

4.2 生成多項式識別仿真

下面對本原多項式和生成多項式進行識別，仿真條件與上面相同。m=5對應(yīng)6個本原多項式，分別為p1(X)=1+X2+X5、p2(X)=1+X3+X5、p3(X)=1+X+X2+X3+X5、p4(X)=1+X+X2+X4+X5、p5(X)=1+X+X3+X4+X5和p6(X)=1+X2+X3+X4+X5，在Matlab軟件中用十進制分別表示為37、41、47、55、59和61。取M=200，用本原元α對6種本原多項式進行判決，結(jié)果如表3所示?？梢钥闯?，僅在37處，所得到的h值大于判決門限，因此編碼域?qū)?yīng)的本原多項式為p1(X)=1+X2+X5，與實際相符。

表3 本原根α判定結(jié)果Tab.3 Judgment result of primitive element α

然后對除了α以外的其他根進行判定，結(jié)果如表4所示?？梢钥闯?，α2～α10均符合要求，而從α11開始，計算得到的h值小于判決門限，因此2t=10，k=n-2t=21，與實際相符。對應(yīng)生成多項式為

至此，整個識別過程結(jié)束。

表4 其他碼根判定結(jié)果Tab.4 Judgment result of other code roots

4.3 識別性能分析

圖3給出了m等于5～8四種情況下識別概率隨誤碼率變化的曲線，選取的具體RS碼分別為(31,21)碼、(63,51)碼、(127,113)碼和(255,223)碼?？梢钥闯?，碼長越大，識別概率越低。在誤碼率小于10-3時，對所有碼型的識別概率都能達到90%。

圖3 不同碼長RS碼識別結(jié)果

將本文方法與文獻[6]中矩陣分析結(jié)合碼根統(tǒng)計的方法、文獻[7]中基于GFFT的方法進行性能對比，對(31,21)RS碼進行識別，結(jié)果如圖4所示。由圖可見本文方法略優(yōu)于文獻[6]中的方法，但遜于文獻[7]中的方法。原因在于，文獻[6]進行矩陣分析時，初等變換的過程會造成錯誤傳播，且進行碼根統(tǒng)計時未定義判決門限，因此其抗誤碼性能比本文差。文獻[7]采用變換域方法，通過遍歷本原多項式和碼長完成識別，在犧牲計算復(fù)雜度的前提下獲得較好的性能。

圖4 識別性能對比

最后，對3種方法的計算復(fù)雜度進行分析。本文中，求單個碼字碼重的計算復(fù)雜度為mn，驗證元素是否為碼字多項式根需要n-1次GF(2m)域乘法和加法，轉(zhuǎn)換到二元域的計算復(fù)雜度為(n-1)·[3m(m-1)+m]；設(shè)文獻[6]中識別碼長時每個m值下驗證1 000次，則矩陣分析需進行500(mn-1)mn次行模2加運算，驗證碼根的計算復(fù)雜度與本文相同；文獻[7]中一次GFFT需n2次GF(2m)域乘法和n2-n次GF(2m)域加法，換算到二元域的計算復(fù)雜度為3m2n2-2mn2-mn[15]。取N=1 000，M=5n，上述3種方法的理論計算復(fù)雜度如圖5所示。可以看出，本文方法計算復(fù)雜度明顯小于其他兩種方法，結(jié)合圖4，說明本文方法適用于低誤碼率情況下的識別。

圖5 計算復(fù)雜度對比

5 結(jié) 論

根據(jù)RS碼的編碼結(jié)構(gòu)和特性，本文提出了一種新的RS碼盲識別方法，首先給出了基于碼重分析的碼長識別模型，然后通過搜尋連續(xù)碼根分布對本原多項式和生成多項式進行識別。與傳統(tǒng)方法相比，本文方法能在低誤碼率(小于10-3)下有效完成對常用RS碼的識別，且計算復(fù)雜度明顯得到降低，因此適用于對實時性要求較高的系統(tǒng)。在后續(xù)研究中，需要進一步提升方法在高誤碼率下的性能。

[1] XIA T,WU H C. Novel blind identification of LDPC codes using average LLR of syndrome a posteriori probability[J].IEEE Transactions on Signal Processing,2014,62(3):632-640.

[2] CHEN W,WU G Q. Blind recognition of(n-1)/n rate punctured convolutional encoders in a noisy environment[J].Journal of Communications,2015,10(4):260-267.

[3] YARDI A D,VIJAYAKUMARAN S,KUMAR A. Blind reconstruction of binary cyclic codes from unsynchronized bit stream[J].IEEE Transactions on Communications,2016,64(7):2693-2706.

[4] LIN S,COSTELLO D J. Error control coding[M].2nd ed. New Jersey,USA:Prentice Hall,2005:158-161.

[5] 李燦,張?zhí)扃?劉瑜. 基于伽羅華域高斯列消元法的 RS碼盲識別[J].電訊技術(shù),2014,54(7):926-931. LI Can,ZHANG Tianqi,LIU Yu. Blind recognition of RS codes based on Galois field columns Gaussian elimination[J].Telecommunication Engineering,2014,54(7):926-931.(in Chinese)

[6] 聞年成,楊曉靜. RS碼的盲參數(shù)識別[J].計算機工程與應(yīng)用,2011,47(19):136-139. WEN Niancheng,YANG Xiaojing. Blind recognition of RS codes parameters[J].Computer Engineering and Applications，2011,47(19):136-139.(in Chinese)

[7] 劉健,謝锘,周希元. RS碼的盲識別方法[J].電子科技大學(xué)學(xué)報,2009,38(3):363-367. LIU Jian,XIE Nuo，ZHOU Xiyuan. Blind recognition method of RS coding[J].Journal of University of Electronic Science and Technology of China,2009,38(3):363-367.(in Chinese)

[8] 王豐華,解輝,黃知濤，等. 基于頻譜累積量的線性分組碼檢測識別方法[J].系統(tǒng)工程與電子技術(shù),2013,35(12):2595-2599. WANG Fenghua,XIE Hui,HUANG Zhitao,et al.Blind recognition of linear block code based on spectral cumulants[J].Systems Engineering and Electronics,2013,35(12):2595-2599.(in Chinese)

[9] 解輝,王豐華,黃知濤，等. 基于頻譜預(yù)處理的RS碼盲檢測識別方法[J].宇航學(xué)報,2013,34(1):128-132. XIE Hui,WANG Fenghua,HUANG Zhitao,et al.Blind detection and recognition of RS code based on spectral preprocessing[J].Journal of Astronautic,2013,34(1):128-132.(in Chinese)

[10] 包昕,陸佩忠,游凌. 基于伽羅華域傅里葉變換的RS碼識別方法[J].電子科技大學(xué)學(xué)報,2016,45(1):30-35. BAO Xin,LU Peizhong,YOU Ling. Recognition of RS coding based on Galois field Fourier transform[J].Journal of University of Electronic Science and Technology of China,2016,45(1):30-35.(in Chinese)

[11] 王新梅,肖國鎮(zhèn). 糾錯碼——原理與方法[M].西安:西安電子科技大學(xué)出版社,2006:259-262.

[12] MACWILLIAMS F J,SLOANE N J A. The theory of error-correcting codes[M].New York:North-Holland Publishing Company,1977:320-321.

[13] 陳魯生,沈世鎰. 編碼理論基礎(chǔ)[M].北京:高等教育出版社,2005:37- 58.

[14] 王平,曾偉濤,陳健,等. 一種利用本原元的快速RS碼盲識別算法[J].西安電子科技大學(xué)學(xué)報(自然科學(xué)版),2013,40(1):105-110. WANG Ping,ZENG Weitao,CHEN Jian,et al.Fast blind recognition algorithm for RS codes by primitive element[J].Journal of Xidian University(Natural Science Edition),2013,40(1):105-110.(in Chinese)

[15] 解輝,黃知濤,王豐華. 信道編碼盲識別技術(shù)研究進展[J].電子學(xué)報,2013,41(6):1166-1173. XIE Hui,HUANG Zhitao,WANG Fenghua. Research progress of blind recognition of channel coding[J].Acta Electronica Sinca,2013,41(6):1166-1173.(in Chinese)

Blind Parameter Recognition of RS Codes

ZHANG Limin,LIU Jie1,SUN Yongwei2，ZHAO Zhimei3

(1.Research Institute of Information Fusion,Naval Aeronautical and Astronautical University,Yantai 264001,China;2.Unit 91640 of PLA,Zhanjiang 524054，China；3.Space Star Technology Co.,Ltd.,Beijing 100086,China)

As the existing methods for Reed-Solomon(RS) codes recognition are very complicated,a new method is proposed. Firstly,code weight distribution under different block length is counted. By defining similarity coefficient to the theoretical code weight,the most similar one is found,which corresponds to the correct code length. Then binary hypothesis test is established with a decision threshold to find code roots. By traversing all the primitive polynomials in the field,the complete distribution of continuous code roots is found,with which generator polynomial is calculated. Simulation results show that the computation cost of this method is significantly less than that of other methods,and it can effectively complete the recognition of code length and generator polynomial which has a recognition probability of 90% for the commonly used RS codes when the bit error rate is less than 10-3.

channel coding;RS codes;blind recognition;code weight distribution;continuous code roots

10.3969/j.issn.1001-893x.2017.06.006

張立民，劉杰，孫永威，等.RS碼編碼參數(shù)的盲識別[J].電訊技術(shù)，2017,57(6):650-655.[ZHANG Limin,LIU Jie,SUN Yongwei，et al.Blind parameter recognition of RS codes[J].Telecommunication Engineering,2017,57(6):650-655.]

2016-10-19；

2016-12-23 Received date:2016-10-19；Revised date：2016-12-23

國家自然科學(xué)基金重大研究計劃項目(91538201)；山東省“泰山學(xué)者”建設(shè)工程項目(ts201511020)

TN911.2

A

1001-893X(2017)06-0650-06

張立民(1966—)，男，遼寧開原人，2005年于天津大學(xué)獲博士學(xué)位，現(xiàn)為教授、博士生導(dǎo)師，主要研究方向為衛(wèi)星信號處理及應(yīng)用；

Email:iamzlm@163.com

劉 杰(1990—)，男，湖北宜昌人，博士研究生，主要研究方向為現(xiàn)代信號處理技術(shù)及應(yīng)用;

Email:iamliu1573@163.com

孫永威(1979—)，男，山東威海人，工程師，主要研究方向為電路與系統(tǒng);

趙志梅(1981—)，女，北京人，工程師，主要研究方向為航測遙感。

**通信作者：iamliu1573@163.com Corresponding author：iamliu1573@163.com1，孫永威2,趙志梅3