Decoding device and decoding method

According to an embodiment, a decoding device includes a variable node processor, a check node processor, a first forwarder, and a second forwarder. The variable node processor is configured to perform variable node processing on variable nodes defined by a code and output first messages. The check node processor is configured to perform check node processing on check nodes defined by the code based on the first messages and output second messages. The first forwarder is configured to forward one or more first messages remaining after excluding messages to be forwarded to one or more check nodes corresponding to one or more of the second messages having been stored in ae storage, to the check nodes. The second forwarder is configured to forward the second messages to the variable nodes and forward the one or more of the second messages to the storage.

CROSS-REFERENCE TO RELATED APPLICATION

This application is based upon and claims the benefit of priority from Japanese Patent Application No. 2015-018840, filed on Feb. 2, 2015; the entire contents of which are incorporated herein by reference.

FIELD

Embodiments described herein relate generally to a decoding device and a decoding method.

BACKGROUND

An LDPC code (LDPC stands for Low-Density Parity-Check) is known as an encoding method that has a strong error correction/encoding capacity and that is used in communication systems and memory devices. An LDPC code uses a parity check matrix and repeatedly performs message value calculation called row processing and column processing; and performs decoding by obtaining the posterior probability of received-word data. From among the existing types of error correction codes, an LDPC code has the error correction capacity close to the theoretical limit. For that reason, the LDPC code is widely used in communication systems and storage devices.

Meanwhile, regarding the flash memory that, in recent years, has become mainstream as far as nonvolatile semiconductor memory devices are concerned, miniaturization of memory cells and multi-bit per cell architecture have escalated the errors occurring during reading. For that reason, the error correction capacity of the conventional BCH code (BCH stands for Bose, Chandhuri, Hocquenghem) has become insufficient. Thus, in recent years, a lot of attention is being focused on the LDPC codes having a higher error correction capacity. Besides, in order to retain the intergenerational compatibility among the error correction methods, there has been a demand for a technology providing an on-chip decoding circuit for decoding the LDPC codes. As a result of providing an on-chip decoding technology, the LDPC code decoding operation can be performed using a circuit arranged on the chip on which the semiconductor memory device is formed. As a result, the apparent error occurrence rate of the semiconductor memory device can be held down to a certain level or lower.

Meanwhile, since an LDPC code performs probability-based error correction, it becomes necessary to perform complex real number calculation. Particularly, in the check node processing performed during the calculations for decoding an LDPC code, it is necessary to perform product-sum operations of probability values, thereby requiring a large amount of calculation resources. Hence, in order to implement the decoding operation for an LDPC code using hardware, a large-scale digital semiconductor circuit is required. That makes on-chip implementation a difficult task.

In that regard, in order to downscale the semiconductor circuit that performs decoding of an LDPC code, a method has been proposed in which the real numbers are expressed as electrical current and the real number calculation is performed using analog circuitry. However, in the case of expressing data values as electrical current, electrical current must continuously flow during the data processing. That leads to consumption of an enormous amount of electrical power.

In this way, in order to achieve a sufficient error correction capacity in an LDPC code using the conventional technology, it is necessary to perform the decoding operation using real number calculation. Unfortunately, this enlarges implementation of an error correction device using a semiconductor integrated circuit.

DETAILED DESCRIPTION

According to an embodiment, a decoding device includes a variable node processor, a check node processor, a storage, a first forwarder, and a second forwarder. The variable node processor is configured to perform variable node processing on variable nodes defined by a code and output first messages. The check node processor is configured to perform check node processing on check nodes defined by the code based on the first messages and output second messages. The storage is configured to store one or more of the second messages. The first forwarder is configured to forward one or more first messages remaining after excluding messages to be forwarded to one or more check nodes corresponding to the one or more of the second messages having been stored in the storage, to the check nodes. The second forwarder is configured to forward the second messages to the variable nodes and forward the one or more of the second messages to the storage.

Configurations Shared Between Embodiments

A decoding device according to embodiments will now be explained. The decoding device according to the embodiments decodes LDPC codes.FIG. 1is a schematic of an exemplary configuration of a memory system including the decoding device according to the embodiments.

With reference toFIG. 1, a memory system1includes a memory unit2, an encoder3, and a decoder4. Firstly, input data5is input to the encoder3. Then, the encoder3encodes the input data5into an LDPC code, and sends the LDPC code to the memory unit2that includes, for example, a controller and a memory medium. Thus, the LDPC code that is sent to the memory unit2is written in the memory medium by the controller. In a first embodiment, it is assumed that a flash memory is used as the memory medium.

The memory unit2, the encoder3, and the decoder4may be integrated into one semiconductor chip, but without limitation. The memory unit2, the encoder3, and the decoder4may also be implemented as separate pieces of hardware. Alternatively, the encoder3and the decoder4may be configured as a computer program operating on a central processing unit (CPU).

Meanwhile, for example, when the memory unit2receives a read request from outside, the controller reads the LDPC code from the memory medium and sends it to the decoder4. Then, the decoder4decodes the LDPC code; restores the original input data5; and outputs the restored input data5as output data6from the memory system1.

