龍 浪 楊俊安 劉 輝 梁宗偉

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

引 言

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

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

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

1 RS碼識(shí)別基礎(chǔ)

RS碼屬于一個(gè)特殊的非二進(jìn)制BCH碼，碼符號(hào)來(lái)源于伽羅華域(Galois field，GF)，GF(2m)，其中m表示每個(gè)符號(hào)的位數(shù)且m≥3。假設(shè)α為GF(2m)的本原元，則α2m-1=1。在糾錯(cuò)能力為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。

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

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

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

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

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

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

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

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

2 基于非零均值比的盲識(shí)別算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3 算法流程

（1）設(shè)RS碼的估計(jì)碼長(zhǎng)為n′，遍歷對(duì)應(yīng)的符號(hào)數(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′且滿(mǎn)足a?b，構(gòu)建分析矩陣。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2 識(shí)別性能分析

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

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

圖4 不同信息位長(zhǎng)識(shí)別性能比較Fig.4 Comparison of recognition performance among different information bit lengths

圖5 不同碼長(zhǎng)識(shí)別性能比較Fig.5 Comparison of recognition performance among different code lengths

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

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

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

4 結(jié)束語(yǔ)

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