# Multiple Dimensional Encoding/Modulation Shift-and-Addition Design for Distributed Systems

Authors: Mingjun Dai; Chanting Zhang; Zhaoyan Hong; Paweł Wawrzyński; Tomasz Trzciński; Xiaohui Lin
Journal: Wireless Communications and Mobile Computing
 (2022)

---

## Abstract

In distributed computing/storage/machine learning system, the method of encoding and decoding combing shift-and-addition (SA) and zigzag decoding (ZD) is proposed to solve the problem of high computational complexity. However, in each encoded packet, one element takes part in the encoding only once, so the obtained overhead is extremely high. In this work, based on the idea of multidimensional encoding/modulation, we propose to employ one element of the encoding process multiple times when constructing one encoded packet based on the Cauchy matrix, thereby leveraging the favourable properties of the code based on Cauchy matrix. The overhead is reduced from square to logarithmic in certain parameters. Compared with the overhead of the existing square computational complexity, it is greatly reduced.


---

## Body

## 1. Introduction

In the era of big data [1], the amount of data is growing at a doubling rate annually. The way of data processing has been shifted from the centralized data processing to the distributed data processing. However, in distributed applications, not all devices are reliable. Some devices may fail to work, or the performance of the devices is not consistent. In any task of data processing, there will be some unreliable devices whose computing speed is slower than the average speed, which are called stragglers [2, 3]. For example, in a data center of Facebook, more than 100 nodes may fail per day [4, 5]. The completion time of data processing is constrained by the slowest working node. Therefore, how to deal with stragglers becomes a challenge for data processing. To solve this problem, network coding techniques have been developed, and the code with combination property (CP) is proposed: k original packets are encoded into n packets, where n>k, and any k out of these n packets are able to recover the original data. The code with CP has been widely used in distributed systems, including distributed storage (DS) [6–10], distributed computing (DC) [11–16], and distributed machine learning [17].In distributed systems, linear code is adopted in most of the coding technologies, but linear code involves a lot of multiplication and division operations, which greatly increase the complexity of coding and decoding. For the sake of low computation complexity, a kind of CP-ZD code [18–20] with CP is proposed, which combines shift-and-addition (SA) and zigzag decoding (ZD) [21]. However, for the case where one element takes part in the encoding only once when constructing an encoded packet, the overhead is as high as square of the parameters’ number (nork).Multidimensional encoding/modulation promises high data rate [18, 19], which has been used as promising technique in communication [20] and distributed systems [22, 23]. As a result, to further reduce the overhead, based on the idea of multidimensional encoding/modulation, we propose the idea of one element taking part in the encoding process multiple times when constructing one encoded packet. Using the properties of the code based on Cauchy matrix in finite field, we design a framework of one element taking part in the encoding process multiple times for constructing an encoded packet. The overhead of this coding framework reduces from square to logarithmic with respect to the parameter. Specifically, the idea that one element takes part in the encoding only once in each encoded packet can be interpreted as each source packet being treated as an element and occurring at most once in a coded packet. Similarly, the idea that one element takes part in the encoding process multiple times when constructing one encoded packet is that each source packet occurs multiple times in an encoded packet, which is added to its own multiple distinct shifts.


## 2. Preliminary

### 2.1. Definition of Cauchy Matrix

Givenx1,x2,⋯xn, y1,y2,⋯yn, let ci,j=1/xi+yj1≤i,j≤n, then the matrix C=ci,j is called the Cauchy matrix [24], and its determinant is as follows:
(1)detC=∏1≤i<j≤nxj−xiyj−yi∏i=1n∏j=1nxi+yj.Similarly, a Cauchy matrix over a finite field is defined as follows: letX and Y be two sets of elements in a finite field. Among them, X=x1,x2,⋯,xp and Y=y1,y2,⋯,yq. If for ∀i∈1,2,⋯,p, ∀j∈1,2,⋯,q, the following is satisfied:
(1)
xi+yj≠0(2)
∀i,j∈1,2,⋯,p, i≠j, xi≠xj(3)
∀i,j∈1,2,⋯,q,i≠j,yi≠yjThen, the following matrix is called a Cauchy matrix over a finite field:
(2)G=1x1+y11x1+y2⋯1x1+yq1x2+y11x2+y2⋯1x2+yq⋮⋮⋱⋮1xp+y11xp+y2⋯1xp+yq.It is straightforward to obtain the following theorem from the construction rules of the Cauchy matrix:Theorem 1.
WhenG is a Cauchy matrix, any square submatrix Gl of G is nonsingular, where l indicates the number of rows and columns of the submatrix Gl (1≤l≤minp,q); then,
(3)detGl=∏1≤i<j≤lxj−xiyj−yi∏i=1l∏j=1lxi+yj≠0.In other words, every submatrix of the Cauchy matrix is invertible.


### 2.2. The Arithmetic Operation in Finite Fields

