CN103151078A

CN103151078A - 一种存储器检错纠错码生成方法

Info

Publication number: CN103151078A
Application number: CN2013100869652A
Authority: CN
Inventors: 周玉梅; 王雷; 戴睿; 刘海南; 蒋见花
Original assignee: Institute of Microelectronics of CAS
Current assignee: Institute of Microelectronics of CAS
Priority date: 2013-03-19
Filing date: 2013-03-19
Publication date: 2013-06-12
Anticipated expiration: 2033-03-19
Also published as: CN103151078B

Abstract

本发明公开了一种用于存储器加固的检错纠错码的生成方法。该方法包括：根据原始数据位宽和所需纠检错能力预估校验位个数；初始化校验矩阵；从待检验的校正子向量池中逐个搜索符合线性独立要求的校正子向量填入校验矩阵；记录每次搜寻所产生的完整的校验矩阵，并改变向量搜寻的起始位置，重新进行搜索直至搜寻的起始位置穷尽整个校正子向量池；如果没有得到完整的校验矩阵，则增加校验位个数，并重复执行步骤2至4；如果有多个完整的校验矩阵，则从中选择一个最优的校验矩阵作为检错纠错码。采用本发明所提出的方法可以大大加快各种存储器加固编码的生成速度，无需再对各种编码算法进行研究便可得到较优结果。

Description

一种存储器检错纠错码生成方法

技术领域

本发明涉及存储器加固编码领域，特别涉及一种存储器检错纠错码生成方法。

背景技术

检错纠错码(Error Detection and Correction，EDAC)是存储器加固的一种常用手段。目前已有多种编码方式用于不同的应用需求，如汉明码(Hamming Code)，海思码(Hsiao Code)，里德-所罗门码(Reed-SolomonCode)等等。各种编码方式虽然算法有所不同，但用于存储器加固时的基本工作方式是一样的。如附图1所示，为了实现纠检错的功能，存储器需要在原始数据之外增加若干位的存储空间用于存放校验位。用字母k来表示原始信息的位宽，字母n来表示加入校验位后的位宽，对应的编码也被称为(n，k)码。显然，n位的码字中有k位的原始信息，(n-k)位冗余的校验位。当进行写操作时，需要将原始信息通过编码电路以生成检验位，并一同存入存储器；而进行读操作时，将原始信息的数据再次通过编码电路，其结果和读出的检验位数据进行异或运算得到校正子，然后根据校正子对数据进行纠检错操作。其中要注意的是编码电路所生成的校验位与原始信息一同存储，因此解码电路不但要能够纠检原始信息中的错误，也要能够纠检校验位中的错误。

目前各类系统中所采用的存储器种类繁多，应用面广泛，不同的存储器有着不同的应用环境和工作模式，对检错纠错码的需求也各不相同。已有的各种编码方式往往功能固定，如汉明码和海斯码只能进行“纠一检二”的功能，常见的奇偶校验码只能实现检测奇数位错误的功能，而RS码虽然能纠多位错，但代价较大。要实现不同能力的纠检错能力就需要掌握不同编码的计算原理，这对于存储器设计而言带来更多挑战。而且，用固定算法往往只能得到一种解码矩阵，无法对其进行进一步的优化。

发明内容

(一)要解决的技术问题

为此，本发明提出针对具体情况定制一种合适的校验矩阵，实现对不同要求的存储器加固编码进行定制的方法，通过校正子向量搜索的方法实现用最小的冗余度、面积和延时代价来完成特定加固的目标。

(二)技术方案

为实现上述目标，本发明提供了一种用于存储器加固的检错纠错码的生成方法，包括：

步骤1、根据原始数据位宽和所需纠检错能力预估校验位个数；

步骤2、初始化校验矩阵；

步骤3、从待检验的校正子向量池中逐个搜索符合线性独立要求的校正子向量填入校验矩阵；

步骤4、记录每次搜寻所产生的完整的校验矩阵，并改变向量搜寻的起始位置，重新进行搜索直至搜寻的起始位置穷尽整个校正子向量池；

步骤5、如果没有得到完整的校验矩阵，则增加校验位个数，并重复执行步骤2至4；

步骤6、如果有多个完整的校验矩阵，则从中选择一个最优的校验矩阵作为检错纠错码。

(三)有益效果

