Decoding apparatus for low-density parity-check codes using sequential decoding, and method thereof

Abstract

Disclosed is a decoding apparatus for LDPC (Low-Density Parity-Check) codes when receiving data encoded with LDPC codes on a channel having consecutive output values, and a method thereof. The decoding method for LDPC codes uses sequential decoding and includes the following steps: (a) the nodes are divided according to a parity-check matrix into check nodes for a parity-check message and variable nodes for a bit message; (b) the check nodes are divided into a predetermined number of subsets; (c) the LDPC codeword of each subset for all the check nodes is sequentially decoded; (d) an output message is generated for verifying validity of the decoding result; and (e) the steps (b), (c), and (d) are iteratively performed by a predetermined number of iterations.

What is claimed is: 
     
       1. A method for a decoding apparatus to decode, the method comprising:
 (a) dividing, by a message-passing decoder of the decoding apparatus, nodes into check nodes for a parity-check message and variable nodes for a bit message according to a parity-check matrix; 
 (b) dividing, by the message-passing decoder of the decoding apparatus, the check nodes into a predetermined number of subsets; 
 (c) sequentially decoding, by the message-passing decoder of the decoding apparatus, a LDPC (Low Density Parity Check) codeword of each subset for all the check nodes; 
 (d) generating, by the message-passing decoder of the decoding apparatus, an output message for verifying validity of the decoding result; and 
 (e) iteratively performing, by the message-passing decoder of the decoding apparatus, the steps (b), (c), and (d) by a predetermined number of iterations, wherein the number of decoding iterations is reduced according to an increase in the convergence rate when the validity of the LDPC codeword is determined from the output message of the step (d). 
 
     
     
       2. The method as claimed in  claim 1 , further comprising: interrupting the decoding operation when the output message of the step (d) satisfies a defined decoding check equation. 
     
     
       3. The method as claimed in  claim 1 , wherein the number of decoding iterations is fixed at a value smaller than the maximum number of decoding iterations during the iterative decoding process. 
     
     
       4. The method as claimed in  claim 1 , wherein each of the subsets of the check nodes is decoded with a different priority. 
     
     
       5. The method as claimed in  claim 4 , wherein the subset for highest-order variable nodes connected to the check nodes is decoded with a highest priority. 
     
     
       6. The method as claimed in  claim 1 , wherein the step (b) comprises: dividing the check nodes into subsets each having a different number of elements. 
     
     
       7. The method as claimed in  claim 6 , wherein the number of the subsets is an integer other than a divisor of the number of the check nodes. 
     
     
       8. A method for a decoding apparatus to decode, the method comprising:
 (a) dividing, by a message-passing decoder of the decoding apparatus, nodes into check nodes for a parity-check message and variable nodes for a bit message according to a parity-check matrix; 
 (b) dividing, by the message-passing decoder of the decoding apparatus, the check nodes into a predetermined number of subsets; 
 (c) sequentially decoding, by the message-passing decoder of the decoding apparatus, a LDPC (Low Density Parity Check) codeword of each subset for all the check nodes; 
 (d) generating, by the message-passing decoder of the decoding apparatus, an output message for verifying validity of the decoding result; and 
 (e) iteratively performing, by the message-passing decoder of the decoding apparatus, the steps (b), (c), and (d) by a predetermined number of iterations, wherein the step (e) comprises: changing the decoding order of the subsets used in a previous decoding operation when the number of decoding iterations is increased. 
 
     
     
       9. The method as claimed in  claim 8 , comprising: reversing the decoding order used in the previous decoding operation, or determining a new decoding priority to the subsets. 
     
     
       10. The method as claimed in  claim 8 , comprising: differentiating the decoding priority to the subsets of the check nodes according to the number of decoding iterations. 
     
     
       11. An apparatus comprising:
 a codeword regenerator for regenerating LDPC codes received through a channel into a codeword for decoding; 
 a message-passing decoder for sequentially decoding the LDPC codeword of each subset for all check nodes, the check nodes being divided into predetermined subsets, wherein the message-passing decoder comprises:
 a parity-check matrix memory for storing a parity-check matrix, 
 an input buffer memory for storing an input message, and 
 a variable node message updater for receiving an input from the input buffer memory and a check node output memory and processing an output message of the variable nodes according to the stored parity-check matrix; and 
 
 an information-restoring section for determining whether there is an error in the decoded codeword, and extracting and transmitting information when there is no error in the codeword. 
 
     
     
       12. The apparatus as claimed in  claim 11 , wherein the message-passing decoder exchanges messages through defined edges between check nodes for a parity-check message and variable nodes for a bit message according to a parity-check matrix to update a node message. 
     
     
       13. The apparatus as claimed in  claim 12 , wherein the number of subsets is equal to or greater than a maximum order of the variable nodes. 
     
     
       14. The apparatus as claimed in  claim 12 , wherein each of all the edges connected to a specific one of the variable nodes is included in a different subset. 
     
     
       15. The apparatus as claimed in  claim 11 , wherein the message-passing decoder comprises:
 a variable node output memory for storing a result of the variable node message updater; 
 a check node processor for receiving data stored in the variable node output memory to process the output message of the check nodes, and transmitting the processed output message to the variable node message updater; 
 a check node output memory for storing a processing result of the output message of the check nodes; 
 an output buffer memory for transmitting the decoding result to the information-restoring section so as to verify validity of the decoding result, after completion of the decoding operation for all the subsets; and 
 a decoding operation controller for determining all kinds of operations related to the decoding operation. 
 
     
     
       16. The apparatus as claimed in  claim 15 , wherein the data of the variable node output memory are message-updated as often as the number of the subsets. 
     
     
       17. The apparatus as claimed in  claim 15 , wherein after the completion of the decoding operation on one subset, the connection state of nodes and edges in the variable node message updater and the check node processor is loaded from the decoding operation controller to reset nodes and edges for a next subset. 
     
     
       18. The apparatus as claimed in  claim 11 , wherein the decoding operation of the message-passing decoder is iteratively performedwith a predetermined number of decoding iterations. 
     
     
       19. A method for a decoding apparatus to decode, the method comprising:
 (a) dividing, by a message-passing decoder of the decoding apparatus, nodes into check nodes for a parity-check message and variable nodes for a bit message according to a parity-check matrix;   (b) dividing, by the message-passing decoder of the decoding apparatus, the check nodes into a predetermined number of subsets;   (c) sequentially decoding, by the message-passing decoder of the decoding apparatus, a Low Density Parity Check codeword of each subset for all the check nodes;   (d) generating, by the message-passing decoder of the decoding apparatus, an output message; and   (e) iteratively performing, by the message-passing decoder of the decoding apparatus, the steps (b), (c), and (d) by a predetermined number of iterations, wherein the number of decoding iterations is reduced according to an increase in the convergence rate when a validity of the Low Density Parity Check codeword is determined from the output message of the step (d).   
     
     
       20. A method for a decoding apparatus to decode, the method comprising:
 (a) dividing, by a message-passing decoder of the decoding apparatus, nodes into check nodes for a parity-check message and variable nodes for a bit message according to a parity-check matrix;   (b) dividing, by the message-passing decoder of the decoding apparatus, the check nodes into a predetermined number of subsets;   (c) sequentially decoding, by the message-passing decoder of the decoding apparatus, a Low Density Parity Check codeword of each subset for all the check nodes;   (d) generating, by the message-passing decoder of the decoding apparatus, an output message; and   (e) iteratively performing, by the message-passing decoder of the decoding apparatus, the steps (b), (c), and (d) by a predetermined number of iterations, wherein the step (e) comprises: changing the decoding order of the subsets used in a previous decoding operation when the number of decoding iterations is increased.   
     
     
       21. An apparatus comprising:
 a codeword regenerator that regenerates Low Density Parity Check codes received through a channel into a codeword for decoding;   a message-passing decoder that sequentially decodes the Low Density Parity Check codeword of each subset for all check nodes, the check nodes being divided into predetermined subsets, wherein the message-passing decoder comprises:   a parity-check matrix memory that stores a parity-check matrix,   an input buffer memory that stores an input message, and   a variable node message updater that receives an input from the input buffer memory and a check node output memory and processes an output message of the variable nodes according to the stored parity-check matrix; and   an information-restoring section that determines whether there is an error in the decoded codeword and extracts information when there is no error in the codeword.