突發錯誤檢測重數分配算法及其電路設計

胡巖,張為,王令宇,王旸

(天津大學微電子學院,300072,天津)

差錯控制編碼是使用信道編譯碼技術對信道噪聲產生的錯誤進行控制糾正以提高數字信息傳輸準確性的基本方法,目前廣泛應用的差錯控制編碼主要有Turbo碼、低密度奇偶校驗碼、極化碼和里德-所羅門(Reed-Solomon,RS)碼[1]等,其中RS碼因其能夠糾正隨機錯誤和突發錯誤的特性而被廣泛應用。RS碼的譯碼算法直接決定了信息傳輸的準確性,目前,RS譯碼算法主要分為兩種,分別是硬判決譯碼(hard decision decoding,HDD)[2]和代數軟判決譯碼(algebraic soft decoding,ASD)[3],相比較于HDD,ASD譯碼算法能夠獲得更加顯著的譯碼增益和更好的譯碼性能,軟判決譯碼算法中,低復雜度蔡斯(low-complexity chase,LCC)[4]算法因為其重數為1、計算簡單而得到廣泛研究。

近幾年來,高速數字通信系統中隨機錯誤譯碼算法取得了很多突破性的進展[5],然而,突發錯誤譯碼算法的研究仍然被復雜的計算和結構所限制。最近,有研究者提出了新的糾正突發錯誤的譯碼算法并取得了廣泛的關注[6-9],其中,改進于突發錯誤糾正(burst-error correction, BC)算法[6]的新型無逆突發錯誤糾正(reformulated inversionless BC, RiBC)[7]算法已經取得實際應用,但該算法為硬判決譯碼算法,沒有充分利用信道軟信息,譯碼復雜度高;改進于基于硬判決的LCC(HDD-LCC)算法[10]與RiBC的BCHDD-LCC算法[11]將突發錯誤譯碼和隨機錯誤譯碼相融合,取得了更好的譯碼性能,但該算法中采用的信道模型不能完成對隨機錯誤信道與突發錯誤信道的識別,此外,采用的突發錯誤預判斷機制缺乏理論依據,且對突發錯誤位置的判斷范圍較大,準確度差。

為解決上述問題,從信道中獲取突發錯誤軟信息并且將突發錯誤信道與隨機錯誤信道相結合,實現兩種信道的識別和轉換以便更加有針對性地進行譯碼,本文提出了一種新的混合信道模型,從該模型出發提出了基于突發錯誤檢測的新型重數分配(BD-RCMA)算法,通過在傳統RS碼軟判決獲得的信道軟信息中,充分挖掘符號中各子碼的電平信息,獲取突發錯誤的準確位置,降低后續譯碼的迭代次數,充分發揮RS碼糾正突發錯誤的能力。與現有算法相比,該算法能夠顯著提高突發錯誤信道下的譯碼性能。

1 混合信道模型

隨機噪聲指的是通信系統中的加性白噪聲,而突發噪聲通常由脈沖干擾和多徑衰落的原因引入。經隨機噪聲與突發噪聲干擾的RS碼編譯碼的數字通信系統框圖如圖1所示。圖1中的數字信道由隨機噪聲源ng(n)和突發噪聲源nb(n)組成。對于RS(n,k)碼,n=2q-1,一個編碼后的RS碼符號由q個子碼組成,因此信息傳輸的基本單元是子碼而非編碼后的符號。對于子碼進行研究,可以在僅增加少量計算量的條件下更好地反映信道噪聲對電平的作用與影響,因此本文以子碼作為研究信道噪聲的基本單元,突發錯誤是指由突發噪聲脈沖干擾造成的的連續子碼錯誤。為簡化模型建立,首先做幾點合理性假設:

(2)突發噪聲脈沖到來的概率為泊松分布,泊松到達率為τ[12];

(3)突發噪聲脈沖具有固定長度其造成的突發錯誤所包含的子碼數量為L[13]。

圖1 有噪聲干擾的RS碼數字通信系統框圖

1.1 噪聲占比參數

(1)

(2)

假設在1 s內通過方差為σ2的加性高斯白噪聲(AWGN)信道傳輸f個子碼,則譯碼器在1 s內收到的子碼序列為x=[x1,x2,…,xf],且期望E(x)=0,方差D(x)=E(x2)=σ2,該子碼序列的能量E為每一個子碼的電平的平方和

(3)

由此可得

(4)

(5)

(6)