本发明提供了一种通用的方式来生成各种要求不同的存储器加固编码，通过预估校验位个数，采用单位矩阵初始化整个校验矩阵，然后遍历搜寻整个向量空间来填充校验矩阵。用变换向量遍历的方式来得到各种不同的校验矩阵，并从中挑选最优者。采用本发明所提出的方法可以大大加快各种存储器检错纠错码的生成速度，无需再对各种编码算法进行研究便可得到较优结果。

附图说明

图1是本发明中采用检错纠错码对存储器进行加固的原理框图；

图2是本发明中存储器检错纠错码生成方法的流程图。

具体实施方式

为使本发明的目的、技术方案和优点更加清楚明白，以下结合具体实例对本发明作进一步的详细说明。

图1示出了本发明采用检错纠错码对存储器进行加固的原理框图。如图1所示，采用检错纠错码对存储器进行加固需要实现编码模块、校正子计算模块和纠检错模块。所述编码模块，在写操作时，用于在原始数据输入存储器时计算相应的校验位并一同存入存储器，在读操作时，同样对原始数据进行计算得到校验结果。所述校正子计算模块，在读操作时，用于将编码模块所计算得到的校验结果和所存储的校验位进行异或操作，并得到校正子。所述纠检错模块用于根据所述校正子计算模块得到的校正子对存储器数据进行纠错检错。

本发明中，所述编码模块通过实现一校验矩阵的功能来实现对原始数据的编码。以下将详细介绍该校验矩阵的原理及生成过程。

定义k位的原始数据向量为D，n位的码字向量即经编码模块加入校验位后的数据为C。可以通过一个大小为k×n的生成矩阵G将向量D转为向量C。生成矩阵G可分为两部分：I_k与P。其中I_k为k位宽的单位矩阵，P为k×(n-k)的编码矩阵，用来根据k位的原始数据得到相应的(n-k)位的校验位。可见，所述编码模块实现的就是编码矩阵P所代表的功能。需注意的是由于存储器内的数据都是二进制的数据，因此这里所用的矩阵也都是二进制域内的矩阵，其加法等同于位操作中的异或操作(对于二进制域内的加法，0+0＝0，1+0＝1，1+1＝0)。

以针对8位数据进行纠单错的汉明码为例说明，加入矩阵P如下所示：

P = [\begin{matrix} 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 \end{matrix}]

如上文所述可以用异或运算来实现矩阵中的加法，因此将该矩阵转化为采用异或运算的校验位生成公式。设码字C中的低位部分为原始数据，即C₇～C₀等于D₇～D₀；高位部分C₁₁～C₈为冗余校验位，其生成公式如下(符号

代表异或运算)：

C_{11} = D_{7} &CirclePlus; D_{6} &CirclePlus; D_{5} &CirclePlus; D_{4}

C_{10} = D_{7} &CirclePlus; D_{3} &CirclePlus; D_{2} &CirclePlus; D_{1}

C_{9} = D_{6} &CirclePlus; D_{5} &CirclePlus; D_{3} &CirclePlus; D_{2} &CirclePlus; D_{0}

C_{8} = D_{6} &CirclePlus; D_{4} &CirclePlus; D_{3} &CirclePlus; D_{1} &CirclePlus; D_{0}

而相应的也可以用一个校验矩阵H来代表校正子计算过程，H＝[I_n-kP]^T，I_n-k为n-k位宽的单位矩阵，H为n×k矩阵。通常会采用校验矩阵H来表示一个编码，其优点为：若发生数据意外翻转，校正子显示的正是出错位在矩阵H中对应的行向量。其中单位矩阵I_n-k代表的是检验信息出错时的初始化的校正子向量，矩阵P代表原始数据部分出错时的待填充的校正子向量。如原始数据最低位C₀发生翻转，则校正子计算结果便显示为矩阵P中最低一行的校正子向量“0011”。如果有多位数据发生意外翻转，得到的校正子为各个出错位的校正子向量异或的结果，如最低两位C₀和C₁发生意外翻转，得到的校正子为“0110”。纠检错模块是根据校正子对数据进行检错纠错，如果校正子为全“0”，代表数据无错，将原始信息部分的数据直接输出；如果校正子不为全“0”，根据其具体数值判断错误类型，进行纠错或者报错。

图2示出了本发明中检错纠错码生成方法流程图。本发明从校验矩阵角度出发，通过搜寻校正子向量的方法组成校验矩阵，并以此得到对应的检错纠错码。如图2所示，本发明提出的用于存储器加固的检错纠错码生成方法包括：

