高性能超低延迟BCH译码器电路结构设计

杨宇恒， 刘海洋， 李金海， 原青， 刘建(中国科学院 微电子研究所， 北京 100029)

随着工艺尺寸的不断缩小，集成电路在成品率和可靠性等方面临着诸多问题[1]。对于处理器而言，存储器是重要的组成部分，存储器与处理器的可靠性高度相关，决定了处理器是否能够得到正确的指令或数据。处理器中常用的存储器有静态随机存储器(static random-access memory，SRAM)和闪存等，为了提高存储器的可靠性，采用冗余设计的诊断或纠错方法[2-4]，效率最高的容错设计是纠错码(error correction code, ECC)方案，用于检测和纠正存储器中的错误[5-6]。目前，存储器的ECC方案中最常用的是(bose-chaudhuri-hocquenghem，BCH)码，虽具有于多比特纠错能力[7]，但应用于处理器也存在许多问题[8]。首先，BCH码的纠错能力有限，当存储器中的错误比特数超出BCH码的纠错能力时，译码器无法保证正确的译码输出，处理器可能得到错误指令或数据[9]。另外，由于处理器是根据存储器中的指令运行的，因此，对译码延迟和吞吐率要求较高，否则将影响处理器的执行效率，随着信息位长度的增加，译码过程中需要存储规模较大的元素查找表，将大幅提升处理器的面积成本。

针对处理器中的闪存类型存储器，本文提出了一种具有低译码延迟的适用于处理器的BCH译码器结构，用于提高处理器的可靠性，以独立的有限域运算单元代替了译码算法中的查表结构[10]，缩减了译码器电路面积，此外，通过对译码算法迭代过程的优化，使用逆向错误搜索电路，降低了译码器的延迟。

1 BCH译码算法

假设α是有限域GF(2m)的本源元，则纠错能力为t的BCH码C的生成多项式g(x)是以α、α2、α3、…、α2t为根的最低次多项式：

g(x)=LCM(g1(x),g2(x),…,g2t(x))

(1)

式中：LCM表示若干多项式的最小公倍式。

BCH码C的参数应满足：1)码字长度n=2m-1；2)维度数量k=n-mt；3)最小距离d≥2t+1。

在实际应用中，信息序列的码字长度往往不能满足上述形式，一般通过对信息序列补零的形式，以满足对BCH编码对码字长度的要求，进而进行编码，编码后的数据再删除数据段补充的零比特，形成最终编码后的码字。

BCH码的译码过程可简述如下：假设C的码字为c=(c0,c1,…,cn-1)，其对应的多项式为：

c(x)=c0+c1·x+…+cn-1·xn-1

(2)

同时，假设在数据的读取过程中可能产生的错误为：

e(x)=e0+e1·x+…+en-1·xn-1

(3)

实际的读取过程中的接收序列可表示为：

r(x)=c(x)+e(x)

(4)

对于纠错能力为t的BCH码，其2t个伴随式为：

Si=r(αi), 1≤i≤2t

(5)

式中：αi为有限域GF(2m)的元素，通常以位宽为m、深度为n的查找表的方式实现。

假定接收序列中v(v≤t)个位置出现错误，可定义错误位置多项式为：

(6)

式中σi为有限域GF(2m)的元素，σ0=1。

BCH的译码过程就是根据2t个伴随式Si(1≤i≤2t)求解上述错误位置多项式σ(x)的过程，进而通过σ(x)的根找到错误位置，即σ(x)的所有根表示码字中的错误位置。

图1 BCH译码算法流程Fig.1 The flowchart of BCH decoding process

在图1所示的BCH码译码算法中，错误位置多项式计算是复杂度最高的部分，通常采用Berlekamp-Massey(BM)算法实现。该算法需要对元素αi进行求逆运算(αi)-1=αn-i。通常元素求逆运算可以通过查表的形式实现，在信息序列长度较小的译码器设计中，查找表的规模较小，可以通过简单的地址映射完成元素求逆运算。当信息序列长度较大时，查找表的规模在硬件实现中是难以接收的，例如，对于4 096 bit信息位的BCH码，需要深度8 191的元素查找表。而根据GF(2m)的运算规则αi·αj=αi+j可知，元素求逆计算也可以实时计算生成，但译码延迟将会显著增加，难以适应译码在处理器应用中的低译码延迟的需求。

