基于信息位與校驗(yàn)位分離的RS碼盲識別

龍 浪，楊俊安，劉 輝，梁宗偉

(1.國防科技大學(xué)電子對抗學(xué)院，安徽 合肥 230037；2.安徽省電子制約技術(shù)重點(diǎn)實(shí)驗(yàn)室，安徽 合肥 230037)

0 引言

RS(Reed Solomon，RS)碼是一類糾錯(cuò)性能優(yōu)異的多進(jìn)制BCH(Bose Chaudhuri Hocquenghem)碼，它具有編碼結(jié)構(gòu)簡單，糾正隨機(jī)錯(cuò)誤和突發(fā)錯(cuò)誤能力強(qiáng)的特點(diǎn)，被廣泛應(yīng)用于無線通信、深空通信、軍事通信等各個(gè)領(lǐng)域中[1]。因此，研究RS碼的盲識別方法有重要意義。

現(xiàn)有的文獻(xiàn)表明，國內(nèi)外已有大量學(xué)者對RS碼盲識別算法展開研究。文獻(xiàn)[2]利用衡量譜分量概率分布差異性的歐幾里德距離測度來完成對RS碼本原多項(xiàng)式和生成多項(xiàng)式的識別，但對RS碼其他編碼參數(shù)識別未做詳細(xì)研究。文獻(xiàn)[3]通過求取矩陣的差值函數(shù)來識別碼長及符號數(shù)，并利用熵函數(shù)差值來完成對本原多項(xiàng)式的識別，但該方法計(jì)算量較大，抗誤碼性能較差，且只適用于本原RS碼，不能識別出縮短RS碼。文獻(xiàn)[4]通過碼重分布識別碼長，并利用二元假設(shè)識別本原多項(xiàng)式和生成多項(xiàng)式，減少了計(jì)算量，但同樣不適用于縮短RS碼。文獻(xiàn)[5]通過伽羅華域(Galois Field，GF)的高斯約當(dāng)消元法識別碼長，并利用伽羅華域傅里葉變換(Galois Field Fourier Transform，GFFT)識別本原多項(xiàng)式和生成多項(xiàng)式，該方法雖然可完成對RS碼和縮短RS碼的識別，但計(jì)算量較大，抗誤碼性能不佳。綜上，已有的算法沒有較好的權(quán)衡算法的計(jì)算量和抗誤碼性能，且識別的參數(shù)不夠全面，均未對RS碼的信息位長度這一參數(shù)進(jìn)行識別，并且針對RS縮短碼的識別研究相對較少。針對以上存在的不足，本文提出一種基于信息位與校驗(yàn)位分離的盲識別算法。

1 RS碼識別基礎(chǔ)

1.1 RS碼的定義

定義1[6]：GF(q)(q≠2，通常q=2m)上，碼長n=q-1的本原BCH碼稱為本原RS碼。

在實(shí)際應(yīng)用中q一般取2m，所以主要對GF(2m)上的RS碼進(jìn)行識別研究。

1.2 RS碼的性質(zhì)

RS碼是線性分組碼的一種重要子類，所以RS碼具有線性分組碼的性質(zhì)。

性質(zhì)1[8]：設(shè)V是由GF(2m)上的k×n階生成矩陣G所生成的RS碼，則V的向量表示(mn，mk)是GF(2)上的線性分組碼。

若將GF(2m)上的(n，k)RS碼映射為GF(2)上的線性分組碼，其中n為RS碼碼長，k為RS碼信息位長度，m為符號數(shù)，則GF(2)上的等價(jià)線性分組碼碼長mn=m(2m-1)，等價(jià)信息位長為mk，其中m≥2。

性質(zhì)2[5]:RS碼的碼字信息位與校驗(yàn)位線性相關(guān)。

性質(zhì)3[9]：多項(xiàng)式a(x)以αj為根的充要條件是其譜多項(xiàng)式A(z)的系數(shù)滿足：Aj=a(αj)=0

性質(zhì)4[9]:對任一距離為δ的RS碼字進(jìn)行伽羅華域上的離散傅里葉變換，則A(z)中至少有δ-1個(gè)連零。

對于縮短RS碼[10]，它是原(n,k)本原RS碼刪除前i位信息位為0的碼字后所構(gòu)造的新碼，由于仍可構(gòu)成一個(gè)(k-i)維的線性子空間，所以能得到一個(gè)(n-i,k-i)(1≤i≤k)的縮短RS碼，其碼長n≠2m-1，其他參數(shù)均與原RS碼相同，因此，對縮短RS碼的識別方法與原RS碼一致。

2 RS碼盲識別實(shí)現(xiàn)

