JP2016092833A - Decoding technique, decoder and receiver - Google Patents

Abstract

PROBLEM TO BE SOLVED: To provide a decoding technique, a decoder and a receiver.SOLUTION: A decoder includes an initialization unit for initializing a first decoding matrix and a second decoding matrix to an all-zero matrix, a processing unit for making the diagonal elements of the first decoding matrix entirely 1, by receiving an encoding vector and generation vector information, and updating the first decoding matrix and second decoding matrix, based on the encoding vector and generation vector information, and a decoding unit for obtaining original data based on the updated first decoding matrix and second decoding matrix.SELECTED DRAWING: Figure 3

Description

  The present invention relates to the field of communication technology, and in particular, to a decoding method, a decoder, and a receiver.

  In a multihop network, an intermediate node on the path from the source node to the target node can forward (transfer) data, thereby realizing communication between the source node and the target node. be able to.

  FIG. 1 is a diagram illustrating a conventional communication method in a multi-hop network. As shown in FIG. 1, when nodes A and B transmit a data packet via the intermediate node S, at least four transmission steps, that is, the node A transmits the data packet a to the intermediate node S. The intermediate node S transmits the data packet a to the node B, the node B transmits the data packet b to the intermediate node S, and the intermediate node S transmits the data packet b to the node A.

をノードA及びBに送信し、これによって、ノードA、Bは、受信した符号化結果に対して復号を行うことで、データパケットb、aをそれぞれ得ることができる。これによって分かるように、ネットワーク符号化による通信方式では、A、B間のデータの伝送は、3つのみの伝送ステップ、即ち、ノードAがデータパケットaを中間ノードSに送信し、ノードBがデータパケットbを中間ノードSに送信し、そして、中間ノードSがネットワーク符号化の結果を１回のブロードキャストの形式でノードA及びBに送信するというステップを要する。よって、データ伝送のステップ及びそれに対応するタイムスロット（time slot）を節約することができる。 FIG. 2 is a diagram illustrating a communication method using network coding in a multi-hop network. As shown in FIG. 2, network encoding may be performed on the data packets a and b received by the intermediate node S. For example, an algebraic combination operation such as exclusive OR is performed on the data packets a and b. After that, the result of network coding by one broadcast transmission method (External 1)

Are transmitted to the nodes A and B, whereby the nodes A and B can obtain the data packets b and a by decoding the received encoding results, respectively. As can be seen, in the communication system using network coding, the transmission of data between A and B involves only three transmission steps: node A sends data packet a to intermediate node S, and node B A step is required in which the data packet b is transmitted to the intermediate node S, and the intermediate node S transmits the result of the network coding to the nodes A and B in the form of one broadcast. Therefore, a data transmission step and a corresponding time slot can be saved.

  In a multi-hop network that is more complex than the network shown in FIG. 2, each node may be a source node, an intermediate node, or a target node, so each source node employs a generation matrix to receive received data. The network or the data packet generated by the node itself may be subjected to network encoding, and the encoded data packet generated after the network encoding may be transmitted to a plurality of target nodes. Can decode the received encoded data packet to obtain the original data packet from the source node.

  In the communication system using network coding, the data transmission process is simplified, but the decoding process of the coded data packet is an important factor affecting the communication time delay.

  In the prior art, a plurality of types of decoding methods have been proposed. For example, in Reference 1, the target node performs decoding after receiving all encoded data packets encoded by the same generation matrix. Reference 1 and Reference 2 disclose a method called ED (Earliest Decoding, ED), that is, the target node can perform decoding after the received linearly independent encoded data packets reach a predetermined number. Although disclosed, the decoding process requires complex matrix inverse operations. Further, Document 2 discloses a method called MED (Modified Earliest Decoding (MED)), which can reduce the complexity of matrix inverse operation.

Reference 1: PA Chou, Y. Wu, and K. Jain, “Practical Network Coding”, the 51 ^st Allerton Conference on Communication, Control and Computing, 2003;
Reference 2: S. von Solms and ASJ Helberg, “Modified Earliest Decoding in networks that implement Random Linear Network Coding”, Africa Research Journal, vol. 103, no. 4, pp. 165-171, Dec 2012.

  In the decoding method of the above-mentioned document 1, since the reception time of all encoded data packets is directly proportional to the scale of the generation matrix, it may cause a relatively long communication time delay. In the above ED and MED methods, Since it is necessary to perform matrix inverse operation and decoding operation only after receiving a certain amount of encoded data packets, communication time delay may be increased.

  It is an object of an embodiment of the present invention to provide a decoding method, a decoder, and a receiver that can reduce a time required for decoding and reduce a communication time delay.

According to a first aspect of an embodiment of the present invention, a decoder is provided, wherein the decoder comprises:
An initialization unit for initializing the first decoding matrix and the second decoding matrix to an all-zero matrix;
Receiving the encoded vector and the corresponding generated vector information, and updating the first decoded matrix and the second decoded matrix based on the encoded vector and the generated vector information, so that the pair of the first decoded matrix A processing unit for setting all of the corner elements to 1; and a decoding unit for obtaining original data based on the updated first decoding matrix and the second decoding matrix.

  According to a second aspect of an embodiment of the present invention, a receiver is provided, which includes the above-described decoder according to the first aspect of the above-described embodiment.

