王 暉

泰州機(jī)電高等職業(yè)技術(shù)學(xué)校，江蘇泰州 225300

0 引言

隨著技術(shù)的進(jìn)步在SoC設(shè)計中，F(xiàn)lash儲存器越來越小，但是儲存器的密度卻不斷增加，為了對FLASH的存儲能力及其性能的穩(wěn)定性進(jìn)行加強(qiáng)，采用糾錯碼的方式對FLAH存儲系統(tǒng)進(jìn)行編碼，能夠起到降低FLASH失誤的幾率?；赗S（reed solomon code；即里德-索羅門碼）編解碼技術(shù)對FLASH存儲的數(shù)據(jù)進(jìn)行編碼和解碼，并采用流水線結(jié)構(gòu)、改進(jìn)新型riBM（reformulated inversionless Berlekamp-Massey）即伯利坎普迭代算法的RS解碼，通過這種方法能夠提高RS解碼的速度和可實(shí)現(xiàn)能力，對于解決Flash控制器SoC設(shè)計中的Flash存儲器部分?jǐn)?shù)據(jù)讀寫失效的問題有很好的幫助。

1 RS編碼的算法簡介

1.1 RS編碼算法

RS編碼為多元BCH編碼，屬于線性的循環(huán)碼，將其定義于GF（galois field；伽羅華域）上,能夠糾正RS編碼的w個錯誤，對RS編碼進(jìn)行參數(shù)設(shè)置：

RS編碼長度L=q-1 q=2n n為自然數(shù)；

采用一致性的方式對位數(shù)目L-k=2w進(jìn)行檢驗(yàn)；

RS編碼中的最小碼距jmin= 2w+1；

jk-1,jk-2，…，j1，j0表示的是寬度為m bit的k個數(shù)據(jù)，如果m bit的k個數(shù)據(jù)經(jīng)過有限域GF（2m）進(jìn)行編碼，其傳輸?shù)拇a字（cn-1,cn-2,…,c1,c0），采用多項(xiàng)式表示的方法表示數(shù)據(jù)為：

多項(xiàng)式 ：J（z）=jk-1zk-1+jk-2zk-2+,…,+j1z+j0 ；

碼字多項(xiàng) ：C（z）=ck-1zk-1+ck-2zk-2+,…,+c1z+c0；

式中：α是G（z）的根,因?yàn)镃（z）為G（z）的倍式，得到C（z）的表達(dá)式為：

對C（z）進(jìn)行計算，將數(shù)據(jù)多項(xiàng)式向右移動k位可以得到 zn-kJ（z）

設(shè)：D（z）為商式；E（z）為余式

滿足方程式 ：zn-kJ（z）=D（z）G（z）+E（z）

式中：G（z）是2w次多項(xiàng)式、E（z）的次數(shù)n-k。

將方程式 zn-kJ（z）=D（z）G（z）+E（z）進(jìn)行改寫 ，得出 ∶

C（z）=D（z）G（z）=zn-kJ（z）-E（z）

對于GF域加減形式相同得出：

（cn-1,cn-2,…,c1,c0）=（jk-1,jk-2,…,j1,j0,en-k-1,en-k-2,…,e1,e0）。

1.2 RS解碼算法

RS解碼算法公式：R（z）=C（z）+E（z）

C（z）=ck-1zk-1+ck-2zk-2+,…,+c1z+c0為發(fā)送端的碼字多項(xiàng)式；

R（z）=C（z）+E（z）= rn-1zn-1+rn-2zn-2+…+r1z+r0為接收端的碼字多項(xiàng)式；

E（z）=en-1zn-1+en-2zn-2+…+e1z+e0是傳輸中產(chǎn)生錯誤的碼字多項(xiàng)式；

通過 C（z）=D（z）G（z）=zn-kJ（z）-E（z） 編碼過程得知 ：

R（z）=D（z）G（z）+S（z）=C（z）+S（z）

