Turbo code symbol interleaver

• US 6,351,832 B1
• Filed: 04/28/2000
• Issued: 02/26/2002
• Est. Priority Date: 05/28/1999
• Status: Expired due to Term

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Wei, Lee-Fang
• Primary Examiner(s): Decady, Albert
• Assistant Examiner(s): Chase, Shelly A
• Application Number:
  US09/560,728
• Time in Patent Office: 669 Days
• Field of Search: 714/701, 714/786, 714/792, 375/222
• US Class Current: 714/701
• CPC Class Codes: H03M 13/256 with trellis coding, e.g. with convolutional codes and TCM
• CPC Class Codes: H03M 13/258 with turbo codes, e.g. Turbo Trellis Coded Modulation [TTCM]
• CPC Class Codes: H03M 13/2703 the interleaver involving at least two directions
• CPC Class Codes: H03M 13/2972 Serial concatenation using convolutional component codes
• CPC Class Codes: H03M 13/2993 Implementing the return to a predetermined state, i.e. trellis termination

Abstract

Advantageous error rate performance, high bandwidth efficiency, low delay and reduced error floor are achieved at an acceptable level of decoding complexity via the use of serial concatenated turbo codes. These are codes for which at least some of the output bits, including at least one redundant bit, provided by a first, outer encoder are, after interleaving, further processed by a second, inner encoder. The interleaver uses as its interleaved elements the bits associated with a particular symbol interval. The resulting data and redundant bits then select a symbol from a predetermined constellation for transmission. In the receiver, the turbo code is decoded using a corresponding number of soft output decoders which operates iteratively in such a way that improved performance as compared to a single encoding can be achieved. The turbo codes can be of various dimensionalities and can be used as a component of a multilevel code to achieve a desired level of bandwidth efficiency.

Claims

1. A method for operation of an interleaver in an arrangement comprising first and second redundancy encoders, said method comprising the steps, performed during successive symbol intervals, of:

receiving encoded bits from said first redundancy encoder, said encoded bits associated with a particular one of said symbol intervals;

receiving remaining bits associated with said particular symbol interval;

storing, as a group, said encoded bits from said first redundancy encoder; and

outputting stored groups of bits in an order different from the order in which they were stored, at least a portion of each of said outputted groups of bits being provided to said second redundancy encoder; and

wherein the step of storing comprises storing, as a group, said remaining bits along with said encoded bits from said first redundancy encoder.

2. The method of claim 1 further comprising the step of:

storing n groups of bits as an interleaving frame.

3. The method of claim 2 wherein:

said first redundancy encoder uses a first redundancy code having a first decoding depth and said second redundancy encoder uses a second redundancy code having a second decoding depth;

J is a function of said second decoding depth and K is a function of said first decoding depth; and

4. The method of claim 3 wherein said groups are stored organized as a matrix having J rows and K columns.

5. The method of claim 1 wherein said groups of bits are stored organized as a matrix having J rows and K columns.

6. The method of claim 5 further comprising the step of:

storing successive bit groups in each row separated by K₁ columns.

7. The method of claim 6 wherein K₁=2.

8. The method of claim 5 further comprising the step of:

storing successive contiguous K input groups having alternating J₁ and J₁−

1 row separation.

9. The method of claim 8 wherein J₁=J/2.

10. The method of claim 5 wherein said step of outputting comprises the step of:

outputting stored groups of bits in a column-by-column sequence.

11. An interleaver comprising:

means for receiving encoded bits from a first redundancy encoder, said encoded bits associated with a particular symbol interval;

means for receiving remaining bits associated with said particular symbol interval;

means for storing, as a group, said encoded bits from said first redundancy encoder; and

means for outputting stored groups of bits in an order different from the order in which they were stored, at least a portion of each of said groups of bits being provided to said second redundancy encoder; and

wherein said means for storing comprises means for storing, as a group, said remaining bits along with said encoded bits from said first redundancy encoder.

12. The interleaver of claim 11 further comprising:

means for storing n groups of bits as an interleaving frame.

13. The interleaver of claim 12 wherein:

said first redundancy encoder uses a first redundancy code having a first decoding depth and said second redundancy encoder uses a second redundancy code having a second decoding depth;