Finite field is a field with a finite number of elements, for example,GF2ω represents a finite field containing 2ω elements. Before describing the arithmetic operation in finite fields, we briefly introduce the concept of the primitive polynomial.The primitive polynomial is essentially a polynomial that cannot be factored. When a finite field determines its primitive polynomials, the arithmetic operations in that field are also determined. In general, the primitive polynomial of a field can be obtained by looking up the table, and the primitive polynomial of a field is not unique. Take the finite fieldGF23 as an example, there is more than one primitive polynomial over GF23, and the most common primitive polynomial is qz=z3+z+1. Table 1 shows some of the primitive polynomials [25] present in GF2ω.Table 1
Table of common primitive polynomials.
Finite fieldPrimitive polynomialGF22z2+z+1GF23z3+z+1GF24z4+z+1GF28z8+z4+z3+z2+1GF216z16+z12+z3+z+1The addition and subtraction operation [22] of finite fields are the XOR operation in polynomial calculation. The rule for adding and subtracting is to XOR coefficients of the same order in two polynomials, and there is no difference between the two operations, such as z2+z+z+1=z2+1,z2+z−z+1=z2+1. At present, the multiplication and division operations [23] of finite fields usually count on the look-up tables. Each field has positive and negative tables, which are denoted as gflog and gfilog, respectively, on the GF2ω field. Taking GF23 as an example, its table gflog and gfilog are generated as shown in Table 2 [16]:Table 2
gflog and gfilog for GF23.
igflogigfilogi0-110221433342656764575-If the multiplication and division operations are performed on theGF23 field, as shown in Table 2, the multiplication operation is as follows:
(4)2×3=gfiloggflog2+gflog3=gfilog1+3=gfilog4=6,and the division operation is as follows:(5)1÷5=gfiloggflog1−gflog5=gfilog0−6=gfilog1=2.


### 2.3. Transformation from FieldGF2ω to Field GF2z/qz

FieldGF2ω is constructed by finding a primitive polynomial of ω degrees on GF2 and then enumerating elements (in polynomial form) by using the generating element z. The addition in this field is performed using polynomial addition, and multiplication is performed using polynomial multiplication and modulo the result with respect to qz, such field GF2ω can be written as GF2ω=GF2z/qz [25], which can also be said that field GF2ω and field GF2ω=GF2z/qz are isomorphic [26].The conversion rule for fieldGF2ω to field GF2z/qz [25] is the conversion of numerical form to polynomial form. Taking GF2ω as an example, the implementation steps are as follows:Step 1.
Initialize the set as0,1,z.Step 2.
Multiply the last element of the set byz, such as z, and modulo the result with respect to qz if the resulting degree is greater than or equal to ω.Step 3.
Continue Step2 until there are 2ω elements in the set, at which point the last element is multiplied by z and modulo qz, resulting in a value of 1.To better understand the above steps, let us elaborate on a simple example:Example 1.
Supposeω=2; then, the original polynomial is qz=z2+z+1; to construct GF22=GF4, we initialize the set as 0,1,z, so the next element is z2; since the degree of the element is 2, modulo it with respect to qz=z2+z+1, which resulting in z+1. Therefore, four elements are generated: 0,1,z,z+1, and the corresponding numerical forms are 0,1,2,3, which are shown in Table 3. If we continue, we can get the following:
(6)z+1zmodqz=z2+zmodz2+z+1=1.
According to Step3, we can end the enumeration.Table 3
Transformation ofGF4 from field GF2ω to field GF2ω=GF2z/qz.
Generating elementPolynomial formNumerical form000z011z1z2z2z+13


### 2.4. Mathematical Model

We want to constructn,k code that possesses the n,k CP. This section adopts the method in reference [27]. We represent each packet as a polynomial of GF2ω, where a number is denoted by several bits within this packet. Source packet si is represented with the polynomial form, as shown in Formula (7), i∈K≜1,2,⋯,k,
(7)siz≜si,1+si,2z+si,3z2+⋯+si,LzL−1,where L indicates the length of the source packet and z indicates the right shift by one bit.Fori∈K, the i-th encoded packet can be expressed as ciz=siz. Let m≜n−k denote the number of parity packets. For i∈M≜1,2,⋯,m, the polynomial form of the i-th parity packet is as follows:
(8)ck+iz≜αi,1zs1z+αi,2zs2z+⋯+αi,kzskz,where αi,jz≜zTij, i∈M,j∈K.Combined with the systematic packets and parity packets, the final coding expression is shown in the following formula:(9)cz=Azsz,where cz≜c1z,c2z,⋯,cnz, sz≜s1z,s2z,⋯,skz, and
(10)Az≜IKzTz,which is a matrix with dimension of n×k, Ikz is a k×k identity matrix, and Tz is a m×k shift matrix,
(11)Tz≜zT11zT12zT13⋯zT1kzT21zT22zT23⋯zT2kzT31zT32zT33⋯zT3k⋮⋮⋮⋮⋮zTm1zTm2zTm3⋯zTmk.The exponent of the element inz is indicated by T, whose actual meaning is the shifted bits of packets.