相对于标准的BM算法，避免求逆的BM算法的译码过程是一个迭代过程，避免有限域的元素求逆运算，能够有效减少迭代过程中的运算量，以及减少电路面积成本，易于硬件实现。避免求逆的BM译码算法的实现步骤为：

初始化：σ0(x)=1，β0(x)=x，θ0=1，L0=0，j=1。

步骤1)：通过式(7)计算Δj，其中Sj为伴随式：

(7)

步骤2)：根据Δj和变量L判断变量δ：

(8)

步骤3)：更新错误位置多项式σj(x)以及中间变量βj(x)为：

σj(x)=θj-1σj-1(x)-Δjxβj-1(x)

(9)

βj(x)=δσj-1(x)+(1-δ)xβj-1(x)

(10)

步骤4)：根据式(11)和式(12)更新中间变量θj和Lj为：

θj=δΔj+(1-δ)θj-1

(11)

Lj=δ(j-Lj-1)+(1-δ)Lj-1

(12)

步骤5)：若j=2t停止；否则置j←j+1，返回步骤1)。

在避免求逆的BM译码算法中，错误位置多项式σ(x)的更新过程是计算复杂度最高的部分，其更新过程如图2所示。

图2 错误位置多项式求解流程Fig.2 Solution process of error location polynomial

在更新σ(x)后，对σ(x)=0进行求解得到v个根，σ(x)可分为：

σ(x)=(1+β1x)(1+β2x)…(1+βvx)

(13)

βk=αjk,k=1,2,…,v

(14)

由于在有限域的运算中α-jk=αn-jk，因此σ(x)=0的根与接收序列r(x)中错误位置之间应满足若σ(αj1)=0，则r(x)中的第n-j1比特为实际的错误位置。即通过对σ(x)=0求解找到的v个根，即为接收序列r(x)中实际产生的v个错误位所对应的位置。

通过上述对译码过程的描述中可以看到，在错误位置搜索阶段，当前参与计算的元素序号与对应的搜索码字序号通过n-j1对称，如果按照标准译码算法进行顺序搜索，译码器的首个有效输出位将延迟约n/2个译码周期，译码数据将逆序输出。以本文的设计为例，根据NAND-FLASH的存储器特点，以扇区为基本的存储单元，每个扇区对应512 bit，则编码的信息位字长为4 096 bit，顺序搜索方式将导致2 048个周期的译码延迟。另外，根据式(6)中的描述，BCH码的纠错能力为t，当错误比特的数量v>t时，译码器将无法纠正码字中的全部错误位，甚至得到错误的译码信息。

为尽量降低译码器的延迟，以满足处理器的应用需求，本文对上述译码算法进行了改进，根据GF(2m)的运算规则α-i=αn-i和αn·α-i=αn-i可知，对错误位置进行逆序搜索，使译码器能够产生正序的译码输出，并且，对比于原始译码算法，译码器能够减少约n/2个周期的译码延迟。

另外，为提高译码器电路的可靠性和数据利用率，本文对信息位中加入了CRC校验。采用分段校验的方式，具有以下2个优点：1)当实际读取的码字中错误位大于t时，BCH译码器无法产生正确译码结果，则可通过CRC校验对译码后数据进行二次校验，确定译码器的输出的正确性；2)码字中的错误位可能随机产生在信息位的任意位置，采用分段CRC校验的方式，能够使处理器分别识别每段数据的正确性，单独读取正确数据段的信息位，提高数据的利用率。

2 BCH译码器电路实现

2.1 译码器电路实现

编码后的数据格式如图3中所示，其中最大纠错能力t设定为9，即最多能够纠正随机分布的9 bit错误。首先，将长度为4 096 bit的信息序列分为4段，每段长度为1 024 bit。然后，对于每段信息序列，分别通过CRC-16校验产生16 bit的CRC校验位，将4段信息比特和CRC校验比特一起组成4 160 bit数据，最后补充3 914 bit，经过BCH编码，得到117 bit BCH校验位后，删除补充的零比特形成最终的编码数据格式。

