基于快速碼根檢驗的RS 碼綜合識別算法

張曉林，李修橋，孫溶辰

（哈爾濱工程大學信息與通信工程學院，黑龍江 哈爾濱 150001）

0 引言

通信系統(tǒng)中，信道編碼技術實現(xiàn)了在信息層面對數(shù)據(jù)進行檢錯和糾錯。RS（Reed-Solomon）碼是一種多進制信道編碼，其由于編碼特性具有較強的抵抗突發(fā)錯誤的能力，因此被廣泛應用于深空通信和衛(wèi)星通信。在認知無線電領域，信道編碼識別是通信偵察和截獲的重要環(huán)節(jié)。如何在復雜的信道環(huán)境下根據(jù)截獲的信息快速、準確地恢復編碼參數(shù)是關鍵問題。對于RS 碼的盲識別問題，目前的識別算法依據(jù)是否需要先驗信息可分為硬判決和軟判決兩大類。硬判決算法以排除不可能事件為中心思想設置適當閾值；軟判決需要確定信噪比，并在特定的調(diào)制方式下由信噪比轉化為誤比特率，進而推導較準確的閾值，兩者各有優(yōu)缺點。

RS 碼具體的識別算法包括高斯消元法[1-2]、歐幾里得算法[3]、基于伽羅華域傅里葉變換（GFFT,Galois field Fourier transform）算法[4-7]、基于中國剩余定理算法[8]、碼根檢驗算法[9-11]等。高斯消元法通過分析矩陣秩的情況識別碼長，適用于低誤比特率情況；歐幾里得算法將碼字多項式輾轉相除，依次識別碼長和生成多項式，需要存在足夠多的正確碼字；基于中國剩余定理算法將編碼映射為環(huán)上的線性碼，依次識別碼長和本原多項式，算法復雜度低，但性能較差；基于GFFT 算法和碼根檢驗算法本質上都是基于有限域校驗矩陣尋找連續(xù)碼根，可以實現(xiàn)對碼長、本原多項式和糾錯能力的聯(lián)合識別，性能較好，但是該類算法基于有限域進行計算，復雜度高。

近些年，相關算法主要改進GFFT 和碼根檢驗。文獻[12]實現(xiàn)在二元域的識別，先通過本原元檢驗篩選，再判斷連續(xù)的偶數(shù)碼根，降低了計算復雜度，但是閾值兼容性不高。文獻[13]通過前2 個碼根篩選，再通過GFFT 進行識別，但識別過程仍然存在較高的虛警概率和漏警概率。文獻[14]提出糾正單比特錯誤碼字，但前提是需要預先得知碼長，且計算量較大。文獻[15]提出一種基于平均余弦符合度的二進制循環(huán)碼識別方法，利用軟判決序列度量奇偶校驗關系。文獻[16]提供了正確識別生成器多項式因子的概率下界。文獻[17]推導并分析了多種調(diào)制方式下的RS 碼和交織器的聯(lián)合識別。

目前，碼根檢驗算法識別性能較好，但復雜度仍有待降低，并且大多數(shù)算法基于遍歷各種參數(shù)最終選取最優(yōu)解，需要同時兼容不同長度的編碼，會犧牲不同長度編碼的特性，導致整體識別概率不高。本文提出一種快速碼根檢驗算法，利用組合碼根進行檢驗，并將RS 碼劃分為短碼和長碼分開識別。首先，在短碼情況下，降低隨機序列和相同級數(shù)不同本原多項式的RS 碼對算法的影響，通過組合碼根檢驗綜合考慮通過判定的參數(shù)，降低漏警概率；然后，對長碼直接使用碼根檢驗，快速定位參數(shù)。算法使用的校驗矩陣以二進制比特數(shù)據(jù)形式存儲，識別過程基于二元域，計算量小，速度快；另外，該算法不需要獲取先驗信息，當信道條件未知時能以較高的性能完成識別。

1 RS 碼原理及其性質

定義1[18]伽羅華域GF(q)(q＞ 2)中，本原元為α、碼長為n=q-1的本原BCH 碼為RS 碼。

RS 碼是多進制編碼，其編碼域為GF(2)的擴域GF(2m)，通常m∈ [3,8]。若本原多項式為p(x)，則可以表示為。定義(n,k)RS碼，n為碼長，k為信息位長度，糾錯能力為t。非縮短RS 碼滿足n=2m-1,n-k=2t，生成多項式通常為

