WO2019230371A1

WO2019230371A1 - Adaptive linear programming decoding method

Info

Publication number: WO2019230371A1
Application number: PCT/JP2019/019128
Authority: WO
Inventors: 博則牛坂
Original assignee: 日本電信電話株式会社
Priority date: 2018-05-28
Filing date: 2019-05-14
Publication date: 2019-12-05
Also published as: JP2019208097A

Abstract

The purpose of the present invention is to provide an ALP decoding method in which decoding by ALP of a hamming code is achieved, and as a result, implementation load of the decoding method can be reduced and computation time can be shortened. An ALP decoding method, provided with: a factor graph generation step for generating a factor graph of a hamming code defined by a prescribed check matrix; a constraint condition derivation step for deriving a constraint condition of a number node on the basis of a condition expression that a variable node ought to satisfy; an isolated variable node detection step for detecting an isolated variable node connected to a check node, from among variable nodes connected to a plurality of check nodes from the generated factor graph; a restriction addition step for adding a restriction in that the isolated variable node is an integer value; and a decoding result calculation step for calculating, on the basis of the constraint condition and information relating to the isolated variable node to which the restriction has been added, a solution by MILP and deeming the solution to be the result of decoding the hamming code.

Description

Adaptive linear programming decoding method

The present invention relates to an adaptive linear programming decoding method, and more particularly to a decoding technique using an adaptive linear programming method for a Hamming code.

Low density parity check code (Low Density Parity Check Code, hereinafter referred to as “LDPC”) is a code correction method first discovered by Gallarger and then developed by MacKay (see Non-Patent Document 2). This code correction is characterized in that a matrix called a sparse matrix is used as a check matrix.

FIG. 33 shows an example of the parity check matrix. In a sparse matrix (hereinafter referred to as “H”), for example, a matrix format often used in the case of 100 rows and 200 columns includes three “1” s contained in one column and one row. The number of “1” s is six. Since the number of “1” is sparse, it is called a sparse matrix.

33. In the example of the conventional LDPC parity check matrix shown in FIG. 33, a square loop having an arrangement of “1” surrounded by a broken-line circle is prohibited. Therefore, in this case, one of “1” surrounded by four broken lines is deleted.

Here, a conventional code correction method using LDPC will be described using the Mackay method. First, for all the rows of the sparse matrix, the probability r ^x _{mn of} whether it is “1” or “0” for the sign bit corresponding to the array element of “1” (where mn represents a matrix element) , X takes "0" or "1"). Thereafter, for the elements of “1” in all columns of the parity check matrix, using the calculated probability r ^x _mn , the probability q ^x _mn that the bit position of the code corresponding to that column is “1” or “0” is obtained. calculate.

The probability q ^x _mn is multiplied by the matrix element m and set as q ^x _n . When q ^x _n is larger than 0.5, it is “1”, and when it is smaller, it is “0”. If q is a vector having q ^x _n as a component, if q × H ^T = 0 is satisfied, q is a code to be obtained. The calculation of the probabilities q ^x _mn and r ^x _mn is called a probability propagation (hereinafter referred to as “BP”) method as if the probability density is propagated.

In contrast to such a conventional decoding method, as described in Non-Patent Document 1, Feldman proposed a decoding method using linear programming (hereinafter referred to as “LP”) in 2005. This obtains a log-likelihood ratio (hereinafter sometimes referred to as “LLR”) for each bit to be decoded, and creates a linear function with LLR as a coefficient and a code component as a variable.

The log likelihood ratio (LLR) is a logarithm of the ratio obtained by obtaining the probability that the bit is “0” and the probability that the bit is “1”. When the minimum value of the linear function is obtained by LP, the component at that time is a code to be decoded.

Non-Patent Document 3 discloses adaptive linear programming (Adaptive LP, hereinafter referred to as “ALP”), which is a further development of this LP. Explaining using the parity check matrix in FIG. 34, there have been only three parity checks so far corresponding to the number of rows in the parity check matrix, but the addition of the rows is also added to the parity check. is there.

This newly generated parity check is referred to as a redundant parity check (hereinafter referred to as “RPC”). When decoding is performed using this RPC, decoding characteristics (that is, Ber (Bit Error rate) vs. SNR (Signal Noise Ratio: SN ratio) characteristics) are improved.

However, when the conventional ALP decoding method is used for decoding the Hamming code, there is a case where LP does not work well and a solution cannot be obtained under the parity check of the linear combination by the original parity check of the check matrix (FIG. 34). is there. For this reason, there has been a problem that the load for implementing the decoding method is large and the calculation time becomes long.

The present invention has been made to solve the above-described problem, and realizes adaptive Hamming code decoding by ALP, and as a result, can reduce the implementation load of the decoding method and reduce the calculation time. An object is to provide a decryption method.

In order to solve the above-described problem, an adaptive linear program decoding method according to the present invention is an adaptive linear program decoding method executed by a decoding device including an arithmetic device, a storage device, and a communication control device. A factor graph generation step of generating a factor graph of a Hamming code defined by a predetermined parity check matrix received via the communication control device and storing the factor graph in the storage device; and the arithmetic device includes a plurality of the parity check matrices. A constraint condition deriving step for deriving a constraint condition of a variable node corresponding to each column based on a conditional expression to be satisfied by a variable node stored in the storage device; and the arithmetic device is stored in the storage device. Among the variable nodes connected to a plurality of check nodes respectively corresponding to a plurality of rows of the parity check matrix from the factor graph An isolated variable node detecting step for detecting an isolated variable node connected to two check nodes, a restriction adding step for adding a restriction in which the arithmetic device sets the isolated variable node to an integer value, and the arithmetic device comprises the Decoding result calculation that calculates a solution by mixed integer linear programming based on the constraint condition and the information on the isolated variable node to which the restriction is added, and stores the calculation result in the storage device as the decoding result of the Hamming code And a step.