## 2.1. Definition of Cauchy Matrix

Givenx1,x2,⋯xn, y1,y2,⋯yn, let ci,j=1/xi+yj1≤i,j≤n, then the matrix C=ci,j is called the Cauchy matrix [24], and its determinant is as follows:
(1)detC=∏1≤i<j≤nxj−xiyj−yi∏i=1n∏j=1nxi+yj.Similarly, a Cauchy matrix over a finite field is defined as follows: letX and Y be two sets of elements in a finite field. Among them, X=x1,x2,⋯,xp and Y=y1,y2,⋯,yq. If for ∀i∈1,2,⋯,p, ∀j∈1,2,⋯,q, the following is satisfied:
(1)
xi+yj≠0(2)
∀i,j∈1,2,⋯,p, i≠j, xi≠xj(3)
∀i,j∈1,2,⋯,q,i≠j,yi≠yjThen, the following matrix is called a Cauchy matrix over a finite field:
(2)G=1x1+y11x1+y2⋯1x1+yq1x2+y11x2+y2⋯1x2+yq⋮⋮⋱⋮1xp+y11xp+y2⋯1xp+yq.It is straightforward to obtain the following theorem from the construction rules of the Cauchy matrix:Theorem 1.
WhenG is a Cauchy matrix, any square submatrix Gl of G is nonsingular, where l indicates the number of rows and columns of the submatrix Gl (1≤l≤minp,q); then,
(3)detGl=∏1≤i<j≤lxj−xiyj−yi∏i=1l∏j=1lxi+yj≠0.In other words, every submatrix of the Cauchy matrix is invertible.


## 2.2. The Arithmetic Operation in Finite Fields

Finite field is a field with a finite number of elements, for example,GF2ω represents a finite field containing 2ω elements. Before describing the arithmetic operation in finite fields, we briefly introduce the concept of the primitive polynomial.The primitive polynomial is essentially a polynomial that cannot be factored. When a finite field determines its primitive polynomials, the arithmetic operations in that field are also determined. In general, the primitive polynomial of a field can be obtained by looking up the table, and the primitive polynomial of a field is not unique. Take the finite fieldGF23 as an example, there is more than one primitive polynomial over GF23, and the most common primitive polynomial is qz=z3+z+1. Table 1 shows some of the primitive polynomials [25] present in GF2ω.Table 1
Table of common primitive polynomials.
Finite fieldPrimitive polynomialGF22z2+z+1GF23z3+z+1GF24z4+z+1GF28z8+z4+z3+z2+1GF216z16+z12+z3+z+1The addition and subtraction operation [22] of finite fields are the XOR operation in polynomial calculation. The rule for adding and subtracting is to XOR coefficients of the same order in two polynomials, and there is no difference between the two operations, such as z2+z+z+1=z2+1,z2+z−z+1=z2+1. At present, the multiplication and division operations [23] of finite fields usually count on the look-up tables. Each field has positive and negative tables, which are denoted as gflog and gfilog, respectively, on the GF2ω field. Taking GF23 as an example, its table gflog and gfilog are generated as shown in Table 2 [16]:Table 2
gflog and gfilog for GF23.
igflogigfilogi0-110221433342656764575-If the multiplication and division operations are performed on theGF23 field, as shown in Table 2, the multiplication operation is as follows:
(4)2×3=gfiloggflog2+gflog3=gfilog1+3=gfilog4=6,and the division operation is as follows:(5)1÷5=gfiloggflog1−gflog5=gfilog0−6=gfilog1=2.


## 2.3. Transformation from FieldGF2ω to Field GF2z/qz

FieldGF2ω is constructed by finding a primitive polynomial of ω degrees on GF2 and then enumerating elements (in polynomial form) by using the generating element z. The addition in this field is performed using polynomial addition, and multiplication is performed using polynomial multiplication and modulo the result with respect to qz, such field GF2ω can be written as GF2ω=GF2z/qz [25], which can also be said that field GF2ω and field GF2ω=GF2z/qz are isomorphic [26].The conversion rule for fieldGF2ω to field GF2z/qz [25] is the conversion of numerical form to polynomial form. Taking GF2ω as an example, the implementation steps are as follows:Step 1.
Initialize the set as0,1,z.Step 2.
Multiply the last element of the set byz, such as z, and modulo the result with respect to qz if the resulting degree is greater than or equal to ω.Step 3.
Continue Step2 until there are 2ω elements in the set, at which point the last element is multiplied by z and modulo qz, resulting in a value of 1.To better understand the above steps, let us elaborate on a simple example:Example 1.
Supposeω=2; then, the original polynomial is qz=z2+z+1; to construct GF22=GF4, we initialize the set as 0,1,z, so the next element is z2; since the degree of the element is 2, modulo it with respect to qz=z2+z+1, which resulting in z+1. Therefore, four elements are generated: 0,1,z,z+1, and the corresponding numerical forms are 0,1,2,3, which are shown in Table 3. If we continue, we can get the following:
(6)z+1zmodqz=z2+zmodz2+z+1=1.
According to Step3, we can end the enumeration.Table 3
Transformation ofGF4 from field GF2ω to field GF2ω=GF2z/qz.
Generating elementPolynomial formNumerical form000z011z1z2z2z+13


