CN105871508B

CN105871508B - Network coding and decoding method and system

Info

Publication number: CN105871508B
Application number: CN201610177923.3A
Authority: CN
Inventors: 代明军; 王磊; 毛白露; 范永俊; 林晓辉; 陈彬; 王晖
Original assignee: Shenzhen University
Current assignee: Shanxi Jinchan e-commerce Co., Ltd
Priority date: 2016-03-25
Filing date: 2016-03-25
Publication date: 2020-01-07
Anticipated expiration: 2036-03-25
Also published as: CN105871508A

Abstract

The invention provides a network coding and decoding method and system, and belongs to the technical field of computers. The network decoding process of the invention comprises the following steps: obtaining a sub-matrix T of a shift matrix T^‑Wherein the sub-matrix T^‑The system code block is composed of a row representing a failed system code block and a column representing a survivor check code block; extracting the minimum number of each row in the submatrix T-and different columns of the prior selected value from the first row, wherein the selected value of each row represents the initial position of code extraction of the check code block corresponding to the row, and then extracting the front L bits of the check code packet from the initial position; and carrying out bit-by-bit substitution decoding according to the extracted data elements of the surviving check code block and the surviving systematic code block. The invention has the beneficial effects that: the transmission bandwidth in the decoding process is reduced, the coding and decoding time delay is greatly shortened, and the coding and decoding efficiency is improved.

Description

Network coding and decoding method and system

Technical Field

The present invention relates to the field of computer technologies, and in particular, to a network coding and decoding method and system.

Background

With the rapid development of cloud computing, the application of network coding and decoding in a distributed storage system draws a great deal of attention. The network coding and decoding can save the storage space and reduce the network congestion of data restoration. Network codec generally adopts the following modes:

maximum Distance Separable (MDS) property: codes with MDS properties are widely used in order to tolerate the maximum number of failed storage nodes. The original data of k packets are mapped to n (n ≧ k) packet data, where any k of the n data can completely reconstruct the original n packet data. That is, the original information stream is divided into k equal-length data packets and encoded into n data packets, and any k of the n data packets can recover the original information. In other words, the original data can be recovered as long as the number of the remaining intact nodes is not less than k.

The solomon (RS) code is a code with MDS property, and is widely used in a network coded distributed storage system. The RS code has the defects that the encoding and decoding operation of the RS code is applied to a high-access finite field, has higher encoding and decoding complexity and needs complex encoding and decoding technology; the decoding time is long due to long coding and decoding time delay; the energy consumption is high. The decoding complexity of the high-binary domain is high, so a lot of work is now focused on binary network coding and zigzag (zig-zag) decoding.

zigzag decoding: and zigzag decoding is carried out in a binary domain, so that the cubic operation in the decoding is changed into linear operation, and the operation complexity is reduced. Zigzag Decode (ZD) codes, which use zigzag decoding in the binary field.

The applicant of the present application filed a patent document with application number 201510354829, and relates to a network coding method based on Zigzag Decode (ZD) code modification, wherein the coding process in the method includes the following steps:

first, dividing the original message into k equal-length data packets, using C respectively₁，C₂，…,C_kIndicates that each packet is of length L, where C_iData element S in (1)_i,jE {0,1} represents C_iJ belongs to {1,2, 3.., k }, j belongs to {0,1, 2.., L-1 };

second, adopt the system code frame C₁，C₂，…,C_kK original non-coding packets contain all original messages, which are the basis of the last n-k check coding packets;

thirdly, coding check code blocks, the last n-k are called check code packets, and C is used_k+1,C_k+2,...,C_nThe method comprises the steps of representing the data packets by using code words generated by bitwise XOR after the first k non-coding packets are shifted, and finally storing n data packets on n independent nodes respectively.

Zigzag Decode (ZD) codes, which use zigzag decoding in the binary field, but shift cycles during encoding result in a check code with more multi-bit redundancy than the systematic code, thus increasing transmission bandwidth during transmission. Especially, under the conditions of large check code and more displacement, the increased transmission bandwidth is not ignored, the coding and decoding time delay is greatly prolonged, and the coding and decoding time is prolonged.

Disclosure of Invention

In order to solve the problems in the prior art, the invention provides a network coding and decoding method and system.

The network coding and decoding method comprises a coding process and a decoding process, wherein the coding process comprises the following steps:

the first step, dividing system code block, dividing original message into k equal length system code data packets, using C respectively₁，C₂，…,C_kIndicates that the packet length of each systematic code is L, where C_iData element S in (1)_i,jE {0,1} represents C_iJ belongs to {1,2, 3.., k }, j belongs to {0,1, 2.., L-1 };

