基于FPGA的检纠错逻辑算法的实现

　　引 言

　　随着现代技术的发展，作为现代高科技代表的航天工程，对星载计算机的依赖程度也越来越高。由于宇宙中存在着大量的带电粒子，星载计算机硬件系统的电子器件会受到电磁场的辐射和重粒子的冲击，其相互作用产生各种效应，其中单粒子反转(SEU)效应的影响尤为明显，它将引起卫星工作的异常或故障。这种错误若不及时进行纠正，将会影响计算机系统的运行和关键数据的正确性，造成程序运行不稳定和设备状态改变。

　　1 纠错原理

　　汉明码(Hamming Code)是由Richard Hamming于1950年提出的，属于线性分组码的范畴，其基本原理是将信息码元与监督码元通过线性方程式联系起来的，每一个监督位被编在传输码字的特定比特位置上。系统对于错误的数位无论是原有信息位中的，还是附加监督位中的都能把它分离出来。(n，k)线性分组码的生成矩阵G和校验矩阵H分别为n×k和n×(n-k)维矩阵，其中校验矩阵H决定信息位与校验位的关系，在编码和译码中都要用到。线性码的最小码距为d，即校验矩阵H中任意d-1列线性无关，它与码的纠错能力有以下关系：

　　(1)检测P个随机错误，要求d≥e+1;

　　(2)纠t个随机错误，要求d≥2t+1;

　　(3)纠t个随机错误，同时检测e(e≥t+1)个随机错误，要求d≥e+t+1。

　　作为一种典型的线性分组码，标准汉明码的码长n=2m-1，监督位数为m，信息位数为k=n-m，最小码距d=3，因此它的纠错能力t=1，是一种常用纠单个位错误的编码方式。还可以根据需要对标准汉明码进行扩展，增加1个校验位对所有位进行监测，就得到扩展汉明码。1个(n，k)汉明码经过扩展以后，就变成了(n+1，k)汉明码。扩展以后的汉明码d=4，t=2，e=1，可以纠正单个位错误，并检测出双位的错误。对64位的数据进行纠错设计，满足信息位数大于64要求的最短的标准汉明码为n=26-1时的(127，120)码，它具有7个监督校验位。根据汉明码信息位删减后其纠错能力较之前不会降低的特性，将该码的信息位缩短为64位，使用了(71，64)的删减汉明码。这里设计了一种7个校验位同64个信息位的对应计算关系如图1所示。

　　图1中DA0～DA63为信息位;CC0～CC6为监督校验位。其中CCO是所有位于编号末位数为1列中信息位数据的奇偶校验计算结果。与之类似，CCl对应于所有位于编号次低位数为1列中的信息位。同理，CC3～CC6分别对应了行号各位数为1行中的信息位数据。通过这个对应关系表，可以得出整个汉明码的生成公式：

　　M=DG

　　式中：M为生成的(71，64)汉明码矩阵，每个行向量是一组汉明码;D为信息位数据矩阵行，64个信息位组成一个行向量;G成为汉明码生成矩阵，可以根据上述的对应计算关系得出来。

当执行纠错功能时，需要同时读取数据位和监督校验位，并且对所读取的数据位按照校验位的生成算法重新进行1次校验位的生成(可以用NCC0～NCC6来表示)，通过CC0～CC6和NCCO～NCC6的比对来进行检错纠错运算。如果发生1位数据翻转错误，则新生成的校验位NCC中会有若干位同原先的CC校验位相异，通过相异的位可以对数据进行纠错。假设目前检测出CCl，CC2，CC4，CC5这4个校验位同新生成的NCC中对应位的异或运算结果为1，如图2中细箭头所示。

　　CCl校验位相异对应出错数据位列号倒数第二位为1;CC2对应列号倒数第3位为1，可以推出错误数据位的列号为110，同理行号相关的几个校验位中CC4，CC5出现相异可以推出错误数据位的行号为0110，由此可以知道出错的数据位是DA22，再对确认出错的数据位取反就实现了纠正1位错误的功能。而如果出现2位错误，比如数据位DAl和DA34同时出错，如图2中所示，这会引起新老校验位中的CC0，CCl，CC3，CC4，CC6同时出现相异。这时如果还按照上述纠正1位错误时的算法，就会推出出错数据位的行号为1011列号为011，这样，就会认为是数据为DA51发生了翻转，从而产生错误的检纠错结果，如图2中粗箭头所示。以前的测试数据表明，若在近地轨道中，SRAM存储器中的每一个存储数据位一天之内发生SEU概率约是10-7(位·天)，则可以推导出这个SRAM中1组64位的数据，在一天时间内有2位同时出现错误的可能性约为10-10(次·天)，在南大西洋辐射异常区和太阳活动高峰期，这种情况的发生率可能还会提高1～2个数量级。

　　为了避免在发生双位元错误时出现错检错纠的情况，需要增加1个校验位CC7，它是所有数据位的奇偶校验结果，即CC7=DA0⊕DAl⊕DA2⊕DA3⊕…⊕DA63。这样在每次出现1个数据位错误时，新生成的NCC7也都会与先前的值相异，而当数据位中有2个存储单元出错，其他校验位会检测有错误出现，但NCC7不会发生变化，NCC7⊕CC7=0，这时就可以判断出有双位错误，从而使系统实现了检测双位错误的功能。

　　2 设计实现

　　将所有与主存储器中数据一一对应的校验位(CCl～CC8)存储在另一个独立的8位SRAM中，系统的硬件结构如图3所示。

　　存储校验位的8位数据SRAM2同样遇到出现SEU效应得可能，通过分析可以知道，SRAM2出现1位数据翻转时，只有对应的一位数值与通过数据位新生成的校验位数值相异，而其他的7个校验位数据都没有变化，此时对对应的校验位取反就实现了纠错功能。对于出现双位元错误的可能，通过理论分析，可以知道一组8位的校验数据在一天中出现这种情况的概率约为7×10-13。，相比于主存储器而言降低了两三个数量级，暂时可以不予考虑。

　　FPGA的检纠错逻辑设计采用VHDL语言实现。设计使主存储器SRAMl中的64位数据新生成的NCC[7：0]与SRAM2中的7位校验位CC[7：0]一起经过异或运算，生成8位的校正子，其中前7位就对应于前述定位错误数据的行号和列号的值，第8位用于判断是否出现双位元错误。8位校验子的值可以求出1个64位纠错掩码(Mask)，用以校正单位元错误。如果未检测到错误，此掩码的所有位都为零。如果检测到单位元错误，相应掩码会屏蔽除错误位之外的所有位。下一阶段，使用原始数据对此掩码进行异或运算。最终，错误位被反转(或校正)至正确状态。如果检测到双位元错误，所有掩码位也都为零。使用1个双位的数组(ER[1，O])用于报告检测的错误类型(“OO”表示无错、“01”表示单位元错误、“10”表示双位错误、“11”表示无法判断的多位错误)。整个纠错逻辑的工作过程如图4所示。生成错误类型报告数组和相应的校正掩码的工作都在同一时钟周期内完成，体现了采用FPGA进行并行处理的独特优势。

　　3 结 语

　　对综合后进行仿真的结果进行分析，期间人为地加入1位、2位、3位随机分布的数据位错误，该系统能够在2个系统时钟周期内对1位错误的情况成功地检测并予以纠正;对2位和3位错误情况也都进行了正确的类别判定。仿真结果表明，设计的系统比较理想，能满足设计要求。