In the adaptive linear programming decoding method according to the present invention, the Hamming code is an extended Hamming code based on the parity check matrix, and the restriction adding step is performed on the isolated variable node and the extended Hamming code of the parity check matrix. You may add the restriction | limiting which makes the isolated variable node detected at the said isolated variable node detection step an integer value.

Also, in the adaptive linear programming decoding method according to the present invention, the decoding result calculation step uses the mixed integer linear programming method by using a row of the parity check matrix and an arbitrary new row obtained by linear combination of the rows. You may calculate the solution by.

According to the present invention, an isolated variable node connected to only one check node among variable nodes connected to a check node from a factor graph of a Hamming code defined by a predetermined check matrix is an integer value. Therefore, the decoding result is calculated by the mixed integer linear programming, so that the decoding by the ALP of the Hamming code can be realized, the mounting load of the decoding method can be reduced, and the calculation time can be shortened.

FIG. 1 is a block diagram showing a hardware configuration of a decoding apparatus that performs an ALP decoding method according to an embodiment of the present invention. FIG. 2 is a diagram showing a parity check matrix according to the embodiment of the present invention. FIG. 3 is a diagram illustrating a factor graph corresponding to FIG. FIG. 4 is a diagram showing an example of the cost vector according to the embodiment of the present invention. FIG. 5 is a diagram showing expressions to be satisfied by variable nodes belonging to the check node according to the embodiment of the present invention. FIG. 6A is a diagram showing an example of an LP decoding program according to the embodiment of the present invention. FIG. 6B is a diagram showing an example of an LP decoding program according to the embodiment of the present invention. FIG. 7 is a diagram for explaining a procedure for deleting a variable node having an integer value in the factor graph of FIG. 3 by “x” and obtaining a circle formed by other variable nodes and check nodes. FIG. 8 is a diagram illustrating a determinant that should be satisfied by the parity check of the sum of the first and third rows of the parity check matrix in FIG. FIG. 9 is a factor graph showing the result of Step 2. FIG. 10 is a factor graph showing the result of Step 3. FIG. 11 is a factor graph showing the result of Step 4. FIG. 12 is a diagram illustrating a matrix in which the parity check matrix of FIG. 2 is rearranged. FIG. 13 is a diagram for explaining a reduction matrix of the matrix of FIG. FIG. 14 is a diagram for explaining replacement of columns of the parity check matrix in FIG. FIG. 15 is a diagram for explaining the simplification matrix of FIG. FIG. 16 is a diagram illustrating a factor graph reflecting the values of variable nodes in iteration 2-1 in Table 1. FIG. 17 is a flowchart for explaining the ALP decoding method according to the present embodiment. FIG. 18 is a diagram illustrating a parity check matrix of a shortened Hamming code. FIG. 19 is a diagram illustrating a factor graph corresponding to FIG. FIG. 20 is a diagram illustrating a factor graph reflecting the decoding result by LP. FIG. 21 is a diagram illustrating a factor graph reflecting a decoding result obtained by adding check nodes A + C. FIG. 22 is a diagram illustrating a matrix in which the columns of the check matrix in FIG. 18 are replaced. FIG. 23 is a diagram for explaining a reduction matrix of the matrix of FIG. FIG. 24A is a diagram illustrating a parity check matrix of an extended Hamming code. FIG. 24B is a diagram for explaining an expanded Hamming code. FIG. 25 is a diagram illustrating a factor graph corresponding to FIG. 24A. FIG. 26 is a diagram illustrating a factor graph reflecting the evaluation result. FIG. 27 is a diagram illustrating a matrix in which the parity check matrix in FIG. 24A is rearranged according to the decoding result. FIG. 28 is a diagram for explaining a reduction matrix of the matrix of FIG. FIG. 29 is a diagram illustrating a matrix in which the parity check matrix in FIG. 24A is rearranged according to the decoding result. FIG. 30 is a diagram for explaining a simplification matrix of the parity check matrix of FIG. FIG. 31 is a diagram illustrating a matrix in which the parity check matrix in FIG. 24A is rearranged according to the decoding result. FIG. 32 is a diagram for explaining a reduction matrix of the matrix of FIG. FIG. 33 is a diagram for explaining a conventional LDPC method. FIG. 34 is a diagram illustrating a check matrix for explaining a conventional decoding method.

Hereinafter, a preferred embodiment of the present invention will be described in detail with reference to FIGS.
[Principle of the Invention]
First, the principle of the present invention will be described.
First, as described above, it has been found by the simulation shown below that the Hamming code may not be decoded using ALP.

In the following, a code word of a Hamming code having a code length of 7, a signal length of 4 and a parity check length of 3 is written as C (7, 4, 3), and the check matrix is as shown in FIG.

Elements

7, 4, and 3 indicate a minimum number having different elements, that is, a minimum distance, in comparison between the entire code length, signal length, and parity check matrix row to be transmitted.

