新型串行融合Reed-Solomon碼譯碼器設(shè)計

安翔宇,梁煜,張為

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

里德-所羅門(Reed-Solomon,RS)碼[1]是一種重要的差錯控制碼,因其糾錯能力強(qiáng)、構(gòu)造簡單等,廣泛應(yīng)用于深空探測[2-3]、無線通信[4-5]、數(shù)據(jù)存儲[6]等諸多領(lǐng)域,一直是學(xué)術(shù)界和產(chǎn)業(yè)界研究的重點與熱點。RS碼譯碼算法主要包括硬判決譯碼[7-10](HDD)和代數(shù)軟判決譯碼[11-14](ASD)兩大類。

目前,典型的HDD算法是在伯利坎普-梅西(BM)算法[2]基礎(chǔ)上發(fā)展起來的改進(jìn)的無逆伯利坎普-梅西(RiBM)算法[9]。與HDD算法相比,ASD算法充分運用信道軟信息,具有更加優(yōu)異的糾錯性能。在現(xiàn)有的ASD算法中,低復(fù)雜度蔡斯(LCC)[11-12]算法是具有最低計算復(fù)雜度,硬件實現(xiàn)最為簡單的算法。為了進(jìn)一步提升LCC算法的速度、減小硬件實現(xiàn)面積,García-Herrero等提出了一種基于硬判決的軟判決譯碼(HDD-LCC)算法[15-16],用HDD譯碼流程取代傳統(tǒng)LCC算法中復(fù)雜的插值運算,通過求解測試向量并分別譯碼的思路提升糾錯能力。

圖1 流水線結(jié)構(gòu)的融合RS碼譯碼器架構(gòu)

上述譯碼算法在高斯白噪聲信道(AWGN)中表現(xiàn)出優(yōu)異的性能。然而實際中的信道更接近于突發(fā)錯誤信道(Bursty),由于脈沖的干擾,時常出現(xiàn)碼字連續(xù)出錯的現(xiàn)象。連續(xù)突發(fā)錯誤很容易超出傳統(tǒng)譯碼算法的糾錯能力。針對這種特別出錯形式,需要采用特殊的譯碼處理方式來提升譯碼性能。Wu等提出的擦除(BC)算法成為突發(fā)錯誤譯碼算法研究的基礎(chǔ)[17],文獻(xiàn)[18]提出基于該算法的改進(jìn)無逆擦除(RiBC)算法。這類算法可以同時糾正β個隨機(jī)錯誤和長度為f(f<2t-2β-1,t為RS碼糾錯能力)的單段突發(fā)錯誤,通過假設(shè)突發(fā)錯誤位置并迭代求解的方式實現(xiàn)譯碼。為適應(yīng)不同信道的譯碼需求,胡巖等提出了一種結(jié)合隨機(jī)錯誤譯碼與突發(fā)錯誤譯碼的RiBM-RiBC融合譯碼算法[19]。為進(jìn)一步提升譯碼性能,Wang等將修正的RiBC算法(riBC)與軟判決HDD-LCC算法結(jié)合,提出了一種針對突發(fā)錯誤的融合軟判決譯碼算法BCHDD-LCC,并設(shè)計了一種流水線結(jié)構(gòu)的融合RS碼譯碼器,在有無突發(fā)錯誤時分別采用BCHDD-LCC算法及HDD-LCC算法譯碼[20-21]。此類融合譯碼器在譯碼隨機(jī)錯誤與單段突發(fā)錯誤時均具有優(yōu)異的譯碼性能,進(jìn)一步拓寬了RS碼譯碼器的應(yīng)用范圍,為自適應(yīng)信道環(huán)境的RS碼譯碼器設(shè)計提供了思路。

