Parallel concatenated tail-biting convolutional code and decoder therefor

• US 5,721,745 A
• Filed: 04/19/1996
• Issued: 02/24/1998
• Est. Priority Date: 04/19/1996
• Status: Expired due to Term

• Current Assignee: SES AMERICOM, Inc. (SES SA)
• Original Assignee: General Electric Company
• Inventors: Hladik, Stephen Michael, Anderson, John Bailey
• Primary Examiner(s): Baker, Stephen M.
• Application Number:
  US08/636,732
• Time in Patent Office: 676 Days
• Field of Search: 371/43, 371/44, 371/45, 371/46
• US Class Current: 714/755
• CPC Class Codes: H03M 13/2957 Turbo codes and decoding
• CPC Class Codes: H03M 13/2981 using as many component decoders as component codes
• CPC Class Codes: H03M 13/2996 Tail biting
• CPC Class Codes: H03M 13/3723 using means or methods for the initialisation of the decoder
• CPC Class Codes: H03M 13/3905 Maximum a posteriori probability [MAP] decoding or approximations thereof based on trellis or lattice decoding, e.g. forward-backward algorithm, log-MAP decoding, max-log-MAP decoding
• CPC Class Codes: H04L 1/0066 Parallel concatenated codes
• CPC Class Codes: H04L 1/0068 by puncturing

Abstract

A parallel concatenated convolutional coding scheme utilizes tail-biting nonrecursive systematic convolutional codes. The associated decoder iteratively utilizes circular maximum a posteriori decoding to produce hard and soft decision outputs. This encoding/decoding system results in improved error-correction performance for short messages.

Claims

1. A method for parallel concatenated convolutional encoding, comprising the steps of:

providing a block of data bits to a parallel concatenated encoder comprising a plurality of N component encoders and N-1 interleavers connected in a parallel concatenation;

encoding the block of data bits in a first one of the component encoders by applying a tail-biting nonrecursive systematic convolutional code thereto and thereby generating a corresponding first component codeword comprising the data bits and parity bits;

interleaving the block of data bits to provide a permuted block of data bits;

encoding the resulting permuted block of data bits in a subsequent component encoder by applying a tail-biting nonrecursive systematic convolutional code thereto, and thereby generating a corresponding second component codeword comprising the data bits and parity bits;

repeating the steps of interleaving and encoding the resulting permuted block of data bits through the remaining N-2 interleavers and the remaining N-2 component encoders, and thereby generating component codewords comprising the data bits and parity bits; and

formatting the bits of the component codewords to provide a composite codeword.

2. The method of claim 1 wherein the formatting step is performed such that the composite codeword includes only one occurrence of each bit in the block of data bits.

3. The method of claim 1 wherein the formatting step is performed such that the composite codeword includes only selected ones of the bits comprising the component codewords according to a predetermined pattern.

4. A method for decoding parallel concatenated convolutional codes, comprising the steps of:

receiving from a channel a composite codeword that comprises a formatted collection of bits from a plurality (N) of component codewords that have been generated by applying tail-biting nonrecursive systematic convolutional codes to a block of data bits in a parallel concatenated encoder, forming received component codewords from the received composite codeword, each respective received component codeword being received by a corresponding one of a plurality of N component decoders of a composite decoder, each respective component decoder also receiving a set of a priori soft-decision information for vales of the data bits;

decoding the received component codewords by a process of iterations through the N component decoders and N-1 interleavers to provide soft-decision outputs from the composite decoder, the N component decoders each providing soft-decision information on each data bit in the data block in the order encoded by the corresponding component encoder, the N-1 interleavers each interleaving the soft-decision information from a preceding component decoder to provide a permuted block of soft information to a subsequent component decoder, the set of a priori soft-decision information for the first of the N component decoders being calculated assuming that the data bits'"'"' values are equally likely for the first iteration and thereafter comprising a first function of the soft-decision information, which first function of the soft-decision information is fed back from the N^th component decoder via a first deinterleaver comprising N-1 deinterleavers corresponding to the N-1 interleavers, the N-1 deinterleavers of the first deinterleaver being applied in reverse order to the N-1 interleavers, the set of a priori soft-decision information provided to each other component decoder comprising the first function of the soft-decision information from the previous sequential component decoder; and