First, the Hamming code is decoded according to the Feldman method. In accordance with Chapter 5 of Non-Patent Document 4, simulation was performed in matlab (registered trademark) using the parity check matrix shown in FIG. 2 and the vector having the LLR shown in FIG. 4 as a component (hereinafter referred to as “cost vector”). .

In the example of the cost vector λ used in the LP shown in FIG. 4, it corresponds to the variable nodes x ₁ , x ₂ , x ₃ , x ₄ , x ₅ , x ₆ , x ₇ from the left. In this case, since x ₁ = 1, the coefficient (LLR) is −7/4, and other values are zero, so the LLR is “1”. The objective function f is set to f = (− 7/4) x ₁ + x ₂ + x ₃ + x ₄ + x ₅ + x ₆ + x ₇ , and the minimum value of the objective function f is obtained by LP, and the result is set as a decoding result.

In this case, a condition for the transmitted bit data to be a code is given by the equation shown in FIG. Here, x _n is a variable node (a node indicated by “circle” in FIG. 3 described later) connected to a check node (a node indicated by “square” in FIG. 3 described later). .

Here, the formula shown in FIG. 5 will be described using a specific example. n (m) is a collection of all variable nodes connected to the check node, and V is a subset of n (m).

The above expression represents a set obtained by excluding elements of V from elements of n (m), and | V | represents the number of elements. In order for the variable node x _{n to} be a sign, the equation shown in FIG. 5 is established, which means that | V | must be an odd number.

Taking the first row of the check matrix (hereinafter referred to as “check node A” and abbreviated as “chk (A)”) as an example, n (m) = {1, 2, , 4, 5}. Here, assuming that V = {1} and the element is x ₁ , one of the expressions to be satisfied is represented by the following expression (1).
x ₁ − (x ₂ + x ₄ + x ₅ ) ≦ 0 (1)

In the above equation (1), x ₁ is replaced with x ₂ , x ₄ , and x ₅ to obtain the same equation. These are reflected in the matrix A and the matrix b (arrows in FIG. 6A) in the example of the decoding program shown in FIG. 6A. In the program example shown in FIG. 6A, the case of the number of elements | V | = 3 in FIG. 6B is also reflected. Then, the minimum value of the objective function shown in FIG. 6A is obtained under the conditions of the matrix A and the matrix b. If all the found solutions are integers, that is the sign.

A specific example of the decryption process is shown below. Here, for the sake of simplicity, the code [0, 0, 0, 0, 0, 0, 0] is taken, and the first bit is inverted, and the transmission word is [1, 0, 0, 0, 0, 0, 0]. ] Is sent and decrypted by LP.

[Step 1]
When x ₁ = 1 in the last row of the matrix A, the value of the corresponding matrix b is “1” because the maximum value of x ₁ is determined. Since the LLR of the inversion bit is negative as shown in FIG. 4, x ₁ becomes infinitely large unless the corresponding value of the matrix b is set to “1” as described above.
The result was x = [1, 1/3, 0, 1/3, 1/3, 0, 0], which was consistent with the result of Non-Patent Document 4.

Thereafter, decoding is performed by ALP according to

Non-Patent Documents

3 and 4. At this time, since a non-integer element is obtained in Step 1, a factor graph (FIG. 3) for cutting out the integer element portion is required.

FIG. 3 is a diagram illustrating a factor graph corresponding to the parity check matrix illustrated in FIG. In the factor graph, the rows of the check matrix shown in FIG. 2 are the check nodes A, B, and C from the top, and the columns are the variable nodes x ₁ , x ₂ , x ₃ , x ₄ , x ₅ , x ₆ , x ₇ from the left. The relationship between the check node and the variable node is shown.

Since the

elements

1, 3, 6, and 7 are integers, the factor graph is configured as shown in FIG. 7 when the variable node is deleted. In the factor graph of FIG. 7, “x” is shown in the node of the integer part.

[Step 2]
Here, when a cycle (cycle) formed by parity check A (hereinafter referred to as “chk (A)”) and parity check C (hereinafter referred to as “chk (C)”) is employed, chk (A) + chk The condition to be satisfied by (C) is expressed by a determinant shown in FIG. In this case, x ₃ is zero for both chk (A) and chk (C), and x ₄ and x ₅ are zero because they are the same number of binary additions.

When the first line of the determinant shown in FIG. 8 is tried, 1 × 1 + (1/3) × (−1) = 2/3 ≦ 0 is satisfied and the inequality is not satisfied. Therefore, this first line is used as a constraint condition (hereinafter sometimes referred to as “cut”) and added to the constraint condition. Then run the program again to find the optimal solution of the objective function.

The result is x = [1, 2/3, 0, 1/3, 0, 1/3, 0], which is consistent with the result of Non-Patent Document 4. As in step 1, a parity check that is a cycle is searched using the factor graph shown in FIG.

[Step 3]
In this case, there are two cycles in FIG. Here, first, chk (B) and chk (C) are selected. Even if chk (B) and chk (C) are selected, x = [1, 2/3, 0, 1/3, 0, 1/3, 0] is a constraint condition x ₂ −x ₃ −x ₅ − x ₇ ≦ 0 is not satisfied. [0, 1, −1, 0, −1, 0, −1] and “0” are further added to the matrix A and the matrix b shown in FIGS. 6A and 6B, and the simulation is performed.