When a flash memory is used as the memory medium, reading of information is done depending on whether the threshold voltage is high or low.

Given below is the explanation about LDPC codes. An LDPC code is characterized by a low-density matrix called a check matrix in which majority of the components are equal to 0 and only a small number of components are equal to 1. Depending on the code length, a large check matrix is required. However, for the sake of illustration, the following explanation is given about an 8×4 check matrix. An example of a check matrix H is given below in Equation (1).

In the check matrix H, the count of 1 present in each row and each column is called weight, and the check matrix is created in such a way that the weights in all columns and all rows are greater than zero. When the column weight and the row weight are constant values, the check matrix is called a regular matrix. In the check matrix H given in Equation (1), all column weights are equal to four and all row weights are equal to two. Hence, the check matrix H is a regular matrix.

In the LDPC method, a data string x that is to be sent through a communication path or that is to be stored in a memory is converted into a data string c that satisfies HcT=0. This data string c is called a code. Thus, in the LDPC method, the data used in information processing is not the original data string x but is the code c obtained by conversion. The encoder3performs a conversion operation with respect to the data string containing the input data5. The memory unit2writes the code c, which is obtained by conversion of the input data5, in the flash memory.

Generally, the code c represents a data string having a greater data length than the data string x and contains, in addition to the information included in the data string x, information required in performing error correction. Meanwhile, encoding itself represents mapping with one-to-one correspondence. Thus, if the data string x is provided, the code c gets uniquely determined. Conversely, if the code c is provided, the original data string x gets uniquely determined. Moreover, (the length of the data string x)/(the length of the code c) is called a code rate. Herein, it can be said that, higher the code rate, the higher is the efficiency of the error correction.

The check matrix H can be expressed using a Tanner graph illustrated inFIG. 2. In the Tanner graph, nodes {c0, c1, . . . c7} are arranged below nodes {f0, f1, f2, f3}. Then, regarding a component hijof the check matrix H, only when the component hij=1 holds true, the nodes are connected by straight lines. In the Tanner graph, nodes {ci} are called variable nodes, and nodes {fj} are called check nodes. Each of the variable nodes cicorresponds to a row of the check matrix H; and the row numbers of the rows having the value “1” matches with the numbers assigned to the check nodes fjthat are connected to the concerned variable node ci. On the other hand, each of the check nodes fjcorresponds to a column of the check matrix H; and the column numbers of the columns having the value “1” matches with the numbers assigned to the variable nodes cithat are connected to the concerned check node fj.

Equation (2) presents an example of variable nodes {ci} and check nodes {fj} when the check matrix H provided in Equation (1) is used.

A basic operation of LDPC code decoding will now be explained. It is assumed herein that the decoding operation explained below is performed by, for example, the decoder4. In such a configuration, the decoder4reads a code stored in the memory unit2, and decodes the code to recover the original data. Generally known as an error correction method used for LDPC codes is a method using belief propagation (BP). The BP will now be explained.

To begin with, for a string “y”={yi} of some physical quantities, each of the variable nodes cireceives a probability Q0iat which the digital value corresponding to each of the values yiis “0”. Each of the variable nodes cithen sends the probabilities Q0ito the check nodes {fj, fh, . . . } to which that variable node ciis connected, as messages {qij, qih, . . . } (see (a) inFIG. 3).

An example of the string “y” of physical quantities is a bit string read from the memory unit2. When a flash memory is used as a memory medium, the memory unit2reads the threshold voltages of the time when the bit string is read from the memory medium, and converts the threshold voltages into probability values by calculating probabilities indicating likelihood for respective bits of the bit string. Each of the variable nodes cithen receives the probability values of the respective bits as probabilities Q0i.

The check node fjthen calculates, taking the parity condition into account, probabilities {rji, rjk, . . . } at which the respective variable nodes {ci, ck. . . } is a digital data value of “1”, based on messages q={qij, qkj, . . . } received from the respective variable nodes {ci, ck, . . . } connected to that check node fj. The check node fjthen sends back the probabilities {rji, rjk, . . . } to the corresponding variable nodes {ci, ck, . . . } as messages rij(see (b) inFIG. 3).

When a check node fjcalculates a message rjito be sent back to a variable node ci, the check node fjdoes not include the message qijreceived from that variable node ci. In other words, the variable node cireceives the messages rjicorresponding to the variable nodes other than that corresponding to that variable node ci. More particularly, the check node fjperforms the check node processing following Equation (3) below to calculate the messages rji. In Equation (3), the value A(j) represents a set of subscripts {i, k, . . . } given to the variable nodes that are connected to that check node fj.

A variable node ciperforms variable node processing based on the messages (probabilities) {rji, rki, . . . } received from the respective check nodes {fj, fk, . . . } that are connected to that variable node ci.

In other words, the variable node cicalculates a probability Q′iat which the received data is originally “0”, using the messages {rji, rki, . . . } and the probability Q0iretained by that variable node ci. As a result of calculation, if the probability Q′iis equal to or greater than ½, the variable node cipresumes that the value of the received data is “1”. If the probability Q′iis smaller than ½, then the variable node cipresumes that the value of the received data is “0”.