deinterleaving in a second deinterleaver to provide a second function of the soft-decision output from the N^th component decoder as the composite decoder'"'"'s soft-decision output using N-1 deinterleavers corresponding to the N-1 interleavers, the N-1 deinterleavers of the second deinterleaver being applied in reverse order to the N-1 interleavers.

5. The method of claim 4 wherein the number of iterations through the component decoders, interleavers and deinterleavers is a predetermined number.

6. The method of claim 4 wherein the iterations through the component decoders, interleavers and deinterleavers continues until decoder convergence is detected if the number of iterations is less than a maximum number;

otherwise decoding terminates after the maximum number of iterations, and the composite decoder provides the second function of soft-decision outputs from the N^th component decoder as its soft-decision output via the second deinterleaver.

7. The method of claim 4, further comprising the step of implementing a decision rule to provide hard-decision outputs as a function of the composite decoder'"'"'s soft-decision output.

8. The method of claim 4 wherein the formatted collection of bits has been punctured according to a predetermined pattern, the method for decoding further comprising the step of inserting neutral values for all punctured bits when forming the received component codewords.

9. The method of claim 4 wherein the decoding step is performed by the N component decoders comprising circular MAP decoders, the decoding step comprising solving an eigenvector problem.

10. The method of claim 4 wherein the decoding step is performed by the N component decoders comprising circular MAP decoders, the decoding step comprising a recursion method.

11. A method for encoding and decoding parallel concatenated convolutional codes, comprising the steps of:

providing a block of data bits to a parallel concatenated encoder comprising a plurality of N component encoders and N-1 interleavers connected in a parallel concatenation;

encoding the block of data bits in a first one of the component encoders by applying a tail-biting nonrecursive systematic convolutional code thereto and thereby generating a corresponding first component codeword comprising the data bits and parity bits;

interleaving the block of data bits to provide a permuted block of data bits;

encoding the resulting permuted block of data bits in a subsequent component encoder by applying a tail-biting nonrecursive systematic convolutional code thereto and thereby generating a corresponding second component codeword comprising the data bits and parity bits;

repeating the steps of interleaving and encoding the resulting permuted block of data bits through the remaining N-2 interleavers and the remaining N-2 component encoders, and thereby generating component codewords comprising the data bits and parity bits;

formatting the bits of the component codewords to provide a composite codeword;

inputting the composite codeword to a channel;

receiving a received composite codeword from a channel;

forming received component codewords from the received composite codeword

providing each respective received component codeword to a corresponding one of a plurality of N component decoders of a composite decoder, each respective component decoder also receiving a set of a priori probabilities for values of the data bits;

decoding the received component codewords by a process of iterations through the N component decoders and N-1 interleavers to provide soft-decision outputs from the composite decoder, the N component decoders each providing soft-decision information on each data bit in the data block in the order encoded by the corresponding component encoder, the N-1 interleavers each interleaving the soft-decision information from a preceding component decoder to provide a permuted block of soft information to a subsequent component decoder, the set of a priori soft-decision information for the first of the N component decoders being calculated assuming that the data bits'"'"' values are equally likely for the first iteration and thereafter comprising a first function of the soft-decision information, which first function of the soft-decision information is fed back from the N^th decoder via a first deinterleaver comprising N-1 deinterleavers corresponding to the N-1 interleavers, the N-1 deinterleavers of the first deinterleaver being applied in reverse order to the N-1 interleavers, the set of a priori soft-decision information provided to each other component decoder comprising the first function of the soft-decision information from the previous sequential component decoder; and

deinterleaving in a second deinterleaver to provide a second function of the soft-decision output from the N^th component decoder as the composite decoder'"'"'s soft-decision output using N-1 deinterleavers corresponding to the N-1 interleavers, the N-1 deinterleavers of the second deinterleaver being applied in reverse order to the N-1 interleavers.

12. The method of claim 11 wherein the formatting step is performed such that the composite codeword includes only one occurrence of each bit in the block of data bits.