## 2.4. Mathematical Model

We want to constructn,k code that possesses the n,k CP. This section adopts the method in reference [27]. We represent each packet as a polynomial of GF2ω, where a number is denoted by several bits within this packet. Source packet si is represented with the polynomial form, as shown in Formula (7), i∈K≜1,2,⋯,k,
(7)siz≜si,1+si,2z+si,3z2+⋯+si,LzL−1,where L indicates the length of the source packet and z indicates the right shift by one bit.Fori∈K, the i-th encoded packet can be expressed as ciz=siz. Let m≜n−k denote the number of parity packets. For i∈M≜1,2,⋯,m, the polynomial form of the i-th parity packet is as follows:
(8)ck+iz≜αi,1zs1z+αi,2zs2z+⋯+αi,kzskz,where αi,jz≜zTij, i∈M,j∈K.Combined with the systematic packets and parity packets, the final coding expression is shown in the following formula:(9)cz=Azsz,where cz≜c1z,c2z,⋯,cnz, sz≜s1z,s2z,⋯,skz, and
(10)Az≜IKzTz,which is a matrix with dimension of n×k, Ikz is a k×k identity matrix, and Tz is a m×k shift matrix,
(11)Tz≜zT11zT12zT13⋯zT1kzT21zT22zT23⋯zT2kzT31zT32zT33⋯zT3k⋮⋮⋮⋮⋮zTm1zTm2zTm3⋯zTmk.The exponent of the element inz is indicated by T, whose actual meaning is the shifted bits of packets.


## 3. Encoding Design

The encoding framework that one element takes part in the encoding process multiple times when constructing one encoded packet based on Cauchy matrix is mainly constructed in three steps, and the detailed rules are as follows:Step 1.
Determine the size of the finite field and the dimension of the Cauchy matrix according to the relation of coding parametersn,k.According to the relation ofn,k, when k<n≤2ω and ω is a positive integer, we can determine the size of the finite field to be GF2ω, where ω=log2n and the sign  indicates an integer ceiling function. In finite field GF2ω, the dimension of Cauchy matrix over GF2ω is determined as m×k according to the size of m and k. The specific construction process of the corresponding Cauchy matrix (i.e., the coding matrix) is to determine the element set of X and Y first. The elements of X could be any m elements in GF2ω, X=x1,x2,⋯,xm, which correspond to m parity packets. The elements of Y are any k elements in the 2ω−m elements in GF2ω finite field, Y=y1,y2,⋯,yk, which correspond to k parity packets. According to the construction rules of Cauchy matrix in the finite field, the following relationships should be met between the element sets of X and Y:If for∀i∈1,2,⋯,m, ∀j∈1,2,⋯,k, the following is satisfied:
(1)
xi+yj≠0(2)
∀i,j∈1,2,⋯,m,i≠j,xi≠xj(3)
∀i,j∈1,2,⋯,k,i≠j,yi≠yjThen, the elements inX and Y are different, and a coding matrix G with dimension m×k can be constructed as follows:
(12)G=1x1+y11x1+y2⋯1x1+yk1x2+y11x2+y2⋯1x2+yk⋮⋮⋱⋮1xm+y11xm+y2⋯1xm+yk.Step 2.
Convert the numeric form of elements in the coding matrix to polynomial form.Through the arithmetic operation in finite fields and the transformation from fieldGF2ω to field GF2z/qz in Section 2.3, the matrix G is transformed into the polynomial form. Each element of G can be uniquely represented by a polynomial, that is, G⇒Gz.In particular, the exponent ofz of each polynomial represents the size of the bit-shifting. For example, z2+z represents that a systematic package is shifted to the right by 2 and 1 bits, respectively, and then added over. For example, the shift value of the source packet s1 of length L=12 is z2+z, as shown in Figure 1.Step 3.
Determine the shift matrix combined with the systematic code.Figure 1
The form of elements taking part in encoding process multiple timesCombined with the systematic code, a coding matrix(13)Az≜IkzGzwith dimension n×k is obtained through vertical connection.In order to better understand the design rules that one element takes part in the encoding process multiple times, we will walk through the coding steps with a concrete example.Example 2.
Ifn,k=8,5, then the system has k systematic packages and m parity packages, where k=5 and m=n−k=3.Step 1.
We havek<n≤2ω⇒5<8≤23, ω=log28=3, so we can determine that the size of the finite field is GF23. For the finite field GF23, the commonly used polynomial qz=z3+z+1 is chosen as the primitive polynomial. In this case, X and Y take 3 and 5 elements, respectively, and the elements of X and Y are different. Taking X=5,6,7 and Y=0,1,2,3,4 as an example, the coding matrix is as follows:
(14)G=15+015+115+215+315+416+016+116+216+316+417+017+117+217+317+4.Step 2.
Through the arithmetic operations in the finite field, the addition operation is converted to the XOR operation, for example,5⊕1⇒101⊕1=100=4. Multiplication and division can be calculated by looking up tables. For example, Table 2 lists the positive and negative tables of GF23. Based on the above, we can convert the matrix G into the following form:
(15)G=274313472543276.Through the transformation from fieldGF2ω to field GF2z/qz in Section 2.3, the elements of coding matrix G are expressed by polynomials one by one to obtain the coding matrix Gz:
(16)Gz=zz2+z+1z2z+11z+1z2z2+z+1zz2+1z2z+1zz2+z+1z2+z.Step 3.
By vertically concatenating 5 systematic codes, we can obtain the coding matrixAz:
(17)Az=1000001000001000001000001zz2+z+1z2z+11z+1z2z2+z+1zz2+1z2z+1zz2+z+1z2+z.


