Channel decoding method and channel decoding device

Abstract

This method and device makes it possible to implement maximum likelihood decoding of a sparse graph code at low computational complexity in the maximum likelihood decoding of the sparse graph code. This is, in the maximum likelihood of decoding of the sparse graph code, a lost data decoding process by a trivial decoding method and a lost data decoding process by a Gauss elimination method are performed repeatedly and alternately.

Claims

1. A channel decoding device, comprising: a computer; and a storage device that contains a program that causes the computer to: receive a data string that includes redundant data encoded based on a relation of a sparse graph; detect generation of lost data lost in a channel using data from the data string; and multiple times alternately and repeatedly: (a) decode the lost data using a trivial decoding method for restoring one piece of the lost data having no relation with other lost data uniquely; and (b) decode the lost data using a Gauss elimination method, thus yielding corrected data, wherein first, the lost data is decoded using the trivial decoding method, decoding of lost data using the Gauss elimination method is performed on at least one piece of the lost data, and when the at least one piece of the lost data is decoded using the Gauss elimination method, decoding of the lost data using the trivial decoding method is performed using a decoding result using the Gauss elimination method.

2. The channel decoding device according to claim 1, comprising: caching unit that acquires and stores an operation result in decoding the lost data using the trivial decoding method from a trivial decoding unit, and acquires and stores an operation result in decoding the lost data using the Gauss elimination method from a Gauss elimination method decoding unit; the trivial decoding unit, which reads the operation result in decoding the lost data using the Gauss elimination method from the caching unit, decodes the lost data by applying the read operation result to an operation in the trivial decoding method, and stores the operation result by the trivial decoding method in the caching unit; and the Gauss elimination method decoding unit, which reads the operation result in decoding the lost data using the trivial decoding method from the caching unit, decodes the lost data by applying the read operation result to an operation in the Gauss elimination method, and stores the operation result by the Gauss elimination method in the caching unit.

3. The channel decoding device according to claim 2, comprising: a degree sorting unit that rearranges a check matrix corresponding to the lost data that has not been restored completely in the trivial decoding unit in ascending order of degrees of the check matrix; and a pivot selecting/discharging unit that discharges the check matrix in ascending order of degrees of the check matrix as a triangular matrix using forward elimination.

4. The channel decoding device according to claim 3, further comprising: a Gauss column selecting unit that acquires a check matrix corresponding to the lost data that has not been restored completely in the trivial decoding unit, and selects one column in which the lost data is highly likely to be restored by the Gauss elimination method as a Gauss column from the check matrix; and a trivial column selecting unit that selects a column corresponding to the lost data that is restored by the trivial decoding method as a trivial column from the check matrix when it is assumed that the lost data of the Gauss column has been able to be restored, wherein until all columns of the check matrix belong to the Gauss column or the trivial column, alternately: (a) one column is selected as the Gauss column by the Gauss column selecting unit; and (b) the trivial column is selected by the trivial column selecting unit, the pivot selecting/discharging unit converts the trivial column into an identity matrix, and converts the Gauss column into the triangular matrix, and the Gauss elimination method decoding unit restores the lost data included in the Gauss column converted into the triangular matrix.

5. A channel decoding method that is performed by a computer in accordance with a program on a recording device, wherein the method comprises: receiving a data string that includes redundant data encoded based on a relation of a sparse graph; detecting generation of lost data lost in a channel using data from the data string; and multiple times alternately and repeatedly: (a) decoding the lost data using a trivial decoding method for restoring one piece of the lost data having no relation with other lost data uniquely; and (b) decoding the lost data using a Gauss elimination method, thus yielding corrected data, wherein first, the lost data is decoded using the trivial decoding method, decoding of lost data using the Gauss elimination method is performed on at least one piece of the lost data, and when the at least one piece of the lost data is decoded using the Gauss elimination method, decoding of the lost data using the trivial decoding method is performed using a decoding result using the Gauss elimination method.

6. The channel decoding method according to claim 5, further comprising: a caching process of acquiring and storing an operation result in decoding the lost data using the trivial decoding method from a trivial decoding process, and acquiring and storing an operation result in decoding the lost data using the Gauss elimination method from a Gauss elimination method decoding process; the trivial decoding process, which performs operations of reading the operation result in decoding the lost data using the Gauss elimination method from the caching process, decoding the lost data by applying the read operation result to an operation in the trivial decoding method, and storing the operation result by the trivial decoding method in the caching process; and the Gauss elimination method decoding process, which performs operations of reading the operation result in decoding the lost data using the trivial decoding method from the caching process, decoding the lost data by applying the read operation result to an operation in the Gauss elimination method, and storing the operation result by the Gauss elimination method in the caching process.