流水線結(jié)構(gòu)的譯碼器每級延遲是固定的,其中存在大量的空閑等待時間,影響譯碼器的譯碼效率、降低硬件利用率,文獻(xiàn)[22-25]中對此問題進(jìn)行分析并提出了部分改進(jìn)方案。在對流水線結(jié)構(gòu)融合RS碼譯碼器進(jìn)行時序分析時,發(fā)現(xiàn)空閑等待時間的問題同樣存在并值得優(yōu)化。針對此,本文設(shè)計了一種同時適用于隨機(jī)錯誤與單段突發(fā)錯誤譯碼的mSPCF模塊,并提出了一種新型串行融合RS碼譯碼器。實驗結(jié)果表明,與流水線結(jié)構(gòu)的融合譯碼器相比,本文提出的譯碼器具有更低的譯碼延時和更高的吞吐率,實際應(yīng)用更具優(yōu)勢。

1 流水線結(jié)構(gòu)融合譯碼器時序分析

流水線結(jié)構(gòu)融合RS碼譯碼器架構(gòu)如圖1所示。首先通過重數(shù)分配模塊(MA)根據(jù)突發(fā)錯誤預(yù)判斷機(jī)制[21,26]獲取碼字錯誤信息、碼字η個最不可靠位置并得到2η個測試向量,該模塊由軟件實現(xiàn)。再由校驗子計算(SC)模塊得到第一個測試向量的校驗子,其余校驗子由校驗子更新(SU)模塊依次更新得到。關(guān)鍵方程求解(KES)模塊根據(jù)錯誤信息選擇riBC或RiBM算法,得到當(dāng)前測試向量的錯誤值及錯誤位置多項式。多項式選擇(PS)模塊判斷當(dāng)前錯誤多項式能否譯碼成功,如果可以,則無需執(zhí)行后續(xù)測試向量。最終,錢搜索和福尼算法模塊(CSFA)根據(jù)錯誤多項式求得錯誤圖樣并完成譯碼。

流水線結(jié)構(gòu)融合RS碼譯碼器的時序關(guān)系如圖2所示。SU、riBC&RiBM、PS這3個模塊(簡稱SKP)處于同一級流水線階段中,該譯碼器是由SC、SKP、CSFA模塊組成的3級流水線結(jié)構(gòu)。對于流水線結(jié)構(gòu),每級流水線階段都是固定的,只有SC、SKP、CSFA模塊都計算完成才能進(jìn)入下一階段的計算。

(a)總體時序關(guān)系

(b)riBC時序關(guān)系圖2 流水線結(jié)構(gòu)融合RS碼譯碼器時序關(guān)系圖

對于(n,k)RS碼,其糾錯能力t=(n-k)/2。SC、CSFA模塊的譯碼延遲為n,SKP模塊的譯碼延時根據(jù)碼字情況變化。如果SKP模塊譯碼時間小于n,則SKP必須經(jīng)過一定的等待時間才能進(jìn)行下一階段的計算。

由于PS模塊具有判斷錯誤多項式并提前中斷的功能,SKP只需執(zhí)行q(1≤q≤2η)個測試向量。SU模塊與PS模塊的計算時間分別為2t、n/2t。根據(jù)MA模塊得到的錯誤信息,riBC&RiBM模塊將選擇不同關(guān)鍵方程求解算法:譯碼隨機(jī)錯誤時,采用RiBM求解算法,計算時間為2t;譯碼單段突發(fā)錯誤時,采用riBC求解算法,計算時間與突發(fā)錯誤位置測試數(shù)L密切相關(guān),如圖2b所示。特殊的,融合譯碼器沒有譯碼多段突發(fā)錯誤的能力,在錯誤信息判斷后譯碼器直接輸出,以下不予討論。

用TSKP_random、TSKP_burst分別代表譯碼隨機(jī)錯誤、單段突發(fā)錯誤時的SKP計算時間,假設(shè)此時執(zhí)行測試向量數(shù)為q、突發(fā)錯誤位置測試數(shù)為L,tlarger為2t、n/2t中的較大值,則SKP計算時間可分別表示為

TSKP_random=2t+qtlarger

(1)

(2)

為了更直觀地分析SKP譯碼時間,對(255,239)RS碼譯碼時的q、L進(jìn)行概率分布測試。隨機(jī)錯誤由高斯信道產(chǎn)生,單段突發(fā)錯誤由基于馬爾可夫鏈的突發(fā)錯誤信道模型[20]產(chǎn)生。