图3 输入数据编码格式Fig.3 Encoding format of input data

图4为本文提出的BCH译码器的整体电路结构。主要由桶形移位寄存器，伴随式生成器，错误位置多项式生成器，错误位置搜索和CRC-16校验电路以及必要的控制逻辑组成。

图4 译码器整体结构Fig.4 Structure of proposed decoder circuit

译码器输入数据的组织格式与图3中一致，在电路的结构上，为减少译码器的电路面积成本，针对GF(2m)的运算规则，以实时计算αi的方式代替了译码算法中的元素查找表，在图4中对应为寄存器和有限域乘法器组成的累乘结构，而有限域乘法可以通过异或门和与门级联实现，以图3中伴随式生成电路为例，其中包含18条伴随式计算支路，每条支路包括8组累乘单元，共144个累乘单元用于实时计算αi参数表，每个累乘单元的规模仅为37个门电路。而采用查找表的形式则需要8 191×13=106 483个寄存器，相同的累乘结构，也应用于图4中错误位置搜索电路中用于实时计算元素表，因此，本文采用的实时计算αi的电路结构大幅缩减了译码器的电路面积。另外，为提高译码器的吞吐率和较少译码延迟，图4中的桶形移位寄存器也采用了乒乓结构，可将译码器的吞吐率提升一倍，以适应在高速处理器中的应用需求。

译码器的工作时序如图5中所示，共分为3个阶段：1)待译码数据以8 bit为一组向移位寄存器R1中填充，同时，图4中的18条伴随式计算支路同步接收输入数据，并根据式(5)计算各支路对应的伴随式，在一个机器周期内，每条支路同时计算8 bit数据，当全部535 bit数据输入R1后，同时得到18个伴随式S1～S18；2)启动错误位置多项式生成电路，经过23个机器周期后，生成错误位置多项式σ0～σ9；3)启动错误位置搜索和校验电路，同时，桶形移位寄存器持续移位，将R1中数据顺序弹出，并根据σ(αj1)是否为零，对错误位进行纠错。

当搜索过程遍历全部535 bit数据后，译码过程结束，通过图5中对译码器工作时序的描述可以看到，本文提出的译码器结构完成一次译码流程共需要消耗558个机器周期，其中，在错误位置搜索和校验阶段，下一组待译码数据可以向R2中同步填充，即除错误位置多项式的计算阶段需要消耗独立的23个机器周期外，其余译码过程可实现全流水线操作，大幅提高了译码器的吞吐率。

分析图4中桶形移位寄存器的特点与译码器的工作时序可以看到，仅保留一组移位寄存器，译码器也能够保持相同的吞吐率，即在译码器执行错误位置搜索和校验操作时，下一组待译码数可以由R1的底部逐比特向上填充，而原数据则可以同步由R1顶部向上逐比特弹出，同时，译码后的数据由图4中输出端口A同步输出。虽然采用单一移位寄存器的结构能够有效降低译码器的面积与动态功耗，但在处理器的应用中会存在2方面问题：1)为充分保证移位寄存器中数据的正确性，译码器的读/写时钟必须同步，处理器内部总线的效率将会收到限制；2)译码信息必须等待全部码字译码结束后才能得到，例如：错误数量和分段CRC-16的校验结果，由于BCH码的局限性，可能无法完全纠正码字中的错误，导致在处理器在执行应用程序时可能会接收到错误数据，从而导致不可恢复的错误执行结果。

图5 BCH译码工作时序Fig.5 Operation timing of BCH decoder

而使用乒乓结构的桶形移位寄存器一方面能够有效解决读/写时钟的同步问题；另一方面，由于输入码字的数据段采用了分段式CRC-16的组织结构，即使在BCH译码器无法纠正码字中全部错误位的情况下，也能够在处理器读取译码信息后，分别判断4段CRC-16的校验情况，选择4段数据中无错误位的数据，提高译码后数据的利用效率。