13. The method of claim 11 wherein the formatting step is performed such that the composite codeword includes only selected ones of the bits comprising the component codewords according to a predetermined pattern.

14. The method of claim 11 wherein the ,number of iterations through the component decoders, interleavers and deinterleavers is a predetermined number.

15. The method of claim 11 wherein the iterations through the component decoders, N-1 interleavers and deinterleavers continues until decoder convergence is detected if the number of iterations is less than a maximum number;

otherwise decoding terminates after the maximum number of iterations, and the composite decoder provides the second function of soft-decision outputs from the N^th component decoder as its soft-decision output via the second deinterleaver.

16. The method of claim 11, further comprising the step of implementing a decision rule to provide hard-decision outputs as a function of the composite decoder'"'"'s soft-decision output.

17. The method of claim 11 wherein the decoding step is performed by the N component decoders comprising circular MAP decoders, the decoding step comprising solving an eigenvector problem.

18. The method of claim 11 wherein the decoding step is performed by the N component decoders comprising circular MAP decoders, the decoding step comprising a recursion method.

19. The method of claim 11 wherein the formatting step further comprises puncturing selected ones of the bits from the component codewords which comprise the composite codeword according to a predetermined pattern, the method for decoding further comprising the step of inserting neutral values for all punctured bits when forming the received component codewords.

20. A parallel concatenated encoder, comprising:

a plurality (N) of component encoders and a plurality (N-1) of interleavers connected in a parallel concatenation for systematically applying tail-biting nonrecursive systematic convolutional codes to a block of data bits and various permutations of the block of data bits, and thereby generating component codewords comprising the data bits and parity bits; and

a composite codeword formatter for formatting the collection of bits from the component codewords to provide a composite codeword.

21. The encoder of claim 20 wherein the composite codeword formatter produces the composite codeword such that it includes only one occurrence of each bit in the block of data bits.

22. The encoder of claim 20 wherein the composite codeword produces the composite codeword such that it includes only selected ones of the bits comprising the component codewords according to a predetermined pattern.

23. A composite decoder for decoding parallel concatenated convolutional codes, comprising:

a composite-codeword-to-component-codeword converter for receiving a composite codeword from a channel, the composite codeword comprising selected bits of a plurality of N component codewords that have been generated by applying tail-biting nonrecursive convolutional codes to a block of data bits in a parallel concatenated encoder, and forming a plurality of N corresponding received component codewords therefrom;

a plurality (N) of component decoders, each respective decoder receiving a corresponding received component codeword from the composite-codeword-to-component-codeword converter, each respective decoder also receiving a set of a priori soft-decision information for values of the data bits, the N component decoders each providing soft-decision information on each data bit in the data block in the order encoded by a corresponding component encoder in the parallel concatenated encoder;

a plurality of N-1 interleavers, each respective interleaver interleaving the soft-decision information from a corresponding component decoder to provide a permuted block of soft information to a subsequent component decoder, the received codewords being decoded by a process of iterations through the N component decoders and N-1 interleavers to provide soft-decision output from the composite decoder;

,

a first deinterleaver comprising N-1 deinterleavers corresponding to the N-1 interleavers, the N-1 deinterleavers of the first deinterleaver being applied in reverse order to the N-1 interleavers, the set of a priori soft-decision information for the first of the N component decoders being calculated assuming that the data bits'"'"' values are equally likely for the first iteration and thereafter comprising a first function of the soft-decision information, which first function of the soft-decision information is outputted by the N^th decoder and fed back via the first deinterleaver, the set of a priori soft-decision information provided to each other component decoder comprising the first function of the soft-decision information from the previous sequential component decoder; and

a second deinterleaver comprising N-1 deinterleavers corresponding to the N-1 interleavers, the N-1 deinterleavers of the second deinterleaver being applied in reverse order to the N-1 interleavers, the second deinterleaver deinterleaving a second function of the soft-decision output from the N^th component decoder to provide the composite decoder'"'"'s soft-decision output.

24. The decoder of claim 23 wherein the number of iterations through the component decoders, interleavers and deinterleavers is a predetermined number.