圖3是在η=3、信噪比(SNR)為6.2 dB的條件下,隨機(jī)錯誤譯碼的執(zhí)行測試向量數(shù)q的概率分布,譯碼器有90%以上概率只執(zhí)行第1個測試向量,根據(jù)式(1),此時SKP僅需要32個時鐘周期。即使在譯碼器需執(zhí)行所有8個測試向量的情況下,SKP也只需要144個時鐘周期,均遠(yuǎn)小于SC、CSFA執(zhí)行用的255個時鐘周期。因此,在譯碼隨機(jī)錯誤時第2級流水階段SKP中存在大量空閑等待時間。

圖3 隨機(jī)錯誤譯碼執(zhí)行測試向量數(shù)的概率分布

在η=3、β=2,信噪比為6.2 dB的條件下,進(jìn)行單段突發(fā)錯誤譯碼的概率分布測試,結(jié)果如圖4所示。由圖4a所示,所有的單段突發(fā)錯誤均成功實現(xiàn)譯碼,且執(zhí)行測試向量數(shù)q的平均值為1.015。突發(fā)錯誤位置測試數(shù)L的概率分布如圖4b所示,L集中分布在4～7之間,平均值為5.499。根據(jù)式(2)可知,粗略計算SKP的平均譯碼時間為(13×5.499+11)×1.015+16=99.724,此值仍均遠(yuǎn)小于SC、CSFA執(zhí)行用的255個時鐘周期。

(a)執(zhí)行測試向量數(shù)的概率分布

(b)riBC模塊突發(fā)錯誤位置測試數(shù)的概率分布圖4 單段突發(fā)錯誤譯碼的概率分布情況

2 新型串行融合RS碼譯碼器

流水線結(jié)構(gòu)的融合譯碼器在譯碼隨機(jī)錯誤及單段突發(fā)錯誤時,第2級流水階段SKP中均存在大量空閑等待時間,非常影響譯碼效率。調(diào)整譯碼過程時序關(guān)系,設(shè)計新型串行融合RS碼譯碼器將能有效消除等待時間,大大減少譯碼器的譯碼延時。

文獻(xiàn)[25]提出了一種串行高效LCC譯碼器,并設(shè)計了一個并行的校驗子計算-多項式選擇-錢搜索-福尼算法(SPCF)模塊,在不同時間分別實現(xiàn)SC、PS、CS和FA模塊功能,大幅提升了傳統(tǒng)LCC譯碼器的譯碼速度及吞吐率。該譯碼器只適用于隨機(jī)錯誤譯碼,無法適應(yīng)復(fù)雜的信道環(huán)境。因此,在原始SPCF模塊的基礎(chǔ)上,提出了一個能適用于融合譯碼器的修正的SPCF模塊(mSPCF),并設(shè)計了一種新型串行融合RS碼譯碼器。與原始SPCF模塊相比,所提出的mSPCF模塊能用于糾正隨機(jī)錯誤及單段突發(fā)錯誤,并具有更低的譯碼延時。

圖5 mSPCF模塊的電路結(jié)構(gòu)

根據(jù)譯碼各模塊功能及運算過程,PS模塊判斷當(dāng)前錯誤多項式能否譯碼成功,此功能通過檢查錯誤位置多項式的階數(shù)與根的個數(shù)是否相等實現(xiàn)。CS模塊將所有碼元位置依次代入錯誤位置多項式并檢查值是否為0,來搜索錯誤位置多項式的全部根,得到錯誤位置。PS和CS模塊針對錯誤位置多項式根的運算與判斷,無需重復(fù)進(jìn)行。所提mSPCF模塊將原始SPCF模塊中分步進(jìn)行PS、CS的過程修正為PS、CS模塊同時進(jìn)行。

SC模塊計算2t個校驗子Si。令r0～rn-1為碼字的全部碼元,α0～αn-1為碼元的全部位置,α為(n,k)RS碼本原元。將SC模塊設(shè)計為p度并行,則其計算公式可以整理為