其中，n為碼長，2t為校驗位數(shù)量。

根據(jù)定義2 和定理1，無錯RS 碼的譜多項式有連零成分，因此RS 碼識別問題可轉化為在未知編碼參數(shù)的條件下，通過分析矩陣ΦN×2t中零元素的分布情況，識別編碼域級數(shù)m、碼長n、信息位長度k、本原多項式p(x)以及生成多項式g(x)。

2 RS 碼快速碼根檢驗識別模型

2.1 模型假設與構建思路

RS 碼的參數(shù)識別算法通常有如下假設。1) 截獲的編碼序列已完成幀同步，信噪比、誤比特率等先驗信息未知，不參與算法的計算過程。2) 編碼類型為非縮短RS 碼，即碼長n=2m-1。3) 信息位k=1的(n,1)RS 碼校驗位較冗余，碼率極低；當7 ≤m≤ 8時，t=1的(n,n-2)RS碼糾錯性能較弱。因此，(7,1)、(1 27,1)、(2 55,253)等參數(shù)的RS 碼在實際應用中很少使用，本文不予考慮。

基于RS 碼編碼特點，建立如下數(shù)學模型。設截獲的編碼序列參數(shù)為(2m- 1,k)RS 碼，碼字數(shù)量為N，首選設置編碼域GF()，將其轉換到二進制，按行排入N×mx(-1)的識別矩陣中，Nx為待識別碼字的數(shù)量，滿足

上述碼根檢驗算法較冗余，并且算法在短碼情況下容易受相同級數(shù)m、不同本原多項式p(x)的影響，當通過判決閾值時直接完成識別會造成漏警。針對以上問題，本文從減少碼根檢驗計算量和降低識別漏警概率2 個角度展開分析。

2.2 快速碼根檢驗算法

圖1 連續(xù)偶數(shù)碼根的快速檢驗算法流程

2.3 碼根閾值選取

當編碼域設置錯誤時，由于信息位與校驗位的校驗關系被打破，按照當前參數(shù)形成的待識別碼字可等同于隨機序列，每個比特之間取值0,1 相互獨立，因此可得

對 {α α2}和 {α3α4}檢驗分別設定恰當?shù)拈撝礣h1和Th2，用于排除絕大多數(shù)隨機序列的干擾，隨機序列通過 {α α2}和 {α3α4}檢驗的概率分別為

設Nx個碼字中可通過 {α α2}和 {α3α4}檢驗的數(shù)量分別為w1和w2。由定理2 可知，若m x≠m，當前碼字為近似隨機序列，則w1和w2符合二項分布wi～B(N x,pi)，參數(shù)分別為

其中，E i和Di分別為wi(i= 1,2)的均值和方差。每個碼字是否通過 {α α2}或 {α3α4}檢驗之間相互獨立，由中心極限定理可得，當Nx足夠大時，w1和w2的分布趨向于參數(shù)為E i和Di的正態(tài)分布，即wi～N(Ei,Di)。設定一個較高的閾值Thi，則

其中，Q(x)為Q函數(shù)，即

下面，以長度等同于(7,3)RS 碼的隨機序列為例，設置數(shù)量Nx= 1000，蒙特卡羅仿真1 000 次，得到隨機序列通過碼根檢驗的數(shù)量占比和擬合正態(tài)分布曲線如圖2 所示。

圖2 w1 的概率分布曲線和擬合正態(tài)分布曲線

圖2 中擬合正態(tài)分布曲線的均值E1=15.625，方差D1=15.380 9，當設置Th1為28 時，數(shù)量大于或等于Th1的碼字概率小于0.135%，可以將大部分隨機序列剔除，將大部分t=1的RS 碼篩選出來。但是，僅靠閾值Th2不能準確地選取t≥ 2的RS 碼，原因如下。由性質1 可知，即使在無誤碼情況下，t=1的RS 碼部分許用碼字也可以通過 {α3α4}檢驗使w2≥ Th2。因此，需要同時統(tǒng)計通過 {α α2}和{α3α4}檢驗的數(shù)量，選取通過檢驗的數(shù)量與閾值差值最大的參數(shù)作為最終結果。

