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

安翔宇,梁煜,張為

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

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

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

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

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

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

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

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

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

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

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

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

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

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

TSKP_random=2t+qtlarger

(1)

(2)

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

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

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

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

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

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

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

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

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

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

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

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

Si=

(3)

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

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

(4)

0≤i≤n-1

(5)

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

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

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

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

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

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

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

3.1 延時(shí)分析

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

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

(6)

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

(7)

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

Tq,brust=

(8)

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

(9)

(10)

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

圖8 不同譯碼器的延時(shí)對(duì)比

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

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

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

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

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

4 結(jié) 論

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