# A Novel Decoding Method for the Erasure Codes

Authors: Dan Tang; Hongliang Cai
Journal: Security and Communication Networks
 (2021)

---

## Abstract

The erasure codes are widely used in the distributed storage with low redundancy compared to the replication method. However, the current research studies about the erasure codes mainly focus on the encoding methods, while there are few studies on the decoding methods. In this paper, a novel erasure decoding method is proposed; it is a general decoding method and can be used both over the multivariate finite field and the binary finite field. The decoding of the failures can be realized based on the transforming process of the decoding transformation matrix, and it is convenient to avoid the overburdened visiting problem by tiny modification of the method. The correctness of the method is proved by the theoretical analysis; the experiments about the comparison with the traditional methods show that the proposed method has better decoding efficiency and lower reconstruction bandwidth.


---

## Body

## 1. Introduction

Erasure coding is a widely used method in the distributed storage system to protect against the failures of the storage nodes; it can provide better failure tolerance and much lower storage redundancy. The original information is first divided intok blocks; then, the k blocks are encoded into n blocks using the encoding method; when there are less than n−k blocks missed, the lost blocks can be recovered by the decoding method. There are a lot of research studies about the encoding methods, while only a few studies focus on the decoding methods.The typical erasure codes are RS (Reed–Solomon) erasure code and the array codes [1, 2]. The most important property for the RS erasure code [3–5] is that it is MDS (Maximum Distance Separable) code, which means the RS code can provide the optimal failure recovery ability in a certain data redundancy. A storage system based on the RS erasure code can achieve the optimal tradeoff between the storage redundancy and the ability of the failure tolerance. Moreover, the tolerated failures are not restricted as the fixed number as the array codes.However, the typical decoding method of the RS code is the equation solving method [6] over the finite field GFq, and it is equivalent to the matrix inversion method and has very high computational complexity. Therefore, many research studies make efforts to optimize the decoding computation of the RS code. Some research studies improve the decoding efficiency by developing the improved decoding method, for example, the merge decoding method in [7] can be used for RS decoding, but it is in fact the modified method of the traditional equation solving method. Some other research studies improve the decoding efficiency by speeding up the operations over the finite field, for example, a finite field operation library GF-Complete in [8] is developed by Professor James S. Plank; it can speed up the multiplication operation on the finite field by optimizing the bottom SSE instruction, but it does not make any fundamental improvement to reduce the decoding complexity. In this paper, we will improve the decoding efficiency by developing a novel decoding method, and the method of optimizing the operations over the finite field is out of the scope of our research.The array codes are another kind of the erasure codes widely used in the storage system. Since the two-dimensional coding structure of the array code is highly compatible with the disk array layout in some storage systems, the array codes are often used in the RAID system. The array codes with MDS property can tolerate only 2 or 3 failures [9, 10], while the array codes tolerating more failures are usually non-MDS array codes [3, 11, 12].The advantage of the array codes is that the computational efficiency of the encoding and decoding is high because they are performed overGF2, which means only the XOR operations are used in the encoding and the decoding.The typical decoding method of the array codes is the loop iterative method [9–14]; most of the array codes use it as the decoding method, such as X code [10], EVENODD code [9], and RDP code [15]. The decoding is realized by continuously selecting the generating equation with only one missing data block, and the missing data block is recovered from the renewed generating equations of the check blocks. In general, the iterative method can be used for most of the array codes constructed from the perspective of the geometry, and it cannot apply for the array codes constructed from the perspective of the algebra [16, 17].The equation solving method in [6] not only can be used for the RS code but it also can be used for other erasure codes; it is in fact a general decoding method over the field GFq. And, the loop iteration method can be regarded as the general decoding method for different array codes over the field GF2. There are only few research studies about the general decoding method for the different erasure codes over GF2 and GFq. The matrix decoding method in [18] over the binary field GF2 and the merging decoding method in [7] over the field GF2m are two typical general decoding methods. The advantage of the matrix decoding method in [18] is that the matrix inversion operation is not necessary in the decoding process, and the disadvantage is that it only can deal with the case that the invalid blocks are the original data blocks. When there are some original blocks and check blocks invalid, it needs firstly to recover the original blocks and then recalculate the lost check blocks again. It cannot decode directly to recover the check blocks directly in the decoding process. The merge decoding method in [7] can be regarded as the modified method of the traditional equation solving method in [6], which do not actually eliminate the matrix inversion operation. So the decoding performance of the method is gradually closer to the equation solving method while the failures increasingly reach the upper bound of the failure tolerance.The organization of this paper is as follows: Section2 is the preliminary for the proposed method. Section 3 proposes the detailed decoding process, and the proof and the analysis are also given out. And, Section 4 shows some experiments about the comparison between the proposed method and other decoding methods. At last, the conclusion is made in Section 5.


## 2. Preliminary

The finite field is an important concept in the coding theory. The basic concepts and important properties about the finite field can be found in [19]. In this paper, the finite field is constructed as in [20]. It has the property that the inverse element of the addition operation is itself, so the finite field used in this paper is GF2m, which is an important premising constituent of the proposed method in this paper.


### 2.1. The Generator Matrix and the Check Matrix

In then,k linear block code, the original information is divided into k symbols; then, the k symbols are encoded into n symbols which are called as the codeword.Then,k linear code of dimension k and block length n over the GF(q) is in fact a k-dimension subspace GFqk of the space GFqn. And, the k-dimension subspace can be completely spanned by the base composed of k linear independent vectors.Assume that the base of the subspace is shown as (1), where gi,j∈GFq, iandj are integers, 0≤i≤k−1 and 0≤j≤n−1:(1)C0=g0,0,g0,1,…,g0,n−1T,C1=g1,0,g1,1,…g1,n−1T,⋮Ck−1=gk−1,0,gk−1,1,…,gk−1,n−1T.Joint the vectors into a matrix:(2)G=g0,0g0,1…g0,k−1g1,0g1,1…g1,k−1⋮⋮⋱⋮gn−1,0gn−1,1…gn−1,k−1.Supposed is the vector about the original information symbols:(3)d=d0,d1,…,dk−1T.Based on the property [21] that any codeword of the n,k linear block code can be generated by the linear combination of the base, so the codeword C=c0,c1,…,cn−1 can be generated by multiplying the matrix G by the vector d:(4)C=G∗d=g0,0g0,1…g0,k−1g1,0g1,1…g1,k−1⋮⋮⋱⋮gn−1,0gn−1,1…gn−1,k−1⋅d0d1⋮dk−1.Then×k matrix G is called as the generator matrix. And, its rank is k, where gi,j∈GFq. The generator matrix is not unique, and any n×k matrix G with rank k can be used as the generator matrix of the n,k linear block code.There is a linear relationship between the elements ofC=c0,c1,…,cn−1:(5)h0,0c0+h0,1c1+⋯+h0,k−1ck−1=ckh1,0c+h1,1c1+⋯+h1,k−1ck−1=ck+1⋮⋮⋮⋮⋱⋮⋮⋮⋮hn−k−1,0c0+hn−k−1,1c1+⋯+hn−k−1,k−1ck−1=cn−1.The finite field has the property that the inverse element of the addition operation is itself [20]. So (5) can be turned into(6)h0,0c0+h0,1c1+⋯+ck0…0=0h1,0c0+h1,1c1+⋯+0ck+1…0=0⋮⋮⋮⋮⋱⋮⋮⋮⋱⋮⋮⋮hn−k−1,0c0+hn−k−1,1c1+⋯+00…cn−1=0.Equation (6) can be expressed as H⋅C=0:(7)h0,0h0,1…h0,k−110…0h1,0h1,1…h1,k−101…0⋮⋮⋱⋮⋮⋮⋱⋮hn−k−1,0hn−k−1,1…hn−k−1,k−100…1⋅c0c1⋮cn−1=00⋮0,H=h0,0h0,1…h0,k−110…0h1,0h1,1…h1,k−101…0⋮⋮⋱⋮⋮⋮⋱⋮hn−k−1,0hn−k−1,1…hn−k−1,k−100…1.The matrixH is called as the check matrix, and the ith row corresponds to the check equation for the ith check symbol independently, so the different rows can be swapped. The jth column is the coefficients related to the jth symbol, so the different columns cannot be swapped because it will corrupt the linear combination relationship.The basic idea of the decoding method based on the equation solving is as follows. Suppose that there aren−k symbols that are invalid in the codeword; extract the responding rows in matrix G to get the new matrix G¯, C¯=G¯⋅d, so C¯ is the remaining k valid symbols. As any k rows of the matrix G are linear independent, so the matrix G¯ is reversible, and the inverse matrix is denoted as G¯′. Then, multiply G¯′ in both sides of C¯=G¯⋅d, and we can get G¯′.C¯=G¯′.G¯⋅d. As G¯′.G¯=I, so the original data vector can be obtained by d=G¯′⋅C¯.


### 2.2. Linear Relation Matrix and Its Properties

The linear relation matrix is an important concept in the proposed decoding method; the definition of the linear relation matrix is shown as below.Definition 1.
Linear relation matrix.
From the generation of then symbols in the codeword of the n,k linear block code, we can know that they can be represented as the linear combination of the n symbols, as shown in the following equation:(8)c0=a0,0c0+a0,1c1+⋯+a0,n−1cn−1c1=a1,0c0+a1,1c1+⋯+a1,n−1cn−1⋮⋮⋮⋮⋮⋮⋱⋮⋮cn−1=an−1,0c0+an−1,1c1+⋯+an−1,n−1cn−1.
The nonhomogeneous linear equation system is called as the linear relation equation system, and the matrix of the coefficients can be called as the linear relation matrix.
Suppose that the linear relation matrix for then,k linear block code is W:(9)W=a0,0a0,1…a0,n−1a1,0a1,1…a1,n−1⋮⋮⋱⋮an−1,0an−1,1…an−1,n−1,where ai,j∈GFq, iandj are the integers, 0≤i≤n−1 and 0≤j≤n−1. We can get the linear relationship of the ith symbol ci by the ith row vector of W.
Take the (5,3) linear code overGF23 for example; suppose that the linear relation matrix of the code is W1:(10)W1=0762020730320407650052700.
So, we can getc0=7c1+6c2+2c3, c1=2c0+7c2+3c3, and so on.
There are two properties about the transformation of the linear relation matrix, which are important for the proposed decoding method.Property 1.
The result of any elementary row transformation on the linear relation matrix is no longer a linear relation matrix.Proof.
In this paper, we propose a novel method for the erasure codes for the storage system which is different from the replication method, so the erasure codes do not include the repetition code which is in fact the replication method; there are three cases for the elementary row transformation overGFq [21]:Case 1.
Multiply one row of the matrix byt, where t∈GFq and t≠0;Case 2.
Multiply one row of the matrix byt and add the result to another row, where t∈GFq and t≠0;Case 3.
Exchange any two rows in the matrix.
For the three row transformation cases, if the transformed matrix is still the relation matrix or not is discussed, respectively.
For Case 1, from the definition of the linear relation matrix, theith row in the linear relation matrix represents the linear combination about ci, i is an integer and 0≤i≤n−1:(11)ci=ai,0c0+ai,1c1+⋯+ai,n−1cn−1.
Multiply theith row by nonzero t; the ith row is changed into t⋅ai,0,t⋅ai,1,…,t⋅ai,n−1. Multiply t in the both sides of (11):(12)t⋅ci=t⋅ai,0c0+ai,1c1+⋯+ai,n−1cn−1.
Sincet is nonzero, obviously,(13)ci≠t⋅ai,0c0+ai,1c1+⋯+ai,n−1cn−1.
It is clear that theith symbol cannot be represented by the renewed ith row vector t⋅ai,0,t⋅ai,1,…,t⋅ai,n−1, so we can derive that multiplying the row of the matrix by nonzero t makes the matrix no longer a linear relation matrix.
For Case 2, multiply thejth row of the matrix by nonzero t and add the result to the ith row, and the ith row is changed into t⋅aj,0+ai,0,…,t⋅aj,n−1+ai,n−1. As cj=aj,0c0+aj,1c1+⋯+aj,n−1cn−1, multiply the both sides by nonzero t and add (11), and we can get(14)t⋅cj+ci=t⋅aj,0+ai,0c0+⋯+t⋅aj,n−1+ai,n−1cn−1,where i and j are integers and 0≤iandj≤n−1.
Sincet≠0, thus t⋅cj+ci≠ci. ci obviously cannot be represented by the row vector t⋅aj,0+ai,0,…,t⋅aj,n−1+ai,n−1, so the transformed matrix in Case 2 will not be a linear relation matrix.
For Case 3, from the definition of the linear relation matrix, theith row of the matrix represents the ith symbol ci, and it cannot be used to represent the jth symbol cj, and it is obvious that exchanging any two rows of the matrix makes it no longer a linear relation matrix.Property 2.
For the vectorv=v0,v1,…,vn−1, if v0c0+v1c1+⋯+vn−1cn−1=0, ci,vi,andt∈GFq. Multiply the vector v by t and add the result to ith row of the linear relation matrix W, and it is still a linear relation matrix.Proof.
From the definition of the linear relation matrix, theith row vector ai,0,ai,1,…,ai,n−1 is the linear combination of ci,ci=ai,0c0+ai,1c1+⋯+ai,n−1cn−1.
After multiplying the vectorv by t and adding the result to ith row of W, the ith row of the renewed linear matrix becomes ai,0+tv0,…,ai,n−1+tvn−1.
Asv0c0+v1c1+⋯+vn−1cn−1=0, so we can know that(15)tv0c0+tv1c1+⋯+tvn−1cn−1=t⋅0=0.
Add equation (16) to equation (11), and we can get the result:(16)ci=ai,0c0+⋯+ai,n−1cn−1+tv0c0+⋯+tvn−1cn−1.
Merge the similar items:(17)ci=ai,0+tv0c0+⋯+ai,n−1+tvn−1cn−1.
Obviously, the row vectorai,0+tv0,…,ai,n−1+tvn−1 is still the linear representation of the ith symbol ci. So, the renewed matrix after the row transformation is still a linear relation matrix.


## 2.1. The Generator Matrix and the Check Matrix

In then,k linear block code, the original information is divided into k symbols; then, the k symbols are encoded into n symbols which are called as the codeword.Then,k linear code of dimension k and block length n over the GF(q) is in fact a k-dimension subspace GFqk of the space GFqn. And, the k-dimension subspace can be completely spanned by the base composed of k linear independent vectors.Assume that the base of the subspace is shown as (1), where gi,j∈GFq, iandj are integers, 0≤i≤k−1 and 0≤j≤n−1:(1)C0=g0,0,g0,1,…,g0,n−1T,C1=g1,0,g1,1,…g1,n−1T,⋮Ck−1=gk−1,0,gk−1,1,…,gk−1,n−1T.Joint the vectors into a matrix:(2)G=g0,0g0,1…g0,k−1g1,0g1,1…g1,k−1⋮⋮⋱⋮gn−1,0gn−1,1…gn−1,k−1.Supposed is the vector about the original information symbols:(3)d=d0,d1,…,dk−1T.Based on the property [21] that any codeword of the n,k linear block code can be generated by the linear combination of the base, so the codeword C=c0,c1,…,cn−1 can be generated by multiplying the matrix G by the vector d:(4)C=G∗d=g0,0g0,1…g0,k−1g1,0g1,1…g1,k−1⋮⋮⋱⋮gn−1,0gn−1,1…gn−1,k−1⋅d0d1⋮dk−1.Then×k matrix G is called as the generator matrix. And, its rank is k, where gi,j∈GFq. The generator matrix is not unique, and any n×k matrix G with rank k can be used as the generator matrix of the n,k linear block code.There is a linear relationship between the elements ofC=c0,c1,…,cn−1:(5)h0,0c0+h0,1c1+⋯+h0,k−1ck−1=ckh1,0c+h1,1c1+⋯+h1,k−1ck−1=ck+1⋮⋮⋮⋮⋱⋮⋮⋮⋮hn−k−1,0c0+hn−k−1,1c1+⋯+hn−k−1,k−1ck−1=cn−1.The finite field has the property that the inverse element of the addition operation is itself [20]. So (5) can be turned into(6)h0,0c0+h0,1c1+⋯+ck0…0=0h1,0c0+h1,1c1+⋯+0ck+1…0=0⋮⋮⋮⋮⋱⋮⋮⋮⋱⋮⋮⋮hn−k−1,0c0+hn−k−1,1c1+⋯+00…cn−1=0.Equation (6) can be expressed as H⋅C=0:(7)h0,0h0,1…h0,k−110…0h1,0h1,1…h1,k−101…0⋮⋮⋱⋮⋮⋮⋱⋮hn−k−1,0hn−k−1,1…hn−k−1,k−100…1⋅c0c1⋮cn−1=00⋮0,H=h0,0h0,1…h0,k−110…0h1,0h1,1…h1,k−101…0⋮⋮⋱⋮⋮⋮⋱⋮hn−k−1,0hn−k−1,1…hn−k−1,k−100…1.The matrixH is called as the check matrix, and the ith row corresponds to the check equation for the ith check symbol independently, so the different rows can be swapped. The jth column is the coefficients related to the jth symbol, so the different columns cannot be swapped because it will corrupt the linear combination relationship.The basic idea of the decoding method based on the equation solving is as follows. Suppose that there aren−k symbols that are invalid in the codeword; extract the responding rows in matrix G to get the new matrix G¯, C¯=G¯⋅d, so C¯ is the remaining k valid symbols. As any k rows of the matrix G are linear independent, so the matrix G¯ is reversible, and the inverse matrix is denoted as G¯′. Then, multiply G¯′ in both sides of C¯=G¯⋅d, and we can get G¯′.C¯=G¯′.G¯⋅d. As G¯′.G¯=I, so the original data vector can be obtained by d=G¯′⋅C¯.


## 2.2. Linear Relation Matrix and Its Properties

The linear relation matrix is an important concept in the proposed decoding method; the definition of the linear relation matrix is shown as below.Definition 1.
Linear relation matrix.
From the generation of then symbols in the codeword of the n,k linear block code, we can know that they can be represented as the linear combination of the n symbols, as shown in the following equation:(8)c0=a0,0c0+a0,1c1+⋯+a0,n−1cn−1c1=a1,0c0+a1,1c1+⋯+a1,n−1cn−1⋮⋮⋮⋮⋮⋮⋱⋮⋮cn−1=an−1,0c0+an−1,1c1+⋯+an−1,n−1cn−1.
The nonhomogeneous linear equation system is called as the linear relation equation system, and the matrix of the coefficients can be called as the linear relation matrix.
Suppose that the linear relation matrix for then,k linear block code is W:(9)W=a0,0a0,1…a0,n−1a1,0a1,1…a1,n−1⋮⋮⋱⋮an−1,0an−1,1…an−1,n−1,where ai,j∈GFq, iandj are the integers, 0≤i≤n−1 and 0≤j≤n−1. We can get the linear relationship of the ith symbol ci by the ith row vector of W.
Take the (5,3) linear code overGF23 for example; suppose that the linear relation matrix of the code is W1:(10)W1=0762020730320407650052700.
So, we can getc0=7c1+6c2+2c3, c1=2c0+7c2+3c3, and so on.
There are two properties about the transformation of the linear relation matrix, which are important for the proposed decoding method.Property 1.
The result of any elementary row transformation on the linear relation matrix is no longer a linear relation matrix.Proof.
In this paper, we propose a novel method for the erasure codes for the storage system which is different from the replication method, so the erasure codes do not include the repetition code which is in fact the replication method; there are three cases for the elementary row transformation overGFq [21]:Case 1.
Multiply one row of the matrix byt, where t∈GFq and t≠0;Case 2.
Multiply one row of the matrix byt and add the result to another row, where t∈GFq and t≠0;Case 3.
Exchange any two rows in the matrix.
For the three row transformation cases, if the transformed matrix is still the relation matrix or not is discussed, respectively.
For Case 1, from the definition of the linear relation matrix, theith row in the linear relation matrix represents the linear combination about ci, i is an integer and 0≤i≤n−1:(11)ci=ai,0c0+ai,1c1+⋯+ai,n−1cn−1.
Multiply theith row by nonzero t; the ith row is changed into t⋅ai,0,t⋅ai,1,…,t⋅ai,n−1. Multiply t in the both sides of (11):(12)t⋅ci=t⋅ai,0c0+ai,1c1+⋯+ai,n−1cn−1.
Sincet is nonzero, obviously,(13)ci≠t⋅ai,0c0+ai,1c1+⋯+ai,n−1cn−1.
It is clear that theith symbol cannot be represented by the renewed ith row vector t⋅ai,0,t⋅ai,1,…,t⋅ai,n−1, so we can derive that multiplying the row of the matrix by nonzero t makes the matrix no longer a linear relation matrix.
For Case 2, multiply thejth row of the matrix by nonzero t and add the result to the ith row, and the ith row is changed into t⋅aj,0+ai,0,…,t⋅aj,n−1+ai,n−1. As cj=aj,0c0+aj,1c1+⋯+aj,n−1cn−1, multiply the both sides by nonzero t and add (11), and we can get(14)t⋅cj+ci=t⋅aj,0+ai,0c0+⋯+t⋅aj,n−1+ai,n−1cn−1,where i and j are integers and 0≤iandj≤n−1.
Sincet≠0, thus t⋅cj+ci≠ci. ci obviously cannot be represented by the row vector t⋅aj,0+ai,0,…,t⋅aj,n−1+ai,n−1, so the transformed matrix in Case 2 will not be a linear relation matrix.
For Case 3, from the definition of the linear relation matrix, theith row of the matrix represents the ith symbol ci, and it cannot be used to represent the jth symbol cj, and it is obvious that exchanging any two rows of the matrix makes it no longer a linear relation matrix.Property 2.
For the vectorv=v0,v1,…,vn−1, if v0c0+v1c1+⋯+vn−1cn−1=0, ci,vi,andt∈GFq. Multiply the vector v by t and add the result to ith row of the linear relation matrix W, and it is still a linear relation matrix.Proof.
From the definition of the linear relation matrix, theith row vector ai,0,ai,1,…,ai,n−1 is the linear combination of ci,ci=ai,0c0+ai,1c1+⋯+ai,n−1cn−1.
After multiplying the vectorv by t and adding the result to ith row of W, the ith row of the renewed linear matrix becomes ai,0+tv0,…,ai,n−1+tvn−1.
Asv0c0+v1c1+⋯+vn−1cn−1=0, so we can know that(15)tv0c0+tv1c1+⋯+tvn−1cn−1=t⋅0=0.
Add equation (16) to equation (11), and we can get the result:(16)ci=ai,0c0+⋯+ai,n−1cn−1+tv0c0+⋯+tvn−1cn−1.
Merge the similar items:(17)ci=ai,0+tv0c0+⋯+ai,n−1+tvn−1cn−1.
Obviously, the row vectorai,0+tv0,…,ai,n−1+tvn−1 is still the linear representation of the ith symbol ci. So, the renewed matrix after the row transformation is still a linear relation matrix.


## 3. The Proposed Decoding Method for the Erasure Codes

In this paper, we will propose a novel decoding method mainly for the erasure codes in the storage system, such as RS code and array codes. The proposed decoding method is based on the property: for any elementei∈GFq, ei+ei=0, where q=2m, m is a positive integer.


### 3.1. The Decoding Process

Suppose that the original information is divided intok symbols, and they are encoded into n symbols c0,c1,…,cn−1 by the n,k erasure code. There are no more than n−k failures, and the set of failure symbols is marked as F, and the decoding can be achieved by the following steps.(1)
Generaten×n unit matrix W as the linear relation matrix:(18)Wn×n=10…001…0⋮⋮⋱⋮00…1.(2)
Then×n linear relation matrix W and the n−k×n check matrix H are combined into the 2n−k×n decoding transformation matrix S:(19)S2n−k×n=Wn×nHn−k×n=Sn×n∧Sn−k×n∨=a0,0a0,1…a0,n−1a1,0a1,1…a1,n−1⋮⋮⋱⋮a2n−k−1,0a2n−k−1,1…a2n−k−1,n−1.Based on the linear relation of the matrixH and W, we can know that the ith column of H and W both corresponds to ci, so the ith column of S also corresponds to ci.(3)
Select the failed symbolcj from F, j is an integer and 0≤j≤n−1. Find the nonzero elements in the jth column in S2n−k×n, and suppose that there are t nonzero elements, and the row indexes of the nonzero elements are denoted as the set NRj, NRj=nr0j,nr1j,…,nrt−1j.(4)
If there exists the elements greater than or equal ton in the set NRj, the first element is nraj, a∈0,1,2,…,t−1, and go to the Step 5; otherwise, it indicates that the symbol cj cannot be recovered.(5)
For each elementnrbj in NRj except nraj, b≠a, the nrbj row of S2n−k×n is renewed as following:(20)Snrbj,:+=Snraj,:⋅Snrbj,jSnraj,j.The operation of “A+=B” is the shorthand expression of “A=A+B,” which means the value of “A” is reassigned by the result of “A+B.”Then, deletenrbj from the set NRj.(6)
After all thenrbj rows are renewed, set all the elements in the nrajth row of S to be zero. Then, delete cj from the set F.(7)
Now, check whetherSn−k×n∨=0 or not; if yes, it means that the decoding process is terminated. If not, continue to execute the decoding operation.(8)
Repeat Step 3 to Step 7 untilSn−k×n∨=0; if all the elements in the set F are deleted, it means all the failure symbols can be recovered successfully. If there are still some elements in the set F, it means that these symbols cannot be recovered.(9)
In the last step, the uppern×n submatrix of the renewed S2n−k×n is still a linear relation matrix, and it can be used as the decoding matrix D. So, the kth row of the matrix D is the coefficients about the linear combination of the lost symbol ck by the remaining symbols. Thus, ck can be recovered:(21)ck=∑j=0nDk,j⋅cj,where Di,j is the element in the ith row and the jth column of matrix D, i and j are integers and 0≤iandj≤n−1.Based on the matrix transforming process about the decoding transforming matrix, the lost symbols deleted from the setF in (6) can be recovered over GFq no matter they are the original data symbols or the check symbols. If all the symbols are deleted from F, all the lost symbols can be recovered; if not, we also can know which part of symbols can be recovered.


### 3.2. Example of the Decoding

A5,3 erasure code over GF23 is constructed based on the Cauchy matrix, the original information 3,4,1, and encoded into 5 symbols 3,4,1,1,3, and the generator matrix G and the check matrix H are shown as follows:(22)G=100010001765527,(23)H=7651052701.Suppose thatc0 and c1 are lost, F=c0,c1, and the decoding process is as follows:(1)
Generate the5×5 unit matrix I as the initial linear relation matrix W.(2)
Combine the matrixW5×5 and H2×5 to get the initial decoding transformation matrix S,(24)S7×5=W5×5H2×5,=10000010000010000010000017651052701.(3)
Select the first elementc0 in the set F. Find all the elements in the first column of S, and the row indexes of the nonzero elements are NR0=0,5,6.(4)
There are two elements5,6 are greater than or equal to n, n=5, and it satisfies the condition for the next decoding step.(5)
Select the first element in5,6, and nraj=5, so for other elements 0,6 except 5 in NR0, execute the operations on the 0th and 6th row of S as follows:(25)S0,:+=S5,:⋅S0,0S5,0,S6,:+=S5,:⋅S6,0S5,0.Then, the element 0 and 6 are deleted from0,6.(6)
After the two rows are renewed, set all elements in the 5th row to be zero in the matrixS:(26)S==S5×5∧S2×5∨=07620010000010000010000010000001161.The elementc0 can be deleted from F=c0,c1; now, F=c1.(7)
Notice thatS2×5∨≠0, and go to the next decoding step.(8)
Select the next elementc1 from F, and find out the nonzero elements in 1st column, NR1=0,1,6.There is one element 6 which is greater thann, n=5, so for other elements 0,1, perform the operation on the 0th and 1st row of S:(27)S0,:+=S6,:⋅S0,1S6,1,S1,:+=S6,:⋅S1,1S6,1.Then, the element 0 and 1 are deleted from0,1. And, all the elements in the 6th row are set to be zero. The element c1 can be deleted from F=c1; now, F=:(28)S==S5×5∧S2×5∨=00237001610010000010000010000000000.Notice thatS2×5∨=0; it means that the maximum failure tolerance of the code has been reached. F= shows that all the failures c0,c1 can be recovered successfully.(9)
Now the upper5×5 submatrix of the renewed matrix S can be used as the decoding matrix D:(29)D=0023700161001000001000001.The two failure symbolsc0,c1 can be easily decoded:(30)c0=2c2+3c3+7c4=2⋅1+3⋅1+7⋅3=3,c1=1c2+6c3+1c4=1⋅1+6⋅1+1⋅3=4.The addition and the multiplication overGF(23) are operated based on the polynomial operations. At last, all the failure symbols are recovered successfully.


### 3.3. Proof

#### 3.3.1. Proof of the Method

In this section, we will give out two basic important theorems, and the correctness of the proposed method can be proved based on the theorems.Theorem 1.
Suppose thatS is the decoding transformation matrix of the n,k linear block code over the finite field GFq; after multiplying the jth row of S by t, the renewed matrix S is still the decoding transformation matrix, and the upper submatrix Sn×n∧ of the matrix S is still a linear relation matrix where q=2m, t≠0, t∈GFq, j is an integer, and n≤j≤2n−k−1.Proof.
Suppose that thejth row of S is aj,0,…,aj,n−1; after the transformation, the jth row is renewed as taj,0,…,taj,n−1.
From the construction of the decoding transformation matrixS, since the lower part Sn−k×n∨ in the beginning is the check matrix Hn−k×n, so we can get(31)aj,0c0+aj,1c1+⋯+aj,n−1cn−1=0,where j is an integer, n≤j≤2n−k−1.
Then, multiply thejth row of S by t:(32)t⋅aj,0c0+aj,1c1+⋯+aj,n−1cn−1=t⋅aj,0⋅c0+t⋅aj,1⋅c1+⋯+t⋅aj,n−1⋅cn−1=0.where j is an integer, n≤j≤2n−k−1.
It is obvious that the renewedjth row taj,0,…,taj,n−1 is still can be used to check c0,c1,…,cn−1. So, the renewed matrix S is still the decoding transformation matrix. And, the upper submatrix Sn×n∧ of the matrix S is still a linear relation matrix.Theorem 2.
Suppose thatS is the decoding transformation matrix of the n,k linear block code over the finite field GFq. After multiplying the jth row in the lower part by t and adding to the ith row, the upper submatrix Sn×n∧ of the renewed S is still a linear relation matrix, where q=2m, t≠0, t∈GFq, i and j are integers, n≤j≤2n−k−1 and 0≤i≤2n−k−1.Proof.
Suppose that theith row is ai,0,…,ai,n−1; the j th row is aj,0,…,aj,n−1 after the transformation the ith row is renewed as taj,0+ai,0,…,taj,n−1+ai,n−1. We can discuss it in two cases.Case 4.
Ifn≤i≤2n−k−1, the ith row is in the lower part of the matrix S, as the lower part Sn−k×n∨ in the beginning is the check matrix Hn−k×n:(33)ai,0c0+ai,1c1+⋯+ai,n−1cn−1=0,aj,0c0+aj,1c1+⋯+aj,n−1cn−1=0.
Multiply thejth row of the matrix S by t and add to the ith row; we can get(34)taj,0+ai,0c0+⋯+taj,n−1+ai,n−1cn−1=0.
The renewedith row taj,0+ai,0,…,taj,n−1+ai,n−1 still can be used as the check relationship for c0,c1,…,cn−1.Case 5.
If0≤i≤n−1, the ith row is in the upper part of the matrix S, as the upper part of S is the linear relation matrix, so(35)ai,0c0+ai,1c1+⋯+ai,n−1cn−1=ci.
Thejth row is in the lower part of the matrix S, as the lower part of the matrix S is the check matrix, so(36)aj,0c0+aj,1c1+⋯+aj,n−1cn−1=0.
Multiply thejth row in the lower part by t and add to the ith row in the upper part:(37)taj,0+ai,0c0+⋯+taj,n−1+ai,n−1cn−1=ci.
Obviously, the renewedith row taj,0+ai,0,…,taj,n−1+ai,n−1 is still the linear relationship of ci. So, Theorem 2 is valid.
Based on the two basic theorems, the proof can be described as follows.Proof.
In the proposed decoding method, the initial decoding transformation matrix is generated by joining the linear relation matrixW with the check matrix H; in Step 9, the upper part of S is the decoding matrix which is used to decode to recover the lost symbols.
So the key point to prove the correctness of the method is that, how to make sure the matrix transformation will not corrupt the property of the renewed upper matrixSn×n∧; it is still the relation matrix and can be used to show the linear combination about the symbols.
The key transformation in the decoding process is Step 5. As in Step 4, the selected elementnraj≥n; then, the nrajth row of S is multiplied by Sn×n∧ and added to the nrbjth row (b≠a).
Sincenraj≥n, it satisfies n≤nraj≤2n−k−1, so Step 5 is the case that the nrajth row in the lower part of S is multiplied by t and added to the nrbjth row, t =  Sn×n∧. From Theorem 2, the upper submatrix Sn×n∧ of the renewed S is still a linear relation matrix, and Sn×n∧ still can be used to show the linear relationship about the symbols, so in Step 9, we can decode to get the lost symbols by using the decoding matrix D=Sn×n∧.


#### 3.3.2. Analysis of the Algorithm Complexity

The complexity of the proposed method can be derived from the analysis about the decoding process. There are addition and multiplication operations over the finite field in the decoding because the multiplication over the finite field is much more time-consuming than the addition operation, so the complexity is generally evaluated by the multiplication operations.Most of the multiplication operations are executed in Step 5; thenrbjth row of S is renewed by multiplying the nrajth rows by t and adding to the nrbjth row. It is necessary to perform at most n multiplication operations over the finite field; suppose that there are p symbols missing, so the total multiplication operations need to be performed at most p⋅n times in the decoding. So, the complexity of this method is about op⋅n.The computational complexity of the equation solving method used in [6] is about On3, and the merge decoding method used in [7] performs decoding by the inversion of the check matrix, so the complexity is also about On3. The complex of the matrix method in [18] is O(M2), where M is the number of the ones in the row, M < n, so the complexity of the method is O(n2). The decoding method in EVENODD code [9], X code [10], and RDP [15] is the cyclic iteration method, and the decoding complexity is Onlogn, and the decoding method in [3] is also the cyclic iteration method, so the decoding complexity is Onlogn.From the complexity analysis and the comparison between the different methods, we can see that the complexity of the proposed method is nearly linear, and it is lower than other methods.Furthermore, there is another point in the proposed decoding method that is beneficial to improve the decoding efficiency and not as the decoding methods in [11, 15]; when the lost symbols contain both the original data symbols and the check symbols, it is necessary to recover the original symbols first and then perform the multiply operation by using the check matrix to get the lost check symbols. In contrast, the proposed method can decode to get the original data symbols and the check symbols directly, and it is not necessary to recalculate to get the lost check symbols after the decoding process, so the decoding efficiency can be further improved.


## 3.1. The Decoding Process

Suppose that the original information is divided intok symbols, and they are encoded into n symbols c0,c1,…,cn−1 by the n,k erasure code. There are no more than n−k failures, and the set of failure symbols is marked as F, and the decoding can be achieved by the following steps.(1)
Generaten×n unit matrix W as the linear relation matrix:(18)Wn×n=10…001…0⋮⋮⋱⋮00…1.(2)
Then×n linear relation matrix W and the n−k×n check matrix H are combined into the 2n−k×n decoding transformation matrix S:(19)S2n−k×n=Wn×nHn−k×n=Sn×n∧Sn−k×n∨=a0,0a0,1…a0,n−1a1,0a1,1…a1,n−1⋮⋮⋱⋮a2n−k−1,0a2n−k−1,1…a2n−k−1,n−1.Based on the linear relation of the matrixH and W, we can know that the ith column of H and W both corresponds to ci, so the ith column of S also corresponds to ci.(3)
Select the failed symbolcj from F, j is an integer and 0≤j≤n−1. Find the nonzero elements in the jth column in S2n−k×n, and suppose that there are t nonzero elements, and the row indexes of the nonzero elements are denoted as the set NRj, NRj=nr0j,nr1j,…,nrt−1j.(4)
If there exists the elements greater than or equal ton in the set NRj, the first element is nraj, a∈0,1,2,…,t−1, and go to the Step 5; otherwise, it indicates that the symbol cj cannot be recovered.(5)
For each elementnrbj in NRj except nraj, b≠a, the nrbj row of S2n−k×n is renewed as following:(20)Snrbj,:+=Snraj,:⋅Snrbj,jSnraj,j.The operation of “A+=B” is the shorthand expression of “A=A+B,” which means the value of “A” is reassigned by the result of “A+B.”Then, deletenrbj from the set NRj.(6)
After all thenrbj rows are renewed, set all the elements in the nrajth row of S to be zero. Then, delete cj from the set F.(7)
Now, check whetherSn−k×n∨=0 or not; if yes, it means that the decoding process is terminated. If not, continue to execute the decoding operation.(8)
Repeat Step 3 to Step 7 untilSn−k×n∨=0; if all the elements in the set F are deleted, it means all the failure symbols can be recovered successfully. If there are still some elements in the set F, it means that these symbols cannot be recovered.(9)
In the last step, the uppern×n submatrix of the renewed S2n−k×n is still a linear relation matrix, and it can be used as the decoding matrix D. So, the kth row of the matrix D is the coefficients about the linear combination of the lost symbol ck by the remaining symbols. Thus, ck can be recovered:(21)ck=∑j=0nDk,j⋅cj,where Di,j is the element in the ith row and the jth column of matrix D, i and j are integers and 0≤iandj≤n−1.Based on the matrix transforming process about the decoding transforming matrix, the lost symbols deleted from the setF in (6) can be recovered over GFq no matter they are the original data symbols or the check symbols. If all the symbols are deleted from F, all the lost symbols can be recovered; if not, we also can know which part of symbols can be recovered.


## 3.2. Example of the Decoding

A5,3 erasure code over GF23 is constructed based on the Cauchy matrix, the original information 3,4,1, and encoded into 5 symbols 3,4,1,1,3, and the generator matrix G and the check matrix H are shown as follows:(22)G=100010001765527,(23)H=7651052701.Suppose thatc0 and c1 are lost, F=c0,c1, and the decoding process is as follows:(1)
Generate the5×5 unit matrix I as the initial linear relation matrix W.(2)
Combine the matrixW5×5 and H2×5 to get the initial decoding transformation matrix S,(24)S7×5=W5×5H2×5,=10000010000010000010000017651052701.(3)
Select the first elementc0 in the set F. Find all the elements in the first column of S, and the row indexes of the nonzero elements are NR0=0,5,6.(4)
There are two elements5,6 are greater than or equal to n, n=5, and it satisfies the condition for the next decoding step.(5)
Select the first element in5,6, and nraj=5, so for other elements 0,6 except 5 in NR0, execute the operations on the 0th and 6th row of S as follows:(25)S0,:+=S5,:⋅S0,0S5,0,S6,:+=S5,:⋅S6,0S5,0.Then, the element 0 and 6 are deleted from0,6.(6)
After the two rows are renewed, set all elements in the 5th row to be zero in the matrixS:(26)S==S5×5∧S2×5∨=07620010000010000010000010000001161.The elementc0 can be deleted from F=c0,c1; now, F=c1.(7)
Notice thatS2×5∨≠0, and go to the next decoding step.(8)
Select the next elementc1 from F, and find out the nonzero elements in 1st column, NR1=0,1,6.There is one element 6 which is greater thann, n=5, so for other elements 0,1, perform the operation on the 0th and 1st row of S:(27)S0,:+=S6,:⋅S0,1S6,1,S1,:+=S6,:⋅S1,1S6,1.Then, the element 0 and 1 are deleted from0,1. And, all the elements in the 6th row are set to be zero. The element c1 can be deleted from F=c1; now, F=:(28)S==S5×5∧S2×5∨=00237001610010000010000010000000000.Notice thatS2×5∨=0; it means that the maximum failure tolerance of the code has been reached. F= shows that all the failures c0,c1 can be recovered successfully.(9)
Now the upper5×5 submatrix of the renewed matrix S can be used as the decoding matrix D:(29)D=0023700161001000001000001.The two failure symbolsc0,c1 can be easily decoded:(30)c0=2c2+3c3+7c4=2⋅1+3⋅1+7⋅3=3,c1=1c2+6c3+1c4=1⋅1+6⋅1+1⋅3=4.The addition and the multiplication overGF(23) are operated based on the polynomial operations. At last, all the failure symbols are recovered successfully.


## 3.3. Proof

### 3.3.1. Proof of the Method

In this section, we will give out two basic important theorems, and the correctness of the proposed method can be proved based on the theorems.Theorem 1.
Suppose thatS is the decoding transformation matrix of the n,k linear block code over the finite field GFq; after multiplying the jth row of S by t, the renewed matrix S is still the decoding transformation matrix, and the upper submatrix Sn×n∧ of the matrix S is still a linear relation matrix where q=2m, t≠0, t∈GFq, j is an integer, and n≤j≤2n−k−1.Proof.
Suppose that thejth row of S is aj,0,…,aj,n−1; after the transformation, the jth row is renewed as taj,0,…,taj,n−1.
From the construction of the decoding transformation matrixS, since the lower part Sn−k×n∨ in the beginning is the check matrix Hn−k×n, so we can get(31)aj,0c0+aj,1c1+⋯+aj,n−1cn−1=0,where j is an integer, n≤j≤2n−k−1.
Then, multiply thejth row of S by t:(32)t⋅aj,0c0+aj,1c1+⋯+aj,n−1cn−1=t⋅aj,0⋅c0+t⋅aj,1⋅c1+⋯+t⋅aj,n−1⋅cn−1=0.where j is an integer, n≤j≤2n−k−1.
It is obvious that the renewedjth row taj,0,…,taj,n−1 is still can be used to check c0,c1,…,cn−1. So, the renewed matrix S is still the decoding transformation matrix. And, the upper submatrix Sn×n∧ of the matrix S is still a linear relation matrix.Theorem 2.
Suppose thatS is the decoding transformation matrix of the n,k linear block code over the finite field GFq. After multiplying the jth row in the lower part by t and adding to the ith row, the upper submatrix Sn×n∧ of the renewed S is still a linear relation matrix, where q=2m, t≠0, t∈GFq, i and j are integers, n≤j≤2n−k−1 and 0≤i≤2n−k−1.Proof.
Suppose that theith row is ai,0,…,ai,n−1; the j th row is aj,0,…,aj,n−1 after the transformation the ith row is renewed as taj,0+ai,0,…,taj,n−1+ai,n−1. We can discuss it in two cases.Case 4.
Ifn≤i≤2n−k−1, the ith row is in the lower part of the matrix S, as the lower part Sn−k×n∨ in the beginning is the check matrix Hn−k×n:(33)ai,0c0+ai,1c1+⋯+ai,n−1cn−1=0,aj,0c0+aj,1c1+⋯+aj,n−1cn−1=0.
Multiply thejth row of the matrix S by t and add to the ith row; we can get(34)taj,0+ai,0c0+⋯+taj,n−1+ai,n−1cn−1=0.
The renewedith row taj,0+ai,0,…,taj,n−1+ai,n−1 still can be used as the check relationship for c0,c1,…,cn−1.Case 5.
If0≤i≤n−1, the ith row is in the upper part of the matrix S, as the upper part of S is the linear relation matrix, so(35)ai,0c0+ai,1c1+⋯+ai,n−1cn−1=ci.
Thejth row is in the lower part of the matrix S, as the lower part of the matrix S is the check matrix, so(36)aj,0c0+aj,1c1+⋯+aj,n−1cn−1=0.
Multiply thejth row in the lower part by t and add to the ith row in the upper part:(37)taj,0+ai,0c0+⋯+taj,n−1+ai,n−1cn−1=ci.
Obviously, the renewedith row taj,0+ai,0,…,taj,n−1+ai,n−1 is still the linear relationship of ci. So, Theorem 2 is valid.
Based on the two basic theorems, the proof can be described as follows.Proof.
In the proposed decoding method, the initial decoding transformation matrix is generated by joining the linear relation matrixW with the check matrix H; in Step 9, the upper part of S is the decoding matrix which is used to decode to recover the lost symbols.
So the key point to prove the correctness of the method is that, how to make sure the matrix transformation will not corrupt the property of the renewed upper matrixSn×n∧; it is still the relation matrix and can be used to show the linear combination about the symbols.
The key transformation in the decoding process is Step 5. As in Step 4, the selected elementnraj≥n; then, the nrajth row of S is multiplied by Sn×n∧ and added to the nrbjth row (b≠a).
Sincenraj≥n, it satisfies n≤nraj≤2n−k−1, so Step 5 is the case that the nrajth row in the lower part of S is multiplied by t and added to the nrbjth row, t =  Sn×n∧. From Theorem 2, the upper submatrix Sn×n∧ of the renewed S is still a linear relation matrix, and Sn×n∧ still can be used to show the linear relationship about the symbols, so in Step 9, we can decode to get the lost symbols by using the decoding matrix D=Sn×n∧.


### 3.3.2. Analysis of the Algorithm Complexity

The complexity of the proposed method can be derived from the analysis about the decoding process. There are addition and multiplication operations over the finite field in the decoding because the multiplication over the finite field is much more time-consuming than the addition operation, so the complexity is generally evaluated by the multiplication operations.Most of the multiplication operations are executed in Step 5; thenrbjth row of S is renewed by multiplying the nrajth rows by t and adding to the nrbjth row. It is necessary to perform at most n multiplication operations over the finite field; suppose that there are p symbols missing, so the total multiplication operations need to be performed at most p⋅n times in the decoding. So, the complexity of this method is about op⋅n.The computational complexity of the equation solving method used in [6] is about On3, and the merge decoding method used in [7] performs decoding by the inversion of the check matrix, so the complexity is also about On3. The complex of the matrix method in [18] is O(M2), where M is the number of the ones in the row, M < n, so the complexity of the method is O(n2). The decoding method in EVENODD code [9], X code [10], and RDP [15] is the cyclic iteration method, and the decoding complexity is Onlogn, and the decoding method in [3] is also the cyclic iteration method, so the decoding complexity is Onlogn.From the complexity analysis and the comparison between the different methods, we can see that the complexity of the proposed method is nearly linear, and it is lower than other methods.Furthermore, there is another point in the proposed decoding method that is beneficial to improve the decoding efficiency and not as the decoding methods in [11, 15]; when the lost symbols contain both the original data symbols and the check symbols, it is necessary to recover the original symbols first and then perform the multiply operation by using the check matrix to get the lost check symbols. In contrast, the proposed method can decode to get the original data symbols and the check symbols directly, and it is not necessary to recalculate to get the lost check symbols after the decoding process, so the decoding efficiency can be further improved.


## 3.3.1. Proof of the Method

In this section, we will give out two basic important theorems, and the correctness of the proposed method can be proved based on the theorems.Theorem 1.
Suppose thatS is the decoding transformation matrix of the n,k linear block code over the finite field GFq; after multiplying the jth row of S by t, the renewed matrix S is still the decoding transformation matrix, and the upper submatrix Sn×n∧ of the matrix S is still a linear relation matrix where q=2m, t≠0, t∈GFq, j is an integer, and n≤j≤2n−k−1.Proof.
Suppose that thejth row of S is aj,0,…,aj,n−1; after the transformation, the jth row is renewed as taj,0,…,taj,n−1.
From the construction of the decoding transformation matrixS, since the lower part Sn−k×n∨ in the beginning is the check matrix Hn−k×n, so we can get(31)aj,0c0+aj,1c1+⋯+aj,n−1cn−1=0,where j is an integer, n≤j≤2n−k−1.
Then, multiply thejth row of S by t:(32)t⋅aj,0c0+aj,1c1+⋯+aj,n−1cn−1=t⋅aj,0⋅c0+t⋅aj,1⋅c1+⋯+t⋅aj,n−1⋅cn−1=0.where j is an integer, n≤j≤2n−k−1.
It is obvious that the renewedjth row taj,0,…,taj,n−1 is still can be used to check c0,c1,…,cn−1. So, the renewed matrix S is still the decoding transformation matrix. And, the upper submatrix Sn×n∧ of the matrix S is still a linear relation matrix.Theorem 2.
Suppose thatS is the decoding transformation matrix of the n,k linear block code over the finite field GFq. After multiplying the jth row in the lower part by t and adding to the ith row, the upper submatrix Sn×n∧ of the renewed S is still a linear relation matrix, where q=2m, t≠0, t∈GFq, i and j are integers, n≤j≤2n−k−1 and 0≤i≤2n−k−1.Proof.
Suppose that theith row is ai,0,…,ai,n−1; the j th row is aj,0,…,aj,n−1 after the transformation the ith row is renewed as taj,0+ai,0,…,taj,n−1+ai,n−1. We can discuss it in two cases.Case 4.
Ifn≤i≤2n−k−1, the ith row is in the lower part of the matrix S, as the lower part Sn−k×n∨ in the beginning is the check matrix Hn−k×n:(33)ai,0c0+ai,1c1+⋯+ai,n−1cn−1=0,aj,0c0+aj,1c1+⋯+aj,n−1cn−1=0.
Multiply thejth row of the matrix S by t and add to the ith row; we can get(34)taj,0+ai,0c0+⋯+taj,n−1+ai,n−1cn−1=0.
The renewedith row taj,0+ai,0,…,taj,n−1+ai,n−1 still can be used as the check relationship for c0,c1,…,cn−1.Case 5.
If0≤i≤n−1, the ith row is in the upper part of the matrix S, as the upper part of S is the linear relation matrix, so(35)ai,0c0+ai,1c1+⋯+ai,n−1cn−1=ci.
Thejth row is in the lower part of the matrix S, as the lower part of the matrix S is the check matrix, so(36)aj,0c0+aj,1c1+⋯+aj,n−1cn−1=0.
Multiply thejth row in the lower part by t and add to the ith row in the upper part:(37)taj,0+ai,0c0+⋯+taj,n−1+ai,n−1cn−1=ci.
Obviously, the renewedith row taj,0+ai,0,…,taj,n−1+ai,n−1 is still the linear relationship of ci. So, Theorem 2 is valid.
Based on the two basic theorems, the proof can be described as follows.Proof.
In the proposed decoding method, the initial decoding transformation matrix is generated by joining the linear relation matrixW with the check matrix H; in Step 9, the upper part of S is the decoding matrix which is used to decode to recover the lost symbols.
So the key point to prove the correctness of the method is that, how to make sure the matrix transformation will not corrupt the property of the renewed upper matrixSn×n∧; it is still the relation matrix and can be used to show the linear combination about the symbols.
The key transformation in the decoding process is Step 5. As in Step 4, the selected elementnraj≥n; then, the nrajth row of S is multiplied by Sn×n∧ and added to the nrbjth row (b≠a).
Sincenraj≥n, it satisfies n≤nraj≤2n−k−1, so Step 5 is the case that the nrajth row in the lower part of S is multiplied by t and added to the nrbjth row, t =  Sn×n∧. From Theorem 2, the upper submatrix Sn×n∧ of the renewed S is still a linear relation matrix, and Sn×n∧ still can be used to show the linear relationship about the symbols, so in Step 9, we can decode to get the lost symbols by using the decoding matrix D=Sn×n∧.


## 3.3.2. Analysis of the Algorithm Complexity

The complexity of the proposed method can be derived from the analysis about the decoding process. There are addition and multiplication operations over the finite field in the decoding because the multiplication over the finite field is much more time-consuming than the addition operation, so the complexity is generally evaluated by the multiplication operations.Most of the multiplication operations are executed in Step 5; thenrbjth row of S is renewed by multiplying the nrajth rows by t and adding to the nrbjth row. It is necessary to perform at most n multiplication operations over the finite field; suppose that there are p symbols missing, so the total multiplication operations need to be performed at most p⋅n times in the decoding. So, the complexity of this method is about op⋅n.The computational complexity of the equation solving method used in [6] is about On3, and the merge decoding method used in [7] performs decoding by the inversion of the check matrix, so the complexity is also about On3. The complex of the matrix method in [18] is O(M2), where M is the number of the ones in the row, M < n, so the complexity of the method is O(n2). The decoding method in EVENODD code [9], X code [10], and RDP [15] is the cyclic iteration method, and the decoding complexity is Onlogn, and the decoding method in [3] is also the cyclic iteration method, so the decoding complexity is Onlogn.From the complexity analysis and the comparison between the different methods, we can see that the complexity of the proposed method is nearly linear, and it is lower than other methods.Furthermore, there is another point in the proposed decoding method that is beneficial to improve the decoding efficiency and not as the decoding methods in [11, 15]; when the lost symbols contain both the original data symbols and the check symbols, it is necessary to recover the original symbols first and then perform the multiply operation by using the check matrix to get the lost check symbols. In contrast, the proposed method can decode to get the original data symbols and the check symbols directly, and it is not necessary to recalculate to get the lost check symbols after the decoding process, so the decoding efficiency can be further improved.


## 4. Experiments and Analysis

In this section, some experiments about the evaluation of the decoding performance of different decoding methods are given out by simulation.As we all know, there are two typical kinds of erasure codes, RS code, and array codes, so the proposed decoding method is compared with the decoding methods for different kinds of erasure codes.For the RS code, the proposed decoding method is compared with the equation solving method in [6] and the merge decoding method in [7]. For the array codes, the proposed decoding method is compared with the loop iteration method in X code [10], EVENODD code [9], RDP code [15], and iteration decoding method in the slope code [3]. The decoding method in [18] is also compared with the proposed method by the typical array code.The reconstruct bandwidth is another advantage of the method by tiny modification. To evaluate the reconstruction bandwidth, the comparison of the performance of different array codes is given out.At last, the strategy of involved nodes in the decoding to reduce the burden is proposed.


### 4.1. Time Efficiency of Failure Recovery

For RS erasure codes, we will compare our method with the equation solving method in [6] and the merge decoding method in [7]. The Cauchy RS code is used as the failure tolerance method in the simulation.Experiment 1.
Suppose that the erasure code is CRS (4,8) erasure code overGF28; there are 8 independent storage nodes, including 4 original data nodes and 4 check nodes, and it is clear that it can tolerate at most 4 failures.
Suppose that the storage block size in each storage node is 14,376B. The network bandwidth is enough for the data transmission in the distributed storage system. The fieldGF28 is constructed by using the method in [20].
Assume that there are 1, 2, 3, and 4 nodes’ failures in the storage system, respectively. We will decode by using the equation solving method in [6], the merge decoding method in [7], and the proposed decoding method. The comparison of time consumption is shown in Table 1.
From the table, we can see that the decoding performance of the proposed method is much better than both the merge decoding method and the equation solving method. And, the decoding time of the merge decoding method in [7] is lower than the equation solving method in [6] when there is one node failure, but the decoding time is higher in the case of multiple nodes’ failure.
For the array codes, the most common decoding method is the cyclic iteration method, so the proposed method is compared with the cyclic iteration method in Experiments2 and 3.
In Experiment2, the proposed decoding method is compared with the iteration decoding method for EVENODD code [9], X code [10], and RDP code [15].Table 1
The decoding time of different nodes’ failure.
Method in [6]Method in [7]The proposed method1 node’ failure191.0764.11 s15.06 s2 nodes’ failure856.831357.3 s29.78 s3 nodes’ failure1438.62619.89 s47.11 s4 nodes’ failure1499.133077.47 s62.93 sExperiment 2.
For EVENODD code [9], X code [10], and RDP code [15], use the proposed method and the cyclic iteration method as the decoding method, respectively. Assume that the file size is 1,228,800B and the maximum storage block size of each storage node is 10,240 bits. The decoding performance about the different methods is shown in Table 2.
From the table, we can see that the time efficiency in the decoding using our method is better than the method in [9, 10, 15].Table 2
The decoding time of the different methods.
EVENODD decode [9]X decode [10]RDP decode [15]Original decode method1.491.51 s1.62 sThe proposed decode method1.381.42 s1.48 sExperiment 3.
For the slope code [3], suppose that the strip size is 4 and the maximum failure tolerance is 4. From the construction of the slope code, there are 26 storage nodes including 13 data information nodes and 13 check information nodes. Suppose that the file size is 1,261,568B and the block in each storage node is 10,240B. Assume that the failure is from 1 to 4; use the cyclic iteration method and the proposed method as the decoding method for the different failure cases; the comparison of decoding efficiency is shown in Figure 1.
From this figure, we can know that the decoding efficiency of the proposed method in this paper is better than the traditional cyclic iteration method for the slope code.Figure 1
Time comparison of data recovery from multiple failure nodes.Experiment 4.
In this experiment, the decoding efficiency performance between the method in [18] and the proposed method is compared.
Take EVENODD code as the failure tolerance method. Suppose that the data size of each storage node is 10800B, and the decoding efficiency about one node failed is shown as Table3.
The decoding efficiency when there are two nodes failed is shown in Table4.
From the tables, we can see that the decoding efficiency of the proposed method is little better than the method in [18] when there is one node failed, but the decoding efficiency is much better when there are two nodes failed.
From the comparisons among the different decoding methods for RS codes and the array codes, we can draw the conclusion that the decoding efficiency of the proposed method is better than the other methods.Table 3
The decoding time of different file sizes when one node failed.
(KB)Method in [18]The proposed method2000.51 s0.58 s4001.06 s0.97 s6001.55 s1.50 s8002.11 s1.98 s10002.53 s2.46 sTable 4
The decoding time of different file sizes when two nodes failed.
(KB)Method in [18]The proposed method2002.65 s1.98 s4004.31 s3.71 s6006.75 s5.03 s8008.17 s5.21 s100010.25 s8.94 s


### 4.2. Reconstruction Bandwidth

In the distributed storage system based on the (n, k) erasure code, there will be a lot of data need to be transmitted even only one node is failed, which is called as the reconstruction bandwidth problem. So how to effectively reduce the amount of data transmitted is a hot topic in the distributed storage. Based on the basic idea of the regenerating code [22], our method can reduce the reconstruction bandwidth only by tiny modification.It only needs to add a judgment condition in Step 4 of the proposed method. When we select thenraj in Step 4, the element with the highest repetition rate of data blocks involved in the decoding will be selected. In other words, for every selection of nraj in the decoding, the row with the lowest hamming weight is selected.Experiment 5.
For the array codes including the EVENODD code [9], the X code [10], the RDP code [15], and the slope code [3], use the proposed method and the iteration method in [3, 9, 10, 15] as the decoding method. Assume that the file size is 1,261,568B, and the block size of each storage node is 10,240 bits. The comparison of the amount of data transmitted is shown in Figure 2, where the EVENODD code, the X code, and the RDP code are constructed based on the prime number 7.
From the figure, we can see that the number of the data blocks need to transmit in the proposed method for different erasure codes is lower than the iteration method in [3, 9, 10, 15].
The comparison of the decoding time is shown as Figure3, as the decoding complexity of the proposed method is lower than the cyclic method, and the amount of data transmitted in the decoding is less than the cyclic method, so from the figure we can see that the decoding efficiency of the proposed method is also better than the other methods.Figure 2
Network transmission blocks required for a single failure node reconstruction.Figure 3
Time comparison for a single failure node reconstruction.Experiment 6.
In the experiment, we will evaluate the reconstruction bandwidth and the recovery performance while the failed nodes are increased.
Suppose the distributed storage system is based on the slope code, the strip size is 5, and the maximum failure tolerance is 5. Assume the file size is 1,261,568B and the block size in each storage node is 10,240 bits; use the cyclic iteration method in [3] and the proposed method as the decoding method, and the transmitted data blocks required for the data reconstruction from 1 to 5 failures are shown in Table 5.
Obviously, the proposed method can reduce the amount of transmitting data in the decoding, which can also improve the decoding efficiency. The comparison of the decoding time from 1 to 5 failure nodes is shown in Table6.Table 5
The data blocks required for multiple failure nodes reconstruction.
Cyclic iteration methodThe proposed method1 node failed25202 node failed45363 node failed65504 node failed85675 node failed10574Table 6
The reconstruction time of multiple nodes failed.
Cyclic iteration method (s)The proposed method (s)1 node failed1.181.132 node failed2.071.953 node failed2.792.294 node failed3.882.945 node failed4.623.61


### 4.3. Design of Involved Nodes for Data Recovery

In the distributed storage system, it is possible that some nodes are visited frequently in a period of time, and it will undoubtedly increase the access burden of these overheated nodes and lead to the low efficiency. In the proposed method, it can dynamically select the involved nodes in the decoding to avoid the excessively visiting overheated nodes.Take the slope code as the example, assume that the strip size is 2 and the maximum failure tolerance is 2. The stripe of the slope code is shown in Figure4; in each strip, the first 3 blocks are the data blocks and the last 3 blocks are the parity blocks, and the layout of all the blocks is shown in Figure 4.Figure 4
A stripe based on the slope code.According to the definition of the slope code, the check matrixH of the slope code is shown as (38). Assume the node 1 is failed, so the blocks {0, 3} in node 1 are invalid, and the decoding matrix D based on the decoding method in this paper is shown as (39):(38)H=100010100000010001010000001100001000100001000100010100000010001010000001,(39)D=000010100000010000000000001000001000001000001000000010000000000001000000000000100000000000010000000000001000000000000100000000000010000000000001.From the decoding method in this paper, the failure blocks can be recovered by using the decoding matrixD,E0=E4+E6. It shows that the nodes {1, 2, 3, 4} will participate in the decoding of the failure blocks {0,3} based on the blocks’ layout, as shown in Figure 4.If the node 1 is visited frequently, to avoid visiting the node 1, we can assume that the node 1 is also failed, so the blocks {1, 4} in the node 1 are failed. Now, there are four blocks {0, 3, 1, 4} that failed, so the decoding matrixD is changed into the following equation:(40)D=001000100001000001010000001000001000001000001000001000000001000001000000000000100000000000010000000000001000000000000100000000000010000000000001.So, the failure blocks can be decoded based on the decoding matrix, andE0=E2+E6+E11, E3=E2+E8. We can find that the nodes {2, 3, 4, 5} will participate in the decoding of the blocks {0, 3}, and the node 1 will not be involved in the decoding.Furthermore, if the node 1 and 2 are overheated, we continue to assume that the node 1 and 2 are failed, so the six blocks {0, 1, 2, 3, 4, 5} are failed. In this situation, there is no valid decoding matrix that can be found. Therefore, we can know that the node 2 is the essential node for the decoding, and the decoding cannot be realized without the node 2.


## 4.1. Time Efficiency of Failure Recovery

For RS erasure codes, we will compare our method with the equation solving method in [6] and the merge decoding method in [7]. The Cauchy RS code is used as the failure tolerance method in the simulation.Experiment 1.
Suppose that the erasure code is CRS (4,8) erasure code overGF28; there are 8 independent storage nodes, including 4 original data nodes and 4 check nodes, and it is clear that it can tolerate at most 4 failures.
Suppose that the storage block size in each storage node is 14,376B. The network bandwidth is enough for the data transmission in the distributed storage system. The fieldGF28 is constructed by using the method in [20].
Assume that there are 1, 2, 3, and 4 nodes’ failures in the storage system, respectively. We will decode by using the equation solving method in [6], the merge decoding method in [7], and the proposed decoding method. The comparison of time consumption is shown in Table 1.
From the table, we can see that the decoding performance of the proposed method is much better than both the merge decoding method and the equation solving method. And, the decoding time of the merge decoding method in [7] is lower than the equation solving method in [6] when there is one node failure, but the decoding time is higher in the case of multiple nodes’ failure.
For the array codes, the most common decoding method is the cyclic iteration method, so the proposed method is compared with the cyclic iteration method in Experiments2 and 3.
In Experiment2, the proposed decoding method is compared with the iteration decoding method for EVENODD code [9], X code [10], and RDP code [15].Table 1
The decoding time of different nodes’ failure.
Method in [6]Method in [7]The proposed method1 node’ failure191.0764.11 s15.06 s2 nodes’ failure856.831357.3 s29.78 s3 nodes’ failure1438.62619.89 s47.11 s4 nodes’ failure1499.133077.47 s62.93 sExperiment 2.
For EVENODD code [9], X code [10], and RDP code [15], use the proposed method and the cyclic iteration method as the decoding method, respectively. Assume that the file size is 1,228,800B and the maximum storage block size of each storage node is 10,240 bits. The decoding performance about the different methods is shown in Table 2.
From the table, we can see that the time efficiency in the decoding using our method is better than the method in [9, 10, 15].Table 2
The decoding time of the different methods.
EVENODD decode [9]X decode [10]RDP decode [15]Original decode method1.491.51 s1.62 sThe proposed decode method1.381.42 s1.48 sExperiment 3.
For the slope code [3], suppose that the strip size is 4 and the maximum failure tolerance is 4. From the construction of the slope code, there are 26 storage nodes including 13 data information nodes and 13 check information nodes. Suppose that the file size is 1,261,568B and the block in each storage node is 10,240B. Assume that the failure is from 1 to 4; use the cyclic iteration method and the proposed method as the decoding method for the different failure cases; the comparison of decoding efficiency is shown in Figure 1.
From this figure, we can know that the decoding efficiency of the proposed method in this paper is better than the traditional cyclic iteration method for the slope code.Figure 1
Time comparison of data recovery from multiple failure nodes.Experiment 4.
In this experiment, the decoding efficiency performance between the method in [18] and the proposed method is compared.
Take EVENODD code as the failure tolerance method. Suppose that the data size of each storage node is 10800B, and the decoding efficiency about one node failed is shown as Table3.
The decoding efficiency when there are two nodes failed is shown in Table4.
From the tables, we can see that the decoding efficiency of the proposed method is little better than the method in [18] when there is one node failed, but the decoding efficiency is much better when there are two nodes failed.
From the comparisons among the different decoding methods for RS codes and the array codes, we can draw the conclusion that the decoding efficiency of the proposed method is better than the other methods.Table 3
The decoding time of different file sizes when one node failed.
(KB)Method in [18]The proposed method2000.51 s0.58 s4001.06 s0.97 s6001.55 s1.50 s8002.11 s1.98 s10002.53 s2.46 sTable 4
The decoding time of different file sizes when two nodes failed.
(KB)Method in [18]The proposed method2002.65 s1.98 s4004.31 s3.71 s6006.75 s5.03 s8008.17 s5.21 s100010.25 s8.94 s


## 4.2. Reconstruction Bandwidth

In the distributed storage system based on the (n, k) erasure code, there will be a lot of data need to be transmitted even only one node is failed, which is called as the reconstruction bandwidth problem. So how to effectively reduce the amount of data transmitted is a hot topic in the distributed storage. Based on the basic idea of the regenerating code [22], our method can reduce the reconstruction bandwidth only by tiny modification.It only needs to add a judgment condition in Step 4 of the proposed method. When we select thenraj in Step 4, the element with the highest repetition rate of data blocks involved in the decoding will be selected. In other words, for every selection of nraj in the decoding, the row with the lowest hamming weight is selected.Experiment 5.
For the array codes including the EVENODD code [9], the X code [10], the RDP code [15], and the slope code [3], use the proposed method and the iteration method in [3, 9, 10, 15] as the decoding method. Assume that the file size is 1,261,568B, and the block size of each storage node is 10,240 bits. The comparison of the amount of data transmitted is shown in Figure 2, where the EVENODD code, the X code, and the RDP code are constructed based on the prime number 7.
From the figure, we can see that the number of the data blocks need to transmit in the proposed method for different erasure codes is lower than the iteration method in [3, 9, 10, 15].
The comparison of the decoding time is shown as Figure3, as the decoding complexity of the proposed method is lower than the cyclic method, and the amount of data transmitted in the decoding is less than the cyclic method, so from the figure we can see that the decoding efficiency of the proposed method is also better than the other methods.Figure 2
Network transmission blocks required for a single failure node reconstruction.Figure 3
Time comparison for a single failure node reconstruction.Experiment 6.
In the experiment, we will evaluate the reconstruction bandwidth and the recovery performance while the failed nodes are increased.
Suppose the distributed storage system is based on the slope code, the strip size is 5, and the maximum failure tolerance is 5. Assume the file size is 1,261,568B and the block size in each storage node is 10,240 bits; use the cyclic iteration method in [3] and the proposed method as the decoding method, and the transmitted data blocks required for the data reconstruction from 1 to 5 failures are shown in Table 5.
Obviously, the proposed method can reduce the amount of transmitting data in the decoding, which can also improve the decoding efficiency. The comparison of the decoding time from 1 to 5 failure nodes is shown in Table6.Table 5
The data blocks required for multiple failure nodes reconstruction.
Cyclic iteration methodThe proposed method1 node failed25202 node failed45363 node failed65504 node failed85675 node failed10574Table 6
The reconstruction time of multiple nodes failed.
Cyclic iteration method (s)The proposed method (s)1 node failed1.181.132 node failed2.071.953 node failed2.792.294 node failed3.882.945 node failed4.623.61


## 4.3. Design of Involved Nodes for Data Recovery

In the distributed storage system, it is possible that some nodes are visited frequently in a period of time, and it will undoubtedly increase the access burden of these overheated nodes and lead to the low efficiency. In the proposed method, it can dynamically select the involved nodes in the decoding to avoid the excessively visiting overheated nodes.Take the slope code as the example, assume that the strip size is 2 and the maximum failure tolerance is 2. The stripe of the slope code is shown in Figure4; in each strip, the first 3 blocks are the data blocks and the last 3 blocks are the parity blocks, and the layout of all the blocks is shown in Figure 4.Figure 4
A stripe based on the slope code.According to the definition of the slope code, the check matrixH of the slope code is shown as (38). Assume the node 1 is failed, so the blocks {0, 3} in node 1 are invalid, and the decoding matrix D based on the decoding method in this paper is shown as (39):(38)H=100010100000010001010000001100001000100001000100010100000010001010000001,(39)D=000010100000010000000000001000001000001000001000000010000000000001000000000000100000000000010000000000001000000000000100000000000010000000000001.From the decoding method in this paper, the failure blocks can be recovered by using the decoding matrixD,E0=E4+E6. It shows that the nodes {1, 2, 3, 4} will participate in the decoding of the failure blocks {0,3} based on the blocks’ layout, as shown in Figure 4.If the node 1 is visited frequently, to avoid visiting the node 1, we can assume that the node 1 is also failed, so the blocks {1, 4} in the node 1 are failed. Now, there are four blocks {0, 3, 1, 4} that failed, so the decoding matrixD is changed into the following equation:(40)D=001000100001000001010000001000001000001000001000001000000001000001000000000000100000000000010000000000001000000000000100000000000010000000000001.So, the failure blocks can be decoded based on the decoding matrix, andE0=E2+E6+E11, E3=E2+E8. We can find that the nodes {2, 3, 4, 5} will participate in the decoding of the blocks {0, 3}, and the node 1 will not be involved in the decoding.Furthermore, if the node 1 and 2 are overheated, we continue to assume that the node 1 and 2 are failed, so the six blocks {0, 1, 2, 3, 4, 5} are failed. In this situation, there is no valid decoding matrix that can be found. Therefore, we can know that the node 2 is the essential node for the decoding, and the decoding cannot be realized without the node 2.


## 5. Conclusion

In this paper, the novel decoding method for the erasure codes is proposed, and it is a general decoding method to improve the decoding efficiency for different kinds of erasure codes over different finite fields. It is easy to get the linear combination of the failure symbols by other valid symbols by the simple matrix transformation of the decoding transformation matrix. For theRS codes over the binary extension field, the proposed method can eliminate the matrix inversion in the decoding, so the decoding efficiency is greatly improved. For the array codes, the proposed method is still useful for the XOR-based array codes over GF(2) to improve the decoding efficiency. Furthermore, the proposed method can effectively reduce the repair bandwidth for the array codes in the data reconstruction compared with the classical iteration method by tiny modification. Another improved strategy can be realized by dynamically planning the valid nodes that are involved in the decoding to lighten the overburdened storage nodes.



---

*Source: 8755697-2021-07-16.xml*