According to a third aspect of an embodiment of the present invention, a decoding technique is provided, of which the decoding technique is
Initializing the first decoding matrix and the second decoding matrix to an all-zero matrix;
Receiving the encoded vector and the corresponding generated vector information, and updating the first decoded matrix and the second decoded matrix based on the encoded vector and the generated vector information, so that the pair of the first decoded matrix Including all of the corner elements as 1; and obtaining original data based on the updated first and second decoding matrices.

  The beneficial effect of the present invention is that processing can be performed on the current first decoding matrix and the second decoding matrix each time an encoded vector is received, and decoding is performed after a certain number of encoded vectors are received. Since there is no need to do this, the time required for decoding can be saved.

It is a figure which shows the conventional communication system in a multihop network. It is a figure which shows the communication system by network encoding in a multihop network. 3 is a flowchart of a decoding method according to the first embodiment. 6 is a flowchart for updating a first decoding matrix and a second decoding matrix in the first embodiment. 4 is a flowchart for performing conversion processing on a first decoding matrix and a second decoding matrix in the first embodiment. FIG. 6 is a diagram illustrating an example of a decoding flow in the first embodiment. FIG. 10 is a diagram showing another example of the decoding flow in the first embodiment. 6 is a configuration diagram of a decoder in Embodiment 2. FIG. 6 is a configuration diagram of a processing unit in Embodiment 2. FIG. 5 is a configuration diagram of a conversion unit in Embodiment 2. FIG. 10 is a configuration diagram of a receiver in Embodiment 3. FIG.

  Hereinafter, embodiments for carrying out the present invention will be described in detail with reference to the accompanying drawings.

  In the scenario of the present invention, each node in the wireless network may be a source node for transmitted data packets and a target node for received data packets.

  When the node is a source node, encoding is performed on K data packets received by the source node and / or generated by itself, and among the K data packets, The longest data packet has N digits, and other original data packets are supplemented with 0 to become N digits, thereby forming K original data packets. Accordingly, one or a plurality of encoded data packets waiting for transmission are generated by performing a linear combination on the K original data packets using the generation matrix G.

In the source node, these K original data packets are represented as x ₁ , x ₂ ,..., X _k , of which x _j (1 ≦ j ≦ K) is a 1 × N vector consisting of 0 and 1 Suppose that As a result, the K original data packets form a K × N original data matrix X as shown in the following equation (1).

Also, the encoding process performed on the original data matrix X using the generation matrix G can be expressed as the following equation (2).

であり、x_jは、オリジナルデータマトリックスX中の第j行のベクトルを表し、そのうち、符号化ベクトルy_iは、生成ベクトルg_iに対応する。 Among them, the generator matrix G is an N × K matrix, g _ij ∈ {0,1}, and represents a 1 × K vector composed of the i-th element of the generator matrix G with g _i , That is, the generation vector g _i = {g _i1 , g _i2 ,..., G _{i (k−1)} , g _k }, and the encoding matrix Y is a matrix composed of encoded data packets y _i , and each code The encoded data packet y _i (1 ≦ i ≦ N) is a 1 × N vector, ie, an encoded vector y _i , and
(Outside 2)

And x _j represents the vector of the j-th row in the original data matrix X, of which the encoded vector y _i corresponds to the generated vector g _i .

In the above equation (2), the multiplication operation and the addition operation are all operations on GF ₂ , and GF ₂ represents a quadratic finite field.

  In the source node, the generation matrix G can be randomly formed independently of other nodes, whereby the encoding process of different nodes becomes independent of each other, for example, the source node A generator matrix G can be formed using a random number generator.

When the source node transmits the encoded vector y _i , the corresponding generated vector g _i may be transmitted together, for example, the generated vector g _i is transmitted as a data header of the encoded vector y _i. May be. Alternatively, the generation matrix may be stored in advance in the source node and the target node, and when the source node transmits the encoded vector y _i , the index (Index) of the generation vector g _i may be transmitted together. Thus, the target node can determine the generation vector g _i based on the index and the pre-stored generation matrix. Therefore, the amount of data to be transmitted can be reduced.

  Hereinafter, a specific method in which the target node performs decoding will be described in detail based on each embodiment.

  Embodiment 1 of the present invention provides a decoding technique. FIG. 3 is a flowchart of the decoding method according to the first embodiment. As shown in FIG. 3, the decoding method includes the following steps.

S301: initializing a first decoding matrix and a second decoding matrix to an all-zero matrix;
S302: receiving an encoded vector and generated vector information, and updating the first decoded matrix and the second decoded matrix based on the encoded vector and the generated vector information, thereby Set all corner elements to 1;
S303: Original data is obtained based on the updated first decoding matrix and second decoding matrix.

In step S301, the first decoding matrix G ₀ may be initialized to a K × K matrix whose elements are all 0; even if the second decoding matrix Y ₀ is initialized to a K × N matrix. Well, all its elements are zero.

In step S302, receives the encoded vectors y _i and generates vector information I _g source node transmits, and, based on the coding vectors y _i and generates vector information I _g, the first decoding matrix G ₀ and the second An update process is performed on the decoding matrix Y ₀ , the first decoding matrix G ₀ is updated to the first decoding matrix G ′ whose diagonal elements are all 1, and the second decoding matrix Y ₀ is the second decoding matrix. When it is updated to Y ′, reception is stopped.

In step S302, the first decoding matrix G ₀ can be updated based on the generated vector information I _g , and the second decoding matrix Y ₀ can be updated based on the encoded vector y _i , Here, the update method of the first decoding matrix G ₀ and the second decoding matrix Y ₀ is the same.