當信道條件較好時，正確參數(shù)的碼字通過{α α2}和 {α3α4}檢驗的數(shù)量遠大于Thi，為降低計算復雜度，仍需要設置一個極高的閾值Th3，當通過檢驗的數(shù)量超過該閾值時，直接判定該參數(shù)為正確參數(shù)。設定當P(w1)＜p3=10-5時對應的最小碼字數(shù)量為閾值，即Th3=35，對應的概率小于10-5。

2.4 算法步驟

算法整體思路如下。賦予長碼較高的置信權重，對短、長碼分別遍歷編碼域，進行參數(shù)判定。對于短碼，若通過 {α α2}檢驗的碼字數(shù)量超過Th3，則直接判定當前參數(shù)；否則，繼續(xù)遍歷，將m下的所有本原多項式進行綜合考慮，判斷所有參數(shù)的{α α2}、{α3α4}檢驗是否分別通過閾值 Th1、Th2，若通過則作為待定參數(shù)。對于長碼，若某一組參數(shù)的 {α3α4}檢驗通過閾值Th2，則直接判定為該參數(shù)；否則，選取短碼的待定參數(shù)作為識別結果。具體步驟如下。

輸入長度n（2）=Nmnbit 的二進制編碼序列、二元域校驗矩陣hτ,j

1)pλ不等，idλ相等。取最小值對應的Pλ，其參數(shù)下的編碼為隨機序列的可能性更低。

2)pλ相等，idλ不等。依據(jù)性質1，若idλ差值為1，較大idλ值對應的d有可能來源于許用碼字重疊，但由于兩者d相等，這種概率幾乎為零，因此選取較大idλ值和其對應的pλ，其參數(shù)下的編碼為隨機序列的可能性更低。

3)pλ不等，idλ不等。同情況2)，選取較大idλ值和其對應的pλ。

步驟1 中，當短碼通過較高的閾值Th3或者長碼通過Th2時直接判定當前參數(shù)。當對應多個id0時，同步驟4 中情況3)，選取較大的id0值和其對應的p0。

步驟6 中，選取待定參數(shù)集合中與閾值差值最大的參數(shù)作為最終結果，若最大差值對應的參數(shù)不唯一，選取步驟3 和步驟4 中和較大的對應的參數(shù)作為最終參數(shù)，如圖3(d)所示。

圖3 非單一最大值的選擇策略

RS 碼識別流程如圖4 所示，其中，產(chǎn)生待定參數(shù)部分對應步驟3 和步驟4，即選取通過檢驗的數(shù)量與閾值的最大差值對應的參數(shù)。

圖4 RS 碼識別流程

3 仿真驗證與分析

3.1 仿真驗證

仿真設定分別生成1 000 組RS 碼，參數(shù)設置如表1 所示。首先以(7,5)RS 碼為例，加入誤比特率為0.03 的錯誤比特，設立識別矩陣，當遍歷到mx=3,p x(x)=x3+x+1時，識別矩陣的所有行對應的連零矩陣的偶數(shù)分布向量為d=(462,2,0)，其中d2= 462大于實際中算法設定閾值Th3=35，所以當遍歷到d2=35時即可完成識別，求出連續(xù)根為α,α2，由連續(xù)根個數(shù)為2，求得碼長n=7，信息位長度k=7 -2=5，g(x)=(x-α)(x-α2)=x2+α4x+α3，識別正確。

表1 RS 碼參數(shù)設置、本原多項式和生成多項式

然后，以(31,27)RS碼為例，加入誤比特率為0.03 的錯誤比特。由于當m x＜m時，Nx＞ 1000，因此仿真時取N′= min(1000,Nx)。由于碼長增加，正確碼字減少，經(jīng)計算后所有參數(shù)均未通過閾值Th3，由閾值 Th1和 Th2得到幾組待定參數(shù)，如表2所示。當遍歷到mx=4,p x(x)=x4+x+1和mx=5,px(x)=x5+x4+x3+x2+1，以及mx=5,px(x)=x5+x2+1時，d中分別存在通過對應閾值 Th2,Th1,Th2的元素，將三組參數(shù)作為待定參數(shù)，并分別計算d與閾值的差值，得到 Δth1,Δth2,Δth3分別為0,1,3，顯然最大值為Δth3，對應的元素為d4，因此最終識別參數(shù)為m=5,p(x)=x5+x2+1,n=31,k=31 -4= 27,g(x)= (x-α)(x-α2)(x-α3)(x-α4)=x4+α24x3+α19x2+α29x+α10，識別正確。