分析式(7)～(12)可以看到，根据Δj与Lj的取值，错误位置多项式σ(x)的计算过程可分解为2个独立的更新过程，其电路结构如图6所示。

图6 σ更新结构Fig.6 σ update structure

根据式(9)与式(10)的更新迭代过程，当δ=1时，βj(x)=σj-1(x)，此时，中间变量βj(x)的更新过程可通过寄存器直接赋值的形式实现，即将σj-1(x)寄存器组的数据直接赋值给β(x)寄存器组；当δ=0时，βj(x)=xβj-1(x)，此时，β(x)的更新过程表现为β(x)寄存器组的向上循环移位过程。上述更新过程与图6中的β(x)寄存器组和选通器结构对应，其中，选通器的控制信号为δ。

根据Δj的状态，图6中σ(x)的更新过程可表示为有限域乘法或有限域乘累加的运算，因此，图6中σ(x)寄存器组对应的选通器控制信号为Δj的取值状态，当Δj=0时，选通器控制信号为0，反之，则为1。

在译码器的错误位置搜索阶段，为求σ(x)的所有解，需要遍历8 191个元素表，为适应处理器的设计需求以及FLASH的时序规范，在本文设计的译码器电路中以bit为单位进行读写操作，因此，在图4所示的结构中，错误位置搜索电路包含8条计算支路，每条计算支路具有相同的电路结构，如图7中所示。

根据式(6)与有限域运算规则可知，图7中以有限域乘法级联的结构实现了式(6)的计算过程，并且，每条支路中以有限域乘法器和寄存器组成的累乘结构实现了逆向的搜索过程，其中，对于每条支路，元素系数仅包含通过寄存器的复位值固化初始化系数α-k(k∈[1,8])和固定的计算间隔系数α-8，在完整的计算过程中，仅需要保留8个元素系数，避免了8 191个元素表的存储，大幅缩减了译码器的电路面积。

图7 错误位置搜索支路Fig.7 Error location search branch

通过量化分析，说明图7中所示的错误位置搜索电路对整体译码器电路面积成本的缩减效果，根据本文设计的译码器参数，纠错能力t=9，包含分段CRC-16校验的信息位的总长度为4 160 bit。在标准的BM译码算法中，对应的元素αi查找表的深度为8 191，元素二进制表示的位宽为13位。而本文提出的错误位置搜索电路避免了元素查找表的使用，可减少8 191×13 bit的存储器资源。以65 nm低功耗工艺为例，即使采用SRAM存储作为元素查找表，也需要89 430.14 μm2的电路面积，约为35 489个等效门电路，因此，图7中的错误位置搜索电路对译码器面积成本的缩减是显著的，而对比于其它采用寄存器作为元素存储的译码器电路，本文提出的错误位置搜索结构在面积成本方面的收益将更加明显。

图7中所示的错误位置搜索电路在降低译码器电路面积的同时，也大幅提高了译码器的吞吐率，以及极大降低了译码延迟。为更清晰的说明图7中电路在译码延迟方面的优势，图8中给出了在错误位置搜索阶段，本文提出的译码器电路的工作时序与标准BM译码算法的搜索时序的对比情况。

在图8中可以看到，在标准的译码算法中使用Chien搜索算法，根据式(13)与(14)的推导结果，由于σ(αj1)=0对应接收序列r(x)中的第n-j1比特的实际错误位置，因此，译码器在前3 915个机器周期内得到的错误位置搜索结果无法与实际接收序列r(x)中的信息位对应，从而无法得到正确的译码结果。而在3 915个机器周期后，错误位置搜索电路经过顺序搜索得到的结果与r(x)中n-j1对应，即采用标准的BM译码算法此时得到的译码结果是倒序输出的，如果得到最终的完整的正序译码结果，则需要等待错误位置搜索过程结束，如图8中所示，共需要至少8 191个机器周期，这将使译码器的译码延迟大幅增加，降低译码器的吞吐率以及实时性，另外，也需要额外的缓存电路接收逆序输出的结果。

图8 错误位置搜索时序对比Fig.8 Timing comparison of error location search