25. The decoder of claim 23 wherein the iterations through the component decoders, interleavers and deinterleavers continues until decoder convergence is detected if the number of iterations is less than a maximum number;

otherwise decoding terminates after the maximum number of iterations, and the composite decoder provides the second function of soft-decision outputs from the N^th component decoder as its soft-decision output via the second deinterleaver.

26. The decoder of claim 23, further comprising a decision device for implementing a decision rule to provide hard-decision outputs as a function of the composite decoder'"'"'s soft-decision output.

27. The decoder of claim 23 wherein the N component decoders comprise circular MAP decoders which decode by solving an eigenvector problem.

28. The decoder of claim 23 wherein the N component decoders comprise circular MAP decoders which decode by using a recursion method.

29. An encoder and decoder system for encoding and decoding parallel concatenated convolutional codes, comprising:

a parallel concatenated encoder comprising a plurality (N) of component encoders and a plurality (N-1) of encoder interleavers connected in a parallel concatenation for systematically applying tail-biting nonrecursive systematic convolutional codes to a block of data bits and various permutations of the block of data bits, and thereby generating component codewords comprising the data bits and parity bits; and

a composite codeword formatter for formatting the collection of bits from the component codewords to provide a composite codeword;

a composite-codeword-to-component-codeword converter for receiving the composite codeword from a channel and forming a plurality of N corresponding received component codewords therefrom;

a plurality (N) of component decoders, each respective decoder receiving a corresponding received component codeword from the composite-codeword-to-component-codeword converter, each respective decoder also receiving a set of a priori soft-decision information for values of the data bits, the N component decoders each providing soft-decision information on each data bit in the data block in the order encoded by a corresponding component encoder in the parallel concatenated encoder;

a plurality of N-1 interleavers, each respective interleaver interleaving the soft-decision information from a corresponding component decoder to provide a permuted block of soft information to a subsequent component decoder, the received codewords being decoded by a process of iterations through the N component decoders and N-1 interleavers to provide soft-decision output from the composite decoder;

a first deinterleaver comprising N-1 deinterleavers corresponding to the N-1 interleavers, the N-1 deinterleavers of the first deinterleaver being applied in reverse order to the N-1 interleavers, the set of a priori soft-decision information for the first of the N component decoders being calculated assuming that the data bits'"'"' values are equally likely for the first iteration and thereafter comprising a first function of the soft-decision information, which first function of the soft-decision information is outputted by the N^th decoder and fed back via the first deinterleaver, the set of a priori soft-decision information provided to each other component decoder comprising the first function of the soft-decision information from the previous sequential component decoder; and

a second deinterleaver comprising N-1 deinterleavers corresponding to the N-1 interleavers, the N-1 deinterleavers of the second deinterleaver being applied in reverse order to the N-1 interleavers, the second deinterleaver deinterleaving a second function of the soft-decision output from the N^th component decoder to provide the composite decoder'"'"'s soft-decision output.

30. The encoder and decoder system of claim 29 wherein the composite codeword formatter produces the composite codeword such that it includes only one occurrence of each bit in the block of data bits.

31. The encoder and decoder system of claim 29 wherein the composite codeword produces the composite codeword such that it includes only selected ones of the bits comprising the component codewords according to a predetermined pattern.

32. The encoder and decoder system of claim 29 wherein the number of iterations through the component decoders, interleavers and deinterleavers is a predetermined number.

33. The encoder and decoder system of claim 29 wherein the iterations through the component decoders, interleavers and deinterleavers continues until decoder convergence is detected if the number of iterations is less than a maximum number;

otherwise decoding terminates after the maximum number of iterations, and the composite decoder provides the second function of soft-decision outputs from the N^th component decoder as its soft-decision output via the second deinterleaver.

34. The encoder and decoder system of claim 29, further comprising a decision device for implementing a decision role to provide hard-decision outputs as a function of the decoders soft-decision output.

35. The encoder and decoder system of claim 29 wherein the N component decoders comprise circular MAP decoders which decode by solving an eigenvector problem.

36. The encoder and decoder system of claim 29 wherein the N component decoders comprise circular MAP decoders which decode by using a recursion method.