## 4. Properties of the Code Based on Cauchy Matrix

### 4.1. CP Property

Before we prove the CP property of the code, we will introduce the properties and lemmas mentioned in the proof.Isomorphism property: the mathematical idea of isomorphism is to establish a one-to-one mapping of two sets that have the same properties associated with operations. For example, assuming that the setsB and B− of algebraic operations are isomorphic, if one set B has a property that is only relevant to the algebraic operations of this set, then the other set B− has exactly similar properties [28].Lemma 2.
Any square submatrix ofGz is invertible.Proof.
According to Section3, matrix G is a Cauchy matrix, and the transformation from G to its polynomial form Gz is equivalent to the transformation from field GF2ω to field GF2z/qz, as shown in Section 2.3. In addition, since field GF2ω and field GF2z/qz are isomorphic [17] and the isomorphism property indicates that reversibility in a field will remain reversibility in the isomorphism field, the reversibility of G in field GF2ω will be mapped to that of Gz in field GF2z/qz. Theorem 1 says that any submatrix of G is invertible, so any submatrix of Gz is also invertible.CP property: Anyk out of n encoded packets are able to recover the information of the original k packets.Proof.
First, we use a mathematical model to solve the above coding and decoding problems. The Cauchy matrixG and the coding matrix A are constructed from the previous coding design in Section 3, where
(18)A≜IkG,and Ik represents the matrix
(19)Ik=0−∞⋯−∞−∞0⋯−∞⋮⋮⋱⋮−∞−∞⋯0with the dimension of k×k. For example,
(20)I3=0−∞−∞−∞0−∞−∞−∞0,where element 0 means that the source packet involved in encoding shifts 0 bit, which means nonshift, and element −∞ means that the source packet does not participate in encoding.
According to the mathematical model of Section2.4, in the finite field GF2ω, the matrix above is represented by polynomial form of z, where z is the radix (assuming that the modulus of z is greater than 1), and every element of matrix A is raised to a proper power and then mod the original polynomial of the finite field. This process is actually a transformation from field GF2ω to field GF2z/qz. For example, the identity matrix Ik to Ikz applies the above transformation to
(21)Ik=0−∞⋯−∞−∞0⋯−∞⋮⋮⋱⋮−∞−∞⋯0⇒Ikz=10⋯001⋯0⋮⋮⋱⋮00⋯1,where element 1 indicates that the source packet participating in the encoding is not shifted, and element 0 indicates that the source packet is not participating in the encoding. The transformation process of matrix G to Gz is shown in Section 2.3. At this point, the polynomial form of the coding matrix A is
(22)Az≜IkzGz,which is a matrix with a size of n×k.
Based on the polynomial form ofz above and the mathematical model in Section 2.4, the polynomial cz represents the encoded packet and the polynomial sz represents the systematic packet. The coding relationship can be expressed as cz=Azsz. Take any k packets from n coded packets, that is, extract k lines at the same position from encoded packet cz and form ckz, corresponding to take k lines at the same position from Az and form k×k matrix Akz.The encoding relationship can be expressed by the expression ckz=Akzsz.
Based on the above model, satisfying CP property is equivalent to the invertibility ofAkz. We claim that Akz is invertible due to the following reasons:
In(23)Az≜IkzGz,take any k rows from Az and form k×k matrix Akz. In this case, Akz to be decoded can be formed in two ways: First, Akz does not contain any rows of Ikz; from Lemma 2 above, we know that every square submatrix of Gz is invertible, so Akz is invertible. Second, Akz is composed of α rows in Ikz and β rows in Gz, where Iαz represents α rows in Ikz and Gβz represents β rows in Gz, and α+β=k. Since the matrix Iαz is a known systematic packet, substituting it into Gβz is equivalent to deleting α columns from it. The deleted Gβz is equivalent to extracting the β×β submatrix from Gz, where k−α=β, as shown in the following Example 3. Similarly, Lemma 2 shows that any square submatrix of Gz is invertible, so Akz is also invertible.
To sum up,Az is invertible, so this coding framework can meet the CP property.Example 3.
Following Example2, if n,k=8,5, the system has 5 systematic packets, m parity packets, where m=n−k=3. The matrix Gz has been constructed as
(24)Gz=zz2+z+1z2z+11z+1z2z2+z+1zz2+1z2z+1zz2+z+1z2+z.Combining the identity matrix I5z,
(25)Az=1000001000001000001000001zz2+z+1z2z+11z+1z2z2+z+1zz2+1z2z+1zz2+z+1z2+z. If we choose any 5×5 submatrix A5z in Az, where A5z is composed of some parts of I5z and Gz, let
(26)A5z=100000100000100zz2+z+1z2z+11z+1z2z2+z+1zz2+1,and then, it can be seen from the matrix A5z that the known systematic packets are s1,s2,s3, so A5z can be simplified as
(27)A5z′=z+11zz2+1,which is equivalent to the 2×2 submatrix of Gz. According to Lemma 2, any submatrix of Gz is invertible, so A5z′ is invertible.