7. The channel decoding method according to claim 6, comprising: a degree sorting process of rearranging a check matrix corresponding to the lost data that has not been restored completely in the trivial decoding process in ascending order of degrees of the check matrix; and a pivot selecting/discharging process of discharging the check matrix in ascending order of degrees of the check matrix as a triangular matrix using forward elimination.

8. The channel decoding method according to claim 7, further comprising: a Gauss column selecting process of acquiring a check matrix corresponding to the lost data that has not been restored completely in the trivial decoding process, and selecting one column in which the lost data is highly likely to be restored by the Gauss elimination method as a Gauss column from the check matrix; and a trivial column selecting process of selecting a column corresponding to the lost data that is restored by the trivial decoding method as a trivial column from the check matrix when it is assumed that the lost data of the Gauss column has been able to be restored, wherein until all columns of the check matrix belong to the Gauss column or the trivial column, alternately: (a) one column is selected as the Gauss column by the Gauss column selecting process; and (b) the trivial column is selected by the trivial column selecting process, the pivot selecting/discharging process converting the trivial column into an identity matrix, and converts the Gauss column into the triangular matrix, and the Gauss elimination method decoding process restoring the lost data included in the Gauss column converted into the triangular matrix.

9. A non-transitory recording medium comprising a program that causes a computer to execute operations of: receiving a data string that includes redundant data encoded based on a relation of a sparse graph; detecting generation of lost data lost in a channel using data from the data string; and multiple times alternately and repeatedly: (a) decoding the lost data using a trivial decoding method for restoring one piece of the lost data having no relation with other lost data uniquely; and (b) decoding the lost data using a Gauss elimination method, thus yielding corrected data, wherein first, the lost data is decoded using the trivial decoding method, decoding of lost data using the Gauss elimination method is performed on at least one piece of the lost data, and when the at least one piece of the lost data is decoded using the Gauss elimination method, decoding of the lost data using the trivial decoding method is performed using a decoding result using the Gauss elimination method.

10. The non-transitory recording medium according to claim 9, wherein the program also causes the computer to perform operations of: a caching process of acquiring and storing an operation result in decoding the lost data using the trivial decoding method from a trivial decoding process, and acquiring and storing an operation result in decoding the lost data using the Gauss elimination method from a Gauss elimination method decoding process; the trivial decoding process, which performs operations of reading the operation result in decoding the lost data using the Gauss elimination method from the caching process, decoding the lost data by applying the read operation result to an operation in the trivial decoding method, and storing the operation result by the trivial decoding method in the caching process, and the Gauss elimination method decoding process, which performs operations of reading the operation result in decoding the lost data using the trivial decoding method from the caching process, decoding the lost data by applying the read operation result to an operation in the Gauss elimination method, and storing the operation result by the Gauss elimination method in the caching process.

11. The non-transitory recording medium according to claim 10, comprising: a degree sorting process of rearranging a check matrix corresponding to the lost data that has not been restored completely in the trivial decoding process in ascending order of degrees of the check matrix; and a pivot selecting/discharging process of discharging the check matrix in ascending order of degrees of the check matrix as a triangular matrix using forward elimination.

12. The non-transitory recording medium according to claim 11, further comprising: a Gauss column selecting process of acquiring a check matrix corresponding to the lost data that has not been restored completely in the trivial decoding process, and selecting one column in which the lost data is highly likely to be restored by the Gauss elimination method as a Gauss column from the check matrix; and a trivial column selecting process of selecting a column corresponding to the lost data that is restored by the trivial decoding method as a trivial column from the check matrix when it is assumed that the lost data of the Gauss column has been able to be restored, wherein until all columns of the check matrix belong to the Gauss column or the trivial column, alternately: (a) one column is selected as the Gauss column by the Gauss column selecting process; and (b) the trivial column is selected by the trivial column selecting process, the pivot selecting/discharging process converting the trivial column into an identity matrix, and converts the Gauss column into the triangular matrix, and the Gauss elimination method decoding process restoring the lost data included in the Gauss column converted into the triangular matrix.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIG. 1 is an explanatory diagram illustrating a packet erasure channel (a packet erasure channel (PEC)).