In the embodiment of the present invention, the first decoding matrix G ′ may be an upper triangular matrix as shown in the following equation (3) or a lower triangular matrix as shown in the following equation (4). In (3) and (4), g ′ _{i, j} = 1, where 1 ≦ i ≦ k and 1 ≦ j ≦ k.

In step S303, the original data matrix X is obtained based on the first decoding matrix G ′ and the second decoding matrix Y ′ obtained after the update. For example, when the first decoding matrix G ′ is an upper triangular matrix as shown in Equation (3), the vector x _j of the j-th row in the original data matrix X is calculated as shown in the following Equation (5). Where g _j ′ represents the vector of the j th row of the first decoding matrix G ′ and y _j ′ represents the vector of the j th row of the second decoding matrix Y ′, where 1 ≦ j ≦ K.

  When the first decoding matrix G ′ is a lower triangular matrix as shown in the equation (4), the original data matrix X can be obtained by a calculation method similar to the equation (5).

  In the decoding method according to the embodiment of the present invention, the first decoding matrix and the second decoding matrix can be updated immediately after receiving the encoded vector and the corresponding generated vector information. As soon as the matrix is updated to the first decoding matrix G ′ whose diagonal element is 1, the reception can be stopped immediately, and the decoding is completed by obtaining the original data matrix X by a simple algebraic operation. be able to. Therefore, the time required for decoding can be shortened, and the amount of calculation for decoding can be reduced.

  Hereinafter, step S302 will be described in detail. Note that the following description is merely an example, and the embodiment of the present invention is not limited to this. In other words, step S302 can be performed by other methods.

  FIG. 4 is a flowchart of step S302. As shown in FIG. 4, step S302 includes the following steps.

S401: Receive encoded vector and generated vector information;
S402: determining a generation vector corresponding to the encoded vector based on the generation vector information;
S403: transforming the current first decoding matrix and the current second decoding matrix based on the encoding vector and the generation vector;
S404: It is determined whether or not all the diagonal elements of the converted first decoding matrix are 1. If “Yes”, the process is terminated, and if “No”, the process returns to Step 401 to return to the next one. One encoded vector and generated vector information are continuously received.

In the embodiment of the present invention, as described above, the generation vector information described above may be the generation vector itself or an index of the generation vector. When the generated vector information I _g received in step S401 is the generated vector g _i , in step S402, the generated vector g _i corresponding to the encoded vector y _i is directly determined based on the received generated vector information. it is determined well; when generated vector information I _g received in step S401 is an index corresponding to the generated vector, as described above, in step S402, based on the index and pre-stored product matrix received The generated vector g _i corresponding to the encoded vector y _i may be determined. Of course, embodiments of the present invention is not limited thereto, in other words, it may be determined The product vector g _i in other ways.

In step S403, based on the coding vectors y _i and the corresponding products vector g _i, performs conversion processing for the current first decoding matrix G ₀ and the second decoding matrix Y _0. In an embodiment of the present invention, based on the column number in the first or last one of the generation vectors g _{i in} the generation vector, the current first decoding matrix G ₀ and the second decoding matrix Y ₀ Determine which row of them to replace, and use the generated vector g _i and the encoded vector y _i to correspond to the corresponding one of the first decoding matrix G ₀ and the second decoding matrix Y ₀ Replace the row vector. In other words, the same conversion process can be performed on the first decoding matrix G ₀ and the second decoding matrix Y ₀ using the generated vector g _i and the encoded vector y _i , respectively.

In this embodiment, when the conversion process is not performed, the current first decoding matrix G ₀ and second decoding matrix Y ₀ in step S403 are initialized to the first decoding matrix G ₀ and the second decoding matrix initialized. may be a matrix Y _0, if the conversion process is performed, the first decoding matrix G ₀ and the second decoding matrix Y ₀ current in step S403, the first decoding obtained after the previous conversion process It may be a matrix G ₀ and a second decoding matrix Y ₀ .

In step S404, it is determined whether or not the first decoding matrix has been updated to the first decoding matrix G ′ whose diagonal elements are all 1. If “Yes”, the new encoding vector y _i and the generation vector are determined. The reception of the information _Ig is stopped. If “No”, the process returns to step S401 to receive the next one encoded vector and generated vector information.

  Hereinafter, the update process in step S403 will be described in detail with reference to the drawings. Note that the following description is merely an example, and the embodiment of the present invention is not limited to this. In other words, step S403 can be performed by other methods.

  As shown in FIG. 5, in one implementation, step S403 may include the following steps.

S501: Extract a column number in the generation vector of the first or last one of the generation vectors;
S502: It is determined whether or not an element whose row number is the same as the column number among diagonal elements of the current first decoding matrix is 0;
S503: When the element is 0, replace the row vector whose row number is the same as the column number in the current first decoding matrix with the generated vector, and also in the current second decoding matrix. The vector of the row whose row number is the same as the column number is replaced with the encoded vector.

In step S501, if it is the first column number a that is extracted from the generation vector g _i , the finally obtained first decoding matrix G ′ is an upper triangular matrix as shown in the above equation (3). If the extracted column number a is the last one in the generation vector g _i , the first decoding matrix G ′ finally obtained is a lower triangular matrix as shown in the above equation (4). is there.

In step S502, it is determined whether or not the element G ₀ (a, a) whose row number is the same as the column number a among the diagonal elements of the current first decoding matrix G ₀ is 0. Means that it is necessary to perform replacement processing for the vector in the a-th row of the current first decoding matrix G ₀ .

