Computationally efficient convolutional coding with rate-matching

• US 9,231,621 B2
• Filed: 11/05/2013
• Issued: 01/05/2016
• Est. Priority Date: 06/08/2007
• Status: Active Grant

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Cheng, Jung-Fu
• Primary Examiner(s): Chase, Shelly A
• Application Number:
  US14/072,524
• Publication Number:
  US 20140059410A1
• Time in Patent Office: 791 Days
• Field of Search: 714701-702, 714/746, 714/786, 714/790
• US Class Current: 1/1
• CPC Class Codes: H03M 13/23 using convolutional codes, e.g. unit memory codes
• CPC Class Codes: H03M 13/235 Encoding of convolutional codes, e.g. methods or arrangements for parallel or block-wise encoding
• CPC Class Codes: H03M 13/27 using interleaving techniques
• CPC Class Codes: H03M 13/2732 Convolutional interleaver; Interleavers using shift-registers or delay lines like, e.g. Ramsey type interleaver
• CPC Class Codes: H03M 13/2792 Interleaver wherein interleaving is performed jointly with another technique such as puncturing, multiplexing or routing
• CPC Class Codes: H03M 13/2957 Turbo codes and decoding
• CPC Class Codes: H03M 13/6356 by repetition or insertion of dummy data, i.e. rate reduction
• CPC Class Codes: H03M 13/6362 by puncturing
• CPC Class Codes: H04L 1/0059 Convolutional codes
• CPC Class Codes: H04L 1/0069 Puncturing patterns
• CPC Class Codes: H04L 1/0071 Use of interleaving interleaving per se H03M13/27

Abstract

An error coding circuit comprises a non-systematic convolutional encoder for coding an input bit stream to produce two or more groups of parity bits, an interleaver circuit for interleaving parity bits within each group of parity bits, and a rate-matching circuit for outputting a selected number of the interleaved parity bits ordered by group to obtain a desired code rate.

Claims

1. An error coding circuit comprising:

a convolutional encoder configured to receive an input bit stream and to generate two or more groups of parity bits from the input bit stream;

an interleaver circuit configured to separately interleave parity bits within each group of parity bits, wherein the interleaver circuit is configured to order parity bits within each group such that odd parity bits precede even parity bits within each group of interleaved parity bits; and

a rate-matching circuit configured to output a selected number of said interleaved parity bits, to obtain an output code rate, such that a first one of the groups is output before a second one of the groups.

2. The error coding circuit of claim 1, wherein the rate-matching circuit includes a circular buffer storing the interleaved parity bits, ordered by group, and wherein said rate-matching circuit is configured to output the selected number of interleaved parity bits from the circular buffer.

3. The error coding circuit of claim 1, wherein said interleaver circuit is configured to apply identical interleaving for each group of parity bits.

4. The error coding circuit of claim 1, wherein the rate-matching circuit is configured to puncture parity bits, when the two or more groups of parity bits include more bits than needed to achieve the output code rate, by puncturing up to all of the parity bits in one of the groups of parity bits before puncturing bits in any other group of parity bits.

5. The error coding circuit of claim 1, wherein the rate-matching circuit is configured to repeat parity bits, when the two or more groups of parity bits include fewer bits than needed to achieve the output code rate, by repeating up to all of the parity bits in one of the groups of parity bits before repeating bits in any other group of parity bits.

6. An error coding circuit comprising:

a convolutional encoder configured to receive an input bit stream and to generate two or more groups of parity bits from the input bit stream;

an interleaver circuit configured to separately interleave parity bits within each group of parity bits; and

a rate-matching circuit configured to output a selected number of said interleaved parity bits, to obtain an output code rate, such that a first one of the groups is output before a second one of the groups;

wherein the convolutional encoder is configured to implement a rate ⅓

tail-biting convolutional code belonging to the class of maximum free distance codes with optimal distance spectra, such that a rate ½

code belonging to the class of maximum free distance codes with optimal distance spectra can be obtained by puncturing one of the groups of parity bits.

7. An error coding circuit comprising:

a convolutional encoder configured to receive an input bit stream and to generate two or more groups of parity bits from the input bit stream;

an interleaver circuit configured to separately interleave parity bits within each group of parity bits; and

a rate-matching circuit configured to output a selected number of said interleaved parity bits, to obtain an output code rate, such that a first one of the groups is output before a second one of the groups;

wherein the convolutional encoder is configured to implement a rate ⅓

tail-biting convolutional code with a constraint length k=7 and a generator polynomial [133, 171, 165]_o.

8. The error coding circuit of claim 7, wherein the rate-matching circuit is configured to obtain a code rate of ½

by outputting all of the parity bits in first and second groups of parity bits and puncturing all of the parity bits in a third group of parity bits.

9. A method for error coding an input bit stream, the method comprising:

generating two or more groups of parity bits from a received input bit stream, using a convolutional encoder;

separately interleaving parity bits within each group of parity bits, wherein said separately interleaving parity bits within each group comprises ordering parity bits within each group such that odd parity bits precede even parity bits within each group of parity bits; and

outputting a selected number of said interleaved parity bits to obtain an output code rate, wherein said outputting comprises outputting a first one of the groups before outputting a second one of the groups.

10. The method of claim 9, further comprising storing the interleaved parity bits in a circular buffer, ordered by group, and outputting the selected number of interleaved parity bits from the circular buffer.

11. The method of claim 9, wherein said separately interleaving parity bits within each group of parity bits comprises applying identical interleaving for each group of parity bits.

12. The method of claim 9, wherein said outputting comprises puncturing parity bits, when the two or more groups of parity bits include more bits than needed to achieve the output code rate, by puncturing up to all of the parity bits in one of the groups of parity bits before puncturing bits in any other group of parity bits.

13. The method of claim 9, wherein said outputting comprises repeating parity bits, when the two or more groups of parity bits include fewer bits than needed to achieve the output code rate, by repeating up to all of the parity bits in one of the groups of parity bits before repeating bits in any other group of parity bits.

14. A method for error coding an input bit stream, the method comprising:

generating two or more groups of parity bits from a received input bit stream, using a convolutional encoder;

separately interleaving parity bits within each group of parity bits; and

outputting a selected number of said interleaved parity bits to obtain an output code rate, wherein said outputting comprises outputting a first one of the groups before outputting a second one of the groups;

wherein generating two or more groups of parity bits from the received input bit stream comprises using a rate ⅓

tail-biting convolutional code belonging to the class of maximum free distance codes with optimal distance spectra, such that a rate ½

code belonging to the class of maximum free distance codes with optimal distance spectra can be obtained by puncturing one of the groups of parity bits.

15. A method for error coding an input bit stream, the method comprising:

generating two or more groups of parity bits from a received input bit stream, using a convolutional encoder;

separately interleaving parity bits within each group of parity bits; and

outputting a selected number of said interleaved parity bits to obtain an output code rate, wherein said outputting comprises outputting a first one of the groups before outputting a second one of the groups;

wherein generating two or more groups of parity bits from the received input bit stream comprises using a rate ⅓

tail-biting convolutional code with a constraint length k=7 and a generator polynomial [133, 171, 165]_o.

16. The method of claim 15, wherein said outputting obtains a code rate of ½

by outputting all of the parity bits in first and second groups of parity bits and puncturing all of the parity bits in a third group of parity bits.