如图8中所示，对比于标准BM译码算法中的搜索过程，图7中所示的结构利用有限域的运算规则：α-i=αn-i和αn·α-i=αn-i，实现了错误位置搜索电路，具体的说，以α-i=αn-i的对称关系，在搜索过程中以αn=αn-1·α-i代替了αn=αn-1·αi，其中，n表示顺序搜索的序号，-i表示图7所示结构所组的成各支路中寄存器的初始元素的幂次，α0=α-i，因此，结合图8中给出的搜索时序，以及根据α-i=αn-i，可以看到图7中的搜索电路结构可直接输出与r(x)序列对应的搜索结果，并得到的译码结果是正序输出的。因此，本文提出的错误位置搜索电路能够降低至少3 915个机器周期，搜索阶段的延迟周期为0，大幅降低了译码器的译码延迟。另外，结合图4中的整体译码器的电路结构也能够看到，本文提出的译码器能够在不增加额外缓存电路的情况下直接由输出端口输出译码结果，并且，由于图7中的搜索电路采用了并行结构，可同时搜索8个错误位置，也进一步提高了译码器的吞吐率。

2.2 实现结果与对比

为得到准确的评估结果，本文采用65 nm工艺对所提出的译码器电路进行了逻辑综合，综合条件为最差工艺角：电压1.08 V，温度125 ℃，时钟频率为200 MHz。面积综合结果为436 333.323 μm2，约为125 819等效门，动态功耗约为34.451 mW。为提供更公平的比较结果，表1中给出了译码器面积指标的2种表示形式：布局布线前的器件面积和等效门数量。其中，等效门数量为相同工艺下器件面积所对应的扇出为4的2输入与非门(NAND FO4的面积为1.4 μm×1.8 μm)的等效数量；功耗指标为50%翻转率情况下，200 MHz工作频率所对应的动态功耗评估结果；译码器电路的关键路径延迟为4.363 ns，满足最大200 MHz的工作频率。

本文提出的译码器电路与其他报告中BCH译码器电路的对比情况如表1中所示，为全面的对比译码器电路的性能，其中包括了电路的面积，码字长度，纠错能力，最大工作频率，以及译码延迟和数据吞吐率的对比情况。另外，为避免工艺尺寸不同对电路面积对比结果的影响，在表1中以等效门数量作为电路面积的比较参数。

表1 译码器性能对比Table 1 Performance comparison of decoder

根据式(3)可知，码字长度n和纠错能力t与计算量正比，译码过程的计算量不仅决定了译码延迟，同时也决定了电路的规模。对比表1中的数据，本文提出的BCH译码器与文献[13]的码字长度相同，纠错能力提升近一倍，但电路面积仅为文献[13]的约38.7%；与文献[12]相比，在码字长度和纠错能力均相同的情况下，本文设计的译码器电路也得到了约20.8%的面积缩减，并且，最大数据吞吐率和译码延迟也得到了近一倍的提升；而表1中文献[11]具有最高的数据吞吐率和最低的译码延迟，但由于使用了αn元素的查找表结构，导致与其他成果相比，即使码字数据长度最短，却具有最高的面积成本，文献[11]中译码器的码字长度仅为本文的3.125%，但面积也是本文的3.4倍。综合上述数据可知，本文提出的BCH译码器结构在码字数据长度与纠错能力相同的情况下具有更低的译码延迟、更高的吞吐率以及更小的面积成本。

3 结论

1)基于避免求逆的BM算法实现译码器结构，消除了元素求逆运算，并通过对元素参数的实时计算避免了原始算法中大规模查找表的使用，使译码器的电路面积得到了大幅缩减。

2)针对FLASH器件的时序特点和处理器对可靠性的要求，采用了CRC-16校验与BCH编码级联的方式组织数据格式，克服了BCH算法的纠错性能限制，使超出译码器纠错能力的读取数据的正确性能够被译码器检测，并采用了分段式CRC-16校验的方式，使处理器能够提取无错误的数据段，提高了对数据的利用率。

3)采用了乒乓结构的桶形移位寄存器，使待译码数据与译码过程并行进行，并采用了全流水线的并行译码过程，获得了更高的吞吐率。