基于非零均值比的RS 碼盲識別方法

龍 浪 楊俊安 劉 輝 梁宗偉

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

引 言

在數(shù)字通信中，信道編碼可以提高通信的可靠性，目前信道編碼主要包括線性分組碼、RS（Reed-Solomon）碼、卷積碼和低密度校驗(yàn)碼（Low-density parity-check，LDPC）碼等[1-2]，其中RS碼是一種特殊的非二進(jìn)制BCH（Bose-Chaudhuri-Hocquenghem）碼，具有糾錯能力強(qiáng)的特點(diǎn)，在數(shù)據(jù)存儲、軍事通信、衛(wèi)星通信和數(shù)字視頻廣播（Digital video broadcasting，DVB）系統(tǒng)中起著至關(guān)重要的作用。因此，研究RS碼的盲識別方法有重要意義。

現(xiàn)有文獻(xiàn)表明，國內(nèi)外已有大量學(xué)者對RS碼盲識別算法展開研究。文獻(xiàn)[3]對各種非二進(jìn)制糾錯碼的碼長進(jìn)行了盲識別，并擴(kuò)展到有噪環(huán)境下的研究,但未對RS碼其他編碼參數(shù)進(jìn)行識別。文獻(xiàn)[4]在文獻(xiàn)[5]對偶碼的識別基礎(chǔ)上研究了有噪環(huán)境下的RS碼盲識別，但算法抗誤碼性能不佳。文獻(xiàn)[6]提出一種基于后驗(yàn)校驗(yàn)對數(shù)似然比[6-8]的方法來對RS碼進(jìn)行識別，但需要在發(fā)射端和接收端預(yù)定義RS編碼集。以上方法并未對縮短RS碼進(jìn)行識別，識別分析不夠全面。

針對以上不足，本文提出一種基于非零均值比的盲識別算法來完成RS碼和縮短RS碼的識別。利用截獲到的RS碼序列建立分析矩陣，通過有限域的高斯約當(dāng)算法[9]獲得分析矩陣的非零均值比，以此來識別碼長、符號數(shù)和本原多項(xiàng)式，然后通過伽羅華域傅里葉變換(Galois field Fourier transform，GFFT)來完成信息位長及生成多項(xiàng)式的識別，最后針對典型的RS碼和縮短RS碼編碼方式，設(shè)計了仿真分析實(shí)驗(yàn)，對不同識別算法在不同誤碼率下的識別性能進(jìn)行了分析比較。

1 RS碼識別基礎(chǔ)

RS碼屬于一個特殊的非二進(jìn)制BCH碼，碼符號來源于伽羅華域(Galois field，GF)，GF(2m)，其中m表示每個符號的位數(shù)且m≥3。假設(shè)α為GF(2m)的本原元，則α2m-1=1。在糾錯能力為t的(n,k)RS碼中，α,α2,…α2t是 n-k次生成多項(xiàng)式 g(x)的根，則 g(x)為

式中：φi(x)是 αi的最小多項(xiàng)式，由于 αi是 GF(2m)中的元素，φi(x)=x- αi，則 g(x)可以表示為[10]

式中：g(x)有2t+1非零項(xiàng)，而g(x)是n-k次多項(xiàng)式，所以n-k=2t。

綜上所述，需要識別的GF(2m)上的RS碼參數(shù)分別為：

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

(2)信息位長k=n-2t。

(3)校驗(yàn)位長2t=n-k。

(4)生成多項(xiàng)式g(x)。

(5)符號數(shù)m，一般m取3～8。

(6)本原多項(xiàng)式p(x)，一般采用十進(jìn)制表示，如p=41表示 p(x)=x5+x3+1，因?yàn)?110=1010012。符號數(shù)m及其本原多項(xiàng)式如表1所示[12]。

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

2 基于非零均值比的盲識別算法

在實(shí)際通信系統(tǒng)中，(n,k,m,p)RS碼是以二進(jìn)制等價碼流進(jìn)行傳輸?shù)腫13]，所以需先將截獲得到的RS碼序列轉(zhuǎn)化為GF(2m)碼元，并構(gòu)建分析矩陣，通過有限域的高斯約當(dāng)算法[9]獲得分析矩陣的非零均值比，以此來識別碼長、符號數(shù)和本原多項(xiàng)式，最后通過GFFT來完成信息位長及生成多項(xiàng)式的識別。

2.1 基于非零均值比的碼長、符號數(shù)和本原多項(xiàng)式的識別