(2) FIG. 2 is a principle configuration diagram of the present disclosure.

(3) FIG. 3 is a basic configuration diagram illustrating a channel decoding device according to a first embodiment of the present disclosure.

(4) FIG. 4 is a flowchart illustrating an exemplary channel decoding method according to the first embodiment.

(5) FIG. 5 is a basic configuration diagram illustrating a channel decoding device according to a second embodiment of the present disclosure.

(6) FIG. 6 is a flowchart illustrating an exemplary channel decoding method according to the second embodiment.

(7) FIG. 7 is a basic configuration diagram illustrating a channel decoding device according to a third embodiment of the present disclosure.

(8) FIG. 8 is a flowchart illustrating an exemplary channel decoding method according to the third embodiment.

(9) FIG. 9 is a basic configuration diagram illustrating a channel decoding device according to a fourth embodiment of the present disclosure.

(10) FIG. 10 is a flowchart illustrating an exemplary channel decoding method according to the fourth embodiment.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT

(11) Hereinafter, exemplary embodiments of the present disclosure will be described in detail with reference to the appended drawings. The present disclosure is not limited to the following embodiments. The following embodiments are merely examples, and the present disclosure can be carried out in various changed or improved forms based on knowledge of those having skill in the art. In this specification and the drawings, components having the same reference numerals are assumed to be identical to each other.

(12) The present disclosure can be carried out without depending on a type of packet, but the description will proceed with an example of delivery using a UDP protocol used in multicast delivery. If the UDP protocol is used, a retransmission process is not performed even when a UDP packet is lost, unlike a TCP protocol, but it can be realized whether a received packet is correct as illustrated in FIG. 1, and there is a feature that it is regarded as an erasure channel in which a position of a lost packet is accurately known.

(13) FIG. 2 illustrates an error correction function for packet level FEC which can be implemented by the present disclosure. An error correction method according to the present disclosure includes a channel encoding process of performing a function of a channel encoding device 10, a packet-based transmission process of performing a function of a packet-based transmitting device 20, a packet-based receiving process of performing a function of a packet-based receiving device 30, and a channel decoding process of performing a function of a channel decoding device 40 in order. In the channel decoding process, a channel decoding method according to the present disclosure is used.

(14) Input information such as video data or audio data is encoded by the channel encoding device 10. At this time, fragmentation and the like in which a packet size and the like are considered is commonly performed in the packet-based transmitting device 20 connected thereto. As a specific example of the channel encoding device 10, when a linear code such as an LDPC code is used, redundant data is generated by the following encoding process.
[Math 1]
C.sub.m.sup.t=[T.sub.m,m.sup.1][G.sub.m,k]S.sub.k.sup.t(1)

(15) Here, S indicates an input information such as video data which performed fragmentation with a certain size, and G and T are sparse matrices corresponding to the sparse graph. An encoding process is known to be performed at a high speed by employing a triangular matrix as T.

(16) The packet-based transmitting device 20 transmits video data or audio data and generated parity data according to a FLUTE standard (RFC 3926) or the like. At a reception side, a transmitted packet is received by the packet-based receiving device 30. The channel decoding device 40 executes the channel decoding process of decoding data of the received packet. At this time, the maximum likelihood decoding unit 42 compares a header format of FLUTE or the like, and makes an attempt to restore a lost packet in case packet loss occurs. It is previously known at the channel decoding device 40 that the following constraint equation is held corresponding to encoding.

(17) $\begin{array}{cc}\left[\mathrm{Math}2\right]& \\ 0=\left[G_{m,k}|T_{m,m}\right]\left[\frac{S_k^t}{C_m^t}\right]& \left(2\right)\\ =\left[H_{m,n}\right]x_n^t& \left(3\right)\end{array}$

(18) For this reason, in the channel decoding device 40, when there is a lost packet, reconstructing a lost packet while satisfying the constraint with as a small number of operations as possible becomes a problem. Here, when .sub.L is an index set of a lost packet, H.sub.L is a parity check matrix corresponding to a lost packet, and x.sub.L is a set of lost packets, the above Formula is rewritten as the following Formula:
[Math 4]
[H.sub.L]x.sub.L.sup.t=[H.sub.R]x.sub.R.sup.t(4)