步骤1，根据原始数据的实际位宽和纠检错能力计算所需的不同的校正子向量，并以此来预估所需要的校验位个数。

如果是纠错方面的需求，每一个不同的错误都需要有单独的校正子向量，对于n位的存储数据(包括k位的原始数据和n-k位的检验位数据)，共有n种的单错，n×(n-1)种的双错。因此要实现纠单错的目的需要有n种不同的校正子向量，如要纠双错则需要有n+n×(n-1)种不同的校正子向量。如果是检错方面的需求，不同的错误可以共用一个校正子向量，只要同用于纠错的校正子不同即可。理论上一种类型的错误最少只要一个校正子向量即可。如对n位的存储数据进行“纠一检二”的加固，即要能纠正任一单错，检测出任何双错，至少需要n+1种校正子向量。在得到所需的校正子向量之后对其求2的底数便可得到预估的校验位个数。该预估数可能小于实际所需的最小校验位个数，尤其是在有检错的需求时，该方法估计的情况过于理想，实际中不容易实现。因此有可能会需要多次迭代来最终确定检验位的个数。对实例中所需的针对8位数据纠任意双错的要求，设检验位个数为c，所需的校正子向量包括8+c个单错校正子向量和(8+c)×(7+c)/2种双错校正子向量，需符合(8+c)+(8+c)×(7+c)/2＜2^c，经计算至少需要7位的校验位。

步骤2中，根据步骤1所得的预估的校验位个数，初始化校验矩阵向量。

首先初始化校验矩阵H，即在校验矩阵H中首先填入针对校验信息的校正子向量，即单位矩阵I，而针对原始数据出错部分的编码矩阵P代表的校正子向量为空，处于待填充状态。初始化后的校验矩阵如下所示。

对于本实例而言，由于校验位为7位，校验矩阵大小为7×15，初始化时填入一个7位宽的单位矩阵，剩下8个列向量需要填充。

步骤3中，从待检验的校正子向量池中逐个挑选向量进行计算，看是否符合线性独立的要求，如果符合就填入校验矩阵的待填充部分，以此往复直至填满整个校验矩阵。

所述待检验的校正子向量池为包含所有非全“0”的c位二进制向量。除去全“0”向量的原因在于校正子为全“0”代表数据无错，无法用来代表其他出错的情况。已经在校验矩阵H中出现的向量也要从池中取出，因此在单位矩阵中的向量都要取出。

对于二进制的向量，线性独立等同于各个向量相互位异或后结果不为全“0”向量。按照从小到大的顺序对校正子向量池中的向量逐个进行抽取，并检验所抽取的向量与校验矩阵中已经存在的向量是否符合线性独立要求，已经在校验矩阵中的向量和已经检验过的向量不再进行检验，其中已经在校验矩阵中的向量包括单位矩阵向量和已经填充在待填充部分中的向量。对于不同的纠检错需求，其线性独立的要求也不一样。通常对于纠t位错，要求任意2t个向量之间线性独立。几种常见的纠检错需求的向量线性独立要求如下表所示。

表1不同纠检错要求下校正子向量的线性独立要求

由于单位矩阵内向量的特殊性，单位矩阵本身符合任意线性独立要求。因此对于待检验的校正子向量，只需要检查涉及到该向量的线性独立计算，不需要对之前已经在校验矩阵内向量之间的线性独立要求进行检查。具体对于本实例而言，从待检验的校正子向量池中最小的向量{0，0，0，0，0，1，1}开始进行检验，需符合任意四个向量之间线性独立。通过计算可发现向量{0，0，0，0，0，1，1}与单位矩阵中的{0，0，0，0，0，0，1}，{0，0，0，0，0，1，0}线性相关，不符合任意四个向量之间线性独立的要求。因此不能填入校验矩阵，继续从向量池中选取向量进行检验。直到检测到向量{0，0，0，1，1，1，1}时才符合要求，因此填入校验矩阵中并继续搜寻，当填满校验矩阵或者搜寻完整个向量池后结束。在本次实例中，搜寻完整个向量池后只能找到4个符合要求的向量：{0，0，0，1，1，1，1}，{0，1，1，0，0，1，1}，{1，0，1，0，1，0，1}，{1，1，0，1，0，1，0}，没能够填满校验矩阵。