In step S503, when it is determined in step S502 that the element G ₀ (a, a) is 0, the vector g _0a of the a-th row in the current first decoding matrix G ₀ is replaced with the generated vector g _i . Also, the vector y _0a in the a-th row of the current second decoding matrix Y ₀ is replaced with the encoded vector y _i , that is, using the generated vector g _i and the encoded vector y _i , respectively. The same conversion operation can be performed on the current first decoding matrix G ₀ and the second decoding matrix Y ₀ .

  In the present embodiment, as shown in FIG. 5, step S403 may further include the following steps.

S504: When the element is not 0, one new generation is performed by performing a linear operation on the generation vector and a vector of a row whose row number is the same as the column number in the current first decoding matrix. A vector is generated, and the new generation vector is set as the generation vector, and the encoding vector and a vector of a row in the current second decoding matrix whose row number is the same as the column number are generated. Performing the linear operation to generate one new encoded vector, and setting the new encoded vector as the encoded vector;
S505: When all the elements of the new generation vector are not zero, return and perform the extraction process again.

In step S504, if it is determined in step S502 that the element G ₀ (a, a) is not 0, it means that the vector in the a-th row of the current first decoding matrix G ₀ has already been replaced in the previous update process. Therefore, by performing a linear operation on the generation vector g _i and the vector g _{0a in} the a-th row of the current first decoding matrix G ₀ , one new generation vector g _0ai is obtained, and The new generation vector is set as a generation vector g _i to be processed, and similarly, a linear operation is performed on the encoding vector y _i and the vector y _{0a in} the a-th row of the current second decoding matrix. Thus, one new encoded vector y _0ai is obtained, and this new encoded vector is set as an encoded vector y _i requiring processing.

In the embodiment of the present invention, the linear operation in step S504 may be, for example, an exclusive OR operation, whereby the new generation vector g _i and the new encoded vector y _i are respectively expressed by the following equations (6) , (7).

In step S505, when all the elements of the new generation vector g _i are not zero, the process returns to step S501 to extract the column number for the generation vector g _i and perform the subsequent processing again.

Also, if all elements of the product vector g _i after updating is zero, performing a receiving step and a subsequent update step again returns to step S401.

  In this embodiment, step S403 may further include the next step S506 (not shown) before step S504.

  S506: If the hamming weight of the generated vector is smaller than the hamming weight of a vector of a row whose row number is the same as the column number of the current first decoding matrix when the element is not 0, the first The row vector of the decoding matrix and the generation vector are exchanged (compatible) with each other, and the row vector of the second decoding matrix and the encoding vector are exchanged with each other, Then, the above-described linear calculation is performed on the exchanged results.

In step S506, when the element G ₀ (a, a) is not 0, the hamming weight w (g _i ) of the generated vector g _i is further compared with the hamming weight w (g _0a ) of the vector g _0a. If w (g _i ) <w (g _0a ), this means that the quantity of 1 in the generated vector g _i is less than the quantity of 1 in the vector g _0a , In order to reduce the generation vector g _i and the vector g _0a, and the encoded vector y _i and the vector y _0a may be compatible. Thereafter, in step S504, a linear operation is performed on the result after the compatibility.

Also, if w (g _i ) ≧ w (g _0a ), it means that the quantity of 1 in the generated vector g _i is greater than or equal to the quantity of 1 in the vector g _0a , so it is necessary to perform compatibility processing There is no, and directly enters step S504.

  In the present embodiment, the number of 1s in the first decoding matrix G ′ can be reduced by the above-described step S506, and accordingly, when the original data matrix X is calculated by using the above equation (5). The amount of computation is relatively small.

  Hereinafter, the complete decoding flow of the present invention will be described in detail with reference to the drawings and examples. The following description is merely an example, and the embodiment of the present invention is not limited to this. In other words, the decoding flow may have other modifications.

  FIG. 6 is an example of a decoding flowchart in Embodiment 1 of the present invention. As shown in FIG. 6, the decoding flow includes the following steps.

S601: a first decoding matrix and the second decoding matrix initialized, for example, a first decoding matrix G ₀ after the initialization may be a matrix of 7 × 7, be all the elements 0, after initialization The second decoding matrix Y ₀ may be a 7 × N matrix, and all of its elements are zero.

S602: receiving a generated vector g _i, which is transmitted together with the encoded vectors y _i and the encoded vectors y _i, for example, generated vector obtained in the m-th received g _i = {0,0,0 , 1,0,1,1} and m is a natural number.

S603: Extracting the first or last one column number a of the generation vector, for example, the generation vector g _i = {0,0,0,1,0,1,1} received this time Since the column number of the first 1 is 4, a = 4.

S604: Determining whether element G ₀ (a, a) in the current first decoding matrix G ₀ is 0, for example, determining whether G ₀ (4, 4) is 0 Here, the current first decoding matrix is a matrix that has not yet been updated after initialization, that is, each element of G ₀ may be 0. In this case, the determination result of step S604 is G _0. (a, a) = 0, and the process proceeds to step S605.

S605: Replace vector g _0a on the a-th row of the current first decoding matrix G ₀ with g _i, and replace vector y _0a on the a-th row of the current second decoding matrix Y ₀ with y _i , For example, the vector on the fourth row of the current first decoding matrix G ₀ is replaced with g _i = {0,0,0,1,0,1,1}, and the current second decoding matrix Y ₀ The vector on the fourth row can be replaced with y _i , and G ₀ after this replacement may be a matrix as shown in the following equation (8).