The results were obtained as follows.
x = [1,1 / 2,0,169 / 745,233 / 853,233 / 853,169 / 745]
Since the decimal number is converted into a fraction by the instruction “rats” at the end of the decryption program shown in FIG. 6A, the above result is expressed as follows when converted to the original decimal number.
x = [1.0000, 0.5000, 0.0000, 0.2268, 0.2732, 0.2732, 0.2268]
From this, it can be seen that x ₅ + x ₇ = 0.5, which satisfies the constraint condition x ₂ −x ₃ −x ₅ −x ₇ ≦ 0 added in this step.

Also, as in step 1 and step 2, create a factor graph and search for a parity check that is a cycle. FIG. 10 is a factor graph showing the above results. In the factor graph of FIG. 10, “x” is shown in the node of the integer part.

Using the conventional RPC search method described in Non-Patent Document 5, it can be seen that the result obtained in step 3 does not produce an RPC that is a redundant parity check. Details of the RPC search method described in Non-Patent Document 5 will be described later.

[Step 4]
Next, select another cycle. When chk (A) and chk (B) are selected, x = [1, 2/3, 0, 1/3, 0, 1/3, 0] satisfies the constraint condition x ₁ −x ₃ −x ₅ −x ₆ ≦ Does not satisfy 0. When calculated in the same manner as in Step 3, x = [1, 1/2, 0, 0, 1/2, 1/2, 0]. This factor graph is shown in FIG. The parity check in the cycle is chk (A) + chk (B) + chk (C). Further, in FIG. 11, “×” is shown in the node of the integer part.

[Step 5]
X = [1, 1/2, 0, 0, 1/2, 1/2, 0] calculated in step 4 does not satisfy the constraint condition x ₁ −x ₃ −x ₄ −x ₇ ≦ 0. The results calculated in the same manner as in Step 4 are as follows.
x = [0.2161, 0.0806, 0.0834, 0.0683, 0.0806, 0.0717, 0.0834] × 10 ⁻⁸

Table 1 shows the simulation results from Step 1 to Step 5 above. Further, Table 2 shows the calculation results obtained by performing the ALP decoding of the Hamming code (7, 4, 3) using the technique described in Non-Patent Document 4 under the same conditions as in the simulation.

Table 1 and Table 2 respectively show iteration (i), a parity check that is a cycle, a constraint condition (cut) of a redundant parity check (RPC), and a solution x that indicates a decoding result.

From the comparison between Table 1 and Table 2, it can be seen that (i) the final results are different from each other. Also, (ii) if iteration 2-1 is selected in the check node selection procedure in iteration 2-1 and iteration 2-2 shown in the calculation results of the simulation from step 1 to step 5 above, the analysis will be performed. You can see that it stops. The fact that the final results of (i) are different from each other can be determined to be coincident because the obtained results are very small and can be regarded as substantially zero.

In this example, the matrix A and the matrix b shown in the program example of FIG. 6A are manually set. However, in actuality, a program is selected to select an arbitrary row of the check matrix to create a linear combination, and the calculation is performed. Do.

Here, in order to determine whether or not RPC exists from the analysis of the received code, the RPC search method described in Non-Patent Document 5 is used. In the RPC search method described in Non-Patent Document 5, first, components of the vector x of the obtained solution are classified according to the order of (a) non-integer, zero, and 1. However, only non-integer elements are rearranged in order from the smaller element according to the absolute value of the distance from 1/2; (b) Next, the columns of the check matrix are arranged in the same order as in (a); (c) Then, the matrix portion of the non-integer elements is made into an echelon shape. At that time, when the weight of the row of the echeloon is only one (there is only one element in the row), the RPC exists.

An RPC search is performed using the simulation example described above. The solution x = [1, 2/3, 0, 1/3, 0, 1/3, 0] indicating the decoding result of iteration 1 in Table 1 is used. FIG. 12 shows a matrix A ₁ obtained as a result of performing the above steps (a) and (b). It should be noted that | 2 / 3−1 / 2 | = | 1 / 3−1 / 2 | = 1/6.

FIG. 13 shows the matrix A ₁ shown in FIG. 12 converted into a reduced matrix (hereinafter referred to as “rref”) according to the procedure (c). In this case, it can be seen that the matrix rref (A ₁ ) has three RPCs. The matrix rref (A ₁ ) shown in FIG. 13 is further converted using binary arithmetic rules (−1 = 1, 2 = 0).

This time, the solution x = [1.0000, 0.5000, 0.0000, 0.2268, 0.2732, 0.2732, 0.2268] indicating the decoding result of iteration 2-1 in Table 1 is used. FIG. 14 shows a matrix A _{1 in} which the columns of the check matrix are exchanged according to the procedures (a) and (b). Further, when the rref is obtained, the matrix rref (A ₁ ) shown in FIG. 15 is obtained, and it can be seen that there is no RPC since every matrix has two or more elements of “1” in the echeloon part. In FIG. 15, the fractional area is an area from 1 to 5 columns. FIG. 16 is a diagram in which the value of the variable node of iteration 2-1 in Table 1 is displayed on the factor graph.

Here, the factor graph based on step 3 of the simulation shown in FIG. Looking at the factor graph of FIG. 16, it can be seen that each common variable node is a fraction in order to satisfy the parity check. Here, in the factor graph that does not satisfy RPC, the variable node that becomes a fraction also occurs in the variable node (here, x ₇ ) connected only to its own parity check.