(19) Here, .sub.R is an index set of a received packet.

(20) If the number of ranks of H.sub.L is the number |x.sub.L| of lost packets in the above Formula, the lost packet can be restored by the maximum likelihood decoding. However, when the Gauss elimination method known as the maximum likelihood decoding method is simply applied to the above Formula, an operation of O(N.sup.3) is necessary for pre-processing of obtaining an inverse matrix of H.sub.L, and an operation of O(N.sup.2) is necessary for an operation of restoring the lost packet x.sub.L actually. In order to reduce these operations, for example, techniques disclosed in Non Patent Literature 5 and 6 have been proposed.

(21) According to the present disclosure, when the constraint is satisfied in a channel decoding device, maximum likelihood decoding capable of showing a maximum of error correction capabilities added by a channel encoding device is efficiently implemented at low computational complexity.

First Embodiment

(22) FIG. 3 illustrates a basic configuration diagram of a channel decoding system that implements the maximum likelihood decoding using the trivial decoding method and the Gauss elimination method repeatedly. 101 indicates a trivial decoding unit that restores lost data for each symbol by a small number operations, 102 indicates a Gauss elimination method matrix processing unit that performs pre-processing necessary for decoding lost data through the Gauss elimination method, and 103 indicates a Gauss elimination method decoding unit that restores lost data through the Gauss elimination method based on the matrix process of 102. The respective components will be described below.

(23) The present system is a channel decoding system that efficiently performs the maximum likelihood decoding on loss occurring on the erasure channel by a small number of processes. For the sake of simplicity, as a preferable example in which the present system functions effectively, an example in which IP packet transmission on the Internet serving as a representative channel of an erasure channel is assumed, and an LDPC code configured by a sparse graph is assumed as a code will be described below with reference to FIG. 4.

(24) When input data is input to the channel decoding device 100, the input data is transferred to the trivial decoding unit 101, and an attempt to restore lost data is made (S101 to S103). In the linear code, it is previously known that a product of received data and a parity check matrix H of each block is 0 (zero).
[Math 5]
0=[H.sub.m,m]x.sub.n.sup.t(5)

(25) Thus, the trivial decoding unit 101 uniquely restores one piece of lost data having no relation with other lost data as restored lost data. This is equivalent to a process of sequentially restoring only one piece of lost data included in each row in the above Formula. The trivial decoding unit 101 can restore lost data through a small number of operations by this processing, if an element thereof is broken down in detail, it can be summed up into two factors: (1) it is unnecessary to perform pre-processing for restoring lost data; and (2) it is possible to restore lost data such as a packet by a small number of processes using characteristics of the sparse graph.

(26) When there is still lost data which has not been able to be restored by the first trivial decoding unit 101 (no in S104), the maximum likelihood decoding is attempted by applying the Gauss elimination method (S105 to S107). This yields an effect of reducing the number of operations of the Gauss elimination method by initially applying the trivial decoding method, similarly to the technique disclosed in Non Patent Literature 6.

(27) In the Gauss elimination method, first, pre-processing of restoring lost data is performed through the Gauss elimination method matrix processing unit 102. The first trivial decoding unit process 101 ends, and when a non-restored lost data index set is .sub.L, a parity check matrix corresponding to a non-restored lost packet is H.sub.L, and a set of non-restored lost packets is x.sub.L, Formula (5) is rewritten as the following Formula:
[Math 6]
[H.sub.L]x.sub.L.sup.t=[H.sub.R]x.sub.R.sup.t(6)

(28) Here, .sub.R is an index set of received data and data restored by the first trivial decoding. An effect obtained by applying the trivial decoding method is derived from that the magnitude by which the Gauss elimination method is applied is
|.sub.L||.sub.L|.

(29) The Gauss elimination method matrix processing unit 102 performs triangular matrix conversion on the above Formula H.sub.L through a forward elimination operation. Here, the forward elimination operation is an operation of setting column elements below a pivot to 0 (zero) through an operation between TOWS.

(30) When a matrix obtained by performing triangular matrix conversion through the forward elimination operation is indicated by H, Formula (6) is converted into the following Formula:
[Math 7]
[H.sub.L]x.sub.L.sup.t=[H.sub.R]x.sub.R.sup.t(7)