Of the first decoded matrix G ₀ after the replacement as shown in the above equation (8), g _0a = {0,0,0,1,0,1,1}.

S606: It is determined whether or not the diagonal elements of the first decoding matrix G ₀ after this replacement are all 1. If “Yes”, the process proceeds to step S607 to calculate the original data, for example, the above formula (5) may be adopted to perform the calculation. If the determination result is “No”, the process returns to step S602, and the reception and subsequent steps are performed again. For example, the first decoding matrix G of the above equation (8) is performed. As for _0, for all of its diagonal elements is not zero, a determination result of step S606 is "no", then returns to step S602, performs the (m + 1) times of reception.

Assume that the generated vector obtained in the (m + 1) th reception step S602 is g _i = {0,0,0,1,1,1,0}, and one of the generated vectors obtained by extraction in step S603. The column number of the first 1 is 4, and the current first decoding matrix G ₀ is a matrix as shown in Expression (8) in step S604, and among them, G ₀ (a, a) = 1, The determination result of step S604 is “No”, and the process proceeds to step S608.

である。 S608: Perform a linear operation on the generation vector g _i and the vector g _0a on the a-th row in the current first decoding matrix G ₀ to obtain one new generation vector g _0ai and the new A generation vector is set as a generation vector g _i , and a linear operation is performed on the encoding vector y _i and the vector y _0a on the a-th row in the current second decoding matrix to _obtain one new encoding vector y _0ai is obtained, and the new encoded vector is set as an encoded vector y _i . For example, if g _i = {0,0,0,1,1,1,0} and g _0a = {0,0,0,1,0,1,1},
(Outside 3)

It is.

S609: It is determined whether or not all elements of the generated vector g _i at this time are 0. If “Yes”, the process returns to step S602 to receive m + 2 times, and if “No”, step returning to S603, the extraction processing for the generated vector g _i at this time. For example, if g _i = {0,0,0,0,1,0,1}, the determination result in S609 is “No”, so the process returns to step S603.

Subsequently, at step S603, it extracts a 5 as one th 1 column number of the updated g _i.

In step S604, it is determined that G ₀ (5, 5) in the current first decoding matrix as shown in equation (8) is 0, and the process proceeds to step S605.

In step S605, the vector on the fifth row of the current first decoding matrix G ₀ is replaced with the updated g _i , and the vector on the fifth row of the current second decoding matrix Y ₀ is updated it can replace the _i, of which, G ₀ after replacement of this may be a matrix such as shown in the following equation (9).

Of the first decoded matrix G ₀ after this conversion as shown in the above equation (9), g _0a = {0,0,0,0,1,0,1}.

  FIG. 7 is another example of the decoding flowchart according to the first embodiment of the present invention. In the present embodiment, the same steps as those in FIG. 6 in FIG. 7 will not be described, and only different portions will be described.

  As shown in FIG. 7, steps S701 and S702 are further included in addition to steps S601 to S609. When the determination in step S604 is “No”, step S701 is executed.

In step S701, it is determined whether the hamming weight w (g _i ) of the generated vector g _i is smaller than the hamming weight w (g _0a ) of the vector g _{0a in} the current first decoding matrix G _0. If “yes”, the process proceeds to step S702. If “no”, the process proceeds to step S608. For example, if g _i = {0,0,0,1,1,0,0} and g _0a = {0,0,0,1,0,1,1}, then w (g _i ) <w (g _0a ), and at this time, the process proceeds to step S702.

In step S702, the generated vector g _i and the vector g _0a are made compatible, and the encoded vector y _i and the vector y _0a are made compatible. Thereafter, step S608 and the subsequent processing are performed on the result after the compatibility. Do. For example, the generated vector g _i and vector g _0a obtained after the compatibility are respectively g _i = {0,0,0,1,0,1,1} and g _0a = {0,0,0,1,1 , 0,0}.

  In the decoding method according to the embodiment of the present invention, the first decoding matrix and the second decoding matrix can be updated immediately after receiving the encoded vector and the corresponding generated vector information. As soon as the matrix is updated to the first decoding matrix G ′ whose diagonal element is 1, the reception can be stopped immediately, and the decoding is completed by obtaining the original data matrix X by simple algebraic operation. Can do. Therefore, the time required for decoding can be shortened, and the amount of calculation for decoding can be reduced. Also, the amount of decoding can be further reduced by replacing the corresponding vector in the first decoding matrix with an encoded vector having a relatively small Hamming weight.

  The second embodiment of the present invention provides a decoder, which corresponds to the decoding method of the first embodiment. FIG. 8 is a configuration diagram of a decoder in the second embodiment. As shown in FIG. 8, the decoder 800 includes an initialization unit 801, a processing unit 802, and a decoding unit 803.