In this case, in order to satisfy the parity check (x ₂ −x ₃ −x ₅ −x ₇ = 0), one variable node (x ₅ ) is not needed, and the other variable nodes (x ₄ , x ₆ ) are not processed. In addition, the variable node (x ₂ ) of other check nodes (here, check nodes A and B) is a fraction. As a result, the number of variable nodes having fractions increases and the condition for generating RPC (in this case, the number of nodes of fractional variables ≦ 3) is not satisfied.

Therefore, in the present invention, a configuration is adopted in which, among the variable nodes connected to the check node, a variable node that is connected to nowhere other than the corresponding check node is added with a restriction that it is not an integer value. . In the present invention, a mixed integer linear programming (hereinafter referred to as “MILP”) obtained by extending a decoding method using LP is used to obtain an optimal solution for a problem having integer and real values in variable nodes. To decode the Hamming code.

[Embodiment]
Hereinafter, a decoding apparatus 1 for implementing an adaptive linear programming (ALP) decoding method according to the present invention will be described.

As shown in FIG. 1, the decoding device 1 includes a computing device 102 having a CPU 103 and a main storage device 104 connected via a bus 101, a communication control device 105, an external storage device 106, and a computer having a display device 107. It can be realized by a program for controlling these hardware resources.

The CPU 103 and the main storage device 104 constitute an arithmetic device 102. A program for the CPU 103 to perform various controls and calculations is stored in the main storage device 104 in advance. Note that the decoding device 1 may be configured with dedicated hardware for executing the decoding process. For example, an integrated circuit such as a graphic processor, an ASIC (Application Specific Integrated Circuit), or an FPGA (Field Programmable Gate Array) can be employed.

The communication control device 105 is a control device for connecting the decryption device 1 and various external electronic devices via the communication network NW. The communication control device 105 receives encoded data to be decoded via the communication network NW.

The external storage device 106 includes a readable / writable storage medium and a drive device for reading / writing various information such as programs and data from / to the storage medium. The external storage device 106 can use a semiconductor memory such as a hard disk or a flash memory as a storage medium. The external storage device 106 is a data storage unit 106a, a setting information storage unit 106b, a program storage unit 106c, and other storage devices (not shown), and for example, backs up programs and data stored in the external storage device 106. A storage device or the like.

The data storage unit 106 a stores encoded data and decoded data received via the communication control device 105.
The setting information storage unit 106b stores setting information such as information related to the check matrix, information related to the constraint conditions, predetermined conditional expressions, and information related to variable nodes that are integers.

The program storage unit 106c stores various programs for executing processing necessary for Hamming code decoding, such as matrix calculation processing, factor graph generation processing, constraint condition derivation processing, and RPC search processing in the present embodiment. Yes.

The display device 107 constitutes the display screen of the decryption device 1. The display device 107 is realized by a liquid crystal display or the like. On the display device 107, for example, the calculation result by the decoding device 1 such as a factor graph is displayed on the screen.

[ALP decoding process of Hamming code]
Next, the ALP decoding process of the Hamming code according to the present embodiment will be described with reference to the flowchart of FIG. In the present embodiment, a Hamming code (7, 4, 3) having a code length of 7, a signal length of 4, and a parity check length of 3 is subject to decoding, similar to the code used in [Principle of the Invention]. The parity check matrix shown is used.

First, the computing device 102 generates the factor graph shown in FIG. 3 from the parity check matrix shown in FIG. 2 (step S1). The generated factor graph is stored in the data storage unit 106a. In the factor graph shown in FIG. 3, the variable nodes x ₁ to x 7 are represented by “circles”, and the check nodes A, B, and C are represented by “squares”.

Next, the arithmetic unit 102 reads an expression (conditional expression) that the variable node x _n belonging to the check node stored in the setting information storage unit 106b should satisfy and an inequality that the Hamming code (7, 4, 3) should satisfy. Is derived (step S2). As a constraint condition, the above-described formula (1) (x ₁ − (x ₂ + x ₄ + x ₅ ) ≦ 0) is obtained. The arithmetic device 102 stores the derived constraint condition in the setting information storage unit 106b.

Next, the arithmetic unit 102 obtains a matrix A and a matrix b for setting conditions in the decoding process in the decoding program (FIG. 6A) stored in the program storage unit 106c (step S3). The computing device 102 sets, for example, the matrix A and the matrix b shown in FIG. 6B. In the matrix A, 1 in the last row [1, 0, 0, 0, 0, 0, 0] and the rightmost column of the matrix b represents x ₁ ≦ 1. The arithmetic unit 102 loads the obtained matrix A and matrix b in the decoding program.

Further, in the present embodiment, since the arithmetic unit 102 uses mixed integer linear programming (MILP), in the decoding program shown in FIG. 6A, the linear program (LP) function “linprob” to the MILP function “ Change to "intlinprob".

Next, the computing device 102 refers to a variable node connected to only one check node (hereinafter referred to as an “isolated variable node”) among the variable nodes connected to the check node in the factor graph generated in step S1. ) Is detected (step S4). In the example illustrated in FIG. 3, the arithmetic device 102 detects isolated variable nodes x ₁ , x ₃ , and x ₇ . The arithmetic device 102 temporarily stores information on the detected isolated variable node in the main storage device 104.

Next, the arithmetic unit 102 specifies that the isolated variable node detected in step S4 is only an integer value (step S5). Specifically, the arithmetic unit 102 imposes a restriction that an isolated variable node x ₁ , x ₃ , x _{7 can} only be an integer. More specifically, the arithmetic unit 102 gives the designation of isolated variable nodes x ₁ , x ₃ , x ₇ as integers by intcon = [1, 3, 7].