式中:Eg、Eb與Ec分別為受隨機噪聲ng(n)、突發噪聲nb(n)與信道噪聲nc(n)干擾后的子碼的能量。由于信息發送端發送功率保持不變,因此在給定信道信噪比RSN的條件下,信道的噪聲能量為常數,從而有

(7)

則突發噪聲的能量越大,隨機噪聲的能量就越小,據此定義信道噪聲占比參數

(8)

參數ψ反映了在信道噪聲中突發噪聲的占比情況,仿真給出了當RSN=5,ψ=0.2～1.0時,信道中突發噪聲與隨機噪聲的干擾造成的子碼電平波動如圖2所示。從圖2可以發現,當ψ≥0.4時,受突發噪聲干擾的子碼電平值通常是受隨機噪聲干擾的子碼電平值的3倍或更多,此時,子碼錯誤通常成串出現,所以通過參數ψ來區分信道狀態。當ψ≥0.4時,信道被認為是突發錯誤信道,此時引入馬爾科夫轉狀態移鏈(MC)模型[11]來描述錯誤內部特性,反之則認為是隨機錯誤信道,用AWGN信道進行描述。

圖2 信道傳輸后的子碼電平

1.2 馬爾科夫狀態轉移鏈模型

當ψ≥0.4時,為了描述突發錯誤內部特性,引入MC模型[11]描述突發錯誤的記憶特性,模型如圖3所示。由于突發噪聲所能干擾的子碼數為L,因此MC模型有L+1個狀態,每一次狀態轉移對應每一個子碼到來。

圖3 馬爾科夫狀態轉移鏈模型

新型混合信道模型實現了隨機錯誤信道與突發錯誤信道的一體化建模,并通過噪聲占比參數實現了2種信道的識別與轉換方式,根據信道下譯碼方式的相似性實現譯碼算法的結合和譯碼器結構的復用,相較于傳統的隨機錯誤信道或突發錯誤信道單一建模的方式更加接近實際信道隨機噪聲與突發噪聲共同存在的環境,在此新型混合信道下進行合理性研究可以充分發揮RS碼糾正隨機錯誤與突發錯誤的能力,相較于針對單一高斯分布隨機錯誤[14]或突發錯誤的譯碼方式具有更加優異的性能。

2 新型重數分配算法

2.1 RCMA算法

在RS(n,k)碼譯碼條件下,RCMA算法[15]的偽代碼如下。

1 Input:接收電平ri,k與插值點個數η;

2 對于每一個符號i(0≤i≤n-1)與其第t(0≤t≤q-1)個子碼,計算

4 fori=0:n-1

5 begin

10 end

11 Output:2η個測試向量。

該算法經過理論推導得到結論:符號的可靠度僅與該符號內電平絕對值最小的子碼有關,即

(9)

式中:Γi為第i個符號的可靠度;|ri,k|為第i個符號第k個子碼接收電平的絕對值,|ri,k|越小,則Γi越大,該符號越不可靠。

2.2 BCHDD-LCC譯碼算法

BCHDD-LCC譯碼算法由重數分配(MA)、校驗子計算(SC)、校驗子更新(SU)、關鍵方程求解(KES)、多項式選擇(PS)、錢搜索和福尼算法(CSFA)6個模塊組成。該算法是通過將KES模塊中求解隨機錯誤的RiBM算法與求解突發錯誤的RiBC算法相結合,通過2種算法迭代的相似性復用譯碼器單元,從而實現對信道中產生的隨機錯誤與突發錯誤進行糾正。該算法產生2個關于突發錯誤的信號變量b和p,分別表示是否有突發錯誤產生以及突發錯誤的大致位置。若b為1,代表有突發錯誤產生,則采用RiBC算法進行關鍵方程求解,反之采用RiBM算法求解。RiBC算法只在產生突發錯誤并且突發錯誤所包含的子碼數在碼字糾錯范圍內時應用,而在其他情況下則使用求解隨機錯誤下關鍵方程的RiBM算法。

在采用RiBC算法糾正突發錯誤時,需要對突發錯誤位置進行預判斷,用b進行記錄并作為RiBC算法的輸入,這將在MA模塊中進行。MA模塊為后續模塊提供插值點和突發錯誤位置信息,BCHDD-LCC譯碼器中采用的獲取插值點的算法是RCMA算法,而獲取突發錯誤位置的方法是根據經驗確定一個閾值,使得隨機錯誤位置處的電平在該閾值以下,而突發錯誤位置處的電平在該閾值以上,并據此給出突發錯誤位置信息。

2.3 BD-RCMA算法