### 4.2. Zigzag Decodability (ZD) Property

The ZD property of one element which takes part in the encoding process multiple times when constructing one encoded packet can be proved by experiment that it cannot be fully zigzag decodable. Starting from the experiment, we set several groups of parameters to obtain the probability of zigzag decodability of one element which takes part in the encoding process multiple times. Through experimental simulation, we set several sets of parametersn,k as 5,3, 8,5, 12,8, and 15,10, respectively, and the conditions of zigzag decodable and not are shown in Table 4.Table 4
Success/failure for differentn,k parameters.
n,kSuccessFailureTotal5,382108,54695612,84059049515,1024085953003It can be seen from Figure2 that the encoding framework that one element takes part in the encoding process multiple times when constructing one encoded packet based on the Cauchy matrix has about 80% probability of ZD decoding, which means that there is about 20% probability that zigzag decoding will not be possible. The following two examples illustrate the case that the encoding framework is able or unable to perform zigzag decoding.Figure 2
Decoding probability for differentn,k parameters.Example 4.
Following Example2 where n,k=8,5, we assume that there are encoded packets c1,c2,c6,c7,c8, where c1=s1 and c2=s2. Based on the above, the remaining problem is to use the encoded packets c6,c7,c8 to decode the three source packets s3,s4,s5. The corresponding coding matrix is as follows:
(28)G=z2z+11z2+z+1zz2+1zz2+z+1z2+z.Assuming that the length of the encoded packets is L=12, we can obtain the decoding diagram of Figure 3 through shift-and-addition encoding by row. In this condition, the coding framework can be zigzagged: s4,1 can be obtained directly from the first exposed bit of c8. Substitute s4,1 into the first bit of c6 to obtain s5,1 through shift-and-addition, and then, substitute s5,1 into c7 to obtain s3,1. In this manner, the first bit of each source packet has been obtained. The decoding of the second bit of each source packet is similar to the decoding of the first bit. Substitute s3,1, s4,1, s5,1 into c6,c7,c8, respectively, so that s4,2 can be obtained. Substitute s4,2 into the second bit of c6, and s5,2 can be obtained by XOR operation. Finally, substitute s5,2 into c7, and then, s3,2 can be obtained.Figure 3
An example of able to perform ZD.Example 5.
Following Example2 where n,k=8,5, we assume that there are encoded packets c4,c5,c6,c7,c8, where c4=s4 and c5=s5.Therefore, the remaining problem is to use the encoded packets c6,c7,c8 to decode the three source packets s1,s2,s3 to form the encoding matrix,
(29)G=zz2+z+1z2z+1z2z2+z+1z2z+1z.Assuming the length of the encoded packets is L=12, through shift-and-addition encoding by row, we cannot perform zigzag decoding in this case. From the first bit of each coded packet, only s2,1 is exposed bit. When it is substituted into the second bit of c6,c8, respectively, no new exposed bit can be obtained. The whole decoding process is locked, so the zigzag decoding cannot proceed, as shown in Figure 4.Figure 4
An example of failure in ZD.


## 4.1. CP Property