During the error correction according to the LDPC method, the parity check is performed using the presumed value. More particularly, with respect to a presumed-value string ctemp={c0temp, c1temp, . . . }, it is determined whether HctempT=0 holds true. If HctempT=0 holds true, calculations are ended under the estimation that the presumed-value string is a digital data string in which the presumed value ctempwas stored. However, if HctempT=0 does not hold true, then the variable node cirecalculates the message q={qij, qkj, . . . } and sends the calculation result to the check nodes {fj, fk, . . . } (see (b) inFIG. 3).

The specific calculation performed by the variable node ciis as Equation (4) below.

Where the value B(i) in Equation (4) represents a set of subscripts {j, k, . . . } given to the check nodes f connected to the variable node ci, and the value K is a normalization constant determined to satisfy Equation (5) below.

Herein, the message qijthat is sent from the variable node cito the check node fjrepresents “the probability at which the value of digital data of the variable node ciis equal to 1” calculated based on probability Q01 and probability {rki, rli, . . . }. That message is not included in the message rjireceived from the check node fj. That is, as a result of receiving the message qij, the check node fjreceives message on the check nodes except for itself.

Upon receiving the message q, the check node calculates the message (probability) r based on the received message q, and returns a variable node. This abovementioned algorithm is repeatedly implemented until the parity condition is satisfied. That is, the presumed-value string ctempis updated using the calculated message r; and, until HctempT=0 holds true with respect to the updated presumed-value string ctemp, the algorithm is repeatedly implemented.

In the embodiments, the process from when each of the variable nodes calculates and transmits the messages q to the corresponding check nodes, and to when the variable node receives the messages r from the corresponding check nodes is used as a unit of the error correction, and this unit is herein referred to as an “iteration”.

FIG. 4is a schematic representation of LDPC code decoding using the BP explained above. Illustrated inFIG. 4is an example in which a matrix of four rows and eight columns presented as an example in Equation (1) is used as the check matrix H. In other words, in the example illustrated inFIG. 4, variable nodes ciinclude eight variable nodes {c0, c1, c2, c3, c4, c5, c6, c7} and the check nodes fjincludes four check nodes {f0, f1, f2, f3}.

At Step S1inFIG. 4, the variable nodes cireceive the probabilities Q0icorresponding to respective eight bits read from the memory unit2, for example. The variable nodes cithen updates the presumed value string ctempbased on the received probabilities Q0i, and sends the probabilities Q0ito the check nodes fjas the messages qij, based on the check matrix H (Step S2).

The check nodes fjthen perform the check node processing, following Equation (3), based on the received messages qij(Step S3), and send back the results to the corresponding variable nodes ci, as the messages rjibased on the check matrix H (Step S4). The messages rjiare then received by the corresponding variable nodes ci(Step S5).

Each of the variable nodes cithen performs the variable node processing based on the received messages rji. The variable node cirecalculates the messages qijif the variable node cidetermines that HcT=0 is not established with the presumed value string ctemp, as a result of the variable node processing.

The variable node cithen transmits the recalculated messages qijto the corresponding check nodes fj(Step S6). Each of the check nodes fjperforms the check node processing based on the received messages qij(Step S7), and transmits the resultant messages rjito the corresponding variable nodes ci(Step S8). The messages rjiare then received by the variable nodes ci(Step S9). The variable nodes cithen update the presumed value string ctempbased on the received messages rji.

The process from when the variable nodes cicalculates the messages qijat Step S5to when the check node fjreceives the messages rjiat Step S9is repeated, as a unit of repetitive process until the parity condition is satisfied. This unit of repetitive process corresponds to the iteration mentioned above.

The process from when the presumed value string ctempis updated based on the received probabilities Q0iand the probabilities Q0iare transmitted to the corresponding check nodes fjto when the messages rjiare received at Step S5is also considered as equivalent to the unit of the repetitive process.

Details of Error Correction According to Embodiments

In the error correction using the BP, probabilities Q′ for estimating the original data in the respective variable nodes are calculated by exchanging the probability values between the variable nodes and the check nodes. Information eventually required in this series of processes is information of whether the probability Q′ is higher than ½, and details of the specific values are less important. Therefore, the probability calculations in the variable node processing and the check node processing do not need to be very exact. A message received from one of the check nodes, in particular, has a limited impact on the final result because the probabilities are calculated in the variable node processing by multiplying the messages received from the check nodes.

Therefore, while the messages transmitted from the check nodes to the variable nodes are updated once in every iteration, the final results are not affected very much even if one or more of the check nodes are kept unupdated.

In the embodiments, considering this point, one or more of the check nodes {f0, f1, . . . } are temporarily kept unupdated so that the check node processing is temporarily kept resting in each iteration. The check nodes to be temporarily kept unupdated are changed between successive iterations. In replacement of the message to be transmitted from the temporarily resting check nodes to the variable nodes, the message calculated by that check node and stored in a memory in the previous iteration is transmitted, for example.

In the manner described above, by keeping one or more of the check nodes {f0, f1, . . . } temporarily unupdated in each iteration, resources required for the check node processing can be reduced. Furthermore, the check node processing can be executed at a higher speed depending on the configuration required for the check node processing.