在實(shí)際數(shù)據(jù)傳輸中，(n，k)RS碼通常是以二進(jìn)制碼流(mn，mk)傳輸?shù)腫11]，當(dāng)截獲到RS碼序列后，根據(jù)RS碼的線性特性，對接收序列構(gòu)建等效二進(jìn)制碼的分析矩陣，通過信息位與校驗(yàn)位分離法，識別出等價(jià)碼長mn，等價(jià)信息位長mk，從而獲得碼率k/n，再通過伽羅華域的離散傅里葉變換求出RS碼的符號數(shù)m，本原多項(xiàng)式p(x)及生成多項(xiàng)式g(x)，最后通過計(jì)算可獲得碼長n，信息位長k。

2.1 基于信息位與校驗(yàn)位分離的盲識別算法

本文通過信息位與校驗(yàn)位分離法來完成對RS碼等價(jià)碼長mn及等價(jià)信息位長度mk的識別，即通過等價(jià)二進(jìn)制碼流中0，1概率方差的不同來區(qū)分信息位及校驗(yàn)位，從而確定mn及mk。例如，在實(shí)際應(yīng)用中，(7,3)RS碼通常是以等價(jià)(21,9)二進(jìn)制碼來進(jìn)行傳輸?shù)?，其中m=3。令等價(jià)二進(jìn)制碼中信息位1的概率為a(0

(1)

如校驗(yàn)位c10是信息位m1和m2異或相加所得，則校驗(yàn)位c10為1的概率如式(2):

P(c10=1)=P(m1⊕m2=1)=P(m1=1)×
P(m2=0)+P(m1=0)×P(m2=1)=
a×b+b×a=2ab

(2)

同理，校驗(yàn)位c10為0的概率如式(3)：

P(c10=0)=P(m1⊕m2=0)=P(m1=1)×
P(m2=1)+P(m1=0)×P(m2=0)=
a×a+b×b=a2+b2

(3)

為了更好地說明信息與校驗(yàn)位分離法，計(jì)算校驗(yàn)位c10所在列(校驗(yàn)列)的1和0概率的概率方差d1與信息位所在列(信息列)的概率方差d2，其中均值μ=(a+b)/2=0.5，定義兩者的差值為d3，通過比較可得，信息列概率方差大于奇偶校驗(yàn)列概率方差，由此可以區(qū)分信息位和奇偶校驗(yàn)位。

d1=(a-0.5)2+(b-0.5)2

(4)

d2=[(a2+b2)-0.5]2+(2ab-0.5)2

(5)

d3=d1-d2=(a-0.5)2+(b-0.5)2-
[(a2+b2)-0.5]2-(2ab-0.5)=2(a+b)2-
2ab-a-b-[(a+b)4-4a3b-4ab3]=2-2ab-
1-(1-4a3b-4ab3)=2ab(2a2+2b2-1)=
2ab[2a2+2b2-(a+b)2]=2ab(a-b)2

(6)

故定義分析矩陣的每列0、1的概率方差d(i)如式(7)，其中col為分析矩陣的列數(shù)。

d(i)=variance(P(0),P(1));1≤i≤col

(7)

與校驗(yàn)位所在列的概率方差相比，消息列的概率方差將會較大，計(jì)算所有col列概率方差的方差d如式(8)：

d=variance(d(1),d(2),…,d(col))

(8)

當(dāng)分析矩陣中碼字對齊時(shí)，即信息位與校驗(yàn)位恰好分離，此時(shí)，各列之間的概率方差的差異最大，總的概率方差達(dá)到一個(gè)最大值。當(dāng)分析矩陣中碼字未對齊時(shí)，列中的元素既有信息位也有校驗(yàn)位，則此時(shí)各列之間概率方差的差異不明顯，總的概率方差相對較小。

因此，通過觀察分析矩陣取不同列數(shù)值下的總概率方差d，當(dāng)d為最大值時(shí)，此時(shí)的分析矩陣中碼字對齊，且碼長估計(jì)準(zhǔn)確，由此可以得到正確的等價(jià)碼長mn及等價(jià)信息位長mk。

2.1.1等價(jià)碼長識別

假設(shè)碼長為5的截獲RS碼序列以不同的估計(jì)碼長按行放入分析矩陣中，其中令A(yù)，B，C為信息位，D，E為校驗(yàn)位，形成的矩陣模型如圖1所示。

圖1 三種排列情況Fig.1 Three cases of arrangement of bitstream

現(xiàn)在，可能有三種排列的情況：

圖1(a)表示當(dāng)碼字對齊，且每行對應(yīng)于實(shí)際的等價(jià)碼長大小為5時(shí)，A，B，C，D，E各自單獨(dú)成列，信息位與校驗(yàn)位分離，所以最終的方差d會出現(xiàn)最高峰。

圖1(b)顯示當(dāng)每行大小為4，即不等于實(shí)際的等價(jià)碼長大小時(shí)，A，B，C，D，E不能單獨(dú)成列，每列既包含信息位A，B，C，又有校驗(yàn)位D，E，信息位不能與奇偶校驗(yàn)位分開，所以最終的方差d不會出現(xiàn)最高峰。

圖1(c)示出了當(dāng)碼字未時(shí)對齊，A，B，C，D，E不能單獨(dú)成列，每列既包含信息位A，B，C，又有校驗(yàn)位D，E，信息位不能與奇偶校驗(yàn)位分開，所以最終的方差d不會出現(xiàn)最高峰。

在構(gòu)建分析矩陣后，計(jì)算每列的0、1概率方差及所有列概率方差的方差d，當(dāng)且僅當(dāng)碼字對齊，且每行對應(yīng)于實(shí)際的等價(jià)碼長大小時(shí)，方差d最大，完成對等價(jià)碼長mn的識別。

2.1.2等價(jià)信息位長識別

與校驗(yàn)列的概率方差相比，消息列的概率方差將會很大，因此可以區(qū)分信息位和奇偶校驗(yàn)位。

當(dāng)碼字對齊且等價(jià)碼長估計(jì)正確時(shí)，按正確的碼長構(gòu)建分析矩陣，計(jì)算每列的0、1概率方差d(i)。與校驗(yàn)列相比，等價(jià)信息位所在列的概率方差大于校驗(yàn)列的概率方差，由此可區(qū)分出校驗(yàn)列與信息列。為了更好的進(jìn)行區(qū)分，取分析矩陣所有列概率方差的均值為門限值Vth。

(9)

當(dāng)概率方差d(i)超過Vth時(shí)，判斷該列為信息列，反之，則為校驗(yàn)列，由此，可識別出等價(jià)信息位的長度mk，通過計(jì)算可以得到RS碼碼率k/n。

2.2 符號數(shù)及本原多項(xiàng)式識別

當(dāng)?shù)葍r(jià)碼長估計(jì)正確且對齊后，選擇不同的估計(jì)符號數(shù)m0，由于RS碼的性能隨碼長的增加而降低，實(shí)際一般使用中短碼，符號數(shù)m0取3～8，并遍歷m0次本原多項(xiàng)式pr0，對截獲序列按估計(jì)出的正確等價(jià)碼長mn進(jìn)行分組，并對其作GF(2m0)上的離散傅里葉變換。當(dāng)多組碼字經(jīng)GF(2m)上的傅里葉變換后具有相同的連零位置且個(gè)數(shù)相同時(shí)，則正確識別出符號數(shù)m及本原多項(xiàng)式pr，最后通過計(jì)算可以得到RS碼的碼長n，信息位長度k。其中符號數(shù)m及其本原多項(xiàng)式如表1所示。

