Clash-free irregular-repeat-accumulate code

• US 20070011566A1
• Filed: 04/14/2006
• Published: 01/11/2007
• Est. Priority Date: 04/15/2005
• Status: Active Grant

• Current Assignee: Trellisware Technologies, Inc. (ViaSat Incorporated)
• Original Assignee: Trellisware Technologies, Inc. (ViaSat Incorporated)
• Inventors: Chugg, Keith, Gray, Paul
• Granted Patent: US 7,584,400 B2
• Time in Patent Office: Days
• US Class Current: 714/758
• CPC Class Codes: H03M 13/03 Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
• 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/1137 Partly parallel processing, i.e. sub-blocks or sub-groups of nodes being processed in parallel
• CPC Class Codes: H03M 13/1174 Parity-check or generator matrices built from sub-matrices representing known block codes such as, e.g. Hamming codes, e.g. generalized LDPC codes
• CPC Class Codes: H03M 13/118 Parity check matrix structured for simplifying encoding, e.g. by having a triangular or an approximate triangular structure H03M13/1165 takes precedence
• CPC Class Codes: H03M 13/1185 wherein the parity-check matrix comprises a part with a double-diagonal
• CPC Class Codes: H03M 13/1197 Irregular repeat-accumulate [IRA] codes
• CPC Class Codes: H03M 13/275 Interleaver wherein the permutation pattern is obtained using a congruential operation of the type y=ax+b modulo c
• CPC Class Codes: H03M 13/29 combining two or more codes or code structures, e.g. product codes, generalised product codes, concatenated codes, inner and outer codes
• CPC Class Codes: H03M 13/6362 by puncturing
• CPC Class Codes: H03M 13/6508 Flexibility, adaptability, parametrability and configurability of the implementation
• CPC Class Codes: H03M 13/6566 Implementations concerning memory access contentions

Abstract

Methods, apparatuses, and systems are presented for performing data encoding involving receiving a sequence of data bits, encoding the sequence of data bits in accordance with a parity check matrix (H-matrix) to generate a sequence of encoded bits, wherein the H-matrix is capable of being partitioned into a first matrix and a second matrix, the first matrix being a dual-diagonal matrix, the second matrix comprising one or more vertically stacked sub-matrices, each sub-matrix consisting of a plurality of columns, each column having a column weight of no more than 1, wherein the second matrix is capable of being expressed as a product of a parity check matrix, an interleaver permutation matrix, and a repeat block matrix, and the interleaver permutation matrix satisfies a clash-free interleaver constraint, and outputting the sequence of encoded bits.

Claims

1. A method for performing data encoding comprising:

receiving a sequence of data bits;

encoding the sequence of data bits in accordance with a parity check matrix (H-matrix) to generate a sequence of encoded bits;

wherein the H-matrix is capable of being partitioned into a first matrix and a second matrix, the first matrix being a dual-diagonal matrix, the second matrix comprising one or more vertically stacked sub-matrices, each sub-matrix consisting of a plurality of columns, each column having a column weight of no more than 1;

wherein the second matrix is capable of being expressed as a product of a parity check matrix, an interleaver permutation matrix, and a repeat block matrix, and the interleaver permutation matrix satisfies a clash-free interleaver constraint; and

outputting the sequence of encoded bits.

2. The method of claim 1 wherein the encoding step is performed using an irregular-repeat-accumulate (IRA) encoder comprising an irregular repetition encoder, an interleaver, a single parity check encoder (SPC), and an accumulator.

3. The method of claim 1 wherein the encoding step performed using an irregular-repeat-accumulate (IRA) encoder comprising an irregular repetition encoder, an interleaver, an accumulator, and a bit puncture unit.

4. The method of claim 1 wherein the encoding step is performed using a low density parity check (LDPC) encoder.

5. The method of claim 1 wherein the clash-free interleaver constraint supports clash-free window decoder operation.

6. The method of claim 1 wherein the clash-free interleaver constraint supports clash-free tile decoder operation.

7. The method of claim 1 wherein the clash-free interleaver constraint supports clash-free window decoder operation and clash-free tile decoder operation.

8. The method of claim 1 wherein the code is selected by finding a particular parity check matrix satisfying the clash-free interleaver constraint, computing a corresponding second matrix based on the particular parity check matrix, and evaluating whether the corresponding second matrix comprises one or more vertically stacked sub-matrices such that each sub-matrix consists of a plurality of columns, with each column having a column weight of no more than 1.

9. The method of claim 1 wherein the code is selected by finding a particular second matrix comprising one or more vertically stacked sub-matrices such that each sub-matrix consists of a plurality of columns, with each column having a column weight of no more than 1, computing a corresponding parity check matrix based on the second matrix, and evaluating whether the parity check matrix satisfies the clash-free interleaver constraint.