Si=

(3)

PS/CS模塊搜索到錯誤位置多項式的全部根,同時判斷該錯誤多項式能否譯碼成功。如果能成功,則由FA模塊求解錯誤值。令關(guān)鍵方程求解模塊得到的錯誤位置多項式σ(x)的系數(shù)為σ0～σe,錯誤值多項式ω(x)的系數(shù)為ω0～ωe-1,σodd(x)是σ(x)的奇數(shù)項,E(x)是最終的錯誤值。PS/CS、FA模塊的計算式為

σ(αi)=σ0+σ1αi+…+σe(αi)e,0≤i≤n-1

(4)

0≤i≤n-1

(5)

式中:在譯碼隨機(jī)錯誤與單段突發(fā)錯誤時,e的值分別為t與2t-β。

可以看出,式(3)～(5)都在求解特定多項式的根,計算過程的電路可以較好地兼容?；诖?設(shè)計mSPCF模塊電路結(jié)構(gòu)(見圖5)。mSPCF模塊最下面一行的選擇器在不同時間分別選擇系數(shù)r0～rn-1、σ0～σe、ω0～ωe-1來執(zhí)行SC、PS/CS、FA模塊功能。mSPCF模塊的每一個基本單元(實線框)計算多項式的一項。為了能夠同時糾正隨機(jī)錯誤及單段突發(fā)錯誤,mSPCF模塊的基本單元共2t(2t-β)個。

在進(jìn)行式(4)、式(5)的PS/CS或FA模塊運算時,需要對全部n個碼元位置進(jìn)行運算,共計n個多項式。如圖5所示,mSPCF模塊共2t行,每行計算一個多項式值,計算完所有多項式共需n/2t個計算周期。為方便FA模塊的求解,σodd(αi)與σeven(αi)分開計算,并由求逆器求解σodd(αi)的倒數(shù)。如果碼字錯誤為單段突發(fā)錯誤,每行所有2t-2β個基本單元均參與運算。如果碼字錯誤為隨機(jī)錯誤,則只有虛線框內(nèi)的2t個基本單元參與運算。

此外,在高斯信道環(huán)境下,隨著信噪比增大,會出現(xiàn)越來越多的無錯誤情況,此時2t個校驗子全為0。對無錯誤的情況繼續(xù)進(jìn)行錯誤多項式的求解過程,將會造成不必要的時間及資源消耗。因此,在mSPCF模塊新增了一個校驗子判斷環(huán)節(jié)。如果校驗子計算后結(jié)果全為0,說明碼字無錯誤,直接將全部輸入碼字輸出。否則,仍需依次通過SU、riBC& RiBM、PS、CS、FA過程求解錯誤圖樣最終完成譯碼。此判斷只需增加極少的硬件資源消耗,卻在信道環(huán)境較好的情況下大幅降低譯碼器延時。

基于所設(shè)計的mSPCF模塊,提出了一種新型串行融合RS碼譯碼器,架構(gòu)如圖6所示。mSPCF模塊在不同時間分別實現(xiàn)SC、PS/CS、FA模塊功能,因此串行融合譯碼器只需MA、mSPCF、SU、riBC&RiBM模塊即可實現(xiàn)譯碼。

圖6 新型串行融合RS碼譯碼器架構(gòu)

3 新型串行融合譯碼器性能分析

3.1 延時分析

圖7 新型串行融合RS碼譯碼器時序關(guān)系

在譯碼碼字無錯誤時,譯碼器只需進(jìn)行SC模塊并以2t度并行輸出,此時譯碼器譯碼延時為

(6)

在碼字錯誤為隨機(jī)錯誤時,SKP計算時間同式(1),此時譯碼器譯碼延時為

(7)

在碼字錯誤為單段突發(fā)錯誤時,SKP計算時間同式(2),此時譯碼器譯碼延時Tq,burst為

Tq,brust=

(8)

該譯碼器在高斯信道及突發(fā)錯誤信道(考慮所有碼字均含單段突發(fā)錯誤)的平均延時計算式為

