基于RS編解碼技術的Flash控制器SoC設計研究

王 暉

泰州機電高等職業技術學校，江蘇泰州 225300

0 引言

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

1 RS編碼的算法簡介

1.1 RS編碼算法

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

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

采用一致性的方式對位數目L-k=2w進行檢驗；

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

jk-1,jk-2，…，j1，j0表示的是寬度為m bit的k個數據，如果m bit的k個數據經過有限域GF（2m）進行編碼，其傳輸的碼字（cn-1,cn-2,…,c1,c0），采用多項式表示的方法表示數據為：

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

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

式中：α是G（z）的根,因為C（z）為G（z）的倍式，得到C（z）的表達式為：

對C（z）進行計算，將數據多項式向右移動k位可以得到 zn-kJ（z）

設：D（z）為商式；E（z）為余式

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

式中：G（z）是2w次多項式、E（z）的次數n-k。

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

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為發送端的碼字多項式；

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

E（z）=en-1zn-1+en-2zn-2+…+e1z+e0是傳輸中產生錯誤的碼字多項式；

通過 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）為伴隨式多項式，S（z）的取值與傳輸過程中產生錯誤值E（z）相關聯，當產生錯誤值E（z）=0時，伴隨式多項式S（z）=0，這種情況下表示FLAH控制器無錯誤。在數據傳輸過程中，因為錯誤E（z）的取值并不能直接獲得，所以通過RS解碼能夠為接收端R（z）夠確定數據傳輸過程中產生錯誤E（z）值。如果數據傳輸過程中產生錯誤E（z）位置w個錯誤，即在設定范圍內，其為可糾正性錯誤。如果數據傳輸過程中產生錯誤E（z）位置w個錯誤，即不在設定范圍內，其為不可糾正性錯誤。正因為在數據傳輸過程中E（z）錯誤具有未知性，所以通過RS解碼器采用伴隨式多項式S（z）的方式進行計算，可得到E（z）的值。RS解碼器的伴隨式多項式 S（z）=s0+s1z+…+s2w-1z2w-1。

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

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

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

2 RS編解碼的硬件實現

2.1 RS編碼

編碼器是將數據（jk-1,jk-2,…,j1,j0）加上余式碼字（enk-1,en-k-2,…,e1,e0）得出發送碼字（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）得出發送通過乘法電路獲得，如圖1所示，數據碼字從最高位寄存器移入，相當于方程式zn-kJ（z）=D（z）G（z）+E（z）將數據多項式向右移位2w位（2w=n-k）。

圖1 RS編碼乘法電路圖

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

2.2 RS解碼

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

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

RS解碼器的設計流程圖如下：

RS解碼器設計流程圖

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

3 結論

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

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

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

[3]劉海清.基于隨機掩碼的AES算法抗DPA攻擊硬件實現[J].國防科學技術大學，2008.