(31) Matrix information generated by the Gauss elimination method matrix processing unit 102 is transferred to the Gauss elimination method decoding unit 103, and actually, one or more pieces of lost data x.sup.t.sub.R is restored as restored lost data by backward substitution. Commonly, since decoding of lost data by the backward substitution costs more than decoding of lost data by the trivial decoding method, small restored lost data is desirable in the Gauss elimination method decoding unit 103 in terms of computational complexity. Thus, in this process, it is recommended to restore one piece of lost data which is the smallest restoration number, and data is transferred to the trivial decoding unit 101 again.

(32) Again, in the trivial decoding unit 101, similarly to the first trivial decoding, one piece of lost data having no relation with other lost data is uniquely sequentially restored as restored lost data. When all losses can be recovered, a data string is output as output data (yes in S104), but when there is non-restored data, it returns to the Gauss elimination method decoding unit 103 (no in S104), one piece of lost data is restored as restored lost data, and the process of performing the trivial decoding is repeated until all losses are recovered whenever possible.

(33) As described above, in the channel decoding method according to the present embodiment, the trivial decoding unit 101 performs steps S101 to S105, the Gauss elimination method matrix processing unit 102 performs step S107, and the Gauss elimination method decoding unit 103 performs step S106. As a result, in the disclosure according to the present embodiment, the number of data actually restored by the Gauss elimination method is reduced, and the number of data restored by the trivial decoding method is increased, and thus the maximum likelihood decoding in which the number of operation processes is reduced can be implemented. Further, when the present method is applied so that as a small number of operations as possible is performed, a completion state in which all lost data is decoded is formed by the trivial decoding unit 101.

Second Embodiment

(34) FIG. 5 illustrates a basic configuration diagram of a channel decoding system that implements the maximum likelihood decoding using the trivial decoding method and the Gauss elimination method repeatedly. 201 indicates a trivial decoding unit that restores lost data by a small number operations, 202 indicates a decoding partial caching unit that holds partial data of a restoration operation process as a cache when lost data is reconstructed through the trivial decoding unit 201 and a Gauss elimination method decoding unit 204, 203 indicates a Gauss elimination method matrix processing unit that performs pre-processing necessary for decoding lost data through the Gauss elimination method, and 204 indicates a Gauss elimination method decoding unit that restores lost data through the Gauss elimination method based on the matrix process of 203. The respective components will be described below.

(35) The present system is a channel decoding system that efficiently performs the maximum likelihood decoding on loss occurring on the erasure channel by a small number of processes. For the sake of simplicity, similarly to the first embodiment, as a preferable example in which the present system functions effectively, an example in which IP packet transmission on the Internet serving as a representative channel of an erasure channel is assumed, and an LDPC code configured by a sparse graph is assumed as a code will be described below with reference to FIG. 6.

(36) When input data is input to the channel decoding device 200, the input data is transferred to the trivial decoding unit 201, and an attempt to restore lost data is made (S201 to S203). In the linear code, it is previously known that a product of received data and a parity check matrix H of each block is 0 (zero). For this reason, the trivial decoding unit 201 uniquely restores one lost data having no relation with other lost data as the restored lost data.

(37) If all lost data has been restored at the first trivial decoding unit 201 (no in S204), the decoding process ends, and data is output. However, when there is still lost data which has not been able to be restored by the first trivial decoding unit 201, similarly to the first embodiment, the maximum likelihood decoding is attempted by applying the Gauss elimination method (S205 to S207), but part of the operation result calculated by the trivial decoding unit 201 is held in the decoding partial caching unit 202 before the maximum likelihood decoding is attempted. This is because the computational complexity is expected to be reduced by using the held part when lost data is reconstructed by the subsequent Gauss elimination method.

(38) The Gauss elimination method matrix processing unit 203 performs the triangular matrix conversion through the forward elimination, similarly to the first embodiment, but at this time, in order to effectively use the cache of the decoding partial caching unit 202, Formula (6) is changed to the following Formula using an identity matrix I and a cache memory r.
[Math 8]
[H.sub.]x.sub..sup.t=[I.sub.m,m](r+[H.sub.]x.sub..sup.t)(8)

(39) A matrix that has undergone the triangular matrix conversion is derived as the following Formula:
[Math 9]
[H.sub.]x.sub..sup.t=[I.sub.m,m](r+[H.sub.]x.sub..sup.t)(9)