Among them, the initialization unit 801, a first decoding matrix G ₀ and the second decoding matrix Y ₀ is initialized to all-zero matrix; processing unit 802 receives the encoded vector y _i and generates vector information I _g, the Updating the first decoding matrix and the second decoding matrix based on the encoded vector and the generated vector information, so that the diagonal elements of the first decoding matrix are all 1; Original data is obtained based on the updated first decoding matrix and second decoding matrix.

  FIG. 9 is a configuration diagram of the processing unit 802 according to the second embodiment. As shown in FIG. 9, the processing unit 802 includes a reception unit 901, a determination unit 902, a conversion unit 903, and a determination unit 904.

  Among them, the receiving unit 901 receives the encoded vector and the generated vector information; the determining unit 902 determines the generated vector corresponding to the encoded vector based on the generated vector information; Transform the current first decoding matrix and the current second decoding matrix based on the encoded vector and the generated vector; the decision unit 904 determines that all the diagonal elements of the converted first decoding matrix are all If it is “Yes”, the process is terminated, and if “No”, the receiving unit continuously receives one encoded vector and generated vector information.

  FIG. 10 is a configuration diagram of the conversion unit 903 of the second embodiment. As shown in FIG. 10, the conversion unit includes an extraction unit 1001, a first determination subunit 1002, and a first update unit 1003.

  Among them, the extraction unit 1001 extracts the column number in the first or last one of the generation vectors in the generation vector; the first determination subunit 1002 is the diagonal element of the current first decoding matrix. It is determined whether or not the element whose row number is the same as the column number is 0; the first update unit 1003 determines that the determination result of the first determination subunit 1002 is “the element is 0”. Sometimes, a vector of a row in the current first decoding matrix whose row number is the same as the column number is replaced with the generated vector, and a row number in the current second decoding matrix is the column number. Replace the row vector that is the same with the coded vector.

  As shown in FIG. 10, the conversion unit 903 further includes a calculation unit 1004 and a second determination subunit 1005.

  Among them, when the determination result of the first determination subunit 1002 is “the element is not 0”, the calculation unit 1004 has the same row number as the column number in the generated vector and the current first decoding matrix. A new generation vector is obtained by performing a linear operation on a vector of a row, and the new generation vector is set as the generation vector. The encoding vector and the current second decoding matrix To obtain a new encoded vector by performing a linear operation on a vector of the row whose row number is the same as the column number, and the new encoded vector as the encoded vector. To do.

  The second determination subunit 1005 determines whether or not all elements of the new generation vector are zero. If “No”, the extraction unit performs the extraction process on the new generation vector again.

  As shown in FIG. 10, the conversion unit 903 may further include a second update unit 1006. When the determination result of the first determination subunit 1002 is “the element is not 0”, the Hamming weight of the generated vector is the Hamming weight of the vector of the row whose row number in the first decoding matrix is the same as the column number. The second update unit 1006 is compatible with the vector of the row in the first decoding matrix and the generated vector, and the vector of the row in the second decoding matrix; Compatible with the coding vector, and the calculation unit performs the linear operation described above.

  In the second embodiment of the present invention, the operation principle of each unit of the decoder 800 corresponds to each step in the first embodiment, and thus detailed description thereof is omitted here.

  According to the decoder in Embodiment 2 of the present invention, the update process can be performed immediately on the first decoding matrix and the second decoding matrix after receiving the encoded vector and the corresponding generated vector information. As soon as the first decoding matrix is updated to the first decoding matrix G ′ whose diagonal element is 1, the reception can be stopped immediately, and the decoding can be performed by obtaining the original data matrix X by a simple algebra operation. Can be completed. Therefore, the time required for decoding can be shortened, and the amount of calculation for decoding can be reduced. Also, the amount of decoding can be further reduced by replacing the corresponding vector in the first decoding matrix with an encoded vector having a relatively small Hamming weight.

  Embodiment 3 of the present invention provides a receiver, which includes the decoder described in Embodiment 2.

  FIG. 11 is a block diagram of a receiver in the embodiment of the present invention. As shown in FIG. 11, the receiver 1100 may include a central processing unit (CPU) 1101 and a storage device 1102, and the storage device 1102 is coupled to the central processing unit 1101. Among them, the storage device 1102 can store various data, and may store an information processing program. Also, by executing the program under the control of the central processing unit 1101, it is possible to receive various types of information transmitted by the source node and transmit information to other nodes.

  In one implementation, the decoder functionality may be centralized in the central processing unit 200. Among them, the central processing unit 1101 initializes the first decoding matrix and the second decoding matrix to an all-zero matrix; receives the encoded vector and the corresponding generated vector information, and based on the encoded vector and the generated vector information Updating the first decoding matrix and the second decoding matrix so that the diagonal elements of the first decoding matrix are all 1, and then stopping reception; and the updated first The original data may be obtained based on the decoding matrix and the second decoding matrix.

  In other embodiments, the decoder may be arranged independently of the central processing unit, for example, the decoder is configured as a chip connected to the central processing unit 1101, and the decoder is controlled by the control of the central processing unit. The function may be realized.

  Further, as shown in FIG. 11, the receiver 1100 may further include an antenna 1103 and the like. Among these, the functions of such components are similar to those of the prior art, and thus detailed description thereof is omitted here. Note that the receiver 1100 does not have to include all the components as shown in FIG. Further, the receiver 1100 may further include parts not shown in FIG. 11, and the prior art can be referred to for this.

  Embodiments of the present invention further provide a computer readable program, of which when executing the program in a receiver, the program causes the computer to execute the decoding technique described in Embodiment 1 in the receiver.

  The embodiment of the present invention further provides a storage medium storing a computer readable program, wherein the computer readable program causes a computer to execute the decoding method described in the first embodiment in a receiver.

  The above apparatus and method of the present invention can be realized by hardware, and can also be realized by a combination of hardware and software. The present invention also relates to such a computer-readable program, that is, when the program is executed by a logic component, the logic component can cause the above-described apparatus or component to be realized, or the logic The component can implement the various methods or steps described above. The present invention further relates to a storage medium for the above-described program, such as a hard disk, a magnetic disk, an optical disk, a DVD, and a flash memory.

  Moreover, the following additional remarks are disclosed regarding the embodiment including each of the above-described examples.