FIG. 5is a schematic representation of the steps in the LDPC code decoding using the BP according to the embodiments. In the example illustrated inFIG. 5, the matrix of four rows and eight columns, which is presented as an example in Equation (1), is used as the check matrix H, and the variable nodes ciincludes the eight variable nodes {c0, c1, c2, c3, c4, c5, c6, c7}, and the check nodes fjinclude four check node {f0, f1, f2, f3}, in the same manner as in the example illustrated inFIG. 4. InFIG. 5, the check nodes fjtemporarily kept unupdated are shown as hatched, and are indicated as “resting”.

The variable nodes and the check nodes are implemented using memory medium such as memories or registers.

In the kthiteration, the check node f0is kept unupdated. In other words, in the kthiteration, the check node f0does not receive the messages qijfrom the variable nodes ci, and does not update the values that are the probabilities r0i. As the message r0isent back from the check node f0to the variable nodes ci, the message r0iresulting from the (k−1)thiteration and stored separately is used instead.

In the kthiteration, the other check nodes f1to f3update their values as usual, and sends back their messages to the variable nodes ci. The message r1ifrom the check node f1in which the value is not updated in the subsequent (k+1)thiteration is stored separately in the memory.

In the same manner, the check nodes f1, f2, and f3are kept temporarily unupdated in the (k+1)th, the (k+2)th, and the (k+3)thiterations, respectively. Therefore in the (k+1)th, the (k+2)th, and the (k+3)thiterations, the check nodes f1, f2, and f3neither receive the messages qijfrom the variable nodes ci, nor their values are updated. The check nodes f1, f2, and f3use the values stored in the previous iterations as the messages sent back to the variable nodes ci, and the message from the check node that is to be kept temporarily unupdated in the subsequent iteration is also stored in the memory.

In the manner described above, by keeping one or more of the check nodes f0to f3temporarily unupdated in each iteration, the check node processing can be executed in a smaller number of check nodes, being smaller than the number of check nodes defined by the check matrix H. In this manner, the amount of computations (the degree of concurrency) required in check node processing can be reduced, so that the circuit can be downscaled.

In the example inFIG. 5, the (k−1)thiteration is the first iteration in the repetitive process of iterations. The process in the first iteration is substantially the same as the process from Step S1to Step S5inFIG. 4. In other words, in the (k−1)thiteration, the variable nodes cireceive probabilities Q0icorresponding to the respective bits read from the memory unit2, for example, update the presumed value string ctemp, and transmit the messages qijto the check nodes f0to f3.

At this time, if the messages qijare transmitted to all of the check nodes f0to f3, to cause the check nodes f0to f3to perform the check node processing, the reduction effect of check node processing might not be achieved sufficiently.

To address this issue, therefore, in the first iteration, the messages qijare not transmitted to a check node (for example, the check node f3) that is not to be kept temporarily unupdated in the subsequent iteration (the kthiteration in the example illustrated inFIG. 5), so that the check node is temporarily kept unupdated. As the messages rijto be transmitted from this check node to the variable nodes ci, a fixed value stored in the memory in advance, for example, is used. An example of the fixed value is ½. The fixed value may be any value that can be used as a probability value, without limitation to ½.

Explained now with reference toFIG. 6is some advantageous effects achieved by keeping one or more of the check nodes temporarily unupdated in the embodiments.FIG. 6illustrates examples of error bit counts achieved by changing the ratio of the check nodes temporarily kept unupdated in every iteration, except the first iteration, in the LDPC code error correction. In the example illustrated inFIG. 6, the error correction is applied to an LDPC code with a code length of 1 kilobit. The check node temporarily kept unupdated transmits the value stored from the previous iteration.

InFIG. 6, the circles represent the results when the ratio of the check nodes temporarily kept unupdated is zero, the asterisks, the crosses, the triangles, and the rhomboids represent the results when the ratio of the check nodes temporarily kept unupdated are 1/10, 2/10, 3/10, 4/10, and 5/10, respectively. InFIG. 6, the vertical axis represents the average error bit count resulting from error corrections, and the horizontal axis represents the iteration count.

When the check nodes temporarily kept unupdated occupies a ratio of equal to or lower than 3/10, the average error bit count declines as the iteration is repeated. By contrast, when the check nodes temporarily kept unupdated occupies a ratio of equal to or higher than 4/10, the average error bit count does not decline as the iteration is repeated, and the error floor appears.

It is preferable to change the check node temporarily kept unupdated in each of the iterations. It is also preferable to keep each of the check nodes temporarily unupdated at a fair ratio. If each of the check nodes is kept temporarily unupdated at an unfair ratio, some of the variable nodes may fall incapable of correcting errors appropriately.

Used in the error correction illustrated inFIG. 6is a check matrix in which every variable node is connected to three check nodes. As explained with reference toFIG. 3and Equation (3), when a variable node transmits messages to a check node, the variable node transmits messages resultant of the messages sent back from the check nodes except for that check node. Therefore, in the example illustrated inFIG. 6, the messages to be transmitted to a check node are derived from the information from the other two check nodes.