J is a function of said second decoding depth and K is a function of said first decoding depth; and

14. The interleaver of claim 13 wherein said groups are stored organized as a matrix having J rows and K columns.

15. The interleaver of claim 11 wherein said groups are stored organized as a matrix having J rows and K columns.

16. The interleaver of claim 15 further comprising:

means for storing successive bit groups in each row separated by K₁ columns.

17. The interleaver of claim 16 wherein K₁=2.

18. The interleaver of claim 15 further comprising:

means for storing successive contiguous K input groups having alternating J₁ and J₁−

1 row separation.

19. The interleaver of claim 18 wherein J₁=J/2.

20. The interleaver of claim 15 wherein said means for outputting comprises:

means for outputting stored groups of bits in a column-by-column sequence.

21. A method for generating data symbols representing a stream of input bits, and from which said input bits can be recovered, each data symbol being generated for a respective symbol interval and being represented by at least one signal space coordinate, the method comprising the steps, performed for each symbol interval of:

encoding a predetermined number of said input bits, associated with a particular symbol interval, with a first redundancy code to generate first redundancy encoded output bits;

interleaving a group of bits on a bit-group-by-bit-group level, said group including said first redundancy encoded output bits;

encoding a predetermined number of said interleaved first redundancy encoded output bits with a second redundancy code to generate second redundancy encoded output bits; and

generating one of said data symbols as a function of a plurality of bits, said plurality of bits including any remaining ones of said interleaved first redundancy encoded output bits, said second redundancy encoded output bits, and any remaining input bits associated with said particular symbol interval.

22. The method of claim 21 wherein said first and second redundancy codes are trellis codes.

23. The method of claim 21 wherein said step of interleaving comprises:

storing n groups of bits as an interleaving frame.

24. The method of claim 23 wherein:

said first redundancy code has a first decoding depth and said second redundancy code has a second decoding depth;

J is a function of said second decoding depth and K is a function of said first decoding depth; and

25. The method of claim 24 wherein said groups of bits are stored organized as a matrix having J rows and K columns.

26. The method of claim 21 wherein said step of interleaving comprises the step of storing groups of bits organized as a matrix having J rows and K columns.

27. The method of claim 26 wherein said step of storing comprises the step of:

storing successive bit groups in each row separated by K₁ columns.

28. The method of claim 27 wherein K₁=2.

29. The method of claim 26 wherein said step of storing comprises the step of:

storing successive contiguous K groups having alternating J₁ and J₁−

1 row separation.

30. The method of claim 29 wherein J₁=J/2.

31. The method of claim 26 wherein said step of interleaving further comprises the step of:

outputting stored groups of bits in a column-by-column sequence.

32. An apparatus for generating data symbols representing a stream of input bits, and from which said input bits can be recovered, each data symbol being generated for a respective symbol interval and being represented by at least one signal space coordinate, the apparatus comprising:

a first redundancy encoder adapted to encode a predetermined number of input bits, associated with a particular symbol interval, using a first redundancy code to generate first redundancy encoder output bits;

an interleaver adapted to interleave a group of bits on a bit-group-by-bit-group level, said group including said first redundancy encoded output bits; and

a second redundancy encoder adapted to encode a predetermined number of said interleaved first redundancy encoder output bits using a second redundancy code to generate second redundancy encoder output bits; and

a mapper adapted to select a data symbol from a predetermined signal constellation as a function of a plurality of bits, said plurality of bits including any remaining ones of said interleaved first redundancy encoder output bits, said second redundancy encoder output bits, and any remaining input bits associated with said particular symbol interval.

33. The apparatus of claim 32 wherein said first and second redundancy encoders are trellis encoders.

34. The apparatus of claim 32 wherein said interleaver stores n groups of bits as an interleaving frame.

35. The apparatus of claim 34 wherein:

said first redundancy code has a first decoding depth and said second redundancy code has a second decoding depth;

J is a function of said second decoding depth and K is a function of said first decoding depth; and

36. The apparatus of claim 35 wherein said groups of bits are stored organized as a matrix having J rows and K columns.

37. The apparatus of claim 32 wherein said interleaver stores groups of bits organized as a matrix having J rows and K columns.

38. The apparatus of claim 37 wherein said interleaver stores successive bit groups in each row separated by K₁ columns.