表1 m值及其對應(yīng)的本原多項(xiàng)式十進(jìn)制表示

2.3 生成多項(xiàng)式識別

設(shè)α表示GF(2m)的本原元，那么{1,α,α2,…,α2m-2}是GF(2m)上的2m-1個(gè)不同的非零元素。最小碼距為d=2t+1(t=(n-k)/2)的RS碼生成多項(xiàng)式g(x)如式(10)[12]。

(10)

在碼長及本原多項(xiàng)式正確識別后，找到連零碼譜出現(xiàn)的位置對應(yīng)的碼根，根據(jù)式(7)計(jì)算出生成多項(xiàng)式g(x)。

2.4 算法流程：

步驟4 按正確的等價(jià)碼長n′構(gòu)建分析矩陣，計(jì)算每列的0，1概率方差d(i)，并與門限值Vth相比較，得到等價(jià)信息位長度k′，得到碼率為k′/n′。

步驟5 估計(jì)符號數(shù)m0，并遍歷m0次本原多項(xiàng)式pr0，對碼序列作GF上的傅里葉變換。當(dāng)有N組碼字作GF上的傅里葉變換，其中h組碼組碼字變換后具有相同的連零位置且個(gè)數(shù)相同時(shí)，則正確識別出符號數(shù)m及本原多項(xiàng)式pr，則n=n′/m，k=n·k′/n′。

步驟6 找到連零碼譜出現(xiàn)位置所對應(yīng)的碼根，根據(jù)式(10)計(jì)算出生成多項(xiàng)式。

3 仿真實(shí)驗(yàn)與性能分析

3.1 實(shí)驗(yàn)驗(yàn)證

為了驗(yàn)證本文所提方法的有效性，分別針對本原RS碼以及縮短RS碼設(shè)計(jì)仿真分析實(shí)驗(yàn)，編碼參數(shù)設(shè)置如表2所示。利用Matlab隨機(jī)生成0，1隨機(jī)序列，然后以表2中編碼參數(shù)進(jìn)行編碼，并疊加高斯隨機(jī)噪聲，產(chǎn)生誤碼率為pe的碼序列，并用本文所提出的算法對其進(jìn)行識別。