second, coding check code block, setting m check code packets after original non-coded packet, using C_k+1,C_k+2,...,C_nThe code word is generated by bitwise XOR after the first k non-coding packets are shifted according to the number in the shift matrix T, wherein m is n-k; finally, n data packets are respectively stored on n independent nodes,

the decoding process comprises the steps of:

the method comprises the following steps: obtaining a sub-matrix T of a shift matrix T^-Wherein the sub-matrix T^-The system code block is composed of a row representing a failed system code block and a column representing a survivor check code block;

step two: slave submatrix T^-Extracting the numbers of different rows and columns to minimize the sum of all the obtained numbers, wherein the selected value of each row represents the initial position of code extraction of the check code block corresponding to the row, and then extracting the first L bits of the check code packet from the initial position;

step three: and carrying out bit-by-bit substitution decoding according to the extracted data elements of the surviving check code block and the surviving systematic code block.

The invention is further improved, in the second step, the shift matrix T is a cyclic permutation matrix or an incremental shift matrix, in order to ensure zigzag decoding and MDS properties, each element in a non-coding packet is shifted to the right according to a shift matrix row vector, and then the elements after being shifted to the right are subjected to bitwise exclusive OR according to columns, wherein any row or column in the shift matrix T has no same number; the differences of any two columns contain different elements.

The invention is further improved by each non-coded element being represented by a shift matrix T as a designated bit shifted to the right by the row vector, the (i, j) th element in the matrix representing the coded packet C_i+kThe j row element of (1) is right shifted by the number of bits, and C is completed by the rule_i+kI ∈ {1,2, 3., n-k }, j ∈ {1,2, 3., k }.

The invention is further improved, in the shift matrix T, the maximum number of each row is p, and then the length of the check coding packet corresponding to each row is L + p.

The invention is further improved in that in step one, the sum of the surviving systematic code blocks and the check code blocks is not less than

The invention also provides a system for realizing the method, which comprises an encoding module and a decoding module, wherein the encoding module comprises:

a system code block dividing unit for dividing the original message into k system code data packets with equal length, which are respectively C₁，C₂，…,C_kIndicates that the packet length of each systematic code is L, where C_iData element S in (1)_i,jE {0,1} represents C_iJ belongs to {1,2, 3.., k }, j belongs to {0,1, 2.., L-1 };

a check code block encoding unit for setting m check code packets after the original non-code packet by C_k+1,C_k+2,...,C_nThe code word is generated by bitwise XOR after the first k non-coding packets are shifted according to the number in the shift matrix T, wherein m is n-k; finally, n data packets are respectively stored on n independent nodes,

the decoding module includes:

an acquisition unit: sub-matrix T for obtaining a shift matrix T^-Wherein the sub-matrix T^-The system code block is composed of a row representing a failed system code block and a column representing a survivor check code block;

an extraction unit: for slave submatrix T^-Extracting the numbers of different rows and columns to minimize the sum of all the obtained numbers, wherein the selected value of each row represents the initial position of code extraction of the check code block corresponding to the row, and then extracting the first L bits of the check code packet from the initial position;

a decoding unit: and carrying out bit-by-bit substitution decoding according to the extracted data elements of the surviving check code block and the surviving systematic code block.

The invention is further improved, in the check code block coding unit, the shift matrix T is a cyclic permutation matrix or an incremental shift matrix, in order to ensure zigzag decoding and MDS properties, each element in a non-coding packet is shifted to the right according to a shift matrix row vector to indicate a position, and then the elements after right shift are bitwise XOR according to columns, wherein any row or column in the shift matrix T has no same number; the differences of any two columns contain different elements.

The invention is further improved by each non-coded element being represented by a shift matrix T as a designated bit shifted to the right by the row vector, the (i, j) th element in the matrix representing the coded packet C_i+kThe j row element of (1) is right shifted by the number of bits, and C is completed by the rule_i+kI e {1,2, 3.,n-k}，j∈{1,2,3,...,k}。

The invention is further improved in that in the acquisition unit of the decoding module, the sum of the surviving systematic code blocks and the check code blocks is not less than

Compared with the prior art, the invention has the beneficial effects that: the decoding process is improved and innovated on the basis of the existing zigzag encoding and decoding, the transmission bandwidth in the decoding process is reduced, the time delay of encoding and decoding is greatly shortened, and the encoding and decoding efficiency is improved.

Drawings

FIG. 1 is a ZD-MDS (8, 4) code encoding diagram according to the present invention;