(40) Here, I is a matrix obtained by performing an operation corresponding to the forward elimination on the identity matrix.

(41) The Gauss elimination method decoding unit 204 restore one or more pieces of lost data through a relational expression derived by the Gauss elimination method matrix processing unit 203, similarly to the first embodiment (S206), but at this time, since a portion corresponding to [H.sub.]x.sub..sup.t on the right side of Formula (9) is data already held in the decoding partial caching unit 202, it is possible to additionally reduce the computational complexity using the cache data r. Further, when the lost data is restored, part of the calculated operation result is held in the decoding partial caching unit 202. Specifically, the part is calculation data corresponding to [H.sub.]x.sub..sup.t on the right side of Formula (9). Here, it is a partial operation result of a part excluding I on the right side other than an operation result of the entire right side used for reconstruction of lost data and thus called a partial cache.

(42) When one or more pieces of lost data are restored as restored lost data, it returns to the trivial decoding unit 201 again, and one lost data having no relation with other lost data is uniquely restored as restored lost data. In this process, when all losses can be recovered, a data string is output as output data (yes in S204), but when there is non-restored data (no in S204), it returns to the Gauss elimination method decoding unit 204, one piece of lost data is restored as restored lost data (S205 to S208), and the process of performing the trivial decoding is repeated until all losses are recovered whenever possible.

(43) As described above, in the channel decoding method according to the present embodiment, the trivial decoding unit 201 executes steps S201 to S205, the Gauss elimination method matrix processing unit 203 executes step S207, and the Gauss elimination method decoding unit 204 executes step S206. In these process, when there is already corresponding data in the decoding partial caching unit 202, the corresponding data is read from the caching unit and then used, and when there is no corresponding data, part of a corresponding operation result calculated when lost data is restored is held in the decoding partial caching unit, and thus the number of operation processes can be reduced.

(44) The above embodiment has been described in connection with the example using the diagonal matrix, but the present disclosure is not limited thereto. For example, instead of using the diagonal matrix, an exclusive OR may be used. In this case, an exclusive OR of a packet is performed directly on the data of the decoding partial caching unit 202. In other words, the right side used for reconstruction of lost data is calculated by performing an exclusive OR of a packet directly on [H.sub.]x.sub..sup.t on the right side of Formula (8).

Third Embodiment

(45) FIG. 7 illustrates a basic configuration diagram of a channel decoding system that implements the maximum likelihood decoding using the trivial decoding method and the Gauss elimination method repeatedly. 301 indicates a trivial decoding unit that restores lost data by a small number operations, 302 indicates a decoding partial caching unit that holds partial data of a restoration operation process as a cache when lost data is reconstructed at the trivial decoding unit 301 and a Gauss elimination method decoding unit 305, 303 indicates a degree sorting unit that sorts the sparse graphs according to a degree, 304 indicates a pivot selecting/discharging unit that selects a pivot and performs the forward elimination, and 305 indicates a Gauss elimination method decoding unit that actually restores lost data. Here, the pivot refers to an axis used as a reference when the forward elimination is performed. The respective components will be described below.

(46) The present system is a channel decoding system that efficiently performs the maximum likelihood decoding on loss occurring on the erasure channel by a small number of processes. For the sake of simplicity, similarly to the first and second embodiments, as a preferable example in which the present system functions effectively, an example in which IP packet transmission on the Internet serving as a representative channel of an erasure channel is assumed, and an LDPC code configured by a sparse graph is assumed as a code will be described below with reference to FIG. 8.

(47) When input data is input to the channel decoding device 300, the input data is transferred to the trivial decoding unit 301, and an attempt to restore lost data is made (S301 to S303). In the linear code, it is previously known that a product of received data and a parity check matrix H of each block is 0 (zero). For this reason, the trivial decoding unit 301 uniquely restores one lost data having no relation with other lost data as the restored lost data.

(48) If all lost data has been restored at the first trivial decoding unit 301 (yes in S304), the decoding process ends, and data is output. However, when there is still lost data which has not been able to be restored by the first trivial decoding unit 301 (no in S304), similarly to the first and second embodiments, the maximum likelihood decoding is attempted by applying the Gauss elimination method (S306), but the restored data calculated by the trivial decoding unit 301 is held in the decoding partial caching unit 302 before the maximum likelihood decoding is attempted. This is because the computational complexity is expected to be reduced by using the held part when lost data is reconstructed by the subsequent Gauss elimination method.

