Patent Publication Number: US-11050440-B2

Title: Encoder, decoder, encoding method and decoding method based on low-density parity-check code

Description:
BACKGROUND OF THE INVENTION 
     Field of the Invention 
     The invention relates to an encoder, a decoder, an encoding method and a decoding method based on Low-Density Parity-Check (LDPC) code. 
     Description of the Related Art 
     Low-Density Parity-Check (LDPC) code is a linear error correction code (ECC), which is widely used in error correction mechanisms of communication systems and memory devices. However, although the ability of error correction of LDPC code outperforms algebraic code, the ability of error correction of LDPC code is not good enough in cases that the raw bit error rate is extremely low. 
     SUMMARY OF THE INVENTION 
     An embodiment of the present invention discloses an encoder based on Low-Density Parity-Check (LDPC) code comprises a first encoding unit, a second encoding unit and a concatenation unit. The first encoding unit is configured to receive an information for encoding, and generate a first portion codeword according to a first encoding rule and the information for encoding, wherein the first encoding rule is an encoding rule configured to generate LDPC code. The second encoding unit is coupled to the first encoding unit, and is configured to receive the first portion codeword, and generate a second portion codeword according to a second encoding rule different from the first encoding rule and a double check region of the first portion codeword. The concatenation unit is coupled to the first encoding unit and the second encoding unit, and is configured to concatenate the first portion codeword and the second portion codeword to generate a codeword. A plurality of trapping sets corresponding to the first encoding rule include at least one error bit within the double check region. 
     An embodiment of the present invention discloses a decoder based on Low-Density Parity-Check (LDPC) code comprises a first decoding unit and a second decoding unit. The first decoding unit is configured to receive a codeword, extract a first portion codeword of the codeword, and decode the first portion codeword according to a first decoding rule, wherein the first decoding rule is a decoding rule configured to decode LDPC code. The second decoding unit is coupled to the first decoding unit, and is configured to receive the codeword processed by the first decoding unit when the first decoding unit fails to decode the first portion codeword, extract a second portion codeword of the codeword, decode the second portion codeword according to a second decoding rule different from the first decoding rule, correct a double check region of the first portion codeword according to a result of decoding the second portion codeword, and transmit the first portion codeword which includes the correct double check region for decoding again. A plurality of trapping sets corresponding to the first decoding rule include at least one error bit within the double check region. 
     An embodiment of the present invention discloses an encoding method based on Low-Density Parity-Check (LDPC) code comprises: receiving, by an encoder, an information for encoding; generating, by the encoder, a first portion codeword according to a first encoding rule and the information for encoding, wherein the first encoding rule is an encoding rule configured to generate LDPC code; generating, by the encoder, a second portion codeword according to a second encoding rule different from the first encoding rule and a double check region of the first portion codeword; and concatenating, by the encoder, the first portion codeword and the second portion codeword to generate a codeword. A plurality of trapping sets corresponding to the first encoding rule include at least one error bit within the double check region. 
     An embodiment of the present invention discloses a decoding method based on Low-Density Parity-Check (LDPC) code comprises: receiving, by a decoder, a codeword; extracting, by the decoder, a first portion codeword of the codeword, and decoding the first portion codeword according to a first decoding rule, wherein the first decoding rule is a decoding rule configured to decode LDPC code; determining, by the decoder, whether the decoding is success; when decoding fails, extracting, by the decoder, a second portion codeword of the codeword, and decoding the second portion codeword according to a second decoding rule different from the first decoding rule; correcting, by the decoder, a double check region of the first portion codeword according to a result of decoding the second portion codeword, and decoding, by the decoder, the first portion codeword which includes the corrected double check region. A plurality of trapping sets corresponding to the first decoding rule include at least one error bit within the double check region. 
     The above and other aspects of the invention will become better understood with regard to the following detailed description of the preferred but non-limiting embodiment(s). The following description is made with reference to the accompanying drawings. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  shows a block diagram of an encoding/decoding system based on LDPC code according to an embodiment of the present invention. 
         FIG. 2  shows a schematic diagram of trapping sets of a LDPC code. 
         FIG. 3  shows a block diagram of an encoder based on LDPC code according to an embodiment of the present invention. 
         FIG. 4  shows a flowchart of an encoding method based on LDPC code according to an embodiment of the present invention. 
         FIG. 5  shows a block diagram of a decoder based on LDPC code according to an embodiment of the present invention. 
         FIG. 6  shows a flowchart of a decoding method based on LDPC code according to an embodiment of the present invention. 
     
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     Referring to  FIG. 1 ,  FIG. 1  shows a block diagram of an encoding/decoding system based on Low-Density Parity-Check (LDPC) code according to an embodiment of the present invention. Encoding/decoding system  10  includes an encoder  20  and a decoder  30 . The encoder  20  is configured to encode an information for encoding IF into a codeword according to an encoding algorithm based on LDPC code, and transmit the codeword to the decoder  30  via a channel  40 . The decoder  30  is configured to decode the codeword to a decoded information DeIF according to a decoding algorithm based on LDPC code. Details of the encoder  20 , the decoder  30 , the encoding algorithm and the decoding algorithm may be described below. 
     Before the details of the encoder  20 , the decoder  30 , the encoding algorithm and the decoding algorithm being described, a problem encountered by the LDPC code may be explained firstly. Refers to a schematic diagram of trapping sets of a LDPC code shown in  FIG. 2 . Codewords generated based on a specific LDPC encoding rule may have error bits for various reason during transmission through the channel and when the decoder is receiving. Some of these codewords having error bits (hereafter, error pattern) may be corrected by the decoder during iterations and the correct information may be obtained, but some of the error patterns may not be corrected by the decoder during iterations due to the mechanism of LDPC code so that the correct information may not be obtained. A set formed by these an error pattern which cannot be corrected is called a trapping set corresponding to the specific LDPC encoding rule. That is, in conventional LDPC code, the error patterns of the trapping set may not be corrected by a LDPC decoder. This may lead to the difficulty of improving the error correction ability of conventional LDPC code in a case that the raw bit error rate (RBER) is extremely low. In the example of  FIG. 2 , an encoded codeword includes ten bits. The corresponding trapping sets include TP 1 ˜TP 5 , wherein correct bits are represented by white circles, and error bits are represented by black circles. 
     Referring to  FIG. 3 ,  FIG. 3  shows a block diagram of an encoder based on LDPC code according to an embodiment of the present invention. The encoder  20  includes a first encoding unit  201 , a second encoding unit  203  and a concatenation unit  205 . 
     The first encoding unit  201  is configured to receive the information for encoding IF, and generate a first portion codeword CW 1  according to a first encoding rule and the information for encoding, wherein the first encoding rule is an encoding rule configured to generate a LDPC code. In other words, the first portion codeword CW 1  by the first encoding unit  201  by encoding the information for encoding IF is a LDPC codeword. Noted that the encoding rule of LDPC code is well known by the skilled person in the art, and may not be describe herein. 
     The second encoding unit  203  is coupled to the first encoding unit  203 , is configured to receive the first portion codeword CW 1 , and generate a second portion codeword CW 2  according to a second encoding rule and a double check region of the first portion codeword CW 1 , wherein the second encoding rule is different from the first encoding rule. For example, the second encoding rule may be a encoding rule configured to generate a Bose Chaudhur Hocquenghem (BCH) code. In other embodiments, the second encoding rule may be an encoding rule for generating Cyclic redundancy check (CRC), check sum, Reed-solomon code (RS-code) or Turbo code. The “double check region” refers to a section consisting of partial bits of the first portion codeword CW 1 . The bits which make up the double check region may be continuous or discontinuous. The double check region is determined according to a trapping set corresponding to the first encoding rule, and each of the trapping sets corresponding to the first encoding rule includes at least one error bit within the double check region. A length of the double check region is less than a length of the first portion codeword CW 1 . 
     For clearly understanding of how to determine the double check region, the example of  FIG. 2  may be taken for illustration. It is assumed that the trapping set corresponding to the first encoding rule is the trapping set shown in  FIG. 2 . In an embodiment, the double check region may be determined as from the 8th bit to the 10th bit of the first portion codeword CW 1 , that is, three continuous bits. It can be observed in the trapping set shown in  FIG. 2  that, the trapping set TP 1  has an error bit within the double check region, the trapping set TP 2  has an error bit within the double check region, the trapping set TP 3  has an error bit within the double check region, the trapping set TP 4  has two error bits within the double check region, and the trapping set TP 5  has an error bit within the double check region, that is the condition for determining the double check region is met. In another embodiment, the double check region may be determined as the combination of the 2nd bit and the 8th bit of the first portion codeword CW 1 , that is, two discontinuous bits. It can be observed in the trapping set shown in  FIG. 2  that, the trapping set TP 1  has an error bit within the double check region, the trapping set TP 2  has an error bit within the double check region, the trapping set TP 3  has an error bit within the double check region, the trapping set TP 4  has two error bits within the double check region, and the trapping set TP 5  has an error bit within the double check region, that is the condition for determining the double check region is met. 
     It should be noted that after the first encoding rule is determined by an encoding designer, the trapping set corresponding to the first encoding rule may be obtained by analyzing possible error patterns of the first portion codeword CW 1 , and then the double check region may be determined by analyzing the trapping set. Therefore, the double check region may be pre-set in the second encoding unit  203 . 
     The concatenation unit  205  is coupled to the first encoding unit  201  and the second encoding unit  203 , and is configured to concatenate the first portion codeword CW 1  and the second portion codeword CW 2  to generate the codeword CW. In an embodiment, the concatenation unit  205  concatenates the second portion codeword CW 2  to the end of the first portion codeword CW 1  to generate the codeword CW. In another embodiment, the concatenation unit  205  concatenates the first portion codeword CW 1  to the end of the second portion codeword CW 2  to generate the codeword CW. In yet another embodiment, the concatenation unit  205  inserts the second portion codeword CW 2  into the first portion codeword CW 1  to generate the codeword CW. 
     Referring to  FIG. 4 ,  FIG. 4  shows a flowchart of an encoding method based on LDPC code according to an embodiment of the present invention.  FIG. 4  depicts the encoding algorithm used by the encoder  20  as a flowchart for ease of understanding. 
     In S 401 , receives an information for encoding. 
     In S 403 , encodes the information for encoding into a first portion codeword according to a first encoding rule, wherein the first encoding rule is an encoding rule of LDPC code. 
     In S 405 , encodes a double check region of the first portion codeword into a second portion codeword according to a second encoding rule, wherein the second encoding rule is different from the first encoding rule. 
     In S 407 , concatenates the first portion codeword and the second portion codeword to a codeword. 
     The codeword CW is transmitted via the channel  40  and received by the decoder  30 . Details of the decoder  30  may be illustrated below. 
     The decoder  30  includes a first decoding unit  301  and a second decoding unit  303 . The first decoding unit  301  is configured to extract the first portion codeword CW 1  of the codeword CW, and decode the first portion codeword CW 1  according to a first decoding rule corresponding to the first encoding rule. Since the codeword CW may have some error bits after being transmitted through the channel  40  due to the effect of noise. When the first portion codeword CW 1  is not able to be decoded by the first decoding unit  301 , decoding fail may be determined. When the first portion codeword CW 1  is decoded by the first decoding unit  301  successfully, decoding succeed may be determined, and the decoded first portion codeword CW 1  may be output as the decoded information DeIF. In an embodiment, although decoding fail is determined, the first decoding unit  301  still can correct partial error bits of the first portion codeword CW 1  during the decoding process. The error pattern formed by the rest error bits which cannot be corrected may probably belong to the trapping sets. After decoding fail is determined, the first decoding unit  301  may transmit the codeword CW which includes the preliminarily corrected first portion codeword CW 1  to the second decoding unit  303 . 
     The second decoding unit is coupled to the first decoding unit  301 , and is configured to receive the codeword CW which includes the preliminarily corrected first portion codeword CW 1  from the first decoding unit  301 , extract the second portion codeword CW 2  of the codeword CW, decode the second portion codeword CW 2  according to a second decoding rule corresponding to the second encoding rule, and correct the double check region of the first portion codeword CW 1  according to a result obtain by decoding the second portion codeword CW 2 . When it is observed, by decoding the second portion codeword, that the double check region includes error bit(s), the second decoding unit  303  may locate the error bit(s) in the double check region and correct it according to the result obtained by decoding the second portion codeword CW 2 . When it is observed, by decoding the second portion codeword, that the double check region includes no error bit, the second decoding unit  303  may not modify the double check region. Since each of the trapping sets includes at least one error bit within the double check region, therefore if the error pattern of the preliminarily corrected first portion codeword belongs to the trapping sets, the second decoding unit  303  can correct the error bit(s) within the double check region, and then the first portion codeword CW 1  which is corrected by the second decoding unit  303  may no longer belong to the trapping sets. 
     The codeword CW processed by the second decoding unit  303  may be transmitted to the first decoding unit  301 . The first decoding unit  301  is configured to extract the first portion codeword CW 1  processed by the second decoding unit  303 , and decode the first portion codeword CW 1  according to the first decoding rule. Since the first portion codeword CW 1  processed by the second decoding unit  303  does not belong to the trapping set anymore, the first decoding unit  301  may probably be able to decode the first portion codeword CW 1  successfully, and output the decoded first portion codeword as the decoded information DeIF. If the first decoding unit  301  still cannot decode the first portion codeword CW 1 , decoding fail confirmed may be determined and end the decoding process. Noted that, the trapping sets obtained by analyzing do not guarantee all the error pattern which causes the first decoding unit  301  to be not able to decode the first portion codeword CW 1  successfully are included, the error pattern of the first portion codeword CW 1  processed by the second decoding unit  303  may be an unknown trapping set to cause decoding fail confirmed. Even so, the encoder and the decoder described above may still solve the problem that the first portion codeword cannot be decoded successfully caused by the known trapping set obtained by analyzing, and increase the probability of error correction. 
     Referring to  FIG. 6 ,  FIG. 6  shows a flowchart of a decoding method based on LDPC code according to an embodiment of the present invention.  FIG. 4  depicts the decoding algorithm used by the decoder  30  as a flowchart for ease of understanding. 
     In S 601 , receive a codeword. 
     In S 603 , extract a first portion codeword of the codeword, and decode the first portion codeword according to a first decoding rule. 
     In S 605 , determine whether the decoding is success. If decoding is success, S 607  is performed; if decoding is not success, S 609  is performed. 
     In S 607 , output the decoded first portion codeword as a decoded information. 
     In S 609 , extract a second portion codeword of the codeword, and decode the second portion codeword according to a second decoding rule. 
     In S 611 , correct a double check region of the first portion codeword according to a result obtained by the decoding of the second portion codeword. 
     In S 613 , decode the first portion codeword which includes the corrected double check region according to the first decoding rule. 
     In S 615 , determine whether the decoding is success. If decoding is success, S 617  is performed; if decoding is not success, end the decoding process. 
     In S 617 , output the decoded first portion codeword as a decoded information. 
     The present invention provides a second layer of protection for the correctness of the double check region, by the encoder, by generating the second portion codeword based on the double check region of the first portion codeword (LDPC code). When the first decoding unit (for decoding LDPC code) of the decoder is not able to decode the first portion codeword, the decoder may use the second decoding unit to check the correctness of the double check region based on the second portion codeword and then correct the error bit(s) of the double check region. While the error bit(s) of the double check region has been corrected, the first decoding unit may probably be able to correct other errors of the first portion codeword like a domino, and decode successfully. Therefore, the present invention can effectively reduce the case of decoding fail caused by the trapping set and improve the error correction ability of the overall encoding/decoding system with a small increase in cost. 
     While the invention has been described by way of example and in terms of the preferred embodiment(s), it is to be understood that the invention is not limited thereto. On the contrary, it is intended to cover various modifications and similar arrangements and procedures, and the scope of the appended claims therefore should be accorded the broadest interpretation so as to encompass all such modifications and similar arrangements and procedures.