基于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.