Thereafter, the arithmetic device 102 performs decoding by MILP to obtain a solution (step S6).
More specifically, the arithmetic unit 102 determines the MILP based on the constraint condition derived in step S2, the matrix A and the matrix b obtained in step S3, and the information on the isolated variable node to which the restriction to be an integer is added. And the calculation result is stored in the data storage unit 106a as a Hamming code decoding result.

More specifically, when the evaluation shown in Table 1 by MILP executed by the arithmetic unit 102 is performed, the solution x indicating the decoding result of the iteration 2-1 in Table 1 is x = [1, 1/2, 0 , 0, 1/2, 1/2, 0]. In the subsequent iterations, the values were the same as the solution x indicating the decoding results of

iterations

3 and 4 shown in Table 2.

As described above, according to the ALP decoding method of the Hamming code according to the present embodiment, any combination of check nodes can be obtained by finding a solution by linear programming under the condition that an independent variable node of the check matrix is an integer. But it can be seen that RPC exists. Therefore, in this case, the RPC search process according to Non-Patent Document 5 is unnecessary, the implementation of the decoding method is simplified, and the calculation time can be shortened. That is, the Hamming code can be decoded by applying the check node combinations in Table 2 in order.

[Modification 1]
Next, Modification 1 of the ALP decoding method for the Hamming code according to the present embodiment will be described. In Modification 1, the decoding of the shortened Hamming code (8, 4, 4) generated from the parity check matrix (15, 11, 3) shown in FIG. 18 (the parity check matrix of Example 2.20 of Non-Patent Document 6) will be described. To do.

Also in the first modification, the arithmetic unit 102 performs the decoding process from step S1 to step S6 shown in the flowchart of FIG. 17 on the shortened Hamming code as in the above-described embodiment. FIG. 19 shows a factor graph generated in step S1 by the arithmetic device 102 based on the parity check matrix.

Here, for comparison with the present invention, a solution of a decoding result derived by LP will be described. A solution x obtained by the arithmetic unit 102 performing the decoding by LP according to the decoding program shown in FIG. 6A is expressed by the following equation (2).
x = [1, 1/2, 1/2, 1/2, 0, 0, 0, 0] (2)
FIG. 20 shows a factor graph reflecting the decoding result. Integer nodes are indicated by “x”. Further, as shown in FIG. 20, it can be seen that there are five types of check node loops created from the variable nodes x ₂ , x ₃ , and x ₄ .

Specifically, a circle composed of check nodes A and C (hereinafter referred to as “AC”); a circle of check nodes composed of B and C (hereinafter referred to as “BC”); a loop of check nodes Is a circle composed of C and D (hereinafter referred to as “CD”); a circle of check nodes is composed of A, B, and C (hereinafter referred to as “ABC”); and a loop of check nodes is There are five types of circles composed of A, B, and D (hereinafter referred to as “ABD”). In the following, some cases will be considered.

(A) When Circle A-C is Selected In this case, one of the constraint conditions that should be satisfied by the sign is x ₁ −x ₃ −x when | V | = 1 from the conditional expression shown in FIG. ₅ −x ₇ ≦ 0. The solution x by LP shown in the above equation (2) does not satisfy this constraint condition. Here, [1, 0, −1, 0, −1, 0, −1, 0] is inserted into the matrix A in FIGS. 6A and 6B, and “0” is inserted into the matrix b, and the evaluation is performed. As a result, a solution x indicating a decoding result such as the following equation (3) was obtained.
x = [1, 1/3, 2/3, 1/3, 1/3, 0, 0, 0] (3)

FIG. 21 shows a factor graph of the decryption result obtained by adding the circles AC of check nodes represented by the above equation (3). As shown in FIG. 21, the circle created by each check node is the same as that shown in the factor graph of FIG.

Here, the RPC search method described in Non-Patent Document 5 is performed. FIG. 22 shows a matrix A _{1 in} which the columns of the parity check matrix shown in FIG. 18 are replaced by a solution x indicating the decoding result represented by the above equation (3), and FIG. 23 shows a matrix rref (A ₁ ) in the form of rref. Show. The numbers in the lower column of the matrix rref (A ₁ ) shown in FIG. 23 indicate the columns of A ₁ . As a result, since all rows satisfy the condition that RPC exists, the first row is taken. When this is confirmed by a factor graph reflecting the decoding result obtained by adding the check nodes (circles AC) shown in FIG. 21, it becomes a circle CD.

One of the parity checks made from this RPC is x ₁ −x ₂ −x ₇ −x ₈ ≦ 0, which does not satisfy the solution of the decoding result shown in the above equation (3). From this, [1, -1,0,0,0,0, -1, -1] is inserted into the matrix A shown in FIGS. 6A and 6B, and “0” is inserted into the matrix b. The solution x is calculated.

The solution x in this case is expressed by the following equation (4).
x = 1.0e-14 × [0.7219, 0.5291, 0.5291, 0.1532, 0.0469, 0.0044, 0.1538, 0.0469] (4)

Here, in the factor graph (FIG. 19) of the check matrix used in the first modification, isolated variable nodes x ₅ , x ₆ , x ₇ , and x ₈ connected to only one check node are integers. When the decoding is performed by MILP with the restriction of, the solution x of the decoding result is as follows.
x = [1, 1/2, 1/2, 1/2, 0, 0, 0, 0]
This result was the same as the solution of the decoding result when the limitation that the isolated variable nodes x ₅ , x ₆ , x ₇ , and x ₈ are not integers is added. However, when the decoding result by LP is calculated by adding the constraint x ₁ −x ₃ −x ₅ −x ₇ ≦ 0 when the circle AC is selected,
x = [0,0,0,0,0,0,0,0]
was gotten.