When the number of check nodes kept temporarily unupdated occupies one third of the entire check nodes, one of the two check node remain temporarily unupdated. When the number of check nodes kept temporarily unupdated occupies more than one third of the entire check nodes, both of these two check nodes may stay temporarily unupdated. In such a case, because the messages returned from the variable nodes to the check nodes remain unupdated as well, the error correction cannot be performed appropriately. This is the reason why the error floor appears when the ratio of the check nodes temporarily kept resting is 4/10 or 5/10 inFIG. 6.

Let us now discuss the ratio of check nodes that are kept temporarily unupdated with respect to the entire check nodes in each iteration. It is assumed therein that average number of check nodes connected to each of the variable nodes is N (where N>2). As described earlier, when the ratio between the check nodes temporarily kept unupdated and the entire check nodes with respect to a variable node exceeds (N−2)/N, the messages to be returned from the variable node to the check nodes may not be updated, so that the error correction may not be performed appropriately. Therefore, it is preferable for the ratio between the check nodes kept temporarily unupdated and the entire check nodes with respect to a variable node to be equal to or lower than (N−2)/N.

First Embodiment

FIG. 7illustrates an exemplary configuration of a decoding device according to the first embodiment. InFIG. 7, the decoder4includes a variable node processor40, a first forwarder41, a check node processor42, a second forwarder43, a distribution controller44, and a message storage45. The memory unit2includes a memory20, a threshold reader21, a threshold-to-probability converter22, and an initial probability storage23.

The decoder4is implemented as hardware, and the units included in the decoder4are integrated into one semiconductor chip, for example, but without limitation. The units included in the decoder4may be partly or entirely implemented as separate respective pieces of hardware. The message storage45includes a rewritable non-volatile memory and a structure for reading and writing data from and to the non-volatile memory, for example. The units included in the memory unit2are also integrated into one semiconductor chip, for example. The units included in the memory unit2may be partly or entirely implemented as separate respective pieces of hardware.

The decoder4and the memory unit2operate under the control of a higher-level structure above the memory system1in which the decoder4and the memory unit2are included, for example, but without limitation. Alternatively, the memory system1may be provided with a controller, and the controller may control the operations of the decoder4and the memory unit2. In the explanation hereunder, it is assumed that the number of check nodes determined by the check matrix H is six, for the purpose of explanation.

In the memory unit2, the memory20is a memory medium, and an example of the memory20is a flash memory. The threshold reader21reads the threshold voltage when a bit string is read from the memory20. The threshold-to-probability converter22converts the threshold voltage into a probability value by calculating a probability indicating likelihood for each bit of the bit string, based on the threshold voltage acquired by the threshold reader21. The probability values of the respective bits acquired by the threshold-to-probability converter22are stored in the initial probability storage23.

In the decoder4, the variable node processor40performs the variable node processing and calculates the probabilities Q0ibased on the probability values stored in the initial probability storage23or the messages (probability values) rjireceived from the second forwarder43described later. The variable node processor40transmits the calculated probabilities Q0ito the first forwarder41as the messages qij.

Upon receiving the messages qijfrom the variable node processor40, the first forwarder41notifies the distribution controller44of the reception. The first forwarder41also selects the messages to be applied with the check node processing by the check node processor42from the messages qij, and forwards the selected messages to the check node processor42, under the control of the distribution controller44.

The check node processor42performs the check node processing to the check nodes in a number less than a predefined number of check nodes, being predefined by the check matrix H, and calculates the probabilities rij. For example, the check node processor42performs the check node processing to four out of the six check nodes, the six being the number of check nodes defined by the check matrix H. The check node processor42then updates the check nodes with respective probabilities rjicalculated in the check node processing, and transmits the probabilities rjito the second forwarder43as the messages rji.

The second forwarder43stores designated one or more messages from the messages rjireceived from the check node processor42in the message storage45, under the control of the distribution controller44. In this example, because the check node processing is performed to the four check nodes out of six, which is the number predefined by the check matrix H, the second forwarder43stores the messages corresponding to at least two check nodes, representing the difference between four and six, in the message storage45.

The second forwarder43transmits the messages rjireceived from the check node processor42and the messages resulting from the previous iteration and stored in the message storage45to the variable node processor40so that such messages are supplied to the appropriate variable nodes, under the control of the distribution controller44. The variable node processor40calculates the probabilities Q0i′ for the respective variable nodes, and acquires a presumed value string ctemp.

A determiner46determines whether Hctemp=0 is established with the presumed value string ctempacquired by the variable node processor40. If the determiner46determines that Hctemp=0 is established, the determiner46converts the probabilities Q0i, which are calculated for the respective variable nodes, into respective bits values, and outputs the bit values to a higher-level structure above the memory system1, for example. If the determiner46determines that Hctemp=0 is not established, the determiner46notifies the higher-level structure of Hctemp=0 not being established.

A process of the kthiteration performed in the distribution controller44will now be explained more in detail. Upon being notified that the messages qijare received from the first forwarder41, the distribution controller44determines the check nodes to which the received message qijare to be forwarded, and forwards the messages qijto the determined check nodes in the check node processor42.