由于BCHDD-LCC譯碼算法中獲取突發錯誤位置的經驗閾值方法缺少一定的理論基礎,對于突發噪聲下頻繁變動的子碼電平很難給出準確的突發錯誤位置信息,因此本文提出基于突發錯誤檢測的新型重數分配算法,將獲取插值點與突發錯誤位置統一于重數分配算法中,在提高算法性能的同時降低運算復雜度。

由圖1可知,隨機噪聲與突發噪聲將導致子碼電平產生不同的波動,突發錯誤信道下突發噪聲的影響較大,導致子碼電平的波動較大,且通常為連續波動,而隨機噪聲對子碼電平波動的影響較小,因此可根據符號內子碼電平的波動情況獲取突發錯誤位置。符號內子碼電平波動越大即電平絕對值越大,則該符號越有可能處于突發錯誤狀態。用|ri,l|表示第i個符號的第l個子碼接收電平的絕對值,該子碼為該符號內接收電平絕對值最大的子碼。類似于符號可靠度,定義突發錯誤狀態的可能性即突發度為

(10)

由式(10)可知,|ri,l|越大,Bi越小,該符號越有可能為突發錯誤位置。

(11)

式中:κTH=max{|μ-3σc|,|μ+3σc|}對于第i個符號,若|ri,l|≥κTH,即Bi≤BTH,該符號為突發錯誤位置,反之則為隨機錯誤位置。綜上,BD-RCMA算法的偽代碼如下:

1 Input:子碼接收電平ri,k與插值點個數η;

2 對于每一個符號i(0≤i≤n-1)與其第k個子碼(0≤k≤q-1),計算:

突發閾值κTH=max{|μ-3σ2|,|μ+3σ2|};

4 fori=0:n-1

5 begin

然而，作為一名大學教師，筆者感到當代大學生家庭感恩教育和社會感恩教育的缺乏和不成功，由此在大學階段進行感恩教育更加必要。

10 ifκi>κTH

12 end

BD-RCMA算法的輸入同RCMA算法,對于每一個符號i以及它的第k個子碼,在RCMA基礎上計算該符號內子碼電平絕對值的最大值κi與突發閾值κTH,如果κi≥κTH,則i為突發錯誤位置,反之則不是。BD-RCMA算法在獲取插值點的同時更精確地獲取突發錯誤位置信息,最后輸出突發錯誤位置信息到KES模塊進行突發錯誤譯碼。

3 譯碼器架構與仿真結果

3.1 BD-RCMA算法的硬件實現

由于BD-RCMA與RCMA算法具有相似性,因此可以在RCMA的硬件實現基礎上增加突發錯誤檢測模塊(burst detection module,BD)來追蹤突發錯誤的位置信息。BD模塊的電路結構如圖4所示。

圖4 BD模塊的電路結構

本文BD-RCMA算法可以與校驗子計算(SC)模塊同時工作,而后續的校驗子更新(SU)、關鍵方程求解(KES)、錢搜索與福尼算法(CSFA)等模塊則是采用BCHDD-LCC譯碼器的串行流水線結構。將BD-RCMA模塊應用在BCHDD-LCC譯碼器架構中,得到如圖5所示的BD-BCHDD-LCC譯碼器,采用該譯碼器對RS(255,239)碼進行譯碼,在η=3條件下采用Verilog HDL語言進行建模,并采用SMIC 0.13 μm工藝下的Design Compiler進行綜合,得到該譯碼器的總面積為0.49 mm2(47 050個異或門),最大頻率為143 MHz,由此計算得到該譯碼器的吞吐率為1.14 Gbit/s。

圖5 BD-BCHDD-LCC譯碼器流水線架構

3.2 仿真結果

混合信道模型由隨機噪聲方差、突發噪聲方差、突發脈沖的泊松到達率與突發錯誤包含的子碼數這4個參數唯一確定。

(a)L=65 bit

(b)L=71 bit圖6 5種譯碼算法對RS(255,239)碼的仿真結果