(B) When Circle BC is selected Next, when Circle BC is selected, the solution of the decoding result by LP when the restriction that the isolated variable node is an integer is not added is
x = [1, 1/3, 1/3, 2/3, 0, 1/3, 0, 0]
Is obtained, but the solution x of the decoding result by MILP when the restriction to make the isolated variable node an integer is added is
x = [0,0,0,0,0,0,0,0]
It became.

(C) When Circle ABD is selected Next, when Circle ABD is selected, the solution x of the decoding result by LP when the limitation that the isolated variable node is an integer is not added is ,
x = 1.0e-12 × [0.6749, 0.2305, 0.2305, 0.2305, 0.2297, 0.2297, 0.0096, 0.2297]
However, the solution x of the decoding result by MILP when the restriction that the isolated variable node is an integer is added is
x = [0,0,0,0,0,0,0,0]
It became.

The results of the above (a), (b) and (c) are shown in Tables 3 to 8.
Tables 3 and 4 show the decoding results of “no integer designation” and “integer designation” when the linear combination of the first and third rows of the parity check matrix is selected as the parity check, respectively.
Tables 5 and 6 show the decoding results of “no integer designation” and “integer designation”, respectively, when a linear combination of two and three rows of the parity check matrix is selected as the parity check.
Tables 7 and 8 show the decoding results of “no integer designation” and “integer designation”, respectively, when linear combination of 1 row, 2 rows, and 4 rows of the parity check matrix is selected as the parity check.

As described above, the decoding of the shortened Hamming code is also performed by obtaining the MILP solution by adding the restriction that designates an isolated variable node as an integer, so that the RPC search process becomes unnecessary, and the implementation of the ALP decoding method becomes easier. Further, by performing the evaluation under the condition that the isolated variable node is an integer, it is possible to reach the solution with a small number of evaluations, so that the calculation time in the decoding by LP can be shortened.

[Modification 2]
Next, a second modification of the ALP decoding method for the Hamming code according to the present embodiment will be described. In the second modification, decoding of the extended Hamming code (8, 4, 4) generated from the parity check matrix (7, 4, 3) illustrated in FIG. 24A will be described.

As shown in FIG. 24B, the expanded Hamming code is a Hamming code in which the parity check matrix is extended by adding 1 row and 1 column to the parity check matrix shown in FIG. In the example of FIG. 24B, 1 row and 8 columns in which all elements are “1” are added to the last row of the check matrix (FIG. 2) of the Hamming code (7, 4, 3) (arrow of FIG. 24B), and the last 3 rows and 1 column in which all elements are "0" are added to the column (arrow in FIG. 24B).

Also in the second modification, the arithmetic unit 102 executes the decoding process from step S1 to step S6 shown in the flowchart of FIG. 17 for the expanded Hamming code, similarly to the above-described embodiment. FIG. 25 shows a factor graph generated by the arithmetic unit 102 in step S1 based on the check matrix. In the factor graph shown in FIG. 25, the dotted line represents the connection by the new check node D in the expanded Hamming code.

Here, a solution derived by LP will be described for comparison with the present invention. A solution x indicating a decoding result by LP executed by the arithmetic device 102 according to the decoding program shown in FIG. 6A is expressed by the following equation (5).
x = [1, 1/3, 0, 1/3, 1/3, 0, 0, 0] (5)

The factor graph of the decryption result is shown in FIG. Integer nodes are indicated by “x”. The check nodes forming the circle are AB, AC, AD, CBD, CBA, and CBDA.

Here, the RPC search described in Non-Patent Document 5 is performed.
The columns of the parity check matrix shown in FIG. 24 are rearranged in the order of fraction; zero; 1 in accordance with the solution x by LP shown in the above equation (5). The rearranged matrix A ₁ is shown in FIG.

FIG. 28 shows a matrix rref (A ₁ ) obtained from the rearranged matrix A ₁ . In FIG. 28, the numbers shown above the matrix correspond to the columns of the parity check matrix in FIG. 24A. From the first row of the matrix rref (A ₁ ) shown in FIG.
x ₁ −x ₂ −x ₆ −x ₇ ≦ 0
The solution x indicating the decoding result by LP shown in the above equation (5) does not satisfy the above condition. As RPC (corresponding to circles AC), [1, -1,0,0,0, -1, -1,0] is inserted into the matrix A shown in FIGS. 6A and 6B, and the matrix b is inserted. Inserts “0” and performs LP decoding.

The solution x indicating the decoding result by LP is
x = [1, 2/3, 0, 1/3, 0, 1/3, 0, 0] (6)
It became.

Here, again, the columns of the parity check matrix shown in FIG. 24 are rearranged in the order of fraction; zero; 1 in accordance with the decoding result represented by the above equation (6). The rearranged matrix A ₁ is shown in FIG. Further, rref of the matrix A ₁ is obtained. FIG. 30 shows the matrix rref (A ₁ ). The numbers shown above the matrix in FIG. 30 correspond to the columns of the parity check matrix in FIG.