12. The apparatus of claim 1 wherein the encoder is an irregular-repeat-accumulate (IRA) encoder comprising an irregular repetition encoder, an interleaver, a single parity check encoder (SPC), and an accumulator.

13. The apparatus of claim 1 wherein the encoder is an irregular-repeat-accumulate (IRA) encoder comprising an irregular repetition encoder, an interleaver, an accumulator, and a bit puncture unit.

14. The apparatus of claim 1 wherein the encoder is a low density parity check (LDPC) encoder.

15. The apparatus of claim 1 wherein the clash-free interleaver constraint supports clash-free window decoder operation.

16. The apparatus of claim 1 wherein the clash-free interleaver constraint supports clash-free tile decoder operation.

17. The apparatus of claim 1 wherein the clash-free interleaver constraint supports clash-free window decoder operation and clash-free tile decoder operation.

18. The apparatus of claim 1 wherein the code is selected by finding a particular parity check matrix satisfying the clash-free interleaver constraint, computing a corresponding second matrix based on the particular parity check matrix, and evaluating whether the corresponding second matrix comprises one or more vertically stacked sub-matrices such that each sub-matrix consists of a plurality of columns, with each column having a column weight of no more than 1.

19. The apparatus of claim 1 wherein the code is selected by finding a particular second matrix comprising one or more vertically stacked sub-matrices such that each sub-matrix consists of a plurality of columns, with each column having a column weight of no more than 1, computing a corresponding parity check matrix based on the second matrix, and evaluating whether the parity check matrix satisfies the clash-free interleaver constraint.

10. A method for performing data decoding comprising:

receiving a sequence of encoded bits;

decoding the sequence of encoded bits in accordance with a parity check matrix (H-matrix) to generate a sequence of decoded bits;

wherein the H-matrix is capable of being partitioned into a first matrix and a second matrix, the first matrix being a dual-diagonal matrix, the second matrix comprising one or more vertically stacked sub-matrices, each sub-matrix consisting of a plurality of columns, each column having a column weight of no more than 1;

wherein the second matrix is capable of being expressed as a product of a parity check matrix, an interleaver permutation matrix, and a repeat block matrix, and the interleaver permutation matrix satisfies a clash-free interleaver constraint; and

outputting the sequence of decoded bits.

11. An apparatus for performing data encoding comprising:

an input interface for receiving a sequence of data bits;

an encoder coupled to the input interface capable of encoding the sequence of data bits in accordance with a parity check matrix (H-matrix) to generate a sequence of encoded bits;

wherein the H-matrix is capable of being partitioned into a first matrix and a second matrix, the first matrix being a dual-diagonal matrix, the second matrix comprising one or more vertically stacked sub-matrices, each sub-matrix consisting of a plurality of columns, each column having a column weight of no more than 1;

wherein the second matrix is capable of being expressed as a product of a parity check matrix, an interleaver permutation matrix, and a repeat block matrix, and the interleaver permutation matrix satisfies a clash-free interleaver constraint; and

an output interface couple to the encoder for outputting the sequence of encoded bits.

20. A apparatus for performing data decoding comprising:

an input interface for receiving a sequence of encoded bits;

a decoder coupled to the input interface capable of decoding the sequence of encoded bits in accordance with a parity check matrix (H-matrix) to generate a sequence of decoded bits;

wherein the H-matrix is capable of being partitioned into a first matrix and a second matrix, the first matrix being a dual-diagonal matrix, the second matrix comprising one or more vertically stacked sub-matrices, each sub-matrix consisting of a plurality of columns, each column having a column weight of no more than 1;

wherein the second matrix is capable of being expressed as a product of a parity check matrix, an interleaver permutation matrix, and a repeat block matrix, and the interleaver permutation matrix satisfies a clash-free interleaver constraint; and

an output interface coupled to the decoder for outputting the sequence of decoded bits.

21. A system for performing data encoding comprising:

means for receiving a sequence of data bits;

means for encoding the sequence of data bits in accordance with a parity check matrix (H-matrix) to generate a sequence of encoded bits;

wherein the H-matrix is capable of being partitioned into a first matrix and a second matrix, the first matrix being a dual-diagonal matrix, the second matrix comprising one or more vertically stacked sub-matrices, each sub-matrix consisting of a plurality of columns, each column having a column weight of no more than 1;

wherein the second matrix is capable of being expressed as a product of a parity check matrix, an interleaver permutation matrix, and a repeat block matrix, and the interleaver permutation matrix satisfies a clash-free interleaver constraint; and

means for outputting the sequence of encoded bits.