(Appendix 1)
A decoder comprising:
An initialization unit for initializing the first decoding matrix and the second decoding matrix to an all-zero matrix;
Diagonal elements of the first decoding matrix by receiving encoded vector and generated vector information and updating the first decoding matrix and the second decoding matrix based on the encoded vector and the generated vector information A decoder comprising: a processing unit for causing all to be 1; and a decoding unit for obtaining original data based on the updated first decoding matrix and the second decoding matrix.

(Appendix 2)
The decoder according to appendix 1, wherein
The processing unit is
A receiving unit for receiving encoded vector and generated vector information;
A determination unit for determining a generation vector corresponding to the encoded vector based on the generation vector information;
A transform unit for transforming the current first decoding matrix and the current second decoding matrix based on the encoded vector and the generated vector; and diagonal elements of the transformed first decoding matrix; In order to determine whether or not all are 1, and to end the process if yes, and to make the receiving unit continuously receive the next one encoded vector and generated vector information if no A decoder including a decision unit.

(Appendix 3)
The decoder according to appendix 2, wherein
The decoder, wherein the generation vector information is a generation vector, and the determination unit determines the generation vector directly based on the generation vector information received by the receiving unit.

(Appendix 4)
The decoder according to appendix 2, wherein
The decoder, wherein the generation vector information is an index corresponding to the generation vector, and the determination unit determines the generation vector based on the index received by the receiving unit and a generation matrix stored in advance.

(Appendix 5)
The decoder according to appendix 2, wherein
The conversion unit is
An extraction unit for extracting a column number in the generation vector of the first or last one in the generation vector;
A first determining subunit for determining whether an element having a row number equal to the column number in a diagonal element of the current first decoding matrix is 0; and when the element is 0, Replace the vector of the row whose row number in the current first decoding matrix is the same as the column number with the generated vector, and the row number whose row number in the current second decoding matrix is the same as the column number. A decoder comprising a first update unit for replacing a vector with the encoded vector.

(Appendix 6)
The decoder according to appendix 5, wherein
The conversion unit further comprises:
When the element is not 0, a linear operation is performed on the generated vector and a vector of the row whose row number in the current first decoding matrix is the same as the column number, thereby obtaining one new generated vector. And taking the new generation vector as the generation vector, and linearly operating on the encoding vector and a vector of rows whose row number in the current second decoding matrix is the same as the column number A calculation unit for obtaining one new encoded vector and making the new encoded vector the encoded vector; and determining whether all elements of the new generated vector are zero If no, a second decision subunit is included for causing the extraction unit to perform an extraction process on the new generated vector. Decoder.

(Appendix 7)
The decoder according to appendix 6, wherein
The conversion unit further comprises:
If the hamming weight of the generated vector is less than the hamming weight of the row vector whose row number in the current first decoding matrix is the same as the column number when the element is not 0, in the first decoding matrix The vector of the row and the generated vector are compatible, the vector of the row in the second decoding matrix is compatible with the encoding vector, and the calculation unit performs the above-described operation. A decoder comprising a second update unit for causing

(Appendix 8)
A receiver,
Including a decoder, wherein the decoder comprises:
Initializing the first decoding matrix and the second decoding matrix to an all-zero matrix;
Diagonal elements of the first decoding matrix by receiving encoded vector and generated vector information and updating the first decoding matrix and the second decoding matrix based on the encoded vector and the generated vector information Are configured to obtain original data based on the updated first decoding matrix and the second decoding matrix.

(Appendix 9)
A decryption technique,
Initializing the first decoding matrix and the second decoding matrix to an all-zero matrix;
Diagonal elements of the first decoding matrix by receiving encoded vector and generated vector information and updating the first decoding matrix and the second decoding matrix based on the encoded vector and the generated vector information A decoding technique comprising obtaining original data based on the updated first decoding matrix and the second decoding matrix.

(Appendix 10)
The decoding method according to attachment 9, wherein
Updating the first decoding matrix and the second decoding matrix based on the encoded vector and the generated vector information,
Receiving encoded vector and generated vector information;
Determining a generated vector corresponding to the encoded vector based on the generated vector information;
Transforms the current first decoding matrix and the current second decoding matrix based on the encoded vector and the generated vector; and the diagonal elements of the first decoded matrix after the conversion are all 1 A decoding technique comprising: determining whether or not, if yes, terminating the process, and if no, continuing to receive the next one encoded vector and generated vector information.

(Appendix 11)
The decoding method according to attachment 10, wherein
A decoding method for determining the generation vector directly based on the received generation vector information when the generation vector information is a generation vector.

(Appendix 12)
The decoding method according to attachment 10, wherein
A decoding method for determining the generation vector based on the received index and a previously stored generation matrix when the generation vector information is an index corresponding to the generation vector.

(Appendix 13)
The decoding method according to attachment 10, wherein
Based on the encoded vector and the generated vector, transforming the current first decoding matrix and the current second decoding matrix comprises
Extracting the column number in the generation vector of the first or last one in the generation vector;
Determining whether the element whose row number in the diagonal element of the current first decoding matrix is the same as the column number is 0;
When the element is 0, the vector of the row whose row number in the current first decoding matrix is the same as the column number is replaced with the generation vector, and the row number in the current second decoding matrix is A decoding technique comprising replacing a vector of a row that is the same as a column number with the encoded vector.