步骤4中，通过改变搜寻起始位置的之后再次执行步骤3，以得到不同的搜寻结果。起始位置应大于之前搜索到的第一个有效向量，否则结果相同，所述第一个有效向量为前次搜索时第一个填入校验矩阵的校正子向量。在本实例中，如果不从{0，0，0，0，0，1，1}而是从{0，0，1，0，0，0，1}开始搜索，得到的结果是{0，0，1，0，1，1，1}，{0，1，0，1，0，1，1}，{1，0，0，1，1，0，1}，{1，1，1，0，0，1，0}；如果从{0，1，0，0，0，0，1}开始搜索，得到的结果是{0，1，0，0，1，1，1}，{0，1，1，1，0，0，1}，{1，0，0，1，0，1，1}，{1，0，1，0，1，1，0}。

步骤5中，如果通过步骤4改变搜寻起始位置没有得到完整的校验矩阵，便需要增加一位校验位。然后重复步骤2至步骤4。在步骤1中所求得的只是一个校验位预估的最小值，并不能保证实现最终检错纠错目的。校验位数量越多，能够实现的检错纠错能力越强，但也因此要增加不少冗余的面积。设计时，在保证功能实现的前提下，总是希望校验位的数量越少越好。因此如果通过步骤4调整校正子搜寻起始位置后还是无法找到合格的校验矩阵后就必须增加校验位个数，但每次也只是增加1位，这样虽然会增加迭代的计算量，但可以保证用最小的面积代价实现特定的加固要求。本实例中，增加一位校验位后共有8位校验位，校验矩阵也调整为8×16。经过步骤3后得到一个合格的校验矩阵如下所示。

