安翔宇,梁煜,張為

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

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

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

圖1 流水線結構的融合RS碼譯碼器架構

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

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

1 流水線結構融合譯碼器時序分析

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

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

(a)總體時序關系

(b)riBC時序關系圖2 流水線結構融合RS碼譯碼器時序關系圖

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

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

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

TSKP_random=2t+qtlarger

(1)

(2)

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

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

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

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

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

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

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

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

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

圖5 mSPCF模塊的電路結構

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

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

Si=

(3)

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

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

(4)

0≤i≤n-1

(5)

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

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

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

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

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

圖6 新型串行融合RS碼譯碼器架構

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

3.1 延時分析

圖7 新型串行融合RS碼譯碼器時序關系

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

(6)

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

(7)

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

Tq,brust=

(8)

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

(9)

(10)

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

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

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

3.2 硬件實現結果

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

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

表1 RS(255,239)融合譯碼器實現結果

4 結 論

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