(9)

(10)

式中:pq,random、pq,burst分別表示譯碼隨機(jī)錯誤及單段突發(fā)錯誤時執(zhí)行q個測試向量的概率,pr表示碼字無錯誤的概率,概率大小與信道環(huán)境密切相關(guān)。

圖8 不同譯碼器的延時對比

圖8給出在RS(255,239)、η=3、β=2條件下串行融合譯碼器的譯碼延時,并與基于USC的LCC譯碼器[16]、流水線結(jié)構(gòu)融合譯碼器[20]、串行ET-LCC譯碼器[27]、基于SPCF的串行LCC譯碼器[25]對比。其中,實線是高斯信道下的譯碼延時情況,虛線是突發(fā)錯誤信道且每個碼字均含單段突發(fā)錯誤時的譯碼延時情況。可以看出,在高斯信道下,串行融合譯碼器具有最低的譯碼延時,且隨著信噪比的增大不斷下降。在信噪比6.2～7.4 dB范圍內(nèi)時,所提譯碼器的平均延時相比文獻(xiàn)[16]、[20]、[27]、[35]中譯碼器可分別減少75.38%、73.45%、63.01%、29.68%。此外,在突發(fā)錯誤信道下,信噪比變化影響的是碼字含單段突發(fā)錯誤的概率。當(dāng)僅對單段突發(fā)錯誤進(jìn)行測試時,其譯碼延時基本不隨信道信噪比變化,且比流水線結(jié)構(gòu)譯碼器的平均延時減少了45.65%。

3.2 硬件實現(xiàn)結(jié)果

本文提出的新型串行融合譯碼器在RS(255,239)、η=3、β=2的條件下實現(xiàn)了Verilog HDL建模,并在SMIC 0.13μm CMOS工藝下采用Design Compiler工具實現(xiàn)了邏輯綜合?？紤]到同時具有糾正隨機(jī)錯誤與單段突發(fā)錯誤的能力,表1給出了流水線結(jié)構(gòu)融合譯碼器及所提串行架構(gòu)融合譯碼器的綜合結(jié)果對比(綜合工具及工藝保持一致)。

新型串行融合RS碼譯碼器的面積為0.447 mm2,需要37 620個二進(jìn)制異或門,相比流水線結(jié)構(gòu)減少約9.4%的硬件資源消耗。串行融合譯碼器的最大時鐘頻率為187 MHz,相比流水線結(jié)構(gòu)有所下降。信噪比在6.2～7.4 dB范圍內(nèi)的高斯信道下,串行融合譯碼器平均延時約為67.7,吞吐率達(dá)5 634 Mb/s,相比流水線結(jié)構(gòu)增加約236.76%。在僅含單段突發(fā)錯誤的突發(fā)錯誤信道下,串行融合譯碼器的平均延時約為138.6,吞吐率達(dá)2 752 Mb/s,相比流水線結(jié)構(gòu)增加約64.49%。

表1 RS(255,239)融合譯碼器實現(xiàn)結(jié)果

4 結(jié) 論

本文分析流水線結(jié)構(gòu)融合譯碼器的時序關(guān)系,發(fā)現(xiàn)其第2級流水階段存在大量空閑等待時間。為消除該等待時間、提升譯碼效率,本文提出了一種新型串行融合RS碼譯碼器,并設(shè)計了修正的SPCF模塊。本文進(jìn)行了串行融合譯碼器的譯碼延時分析,與其他多種譯碼器對比,所提譯碼器均取得了一定的延時優(yōu)勢。串行融合譯碼器通過Design Compiler工具在SMIC 0.13μm CMOS工藝下實現(xiàn),與流水線結(jié)構(gòu)相比,所提串行結(jié)構(gòu)可減少約9.4%的硬件資源消耗,在高斯信道及突發(fā)錯誤信道下譯碼時,吞吐率可分別提升236.76%和64.49%。綜上,本文所提具有融合糾錯能力的串行融合譯碼器具有更為優(yōu)異的性能。