At this time, the distribution controller44controls the first forwarder41so as not to forward messages qiAto be addressed to a check node fAbelonging to a subset A, including one or more of the check nodes fj, to the check node processor42. In other words, the distribution controller44forwards the messages resulting from excluding the message qiAto be sent to the check node fA, included in the subset A, from the messages qijto be sent to the entire check nodes fj(referred to as messages qi(j-A)) to the check node processor42. In this manner, the check node processing for the check node fAis temporarily kept resting, and the check node fAis left unupdated.

Under such control, the first forwarder41forwards the message qi(j-A)to the check node processor42.

The check node processor42performs the check node processing corresponding to the respective check nodes. Because the first forwarder41does not forward the message qiAto be sent to a check node fAbelonging to the subset A to the check node processor42, the check node processor42does not perform the process corresponding to the check node fAbelonging to the subset A. The check node processor42transmits messages r(j-A)igenerated in the check node processing to the second forwarder43. These messages r(j-A)iare messages generated by applying check node processing to the remaining check nodes after excluding the check node fAfrom the entire check nodes fj.

The distribution controller44then controls the second forwarder43to read a message rAi′ from the message storage45. The message rAi′ is a message resulting from the subset A and is stored in the previous iteration (in this example, in the (k−1)thiteration). The messages rAi′ read from the message storage45are used as replacement of the messages rAiexcluded by the check node processor42and left out without being forwarded in the kthiteration.

Before executing the process of the iteration for the first time (first iteration), messages serving as initial values are stored in the message storage45. These messages serving as the initial values may be any value that can be used as probability values, without limitation. For example, ½ may be stored as an initial value in the message storage45.

The distribution controller44controls to cause the second forwarder43to forward the messages rAi′ read from the message storage45, and the messages r(j-A)ireceived from the check node processor42to the variable node processor40. At this time, the distribution controller44determines the variable nodes to which these messages rAi′ and messages r(j-a)iare to be transmitted, and controls the second forwarder43to forward the messages to the determined variable nodes in the variable node processor40.

The distribution controller44also controls to cause the second forwarder43to store the messages (referred to as messages rBi) received from a check node fBbelonging to a subset B in the message storage45. The check node fBis a check node for which the check node processing is to be temporarily kept resting in the subsequent (k+1)thiteration, among the entire check nodes fj.

As an example, the distribution controller44may select the check node for which the check node processing is to be temporarily kept resting in the kthiteration, the (k+1)thiteration, . . . , and so on, sequentially from the check nodes f0to f3, e.g., the check node f0, the check node f1, . . . , as illustrated inFIG. 5explained above, but without limitation. Alternatively, the distribution controller44may randomly select the check node for which the check node processing is to be temporarily kept resting from the check nodes f0to f3, using a random number, for example. The distribution controller44may also select the check node for which the check node processing is to be temporarily kept resting based on a table prepared in advance.

Under such control, the second forwarder43forwards the messages rAi′ and messages r(j-A)ito the variable nodes determined by the variable node processor40, and stores the messages rBiin the message storage45.

Using the messages rAi′ and messages r(j-A)ireceived from the second forwarder43, the variable node processor40calculates probabilities Q0i′ at which the bits in the respective variable nodes are 0 (or 1). The variable node processor40then transmits the calculated probabilities Q0i′ to the determiner46. The process up to when the variable node processor40transmits the probabilities Q0i′ to the determiner46is the process within the scope of the kthiteration.

The determiner46then determines whether the calculations have been converged, based on the probabilities Q0i′. In other words, the determiner46determines, for the presumed value string ctemp, whether the values in HctempThave converged, based on the probabilities Q0i′. If the determiner46determines that the calculations have been converged, the determiner46outputs the probabilities Q0i′, or bit values resultant of converting the probabilities Q0i′ to the higher-level structure.

If the determiner46determines that the calculations have not been converged yet, the determiner46transmits the notification to the higher-level structure, for example. In this case, the process of the following (k+1)thiteration is started under the control of the higher-level structure.

In the (k+1)thiteration, when the first forwarder41receives the message qijfrom the variable node processor40, the distribution controller44determines the check nodes to which the received messages qijare to be forwarded. The distribution controller44then controls to cause the first forwarder41to forward the messages (referred to as messages qi(j-b)) excluding the messages qiBthat are to be forwarded to the check node fBto the appropriate check nodes in the check node processor42. The check node fBbelongs to the subset B that includes some of the entire check nodes fj, and is different from the subset A.

As described above, the decoder4according to the first embodiment excludes the message to be transmitted to one or more of the check nodes from the messages qijto be forwarded from the variable node processor40to the check node processor42, and sends the remaining messages to the check node processor42. The decoder4allows the variable node processor40to use a past message stored in the message storage45, in replacement of the excluded message. In this manner, with the decoder4according to the first embodiment, the amount of computations required in the check node processing can be reduced, and the circuit of the check node processor42can be downscaled compared with existing structures.

In the configuration described above, it is preferable to change the subset of the check nodes excluded from those to which the first forwarder41forwards the messages, in every iteration. Preferably, a subset of check nodes excluded from those to which the first forwarder41forwards the message does not share any common check nodes with other subsets in successive iterations.