(49) Similarly to the second embodiment, the degree sorting unit 303 changes Formula (8) in which the identity matrix is prepared to the following relational expression by rearranging the matrix H.sub. on the left side in the ascending order of degrees (S309).
[Math 10]
[H.sub.]x.sub..sup.t=[I.sub.m,m][H.sub.]x.sub..sup.t(10)

(50) Here, H.sub. is a matrix that is sorted in the ascending order of degrees. If degree sorting is limited to only column sorting, it is unnecessary to change the right side of the above Formula, and even when rows are changed, it is possible to cope with it by switching rows of the identity matrix on the right side and changing it to I. Here, an example in which only highly effective columns are sorted is described, but in the case of a class called an LDPC-Staircase code, discharging of a subsequent process can be performed at a high speed by preferentially sorting an staircase matrix. Generally, it is desirable to avoid fill-in occurring during the discharging process to the utmost since it is associated with an increase in the computational complexity, but rearranging in which the fill-in is minimum is known to be an NP-complete problem. Here, the fill-in refers to what a value is input to a location that was originally an element of 0 in the discharging process. The method of sorting in the ascending order of degrees can easily reduce the occurrence of the fill-in, and thus a high-speed operation can be performed. As the staircase matrix is preferentially sorted, the occurrence of the fill-in can be further suppressed, leading to the high-speed operation. Moreover, as another speed increasing method, a technique such as the triangular matrix conversion is widely known, and this technique may be applied.

(51) Then, the pivot selecting/discharging unit 304 performs the forward elimination on the rearranged matrix (S310). Since the discharging unit performs rearranging in which the occurrence of the fill-in is suppressed, the fast discharging can be performed.

(52) When the triangular matrix conversion is performed, a form similar to Formula (9) can be obtained, and as the subsequent process (S306) of the Gauss elimination method decoding unit 305, the same process as in the second embodiment is performed.

(53) As described above, in the channel decoding method according to the present embodiment, the trivial decoding unit 301 executes steps S301 to S305, the degree sorting unit 303 executes step S309, the pivot selecting/discharging unit 304 executes step S310, and the Gauss elimination method decoding unit 305 executes step S306.

Fourth Embodiment

(54) FIG. 9 illustrates a basic configuration diagram of a channel decoding system that implements the maximum likelihood decoding using the trivial decoding method and the Gauss elimination method repeatedly. 401 indicates a trivial decoding unit that restores lost data by a small number operations, 402 indicates a decoding partial caching unit that holds partial data of a restoration operation process as a cache when lost data is reconstructed through the trivial decoding unit 401 and a Gauss elimination method decoding unit 407, 403 indicates a Gauss column selecting unit that selects a parity check matrix corresponding to lost data that is restored by the Gauss elimination method as a Gauss column, 404 indicates a trivial column selecting unit that selects a parity check matrix corresponding to lost data that is restored by the trivial decoding method as a trivial column, 405 indicates a degree sorting unit that sorts the sparse graphs according to a degree, and 406 indicates a pivot selecting/discharging unit that selects a pivot, converts the trivial column into an identity matrix through the forward elimination, and converts the Gauss column into a triangular matrix, and 407 indicates a Gauss elimination method decoding unit that actually restores lost data. The respective components will be described below.

(55) The present system is a channel decoding system that efficiently performs the maximum likelihood decoding on loss occurring on the erasure channel by a small number of processes. For the sake of simplicity, similarly to the first, second, and third embodiments, as a preferable example in which the present system functions effectively, an example in which IP packet transmission on the Internet serving as a representative channel of an erasure channel is assumed, and an LDPC code configured by a sparse graph is assumed as a code will be described below with reference to FIG. 10.

(56) When input data is input to the channel decoding device 400, the input data is transferred to the trivial decoding unit 401, and an attempt to restore lost data is made (S401 to S403). In the linear code, it is previously known that a product of received data and a parity check matrix H of each block is 0 (zero). For this reason, the trivial decoding unit 401 uniquely restores one lost data having no relation with other lost data as the restored lost data.

