Turbo coding, decoding devices and turbo coding, decoding methods

• US 6,233,711 B1
• Filed: 04/30/1999
• Issued: 05/15/2001
• Est. Priority Date: 09/02/1997
• Status: Expired due to Term

• Current Assignee: Robert J. Mceliece, Sony Corporation (Sony Group Corp.)
• Original Assignee: Robert J. Mceliece, Sony Corporation (Sony Group Corp.)
• Inventors: McEliece, Robert J., Murayama, Jun, Hattori, Masayuki
• Primary Examiner(s): Decady, Albert
• Assistant Examiner(s): LAMARRE, GUY J
• Application Number:
  US09/310,161
• Time in Patent Office: 746 Days
• Field of Search: 714/786-787, 375/140, 375/145, 375/146, 375/367, 375/265, 375/262, 375/341
• US Class Current: 714/786
• CPC Class Codes: H03M 13/2771 Internal interleaver for turbo codes H03M13/2714 and H03M13/2725 take precedence
• 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/2903 Methods and arrangements specifically for encoding, e.g. parallel encoding of a plurality of constituent codes
• CPC Class Codes: H03M 13/2945 using at least three error correction codes H03M13/2957 takes precedence
• CPC Class Codes: H03M 13/2993 Implementing the return to a predetermined state, i.e. trellis termination

Abstract

A device for encoding turbo codes for use in satellite communications. Input data including termination bits are supplied to a series of interleaver circuits. Coding circuits perform convolution operations on data output from the respective interleavers, thereby obtaining coded data. The encoding process automatically results in terminated coded data. Thus, termination circuits are unnecessary. The determination of substitute positions by the respective interleavers through arithmetic computations makes it unnecessary to provide separate memory to store substitute position information.

Claims

1. A turbo coding device, comprising:

a first convolution coding circuit for performing convolution coding on input data;

first to (m−

1)th (where m is an integer≧

2) interleave circuits for successively interleaving the input data;

wherein said first to (m−

1)th interleave circuits respectively have a data arithmetic substitution circuit for computing substitute positions π

i for respective data in the input data; and

second to mth convolution coding circuits for respectively performing convolution coding on data output from the first to (m−

1)th interleave circuits.

2. The turbo coding device according to claim 1,

wherein said first to (m− 1)th interleave circuits and said second to mth convolution coding circuits are configured in series and which alternately perform interleave and convolution coding processes on data output from said first convolution coding circuit.

3. The turbo coding device according to claim 1, wherein said each data arithmetic substitution circuit determines said substitute positions π

i corresponding to positions i for the respective data in the input data from π

i=(a·

i+b)modN with the size of said each interleave circuit as N, an integer prime relative to N with each other as a and an arbitrary integer as b.

4. The turbo coding device according to claim 1, wherein said data arithmetic substitution circuit determines said substitute positions π

i corresponding to positions i for the respective data in the input data from π

i=(a·

π

<sub>i−

1</sub>+b)modN (where π

₀=c modN when c is defined as an arbitrary integer) with the size of said each interleave circuit as N, and predetermined integers as a and b.

5. The turbo coding device according to claim 4, wherein when said b is 0, said a is such an integer as to meet a^p≠

1 (2≦

p≦

N−

2).

6. The turbo coding device according to claim 4, wherein when said b is not 0, N is set to a number reduced by one from said N, and said a and b respectively meet the conditions that b and N are prime with each other, a−

1 is a multiple of all the prime numbers which divide N, and where N is a multiple of four, then a−

1 is also the multiple of four.

7. The turbo coding device according to claim 4, wherein said data arithmetic substitution circuit determines the substitute positions π

i corresponding to the positions i for the respective data in the input data by using an M series generating circuit.

8. The turbo coding device according to claim 1, wherein the input data is divided into a plurality of portions with each portion including termination bits;

said first to (m−

1)th interleave circuits successively interleaving the input data including the termination bits so that the coded data output from said second to mth convolution coding circuits automatically terminates.

9. The turbo coding device according to claim 8, wherein said first to (m−

1)th interleave circuits interleave the data inside each of said plurality of portions individually.

10. The turbo coding device according to claim 8, wherein said first to (m−

1)th interleave circuits interleave the input data in units of portions.

11. The turbo coding device according to claim 8, wherein said first to (m−

1)th interleave circuits interleave the data inside each of said plurality of portions individually and interleave said plurality of portions themselves.

12. A turbo decoding device for decoding turbo encoded data, comprising:

a plurality of soft output decoding circuits connected in series for successively performing decoding operations on the turbo encoded data, wherein said plurality of soft output decoding circuits perform a transfer of estimated probability-value data with respect to all the input data including termination bits therebetween, thereby decoding the encoded data, and

a plurality of de-interleave circuits corresponding to said plurality of soft output decoding circuits, the de-interleave circuits performing a de-interleave operation on the output of a corresponding soft output decoding circuit and passing the de-interleaved data onto a next soft output decoding circuit.

13. A turbo coding method, comprising the following steps:

a first convolution coding step for performing convolution coding on input data using a convolution coding circuit;

first to (m−

1)th (where m is an integer≧

2) interleave steps for successively interleaving the input data using interleaver circuits;

wherein in said first to (m−

1)th interleave steps, substitute positions π

i for respective data in the data to be interleaved are determined by computation using a data arithmetic substitution circuit; and

second to mth convolution coding steps for respectively performing convolution coding on data output from the first to (m−

1)th interleave steps using convolution coding circuits.

14. The turbo coding method according to claim 13, wherein said first to (m−

1)th interleave steps and said second to mth convolution coding steps are performed in an alternating serial manner so that the data output from said first convolution coding step is alternately interleaved and convolved.

15. The turbo coding method according to claim 13, wherein in said interleave step, said substitute positions π

i corresponding to positions i for the respective data in the data to be interleaved are determined from π

i=(a·

i+b)modN with the size of said interleave as N, an integer prime relative to N with each other as a and an arbitrary integer as b.

16. The turbo coding method according to claim 13, wherein in said interleave step, said substitute positions π

i corresponding to positions i for the respective data in the data to be interleaved are determined from π

i=(a·

π

<sub>i−

1</sub>+b)modN (where π

₀=c modN when c is defined as an arbitrary integer) with the size of said interleave as N, and predetermined integers as a and b.

17. The turbo coding method according to claim 16, wherein when said b is 0, said a is such an integer as to meet a^p≠

1 (2≦

p≦

N−

2).

18. The turbo coding method according to claim 16, wherein when said b is not 0, N is set to a number reduced by one from said N, and said a and b respectively meet the conditions that b and N are prime with each other, a−

1 is a multiple of all the prime numbers which divide N, and where N is a multiple of four, then a−

1 is also the multiple of four.

19. The turbo coding method according to claim 13, wherein in the interleave steps, the substitute positions π

i corresponding to the positions i for the respective data in the input data to be interleaved are determined by an M series generation circuit.

20. A turbo decoding method for decoding turbo encoded data, comprising the following steps:

a decoding step for decoding the encoded data by using a plurality of soft output decoding circuits, wherein in said decoding step, a transfer of estimated probability-value data with respect to input data including termination bits is performed between said plurality of soft output decoding circuits thereby decoding the encoded data, and

a de-interleaving step for de-interleaving the output of said plurality of soft output decoding circuits and passing the de-interleaving data onto a next soft output decoding circuit, said de-interleaving step being performed using a plurality of de-interleave circuits which correspond to said plurality of soft output decoding circuits.