S（z）為伴隨式多項(xiàng)式，S（z）的取值與傳輸過程中產(chǎn)生錯誤值E（z）相關(guān)聯(lián)，當(dāng)產(chǎn)生錯誤值E（z）=0時，伴隨式多項(xiàng)式S（z）=0，這種情況下表示FLAH控制器無錯誤。在數(shù)據(jù)傳輸過程中，因?yàn)殄e誤E（z）的取值并不能直接獲得，所以通過RS解碼能夠?yàn)榻邮斩薘（z）夠確定數(shù)據(jù)傳輸過程中產(chǎn)生錯誤E（z）值。如果數(shù)據(jù)傳輸過程中產(chǎn)生錯誤E（z）位置w個錯誤，即在設(shè)定范圍內(nèi)，其為可糾正性錯誤。如果數(shù)據(jù)傳輸過程中產(chǎn)生錯誤E（z）位置w個錯誤，即不在設(shè)定范圍內(nèi)，其為不可糾正性錯誤。正因?yàn)樵跀?shù)據(jù)傳輸過程中E（z）錯誤具有未知性，所以通過RS解碼器采用伴隨式多項(xiàng)式S（z）的方式進(jìn)行計算，可得到E（z）的值。RS解碼器的伴隨式多項(xiàng)式 S（z）=s0+s1z+…+s2w-1z2w-1。

錯誤位置多項(xiàng)式：Λ(z)=1+λ1z+…+λeze

錯誤值多項(xiàng)式：Ω (z)=ω0+ω1z+…+ωe-1ze-1

錯誤位置多項(xiàng)式、錯誤值多項(xiàng)式與伴隨多項(xiàng)式滿方程Λ（z）S（z）=Ω（z）modz2w。采用riBM迭代算法求解方程,當(dāng)錯誤數(shù)e小于w的前提下，能夠找到Λ（z）和Ω（z）。RS解碼就是求解關(guān)鍵方程Ω (z)=ω0+ω1z+…+ωe-1ze-1。

2 RS編解碼的硬件實(shí)現(xiàn)

2.1 RS編碼

編碼器是將數(shù)據(jù)（jk-1,jk-2,…,j1,j0）加上余式碼字（enk-1,en-k-2,…,e1,e0）得出發(fā)送碼字（cn-1,cn-2,…,c1,c0）=（jk-1,jk-2,…,j1,j0,en-k-1,en-k-2,…,e1,e0）。 通 過 方 程 式zn-kJ（z）=D（z）G（z）+E（z）與方程式 C（z）=D（z）G（z）=zn-kJ（z）-E（z）得出發(fā)送通過乘法電路獲得，如圖1所示，數(shù)據(jù)碼字從最高位寄存器移入，相當(dāng)于方程式zn-kJ（z）=D（z）G（z）+E（z）將數(shù)據(jù)多項(xiàng)式向右移位2w位（2w=n-k）。

圖1 RS編碼乘法電路圖

當(dāng)開關(guān)置于A端時，gate接通，jk-1,jk-2,…,j1,j0依次輸入編碼乘法電路，當(dāng)開關(guān)置于B端時，gate關(guān)閉，en-k-1,en-k-2,…,e1,e0依次輸出。

2.2 RS解碼

RS解碼相對于RS編碼較為復(fù)雜，RS解碼的算法為流水式計算方法，其流程可以分為四個步驟：

1）接收碼字并進(jìn)行伴隨式計算；2）采用riBM即伯利坎普迭代計算法對相關(guān)的方程式進(jìn)行計算；3）采用Ω (z)多項(xiàng)式進(jìn)行計算；4）對于產(chǎn)生錯誤的位置的錯誤值進(jìn)行糾正計算。

RS解碼器的設(shè)計流程圖如下：

RS解碼器設(shè)計流程圖

首先通過輸入進(jìn)入伴隨式計算環(huán)節(jié)，再通過riBM迭代計算法進(jìn)行計算，通過找根或者Ω (z)多項(xiàng)式的計算；對FLASH控制器錯誤進(jìn)行糾正，再通過流水線儲存器進(jìn)行輸出調(diào)整，最后輸出。

3 結(jié)論

在SoC系統(tǒng)級芯片設(shè)計中基于RS編解碼技術(shù)的FLASH控制器的編碼和解碼，采用riBM迭代計算法對相關(guān)的方程式進(jìn)行計算，從而不但能夠降低Flash控制器的失效幾率，還可以高RS解碼的速度和可實(shí)現(xiàn)能力，對于提升SoC設(shè)計具有良好的參考價值。

[1]吳斌，等.基于RS編解碼Flash控制器的SoC設(shè)計[J].電子測量技術(shù)，2011(34).

[2]曾德才，等.基于ME算法的RS譯碼器的原理和FPGA實(shí)現(xiàn)[J].科學(xué)技術(shù)與工程，2007(9).

[3]劉海清.基于隨機(jī)掩碼的AES算法抗DPA攻擊硬件實(shí)現(xiàn)[J].國防科學(xué)技術(shù)大學(xué)，2008.