FIG. 2 is a decoding diagram of the first embodiment of the present invention;

FIG. 3 shows a sub-matrix T of a shift matrix T according to a second embodiment of the present invention^-Generating a schematic diagram;

FIG. 4 is a decoding diagram of a second embodiment of the present invention;

FIG. 5 shows a sub-matrix T of a shift matrix T according to a third embodiment of the present invention^-Generating a schematic diagram;

FIG. 6 is a decoding diagram of a third embodiment of the present invention;

FIG. 7 shows a sub-matrix T of a shift matrix T according to a fourth embodiment of the present invention^-Generating a schematic diagram;

FIG. 8 is a decoding diagram of a fourth embodiment of the present invention.

Detailed Description

The present invention will be described in further detail with reference to the accompanying drawings and examples.

The invention comprises an encoding process and a decoding process, wherein the encoding process comprises the following steps:

the first step, dividing system code block, dividing original message into k equal length system code data packets, using C respectively₁，C₂，…,C_kIndicate, each ofThe systematic code has a packet length of L, where C_iData element S in (1)_i,jE {0,1} represents C_iJ belongs to {1,2, 3.., k }, j belongs to {0,1, 2.., L-1 };

the decoding process comprises the steps of:

As shown in FIG. 1, the original message of the present invention is divided into four equal-length packets, which are respectively denoted by C₁，C₂，C₃,C₄Indicates that the packet length of each systematic code is L, where C_iData element S in (1)_i,jE {0,1} represents C_iJ is in {0,1, 2.,. 1 }.

Then, coding check code block, setting 4 check coding packets after original non-coding packet, using C₅,C₆,C₇,C₈The expression is that the code word is formed by bitwise XOR generation after the first 4 non-coding packets are shifted according to the number in the shift matrix T, and finally 8 data packets are respectively stored on 8 independent nodes. Wherein, each non-coding element is represented by a designated position of right shift of the row vector, such as a shift matrix T, and the (i, j) th element table in the matrixPair-indicating coded packet C_i+kThe j row element of (1) is right shifted by the number of bits, and C is completed by the rule_i+kI ∈ {1,2, 3., n-k }, j ∈ {1,2, 3., k }, the shift matrix T of this example being:

in a check code block coding unit, the shift matrix T is a cyclic permutation matrix or an incremental shift matrix, in order to ensure zigzag decoding and MDS properties, each element in a non-coded packet is shifted to the right by a designated bit according to a shift matrix row vector, and then the elements after right shift are subjected to bitwise XOR according to columns, wherein any row or column in the shift matrix T does not have the same number; the differences of any two columns contain different elements.

For example: the first row (0, 1, 3, 2) represents the encoded packet C₅Middle structural element C₁To C₄The bits are shifted to the right by 0,1, 3 and 2 bits respectively, and it can be seen that the elements of each row and each column are changed according to the corresponding elements in the matrix, and the obtained encoding result is shown in fig. 1, where each column in the encoded packet represents the result of xoring the relevant bits, such as C₅The first bit of (A) is s_1,0The second bit is S_1,1And S_2,0And the XOR result is sequentially subjected to bitwise XOR and then stored.

In the encoding method of this example, the first column to the fourth column elements of each row of the shift matrix represent the number of bits by which the systematic code blocks C1 to C4 are respectively shifted. The first row to the fourth row of the shift matrix represent check code blocks C5 to C8, respectively, and have a length of L + p (p is for a packet), where the length L of the packet is 10 and the overhead is 3. If the shift is larger or the number of check code blocks is larger, the increased transmission bandwidth is very considerable, because the decoding process of the embodiment only uses L bits of each check code block, the transmission bandwidth can be effectively reduced, and the decoding efficiency can be increased.

As shown in fig. 2, as a first embodiment of this example, assume that 4 check-code blocks survive:

then the sub-matrix T^-By representing failureThe row in which the systematic code block is located and the column in which the check code block representing the survivor is located, because the systematic code blocks all fail and the check code blocks all survive, in this case, the submatrix T^-Equivalent to the shift matrix T.