Before we prove the CP property of the code, we will introduce the properties and lemmas mentioned in the proof.Isomorphism property: the mathematical idea of isomorphism is to establish a one-to-one mapping of two sets that have the same properties associated with operations. For example, assuming that the setsB and B− of algebraic operations are isomorphic, if one set B has a property that is only relevant to the algebraic operations of this set, then the other set B− has exactly similar properties [28].Lemma 2.
Any square submatrix ofGz is invertible.Proof.
According to Section3, matrix G is a Cauchy matrix, and the transformation from G to its polynomial form Gz is equivalent to the transformation from field GF2ω to field GF2z/qz, as shown in Section 2.3. In addition, since field GF2ω and field GF2z/qz are isomorphic [17] and the isomorphism property indicates that reversibility in a field will remain reversibility in the isomorphism field, the reversibility of G in field GF2ω will be mapped to that of Gz in field GF2z/qz. Theorem 1 says that any submatrix of G is invertible, so any submatrix of Gz is also invertible.CP property: Anyk out of n encoded packets are able to recover the information of the original k packets.Proof.
First, we use a mathematical model to solve the above coding and decoding problems. The Cauchy matrixG and the coding matrix A are constructed from the previous coding design in Section 3, where
(18)A≜IkG,and Ik represents the matrix
(19)Ik=0−∞⋯−∞−∞0⋯−∞⋮⋮⋱⋮−∞−∞⋯0with the dimension of k×k. For example,
(20)I3=0−∞−∞−∞0−∞−∞−∞0,where element 0 means that the source packet involved in encoding shifts 0 bit, which means nonshift, and element −∞ means that the source packet does not participate in encoding.
According to the mathematical model of Section2.4, in the finite field GF2ω, the matrix above is represented by polynomial form of z, where z is the radix (assuming that the modulus of z is greater than 1), and every element of matrix A is raised to a proper power and then mod the original polynomial of the finite field. This process is actually a transformation from field GF2ω to field GF2z/qz. For example, the identity matrix Ik to Ikz applies the above transformation to
(21)Ik=0−∞⋯−∞−∞0⋯−∞⋮⋮⋱⋮−∞−∞⋯0⇒Ikz=10⋯001⋯0⋮⋮⋱⋮00⋯1,where element 1 indicates that the source packet participating in the encoding is not shifted, and element 0 indicates that the source packet is not participating in the encoding. The transformation process of matrix G to Gz is shown in Section 2.3. At this point, the polynomial form of the coding matrix A is
(22)Az≜IkzGz,which is a matrix with a size of n×k.
Based on the polynomial form ofz above and the mathematical model in Section 2.4, the polynomial cz represents the encoded packet and the polynomial sz represents the systematic packet. The coding relationship can be expressed as cz=Azsz. Take any k packets from n coded packets, that is, extract k lines at the same position from encoded packet cz and form ckz, corresponding to take k lines at the same position from Az and form k×k matrix Akz.The encoding relationship can be expressed by the expression ckz=Akzsz.
Based on the above model, satisfying CP property is equivalent to the invertibility ofAkz. We claim that Akz is invertible due to the following reasons:
In(23)Az≜IkzGz,take any k rows from Az and form k×k matrix Akz. In this case, Akz to be decoded can be formed in two ways: First, Akz does not contain any rows of Ikz; from Lemma 2 above, we know that every square submatrix of Gz is invertible, so Akz is invertible. Second, Akz is composed of α rows in Ikz and β rows in Gz, where Iαz represents α rows in Ikz and Gβz represents β rows in Gz, and α+β=k. Since the matrix Iαz is a known systematic packet, substituting it into Gβz is equivalent to deleting α columns from it. The deleted Gβz is equivalent to extracting the β×β submatrix from Gz, where k−α=β, as shown in the following Example 3. Similarly, Lemma 2 shows that any square submatrix of Gz is invertible, so Akz is also invertible.
To sum up,Az is invertible, so this coding framework can meet the CP property.Example 3.
Following Example2, if n,k=8,5, the system has 5 systematic packets, m parity packets, where m=n−k=3. The matrix Gz has been constructed as
(24)Gz=zz2+z+1z2z+11z+1z2z2+z+1zz2+1z2z+1zz2+z+1z2+z.Combining the identity matrix I5z,
(25)Az=1000001000001000001000001zz2+z+1z2z+11z+1z2z2+z+1zz2+1z2z+1zz2+z+1z2+z. If we choose any 5×5 submatrix A5z in Az, where A5z is composed of some parts of I5z and Gz, let
(26)A5z=100000100000100zz2+z+1z2z+11z+1z2z2+z+1zz2+1,and then, it can be seen from the matrix A5z that the known systematic packets are s1,s2,s3, so A5z can be simplified as
(27)A5z′=z+11zz2+1,which is equivalent to the 2×2 submatrix of Gz. According to Lemma 2, any submatrix of Gz is invertible, so A5z′ is invertible.


## 4.2. Zigzag Decodability (ZD) Property

