基于信息位與校驗位分離的RS碼盲識別

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

(1.國防科技大學電子對抗學院，安徽 合肥 230037；2.安徽省電子制約技術重點實驗室，安徽 合肥 230037)

0 引言

RS(Reed Solomon，RS)碼是一類糾錯性能優異的多進制BCH(Bose Chaudhuri Hocquenghem)碼，它具有編碼結構簡單，糾正隨機錯誤和突發錯誤能力強的特點，被廣泛應用于無線通信、深空通信、軍事通信等各個領域中[1]。因此，研究RS碼的盲識別方法有重要意義。

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

1 RS碼識別基礎

1.1 RS碼的定義

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

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

1.2 RS碼的性質

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

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

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

性質2[5]:RS碼的碼字信息位與校驗位線性相關。

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

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

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

2 RS碼盲識別實現

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

2.1 基于信息位與校驗位分離的盲識別算法

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

(1)

如校驗位c10是信息位m1和m2異或相加所得，則校驗位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)

同理，校驗位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)

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

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為分析矩陣的列數。

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

(7)

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

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

(8)

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

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

2.1.1等價碼長識別

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

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

現在，可能有三種排列的情況：

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

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

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

在構建分析矩陣后，計算每列的0、1概率方差及所有列概率方差的方差d，當且僅當碼字對齊，且每行對應于實際的等價碼長大小時，方差d最大，完成對等價碼長mn的識別。

2.1.2等價信息位長識別

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

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

(9)

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

2.2 符號數及本原多項式識別

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

表1 m值及其對應的本原多項式十進制表示

2.3 生成多項式識別

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

(10)

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

2.4 算法流程：

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

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

步驟6 找到連零碼譜出現位置所對應的碼根，根據式(10)計算出生成多項式。

3 仿真實驗與性能分析

3.1 實驗驗證

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

表2 參數設置

圖2、圖3分別給出了在對本原RS碼序列進行識別時，方差d與等價碼長及等價信息位長之間的關系。

圖2 本原RS碼的等價碼長的估計Fig.2 The equivalent code length recognition of the primitive RS code

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

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

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

圖4 縮短RS碼的等價碼長的估計Fig.4 The equivalent code length recognition of the shorten RS code

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

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

3.2 識別性能分析

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

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

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

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

4 結論

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