CN104850468A - 基于校验矩阵的纠删码解码方法 - Google Patents
基于校验矩阵的纠删码解码方法 Download PDFInfo
- Publication number
- CN104850468A CN104850468A CN201510290040.9A CN201510290040A CN104850468A CN 104850468 A CN104850468 A CN 104850468A CN 201510290040 A CN201510290040 A CN 201510290040A CN 104850468 A CN104850468 A CN 104850468A
- Authority
- CN
- China
- Prior art keywords
- check matrix
- matrix
- row
- correcting
- eleting codes
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
- 239000011159 matrix material Substances 0.000 title claims abstract description 156
- 238000000034 method Methods 0.000 title claims abstract description 60
- 238000004364 calculation method Methods 0.000 claims description 15
- 230000009466 transformation Effects 0.000 claims description 6
- 230000004083 survival effect Effects 0.000 claims description 5
- 230000008859 change Effects 0.000 claims description 3
- 230000008901 benefit Effects 0.000 abstract description 4
- 238000012937 correction Methods 0.000 description 21
- 230000008569 process Effects 0.000 description 8
- 239000013598 vector Substances 0.000 description 5
- 238000012795 verification Methods 0.000 description 4
- 238000010586 diagram Methods 0.000 description 3
- 238000005516 engineering process Methods 0.000 description 3
- 238000012986 modification Methods 0.000 description 3
- 230000004048 modification Effects 0.000 description 3
- 238000003491 array Methods 0.000 description 2
- 238000011084 recovery Methods 0.000 description 2
- 230000007812 deficiency Effects 0.000 description 1
- 238000013461 design Methods 0.000 description 1
- 238000007429 general method Methods 0.000 description 1
- 238000005457 optimization Methods 0.000 description 1
- 230000000750 progressive effect Effects 0.000 description 1
- 238000000844 transformation Methods 0.000 description 1
Landscapes
- Error Detection And Correction (AREA)
- Detection And Correction Of Errors (AREA)
Abstract
本发明提供了一种基于校验矩阵的纠删码解码方法，本发明适用于任意基于异或操作的纠删码，本发明通过对校验矩阵进行解码，从而对解码效率带来非常大的提升。另外，通过构造稀疏校验矩阵的迭代算法，能进一步提升本发明的解码效率。相比于传统的两种实现方法，本发明同时具有通用性和高效性。
Description
技术领域
本发明涉及一种基于校验矩阵的纠删码解码方法。
背景技术
随着大型存储系统中对数据可靠性的要求不断提升，纠删码作为一种高效低成本的保证高可靠性技术，被广泛采用。通过使用纠删码技术，原始数据与通过编码生成的校验数据被一同存放在多个存储设备上(典型应用如磁盘阵列)，从而当其中一些设备发生故障时，它所丢失的数据可用其他设备上的数据来恢复。
在多种多样的纠删码之中，有一类是基于异或(Exclusive-OR)操作的，另一类则是基于有限域上的运算来进行编码解码的。目前来说，基于异或的编码更加流行，这是由于硬件通常都直接支持异或操作，使得这类编码的运算代价非常低，编码解码的效率非常高。常见的基于异或操作的编码有如下一些：用于恢复两个磁盘失效的有EVENODD，RDP编码，而能容忍三个磁盘失效的有STAR和HoVer等。
通常，我们有两种途径来实现这些编码。第一种方法我们称之为“矩阵方法”：对于任意一种纠删码，只要给出它的“生成矩阵”(所有纠删码都有其生成矩阵)，我们便能利用一系列矩阵操作进行编码或解码。该方法是一种通用方法，对于任意纠删码，我们均可用该方法来实现。第二种方法我们称之为专用方法：对于某些编码，存在一些特定的编码、解码算法。这些算法是根据编码本身固有的特性来设计的，因此并不具有通用性。具体来说，适用于一种纠删码的专用编码、解码算法，通常不适用于另一种纠删码。
现有的两种实现纠删码的方法，即矩阵方法和专用方法，均存在显著的缺点。一方面，矩阵方法虽然较为通用，但它在解码速度上有显著的不足，从而限制了磁盘阵列的恢复速度，降低存储系统的可靠性与可用性。另一方面，专用方法在解码速度上仍然不能达到最优(如EVENODD和STAR编码)，而且这类算法的实现非常复杂，不利于进一步优化；此外，很多高效的编码并不具有专用的实现方式，因此专用方法存在很大的局限性。总结来说，现有的实现纠删码的两种方法均不能同时具有通用性和高效性。
发明内容
本发明的目的在于提供一种基于校验矩阵的纠删码解码方法，能够对解码效率带来非常大的提升
为解决上述问题，本发明提供一种基于校验矩阵的纠删码解码方法，包括：
根据磁盘阵列的基于异或操作的纠删码的编码矩阵的编码方式，构造出对应于所述纠删码的校验矩阵，所述校验矩阵为一个01矩阵；
根据所述校验矩阵计算出磁盘阵列中失效磁盘的失效数据。
进一步的，在上述方法中，，根据所述校验矩阵计算出磁盘阵列中失效磁盘的失效数据，包括：
标记出磁盘阵列中存活数据S和失效磁盘的失效数据L；
将校验矩阵H分割成两个子矩阵HL和HS，分别对应于所述失效数据L和存活数据S；
利用等式即可通过校验矩阵计算磁盘阵列中失效磁盘的失效数据，其中，为01矩阵的广义逆矩阵。
进一步的，在上述方法中，根据磁盘阵列的基于异或操作的纠删码的编码矩阵的编码方式，构造出对应于所述纠删码的校验矩阵中，
校验矩阵的行数等于纠删码的编码矩阵中的校验块的数量，校验矩阵的列数等于纠删码的编码矩阵中所有检验块和数据块的数量。
进一步的，在上述方法中，根据磁盘阵列的基于异或操作的纠删码的编码矩阵的编码方式，构造出对应于所述纠删码的校验矩阵中，
校验矩阵的每一行对应所述编码矩阵的一个校验计算公式，每一列对应编码矩阵中的一个元素，当且仅当第j列对应的元素出现在第i个校验计算式子中时,校验矩阵的第i行j列的元素的值为1。
进一步的，在上述方法中，根据磁盘阵列的基于异或操作的纠删码的编码矩阵的编码方式，构造出对应于所述纠删码的校验矩阵中，
所述校验矩阵为稀疏校验矩阵。
进一步的，在上述方法中，所述稀疏校验矩阵通过初等变换得到。
进一步的，在上述方法中，所述稀疏校验矩阵通过如下迭代算法构造得到：
步骤S11，设置变量update，表示一轮迭代中校验矩阵是否被更新，初始值设置为false；
步骤S12，初始化过程，包括步骤S121～步骤S123：
步骤S121，计算数组ones[x]，其中，数组ones[x]表示校验矩阵第x行所包含的1的数量；
步骤S122，记数组from[x]，其中from[x]表示第x行存放该行与哪一行之和，初始值为-1表示不存放任何其他行；
步骤S123，记数组visit[x]，其中，visit[x]表示第x行是否被访问过，初始全置为false，该行未被访问；
步骤S13，循环执行以下步骤S131～步骤S134，直至所有行均被访问：
步骤S131，在所有未被访问过的行里，选取包含1数量最少的行，假设是x行，即ones[x]的值最小；
步骤S132，枚举所有其他行，设行号为y，执行如下步骤S1321～S1322：
步骤S1321，计算x行与y行的汉明距离，即有多少列的元素不相同，记该值为dis；
步骤S1322，若dis<ones[y]，则表示需要将x行加至y行，于是将dis赋值给ones[y]，然后将from[y]的值改为x，最后将update的值设成true；
步骤S133，若from[x]的值不为-1，则将from[x]这一行加至第x行；
步骤S134，将visit[x]设成true，表示该行已经被访问；
步骤S14，若update的值为true，则返回步骤S11，否则算法结束。
与现有技术相比，本发明适用于任意基于异或操作的纠删码，本发明通过对校验矩阵进行解码，从而对解码效率带来非常大的提升。另外，通过构造稀疏校验矩阵的迭代算法，能进一步提升本发明的解码效率。相比于传统的两种实现方法，本发明同时具有通用性和高效性。
附图说明
图1是本发明一实施例的EVENODD水平校验的编码方式的示意图；
图2是本发明一实施例的EVENODD斜向校验的编码方式的示意图；
图3是本发明一实施例的EVENODD的校验矩阵样例图；
图4是本发明一实施例的校验矩阵解码流程示意图。
具体实施方式
为使本发明的上述目的、特征和优点能够更加明显易懂，下面结合附图和具体实施方式对本发明作进一步详细的说明。
在介绍本发明之前，先通过具体例子来阐述纠删码的基本概念与传统实现方式，以便于更好地阐述本发明的概念以及展示本发明的优势。以经典的EVENODD编码作为案例，该编码可用来实现RAID-6磁盘阵列，使其能容忍两个磁盘同时失效而不使数据丢失。EVENODD适用于具有p+2个磁盘的阵列，这里p必须是一个质数；并且在这p+2个磁盘中，有p个磁盘始终用来存放原始数据，而剩余两个磁盘用来存放校验数据，这些校验数据是由原始数据经过编码流程计算而得的。图1和图2展示展示了适用于7个磁盘的EVENODD的编码流程，该编码对应的质数为p＝5。
在图1和图2中，我们用一个(p-1)*(p+2)的矩阵来表示EVENODD编码，其中矩阵的每一列表示一个磁盘，每一个格子表示的是磁盘上一个大小固定的块。先将矩阵的列从左至右编号为0-6，前5个磁盘存放数据，后两个磁盘存放校验。同样地，矩阵的行从上至下编号为0-3，而矩阵中第i行第j列的元素表示为Ci,j。
图1展示了磁盘5上的校验数据的计算方式。对于磁盘5上的每个校验块，它是由磁盘0-4中同一行的数据块用异或操作求和而得，举例来说,C0,5是由公式计算而得。对应到图中，每个校验块是由同样形状的数据块用异或求和而得。由于这部分计算只用到同一横行的元素，因此该校验通常被称为横向校验。
图2展示了磁盘6上的校验数据的计算方式。我们采用了同图1类似的表达方式，用同样的形状表示参与一个校验块计算的所有数据块。我们首先要计算一个中间值M,计算公式为计算出M之后，磁盘6上的每个校验块则由图2中同样形状的数据块的值，以及M的值一同求和而得。例如，该校验通常被称为斜向校验。
若在一个计算公式中，只有一个元素是丢失数据，那么该元素可通过公式中其他元素用异或求和而恢复出来。传统的恢复算法即利用了该特性。例如，当两个数据盘同时失效时，首先，该编码能利用存活的两个校验盘上的数据恢复出s的值；然后先寻找一个数据块，它能被某个斜向校验计算公式直接恢复出来；接下来利用横向校验公式，可恢复同一行中的另一个缺失数据；接下来再利用斜向校验恢复下一个数据，如此迭代直至所有数据恢复完毕。
本发明提供一种基于校验矩阵的纠删码解码方法，包括：
步骤S1，根据磁盘阵列的基于异或操作的纠删码的编码矩阵的编码方式，构造出对应于所述纠删码的校验矩阵，所述校验矩阵为一个01矩阵，将其记为H；
步骤S2，根据所述校验矩阵计算出磁盘阵列中失效磁盘的失效数据。
本发明的基于校验矩阵的纠删码解码方法的一优选的实施例中，步骤S2，根据所述校验矩阵计算出磁盘阵列中失效磁盘的失效数据，包括：
步骤S21,标记出磁盘阵列中存活数据S和失效磁盘的失效数据L；
步骤S22，将校验矩阵H分割成两个子矩阵HL和HS，分别对应于所述失效数据L和存活数据S,根据校验矩阵的性质，满足如下等式HL·L＝HS·S；校验矩阵有一个重要的性质，即它与编码后的数据的乘积始终为0，这个性质是由其定义方式所决定的，且该性质对解码步骤来说至关重要，图3已经借助EVENODD的例子阐明了这种关系，而具体的解码方案将在下文详细叙述；
步骤S23，由上一步等式可得利用该等式即可通过校验矩阵计算磁盘阵列中失效磁盘的失效数据，其中，为01矩阵的广义逆矩阵。具体的，为了更好地解释解码流程，我们先假设当前有若干个磁盘失效。我们仍然把整个条带内的数据看作一个向量，则失效磁盘上的数据就被看作是未知数。现在，我们将图3所示的等式进行拆解，首先将表示所有数据的向量拆成两个向量，其中一个全由失效数据构成(记为L)，另一个则由存活数据构成(记为S)；而校验矩阵H也被分割成两个子矩阵，一个由失效元素所对应的列构成(记为HL)，另一个由存活元素所在列构成(记为HS)。则根据图3所示的等式，我们可以得到：在这个等式中，仅有L为未知量表示丢失的数据。HL·L与HS·S的计算结果均为列向量。而两个列向量异或值为0说明它们相等，因此该式子可以写成HL·L＝HS·S,我们再通过矩阵运算，可以将该式子中的未知量解出来：最后，图4展示了一个恢复失效数据的具体实例。我们仍然采用之前例子中的EVENODD编码，并假定有7块磁盘，其中0号和2号磁盘是失效盘，该磁盘上的数据均为失效数据。我们首先对校验矩阵按列进行分割，然后将编码后的数据分为存活数据和失效数据。此时，图4表示了分割之后校验矩阵与编码后数据的关系。接下来，我们求出HL的逆矩阵，并计算出等式右端的结果，将两者相乘即求出失效数据。
本发明的基于校验矩阵的纠删码解码方法的一优选的实施例中，步骤S1，根据磁盘阵列的基于异或操作的纠删码的编码矩阵的编码方式，构造出对应于所述纠删码的校验矩阵中，校验矩阵的行数等于纠删码的编码矩阵中的校验块的数量，校验矩阵的列数等于纠删码的编码矩阵中所有检验块和数据块的数量，即编码矩阵中所有元素的数量，校验矩阵的每一行对应所述编码矩阵的一个校验计算公式，每一列对应编码矩阵中的一个元素，当且仅当第j列对应的元素出现在第i个校验计算式子中时,校验矩阵的第i行j列的元素的值为1。具体的，校验矩阵是与纠删码密切相关的一个矩阵，它可以表示编码后的数据的各个字段之间的线性关系。在上述例子中，用于表示EVENODD的矩阵为4行7列共包含28个元素包括校验块和数据块，并且最后两列的8个元素是校验块，因此与EVENODD编码对应的校验矩阵有8行28列。具体来说，校验矩阵的每一行对应所述编码矩阵的一个校验计算公式，每一列对应编码矩阵中的一个元素。校验矩阵的每个元素值非0即1，并且当且仅当第j列对应的元素出现在第i个校验的计算式子中时校验矩阵的第i行1列的元素的值为1。图3给出了与图1-2相对应的EVENODD编码的校验矩阵的样例。该图3所示的校验矩阵中，前四行对应了磁盘5上每个元素的校验计算公式，而后四行对应了磁盘6上每个元素的校验计算公式。
本发明的基于校验矩阵的纠删码解码方法的一优选的实施例中，步骤S1，根据磁盘阵列的基于异或操作的纠删码的编码矩阵的编码方式，构造出对应于所述纠删码的校验矩阵中，所述校验矩阵为稀疏校验矩阵，以进一步提升解码速度，使校验矩阵在解码过程中复杂度显著降低。
本发明的基于校验矩阵的纠删码解码方法的一更优选的实施例中，所述稀疏校验矩阵通过初等变换得到。首先，我们观察到一个编码矩阵的校验矩阵并不唯一。一个合法的校验矩阵与编码后的数据的乘积应当为0，而我们若构造了任意一个合法校验矩阵，我们对该矩阵进行初等行变换，即我们将一行的值加至另一行中，变换后的新矩阵仍然是合法的校验矩阵。而根据之前所述的解码流程，我们观察到，稀疏的校验矩阵具有更小的编码/解码代价，因此我们可以利用初等变换来提升本发明的实现速度。
本发明的基于校验矩阵的纠删码解码方法的一更优选的实施例中，所述稀疏校验矩阵通过如下迭代算法构造得到：
步骤S11，设置变量update，表示一轮迭代中校验矩阵是否被更新，初始值设置为false；
步骤S12，初始化过程，包括步骤S121～步骤S123：
步骤S121，计算数组ones[x]，其中，数组ones[x]表示校验矩阵第x行所包含的1的数量；
步骤S122，记数组from[x]，其中from[x]表示第x行存放该行与哪一行之和，初始值为-1表示不存放任何其他行；
步骤S123，记数组visit[x]，其中，visit[x]表示第x行是否被访问过，初始全置为false，该行未被访问；
步骤S13，循环执行以下步骤S131～步骤S134，直至所有行均被访问：
步骤S131，在所有未被访问过的行里，选取包含1数量最少的行，假设是x行，即ones[x]的值最小；
步骤S132，枚举所有其他行，设行号为y，执行如下步骤S1321～S1322：
步骤S1321，计算x行与y行的汉明距离，即有多少列的元素不相同，记该值为dis；
步骤S1322，若dis<ones[y]，则表示需要将x行加至y行，于是将dis赋值给ones[y]，然后将from[y]的值改为x，最后将update的值设成true；
步骤S133，若from[x]的值不为-1，则将from[x]这一行加至第x行；
步骤S134，将visit[x]设成true，表示该行已经被访问；
步骤S14，若update的值为true，则返回步骤S11，否则算法结束。通过以上算法，反复利用初等行变换来提升校验矩阵的稀疏性，可以使某些编码的校验矩阵更为稀疏，从而具有更快的编码解码速度。
本发明适用于任意基于异或操作的纠删码，本发明通过对校验矩阵进行解码，从而对解码效率带来非常大的提升。另外，通过构造稀疏校验矩阵的迭代算法，能进一步提升本发明的解码效率。相比于传统的两种实现方法，本发明同时具有通用性和高效性。
本说明书中各个实施例采用递进的方式描述，每个实施例重点说明的都是与其他实施例的不同之处，各个实施例之间相同相似部分互相参见即可。
专业人员还可以进一步意识到，结合本文中所公开的实施例描述的各示例的单元及算法步骤，能够以电子硬件、计算机软件或者二者的结合来实现，为了清楚地说明硬件和软件的可互换性，在上述说明中已经按照功能一般性地描述了各示例的组成及步骤。这些功能究竟以硬件还是软件方式来执行，取决于技术方案的特定应用和设计约束条件。专业技术人员可以对每个特定的应用来使用不同方法来实现所描述的功能，但是这种实现不应认为超出本发明的范围。
显然，本领域的技术人员可以对发明进行各种改动和变型而不脱离本发明的精神和范围。这样，倘若本发明的这些修改和变型属于本发明权利要求及其等同技术的范围之内，则本发明也意图包括这些改动和变型在内。
Claims (7)
1.一种基于校验矩阵的纠删码解码方法，其特征在于，包括：
根据磁盘阵列的基于异或操作的纠删码的编码矩阵的编码方式，构造出对应于所述纠删码的校验矩阵，所述校验矩阵为一个01矩阵；
根据所述校验矩阵计算出磁盘阵列中失效磁盘的失效数据。
2.如权利要求1所述的基于校验矩阵的纠删码解码方法，其特征在于，根据所述校验矩阵计算出磁盘阵列中失效磁盘的失效数据，包括：
标记出磁盘阵列中存活数据S和失效磁盘的失效数据L；
将校验矩阵H分割成两个子矩阵HL和HS，分别对应于所述失效数据L和存活数据S；
利用等式即可通过校验矩阵计算磁盘阵列中失效磁盘的失效数据，其中，为01矩阵的广义逆矩阵。
3.如权利要求2所述的基于校验矩阵的纠删码解码方法，其特征在于，根据磁盘阵列的基于异或操作的纠删码的编码矩阵的编码方式，构造出对应于所述纠删码的校验矩阵中，
校验矩阵的行数等于纠删码的编码矩阵中的校验块的数量，校验矩阵的列数等于纠删码的编码矩阵中所有检验块和数据块的数量。
4.如权利要求3所述的基于校验矩阵的纠删码解码方法，其特征在于，根据磁盘阵列的基于异或操作的纠删码的编码矩阵的编码方式，构造出对应于所述纠删码的校验矩阵中，
校验矩阵的每一行对应所述编码矩阵的一个校验计算公式，每一列对应编码矩阵中的一个元素，当且仅当第j列对应的元素出现在第i个校验计算式子中时,校验矩阵的第i行j列的元素的值为1。
5.如权利要求4所述的基于校验矩阵的纠删码解码方法，其特征在于，根据磁盘阵列的基于异或操作的纠删码的编码矩阵的编码方式，构造出对应于所述纠删码的校验矩阵中，
所述校验矩阵为稀疏校验矩阵。
6.如权利要求5所述的基于校验矩阵的纠删码解码方法，其特征在于，所述稀疏校验矩阵通过初等变换得到。
7.如权利要求6所述的基于校验矩阵的纠删码解码方法，其特征在于，所述稀疏校验矩阵通过如下迭代算法构造得到：
步骤S11，设置变量update，表示一轮迭代中校验矩阵是更新，初始值设置为false；
步骤S12，初始化过程，包括步骤S121～步骤S123：
步骤S121，计算数组ones[x]，其中，数组ones[x]表示校验矩阵第x行所包含的1的数量；
步骤S122，记数组from[x]，其中from[x]表示第x行存放该行与哪一行之和，初始值为-1表示不存放任何其他行；
步骤S123，记数组visit[x]，其中，visit[x]表示第x行是否被访问过，初始全置为false，该行未被访问；
步骤S13，循环执行以下步骤S131～步骤S134，直至所有行均被访问：
步骤S131，在所有未被访问过的行里，选取包含1数量最少的行，假设是x行，即ones[x]的值最小；
步骤S132，枚举所有其他行，设行号为y，执行如下步骤S1321～S1322：
步骤S1321，计算x行与y行的汉明距离，即有多少列的元素不相同，记该值为dis；
步骤S1322，若dis<ones[y]，则将dis赋值给ones[y]，然后将from[y]的值改为x，最后将update的值设成true；
步骤S133，若from[x]的值不为-1，则将from[x]这一行加至第x行；
步骤S134，将visit[x]设成true，表示该行已经被访问；
步骤S14，若update的值为true，则返回步骤S11，否则算法结束。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201510290040.9A CN104850468B (zh) | 2015-05-31 | 2015-05-31 | 基于校验矩阵的纠删码解码方法 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201510290040.9A CN104850468B (zh) | 2015-05-31 | 2015-05-31 | 基于校验矩阵的纠删码解码方法 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN104850468A true CN104850468A (zh) | 2015-08-19 |
| CN104850468B CN104850468B (zh) | 2018-04-27 |
Family
ID=53850123
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201510290040.9A Active CN104850468B (zh) | 2015-05-31 | 2015-05-31 | 基于校验矩阵的纠删码解码方法 |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN104850468B (zh) |
Cited By (20)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| TWI573147B (zh) * | 2015-11-05 | 2017-03-01 | 大心電子股份有限公司 | 解碼方法、記憶體儲存裝置及記憶體控制電路單元 |
| CN106484559A (zh) * | 2016-10-17 | 2017-03-08 | 成都信息工程大学 | 一种校验矩阵的构造方法及水平阵列纠删码的构造方法 |
| CN108132854A (zh) * | 2018-01-15 | 2018-06-08 | 成都信息工程大学 | 一种可同时恢复数据元素及冗余元素的纠删码解码方法 |
| CN108733503A (zh) * | 2017-04-24 | 2018-11-02 | 慧与发展有限责任合伙企业 | 在分布式存储系统中存储数据 |
| CN109086000A (zh) * | 2018-06-22 | 2018-12-25 | 浙江工业大学 | 一种raid存储系统中的三容错数据布局方法 |
| US10210044B2 (en) | 2016-12-24 | 2019-02-19 | Huawei Technologies Co., Ltd | Storage controller, data processing chip, and data processing method |
| US10230398B2 (en) | 2016-08-19 | 2019-03-12 | Samsung Electronics Co., Ltd. | Erasure code data protection and recovery computation system and method |
| CN110071727A (zh) * | 2019-04-26 | 2019-07-30 | 成都海光集成电路设计有限公司 | 编码方法、译码方法、纠错方法及装置 |
| WO2019227456A1 (zh) * | 2018-06-01 | 2019-12-05 | 东莞理工学院 | 一种evenodd码的构造方法 |
| CN111090540A (zh) * | 2019-06-24 | 2020-05-01 | 华为技术有限公司 | 基于纠删码的数据处理方法与装置 |
| CN111541512A (zh) * | 2020-03-13 | 2020-08-14 | 中国科学院深圳先进技术研究院 | 数据的处理方法、终端设备、可读存储介质 |
| CN111679793A (zh) * | 2020-06-16 | 2020-09-18 | 成都信息工程大学 | 一种基于star码的单盘故障快速恢复方法 |
| CN107665152B (zh) * | 2017-07-02 | 2020-10-16 | 成都信息工程大学 | 一类纠删码的译码方法 |
| WO2020238736A1 (zh) * | 2019-05-28 | 2020-12-03 | 阿里巴巴集团控股有限公司 | 一种生成解码矩阵的方法、解码方法和对应装置 |
| WO2021098665A1 (zh) * | 2019-11-18 | 2021-05-27 | 北京中电兴发科技有限公司 | 一种纠删码计算方法 |
| US11038533B2 (en) | 2019-04-25 | 2021-06-15 | International Business Machines Corporation | Expansion for generalized EVENODD codes |
| CN113391946A (zh) * | 2021-05-25 | 2021-09-14 | 杭州电子科技大学 | 一种分布式存储中的纠删码的编解码方法 |
| CN113452479A (zh) * | 2021-06-08 | 2021-09-28 | 东莞理工学院 | Evenodd码的编码方法及其解码方法 |
| CN114153393A (zh) * | 2021-11-29 | 2022-03-08 | 山东云海国创云计算装备产业创新中心有限公司 | 一种数据编码方法、系统、设备以及介质 |
| CN114333917A (zh) * | 2021-12-30 | 2022-04-12 | 山东云海国创云计算装备产业创新中心有限公司 | 基于rdp纠删算法的数据纠错方法、装置、设备及介质 |
Citations (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US20030237019A1 (en) * | 2002-06-24 | 2003-12-25 | Kleiman Steven R. | Using file system information in RAID data reconstruction and migration |
| CN1889367A (zh) * | 2005-06-28 | 2007-01-03 | 松下电器产业株式会社 | 构造稀疏生成矩阵的方法及低密度分组校验码的编码方法 |
| CN101588183A (zh) * | 2009-06-26 | 2009-11-25 | 北京交通大学 | 一种ldpc码快速编码方法与系统 |
| WO2010073570A1 (ja) * | 2008-12-26 | 2010-07-01 | パナソニック株式会社 | 符号化方法、符号化器及び復号器 |
| CN102521067A (zh) * | 2011-12-01 | 2012-06-27 | 华中科技大学 | 优化部分条带写性能的raid-6编码和重构方法 |
| CN102833040A (zh) * | 2012-08-03 | 2012-12-19 | 中兴通讯股份有限公司 | 解码处理方法、装置及编解码系统 |
-
2015
- 2015-05-31 CN CN201510290040.9A patent/CN104850468B/zh active Active
Patent Citations (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US20030237019A1 (en) * | 2002-06-24 | 2003-12-25 | Kleiman Steven R. | Using file system information in RAID data reconstruction and migration |
| CN1889367A (zh) * | 2005-06-28 | 2007-01-03 | 松下电器产业株式会社 | 构造稀疏生成矩阵的方法及低密度分组校验码的编码方法 |
| WO2010073570A1 (ja) * | 2008-12-26 | 2010-07-01 | パナソニック株式会社 | 符号化方法、符号化器及び復号器 |
| CN101588183A (zh) * | 2009-06-26 | 2009-11-25 | 北京交通大学 | 一种ldpc码快速编码方法与系统 |
| CN102521067A (zh) * | 2011-12-01 | 2012-06-27 | 华中科技大学 | 优化部分条带写性能的raid-6编码和重构方法 |
| CN102833040A (zh) * | 2012-08-03 | 2012-12-19 | 中兴通讯股份有限公司 | 解码处理方法、装置及编解码系统 |
Non-Patent Citations (1)
| Title |
|---|
| 蒋海波: "海量数据存储系统的高可靠性关键技术研究与应用", 《中国博士学位论文全文数据库 信息科技辑》 * |
Cited By (31)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| TWI573147B (zh) * | 2015-11-05 | 2017-03-01 | 大心電子股份有限公司 | 解碼方法、記憶體儲存裝置及記憶體控制電路單元 |
| US10230398B2 (en) | 2016-08-19 | 2019-03-12 | Samsung Electronics Co., Ltd. | Erasure code data protection and recovery computation system and method |
| CN106484559A (zh) * | 2016-10-17 | 2017-03-08 | 成都信息工程大学 | 一种校验矩阵的构造方法及水平阵列纠删码的构造方法 |
| WO2018072294A1 (zh) * | 2016-10-17 | 2018-04-26 | 成都信息工程大学 | 一种校验矩阵的构造方法及水平阵列纠删码的构造方法 |
| CN110089035A (zh) * | 2016-12-24 | 2019-08-02 | 华为技术有限公司 | 存储控制器、数据处理芯片及数据处理方法 |
| US10210044B2 (en) | 2016-12-24 | 2019-02-19 | Huawei Technologies Co., Ltd | Storage controller, data processing chip, and data processing method |
| CN108733503B (zh) * | 2017-04-24 | 2021-10-01 | 慧与发展有限责任合伙企业 | 存储节点、分布式存储系统以及用于存储数据的方法 |
| CN108733503A (zh) * | 2017-04-24 | 2018-11-02 | 慧与发展有限责任合伙企业 | 在分布式存储系统中存储数据 |
| CN107665152B (zh) * | 2017-07-02 | 2020-10-16 | 成都信息工程大学 | 一类纠删码的译码方法 |
| CN108132854B (zh) * | 2018-01-15 | 2020-11-17 | 成都信息工程大学 | 一种可同时恢复数据元素及冗余元素的纠删码解码方法 |
| CN108132854A (zh) * | 2018-01-15 | 2018-06-08 | 成都信息工程大学 | 一种可同时恢复数据元素及冗余元素的纠删码解码方法 |
| WO2019227456A1 (zh) * | 2018-06-01 | 2019-12-05 | 东莞理工学院 | 一种evenodd码的构造方法 |
| CN109086000B (zh) * | 2018-06-22 | 2021-08-03 | 浙江工业大学 | 一种raid存储系统中的三容错数据布局方法 |
| CN109086000A (zh) * | 2018-06-22 | 2018-12-25 | 浙江工业大学 | 一种raid存储系统中的三容错数据布局方法 |
| US11038533B2 (en) | 2019-04-25 | 2021-06-15 | International Business Machines Corporation | Expansion for generalized EVENODD codes |
| CN110071727A (zh) * | 2019-04-26 | 2019-07-30 | 成都海光集成电路设计有限公司 | 编码方法、译码方法、纠错方法及装置 |
| WO2020238736A1 (zh) * | 2019-05-28 | 2020-12-03 | 阿里巴巴集团控股有限公司 | 一种生成解码矩阵的方法、解码方法和对应装置 |
| CN111090540A (zh) * | 2019-06-24 | 2020-05-01 | 华为技术有限公司 | 基于纠删码的数据处理方法与装置 |
| CN111090540B (zh) * | 2019-06-24 | 2022-06-14 | 华为技术有限公司 | 基于纠删码的数据处理方法与装置 |
| US11249846B2 (en) | 2019-06-24 | 2022-02-15 | Huawei Technologies Co., Ltd. | Erasure code-based data processing method and apparatus |
| US11303302B2 (en) | 2019-11-18 | 2022-04-12 | BEIJING iChinaE SCIENCE & TECHNOLOGY CO., LTD. | Erasure code calculation method |
| WO2021098665A1 (zh) * | 2019-11-18 | 2021-05-27 | 北京中电兴发科技有限公司 | 一种纠删码计算方法 |
| CN111541512A (zh) * | 2020-03-13 | 2020-08-14 | 中国科学院深圳先进技术研究院 | 数据的处理方法、终端设备、可读存储介质 |
| CN111679793A (zh) * | 2020-06-16 | 2020-09-18 | 成都信息工程大学 | 一种基于star码的单盘故障快速恢复方法 |
| CN111679793B (zh) * | 2020-06-16 | 2023-03-14 | 成都信息工程大学 | 一种基于star码的单盘故障快速恢复方法 |
| CN113391946A (zh) * | 2021-05-25 | 2021-09-14 | 杭州电子科技大学 | 一种分布式存储中的纠删码的编解码方法 |
| CN113391946B (zh) * | 2021-05-25 | 2022-06-17 | 杭州电子科技大学 | 一种分布式存储中的纠删码的编解码方法 |
| CN113452479A (zh) * | 2021-06-08 | 2021-09-28 | 东莞理工学院 | Evenodd码的编码方法及其解码方法 |
| CN114153393A (zh) * | 2021-11-29 | 2022-03-08 | 山东云海国创云计算装备产业创新中心有限公司 | 一种数据编码方法、系统、设备以及介质 |
| CN114333917A (zh) * | 2021-12-30 | 2022-04-12 | 山东云海国创云计算装备产业创新中心有限公司 | 基于rdp纠删算法的数据纠错方法、装置、设备及介质 |
| CN114333917B (zh) * | 2021-12-30 | 2023-11-03 | 山东云海国创云计算装备产业创新中心有限公司 | 基于rdp纠删算法的数据纠错方法、装置、设备及介质 |
Also Published As
| Publication number | Publication date |
|---|---|
| CN104850468B (zh) | 2018-04-27 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN104850468B (zh) | 基于校验矩阵的纠删码解码方法 | |
| Tuckett et al. | Fault-tolerant thresholds for the surface code in excess of 5% under biased noise | |
| CN111078460B (zh) | 一种快速纠删码计算方法 | |
| WO2018072294A1 (zh) | 一种校验矩阵的构造方法及水平阵列纠删码的构造方法 | |
| US8522125B1 (en) | System and method for efficient horizontal maximum distance separable raid | |
| US10425106B2 (en) | Balanced Reed-Solomon codes | |
| CN105553485B (zh) | 基于fpga的bch编解码装置及其编解码方法 | |
| CN113297001B (zh) | 一种raid编解码方法及编解码电路 | |
| CN110941505A (zh) | 产生错误校正电路的方法 | |
| CN103746774A (zh) | 一种高效数据读取的容错编码方法 | |
| CN110750381B (zh) | 基于nand flash存储器的纠错方法及装置 | |
| WO2023151288A1 (zh) | 校验数据生成方法、装置、设备及存储介质 | |
| CN110837436A (zh) | 有限域上高效纠删码轻量化自动解码方法、智能终端模块 | |
| CN104866243A (zh) | 优化输入输出负载的raid-6横向斜向校验编码及解码方法 | |
| CN107665152B (zh) | 一类纠删码的译码方法 | |
| CN104866386B (zh) | 具有最优更新代价的编码及解码方法 | |
| CN104932836B (zh) | 一种提高单写性能的三盘容错编码和解码方法 | |
| CN109496298A (zh) | 一种evenodd码的构造方法 | |
| CN103151078A (zh) | 一种存储器检错纠错码生成方法 | |
| CN104508982B (zh) | 组合的块符号纠错 | |
| Liang et al. | An optimal recovery approach for liberation codes in distributed storage systems | |
| US10404282B2 (en) | Apparatuses and methods for integrated interleaved Reed-Solomon encoding and decoding | |
| CN110990188B (zh) | 一种基于Hadamard矩阵的部分重复码的构造方法 | |
| JP2023552994A (ja) | プログラム可能な誤り訂正コードの符号化及び復号論理 | |
| CN111988437B (zh) | 一种通用的Expanded-Blaum-Roth码的编码方法及其解码方法 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| C06 | Publication | ||
| PB01 | Publication | ||
| EXSB | Decision made by sipo to initiate substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |