# PB: A Product-Bitmatrix Construction to Reduce the Complexity of XOR Operations of PM-MSR and PM-MBR Codes overGF2w

Authors: Chuqiao Xiao; Xueqing Gong; Yefeng Xia; Qian Zhang
Journal: Security and Communication Networks
 (2021)

---

## Abstract

Edge computing, as an emerging computing paradigm, aims to reduce network bandwidth transmission overhead while storing and processing data on edge nodes. However, the storage strategies required for edge nodes are different from those for existing data centers. Erasure code (EC) strategies have been applied in some decentralized storage systems to ensure the privacy and security of data storage. Product-matrix (PM) regenerating codes (RGCs) as a state-of-the-art EC family are designed to minimize the repair bandwidth overhead or minimize the storage overhead. Nevertheless, the high complexity of the PM framework contains more finite-domain multiplication operations than classical ECs, which heavily consumes computational resources at the edge nodes. In this paper, a theoretical derivation of each step of the PM minimum storage regeneration (PM-MSR) and PM minimum bandwidth regeneration (PM-MBR) codes is performed and the XOR complexity over finite fields is analyzed. On this basis, a new construct called product bitmatrix (PB) is designed to reduce the complexity of XOR operations in the PM framework, and two heuristics are used to further reduce the XOR numbers of the PB-MSR and PB-MBR codes, respectively. The evaluation results show that the PB construction significantly reduces the XOR number compared to the PM-MSR, PM-MBR, Reed–Solomon (RS), and Cauchy RS codes while retaining optimal performance and reliability.


---

## Body

## 1. Introduction

Edge computing has emerged as a new paradigm for addressing local computing needs and moving data computation or storage to an edge node near the end user [1–3]. In contrast to cloud storage built on a network, edge computing-based storage is distributed among the edges of the network structure [4, 5]. Consequently, these edge nodes are particularly in need of fault-tolerant techniques to ensure system reliability and availability and even more importantly to ensure data privacy and security [6]. Nowadays, whether it is a distributed storage system [7] or a decentralized system [8, 9], it needs to guarantee the storage reliability of the source data, and these systems have used an erasure code (EC) strategy as opposed to a replication strategy which has a higher storage overhead. [10]. The well-known Reed–Solomon (RS) codes or more generally, maximum distance separable codes (MDS), have been applied to many storage systems [11]. But in a word, an EC is essentially a particular linear combination of data symbols that involves a large number of finite field matrix product operations, and the calculation complexity over finite field is too high. There have been many studies on this issue [12–14]. In addition to the problem of high computational complexity over GF2w, another problem of EC is that their repair bandwidth is equal to the size of the entire source data [15]. It has been reported that, based on RS coding, an average of 95,500 coded blocks per day needs to be recovered, and more than 180 TB of data per day must be transmitted through the TOR switch for data recovery [16]. Recently, a new class of ECs called regenerating codes (RGCs) has emerged that trades off both storage overhead and repair bandwidth [17]. RGC maintains the same reliability as ECs, but both of them are calculated over a finite field. There are two principal RGC classes, namely, minimum storage regenerating (MSR) and minimum bandwidth regenerating (MBR) codes, which imply two extreme points in a trade-off known as the storage-repair bandwidth trade-off. There have been many frameworks designed for MSR and MBR codes, respectively [7, 18–20], but as far as we know, the product-matrix (PM) framework proposed by Rashmi et al. is the only framework that constructs two codes in a unified way [21], and the PM framework provides exact repair of PM-MSR 2k−2≤d and PM-MBR k≤d≤n−1 codes. While there has been some research on the optimization of extensions based on this framework, such as reducing the disk I/O overhead or dynamically changing the number of helper nodes according to system requests and network changes, these studies have not analyzed and optimized the framework itself [22–24]. In this paper, we focus on the PM framework, analyzing the computational complexity of the encoding, decoding, and repair processes over GF2w. Since the PM framework has a large number of XORs at each step, especially in the decoding process of the PM-MSR code, the computational complexity of the inversion of the Vandermonde matrix is On3. Therefore, we propose a new construction called product bitmatrix (PB). Our contributions include the following:(i)
The computational complexity of the PM-MSR and PM-MBR codes is strictly theoretically derived in combination with the finite field arithmetic operations.(ii)
A new construction called product bitmatrix for MSR and MBR codes is designed, and we elaborate on the encoding, decoding, and repair processes in detail.(iii)
Two new heuristic algorithms are presented that find a locally optimal PB which has low XORs, thereby reducing computational complexity. The experimental results show that the number of XORs dropped by 11.73% of the PB-MSR and 20.17% of the PB-MBR codes.The remainder of this paper is organized as follows. The background of the two codes and arithmetic complexity analysis over the finite field are analyzed in Section2. Section 3 is the analysis of the computational complexity of the encoding, decoding, and repair processes of the PM framework. In Section 4, a new PB construction is presented and implemented. In Section 5, two different heuristic algorithms are designed to find the locally optimal product bitmatrix that has the least number of XORs. Then, the results of many evaluation experiments conducted to verify the performance of optimization are presented in Section 6. Finally, Sections 7 and 8 are related works and conclusions.


## 2. Foundations

### 2.1. MSR and MBR Codes

RGCs are state-of-the-art ECs that aim to reduce the amount of data during the repair process, which means a new replacement node needs to connect to anyd helper nodes and download β symbols from each node. As shown in Figure 1, a comparison between the reconstruction and repair processes is presented. Any kα symbols in an α-level stripe are transferred to reconstruct origin symbols, while dβ symbols downloaded for repair are much smaller than the total size of B. It is shown in the following formula:(1)B≤∑i=0k−1minα,d−iβ.Figure 1
An example of parameters (n = 10, k = 5, d = 9): reconstruction by the data collector (DC) is shown on the left and repair by a new node when old node has failed is shown on the right.Since both storage overheadα and bandwidth overhead β are costs, it is desirable to minimize both α as well as β. In [17], when n,k,d,B are fixed values, there is a trade-off between α and β; the two extreme points in this trade-off are termed the MSR and MBR. Clearly, α,β of the minimum storage point is given by B/k,α/d−k+1, and at the the minimum bandwidth point of the trade-off, α,β is given by dβ,2B/k2d−k+1. RGC over GF2w is associated with a set of parameters n,k,d,α,β,B. A comparison about metrics between Replication, EC, MSR, and MBR is shown in Table 1.Table 1
Comparison of replication, EC, MSR, and MBR.
ReplicationErasure codeMSRMBRParameters−n,kn≥2k−1,k,d≥2k−2n,k,dStorage efficientRk/nk/nk/n2d−k+1/2d·k/nStorage overheadαB/kB/kB/kB/k·2d/2d−k+1Repair bandwidthγB/kBB/k⋅d/d−k+1B/k·2d/2d−k+1Disk access1kddAs shown in Table1, the upper bound of storage efficient RMBR code is reached (1/2) when k=d=n−1, but there is no such limitation of RMSR. For the sake of simplicity, if the size of a file is B = 6, n,k,d=6,3,5, the repair bandwidth γ of EC, MSR, and MBR is 6, 3.33, and 2.5,respectively, and the total storage overhead nα of EC, MSR, and MBR is 12, 12, and 15, respectively. Although the EC and MSR codes use the same storage, the repair bandwidth of EC is higher than MSR. MBR code is where storage space is allowed to expand, but repair bandwidth is at the lowest bound. The MSR codes minimize γ based on the optimal α, while the MBR codes minimize α under the optimal γ.


### 2.2. Finite Field Arithmetic Complexity

Since the finite field of prime size is not suitable for computers, the finite field of a size equal to a power of 2 is generally preferred. InGF2w, each element is represented by the formal power series, which is a way of writing infinite sequences of bits. For example, a and b are bit sequences over the finite field GF2; a=a0,a1,a2,a3,…;b=b0,b1,b2,b3,…. Addition of a and b could be easily done by bitwise XOR, but multiplication is more complicated, a·b=a0b0,a0b1+a1b0,…,∑i=0l−1aibl−1−i…, where l is length of sequence. A notation a(z) is used as a formal power series (polynomial) to represent an infinite sequence:(2)az=a0+a1z+a2z2+⋯+al−1zl−1.The multiplication overGF2w is performed by multiplying two polynomials with coefficients in binary field GF2 and then reducing the product by irreducible polynomials [25]. Hence, a polynomial represents a field element, and the set of polynomials is denoted by F2z. Due to the highest power series, dega(z) of a(z) is equal to w-1, and the sum of nonzero terms of polynomials as the weight of a(z) is denoted as az which equals w. The addition is a bitwise XOR operation whose complexity is w.For multiplication, wherecz:=azbz, there are two steps to compute complexity: compute the product and reduce while a(z), b(z)∈F2z, a(z)≠b(z).Step 1: in the \emph{product} stage, the complexity of this stage is the \emph{coefficients-XOR}, where(3)cz=a0b0+a1b0⊕a0b1z+a2b0⊕a1b1⊕a0b2z2+⋯+aw−1b0⊕aw−2b1⊕aw−3b2⊕⋯⊕a1bw−2⊕a0bw−1zw−1.For example,a0=1, a1=1, a2=1, b0=0, b1=1, b2=1. cz=0+0⊕1z+0⊕1⊕1z2+1⊕1z3+z4=z4+z. The sum of XORs is S=1+⋯+w−2+w−1+w−2+⋯+1=w−12, so the product stage is w−12.Step 2: in the second stage, ifdegc(z) ≥ w, c(z) is reduced by an irreducible polynomial g(z), until degc(z)  w. Let l = degc(z), and convert the term clzl to clgz−zwzl−w. Because an irreducible polynomial g(z) degree is w, h(z) = g(z)-zw, degh(z) = w′, and maximum weight of h(z) is w′+1.Dividec(z) into three polynomials: no-reduce part d(z), once-reduce part e(z), and twice-reduce part f(z) as shown in Table 2. While w−2+w′≤w−1, there is a nonexistent second reduction.Table 2
Dividingc(z) into three polynomials.
d(z)e(z)f(z)Power range0,w−1w,2w−w′−12w−w′,2w−2Maxweightww−w′w′−1Product XORs0w′2w−22+w′2Becausec(z) = d(z) + e(z) + f(z), the reduction part is as follows:(4)ez+fz=cwzw+cw+1zw+1+cw+2zw+2+⋯+c2w−2z2w−2=zwcw+cw+1z+cw+2z2+⋯+c2w−w′−1zw−w′−1+zwc2w−w′zw−w′+⋯+c2w−2zw−2=hzcw+cw+1z+cw+2z2+⋯+c2w−w′−1zw−w′−1+hzc2w−w′zw−w′+⋯+c2w−2zw−2.Therefore, theonce-reduce part e(z) has w′2 XORs. Then, we compute number of XORs of the twice-reduce part.Lethzc2w−w′zw−w′+⋯+c2w−2zw−2=hz∗mz, and the new polynomial mz=∑i=2w′zw−i,i∈2,w′, i∈2,w′; degm(z) = w−2 and mz=w′−1. Then, fz=f0+f1z+f1z2+⋯+fw+w′−2zw+w′−2 which needs w−22 XORs. And if w′≥1, f(z) also must be reduced.(5)fz=f0+f1z+⋯+fw−1zw−1+fwzw+⋯+fw+w′−2zw+w′−2=f0+f1z+⋯+fw−1zw−1+hzfw+⋯+fw+w′−2zw′−2︸product XORs isw′2=f0+f1z+⋯+fw−1zw−1+n0+n1z+⋯+nw−1z2w′−2︸addition XORs is2w′−2,where n(z) is a polynomial in which degnz=2w′−2. Thus, twice-reduce part f(z) needs w′2+w−22+2w′−1 XORs.Consequently, the sum of XORsμ of the field multiplication over GF2w including two steps of the addition XOR among three parts is(6)μ=XORstep1+XORstep2=w−12+w′2+w+w′2+w−22+2w′−1+w=2ww−2+2w′2w′+1+4.Generally, a multiplication operation overGF2w takes Ow2 bit operations. For example, when w = 3, multiplication results are as shown in Table 3. Because the finite field size equals 28 that corresponds to a byte in the computer, w is usually set to be an integral times of 8 to make encoding operations convenient.Table 3
Multiplication overGF23 while gz=z3+z+1 is an irreducible polynomial.
01xx+1x2x2+1x2+xx2+x+1000001010011100101110111000000000000100101xx+1x2x2+1x2+xx2+x+1x0100xx2x2+xx+11x2+x+1x2+1x+10110x+1x2+xx2+1x2+x+1x21xx21000x2x+1x2+x+1x2+xxx2+11x2+11010x2+11x2xx2+x+1x+1x2+xx2+x1100x2+xx2+x+11x2+1x+1xx2x2+x+11110x2+x+1x2+1x1x2+xx2x+1Matrix inversion is often used in EC decoding and repair processes. SupposeA is n×n matrix 3≤n, and A−1=A∗/A; the determinant of A is solved by trigonometric matrix. Elements in the solution process include addition and multiplication, which require ∑i=2nii−1μ+∑i=2nii−1w XORs. Adjoint matrix A∗is an (n × n) matrix composed of algebraic cofactors in which each element Ai,j equals the determinant value of A excluding row i and column j. Therefore, computing A∗ requires n2∑i=2n−1ii−1μ+n2∑i=2n−1ii−1w XORs.Consequently, the XORs of matrix inversion are(7)n2+1μ+w∑i=2n−1ii−1+nn−1μ+w=n3−3n2+2n3n2+1μ+w+nn−1μ+w=n5−3n4+4n3−n3μ+w.


## 2.1. MSR and MBR Codes

RGCs are state-of-the-art ECs that aim to reduce the amount of data during the repair process, which means a new replacement node needs to connect to anyd helper nodes and download β symbols from each node. As shown in Figure 1, a comparison between the reconstruction and repair processes is presented. Any kα symbols in an α-level stripe are transferred to reconstruct origin symbols, while dβ symbols downloaded for repair are much smaller than the total size of B. It is shown in the following formula:(1)B≤∑i=0k−1minα,d−iβ.Figure 1
An example of parameters (n = 10, k = 5, d = 9): reconstruction by the data collector (DC) is shown on the left and repair by a new node when old node has failed is shown on the right.Since both storage overheadα and bandwidth overhead β are costs, it is desirable to minimize both α as well as β. In [17], when n,k,d,B are fixed values, there is a trade-off between α and β; the two extreme points in this trade-off are termed the MSR and MBR. Clearly, α,β of the minimum storage point is given by B/k,α/d−k+1, and at the the minimum bandwidth point of the trade-off, α,β is given by dβ,2B/k2d−k+1. RGC over GF2w is associated with a set of parameters n,k,d,α,β,B. A comparison about metrics between Replication, EC, MSR, and MBR is shown in Table 1.Table 1
Comparison of replication, EC, MSR, and MBR.
ReplicationErasure codeMSRMBRParameters−n,kn≥2k−1,k,d≥2k−2n,k,dStorage efficientRk/nk/nk/n2d−k+1/2d·k/nStorage overheadαB/kB/kB/kB/k·2d/2d−k+1Repair bandwidthγB/kBB/k⋅d/d−k+1B/k·2d/2d−k+1Disk access1kddAs shown in Table1, the upper bound of storage efficient RMBR code is reached (1/2) when k=d=n−1, but there is no such limitation of RMSR. For the sake of simplicity, if the size of a file is B = 6, n,k,d=6,3,5, the repair bandwidth γ of EC, MSR, and MBR is 6, 3.33, and 2.5,respectively, and the total storage overhead nα of EC, MSR, and MBR is 12, 12, and 15, respectively. Although the EC and MSR codes use the same storage, the repair bandwidth of EC is higher than MSR. MBR code is where storage space is allowed to expand, but repair bandwidth is at the lowest bound. The MSR codes minimize γ based on the optimal α, while the MBR codes minimize α under the optimal γ.


## 2.2. Finite Field Arithmetic Complexity

Since the finite field of prime size is not suitable for computers, the finite field of a size equal to a power of 2 is generally preferred. InGF2w, each element is represented by the formal power series, which is a way of writing infinite sequences of bits. For example, a and b are bit sequences over the finite field GF2; a=a0,a1,a2,a3,…;b=b0,b1,b2,b3,…. Addition of a and b could be easily done by bitwise XOR, but multiplication is more complicated, a·b=a0b0,a0b1+a1b0,…,∑i=0l−1aibl−1−i…, where l is length of sequence. A notation a(z) is used as a formal power series (polynomial) to represent an infinite sequence:(2)az=a0+a1z+a2z2+⋯+al−1zl−1.The multiplication overGF2w is performed by multiplying two polynomials with coefficients in binary field GF2 and then reducing the product by irreducible polynomials [25]. Hence, a polynomial represents a field element, and the set of polynomials is denoted by F2z. Due to the highest power series, dega(z) of a(z) is equal to w-1, and the sum of nonzero terms of polynomials as the weight of a(z) is denoted as az which equals w. The addition is a bitwise XOR operation whose complexity is w.For multiplication, wherecz:=azbz, there are two steps to compute complexity: compute the product and reduce while a(z), b(z)∈F2z, a(z)≠b(z).Step 1: in the \emph{product} stage, the complexity of this stage is the \emph{coefficients-XOR}, where(3)cz=a0b0+a1b0⊕a0b1z+a2b0⊕a1b1⊕a0b2z2+⋯+aw−1b0⊕aw−2b1⊕aw−3b2⊕⋯⊕a1bw−2⊕a0bw−1zw−1.For example,a0=1, a1=1, a2=1, b0=0, b1=1, b2=1. cz=0+0⊕1z+0⊕1⊕1z2+1⊕1z3+z4=z4+z. The sum of XORs is S=1+⋯+w−2+w−1+w−2+⋯+1=w−12, so the product stage is w−12.Step 2: in the second stage, ifdegc(z) ≥ w, c(z) is reduced by an irreducible polynomial g(z), until degc(z)  w. Let l = degc(z), and convert the term clzl to clgz−zwzl−w. Because an irreducible polynomial g(z) degree is w, h(z) = g(z)-zw, degh(z) = w′, and maximum weight of h(z) is w′+1.Dividec(z) into three polynomials: no-reduce part d(z), once-reduce part e(z), and twice-reduce part f(z) as shown in Table 2. While w−2+w′≤w−1, there is a nonexistent second reduction.Table 2
Dividingc(z) into three polynomials.
d(z)e(z)f(z)Power range0,w−1w,2w−w′−12w−w′,2w−2Maxweightww−w′w′−1Product XORs0w′2w−22+w′2Becausec(z) = d(z) + e(z) + f(z), the reduction part is as follows:(4)ez+fz=cwzw+cw+1zw+1+cw+2zw+2+⋯+c2w−2z2w−2=zwcw+cw+1z+cw+2z2+⋯+c2w−w′−1zw−w′−1+zwc2w−w′zw−w′+⋯+c2w−2zw−2=hzcw+cw+1z+cw+2z2+⋯+c2w−w′−1zw−w′−1+hzc2w−w′zw−w′+⋯+c2w−2zw−2.Therefore, theonce-reduce part e(z) has w′2 XORs. Then, we compute number of XORs of the twice-reduce part.Lethzc2w−w′zw−w′+⋯+c2w−2zw−2=hz∗mz, and the new polynomial mz=∑i=2w′zw−i,i∈2,w′, i∈2,w′; degm(z) = w−2 and mz=w′−1. Then, fz=f0+f1z+f1z2+⋯+fw+w′−2zw+w′−2 which needs w−22 XORs. And if w′≥1, f(z) also must be reduced.(5)fz=f0+f1z+⋯+fw−1zw−1+fwzw+⋯+fw+w′−2zw+w′−2=f0+f1z+⋯+fw−1zw−1+hzfw+⋯+fw+w′−2zw′−2︸product XORs isw′2=f0+f1z+⋯+fw−1zw−1+n0+n1z+⋯+nw−1z2w′−2︸addition XORs is2w′−2,where n(z) is a polynomial in which degnz=2w′−2. Thus, twice-reduce part f(z) needs w′2+w−22+2w′−1 XORs.Consequently, the sum of XORsμ of the field multiplication over GF2w including two steps of the addition XOR among three parts is(6)μ=XORstep1+XORstep2=w−12+w′2+w+w′2+w−22+2w′−1+w=2ww−2+2w′2w′+1+4.Generally, a multiplication operation overGF2w takes Ow2 bit operations. For example, when w = 3, multiplication results are as shown in Table 3. Because the finite field size equals 28 that corresponds to a byte in the computer, w is usually set to be an integral times of 8 to make encoding operations convenient.Table 3
Multiplication overGF23 while gz=z3+z+1 is an irreducible polynomial.
01xx+1x2x2+1x2+xx2+x+1000001010011100101110111000000000000100101xx+1x2x2+1x2+xx2+x+1x0100xx2x2+xx+11x2+x+1x2+1x+10110x+1x2+xx2+1x2+x+1x21xx21000x2x+1x2+x+1x2+xxx2+11x2+11010x2+11x2xx2+x+1x+1x2+xx2+x1100x2+xx2+x+11x2+1x+1xx2x2+x+11110x2+x+1x2+1x1x2+xx2x+1Matrix inversion is often used in EC decoding and repair processes. SupposeA is n×n matrix 3≤n, and A−1=A∗/A; the determinant of A is solved by trigonometric matrix. Elements in the solution process include addition and multiplication, which require ∑i=2nii−1μ+∑i=2nii−1w XORs. Adjoint matrix A∗is an (n × n) matrix composed of algebraic cofactors in which each element Ai,j equals the determinant value of A excluding row i and column j. Therefore, computing A∗ requires n2∑i=2n−1ii−1μ+n2∑i=2n−1ii−1w XORs.Consequently, the XORs of matrix inversion are(7)n2+1μ+w∑i=2n−1ii−1+nn−1μ+w=n3−3n2+2n3n2+1μ+w+nn−1μ+w=n5−3n4+4n3−n3μ+w.


## 3. The Computational Complexity of PM-MSR and PM-MBR

The famous PM-RGC construction is introduced to provide MBR constructions for all feasible values of (n, k, d) and MSR constructions for all n,k,d≥2k−2[21]. A detailed description of the complexity of the PM-MSR and PM-MBR codes is presented in this section, where matrices are used in the framework listed in Table 4.Table 4
The PM framework matrix list.
NotationSizeNameMMSR:d×α,MBR:d×dMessage matrixS1,S2α×αSymmetric matrixSk×kSubmatrix of MT,Ttk×d−k,d−k×kSubmatrix of MΨn×dEncoding matrixΦMSR:n×α,MBR:n×kSubmatrix ofΨΛn×nDiagonal matrixΔn×d−kSubmatrix ofΨCMSR:n×α,MBR:n×dCode matrixΦDCMSR:k×α,MBR:k×kSubmatrix ofΨDCΨDCk×dDecoding matrixΨrepaird×dRepair matrixFor ann,k,d=2k−2 MSR code with β = 1, α=d−k+1=k−1, d=2α, B=kα=αα+1 over GF2w. The original symbols uii=1B are arranged in the form of M=S1S2t where the α+12 entries in the upper-triangular part of S1 and S2 are filled by α+12 symbols.Encoding is constructed using Ψ=ΦΛΦ where each element is chosen to satisfy the properties where (1) any d rows of Ψ are linearly independent; (2) any α rows of Φ are linearly independent; and (3) the n diagonal elements of Λ are distinct. Let the i-th row of Ψ be 1×dψit, the i-th row of Φ be 1×αϕit, and the i-th row of Λ be 1×nλi. The α coded symbols stored by the i-th node are given by c¯it=ψitM=ϕitS1+λiϕitS2. The complexity of encoding equals the sum of addition and multiplication XORs, where the MSR encoding complexity is nαdμ+d−1w and each data encoding needs n/kdμ+d−1w XORs.Decoding is DC to reconstruct B. This process has three steps. Let ΨDC=ΦDCΛDCΦDC be the submatrix of Ψ corresponding to the k nodes. Then, get encoded data(8)ΨDCM=ΦDCΛDCΦDCS1S2t=ΦDCS1+ΛDCΦDCS2.(1)
LetΨDCMΦDCt=ΦDCS1ΦDCt+ΛDCΦDCS1ΦDCt; the result is k×k matrix. This step has k2αμ+α−1w XORs.(2)
SetP=ΦDCS1ΦDCt, Q=ΦDCS2ΦDCt, ΦDC=ϕ1tϕ2t…ϕαtt. Because S1,S2 is symmetric, P and Q are symmetric. ΨDCMΦDCt=P+ΛDCQ. Since i≠j and 1≤i,j≤k, the i,jth element is Pij+λiQij=Pji+λiQji. Then, kk−1/2 sets of equations are derived and one set of equations is as follows:(9)Pij+λiQij=ψitMϕiPij+λjQij=ψjtMϕj⟶1λi1λjPijQij=ψitMϕiψjtMϕj.This step involves matrix inversion; the XORs to compute a pairPij,Qij is 16 μ+ 8w. Consequently, the DC solves the values of Pij,Qij for all i≠j. The sum of XORs in this stage is kk−1/216μ+8w.(3)
After elements ofP are known, the i-th row (excluding the diagonal element) is given by ϕitS1ϕ1…ϕi−1ϕi+1…ϕα+11≤i≤α+1, and ϕitS1|1≤i≤α+1 is recovered through right product ϕ1…ϕi−1ϕi+1…ϕα+1−1. Then, compute ϕ1…ϕαtS1, from which S1 is recovered. S2 is similarly recovered from Q. In this stage, XOR is(10)2α5−3α4+4α3−α3μ+wα+1+2α3μ+2α2α−1w.For example, ifk = 3, α=2 where(11)ΨDCMΦDCt=c11c12c13c21c22c23c31c32c333×3,P=\ϕ1tS1ϕ2ϕ1tS1ϕ3ϕ2tS1ϕ1\ϕ2tS1ϕ3ϕ3tS1ϕ1ϕ3tS1ϕ2\3×3,Q=\ϕ1tS2ϕ2ϕ1tS2ϕ3ϕ2tS2ϕ1\ϕ2tS2ϕ3ϕ3tS2ϕ1ϕ3tS2ϕ2N33×3.The sum of XORs duringdecoding is 126μ+77w.Repair is to regenerate coded symbols on failed node f. Thus, the aim is to reconstruct c¯f where(12)c¯f=ψftM=ϕftλfϕftM=ϕftS1+λfϕftS2.There are two roles in this stage: helper(h) and replacement(r) nodes, respectively. At first, the i-th helper node hi,i∈d computes the inner product ψhjtMϕf and transmits this value to the r node. Then, then r node obtains the vector ΨrepairMϕf=ψh1ψh2…ψhdtMϕf. Because Ψrepair is invertible, the vector Mϕf is recovered. From Mϕf: S1ϕf,S2ϕf, since S1 and S2 are symmetric matrices,(13)Mϕft=ϕftMt=ϕftS1ϕftS2.The contentc¯f is eventually recovered. The process of repair is not complicated. The number of XORs on each h node is αμ+α−1w and the total is dαμ+α−1w. The computational complexity of r includes matrix inversion, matrix product, and coefficient product and is represented as follows:(14)d5−3d4+4d3−d3μ+w+d2μ+dd−1w+αμ+w.All feasible values of (n, k, d) of MBR codes have β = 1, α=d, B=k+12+kd−k over GF2w. The original symbols uii=1B are arranged in the form of M=STTt0 where the upper-triangular part of the symmetric matrix S is filled by k+12 symbols, and the remaining kd−k symbols are used to construct matrix T.Encoding is to obtain coding matrix C by matrix product with Ψ and M. Define the encoding matrix Ψ as the form Ψ=ΦΔ where each element is chosen in such a way that (1)any d rows of Ψ are linearly independent and (2) any k rows of Φ are linearly independent. Then, C is given by C=ΨM. During this process, the sum of XORs is nddμ+d−1w.Decoding is DC to recover original symbols B by connecting to any k nodes. Because the i-th node stored the vector ψitM, the DC gets the k×d matrix ΨDCM=ΦDCS+ΔDCTtΦDCT. Thus, multiply the matrix ΦDC−1 on the left of ΦDCT to recover first T, and the number of XOR in this step is k5−3k4+4k3−k/3μ+w+kd−kkμ+k−1w. Subsequently, compute ΦDCS+ΔDCTt−ΔDCTt and then multiply ΦDC−1 on the left to recover S. The XOR of this step is k2+k2kμ+k−1w.Repair is recover ψftM symbols stored in the failed node to a replacement node by connecting to an arbitrary set hj|j=1,…,d of d helper nodes. First, each hj computes the inner product ψftMψf and sends the result to the replacement node. The replacement node thus obtains the d symbols ΨrepairMψi and then multiplies on the left by Ψrepair−1 to recover matrix Mψf. Since M is symmetric, Mψft=ψftM. The XOR of repair on the i-th node is dμ+d−1w and on the replacement node is d5−3d4+4d3−d/3μ+w+d2dμ+d−1w.The computational complexity of the PM-MSR and PM-MBR codes is shown in Table5. As seen from Table 5, the PM framework requires multiple matrix inversions, and the number of XORs in the decoding process is very high.Table 5
The number of XORs of the PM framework in encoding, decoding, and repair processes.
PM-MSRPM-MBREncoding: XORsnαdμ+d−1wnddμ+d−1wDecoding: XORsk2αμ+α−1w+/kk−1/216μ+8w+2α5−3α4+4α3−α/3μ+wα+1+2α3μ+2α2α−1wk5−3k4+4k3−k/3μ+w+kd−kkμ+k−1w+k2+k2kμ+k−1wRepair: XORs of helper nodesdαμ+α−1wddμ+d−1wRepair: XORs of replacement nodesd5−3d4+4d3−d/3μ+w+d2μ+dd−1w+αμ+wd5−3d4+4d3−d/3μ+w+d2dμ+d−1w


## 4. The New Product BitmatrixΨ Constructed by Cauchy Matrix

In this section, we introduce the process of converting finite field elements into bitmatrices first. Then, we construct a newΨ with the Cauchy matrix and transform this matrix into a bitmatrix called PB. The encoding, decoding, and repair processes of the MSR and MBR codes based on PB are introduced in detail.


### 4.1. Transforming Finite Field Elements Using Bitmatrix

Through the analysis of the finite field arithmetic in the previous section, each elemente in GF2w is represented as a formal power series and the length of these polynomials is w. In [26], they have described a 1×w row vector V or a w×w matrix M which is represented as an element over GF2w in a new representation over GF2z. For any e∈GF2w, use M(e) as the matrix whose ith0≤i column is Ve∗zi−1; M(1) is the identity matrix and M(0) is the all-zero matrix. For example, Figure 2 shows bitmatrices over GF23. The bitmatrix of e = 3 whose 1st column is 011, 2nd column is 3∗z=3∗2=110, and 3rd column is 3∗z2=3∗4=111. There are two forms of multiplication of bitmatrix as shown in Figure 3. Using the bitmatrix representation, the encoding and decoding of PB-MSR and PB-MBR are accomplished by XOR operations, together with some copying operations.Figure 2
Bitmatrix of each element overGF2ww=3; M(0) is the all-zero matrix and M(1) is the identity matrix. Each columns except 1st column is calculated by the left-hand column∗2.Figure 3
Two forms of multiplication based on bitmatrix overGF8.In paper [21], they have adopted classical “Vandermonde” construct Ψ, but the inverse of an n∗n Vandermonde-based matrix needs time of complexity On3. One well-known choice is to use the Cauchy matrix whose inverse has a time complexity On2. Let X=x1…xα and Y=y1…yn, where xi and yj are distinct elements over GF2w and X∩Y=∅. Then, the Cauchy matrix defined by X and Y has 1/xi+yj in element (i, j). It is clear that any submatrix of a Cauchy matrix is still a Cauchy matrix. If using a Cauchy matrix as Ψ and converting it to bitmatrix, the number of ones in the bitmatrix means the number of XOR operations in encoding and o is the average number of ones per row in the matrix. Choosing different X and Y will get different o. Shown in Figure 4 is the instance over the finite field GF(8) of the PB-MSR code with n=5,k=3,d=4,w=3,B=6,α=2,β=1 and PB-MBR code with n=4,k=2,d=43w=3,B=5,α=3,β=1. When Ψ is constructed by Cauchy matrix, it uses bitmatrix transfer Ψ×M.Figure 4
Using Bitmatrix transformΨ×M. Shown in the upper part of this figure is the transformation of PB-MSR codes for the parameters n=5,k=3,d=4, and B=6. The transformation of PB-MBR for the parameters n=4,k=2,d=3, and B=5 is shown in the bottom half of the illustration. All encoded blocks are stored on the corresponding nodes.


### 4.2. New Product BitmatrixΨ of MSR Codes

For the PB-MSR code in the upper part of Figure4, X = {1, 2} and Y = {0, 3, 4, 5, 6} are used to construct n×α matrix Φ, and Λ is an n×n diagonal matrix. Because Ψ=ΦΛΦ, any d rows of Ψ are linearly independent, any α rows of Φ are linearly independent, and the n diagonal elements of Λ are distinct. According to these three conditions, encoded matrix C=Ψ×M is generated, and each row of coded symbols in C is stored on each corresponding node, which means the i-th symbols of a row are stored on the i-th node.(15)c1=u1+5u2+u4+5u5u2+5u3+u5+5u6.In the reconstruction scene, DC links any three nodes and downloadskα=6 symbols.(16)ΨDC×M=u1+5u2+u4+5u5u2+5u3+u5+5u65u1+u2+u4+2u55u2+u3+u5+2u62u1+3u2+6u4+5u52u2+3u3+6u5+5u6.According to the decoding process introduced in Section3, the content of the original symbols is decoded. When node 5 fails, helper nodes d=4. Through connecting any 4 helpers hii∈d (nodes 1, 2, 3, 4 in the example), a replacement node r can exact regenerate symbols. Each hi inner product bitmatrix ϕf as shown in Figure 5 sends results to replacement node r. Then r calculate equation (17) to obtain intermediate results:(17)Ψrepair×M=ψhit×M×ϕf=4u1+5u2+6u3+4u4+5u5+6u62u1+2u2+7u3+4u4+4u5+5u63u1+2u2+2u3+5u4+6u5+6u6u1+5u2+u3+4u4+2u5+4u6.Figure 5
Product bitmatrixϕf on node 1.Then,r calculates Ψrepair−1 according to the number of helper node like this.(18)Ψrepair−1=5104045725377731.UseΨrepair−1×Ψrepair×M×ϕf to get vector Mϕf.(19)Mϕf=4u1+7u24u2+7u34u4+7u54u5+7u6.After the DC recalculatesS1ϕfS2ϕf, the content of node 5 is recovered.However, the method of random enumeration to find suitableΛ based on the third condition is not reasonable. Thus, we present a simple heuristic to create a better Λ.Lemma 1.
In the finite field, any elementa (except 0) has a unique multiplicative inverse element a−1, so the formula aa−1=a−1a=1 holds.IfX=x1,x2 and Y=y1,y2,y3,y4, where xi and yj are distinct elements over GF(2w), then a Cauchy matrix is as Φ:(20)Φ=1x1+y11x2+y11x1+y21x2+y21x1+y31x2+y31x1+y41x2+y4.Because every1/xi+yj is distinct and their multiplicative inverse is also distinct according to Lemma 1, 1/xi+yj−1=xi+yj. Then, the square of the multiplicative inverse of each element in i-th row and j-th column of Φ is used to construct diagonal matrix Λ and Ψ as follows:(21)Ψ=1x1+y11x2+y1x1+y1x1+y12x2+y11x1+y21x2+y2x1+y2x1+y22x2+y21x1+y31x2+y3x1+y3x1+y32x2+y31x1+y41x2+y4x1+y4x1+y42x2+y4.Each column ofΨ is linearly independent. Nevertheless, for every operation based on the finite fields GF2w, when w and primitive polynomial change, the results of all operations change. Hence, matrix inversion is needed to determine whether the current structure is invertible. If the current Ψ has an irreversible submatrix, it changes each element of Λ by multiplying by the power to obtain a new completely different element. Since matrix inverses are encoded, decoded, and repaired only a few times and matrix products occur countless times, it is important to optimize the number of exclusive XORs for the matrix. The other details are covered in the next section.


### 4.3. New Product BitmatrixΨ of MBR Codes

For the lower part of Figure4, combine X = {0, 1, 2} and Y = {3, 4, 5, 6} to construct wn×wd matrix Ψ of PB-MBR. Because Ψ=ΦΔ where Φ and Δ are n×k and n×d−k, any d rows of Ψ are linearly independent and any k rows of Φ are linearly independent. As shown in the example, each node stores 1×α vector, such as(22)c1=6u1+5u2+u46u2+5u3+u56u4+5u5.When decoding the original symbols,DC connects any two nodes and downloads kα=6 data, where(23)ΨDC×M=6u1+5u2+u46u2+5u3+u56u4+5u57u1+2u2+3u47u2+2u3+3u57u4+2u5.WhenΨDCM=ΦDCS+ΔDCTtΦDCT, T is recovered by multiplying ΦDC−1 on the left.(24)ΦDC−1×ΦDC×T=2576×6u4+5u57u4+2u5=u4u5.Subsequently,S is recovered.For example, if node 4 fails, to accurately regenerate coded symbols on ther node, it requires connecting to any three helpers hi(1,2,3 in the example). Each hi inner product bitmatrix ψf, respectively, sends the result to the replacement node. r node obtains d vectors ΨrepairMψf and multiplies Ψrepair−1 on the left where(25)Ψrepair−1=425115124.Then, the DC recoversMψft=ψftM which represents the lost symbols on node 4.


## 4.1. Transforming Finite Field Elements Using Bitmatrix

Through the analysis of the finite field arithmetic in the previous section, each elemente in GF2w is represented as a formal power series and the length of these polynomials is w. In [26], they have described a 1×w row vector V or a w×w matrix M which is represented as an element over GF2w in a new representation over GF2z. For any e∈GF2w, use M(e) as the matrix whose ith0≤i column is Ve∗zi−1; M(1) is the identity matrix and M(0) is the all-zero matrix. For example, Figure 2 shows bitmatrices over GF23. The bitmatrix of e = 3 whose 1st column is 011, 2nd column is 3∗z=3∗2=110, and 3rd column is 3∗z2=3∗4=111. There are two forms of multiplication of bitmatrix as shown in Figure 3. Using the bitmatrix representation, the encoding and decoding of PB-MSR and PB-MBR are accomplished by XOR operations, together with some copying operations.Figure 2
Bitmatrix of each element overGF2ww=3; M(0) is the all-zero matrix and M(1) is the identity matrix. Each columns except 1st column is calculated by the left-hand column∗2.Figure 3
Two forms of multiplication based on bitmatrix overGF8.In paper [21], they have adopted classical “Vandermonde” construct Ψ, but the inverse of an n∗n Vandermonde-based matrix needs time of complexity On3. One well-known choice is to use the Cauchy matrix whose inverse has a time complexity On2. Let X=x1…xα and Y=y1…yn, where xi and yj are distinct elements over GF2w and X∩Y=∅. Then, the Cauchy matrix defined by X and Y has 1/xi+yj in element (i, j). It is clear that any submatrix of a Cauchy matrix is still a Cauchy matrix. If using a Cauchy matrix as Ψ and converting it to bitmatrix, the number of ones in the bitmatrix means the number of XOR operations in encoding and o is the average number of ones per row in the matrix. Choosing different X and Y will get different o. Shown in Figure 4 is the instance over the finite field GF(8) of the PB-MSR code with n=5,k=3,d=4,w=3,B=6,α=2,β=1 and PB-MBR code with n=4,k=2,d=43w=3,B=5,α=3,β=1. When Ψ is constructed by Cauchy matrix, it uses bitmatrix transfer Ψ×M.Figure 4
Using Bitmatrix transformΨ×M. Shown in the upper part of this figure is the transformation of PB-MSR codes for the parameters n=5,k=3,d=4, and B=6. The transformation of PB-MBR for the parameters n=4,k=2,d=3, and B=5 is shown in the bottom half of the illustration. All encoded blocks are stored on the corresponding nodes.


## 4.2. New Product BitmatrixΨ of MSR Codes

For the PB-MSR code in the upper part of Figure4, X = {1, 2} and Y = {0, 3, 4, 5, 6} are used to construct n×α matrix Φ, and Λ is an n×n diagonal matrix. Because Ψ=ΦΛΦ, any d rows of Ψ are linearly independent, any α rows of Φ are linearly independent, and the n diagonal elements of Λ are distinct. According to these three conditions, encoded matrix C=Ψ×M is generated, and each row of coded symbols in C is stored on each corresponding node, which means the i-th symbols of a row are stored on the i-th node.(15)c1=u1+5u2+u4+5u5u2+5u3+u5+5u6.In the reconstruction scene, DC links any three nodes and downloadskα=6 symbols.(16)ΨDC×M=u1+5u2+u4+5u5u2+5u3+u5+5u65u1+u2+u4+2u55u2+u3+u5+2u62u1+3u2+6u4+5u52u2+3u3+6u5+5u6.According to the decoding process introduced in Section3, the content of the original symbols is decoded. When node 5 fails, helper nodes d=4. Through connecting any 4 helpers hii∈d (nodes 1, 2, 3, 4 in the example), a replacement node r can exact regenerate symbols. Each hi inner product bitmatrix ϕf as shown in Figure 5 sends results to replacement node r. Then r calculate equation (17) to obtain intermediate results:(17)Ψrepair×M=ψhit×M×ϕf=4u1+5u2+6u3+4u4+5u5+6u62u1+2u2+7u3+4u4+4u5+5u63u1+2u2+2u3+5u4+6u5+6u6u1+5u2+u3+4u4+2u5+4u6.Figure 5
Product bitmatrixϕf on node 1.Then,r calculates Ψrepair−1 according to the number of helper node like this.(18)Ψrepair−1=5104045725377731.UseΨrepair−1×Ψrepair×M×ϕf to get vector Mϕf.(19)Mϕf=4u1+7u24u2+7u34u4+7u54u5+7u6.After the DC recalculatesS1ϕfS2ϕf, the content of node 5 is recovered.However, the method of random enumeration to find suitableΛ based on the third condition is not reasonable. Thus, we present a simple heuristic to create a better Λ.Lemma 1.
In the finite field, any elementa (except 0) has a unique multiplicative inverse element a−1, so the formula aa−1=a−1a=1 holds.IfX=x1,x2 and Y=y1,y2,y3,y4, where xi and yj are distinct elements over GF(2w), then a Cauchy matrix is as Φ:(20)Φ=1x1+y11x2+y11x1+y21x2+y21x1+y31x2+y31x1+y41x2+y4.Because every1/xi+yj is distinct and their multiplicative inverse is also distinct according to Lemma 1, 1/xi+yj−1=xi+yj. Then, the square of the multiplicative inverse of each element in i-th row and j-th column of Φ is used to construct diagonal matrix Λ and Ψ as follows:(21)Ψ=1x1+y11x2+y1x1+y1x1+y12x2+y11x1+y21x2+y2x1+y2x1+y22x2+y21x1+y31x2+y3x1+y3x1+y32x2+y31x1+y41x2+y4x1+y4x1+y42x2+y4.Each column ofΨ is linearly independent. Nevertheless, for every operation based on the finite fields GF2w, when w and primitive polynomial change, the results of all operations change. Hence, matrix inversion is needed to determine whether the current structure is invertible. If the current Ψ has an irreversible submatrix, it changes each element of Λ by multiplying by the power to obtain a new completely different element. Since matrix inverses are encoded, decoded, and repaired only a few times and matrix products occur countless times, it is important to optimize the number of exclusive XORs for the matrix. The other details are covered in the next section.


## 4.3. New Product BitmatrixΨ of MBR Codes

For the lower part of Figure4, combine X = {0, 1, 2} and Y = {3, 4, 5, 6} to construct wn×wd matrix Ψ of PB-MBR. Because Ψ=ΦΔ where Φ and Δ are n×k and n×d−k, any d rows of Ψ are linearly independent and any k rows of Φ are linearly independent. As shown in the example, each node stores 1×α vector, such as(22)c1=6u1+5u2+u46u2+5u3+u56u4+5u5.When decoding the original symbols,DC connects any two nodes and downloads kα=6 data, where(23)ΨDC×M=6u1+5u2+u46u2+5u3+u56u4+5u57u1+2u2+3u47u2+2u3+3u57u4+2u5.WhenΨDCM=ΦDCS+ΔDCTtΦDCT, T is recovered by multiplying ΦDC−1 on the left.(24)ΦDC−1×ΦDC×T=2576×6u4+5u57u4+2u5=u4u5.Subsequently,S is recovered.For example, if node 4 fails, to accurately regenerate coded symbols on ther node, it requires connecting to any three helpers hi(1,2,3 in the example). Each hi inner product bitmatrix ψf, respectively, sends the result to the replacement node. r node obtains d vectors ΨrepairMψf and multiplies Ψrepair−1 on the left where(25)Ψrepair−1=425115124.Then, the DC recoversMψft=ψftM which represents the lost symbols on node 4.


## 5. Optimization of PB Framework Based on Minimizing the Number of Ones

An arbitrary Cauchy matrix with different X and Y brow the various number of ones, and the impact on performance is significantly different [27]. It is necessary to find a better bitmatrix Ψ which has fewer ones. Therefore, in this section, we optimize the two new Ψ by two new heuristic algorithms.


### 5.1. Optimizing the Number of Ones in BitmatrixΨ of PB-MSR

It is easy to know the number of ones of each element overGF2w. Figure 2 shows that 1–7 elements have several ones that are represented by an array as [3, 4, 7, 5, 4, 7, 6]. A bitmatrix with fewer ones can reduce the encoding computation, and element 1 has the least ones.Forjthj∈1,n/2 column of bitmatrix Ψ of PB-MSR,(1)
Count the number of ones.(2)
For each element divide by elementΦi,j(i is row) and get a new column.(3)
Repeat the first two stepsn times and obtain the best jth column which has the minimum number of ones.Then, repeat the first three steps for all columns and get a new matrix which has a minimal number of ones calledΦ′ as well as the invertibility property.Next, it is necessary to findΛmin×Φ′ which has a minimal number of ones. Let λ=Λ1,Λ2,…,Λd−k+1 denote the set of n×n diagonal matrices and let each Λj be n multiplicative inverses of jth column of Φ′. For each Λj in λ, do the following:(1)
ConstructΨj=Φ′Λj×Φ′.(2)
Determine whether the newΨ is invertible. If it is, continue to the next step; if it is irreversible, Λj=Λj×Λj.(3)
Count the number of ones ofΛj×Φ′.(4)
Repeat the first three steps and whicheverΛmin gives the minimal number of ones, form Ψ by this Λmin×Φ′.Algorithm1 outlines the procedure to generate the set of λ and the process to find the best Λk matrix.Algorithm 1: Finding the optimized bitmatrix Ψ=Φ′ΛΦ′ of PB-MSR (the algorithm first gets a new Φ′ which has a minimal number of ones and then finds Λmin×Φ′ which has minimal number of ones).
(1)
Om is the number of ones of a matrix;(2)
Ocj is the number of ones of the jth column;(3)
Use Cauchy matrix constructΦ and count OΦ;(4)
for each column j=1 to d−k+1do(5)
for each row i=1 to ndo(6)
for each row k=1 to ndo(7)
CalculateΦ′k,j=Φk,j/Φi,j;(8)
CountOcj of this new column;(9)
end for(10)
end for(11)
Choose the column withminOcj as new jth column of Φ′;(12)
end for(13)
ConstructΦ′ and each column has minOcj;(14)
CountOΦ′;(15)
for each column j=1 to d−k+1do(16)
for each row i=1 to ndo(17)
Λi,j=1/Φ′i,j;(18)
for each column x=1 to d−k+1do(19)
Λi,j×Φ′i,x;(20)
end for(21)
end for(22)
ifΨj=Φ′Λj×Φ′ is inverse then(23)
CountOΛj×Φ′;(24)
else(25)
repeat 16–26 steps by multiplying the power ofΛi,j;(26)
end if(27)
end for(28)
Choose the bestΨ which has the minOΛmin×Φ′;For example, as shown in Figure6, ΨMSR has 22 + 22 + 22 + 24 = 90 ones and XORs per row obefore=90/4∗3−1=6.5, but optimized ΨMSR′ has 18 + 18 + 18 + 18 = 72 ones and XORs per row oafter=72/4∗3−1=5, which is a 23% performance improvement.Figure 6
Comparison of originalΨMSR and optimized ΨMSR′ that has a minimal number of ones.


### 5.2. Optimizing the Number of Ones in BitmatrixΨ of PB-MBR

For bitmatrixΨ of PB-MBR, let λ=Λ1,Λ2,…,Λd(d is the number of helper nodes) denote the set of n×n diagonal matrices and let each Λj be n multiplicative inverses of jth column of Ψ. For each Λj, do the following:(1)
UseΛj×Ψ=Ψ′.(2)
Count the number of ones of newΨ′.(3)
Repeat the first two stepsd times and obtain the best Ψ′.After one column ofΨ′ becomes element 1, Algorithm 2 does the same for the remaining d-1 columns, and each column needs to be optimized by dividing the value on this column so that the number of ones in the current column is minimized. The detailed process is written in Algorithm 2.Algorithm 2: Finding the optimized bitmatrix Ψ of PB-MBR (the algorithm first denotes a set of λ and each Λj∈λ and finds the best Ψ′=ΛjΨ which has minimal number of ones).
(1)
Om is the number of ones of a matrix(2)
Ocj is the number of ones of the jth column(3)
Use Cauchy matrix to constructΨ and count OΨ(4)
λ=Λ1,Λ2,…,Λd as the set of n×n diagonal matrices and each matrix form from multiplcative inverses of Ψ(5)
for each Λj∈λdo(6)
Ψ′=Λj×Ψ(7)
CountOΨ′(8)
end for(9)
Choose the bestΨ′ which has the minOΨ′(10)
The column of the matrix with all number 1 isxth(11)
The setη includes all columns except xth column(12)
for each column j∈ηdo(13)
for each row i=1 to ndo(14)
for each row k=1 to ndo(15)
CalculateΨ″k,j=Ψ′k,j/Ψ′i,j(16)
end for(17)
CountOcj of this new column(18)
end for(19)
Choose the column withminOcj as new jth column of Ψ″(20)
end for(21)
Choose columns with theminOcj to construct Ψ″(22)
CountOΨ″For example, as shown in Figure7, original Ψ has 24 + 19 + 21 = 64 ones and XORs per row obefore=64/4∗3−1=4.33, but optimized Ψ″ only has 12 + 18 + 18 = 48 ones and XORs per row oafter=48/12−1=3, which is a 30.7% performance improvement.Figure 7
Comparison of originalΨMBR and optimized ΨMBR″ that has a minimal number of ones.


## 5.1. Optimizing the Number of Ones in BitmatrixΨ of PB-MSR

It is easy to know the number of ones of each element overGF2w. Figure 2 shows that 1–7 elements have several ones that are represented by an array as [3, 4, 7, 5, 4, 7, 6]. A bitmatrix with fewer ones can reduce the encoding computation, and element 1 has the least ones.Forjthj∈1,n/2 column of bitmatrix Ψ of PB-MSR,(1)
Count the number of ones.(2)
For each element divide by elementΦi,j(i is row) and get a new column.(3)
Repeat the first two stepsn times and obtain the best jth column which has the minimum number of ones.Then, repeat the first three steps for all columns and get a new matrix which has a minimal number of ones calledΦ′ as well as the invertibility property.Next, it is necessary to findΛmin×Φ′ which has a minimal number of ones. Let λ=Λ1,Λ2,…,Λd−k+1 denote the set of n×n diagonal matrices and let each Λj be n multiplicative inverses of jth column of Φ′. For each Λj in λ, do the following:(1)
ConstructΨj=Φ′Λj×Φ′.(2)
Determine whether the newΨ is invertible. If it is, continue to the next step; if it is irreversible, Λj=Λj×Λj.(3)
Count the number of ones ofΛj×Φ′.(4)
Repeat the first three steps and whicheverΛmin gives the minimal number of ones, form Ψ by this Λmin×Φ′.Algorithm1 outlines the procedure to generate the set of λ and the process to find the best Λk matrix.Algorithm 1: Finding the optimized bitmatrix Ψ=Φ′ΛΦ′ of PB-MSR (the algorithm first gets a new Φ′ which has a minimal number of ones and then finds Λmin×Φ′ which has minimal number of ones).
(1)
Om is the number of ones of a matrix;(2)
Ocj is the number of ones of the jth column;(3)
Use Cauchy matrix constructΦ and count OΦ;(4)
for each column j=1 to d−k+1do(5)
for each row i=1 to ndo(6)
for each row k=1 to ndo(7)
CalculateΦ′k,j=Φk,j/Φi,j;(8)
CountOcj of this new column;(9)
end for(10)
end for(11)
Choose the column withminOcj as new jth column of Φ′;(12)
end for(13)
ConstructΦ′ and each column has minOcj;(14)
CountOΦ′;(15)
for each column j=1 to d−k+1do(16)
for each row i=1 to ndo(17)
Λi,j=1/Φ′i,j;(18)
for each column x=1 to d−k+1do(19)
Λi,j×Φ′i,x;(20)
end for(21)
end for(22)
ifΨj=Φ′Λj×Φ′ is inverse then(23)
CountOΛj×Φ′;(24)
else(25)
repeat 16–26 steps by multiplying the power ofΛi,j;(26)
end if(27)
end for(28)
Choose the bestΨ which has the minOΛmin×Φ′;For example, as shown in Figure6, ΨMSR has 22 + 22 + 22 + 24 = 90 ones and XORs per row obefore=90/4∗3−1=6.5, but optimized ΨMSR′ has 18 + 18 + 18 + 18 = 72 ones and XORs per row oafter=72/4∗3−1=5, which is a 23% performance improvement.Figure 6
Comparison of originalΨMSR and optimized ΨMSR′ that has a minimal number of ones.


## 5.2. Optimizing the Number of Ones in BitmatrixΨ of PB-MBR

For bitmatrixΨ of PB-MBR, let λ=Λ1,Λ2,…,Λd(d is the number of helper nodes) denote the set of n×n diagonal matrices and let each Λj be n multiplicative inverses of jth column of Ψ. For each Λj, do the following:(1)
UseΛj×Ψ=Ψ′.(2)
Count the number of ones of newΨ′.(3)
Repeat the first two stepsd times and obtain the best Ψ′.After one column ofΨ′ becomes element 1, Algorithm 2 does the same for the remaining d-1 columns, and each column needs to be optimized by dividing the value on this column so that the number of ones in the current column is minimized. The detailed process is written in Algorithm 2.Algorithm 2: Finding the optimized bitmatrix Ψ of PB-MBR (the algorithm first denotes a set of λ and each Λj∈λ and finds the best Ψ′=ΛjΨ which has minimal number of ones).
(1)
Om is the number of ones of a matrix(2)
Ocj is the number of ones of the jth column(3)
Use Cauchy matrix to constructΨ and count OΨ(4)
λ=Λ1,Λ2,…,Λd as the set of n×n diagonal matrices and each matrix form from multiplcative inverses of Ψ(5)
for each Λj∈λdo(6)
Ψ′=Λj×Ψ(7)
CountOΨ′(8)
end for(9)
Choose the bestΨ′ which has the minOΨ′(10)
The column of the matrix with all number 1 isxth(11)
The setη includes all columns except xth column(12)
for each column j∈ηdo(13)
for each row i=1 to ndo(14)
for each row k=1 to ndo(15)
CalculateΨ″k,j=Ψ′k,j/Ψ′i,j(16)
end for(17)
CountOcj of this new column(18)
end for(19)
Choose the column withminOcj as new jth column of Ψ″(20)
end for(21)
Choose columns with theminOcj to construct Ψ″(22)
CountOΨ″For example, as shown in Figure7, original Ψ has 24 + 19 + 21 = 64 ones and XORs per row obefore=64/4∗3−1=4.33, but optimized Ψ″ only has 12 + 18 + 18 = 48 ones and XORs per row oafter=48/12−1=3, which is a 30.7% performance improvement.Figure 7
Comparison of originalΨMBR and optimized ΨMBR″ that has a minimal number of ones.


## 6. Experiment

In this section, we have implemented the new PB-MSR and PB-MBR codes in C/C++ and employed the Jerasure 2.0 [28] with GF-complete [29] libraries for finite field arithmetic operations. All evaluations over GF2w are about the reduction of XORs, encoding, decoding, and repair performances. All tests have been conducted on MacOS Catalina with 8 Intel Core i9 with 2.3 GHz clock speed and 16 GB 2667 MHz. In Section 6.1, we analyze the improved performances of the number of XORs based on new PB construction. In Sections 6.2–6.4, we report on experiments about encoding, decoding, and repair performances. The encoding performance = total encoded file size/encoding time and the decoding performance = total decoded file size/decoding time. Finally, the influence of finite field size about w is analyzed. All experimental results were average values after maximum and minimum values have been removed.


### 6.1. Analyzing New Product Bitmatrix

To better understand the effects of the new PB construct in speeding up the encoding computation, some evaluation experiments were designed on reducing the number of XORs, and the results are reported in Table6. The baseline is based on the original Cauchy matrix without any additional optimization. Original PB-MSR and original PB-MBR have two subcolumns of data, which are the sum of XORs of Cauchy matrices formed by different combinations of X and Y. Since the original PB-MBR code is constructed by original Cauchy matrix, the two columns of before PB-MBR are the actual values of original Cauchy matrices. The latter two columns are reduction of PB-MSR and reduction of PB-MBR, respectively. Improvement is measured in terms of the decrease in XORs. In the last row of the table, the average improvement over all the tested parameters is included.Table 6
Performance improvement by PB construction.
(n,k,d,w)Original PB-MSROriginal PB-MBR(Cauchy)Reduction of PB-MSRReduction of PB-MBR(5, 3, 4, 8)59753664364016.42%5.78%26.28%33.44%(5, 3, 4, 16)189219482123229619.24%15.09%23.60%35.58%(5, 3, 4, 32)655172788043880719.94%10.51%7.68%29.24%(10, 5, 8, 8)255925432642262011.92%11.88%16.28%15.31%(10, 5, 8, 16)84879383891695125.10%14.78%12.07%14.27%(10, 5, 8, 32)3519635816406724016614.36%16.07%22.84%18.47%(16, 8, 14, 8)72927190734274026.62%6.43%10.71%9.70%(16, 8, 14, 16)265992459126722273245.34%4.15%14.68%19.34%(16, 8, 14, 32)11155910344311380611646813.09%14.44%24.56%28.96%AVERAGE11.73%20.17%Since combinations ofX and Y are different and the construction process of the PB-MSR code product matrix is also more complicated, each change will bring completely different results, so this experiment only observes the overall change trend. The size of the finite field is dependent on the size of computer bytes, which are 28, 216, and 232. And the choice of w needs to satisfy the range of n+k≤w−1, when d = 2k-2. It can be seen from Table 1 that PB-MSR provides a 11.73% reduction in the number of XORs and PB-MBR provides a 20.17% reduction in the number of XORs. Because the optimization of PB-MBR is the overall optimization of matrix Ψ, the degree of optimization is greater. Figure 8 shows the XOR change curve. The two line graphs are the original PB-MSR code and PB-MBR code, which are baselines. And the number of XORs optimized for the two codes is lower than the values of the line graphs.Figure 8
The number of XORs of PB-MSR and PB-MBR. The original PB-MSR and PB-MBR are the baselines represented by the line chart. The optimized PB-MSR and PB-MBR are represented by the bar graph.


### 6.2. Encoding Performance Evaluation

The RS and Cauchy codes use the Vandermonde and Cauchy matrices, which are the most classic experiment benchmarks for all erasure codes. Figure9 shows the comparison results of the encoding performance of PB-MSR, PM-MSR, PB-MBR, PM-MBR, RS, and Cauchy codes when the total number of coded blocks n is fixed and r equals 2, 2.5, or 3. Cauchy-good is the optimized Cauchy-matrix encoding scheme provided by the Jerasure 2.0 library. Since encoding performance is directly related to the number of XORs, when the redundancy rate r is the maximum, the coding matrix of any coding scheme is the minimum. Therefore, when r=3, all encoding performances are optimal. With a decrease of r, the multiplicative operations in finite fields increase gradually, and all coding rates decrease. It can be seen from the figure that as r becomes smaller, the PB Ψ becomes larger and more optimization time is required. Therefore, the coding rate of the PB-MSR and PB-MBR codes decreases faster than RS or Cauchy. According to the analysis in the previous section, the different Cauchy matrices will generate different optimization results, so the rise of PB-MBR code in r=3 or r=2.5 does not have the same proportions. However, the PB-MSR encoding rate is not as fast as the PM-MSR using the Vandermonde matrix directly when the coded object is small. This is because it requires more time to generate the optimization bitmatrix. The encoding rate of the PB-MBR code is lower than that of PB-MSR because more redundancy is needed to be written to disk during the encoding process of the PB-MBR code. From Figure 9(b), it can be seen that with an increase of coding objects, the proportion of time to generate or optimize the matrix is relatively small, so the rate of all coding strategies increases.Figure 9
(a) The results of encoding performance under 5 MB. (b) The results of encoding performance under 200 MB.
(a)(b)


### 6.3. Decoding Performance Evaluation

In the decoding/reconstruction experiments, the decoding performances for various values ofr and fixed n for all coding schemes were tested. The decoding performance during reconstruction was measured in terms of the amount of data decoded per unit time. Figure 10 shows the comparison results. It can be observed that the decoding performances of all codes improve with increasing redundancy r. From Figure 10(a), we see that decoding performance of the PB-MSR code increased from 186.72 MB/s when r = 2 to 300.27 MB/s when r = 3. The PB-MBR code increased by 11.95% when r = 3 than when r = 2. From Figure 10(b), it can be seen that from r = 2 to r = 3, the decoding performance of the PB-MSR code increased by 48.26% and that of the PB-MBR code increased by 14.78%. Since the calculation complexity of PB-MSR and PB-MBR decoding is closely related to k, the smaller k, the lower the calculation complexity and the faster the decoding performances. Although the PB-MBR codes are similar to the PB-MSR codes, they are simpler and therefore have a higher decoding rate. As can be seen from Figure 10, PB-MSR decoding performance is about 17.35% higher than PM-MSR, and PB-MBR is about 15.29% higher than PM-MBR.Figure 10
(a) The results of decoding performance under 5 MB. (b) The results of decoding performance under 200 MB.
(a)(b)


### 6.4. Repair Performance Evaluation

Figure11 shows the data transfers across the network to repair one failed node. It can be seen that both the PB-MSR and PB-MBR codes have significantly lower data transfer compared to RS codes. As can be seen from the bar chart in Figure 11(a), when the encoding object is 5 MB, the classical RS code needs 1.5 times overhead of data transfer compared to the PB-MSR code and needs 2.25 times overhead of data transfer compared to the PB-MBR code. It also can be observed from Figure 11(a) that when the redundancy ratio r is fixed, changing the number of d will result in a smaller amount of data transferred across the network. When d=n−1 in Figure 11(a), the data transferred overhead of PB-MSR code and PB-MBR code decreased by 35.74% and 16.22% compared to that of d=2∗k−2.Figure 11
An example of total amount of data transferred across the network while repairing one failed node. (a) Data transferred overhead under 5 MB. (b) Data transferred overhead under 200 MB.
(a)(b)Additionally, the repair performances were tested as shown in Figure12. From the overall trend, while the value of n is fixed, as the redundancy rate increases, k gradually decreases, and the unit storage capacity of each node increases; disk I/O overhead increases, and the overall repair rate decreases. In contrast to Figure 11, although PB-MSR has a larger network transmission overhead than PB-MBR, it is always the smallest in-unit storage capacity α. Thus, the data that need to be written to the disk is also the smallest. Besides, besides, based on the calculation and analysis results about repair complexity in Table 5, it can be seen that PB-MSR has lower calculation complexity than PB-MBR, so its repair rate is slightly higher.Figure 12
The result of repair performance.


### 6.5. The Effect of Finite FieldGF2w on Coding Performance

Based on the analysis thus far, we know that the complexity of the encoding, decoding, or repair process is related to the finite field sizew, which means every symbol x∈0,2w. Therefore, the experiment in this section analyzes the influence of the finite field size on the performance of ECs. The values of (n, k, d) were fixed, and the performances of w = 8, w = 16, and w = 32 were tested as shown in Figure 13. Figures 13(a), 13(b), and 13(c) are the comparison diagrams of encoding, decoding, and repair performances, respectively. From these figures, we see that as the finite field size w gradually increases, the calculation complexity increases and the rate declines in varying degrees.Figure 13
Comparison of performance under differentw.


## 6.1. Analyzing New Product Bitmatrix

To better understand the effects of the new PB construct in speeding up the encoding computation, some evaluation experiments were designed on reducing the number of XORs, and the results are reported in Table6. The baseline is based on the original Cauchy matrix without any additional optimization. Original PB-MSR and original PB-MBR have two subcolumns of data, which are the sum of XORs of Cauchy matrices formed by different combinations of X and Y. Since the original PB-MBR code is constructed by original Cauchy matrix, the two columns of before PB-MBR are the actual values of original Cauchy matrices. The latter two columns are reduction of PB-MSR and reduction of PB-MBR, respectively. Improvement is measured in terms of the decrease in XORs. In the last row of the table, the average improvement over all the tested parameters is included.Table 6
Performance improvement by PB construction.
(n,k,d,w)Original PB-MSROriginal PB-MBR(Cauchy)Reduction of PB-MSRReduction of PB-MBR(5, 3, 4, 8)59753664364016.42%5.78%26.28%33.44%(5, 3, 4, 16)189219482123229619.24%15.09%23.60%35.58%(5, 3, 4, 32)655172788043880719.94%10.51%7.68%29.24%(10, 5, 8, 8)255925432642262011.92%11.88%16.28%15.31%(10, 5, 8, 16)84879383891695125.10%14.78%12.07%14.27%(10, 5, 8, 32)3519635816406724016614.36%16.07%22.84%18.47%(16, 8, 14, 8)72927190734274026.62%6.43%10.71%9.70%(16, 8, 14, 16)265992459126722273245.34%4.15%14.68%19.34%(16, 8, 14, 32)11155910344311380611646813.09%14.44%24.56%28.96%AVERAGE11.73%20.17%Since combinations ofX and Y are different and the construction process of the PB-MSR code product matrix is also more complicated, each change will bring completely different results, so this experiment only observes the overall change trend. The size of the finite field is dependent on the size of computer bytes, which are 28, 216, and 232. And the choice of w needs to satisfy the range of n+k≤w−1, when d = 2k-2. It can be seen from Table 1 that PB-MSR provides a 11.73% reduction in the number of XORs and PB-MBR provides a 20.17% reduction in the number of XORs. Because the optimization of PB-MBR is the overall optimization of matrix Ψ, the degree of optimization is greater. Figure 8 shows the XOR change curve. The two line graphs are the original PB-MSR code and PB-MBR code, which are baselines. And the number of XORs optimized for the two codes is lower than the values of the line graphs.Figure 8
The number of XORs of PB-MSR and PB-MBR. The original PB-MSR and PB-MBR are the baselines represented by the line chart. The optimized PB-MSR and PB-MBR are represented by the bar graph.


## 6.2. Encoding Performance Evaluation

The RS and Cauchy codes use the Vandermonde and Cauchy matrices, which are the most classic experiment benchmarks for all erasure codes. Figure9 shows the comparison results of the encoding performance of PB-MSR, PM-MSR, PB-MBR, PM-MBR, RS, and Cauchy codes when the total number of coded blocks n is fixed and r equals 2, 2.5, or 3. Cauchy-good is the optimized Cauchy-matrix encoding scheme provided by the Jerasure 2.0 library. Since encoding performance is directly related to the number of XORs, when the redundancy rate r is the maximum, the coding matrix of any coding scheme is the minimum. Therefore, when r=3, all encoding performances are optimal. With a decrease of r, the multiplicative operations in finite fields increase gradually, and all coding rates decrease. It can be seen from the figure that as r becomes smaller, the PB Ψ becomes larger and more optimization time is required. Therefore, the coding rate of the PB-MSR and PB-MBR codes decreases faster than RS or Cauchy. According to the analysis in the previous section, the different Cauchy matrices will generate different optimization results, so the rise of PB-MBR code in r=3 or r=2.5 does not have the same proportions. However, the PB-MSR encoding rate is not as fast as the PM-MSR using the Vandermonde matrix directly when the coded object is small. This is because it requires more time to generate the optimization bitmatrix. The encoding rate of the PB-MBR code is lower than that of PB-MSR because more redundancy is needed to be written to disk during the encoding process of the PB-MBR code. From Figure 9(b), it can be seen that with an increase of coding objects, the proportion of time to generate or optimize the matrix is relatively small, so the rate of all coding strategies increases.Figure 9
(a) The results of encoding performance under 5 MB. (b) The results of encoding performance under 200 MB.
(a)(b)


## 6.3. Decoding Performance Evaluation

In the decoding/reconstruction experiments, the decoding performances for various values ofr and fixed n for all coding schemes were tested. The decoding performance during reconstruction was measured in terms of the amount of data decoded per unit time. Figure 10 shows the comparison results. It can be observed that the decoding performances of all codes improve with increasing redundancy r. From Figure 10(a), we see that decoding performance of the PB-MSR code increased from 186.72 MB/s when r = 2 to 300.27 MB/s when r = 3. The PB-MBR code increased by 11.95% when r = 3 than when r = 2. From Figure 10(b), it can be seen that from r = 2 to r = 3, the decoding performance of the PB-MSR code increased by 48.26% and that of the PB-MBR code increased by 14.78%. Since the calculation complexity of PB-MSR and PB-MBR decoding is closely related to k, the smaller k, the lower the calculation complexity and the faster the decoding performances. Although the PB-MBR codes are similar to the PB-MSR codes, they are simpler and therefore have a higher decoding rate. As can be seen from Figure 10, PB-MSR decoding performance is about 17.35% higher than PM-MSR, and PB-MBR is about 15.29% higher than PM-MBR.Figure 10
(a) The results of decoding performance under 5 MB. (b) The results of decoding performance under 200 MB.
(a)(b)


## 6.4. Repair Performance Evaluation

Figure11 shows the data transfers across the network to repair one failed node. It can be seen that both the PB-MSR and PB-MBR codes have significantly lower data transfer compared to RS codes. As can be seen from the bar chart in Figure 11(a), when the encoding object is 5 MB, the classical RS code needs 1.5 times overhead of data transfer compared to the PB-MSR code and needs 2.25 times overhead of data transfer compared to the PB-MBR code. It also can be observed from Figure 11(a) that when the redundancy ratio r is fixed, changing the number of d will result in a smaller amount of data transferred across the network. When d=n−1 in Figure 11(a), the data transferred overhead of PB-MSR code and PB-MBR code decreased by 35.74% and 16.22% compared to that of d=2∗k−2.Figure 11
An example of total amount of data transferred across the network while repairing one failed node. (a) Data transferred overhead under 5 MB. (b) Data transferred overhead under 200 MB.
(a)(b)Additionally, the repair performances were tested as shown in Figure12. From the overall trend, while the value of n is fixed, as the redundancy rate increases, k gradually decreases, and the unit storage capacity of each node increases; disk I/O overhead increases, and the overall repair rate decreases. In contrast to Figure 11, although PB-MSR has a larger network transmission overhead than PB-MBR, it is always the smallest in-unit storage capacity α. Thus, the data that need to be written to the disk is also the smallest. Besides, besides, based on the calculation and analysis results about repair complexity in Table 5, it can be seen that PB-MSR has lower calculation complexity than PB-MBR, so its repair rate is slightly higher.Figure 12
The result of repair performance.


## 6.5. The Effect of Finite FieldGF2w on Coding Performance

Based on the analysis thus far, we know that the complexity of the encoding, decoding, or repair process is related to the finite field sizew, which means every symbol x∈0,2w. Therefore, the experiment in this section analyzes the influence of the finite field size on the performance of ECs. The values of (n, k, d) were fixed, and the performances of w = 8, w = 16, and w = 32 were tested as shown in Figure 13. Figures 13(a), 13(b), and 13(c) are the comparison diagrams of encoding, decoding, and repair performances, respectively. From these figures, we see that as the finite field size w gradually increases, the calculation complexity increases and the rate declines in varying degrees.Figure 13
Comparison of performance under differentw.


## 7. Related Works

Regenerating codes are state-of-the-art ECs with optimal repair bandwidth that have been used by some storage systems. The NCCloud storage system was one of the earliest implementable designs for 2-parity functional MSR codes (F-MSR), which maintain the same data redundancy level and same storage requirement as traditional ECs but use less repair traffic [30]. In [31], Pamies-Juarez et al. have presented the evaluation of a novel MSR code known as the Butterfly codes in both Ceph and HDFS. Their analysis shows that Butterfly codes are capable of reducing network traffic and reading I/O access during repairs. In [20], the Coupled-Layer (Clay) code is an MSR code that offers a simplified construction for decoding/repair by using pairwise coupling across multiple stacked layers of any single MDS code and has been evaluated over an Amazon AWS cluster. The Clay code is simultaneously optimal in terms of storage overhead, repair bandwidth, optimal access, and sub-packetization level. In [22], Rashmi et al. wanted to minimize disk I/O consumed, while simultaneously retaining optimality in terms of both storage, reliability, and network bandwidth. They presented an algorithm to transform PM-MSR codes into I/O optimal codes (which they refer to as the PM-RBT codes). In addition to MSR codes, there was some new literature about MBR codes. In [32], Hu et al. presented NCFS which was a distributed file system under real network setting based on E-MBR codes [33]. In [34], Shah et al. presented the (n = d+1, k, d) exact-repair- (ER-) MBR codes without arithmetic operation in the repair process. In [35], the authors introduced a family of repair-by-transfer (RBT) codes which was a class of (n, k, d = n-1) ER-MBR codes that were constructed based on congruent transformations applied to a skew-symmetric matrix of message symbols. In this construction, the encoding complexity decreases from n4 to n3. Based on the new coding matrix for PM-MBR, the minimum of a finite field is reduced from n-k + d to n. In [18], the authors first introduced a more natural extension to the classical PM-MBR framework, modified to provide flexibility in the choice of the number of helpers during node repair, permitting a certain number of error-prone nodes during repair. This was achieved by proving the nonsingularity of the family of matrices in large enough finite fields. To reduce the high coding and repair complexity that involves expensive multiplication operations in a finite field, another new class of RGC was proposed. In [36–38], the authors proposed a new framework of linear codes with binary parity-check code, named Binary Addition and Shift Implementable Cyclic-convolutional (BASIC) codes which enable coding and repair by XOR and bitwise cyclic shift.Although some systems are currently using RGC, they are designed or optimized for coding structure, bandwidth overhead, storage overhead, and I/O overhead. However, there is still a lack of some classical coding framework complexity analysis from the perspective of the finite field.ECs rely on finite field operations which can be performed using XOR operations. Many acceleration techniques have been proposed: optimizing bitmatrix design, optimizing computation schedule, common XOR operation reduction, cache management, and vectorization techniques [12]. In [13], two new heuristics have been derived called Uber-CHRS and X-Sets to schedule encoding and decoding bitmatrix by reducing the number of XORs. And several technologies were introduced in the same work by using different heuristic algorithms. In addition to smart scheduling and matching algorithms for reducing the number of XORs, other solutions were based on improving hardware performance. In [14], Plank et al. vectorized finite field operations directly based on single-instruction-multiple-data (SIMD).


## 8. Conclusion

In this paper, we have combined the finite field arithmetic operations to elaborate on the computational complexity of the famous PM framework in encoding, decoding, and repair processes and proposed a new construction called product bitmatrix (PB). Based on two heuristic algorithms, PB-MSR and PB-MBR codes find local minimum XORs that can improve encoding, decoding, and repair performances. Although PB has been optimized by the original framework in computation and has advantages in the decoding and repair processes, when the encoding object is small, the optimization time occupies a portion of the total encoding time. Compared with the PM adopted by Vandermonde, its advantage is insufficient.In future research, in addition to theoretical research, we will conduct in-depth research on the fault-tolerant technology of edge computing nodes in combination with the real environment, for instance, improving network transmission performance [39], adapting the recommended data reliability storage algorithm of edge computing [40, 41], or to design new nonlinear coding methods with deep neural networks [42, 43].



---

*Source: 6642121-2021-01-30.xml*