在上述混合信道模型下,設置信道總信噪比為5～9 dB,設置突發噪聲方差為10倍隨機噪聲方差,突發脈沖的泊松到達率可由泊松分布公式唯一確定。仿真實驗分析表明,對于RS(255,239)碼,當突發錯誤包含的子碼的數量大于RS碼的糾錯半徑64時,RiBM算法與RiBC算法的譯碼性能開始產生較大差異。因此,在64到RiBC算法的譯碼數量極限之內選取L=65與L=71進行仿真分析,計算得到噪聲占比參數ψ大于突發信道閾值,仿真信道狀態為突發錯誤信道。每組環境下設置10 000次差異信息作為數據輸入,經仿真實驗得到誤幀率與信噪比的關系如圖6所示。由圖6可以看出,當信道信噪比一定時,BD-BCHDD-LCC譯碼器的譯碼性能要好于原始BCHDD-LCC譯碼器以及傳統的針對隨機錯誤的RS碼譯碼器。當突發錯誤包含的子碼數增加時,采用BD-RCMA算法的譯碼性能要更好,這是因為突發錯誤所包含的子碼數越多,則BD-RCMA算法根據電平信息提取突發錯誤位置的效果就越好,而原始BCHDD-LCC算法對于突發錯誤位置的判斷越不準確,誤碼率也就越高。

4 結 語

論文提出了一種結合隨機錯誤信道與突發錯誤信道的新型突發錯誤信道,基于該信道中所傳輸的子碼的電平特性提出了基于突發錯誤檢測的重數分配算法——BD-RCMA,采用該算法可以在獲取信息可靠度的同時精確地定位突發錯誤的位置。對該算法采用硬件電路實現并應用在BCHDD-LCC譯碼器架構中,仿真結果表明,采用BD-RCMA算法的譯碼器可顯著提高該譯碼器糾正突發錯誤的性能。

[1] REED G, SOLOMON I. Polynomial codes over certain finite fields [J]. Society for Industrial and Applied Mathematics, 1960, 8(2): 300-304.

[2] SARWATE D V, SHANBHAG N R. High-speed architectures for Reed-Solomon decoders [J]. Very Large Scale Integration Systems IEEE Transactions on, 2001, 9(5): 641-655.

[3] LI X, ZHANG W, LIU Y. Efficient architecture for algebraic soft-decision decoding of Reed-Solomon codes [J]. Communications IET, 2014, 9(1): 10-16.

[4] BELLOADO J, KAVCIC A. A low-complexity method for chase-type decoding of Reed-Solomon codes [C]∥IEEE International Symposium on Information Theory. Piscataway, NJ, USA: IEEE, 2006: 2037-2041.

[5] 白婷婷. 高速通信系統中RS編解碼的應用 [J]. 電子測試, 2015(23): 57-59. BAI Tingting. Application of RS code in high speed communication system [J]. Electronic Test, 2015(23): 57-59.

[6] YIN L, LU J, LETAIEF K B, et al. Burst-error-correcting algorithm for Reed-Solomon codes [J]. Electronics Letters, 2001, 37(11): 695-697.

[7] WU Yingquan. Novel burst error correction algorithms for Reed-Solomon codes [J]. IEEE Transactions on Information Theory, 2012, 58(2): 519-529.

[8] 季文潔. 可重構的環境自適應RS碼軟判決譯碼器設計 [D]. 天津: 天津大學, 2015: 47-53.

[9] WU Yingquan. New scalable decoder architectures for Reed-Solomon codes [J]. IEEE Transactions on Communications, 2015, 63(8): 2741-2761.

[10]張為, 潘博陽, 王皓. 一種基于LCC算法的新型RS碼譯碼器 [J]. 北京理工大學學報, 2013, 33(3): 276-279. ZHANG Wei, PAN Boyang, WANG Hao. A novel RS decoder based on LCC algorithm [J]. Transactions of Beijing Institute of Technology, 2013, 33(3): 276-279.

[11]WANG Lingyu, ZHANG Wei, WANG Yang, et al. Multiple channel error-correction algorithms for LCC decoding of Reed-Solomon codes and its high-speed architecture design [J]. IET Communications, 2017, 11(9): 1407-1415.

[12]HAN Gang, LU Jia, WANG Junhui, et al. MIM: A new class of hybrid channel error model [C]∥IEEE Third International Conference on Information Science and Technology. Piscataway, NJ, USA: IEEE, 2013: 1182-1185.

[13]BERMAN T, FREEDMAN J. Non-interleaved Reed-Solomon coding over a bursty channel [C]∥Military Communications Conference. Piscataway, NJ, USA: IEEE, 1992(2): 580-583.

[14]FOSSORIER M. Gaussian elimination decoding of error correcting Reed-Solomon codes in steps and complexity [J]. IEEE Communications Letters, 2015, 19(7): 1101-1104.

[15]PENG Xingru. Reduced-complexity multiplicity assignment algorithm and architecture for low-complexity chase decoder of Reed-Solomon codes [J]. IEEE Communications Letters, 2015, 19(11): 1-4.