39. The apparatus of claim 38 wherein K₁32 2.

40. The apparatus of claim 37 wherein said interleaver stores successive contiguous K groups having alternating J₁ and J₁−

1 row separation.

41. The apparatus of claim 40 wherein J₁=J/2.

42. The apparatus of claim 37 wherein said interleaver outputs stored groups of bits in a column-by-column sequence.

43. A method comprising the steps of:

encoding at least ones of a sequence of input bit groups using a first redundancy code to generate expanded groups of first redundancy encoded output bits;

interleaving said expanded groups of first redundancy encoded output bits on a bit-group-by-bit-group basis;

encoding a predetermined number of said interleaved first redundancy encoded output bits using a second redundancy code to generate an expanded group of second redundancy encoded output bits; and

selecting a data symbol from a predetermined signal constellation as a function of a plurality of bits, said plurality of bits including any remaining ones of said interleaved first redundancy encoded output bits and said second redundancy encoded output bits.

44. The method of claim 43 wherein said first and second redundancy codes are trellis codes.

45. The method of claim 43 wherein said step of interleaving comprises:

storing n expanded groups of first redundancy encoded output bits as an interleaving frame.

46. The method of claim 45 wherein:

said first redundancy code has a first decoding depth and said second redundancy code has a second decoding depth;

J is a function of said second decoding depth and K is a function of said first decoding depth; and

47. The method of claim 46 wherein said expanded groups of first redundancy encoded output bits are stored organized as a matrix having J rows and K columns.

48. The method of claim 43 wherein said step of interleaving comprises the step of:

storing expanded groups of first redundancy encoded output bits organized as a matrix having J rows and K columns.

49. The method of claim 48 wherein said step of interleaving further comprises the step of:

storing successive expanded groups of first redundancy encoded output bits in each row separated by K₁ columns.

50. The method of claim 49 wherein K₁=2.

51. The method of claim 48 wherein said step of interleaving further comprises the step of:

storing successive contiguous K expanded groups of first redundancy encoded output bits having alternating J₁ and J₁−

1 row separation.

52. The method of claim 51 wherein J₁=J/2.

53. The method of claim 48 wherein said step of interleaving further comprises the step of outputting stored groups of bits in a column-by-column sequence.

54. Apparatus comprising:

a first redundancy encoder adapted to encode at least ones of a sequence of input bit groups using a first redundancy code to generate expanded groups of first redundancy encoder output bits;

an interleaver adapted to interleave said expanded groups of first redundancy encoder output bits on a bit-group-by-bit-group basis;

a second redundancy encoder adapted to encode a predetermined number of said interleaved first redundancy encoder output bits using a second redundancy code to generate an expanded group of second redundancy encoder output bits; and

a mapper adapted to select a data symbol from a predetermined signal constellation as a function of a plurality of bits, said plurality of bits including any remaining ones of said interleaved first redundancy encoder output bits and said second redundancy encoder output bits.

55. The apparatus of claim 54 wherein said first and second redundancy encoders are trellis encoders.

56. The apparatus of claim 54 wherein said interleaver stores n expanded groups of first redundancy encoder output bits as an interleaving frame.

57. The apparatus of claim 56 wherein:

said first redundancy code has a first decoding depth and said second redundancy code has a second decoding depth;

J is a function of said second decoding depth and K is a function of said first decoding depth; and

58. The apparatus of claim 57 wherein said expanded groups of first redundancy encoder output bits are stored organized as a matrix having J rows and K columns.

59. The apparatus of claim 54 wherein said interleaver stores expanded groups of first redundancy encoder output bits organized as a matrix having J rows and K columns.

60. The apparatus of claim 59 wherein said interleaver stores successive expanded groups of first redundancy encoder output bits in each row separated by K₁ columns.

61. The apparatus of claim 60 wherein K₁=2.

62. The apparatus of claim 59 wherein said interleaver stores successive contiguous K expanded groups of first redundancy encoder output bits having alternating J₁ and J₁−

1 row separation.

63. The apparatus of claim 62 wherein J₁=J/2.

64. The apparatus of claim 59, wherein said interleaver outputs stored expanded groups of first redundancy encoder output bits in a column-by-column sequence.