[\begin{matrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{matrix}]

再经过步骤4后调整搜寻起始位置，可以得到其他同样符合要求的结果如下所示。

[\begin{matrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{matrix}]

经检验可发现上述两个校验矩阵都可以实现预期的功能。需要对两者进行进一步的比较以确定最终结果。

步骤6中，根据各个校验矩阵所代表的检错纠错码在硬件实现上的差别进行筛选，得到最优的结果。

校验矩阵中的“1”的个数代表了实现该矩阵时所需要的异或门数量。如果校验矩阵中的“1”的个数比较少，便意味着更小的硬件开销。同时，校验矩阵中“1”的个数最多的行向量代表了实现该矩阵时的编解码电路中的关键路径。如果关键路径上的异或门数量较少，就能有更小的延时，也就意味着更好的性能。

以上述提高的两个校验矩阵为例。对于第一个矩阵，每行最多有7个“1”，意味着解码电路的关键路径上需要执行6个异或运算，即S₇和S₆两个校正子的计算。整个矩阵中共有45个“1”，意味着解码电路中共需要37个异或门。

而对于第二个校验矩阵，该矩阵中的“1”的个数为40个，小于第一解码矩阵，这说明在编码和解码过程中所需要的异或门的个数更少，减少了面积开销；每行只有5个“1”，从公式上可以看到每个校正子只需要4个异或运算，小于第一解码矩阵的6个异或运算，也即意味在同样的工艺条件下采用第二解码矩阵可以实现更高的运算速度。因此选择第二个校验矩阵作为最终结果。

定义信息位为D₇～D₀，校验位为C₇～C₀，校正子为S₇～S₀。根据最终校验矩阵可得校验码计算公式：

C_{7} = D_{7} &CirclePlus; D_{6} &CirclePlus; D_{5} &CirclePlus; D_{0}

C_{6} = D_{7} &CirclePlus; D_{6} &CirclePlus; D_{4} &CirclePlus; D_{3}

C_{5} = D_{7} &CirclePlus; D_{5} &CirclePlus; D_{3} &CirclePlus; D_{2}

C_{4} = D_{6} &CirclePlus; D_{5} &CirclePlus; D_{3} &CirclePlus; D_{1}

C_{3} = D_{7} &CirclePlus; D_{4} &CirclePlus; D_{2} &CirclePlus; D_{1}

C_{2} = D_{6} &CirclePlus; D_{4} &CirclePlus; D_{2} &CirclePlus; D_{0}

C_{1} = D_{5} &CirclePlus; D_{4} &CirclePlus; D_{1} &CirclePlus; D_{0}

C_{0} = D_{3} &CirclePlus; D_{2} &CirclePlus; D_{1} &CirclePlus; D_{0}

校正子的生成公式为：

S_{7} = C_{7} &CirclePlus; D_{7} &CirclePlus; D_{6} &CirclePlus; D_{5} &CirclePlus; D_{0}

S_{6} = C_{6} &CirclePlus; D_{7} &CirclePlus; D_{6} &CirclePlus; D_{4} &CirclePlus; D_{3}

S_{5} = C_{5} &CirclePlus; D_{7} &CirclePlus; D_{5} &CirclePlus; D_{3} &CirclePlus; D_{2}

S_{4} = C_{4} &CirclePlus; D_{6} &CirclePlus; D_{5} &CirclePlus; D_{3} &CirclePlus; D_{1}

S_{3} = C_{3} &CirclePlus; D_{7} &CirclePlus; D_{4} &CirclePlus; D_{2} &CirclePlus; D_{1}

S_{2} = C_{2} &CirclePlus; D_{6} &CirclePlus; D_{4} &CirclePlus; D_{2} &CirclePlus; D_{0}

S_{1} = C_{1} &CirclePlus; D_{5} &CirclePlus; D_{4} &CirclePlus; D_{1} &CirclePlus; D_{0}

S_{0} = C_{0} &CirclePlus; D_{3} &CirclePlus; D_{2} &CirclePlus; D_{1} &CirclePlus; D_{0}

综上所述，本发明有如下技术特征：(1)采用检错纠错码的方式对存储器进行加固。(2)根据实际检错纠错需求及数据位宽来计算所需校正子向量，并以此来对校验位个数进行预估。(3)采用单位矩阵初始化校验矩阵，并用搜索整个校正子向量空间的方式来寻找校验矩阵中的其它向量。(4)根据检错纠错需求得到校验矩阵中各向量间所需满足的线性独立关系，并以此为标准对校正子向量进行筛选。(5)通过改变校正子空间的起始位置进行多次校验矩阵的填充，以得到不同的校验矩阵。(6)根据实现电路所需的逻辑门数量和关键路径长度在其中进行筛选，以得到更优的结果。本发明所提供的方法每一步均可以用软件编程的方式实现自动运算，有利于降低设计及实现难度。

以上所述的具体实施例，对本发明的目的、技术方案和有益效果进行了进一步详细说明，应理解的是，以上所述仅为本发明的具体实施例而已，并不用于限制本发明，凡在本发明的精神和原则之内，所做的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。

Claims

1.一种用于存储器加固的检错纠错码的生成方法，包括：

步骤2、初始化校验矩阵；

2.如权利要求1所述的方法，其特征在于，所述校验矩阵由n-k单位矩阵和k×(n-k)的编码矩阵组成，其中k为原始数据位宽，n为编码数据位宽，所述编码数据包括原始数据和校验位。

3.如权利要求2所述的方法，其特征在于，在写操作时，利用所述编码对原始数据进行编码生成并存储校验位，在读操作时，利用所述编码矩阵对原始数据进行编码，并将得到的结果与所存储的校验位进行异或运算得到校正子，然后根据校正子对数据进行纠检错操作。

4.如权利要求1所述的方法，其特征在于，所述待检验的校正子向量池为包含非全0所有二进制向量，且其中不包含单位向量，其位宽为校验位个数。

5.如权利要求1所述的方法，其特征在于，对于二进制向量，线性独立指各个向量之间相互异或后结果不为0。

6.如权利要求2所述的方法，其特征在于，步骤2中所述初始化校验矩阵为初始化其中的单位矩阵，并将所述编码矩阵设置为待填充部分。

7.如权利要求6所述的方法，其特征在于，步骤3具体为从校正子向量池中逐个提取校正子向量，并计算所提取的校正子向量与校验矩阵中相应数量的向量之间的线性独立性，并将与校验矩阵中相应数量的向量之间具有线性独立要求的校正子向量填充到校验矩阵待填充部分。

8.如权利要求1所述的方法，其特征在于，步骤4中，改变后的搜索起始位置大于前次搜索到的第一个有效向量，所述第一个有效向量为前次搜索时第一个填入校验矩阵的校正子向量。

9.如权利要求1所述的方法，其特征在于，步骤6中根据硬件实现上的差别选择最优的校验矩阵。

10.如权利要求7所述的方法，其特征在于，所述相应数量根据纠错检错能力确定。