According to the sub-matrix T^-Determining the starting position of the extracted check code packet, from the submatrix T^-The number of different rows and columns is extracted to minimize the sum of all numbers obtained, i.e. each row is O, and these O's are in different columns, thus starting with the first bit, i.e. C₅To C ₈1 to 10, check C₅To C₈Their first bits are all "exposed", respectively C₁To C₄The first bit of (a), i.e., the bit that has not been operated on with the bits of the other code blocks; then C is mixed₂First bit substitution of C₅Can solve out C₁Second order of (1), in the same way, with C₃First bit substitution of C₆Can solve out C₂Second bit of (C), will₄First bit substitution of C₇Can solve out C₃Second bit of (C), will₁First bit substitution of C₈Can solve out C₄The second bit of (c). Then, adding C₄First bit of (A) and C₂Second bit substitution of (2) into C₅Can solve out C₁The third bit of (1) and, similarly, sequentially cycles to solve C₁To C₄All the bits of the data element are decoded to obtain original information, and the decoding is finished, and the number at the upper right corner of each data element is a specific decoded sequence.

As shown in fig. 3 and 4, as a second embodiment of the decoding process of the present invention, it is assumed that three systematic code blocks and one check code block survive:

suppose the surviving code block is C₃，C₆，C₇，C₈The decoding process is as follows:

the method comprises the following steps: obtaining a sub-matrix T of a shift matrix T^-(ii) a At this time, the submatrix T^-Only three rows and three columns;

step two: extracting the submatrix T^-The number of different columns in each row is minimized, the first action is 0, the second action is1, the third row is 0, but 0 is in the same column as 1 in the second row, and therefore discarded, the second smallest number, i.e. 1, is found, where 1 is not in the same column as the previously selected 0 and 1, and therefore the selected 3 start values for bit fetch are as in the submatrix T of fig. 3^-Shown in boxes. Then, 10 bits of the survivor check code block are taken according to the bit taking rule, namely, C is taken₆1 to 10, C ₇2 to 11, C ₈2 to 11.

Step three: and carrying out bit-by-bit substitution decoding according to the extracted data elements of the surviving check code block and the surviving systematic code block. First inspection, C₂The first bit of (A) is leaked out, and can be solved without operation. Then C₃First bit substitution of C₆The second bit of (A) can solve C₂Second position of (A), handle C₃Second bit substitution of (2) into C₇Second bit of (2), solve for C₄First position of (A), a₂First bit of (A) and C₃Into C₇The third bit of (A) can solve C₄Second position of (A), handle C₄Second bit substitution of (2) into C₈Second bit of (2), can solve C₁The first bit of (1); then C₁First bit of (A) and C₃Second bit substitution of (2) into C₆Third bit of (2), can solve C₂Third position of (1), handle C₁First bit of (C)₂Second bit sum C₃Into the fourth bit of C₇Can solve C₄Third position of (1), handle C₃First bit of (A) and C₄Into C₈The third bit of (A) can solve C₁The second bit of (c). According to the numerical sequence number of the upper right corner of each bit data element, C can be solved₁、C₂、C₄All the number of bits.

As shown in fig. 5 and 6, as a third embodiment of the decoding process of the present invention, it is assumed that two systematic code blocks and two check code blocks survive:

suppose the surviving code block is C₁，C₂，C₅，C₆The decoding process is as follows:

the method comprises the following steps: obtaining a sub-matrix T of a shift matrix T^-(ii) a At this time, the submatrix T^-Only two rows and two columnsComposition is carried out;

step two: slave submatrix T^-The number of different rows and columns is extracted to minimize the sum of all the numbers obtained, the first action 2, the second action 1, wherein 2 and 1 are in different columns, then 10 bits of the survivor check code block are obtained according to the bit obtaining rule, namely C is obtained₅From the 3 rd position to the 12 th position of (A), take C ₆2 nd bit to 11 th bit.

Step three: and carrying out bit-by-bit substitution decoding according to the extracted data elements of the surviving check code block and the surviving systematic code block. Handle C₁Third position of (3), C₂Second bit substitution of (2) into C₅The third bit of (A) can solve C₄First position of (A), a₂Second bit substitution of (2) into C₆Can solve C₃The first bit of (1); c₁First bit of (A) and C₂Into C₆The third bit of (A) can solve C₃Second position of (A), C₁Second position of (1), C₂Fourth bit of (1) and C₄First bit substitution of C₆Can solve C₃The third digit of (1). By analogy, according to C₅，C₆The numerical sequence number of the upper right corner of each bit of the data element can be solved to obtain C₃And C₄Each bit of (a).

As shown in fig. 7 and 8, as a third embodiment of the decoding process of the present invention, it is assumed that three systematic code blocks and one check code block survive:

suppose the surviving code block is C₁，C₂，，C₃，C₅The decoding process is as follows:

the method comprises the following steps: obtaining a sub-matrix T of a shift matrix T^-(ii) a At this time, the submatrix T^-Only one row consists of one number;

step two: extracting the submatrix T^-Then 10 bits of survivor check code block are taken according to the bit taking rule, namely C is taken₅And 3 rd to 12 th.