表2 (31,27)RS 碼識別待定參數(shù)

同理，設置誤比特率為0.004，識別(127,119)RS碼，當遍歷到mx=7,p x(x)=x7+x3+x2+x+1時

3.2 性能分析

由式(12)計算等效的GF(2)校驗矩陣元素，算法計算量主要源于二元域加法。求解一次的模2加運算量為wτ,δ，其中1 ≤τ≤n-1,0 ≤δ≤m-1。將不同取值的τ,δ進行平均化處理，通過仿真得到不同級數(shù)m下的如表3 所示。

表3 不同m 下的

表3 不同m 下的

當級數(shù)m設置錯誤時，由式(13)可知碼根快速檢驗的平均模2 加計算量為

若級數(shù)設置正確，即m=m0，分析誤比特率對算法運算量的影響。低誤比特率情況下，由于閾值Th3的設置，當通過檢驗的數(shù)量達到閾值后停止識別。設停止識別前含錯誤比特的碼字數(shù)量為Ne，無錯碼字數(shù)量為Th3(m)，則 0≤Ne≤N- Th3(m0)，含錯碼字平均模2 加計算量為T0(m0,Ne)，無錯碼字模2 加計算量為

最壞情況下，所有編碼都是最后一個本原多項式，則算法總的模2 加計算量為

其中，γ(m)為級數(shù)m下的本原多項式數(shù)量，m′=m0。同時，考慮到更新向量d的計算量，以及步驟4 的求和計算量T2(m)=2m-1-3，最壞情況下，存在單糾錯和多糾錯情況共8 個待定參數(shù)，因此加法計算量為

對于高誤比特率情況，最壞情況下正確參數(shù)的編碼數(shù)量恰好接近臨界值Th3，需要遍歷所有短碼，此時有

算法完成識別的理論上限是編碼序列中存在至少一個正確碼字。設編碼序列的誤比特率為ε，則碼字無錯誤比特的概率為(1-ε)mn，編碼序列中存在至少一個無錯誤比特碼字的概率為

其中，N為編碼序列的碼字數(shù)量，原理上算法的識別概率P≈Pr。設置存在正確碼字的概率為Pr≥ 0.99，則可以得到不同誤比特率下算法實現(xiàn)99%以上識別率所需的最少碼字數(shù)量，如圖5 所示。當誤比特率增加時，所需碼字數(shù)量快速增加，理論上，只要碼字數(shù)量足夠多就可以完成識別，但實際中獲取的碼字數(shù)量有限。

圖5 不同誤比特率下算法實現(xiàn)99%以上識別率所需的最少碼字數(shù)量

以數(shù)據(jù)存儲和深空通信中常用的編碼類型，包括(7,3)RS 碼、(15,9)RS 碼、(31,15)RS 碼、(63,57)RS 碼、(127,111)RS 碼和(255,223)RS 碼為例，隨機選取本原多項式，仿真產(chǎn)生每種編碼各1 000 組碼字，并加入錯誤比特，蒙特卡羅仿真500 次，根據(jù)式(29)得到算法識別率曲線和正確碼字存在概率曲線，如圖6 所示。圖6 中，實線為實際仿真的識別概率P，虛線為正確碼字存在概率Pr，即識別上限。由圖6 可知，當信道環(huán)境變差，或碼長增加時，正確碼字數(shù)量銳減直至為零。由于設置了組合碼根檢驗并綜合分析待定參數(shù)，本文算法極大地降低了漏警概率，當級數(shù)4 ≤m≤ 8時，識別率P與Pr曲線基本重合；當級數(shù)m=3時，由于碼長較短，隨機序列和相同m不同p(x)的RS 碼容易通過 {α α2}和 {α3α4}檢驗，因此識別率P與Pr有差值。

圖6 RS 碼識別率曲線和正確碼字存在概率曲線