利用假定的符號數(shù)m′及本原多項(xiàng)式p′將截獲到的RS碼流轉(zhuǎn)化為GF(2m)上的0～2m元素，按行放入一個a×b的矩陣A中，其中a表示矩陣的行數(shù)，b表示矩陣的列數(shù)，且a?b。如果矩陣A的矩陣列數(shù)為真實(shí)碼長且符號數(shù)及本原多項(xiàng)式估計正確時，則每行的信息位和校驗(yàn)位對齊，由于校驗(yàn)碼元與信息碼元線性相關(guān)，每行均存在著相同的線性關(guān)系，當(dāng)對矩陣A進(jìn)行高斯消元變換后，n-k列相關(guān)列（校驗(yàn)位所在的列）將會被消去，只會留下k列非零列即獨(dú)立列（信息位所在的列），如圖1(a)所示，分析矩陣將會出現(xiàn)秩的缺失；反之，當(dāng)列數(shù)不是真實(shí)碼長或符號數(shù)及本原多項(xiàng)式估計錯誤時，同一碼字的信息位和奇偶校驗(yàn)位在不同的行中被隔離，在同一列中沒有正確對齊，校驗(yàn)位不能被表示為信息位的線性組合，在特定的行中線性關(guān)系將受到影響，而這將導(dǎo)致列之間的線性關(guān)系消失，因此，矩陣A會表現(xiàn)得像一個隨機(jī)矩陣。當(dāng)矩陣A進(jìn)行高斯消元變換后，由于不存在相關(guān)列，所以秩被完全獲得，如圖1(b)所示，則分析矩陣為滿秩矩陣。

簡而言之 ，當(dāng)且 僅當(dāng)m′=mest,p′=pest,b=nest時，矩陣A為秩缺矩陣，在無誤碼的情況下計算矩陣秩ρ如式(3)所示，歸一化秩ρ′如式(4)所示，此時，秩ρ等于信息位長，歸一化秩ρ′為碼率r。

圖1 分析矩陣結(jié)構(gòu)圖Fig.1 Structure of analysis matrix

其他情況下，矩陣A為滿秩矩陣，此時矩陣秩ρ如式(5)所示，歸一化秩ρ′如式(6)所示，此時，秩ρ等于列數(shù)，歸一化秩ρ′為1。

在無誤碼的情況下，可利用有限域的高斯約當(dāng)法對矩陣A求秩來識別碼長、符號數(shù)及本原多項(xiàng)式，當(dāng)且僅當(dāng)歸一化秩ρ′最小時完成識別。然而在有誤碼的情況下，直接求秩法并不適用[5，9，14]。如前所述，當(dāng)一個矩陣所有行和列都是線性無關(guān)的，此時稱為滿秩矩陣；如果一個矩陣至少有一列/行依賴于其他列/行，那么此時會出現(xiàn)秩缺。在實(shí)際通信系統(tǒng)中，傳輸錯誤或白噪聲的存在增加了行/列之間的線性無關(guān)性[15]，并且這種線性無關(guān)隨著噪聲強(qiáng)度的增大而增大，當(dāng)噪聲水平超過閾值時，使分析矩陣A不會有任何相關(guān)列/行，就像一個隨機(jī)矩陣。此時，不管列數(shù)b是否等于真實(shí)碼長，矩陣A均會是一個滿秩矩陣。

但在有誤碼的情況下，利用有限域的高斯約當(dāng)算法將矩陣A轉(zhuǎn)換成為三角矩陣Q，通過對下三角陣Q的觀察可以發(fā)現(xiàn)，與獨(dú)立列相比，相關(guān)列的非零元素較少，因此，存在秩缺失的矩陣比滿秩矩陣含有的零元素要少，因此，在有誤碼的情況下，可以根據(jù)矩陣Q中每列的非零元素所占的比例來確定矩陣的秩缺情況，故定義非零均值比u′(b)來表示矩陣的秩缺失情況為

式中：φ′(c)表示第c列中非零的數(shù)目，φ′(c)表示下三角矩陣Q中第c列含非零數(shù)目所占比重。

利用有限域的高斯約當(dāng)消元法將分析矩陣A轉(zhuǎn)化為下三角陣Q后，通過計算矩陣Q的非零均值比u′(b)來完成 RS碼參數(shù)的盲識別，當(dāng)且僅當(dāng) m′=mest,p′=pest,b=nest時，u′(b)最小。

2.2 信息位、校驗(yàn)位及生成多項(xiàng)式的識別

設(shè)GF(2m)上的多項(xiàng)式[16]

則它在GF(q)的譜多項(xiàng)式為

在RS碼中，碼多項(xiàng)式與生成多項(xiàng)式具有相同的碼根，因此，在碼長，符號數(shù)及本原多項(xiàng)式正確識別后，將接受序列按正確碼長分組對其進(jìn)行GFFT變換，并采用最大似然法來評估根數(shù)，當(dāng)多組碼字經(jīng)GFFT后具有相同的連零位置且個數(shù)相同時，由此可以估計出碼根數(shù)即校驗(yàn)位長2t，通過計算n-2t=k即可求取信息位長，最后通過式（2）得到生成多項(xiàng)式g(x)。

2.3 算法流程

（1）設(shè)RS碼的估計碼長為n′，遍歷對應(yīng)的符號數(shù)m′及本原多項(xiàng)式p′，并利用p′將截獲的RS碼序列由GF(2)轉(zhuǎn)化為GF(2m)中的元素。

（2）將轉(zhuǎn)化后的RS碼序列按行放入a×b的矩陣A中，其中a為矩陣的行數(shù)，b為矩陣的列數(shù)，b=n′且滿足a?b，構(gòu)建分析矩陣。

（3）利用有限域的高斯消元法將A轉(zhuǎn)化為下三角陣Q。