From the first row of the matrix rref (A ₁ ), _one of the constraint inequalities that the check node should satisfy is
x ₁ −x ₂ −x ₃ −x ₈ ≦ 0
However, the solution x indicating the decoding result by LP shown in the above equation (6) does not satisfy the above condition.

Further, [1, -1, -1,0,0,0, -1] is inserted into the matrix A shown in FIGS. 6A and 6B, and “0” is inserted into the matrix b, and the evaluation is performed again. Note that adding [1, -1, -1, 0, 0, 0, -1] to the matrix A is equivalent to adding check nodes A + C and A + D.

The solution x indicating the decryption result is
x = [1, 4/3, 1/4, 1/4, 0, 1/4, 0, 0] (7)
It became. When the columns of the parity check matrix shown in FIG. 24A are rearranged according to the decoding result shown by the above equation (7), the matrix A ₁ shown in FIG. 31 is obtained.

Further, when rref is obtained from the matrix A ₁ shown in FIG. 31, a matrix rref (A ₁ ) shown in FIG. 32 is obtained. The numbers shown above the matrix in FIG. 32 correspond to the columns of the check matrix in FIG. As shown in FIG. 32, it is indicated that there is no RPC, and the solution of the decoding result represented by the above equation (7) is determined.

Here, in the factor graph (FIG. 25) of the parity check matrix shown in FIG. 24A, if the variable nodes x ₁ , x ₃ , x ₇ , x ₈ are restricted to be integers, the integer variable nodes are “×” in the RPC search. It cannot be contributed to the circle. From this, the factor graph substantially includes, for example, check nodes D at variable nodes x ₂ , x ₄ , x _{5, and} x ₆ of the factor graph in the Hamming code (7, ₄ , ₃ ) shown in FIG. It has a connected structure.

When adding the restriction that the variable node is an integer, the decoding result by the first MILP is as follows:
x = [1, 1/3, 0, 1/3, 1/3, 0, 0, 0]
Thus, the same result as in the case where the variable node is not limited to an integer (equation (5)) was obtained. Similarly, when an RPC search is performed and evaluated, the decryption result is
x = [1, 2/3, 0, 1/3, 0, 1/3, 0, 0]
This is also the same result as when the variable node is not limited to an integer (equation (6)). When the RPC search is performed again and evaluated, the decryption result is
x = [0,0,0,0,0,0,0,0] and the correct answer was reached.

Regarding the decoding results of the extended Hamming code described above, the results for “no integer designation” and “integer designation” are shown in Table 9 and Table 10, respectively.

As described above, according to the second modification, even in the decoding of the extended Hamming code, a restriction that some variable nodes are integers is added, that is, the isolated variable nodes of the check matrix and the newly added check nodes are added. By adding the restriction that the isolated variable node is an integer, the solution of the decoding result can be reached.

Note that the combination of variable nodes that satisfy the expression to be satisfied by the variable nodes belonging to the check node shown in FIG. 5 has no effect on the decoding result. That is, even if the effect of such a combination of variable nodes is taken in and decoding by LP, the decoding result does not change at all.

It can be said that only the combination of parity checks that do not satisfy the relationship shown in FIG. 5 affects the decoding result. Since the integer specification for the variable node guarantees the existence of RPC, it is not necessary to use the RPC search process described in Non-Patent Document 5, and it is confirmed whether any parity check combination satisfies the relationship shown in FIG. Just do it.

The embodiments of the adaptive linear program decoding method of the present invention have been described above. However, the present invention is not limited to the described embodiments, and those skilled in the art assume the scope of the invention described in the claims. Various modifications can be made.

DESCRIPTION OF SYMBOLS 1 ... Decoding device, 101 ... Bus, 102 ... Arithmetic unit, 103 ... CPU, 104 ... Main storage device, 105 ... Communication control device, 106 ... External storage device, 106a ... Data storage unit, 106b ... Setting information storage unit, 106c ... Program storage unit 107 ... Display device, NW ... Communication network.

Claims

An adaptive linear program decoding method executed by a decoding device including an arithmetic device, a storage device, and a communication control device,
A factor graph generating step of generating a factor graph of a Hamming code defined by a predetermined check matrix received via the communication control device and storing the factor graph in the storage device;
A constraint condition deriving step in which the arithmetic device derives constraint conditions of variable nodes respectively corresponding to a plurality of columns of the parity check matrix based on conditional expressions to be satisfied by the variable nodes stored in the storage device;
The arithmetic device is connected to one check node among the variable nodes connected to a plurality of check nodes respectively corresponding to a plurality of rows of the parity check matrix from the factor graph stored in the storage device. An isolated variable node detecting step for detecting an isolated variable node;
A limit adding step in which the arithmetic unit adds a limit to the isolated variable node as an integer value;
The arithmetic unit calculates a solution by a mixed integer linear programming based on the constraint condition and the information on the isolated variable node to which the restriction is added, and the calculation result is used as the decoding result of the Hamming code. And a decoding result calculation step stored in the adaptive linear programming decoding method.
The adaptive linear program decoding method according to claim 1,
The Hamming code is an extended Hamming code based on the parity check matrix;
The limit adding step adds a limit with the isolated variable node detected in the isolated variable node detecting step as an integer value for the isolated variable node and the extended Hamming code of the parity check matrix. Planned decryption method.
The adaptive linear program decoding method according to claim 1 or 2,
The decoding result calculation step calculates a solution by the mixed integer linear programming using a row of the parity check matrix and an arbitrary new row obtained by linear combination of the rows. Decryption method.