仿真不同糾錯能力對算法識別率的影響。以碼長n=31為例，分別設置不同t值的1000 組編碼，并加入錯誤比特，蒙特卡羅仿真500 次，(31,31 -2t)RS 碼識別率曲線和正確碼字存在概率曲線如圖7 所示。由圖7 可知，糾錯能力t≥2的RS 碼的識別率P與Pr曲線基本重合，由此可知算法受碼率的影響較小，穩(wěn)定在臨界值附近；t=1時的(31,29)RS 碼校驗位較少，碼率較高，編碼與隨機序列的差異性小，識別率P與Pr有差值，但仍能在誤比特率為0.03 時達到99%的識別率。

圖7 (31,31 -2 t)RS 碼識別率曲線和正確碼字存在概率曲線

3.3 其他算法對比

首先，對比算法計算量，包括文獻[4]算法、文獻[12]算法和文獻[13]算法。若正確級數(shù)為m0，文獻[4]算法對所有碼字做GFFT，模2 加計算量為

文獻[12]算法經(jīng)過一次碼字剔除后剩余碼字數(shù)量為，模2 加計算量為

文獻[13]算法經(jīng)2Nx次碼根檢驗后對Ngn個碼字做GFFT，模2 加計算量為

設置碼字數(shù)量為1 000，統(tǒng)一使用圖6 中的6 種RS 碼，誤比特率分別為0.02、0.01、0.005、0.002、0.001 和0.000 4。假設在最壞的情況下，本原多項式為最后一項。將加法計算量等同于模2 加計算量，不同級數(shù)m下的算法復雜度對比如圖8 所示。由圖8 可知，算法模2 加計算量隨級數(shù)m增大呈指數(shù)級增加。低誤比特率下，由于使用快速碼根檢驗算法，本文算法復雜度相比同類算法明顯降低，無論短碼還是長碼都可以用較低的計算量完成識別。隨著誤比特率增大，本文算法為降低漏警概率提高識別精度，需要遍歷短碼的全部本原多形式，計算量逐漸增加，并接近長碼的計算量，級數(shù)m=3,4時高于文獻[12-13]算法的計算量。

圖8 算法復雜度對比

然后，仿真并分析文獻[12-13]算法和本文算法的漏警概率。在對某一特定的RS 碼進行識別時，存在識別正確、識別錯誤和未得出識別結果3 種情況，將其概率值分別設為P,Perr,Pnull，則漏警概率Pmiss=Perr+Pnull。以(7,3)RS 碼、(15,9)RS 碼這2 種短碼為例，在不同誤比特率下進行500 次蒙特卡羅仿真，得到算法的漏警概率對比如圖9 所示。由圖9可知，本文算法可在高誤比特率下將部分未識別的結果正確識別，與文獻[13]算法相比，本文算法雖然錯誤識別的數(shù)量小幅度增加，但整體的漏警概率降低。

圖9 算法漏警概率對比

最后，對比本文算法與以上幾種同類算法的識別率。以(7,3) RS 碼、(31,15) RS 碼 和(255,223)RS 碼為例，設置碼字數(shù)量為1 000，分別在不同的誤比特率下進行500 次蒙特卡羅仿真，得到不同算法識別率對比如圖10 所示。由圖10 可知，本文算法的識別率好于其他3 種算法。文獻[12]算法通過校驗和的統(tǒng)計特性設置閾值，并將編碼域和生成多項式分開識別，第一步判決虛警概率和漏警概率都較高；文獻[13]算法在短碼情況下容易受隨機序列影響，漏警概率高。本文算法通過兩組碼根檢驗，并綜合分析待定參數(shù)，因此識別性能明顯好于文獻[12]算法，在短碼情況下較文獻[13]算法更優(yōu)。

圖10 不同算法識別率對比

4 結束語

本文從降低碼根檢驗角度出發(fā)，提出了 一種快速碼根檢驗算法，并將RS 碼劃分為長碼和短碼，通過組合碼根檢驗綜合分析待選參數(shù)，最終完成級數(shù)、本原多項式和生成多項式的聯(lián)合識別。本文使用的綜合識別算法在相對較低的復雜度下降低了識別漏警概率，實現(xiàn)了較好的識別性能，并且在高誤比特率環(huán)境下依然能夠完成識別。本文算法不需要信道先驗信息，因此適用于多種信道環(huán)境，具有較好的工程實用性。本文算法的代價是需要提前存儲二元域校驗矩陣，犧牲存儲空間以加快識別速度；同時，在信道環(huán)境較惡劣時，通過犧牲一定的算法復雜度以提升短碼的識別性能。