表2 參數(shù)設(shè)置

圖2、圖3分別給出了在對本原RS碼序列進(jìn)行識別時(shí)，方差d與等價(jià)碼長及等價(jià)信息位長之間的關(guān)系。

圖2 本原RS碼的等價(jià)碼長的估計(jì)Fig.2 The equivalent code length recognition of the primitive RS code

圖3 本原RS碼的等價(jià)信息位長的估計(jì)Fig.3 The equivalent message length recognition of the primitive RS code

由圖中可以看出，在等價(jià)估計(jì)碼長mn為21時(shí)，方差D出現(xiàn)最大值，故此時(shí)等價(jià)碼長mn識別為21，并且通過方差d與門限值的對比可以看出有9列大于門限值，故可識別出等價(jià)信息位長mk為9，通過計(jì)算可知，RS碼碼率為k/n=9/21=3/7。由于符號數(shù)m是等價(jià)碼長mn的約數(shù)，又是等價(jià)信息位長mk的約數(shù)，且m一般取3～8，故符號數(shù)m只能為3，并遍歷所對應(yīng)的本原多項(xiàng)式，對碼序列作GF上的傅里葉變換。當(dāng)且僅當(dāng)m=3，本原多項(xiàng)式為11(十進(jìn)制表示)時(shí)，在連續(xù)碼根α,α2,α3,α4處碼譜為0，將碼根帶入式(10)得生成多項(xiàng)式為：g(x)=x4+3x3+x2+2x+3，最后通過計(jì)算可得n=7,k=3，至此，就完成了對本原RS碼的識別。

圖4、圖5分別給出了在對縮短RS碼序列進(jìn)行識別時(shí)，方差d與等價(jià)碼長及等價(jià)信息位長之間的關(guān)系由圖中可以看出。

圖4 縮短RS碼的等價(jià)碼長的估計(jì)Fig.4 The equivalent code length recognition of the shorten RS code

圖5 縮短RS碼的等價(jià)信息位長的估計(jì)Fig.5 The equivalent message length recognition of the shorten RS code

同理可得，等價(jià)碼長mn識別為32，等價(jià)信息位長mk為16，通過計(jì)算可知，RS碼碼率為k/n=16/32=1/2。由符號數(shù)與等價(jià)碼長和等價(jià)信息位長之間的關(guān)系可知，符號數(shù)m0的估計(jì)值為4，8，遍歷所對應(yīng)的本原多項(xiàng)式，對碼序列作GF上的傅里葉變換。當(dāng)且僅當(dāng)m=4，本原多項(xiàng)式為19(十進(jìn)制表示)時(shí)，在連續(xù)碼根α,α2,α3,α4處碼譜為0，將碼根帶入式(10)得生成多項(xiàng)式為：g(x)=x4+13x3+12x2+8x+7，最后通過計(jì)算可得n=8,k=4，至此，就完成了對縮短RS碼的識別。

3.2 識別性能分析

圖6給出了不同碼長下，識別正確率與誤碼率之間的關(guān)系，分別取m等于4～8這5種情況下，此時(shí)的RS碼分別為(15，11)碼、(31，11)碼、(63，51)碼、(127，113)碼及(255，223)碼。從圖中可以看出，碼長越大，識別概率越低。在誤碼率小于0.02時(shí)，本文算法對所有碼型的識別概率都能達(dá)到90%，具有較好的容錯(cuò)能力。

圖6 不同碼長的RS碼識別性能Fig.6 Recognition result of different RS code

圖7 不同算法的性能比較Fig.7 Recognition perfor-mance comparison

圖7給出了本文方法與文獻(xiàn)[4]中基于碼重分布法以及文獻(xiàn)[5]中基于高斯約當(dāng)消元法下的識別正確率與系統(tǒng)誤碼率之間的關(guān)系，RS碼采用(7,3)編碼，從圖中可以看出,本文方法要優(yōu)于文獻(xiàn)中的方法，抗誤碼性能較好。

4 結(jié)論

根據(jù)RS碼的編碼結(jié)構(gòu)和特性，本文提出了一種新的RS碼盲識別算法。該算法首先給出了等價(jià)二進(jìn)制碼長識別模型，利用信息位與校驗(yàn)位分離法完成對等價(jià)碼長和等價(jià)信息位長的識別，然后通過搜尋連續(xù)碼根分布對本原多項(xiàng)式和生成多項(xiàng)式進(jìn)行識別，最后通過計(jì)算完成所有參數(shù)的識別。仿真結(jié)果表明，與傳統(tǒng)方法相比，本文方法能在較高誤碼率下有效完成對本原RS碼及縮短RS碼的識別，具有良好的抗誤碼性能。