Method and system for encoding data using rate-compatible irregular LDPC codes based on edge growth and parity splitting

• US 20090006906A1
• Filed: 06/29/2007
• Published: 01/01/2009
• Est. Priority Date: 06/29/2007
• Status: Active Grant

• Current Assignee: LGS Innovations LLC (CACI International Incorporated)
• Original Assignee: Alcatel-Lucent USA, Inc. (Nokia Corporation)
• Inventors: Soni, Robert Atmaram, Jacobsen, Noah
• Granted Patent: US 7,966,548 B2
• Time in Patent Office: Days
• US Class Current: 714/52
• CPC Class Codes: H03M 13/033 Theoretical methods to calculate these checking codes
• CPC Class Codes: H03M 13/11 using multiple parity bits
• CPC Class Codes: H03M 13/6306 Error control coding in combination with Automatic Repeat reQuest [ARQ] and diversity transmission, e.g. coding schemes for the multiple transmission of the same information or the transmission of incremental redundancy H03M13/3761, H03M13/3769 and H03M13/635 take precedence
• CPC Class Codes: H03M 13/635 Error control coding in combination with rate matching
• CPC Class Codes: H03M 13/6393 Rate compatible low-density parity check [LDPC] codes

Abstract

In a system for parity encoding data using a low density parity check (LDPC) code, a rate-compatible, irregular LDPC code is generated by extending a base code using a constrained edge growth operation and a parity splitting operation. The base code is a “daughter” code having an encoding rate higher than a designated rate of the LDPC code. The daughter code is progressively extended to lower and lower rates such that each extension code (including the target LDPC code) is compatible with the previously obtained codes. The extension operation may involve introducing a set of new code symbols to the daughter code, by splitting check nodes of a base graph associated with the daughter code, and through constrained edge growth of the base graph. The LDPC code is used to parity encode a data message as a means for forward error correction across a communication channel.

Claims

1. A method of processing data comprising:

generating a rate-compatible low density parity check (LDPC) code, wherein the LDPC code is generated using a constrained edge growth operation and a parity splitting operation to extend a base code; and

encoding at least a portion of a data message using at least one of the LDPC code and a parity check matrix associated with the LDPC code.

2. The method of claim 1 wherein:

the LDPC code is an irregular LDPC code; and

the base code is an LDPC daughter code having a code rate higher than a designated code rate of the irregular LDPC code.

3. The method of claim 2 wherein:

the data message is encoded at the designated rate; and

the method further comprises optimizing the LDPC code for the designated rate.

4. The method of claim 3 wherein the LDPC code is optimized based on an extrinsic-information transfer (EXIT) chart.

5. The method of claim 4 wherein:

the daughter code is extended by introducing a set of new code symbols to the daughter code;

the number of new code symbols is a function of the rate of the daughter code and the designated rate;

a first subset of the new code symbols is generated by splitting check nodes of a base graph associated with the daughter code; and

a second, remaining subset of the new code symbols is generated by constrained edge growth of the base graph.

6. The method of claim 5 wherein optimization constraints of the LDPC optimization procedure are given by:

(i) check-degree distributions and variable-degree distributions of the base graph; and

(ii) the designated rate.

7. The method of claim 2 wherein:

the daughter code is extended by introducing a set of new code symbols to the daughter code; and

the number of new code symbols is a function of the rate of the daughter code and the designated rate.

8. The method of claim 7 further comprising:

generating a first subset of the new code symbols by splitting check nodes of a base graph associated with the daughter code; and

generating a second, remaining subset of the new code symbols by constrained edge growth of the base graph.

9. A data communications method comprising the steps of:

encoding at least a portion of a data message using a rate-compatible parity check matrix of a low density parity check (LDPC) code; and

transmitting the encoded data message over a communication channel;

wherein the LDPC code is derived from a base code though at least one extension operation, said operation including constrained edge growth and parity splitting of the base code.

10. The method of claim 9 wherein:

the LDPC code is an irregular LDPC code; and

the base code is an LDPC daughter code having a code rate higher than a designated code rate of the irregular LDPC code.

11. The method of claim 10 wherein:

the data message is encoded at the designated rate; and

the method further comprises optimizing the LDPC code for the designated rate.

12. The method of claim 11 wherein the LDPC code is optimized based on an extrinsic-information transfer (EXIT) chart.

13. The method of claim 11 wherein:

the extension operation comprises introducing a set of new code symbols to the daughter code;

the number of new code symbols is a function of the rate of the daughter code and the designated rate.

14. The method of claim 13 further comprising:

generating a first subset of the new code symbols by splitting check nodes of a base graph associated with the daughter code; and

generating a second, remaining subset of the new code symbols by constrained edge growth of the base graph.

15. The method of claim 14 further comprising:

optimizing the first and second subsets, as relating to the number of new code symbols in each subset.

16. The method of claim 14 wherein optimization constraints of the LDPC optimization procedure are given by:

(i) check-degree distributions and variable-degree distributions of the base graph; and

(ii) the designated rate.

17. The method of claim 10 further comprising:

generating redundant data for transmission over the communication channel based on at least one of a redundancy determination by a transmitting unit and feedback received from a receiving unit, wherein the redundant data is generated using at least one linear block code encoding operation.

18. The method of claim 10 further comprising:

receiving the encoded data message over the communication channel; and

decoding the encoded data message in a puncture-less manner, wherein the encoded data message is decoded by a decoding unit that operates only on a parity-check submatrix corresponding to the designated rate.

19. A method of generating a rate-compatible, irregular low density parity check (LDPC) code having a designated coding rate, said method comprising:

extending a base LDPC code having a rate higher than the designated coding rate;

wherein the base LDPC code is extended using a constrained edge growth operation and a parity splitting operation on the base code; and

wherein the LDPC code is optimized for the designated rate.

20. The method of claim 19 wherein:

the base code is extended by introducing a set of new code symbols to the base code, wherein (i) a first subset of the new code symbols is generated by splitting check nodes of a base graph associated with the base code and (ii) a second, remaining subset of the new code symbols is generated by constrained edge growth of the base graph; and

the number of new code symbols is a function of the rate of the base code and the designated rate.