This exclusion will now be explained more specifically with reference toFIGS. 8 and 9. InFIGS. 8 and 9, the check nodes are grouped into four subsets20210,20211,20212, and20213that include no common check nodes. InFIGS. 8 and 9, the subset of the check nodes for which the processing is temporarily kept resting is illustrated as hatched.

FIG. 8is a schematic illustrating the decoding process according to the first embodiment. In the first embodiment, the check node processing is temporarily kept resting for a different check node in every iteration, as mentioned earlier.

In the example illustrated inFIG. 8, in check node processing2021in the kthiteration, the check node processing in a subset20213is temporarily kept resting, so that the check nodes in the subset20213remain unupdated, but the check node processing is executed to the remaining subsets20210to20212, so that these check nodes are updated. The messages resulting from the check node processing performed to the subsets20210to20212including the updated check nodes are then forwarded to variable node processing2002for the following (k+1)thiteration.

In replacement of the messages for the subset20213in the kthiteration, the subset20213being a subset without its check nodes updated in the kthiteration, a message2011generated and stored as a result of the check node processing executed to the subset20213in the previous (k−1)thiteration is forwarded to the variable node processing2002.

The message2012generated as a result of the check node processing performed to the subset20213is also stored in the kthiteration, for the subset20213that will not be updated in the following (k+1)thiteration.

In the (k+1)thiteration, the variable node processing2002is executed using the messages from the subsets20210to20212generated as a result of the check node processing2021, and using the stored message2011. The messages generated as a result of the variable node processing2002are then forwarded to check node processing2022.

In the check node processing2022, the check node processing of the subset20212is temporarily kept resting, so that the check nodes included in the subset20212remain unupdated. The subset20212is different from the subset20213for which the check node processing is temporarily kept resting in the kthiteration. In the remaining subsets20210,20211, and20213, the check node processing is executed and the check nodes are updated. The messages generated as a result of performing the check node processing to the subset20210,20211, and20213including the updated check nodes are forwarded to variable node processing2003for the subsequent (k+2)thiteration.

In replacement of the message from the subset20212including the check nodes that are not updated in the (k+1)thiteration, the message2012generated and stored as a result of the check node processing in the previous kthiteration is forwarded to the variable node processing2003, as a message corresponding to the subset20212in the kthiteration. A message2013generated as a result of performing the check node processing to the subset20211is stored in the (k+1)thiteration, because the subset20211will not be updated in the following (k+2)thiteration.

In the manner described above, in the decoding process according to the first embodiment, when the messages are forwarded from variable node processing200x(where the subscript x is 1, 2, . . . ) to the check node processing202x, the messages are not forwarded to one or more of the check nodes. Therefore, those check nodes remain unupdated, and the messages stored in the previous iteration are forwarded to the variable node processing200xas a replacement.

FIG. 9illustrates an example in which the check node processing for the same check nodes is temporarily kept resting during the entire iterations. InFIG. 9, parts that are the same as those inFIG. 8are assigned with the same reference numerals, and detailed explanations thereof are omitted.

In the example illustrated inFIG. 9, the same check node processing of the subset20213is temporarily kept resting across the entire check node processing2021,2022, and2023in the respective iterations. In this case, for example, the subset20213cannot generate the message2012, which is stored as a replacement for the (k+1)thiteration (seeFIG. 8), in the kthiteration. Therefore, the variable node processing2002in the (k+1)thiteration keeps using the message2011that is the same as the message used in the kthiteration. In such a configuration, the calculation does not converge readily, so that error floor may occur.

Therefore, it is preferable for a set Ckof the check node unupdated in the kthiteration to be different from the set Ck+1of the check node unupdated in the (k+1)thiteration. If the set Ckand the set Ck+1share some check nodes, such common check nodes are updated less frequently, so that the calculation may not readily converge. Therefore, it is preferable that the set Ckand the set Ck+1do not share any check nodes.

Furthermore, to prevent the check nodes from being updated unfairly, it is preferable for the message from every check node to be replaced with a message stored in the past iteration at an equal frequency. For example, the check nodes for which the check node processing is temporarily kept resting may be distributed among the iterations so that the message from every check node is replaced at an equal frequency when an increase in the number of iterations reaches its limit. The check node for which the check node processing is to be temporarily kept resting may be selected sequentially in the respective successive iterations, or selected randomly using a random number, for example. The check node for which the check node processing is to be temporarily kept resting may also be selected based on a table prepared in advance.

Second Embodiment

A second embodiment will now be explained. The second embodiment describes an example in which a plurality of check node calculators, each of which performs the check node processing presented in Equation (3), are provided in parallel to the check node processor42according to the first embodiment explained with reference toFIG. 7.

FIG. 10illustrates an exemplary configuration of a decoding device according to the second embodiment. InFIG. 10, parts that are the same as those inFIG. 7are assigned with the same reference numerals, and detailed explanations thereof are omitted. In the explanation hereunder, it is assumed that the number of check nodes defined by the check matrix H is six, for the purpose of explanation.