(Appendix 14)
The decoding method according to attachment 13, wherein
Performing a transform on the current first decoding matrix and the current second decoding matrix based on the encoding vector and the generation vector further comprises:
When the element is not 0, a linear operation is performed on the generated vector and a vector of the row whose row number in the current first decoding matrix is the same as the column number, thereby obtaining one new generated vector. And obtaining the new generated vector as the generated vector, and the linear vector with respect to the encoded vector and a vector of rows in which the row number in the current second decoding matrix is the same as the column number. Obtaining a new encoded vector by performing an operation, and setting the new encoded vector as the encoded vector; and performing the extraction process again when all elements of the new generated vector are not zero. Including decryption techniques.

(Appendix 15)
The decoding method according to attachment 14, wherein
Performing a transform on the current first decoding matrix and the current second decoding matrix based on the encoding vector and the generation vector further comprises:
If the hamming weight of the generated vector is less than the hamming weight of the row vector whose row number in the current first decoding matrix is the same as the column number when the element is not 0, in the first decoding matrix The row vector and the generated vector, and the row vector in the second decoding matrix and the encoded vector are compatible, and the above-mentioned based on the result after the compatibility A decoding technique that includes performing a linear operation.

  The preferred embodiment of the present invention has been described above, but the present invention is not limited to this embodiment, and all modifications to the present invention belong to the technical scope of the present invention unless departing from the spirit of the present invention.

Claims (10)

A decoder comprising:
An initialization unit for initializing the first decoding matrix and the second decoding matrix to an all-zero matrix;
Diagonal elements of the first decoding matrix by receiving encoded vector and generated vector information and updating the first decoding matrix and the second decoding matrix based on the encoded vector and the generated vector information A decoding unit comprising: a processing unit that causes all to be 1; and a decoding unit that obtains original data based on the updated first decoding matrix and the second decoding matrix. The decoder according to claim 1, wherein
The processing unit is
A receiving unit for receiving the encoded vector and the generated vector information;
A determination unit for determining a generated vector corresponding to the encoded vector based on the generated vector information;
A transform unit that transforms the current first decoding matrix and the current second decoding matrix based on the encoded vector and the generated vector; and all the diagonal elements of the converted first decoding matrix are 1 If “Yes”, the process is terminated. If “No”, the receiving unit continuously receives the next one encoded vector and generated vector information. A decoder containing units. The decoder according to claim 2,
The generation vector information is a generation vector;
The decoding unit, wherein the determination unit determines the generation vector directly based on the generation vector information received by the reception unit. The decoder according to claim 2,
The generated vector information is an index corresponding to the generated vector;
The decoder, wherein the determination unit determines the generation vector based on the index received by the reception unit and a pre-stored generation matrix. The decoder according to claim 2,
The conversion unit is
An extraction unit for extracting a column number in the generation vector of the first or last one of the generation vectors;
A first determining subunit that determines whether an element of the diagonal element of the current first decoding matrix whose row number is the same as the column number is 0; and when the element is 0, Of the first decoding matrix of the first decoding matrix is replaced with the generated vector, and the row number of the current second decoding matrix is the same as the column number. A decoder comprising a first update unit that replaces a vector of a row with the encoded vector. The decoder according to claim 5, wherein
The conversion unit further comprises:
When the element is not 0, a new operation is performed by performing a linear operation on the generation vector and a vector of a row of the current first decoding matrix whose row number is the same as the column number. A vector is obtained, and the new generation vector is set as the generation vector, and the encoding vector and a vector of a row in the current second decoding matrix whose row number is the same as the column number are obtained. A calculation unit that obtains one new encoded vector by performing a linear operation on the encoded vector, and uses the new encoded vector as the encoded vector; and whether the elements of the new generated vector are all zero If the result is “No”, a second determination subunit that causes the extraction unit to perform extraction processing on the new generated vector is determined. No, the decoder. The decoder according to claim 6, wherein
The conversion unit further comprises:
When the element is non-zero and the hamming weight of the generated vector is smaller than the hamming weight of the vector of the row whose row number is the same as the column number of the current first decoding matrix, the first decoding Exchanging the vector of the row of the matrix with the generated vector, and exchanging the vector of the row of the second decoding matrix with the encoding vector, and the computing unit A decoder comprising a second update unit for causing a linear operation to be performed. A receiver including a decoder,
The decoder is
Initializing the first decoding matrix and the second decoding matrix to an all-zero matrix;
Receiving the encoded vector and the corresponding generated vector information, and updating the first decoded matrix and the second decoded matrix based on the encoded vector and the generated vector information, so that the pair of the first decoded matrix A receiver configured to cause all corner elements to be 1; and to obtain original data based on the updated first decoding matrix and the second decoding matrix. A decryption technique,
Initializing the first decoding matrix and the second decoding matrix to an all-zero matrix;
Diagonal elements of the first decoding matrix by receiving encoded vector and generated vector information and updating the first decoding matrix and the second decoding matrix based on the encoded vector and the generated vector information And obtaining all the original data based on the updated first decoding matrix and the second decoding matrix. The decoding method according to claim 9, wherein
Updating the first decoding matrix and the second decoding matrix based on the encoded vector and the generated vector information,
Receiving the encoded vector and the generated vector information;
Determining a generated vector corresponding to the encoded vector based on the generated vector information;
Transforms the current first decoding matrix and the current second decoding matrix based on the encoded vector and the generated vector; and the diagonal elements of the first decoded matrix after the conversion are all 1 A decoding method including: determining whether or not, and if “yes”, ending the process, and if “no”, continuously receiving the next one encoded vector and generated vector information.

Images