(57) If all lost data has been restored at the first trivial decoding unit (yes in S404), the decoding process ends, and data is output. However, when there is still lost data which has not been able to be restored by the first trivial decoding unit (no in S404), similarly to the first, second, and third embodiments, the maximum likelihood decoding is attempted by applying the Gauss elimination method (S405 to S413), but the restored data calculated by the trivial decoding unit 401 is held in the decoding partial caching unit 402 before the maximum likelihood decoding is attempted. This is because the computational complexity is expected to be reduced by using the held part when lost data is reconstructed by the subsequent Gauss elimination method.

(58) Similarly to the second embodiment, in Formula (8) in which the identity matrix is prepared, the Gauss column selecting unit 403 selects one column in which lost data is highly likely to be subsequently restored by the Gauss elimination method from H.sub. (S411). The decoding computational complexity is known to be changed by this selection algorithm, but for sakes of simplicity, an operation of selecting one column (a column in which the sum of all elements in a column is large) in which the degree of H.sub. of Formula (8) is heavy is performed. After one column is designated as the Gauss column, if lost data corresponding to the Gauss column is assumed to have been restored by the trivial column selecting unit 404, a column corresponding to lost data that can be necessarily restored by the trivial decoding method is selected as the trivial column (S412). The lost data that can be necessarily restored by the trivial decoding method is lost data that can be uniquely reconstructed from anticipated restored data of a candidate restored by the Gauss elimination method and received data and is independent data form other lost data. The operations of 403 and 404 are repeated until all columns of H.sub. belong to either of the Gauss column or the trivial column (S413). For example, this determination is performed by the Gauss column selecting unit 403.

(59) When all columns belong to either of the Gauss column or the trivial column, the process proceeds to S409. In S409, the degree sorting unit 405 rearranges the trivial column and the Gauss column (sorting). For the sorting, similarly to the third embodiment, the rearranging technique such as the triangular matrix conversion may be used, but in the present embodiment, for the sake of simplicity, the trivial column and the Gauss column are assumed to be rearranged in the ascending order of degrees (the order in which the sum of all elements in a column is small). The pivot selecting/discharging unit 406 performs identity matrix conversion on the trivial column by the forward elimination, and performs the triangular matrix conversion on the Gauss column. The identity matrix conversion and triangular matrix conversion correspond to steps of the Gauss elimination method. In this process, the pivot is selected in the ascending order of degrees, and similarly to the third embodiment, in the case of the LDPC-Stair code, and it is selected from an upper matrix of the echelon matrix, and thus the high-speed operation can be performed.

(60) When the identity matrix conversion and the triangular matrix conversion are performed, similarly to Formula (9), the form of the upper triangular matrix can be obtained, and thus as the subsequent process of the Gauss elimination method decoding unit 407, the same process as in the second and third embodiments is performed.

(61) As described above, in the channel decoding method according to the present embodiment, the trivial decoding unit 401 executes steps S401 to S405, the Gauss column selecting unit 403 executes steps S411 and S413, the trivial column selecting unit 404 executes step S412, the degree sorting unit 405 executes step S409, the pivot selecting/discharging unit 406 executes step S410, and the Gauss elimination method decoding unit 407 executes step S406.

(62) As described above, in the present disclosure, the fast maximum likelihood decoding can be implemented at low computational complexity by decreasing lost data restored by the Gauss elimination method whenever possible and increasing lost data restored by the trivial decoding method whenever possible in the maximum likelihood decoding of the sparse graph code.

(63) Further, the device of the present disclosure may be implemented by a computer and a program, and the program may be recorded in a recording medium or provided via a network.

INDUSTRIAL APPLICABILITY

(64) The present disclosure can be applied to information communication industry.

REFERENCE SIGNS LIST

(65) 10: channel encoding device 11: channel encoding unit 20: packet-based transmitting device 21: packet transmitting unit 30: packet-based receiving device 31: received data analyzing unit 40, 100, 200, 300, 400: channel decoding device 41: channel decoding unit 42: maximum likelihood decoding unit 101, 201, 301, 401: trivial decoding unit 102, 203, 407: Gauss elimination method matrix processing unit 103, 204, 305: Gauss elimination method decoding unit 202, 302, 402: decoding partial caching unit 303, 405: degree sorting unit 304, 406: pivot selecting/discharging unit 403: Gauss column selecting unit 404: trivial column selecting unit