In the example illustrated inFIG. 10, a check node processor42′ includes four check node calculators4201,4202,4203, and4204, which is in a number less than the number of check nodes defined by the check matrix H. One third of the entire check nodes, therefore, will be kept temporarily unupdated in each of the iterations. Each of the check node calculators4201,4202,4203, and4204performs the check node processing once or a plurality of number of times in every iteration.

When reception of the messages qijis notified from the first forwarder41, the distribution controller44determines the check nodes to which the received messages qijare to be forwarded. The distribution controller44then controls to cause the first forwarder41to forward the messages qijto the corresponding check node calculators4201,4202,4203, and4204based on the result of check node determination. At this time, among the messages qij, the distribution controller44controls to cause the first forwarder41not to forward messages qi2that are to be forwarded to the two remaining check nodes to the check node processor42′.

Under such control, the first forwarder41forwards the messages qi(j-2), which are resultant of excluding the messages q12from the messages qij, to the check node processor42′. The message qi(j-2)are then forwarded to the corresponding check node calculators4201,4202,4203, and4204.

The check node calculators4201,4202,4203, and4204in the check node processor42′ perform their check node processing based on the received messages qi(j-2). The check node processor42′ then forwards the messages r(j-2)icalculated by the check node calculators4201,4202,4203, and4204to the second forwarder43.

The distribution controller44controls to cause the second forwarder43to read messages rji′, acquired from the two check node and stored in the previous iteration, from the message storage45. The messages rji′ read from the message storage45are used as replacement for the messages excluded by the check node processor42as not to be forwarded in the this iteration.

The distribution controller44controls to cause the second forwarder43to forward the messages rji′ read from the message storage45and the messages r(j-2)ireceived from the check node processor42to the variable node processor40. At this time, the distribution controller44determines the variable nodes to which these message rAi′ and the messages r(j-A)iare to be forwarded, and controls to cause the second forwarder43to forward the messages to the determined variable nodes in the variable node processor40.

The distribution controller44also controls to cause the second forwarder43to store the message received from the two out of the entire check nodes fjin the message storage45. These two being the check nodes for which the check node processing is temporarily kept resting in the subsequent iteration.

Under such control, the second forwarder43forwards the message rji′ and the messages r(j-2)ito the determined variable nodes in the variable node processor40, and stores the message received from the two check nodes for which the check node processing is to be temporarily kept resting in the subsequent iteration in the message storage45.

FIG. 11illustrates an exemplary configuration of a decoding device using an existing technology. InFIG. 11, parts that are the same as those inFIGS. 7 and 10are assigned with the same reference numerals, and detailed explanations thereof are omitted herein. As illustrated inFIG. 11, in this decoder4″ using the existing technology, the check node processor101needs to have check node calculators1011,1012, . . . ,1016in the number corresponding to the number of check nodes predefined by the check matrix H (six, in this example).

The check node calculators4201to4204illustrated inFIG. 10and the check node calculators1011to1016illustrated inFIG. 11perform the operation of Equation (3) mentioned above. Equation (3) is an operation of calculating an infinite product, in which multiplications are performed in the number of times equal to the subtraction of one from the number of variable nodes, and a large circuit may be required depending on the number of variable nodes.

In the second embodiment, because the check node processing can be performed with check node calculators in the number smaller than the number of check nodes predefined by the check matrix H, the circuit for the check node processor can be downscaled, compared with the configuration using the existing technology. More specifically, assuming that the number of entire check nodes is C, and the average number of times the check node calculators perform the check node calculation based on Equation (3) in each iteration is L (where L<2×C), the configuration according to the second embodiment can reduce the number of check node calculators to a number smaller than C/L. Therefore, the configuration according to the second embodiment can downsize the circuit of the check node processor, compared with the existing configuration.

Third Embodiment

A third embodiment will now be explained. In the explanation above, the embodiments is used in the decoder4provided to the memory system1illustrated inFIG. 1, but the embodiments are not limited thereto. In other words, the embodiments may be used in a communication system transmitting and receiving data over a wired or wireless communication path.

FIG. 12illustrates an example of a configuration of a communication system that can be implemented in the third embodiment. With reference toFIG. 12, input data5′ is input to an encoder3′. Then, the encoder3′ encodes the input data5′ into an LDPC code. A modulator7modulates the LDPC code in the encoded form according to a method suitable for a communication path8, and sends the modulated code as a modulation signal to the communication path8. A demodulator9receives the modulation signal sent through the communication path8, demodulates the modulation signal as digital data, and sends the digital data to the decoder4′. At that time, the demodulator9sends information related to the received signal to the decoder4′. Based on the information related to the received signal as sent by the demodulator9, the decoder4′ obtains the bit-by-bit probability value of the digital data sent by the demodulator9. Then, based on the obtained probability values, the decoder4′ decodes the LDPC code in the manner described in each embodiment, and restores the input data5′. Subsequently, the decoder4′ outputs the restored data as output data6′.

In the manner described above, in the communication system that transmits and receives information over the communication path8, the circuit of the check node processor that performs the check node processing in the LDPC decoding can be downscaled, compared with the existing configuration.