The ZD property of one element which takes part in the encoding process multiple times when constructing one encoded packet can be proved by experiment that it cannot be fully zigzag decodable. Starting from the experiment, we set several groups of parameters to obtain the probability of zigzag decodability of one element which takes part in the encoding process multiple times. Through experimental simulation, we set several sets of parametersn,k as 5,3, 8,5, 12,8, and 15,10, respectively, and the conditions of zigzag decodable and not are shown in Table 4.Table 4
Success/failure for differentn,k parameters.
n,kSuccessFailureTotal5,382108,54695612,84059049515,1024085953003It can be seen from Figure2 that the encoding framework that one element takes part in the encoding process multiple times when constructing one encoded packet based on the Cauchy matrix has about 80% probability of ZD decoding, which means that there is about 20% probability that zigzag decoding will not be possible. The following two examples illustrate the case that the encoding framework is able or unable to perform zigzag decoding.Figure 2
Decoding probability for differentn,k parameters.Example 4.
Following Example2 where n,k=8,5, we assume that there are encoded packets c1,c2,c6,c7,c8, where c1=s1 and c2=s2. Based on the above, the remaining problem is to use the encoded packets c6,c7,c8 to decode the three source packets s3,s4,s5. The corresponding coding matrix is as follows:
(28)G=z2z+11z2+z+1zz2+1zz2+z+1z2+z.Assuming that the length of the encoded packets is L=12, we can obtain the decoding diagram of Figure 3 through shift-and-addition encoding by row. In this condition, the coding framework can be zigzagged: s4,1 can be obtained directly from the first exposed bit of c8. Substitute s4,1 into the first bit of c6 to obtain s5,1 through shift-and-addition, and then, substitute s5,1 into c7 to obtain s3,1. In this manner, the first bit of each source packet has been obtained. The decoding of the second bit of each source packet is similar to the decoding of the first bit. Substitute s3,1, s4,1, s5,1 into c6,c7,c8, respectively, so that s4,2 can be obtained. Substitute s4,2 into the second bit of c6, and s5,2 can be obtained by XOR operation. Finally, substitute s5,2 into c7, and then, s3,2 can be obtained.Figure 3
An example of able to perform ZD.Example 5.
Following Example2 where n,k=8,5, we assume that there are encoded packets c4,c5,c6,c7,c8, where c4=s4 and c5=s5.Therefore, the remaining problem is to use the encoded packets c6,c7,c8 to decode the three source packets s1,s2,s3 to form the encoding matrix,
(29)G=zz2+z+1z2z+1z2z2+z+1z2z+1z.Assuming the length of the encoded packets is L=12, through shift-and-addition encoding by row, we cannot perform zigzag decoding in this case. From the first bit of each coded packet, only s2,1 is exposed bit. When it is substituted into the second bit of c6,c8, respectively, no new exposed bit can be obtained. The whole decoding process is locked, so the zigzag decoding cannot proceed, as shown in Figure 4.Figure 4
An example of failure in ZD.


## 5. Performance Analysis

In the case of one element takes part in the encoding only once in shift-and-addition encoding, the overhead of several existing CP-ZD codes is the square ofk or n. As can be seen from Section 3, the overhead of the encoding framework that one element taking part in the encoding process multiple times when constructing one encoded packet is related to the size of the finite field; if the size of the finite field is GF2ω, then ω=log2n. Therefore, the maximum overhead of this encoding framework is determined by the number n of encoded packets, and the overhead is OHcauchy=log2n−1. Therefore, the overhead OH has a logarithmic relationship with the number n of encoded packets, which has a huge advantage over the existing zigzag codes. However, due to the existence of multiple encodings, a source packet may be encoded once or more, which is more complex than the case of single encodings, leading to the possibility of decoding failure during zigzag decoding, as shown in Example 5. As can be seen from Figure 2, the ZD decoding rate of the encoding framework that one element takes part in the encoding process multiple times when constructing one encoded packet based on Cauchy matrix in shift-and-addition is about 80%.In general, compared with the encoding framework of one element taking part in the encoding only once in shift-and-addition, the encoding framework of elements’ multiparticipation based on the Cauchy matrix has a good constraint on the overhead and can reduce the overhead from the existing square level to the logarithmic level. However, it has some losses in ZD properties and cannot guarantee ZD decoding.


## 6. Conclusions

Aiming at the problem of high overhead in CP-ZD codes, in this paper, we design a coding framework based on the idea of elements taking part in encoding multiple times in constructing an encoded packet based on Cauchy matrix and shift-and-addition. It is proved here that the framework has CP properties, but not completely with ZD properties. Experimental results show that the ZD decoding rate of this code is about 80%. However, the overhead isOHcauchy=log2n−1, which is reduced from the existing square level to the logarithmic level. The coding framework confirms the advantage of the element participating in the encoding for multiple times and lays a foundation for future research.


## 7. Future Works

The new coding framework proposed in this paper satisfies the CP property, but not the ZD property. At present, there is no mature encoding framework with one element taking part in encoding process multiple times. Aiming at the idea of elements taking part in encoding multiple times, it is obviously of prospective academic and application value to design a feasible ZD decoding framework. What is more, it is also necessary to study the closed form expression of CP-ZD code, which can be used to describe the necessary and sufficient conditions of CP-ZD code that elements taking part in encoding process multiple times.



---

*Source: 5615041-2022-09-15.xml*