（4）計算每列列中非零的數(shù)目φ′(c)，并計算出每列非零數(shù)目所占比重φ′(c)。

（5）計算整個下三角陣Q的非零均值比u′(b)。

（6）改變 RS 的估計碼長 n′，重復(fù)步驟（1）—（5），當(dāng)且僅當(dāng)非零均值比 u′(b)最小時完成識別，即

（7）計算碼字多項(xiàng)式的根，記錄根的數(shù)目來估計n-k，從而計算出信息位長k。

（8）根據(jù)式(2)計算生成多項(xiàng)式g(x)。

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

3.1 實(shí)驗(yàn)仿真

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

表2 參數(shù)設(shè)置Tab.2 Parameter setting

從圖2可以看出，與其他可能的組合相比，當(dāng)[n,m,p]=[63,6,103]時，u′(b)達(dá)到最小值，因此，可以識別出碼長，符號數(shù)及本原多項(xiàng)式。當(dāng)正確識別碼長、符號數(shù)及本原多項(xiàng)式后，利用GFFT可以計算出在碼根α5,α4,α3,α2,α處碼譜為 0，碼根數(shù)為 5，即校驗(yàn)位長 2t=5，則k=n-2t=58，即信息位長 58，將碼根代入式（2），可以得到生成多項(xiàng)式g(x)=x5+62x4+32x3+53x2+3x+31。至此，完成了對本原RS碼的識別。

同樣地，在圖3中，當(dāng)[n,m,p]=[204,8,285]，u′(b)達(dá)到最小值，因此，可以識別出碼長、符號數(shù)及本原多項(xiàng)式。當(dāng)正確識別碼長、符號數(shù)及本原多項(xiàng)式后，利用GFFT可以計算出在碼根α5,α4,α3,α2,α處碼譜為0，碼根數(shù)為5，即校驗(yàn)位長2t=5，則k=n-2t=199，即信息位長199，將碼根代入式（2），可以得到生成多項(xiàng)式g(x)=x5+62x4+63x3+229x2+197x+38。至此，完成了對縮短RS碼的識別。

圖2 本原RS碼識別時u′(b)隨估計參數(shù)的變化Fig.2 Values of assuming primitive RS code

圖3 縮短RS碼識別時u′(b)隨估計參數(shù)的變化Fig.3 Values of assuming short RS code

3.2 識別性能分析

在圖4中，對n=15,m=4,p=19的RS碼，選取k=7,k=9,k=11不同的信息位長在不同誤碼率的情況下進(jìn)行識別性能分析，從圖4中可以看出，RS碼參數(shù)識別性能隨著信息位長k或碼率r的增大而減小。隨著r的增大，n-k減小即相關(guān)列會隨之減少，利用u′(b)區(qū)分滿秩矩陣和秩缺矩陣難度加大，因此，識別難度加大，準(zhǔn)確度下降。

在圖5中，對碼率r≈0.6的(63,38,6,67)RS碼，(127,76,7,131)RS碼和(255,153,8,285)RS碼在不同誤碼率的情況下進(jìn)行識別性能分析，從圖5中可以看出，RS碼參數(shù)識別性能隨著碼長n的增大而減小，在誤碼率不超過0.02時，對所有RS碼都能達(dá)到90%的識別率，具有較好的識別性能。

圖4 不同信息位長識別性能比較Fig.4 Comparison of recognition performance among different information bit lengths

圖5 不同碼長識別性能比較Fig.5 Comparison of recognition performance among different code lengths

圖6 3種算法識別性能比較Fig.6 Comparison of recognition performance among three algorithms

表3 不同算法的運(yùn)行時間對比Tab.3 Comparison of run time among different algorithms

圖6給出了在采用(15,7,4,19)RS碼時，本文算法，文獻(xiàn)[6]中基于后驗(yàn)校驗(yàn)對數(shù)似然比算法與文獻(xiàn)[4]中基于Barbier方法的參數(shù)估計法的比較。隨著誤碼率的增加，3種算法識別性能也隨之下降，但本文算法下降較慢，優(yōu)于其他兩種算法，并給出了正確識別一次3種算法所需時間，如表3所示，本文算法運(yùn)算時間由于經(jīng)過多次行列變換，稍遜于基于后驗(yàn)校驗(yàn)對數(shù)似然比算法，但抗誤碼性能較優(yōu)。

4 結(jié)束語

根據(jù)RS碼的編碼結(jié)構(gòu)及特點(diǎn)，提出了一種基于非零均值比的RS碼盲識別方法，利用有限域的高斯消元法計算出分析矩陣的非零均值比來確定碼長、符號數(shù)及本原多項(xiàng)式，然后利用GFFT變換求解出其他參數(shù)，完成了對本原RS碼縮短RS碼的識別，并且分析了信息位長和碼長與識別的準(zhǔn)確性之間的關(guān)系，隨著信息位長和碼長度的減少，識別更加準(zhǔn)確。并與文獻(xiàn)[4，6]方法進(jìn)行比較，本文算法抗誤碼性能優(yōu)于其他兩種算法，并且計算復(fù)雜度低，更適合有噪環(huán)境下的RS碼識別。