Step three: and carrying out bit-by-bit substitution decoding according to the extracted data elements of the surviving check code block and the surviving systematic code block. Due to C₁，C₂，C₃Each of which knows directly the heel C₄Each bit of (a) carries out the corresponding bit substitution C of operation₅Then can solve out C₄Each bit of (a). And thus decodes the original message. According to C₅The numerical sequence number of the upper right corner of each bit of the data element can be solved to obtain C₄Each bit of (a).

Of course, the greater the number of surviving nodes, the easier it is to decode.

To ensure that the code is decodable, the sum of the surviving systematic code block and the check code block of this example is not less than

Where n is the total number of coded and non-coded packets.

This example applies not only to the coding method described in this example, but also to any decoding applying zigzag coding.

The invention also provides a system for realizing the network coding and decoding method, which comprises a coding module and a decoding module, wherein the coding module comprises:

the decoding module includes:

extraction ofA unit: for slave submatrix T^-Extracting the numbers of different rows and columns to minimize the sum of all the obtained numbers, wherein the selected value of each row represents the initial position of code extraction of the check code block corresponding to the row, and then extracting the first L bits of the check code packet from the initial position;

In the binary field, the invention shifts through the shift matrix, codes the original message to make it have MDS (n, k) property, then adopts zigzag (zigzag) decoding technique, reduces the decoding complexity, reduces the transmission bandwidth in the decoding process, greatly shortens the time delay of coding and decoding, and improves the coding and decoding efficiency.

The above-described embodiments are intended to be illustrative, and not restrictive, of the invention, and all changes that come within the meaning and range of equivalency of the claims are therefore intended to be embraced therein.

Claims

1. A network coding and decoding method comprises an encoding process and a decoding process, wherein the encoding process comprises the following steps:

characterized in that said decoding process comprises the steps of:

2. The network coding and decoding method according to claim 1, wherein: in the second step, the shift matrix T is a cyclic permutation matrix or an incremental shift matrix, in order to ensure the zigzag decoding and MDS properties, each element in the non-coded packet is shifted to the right by a designated bit according to a shift matrix row vector, and then the elements after being shifted to the right are subjected to bitwise exclusive OR according to columns, wherein any row or column in the shift matrix T has no same number; the differences of any two columns contain different elements.

3. The network coding and decoding method according to claim 2, wherein: each non-coded element is represented by a designated bit shifted to the right by the row vector, such as a shift matrix T, in which the (i, j) th element represents the coded packet C_i+kThe j row element of (1) is right shifted by the number of bits, and C is completed by the rule_i+kI ∈ {1,2, 3., n-k }, j ∈ {1,2, 3., k }.

4. The network coding and decoding method according to any one of claims 1 to 3, wherein: in the shift matrix T, the maximum number of each row is p, and then the length of the check code packet corresponding to each row is L + p.

5. The network coding and decoding method according to any one of claims 1 to 3, wherein: in step one, the sum of the surviving systematic code block and the check code block is not less than

6. A system for implementing the network coding and decoding method of any one of claims 1 to 5, comprising an encoding module and a decoding module, the encoding module comprising:

wherein said decoding module comprises:

an extraction unit: for slave submatrix T^-The number of different rows and columns is extracted to minimize the sum of all numbers obtained, and the selected value of each column represents the pair of columnsThe corresponding check code block takes the initial position of the code, and then the first L bits of the check code packet are taken from the initial position;

7. The system of claim 6, wherein: in a check code block coding unit, the shift matrix T is a cyclic permutation matrix or an incremental shift matrix, in order to ensure zigzag decoding and MDS properties, each element in a non-coded packet is shifted to the right by a designated bit according to a shift matrix row vector, and then the elements after right shift are subjected to bitwise XOR according to columns, wherein any row or column in the shift matrix T does not have the same number; the differences of any two columns contain different elements.

8. The system of claim 7, wherein: each non-coded element is represented by a designated bit shifted to the right by the row vector, such as a shift matrix T, in which the (i, j) th element represents the coded packet C_i+kThe j row element of (1) is right shifted by the number of bits, and C is completed by the rule_i+kI ∈ {1,2, 3., n-k }, j ∈ {1,2, 3., k }.

9. The system according to any one of claims 6-8, wherein: in the shift matrix T, the maximum number of each row is p, and then the length of the check code packet corresponding to each row is L + p.

10. The system according to any one of claims 6-8, wherein: in the acquisition unit of the decoding module, the sum of the surviving systematic code block and the check code block is not less than