Method and apparatus for encoding and decoding a turbo code in an integrated modem system

• US 6,484,283 B2
• Filed: 12/30/1998
• Issued: 11/19/2002
• Est. Priority Date: 12/30/1998
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Cromwell, Jonathan, Stephen, Karen J., Lam, Hon W.
• Primary Examiner(s): Decady, Albert
• Assistant Examiner(s): Torres, Joseph D.
• Application Number:
  US09/223,473
• Publication Number:
  US 20020029362A1
• Time in Patent Office: 1,420 Days
• Field of Search: 714/786
• US Class Current: 714/786
• CPC Class Codes: H03M 13/258 with turbo codes, e.g. Turbo Trellis Coded Modulation [TTCM]
• CPC Class Codes: H03M 13/2746 S-random interleaver
• CPC Class Codes: H03M 13/2957 Turbo codes and decoding
• CPC Class Codes: H03M 13/333 Synchronisation on a multi-bit block basis, e.g. frame synchronisation
• CPC Class Codes: H03M 13/3911 Correction factor, e.g. approximations of the exp(1+x) function
• CPC Class Codes: H03M 13/3922 Add-Compare-Select [ACS] operation in forward or backward recursions
• CPC Class Codes: H03M 13/3927 Log-Likelihood Ratio [LLR] computation by combination of forward and backward metrics into LLRs
• CPC Class Codes: H03M 13/3972 using sliding window techniques or parallel windows
• CPC Class Codes: H03M 13/3988 for rate k/n convolutional codes, with k>1, obtained by convolutional encoders with k inputs and n outputs
• CPC Class Codes: H03M 13/6563 Implementations using multi-port memories
• CPC Class Codes: H04L 1/0043 Realisations of complexity reduction techniques, e.g. use of look-up tables
• CPC Class Codes: H04L 1/005 Iterative decoding, including iteration between signal detection and decoding operation
• CPC Class Codes: H04L 1/0052 Realisations of complexity reduction techniques, e.g. pipelining or use of look-up tables
• CPC Class Codes: H04L 1/0066 Parallel concatenated codes

Abstract

The present invention is a method and apparatus for encoding and decoding a turbo code. In the encoder, an interleaver interleaves and delays a block of input bits to generate interleaved input bits and delayed input bits. A first encoder generates a first, second, and third encoded bits. A second encoder generates a fourth encoded bit. A symbol generator generates a plurality of symbols which correspond to the input bits. In a decoder, a sync search engine detects a synchronizing pattern and extracts symbols from the encoded bits. An input buffer is coupled to the sync search engine to store the extracted symbols. A first soft-in-soft-out (SISO1) is coupled to the input buffer to generate a first soft decision set based on the extracted symbols. An interleaver is coupled to the SISO1 to interleave the first soft decision set. A second soft-in-soft-out (SISO2) is coupled to the input buffer and the interleaver to generate a second soft decision set. A de-interleaver is coupled to the SISO2 to de-interleave the second soft decision set. An adder is coupled to the SISO1 and the de-interleaver to generate a hard decision set.

Claims

1. An apparatus comprising:

an interleaver to interleave and delay a block of input bits, the interleaver generating interleaved input bits and delayed input bits;

a serial-to-parallel converter coupled to the interleaver to pair consecutive bits of one of the interleaved and delayed input bits;

a first encoder coupled to the serial-to-parallel converter to generate a first, second, and third encoded bits from the paired bits;

a second encoder coupled to the serial-to-parallel converter to generate a fourth encoded bit; and

a symbol generator coupled to the first and second rate encoders to generate a plurality of symbols, the symbols corresponding to combinations of input bits.

2. The apparatus of claim 1 wherein the interleaver comprises:

an interleaver memory to provide the interleaved input bits and the delayed input bits;

a counter coupled to the interleaver memory to generate addresses to the interleaver memory; and

a look-up table (LUT) memory coupled to the counter to generate a random address to the interleaver memory.

3. The apparatus of claim 2 wherein the interleaver further comprises:

a multiplexer coupled to the interleaver memory to select the delayed input bits and the interleaved input bits; and

a latch circuit coupled to the multiplexer to latch the delayed input bits and the interleaved input bits.

4. The apparatus of claim 1 wherein the delayed input bits include a first delayed bit (su1), a second delayed bit (su2) and the interleaved input bits include a first interleaved input bit (su1′

) and a second interleaved input bit (su2′

).

5. The apparatus of claim 4 wherein two consecutive input bits are paired to generate parallel bits in a same clock cycle.

6. The apparatus of claim 5 wherein the parallel bits include a first parallel delayed bit (pu1), a second parallel delayed bit (pu2), a first parallel interleaved bit (pu1′

), and a second parallel interleaved bit (pu2′

), the pu1, pu2, pu1′

, and pu2′

bits corresponding to the su1, su2, su1′

, and su2′

bits, respectively, the pu1 and pu2 bits forming a delayed bit pair, the pu1′ and

pu2′

bits forming an interleaved bit pair.

7. The apparatus of claim 6 wherein the first and second encoders are rate ⅔

systematic recursive convolutional.

8. The apparatus of claim 7 wherein the first encoder comprises a state machine coupled to receive the delayed bit pair, the state machine having four states s0, s1, s2, and s3, the state machine generating four next states ns0, ns1, ns2, and ns3.

9. The apparatus of claim 8 wherein the four next states are generated from the four states and the delayed bit pair according to four state equations ns0 =s2+s1+pu1, ns1=s0, ns2=s3+s2+s1+pu2, and ns3=s2, respectively.

10. The apparatus of claim 9 wherein the first, second, and third encoded bits are generated as pu1, pu2, and s0+pu2+pu1, respectively.

11. The apparatus of claim 7 wherein the second encoder comprises a state machine coupled to receive the interleaved bit pair, the state machine having four states s0, s1, s2, and s3, the state machine generating four next states ns0, ns1, ns2, and ns3.

12. The apparatus of claim 11 wherein the four next states are generated from the four states and the interleaved bit pair according to four state equations ns0=s2+s1+pu1′

, ns1=s0, ns2=s3+s2+s1+pu2′

, and ns3=s2, respectively.

13. The apparatus of claim 12 wherein the fourth encoded bit is generated as s0+pu2′

+pu1′

.

14. The apparatus of claim 13 wherein the symbol generator combines the encoded bits to form the symbols which include an Inphase (I) symbol and a quadrature (Q) symbol.

15. The apparatus of claim 14 wherein the I symbol includes the first and second encoded bits and the Q symbol includes the third and fourth encoded bits, the first and third encoded bits appearing first in time, the second and fourth encoded bits appearing second in time.

16. A system comprising:

an encoder to receive a stream of input bits to generate encoded bits from the input bits, the encoded bits forming an Inphase (I) and quadrature (Q) symbols the encoder comprising an interleaver to interleave and delay the input bits, and a serial-to-parallel converter to pair consecutive bits of one of the interleaved and delayed input bits;

a sync inserter coupled to the encoder to insert synchronizing pattern into the encoded bits, the sync inserter generating output bits; and

a latch and routing circuit coupled to the encoder and the sync inserter to latch the input and output bits and to route signal paths bypassing the encoder and the sync inserter.

17. The system of claim 16 further comprising a control and bus interface coupled to the encoder, the sync inserter, and the latch and routing circuit, to generate control signals.

18. The system of claim 16 wherein the sync inserter comprises:

a frame counter to keep track of a frame number, the frame counter being cleared when the frame number reaches a predetermined frame count;

a bit counter to keep track of a bit number, the bit counter being cleared when the bit number reaches a predetermined bit count; and

a look up table (LUT) coupled to the bit counter to generate the synchronizing pattern according to the bit number.

19. The system of claim 18 wherein the LUT stores Inphase (I) and quadrature (Q) synchronizing patterns.

20. The system of claim 18 wherein the sync inserter selects the encoded bits when the synchronizing pattern is not generated.

21. An apparatus comprising:

a sync search engine coupled to receive channel symbols representing a plurality of encoded bits to detect a synchronizing pattern using search, trial lock, and lock states, the sync search engine extracting code symbols from the channel symbols;

an input buffer coupled to the sync search engine to store the extracted code symbols;

a first soft-in-soft-out (SISO1) coupled to the input buffer to generate a first soft decision set based on the extracted code symbols;

an interleaver coupled to the SISO1 to interleave the first soft decision set;

a second soft-in-soft-out (SISO2) coupled to the input buffer and the interleaver to generate a second soft decision set;

a de-interleaver coupled to the SISO2 to de-interleave the second soft decision set; and

an adder coupled to the SISO1 and the de-interleaver to generate a hard decision set.

22. The apparatus of claim 21 wherein the sync search engine comprises correlators, each of the correlators generating a correlator score based on a detection of the synchronizing pattern in a different phase orientation.

23. The apparatus of claim 22 wherein the sync search engine produces a final score based on the correlator scores generated by the correlators.

24. The apparatus of claim 23 wherein the synchronizing pattern is detected when the final score exceeds a predetermined threshold.

25. The apparatus of claim 21 wherein the input buffer comprises:

a first port to receive the extracted code symbols;

a second port coupled to the SISO1 to transmit the stored code symbols to the SISO1; and

a third port coupled to the SISO2 to transmit the stored code symbols to the SISO2.

26. The apparatus of claim 21 wherein each of the SISO1 and SISO2 comprises:

a symbol scratchpad coupled to the input buffer to store at least three sets of extracted code symbols, each set having Nb1 extracted code symbols;

a first trellis unit coupled to the input buffer to perform an initial traceback operation, the first trellis unit generating a first traceback result;

a second trellis unit coupled to the symbol scratchpad and the first trellis unit to perform a full traceback operation, the second trellis unit generating a second traceback result;

a third trellis unit coupled to the symbol scratchpad to perform a traceforward operation, the third trellis unit generating a traceforward result;

a state scratchpad coupled to the second trellis unit to store the second traceback result at a rate of Nbl symbols at a time;

an extrinsic information calculator coupled to the symbol scratchpad, the state scratchpad, and the third trellis unit to compute an extrinsic information.

27. The apparatus of claim 26 wherein each of the first, second, and third trellis units comprises:

a branch metric calculator to calculate a branch metric; and

a plurality of add-compare-select (ACS) units connected according to a code topology, each of the ACS units performing a four-way min* function.

28. The apparatus of claim 27 wherein extracted symbols include first, second, third, and fourth encoded bits.

29. The apparatus of claim 26 wherein the SISO1 receives the first, second, and third encoded bits and the SISO2 receives the fourth encoded bit.

30. The apparatus of claim 21 wherein the interleaver and de-interleaver are combined into a single unit comprising three planes of memory, each of the three planes of memory storing N extrinsic information symbols.

31. A method comprising:

detecting a synchronizing pattern by a sync search engine using search, trial lock, and lock states, the sync search engine extracting code symbols from channel symbols representing a plurality of encoded bits;

storing the extracted code symbols in an input buffer;

generating a first soft decision set based on the extracted code symbols by a first soft-in-soft-out (SISO1);

interleaving the first soft decision set by an interleaver;

generating a second soft decision set by a second soft-in-soft-out (SISO2);

de-interleaving the second soft decision set by a de-interleaver; and

generating a hard decision set by an adder.

32. The method of claim 31 wherein detecting a synchronizing pattern comprises generating a correlator score based on a detection of the synchronizing pattern by a plurality of correlators.

33. The method of claim 32 wherein detecting a synchronizing pattern further comprising producing a final score based on the correlator scores generated by the correlators.

34. The method of claim 33 wherein the synchronizing pattern is detected when the final score exceeds a predetermined threshold.

35. The method of claim 31 wherein storing the extracted code symbols comprises:

receiving the extracted code symbols by a first port;

transmitting the stored code symbols to the SISO1 by a second port; and

transmitting the stored code symbols to the SISO2 by a third port.

36. The method of claim 31 wherein generating one of the first and second soft decision sets comprises:

storing at least three sets of extracted code symbols in a symbol scratchpad, each set having Nbl extracted code symbols;

performing an initial traceback operation by a first trellis unit, the first trellis unit generating a first traceback result;

performing a full traceback operation by a second trellis unit, the second trellis unit generating a second traceback result;

performing a traceforward operation by a third trellis unit, the third trellis unit generating a traceforward result;

storing the second traceback result in a state scratchpad at a rate of Nbl symbols at a time; and

computing an extrinsic information by an extrinsic information calculator.

37. The method of claim 36 wherein each of performing an initial traceback, a full traceback, and a traceforward operations comprises:

calculating a branch metric by a branch metric calculator; and

performing a four-way min* function by each of a plurality of add-compare-select (ACS) units, the ACS units being connected according to a code topology.

38. The method of claim 37 wherein extracted code symbols include first, second, third, and fourth encoded bits.

39. The method of claim 36 wherein the SISO1 receives the first, second, and third encoded bits and the SISO2 receives the fourth encoded bit.

40. The method of claim 36 wherein the interleaver and de-interleaver are combined into a single unit comprising three planes of memory, each of the three planes of memory storing N extrinsic information symbols.

41. A system comprising:

an encoder to encode input bits using a turbo code, the encoder comprising;

an interleaver to interleave and delay a block of the input bits, the interleaver generating interleaved input bits and delayed input bits,

a serial-to-parallel converter coupled to the interleaver to pair consecutive bits of one of the interleaved and delayed input bits;

a first encoder coupled to the serial-to-parallel converter to generate a first, second, and third encoded bits from the paired bits,

a second encoder coupled to the serial-to-parallel converter to generate a fourth encoded bit from the paired bits, and

a symbol generator coupled to the first and second rate encoders to generate a plurality of symbols, the symbols corresponding to combinations of input bits; and

a modulator coupled to the encoder to modulate the plurality of symbols, the modulator generating encoded bits corresponding to the plurality of symbols.

42. The system of claim 41 wherein the interleaver comprises:

an interleaver memory to provide the interleaved input bits and the delayed input bits;

a counter coupled to the interleaver memory to generate addresses to the interleaver memory; and

a look-up table (LUT) memory coupled to the counter to generate a random address to the interleaver memory.

43. The system of claim 42 wherein the interleaver further comprises:

a multiplexer coupled to the interleaver memory to select the delayed input bits and the interleaved input bits; and

a latch circuit coupled to the multiplexer to latch the delayed input bits and the interleaved input bits.

44. The system of claim 41 wherein the delayed input bits include a first delayed bit (su1), a second delayed bit (su2) and the interleaved input bits include a first interleaved input bit (su1′

) and a second interleaved input bit (su2′

).

45. The system of claim 44 wherein two consecutive input bits are paired to generate parallel bits in a same clock cycle.

46. The system of claim 45 wherein the parallel bits include a first parallel delayed bit (pu1), a second parallel delayed bit (pu2), a first parallel interleaved bit (pu1′

), and a second parallel interleaved bit (pu2′

), the pu1, pu2, pu1′

, and pu2′

bits corresponding to the su1, su2, su1′

, and su2′

bits, respectively, the pu1 and pu2 bits forming a delayed bit pair, the pu1′ and

pu2′

bits forming an interleaved bit pair.

47. The system of claim 46 wherein the first and second encoders are rate ⅔

systematic recursive convolutional.

48. The system of claim 47 wherein the first encoder comprises a state machine coupled to receive the delayed bit pair, the state machine having four states s0, s1, s2, and s3, the state machine generating four next states ns0, ns1, ns2, and ns3.

49. The system of claim 48 wherein the four next states are generated from the four states and the delayed bit pair according to four state equations ns0=s2+s1+pu1, ns1=s0, ns2=s3+s2+s2+pu2, and ns3=s2, respectively.

50. The system of claim 49 wherein the first, second, and third encoded bits are generated as pu1, pu2, and s0+pu2+pu1, respectively.

51. The system of claim 47 wherein the second encoder comprises a state machine coupled to receive the interleaved bit pair, the state machine having four states s0, s1, s2, and s3, the state machine generating four next states ns0, ns1, ns2, and ns3.

52. The system of claim 51 wherein the four next states are generated from the four states and the interleaved bit pair according to four state equations ns0=s2+s1+pu1′

, ns1=s0, ns2=s3+s2+s1+pu2′

, and ns3=s2, respectively.

53. The system of claim 52 wherein the fourth encoded bit is generated as s0+pu2′

+pu1′

.

54. The system of claim 53 wherein the symbol generator combines the encoded bits to form the symbols which include an Inphase (I) symbol and a quadrature (Q) symbol.

55. The system of claim 54 wherein the I symbol includes the first and second encoded bits and the Q symbol includes the third and fourth encoded bits, the first and third encoded bits appearing first in time, the second and fourth encoded bits appearing second in time.

56. A system comprising:

a demodulator to demodulate a stream of encoded bits, the demodulator generating channel symbols representing the encoded bits; and

a decoder coupled to the demodulator to decode the channel symbols, the decoder comprising;

a sync search engine coupled to receive the channel symbols to detect a synchronizing pattern using search, trial lock, and lock, the sync search engine extracting code symbols from the channel symbols,

an input buffer coupled to the sync search engine to store the extracted code symbols,

a first soft-in-soft-out (SISO1) coupled to the input buffer to generate a first soft decision set based on the extracted code symbols,

an interleaver coupled to the SISO1 to interleave the first soft decision set,

a second soft-in-soft-out (SISO2) coupled to the input buffer and the interleaver to generate a second soft decision set,

a de-interleaver coupled to the SISO2 to de-interleave the second soft decision set, and

an adder coupled to the SISO1 and the de-interleaver to generate a hard decision set.

57. The system of claim 56 wherein the sync search engine comprises correlators, each of the correlators generating a correlator score based on a detection of the synchronizing pattern in a different phase orientation.

58. The system of claim 57 wherein the sync search engine produces a final score based on the correlator scores generated by the correlators.

59. The system of claim 58 wherein the synchronizing pattern is detected when the final score exceeds a predetermined threshold.

60. The system of claim 56 wherein the input buffer comprises:

a first port to receive the extracted code symbols;

a second port coupled to the SISO1 to transmit the stored code symbols to the SISO1; and

a third port coupled to the SISO2 to transmit the stored code symbols to the SISO2.

61. The system of claim 56 wherein each of the SISO1 and SISO2 comprises:

a symbol scratchpad coupled to the input buffer to store at least three sets of extracted code symbols, each set having Nbl extracted code symbols;

a first trellis unit coupled to the input buffer to perform an initial traceback operation, the first trellis unit generating a first traceback result;

a second trellis unit coupled to the symbol scratchpad and the first trellis unit to perform a full traceback operation, the second trellis unit generating a second traceback result;

a third trellis unit coupled to the symbol scratchpad to perform a traceforward operation, the third trellis unit generating a traceforward result;

a state scratchpad coupled to the second trellis unit to store the second traceback result at a rate of Nbl symbols at a time;

an extrinsic information calculator coupled to the symbol scratchpad, the state scratchpad, and the third trellis unit to compute an extrinsic information.

62. The system of claim 61 wherein each of the first, second, and third trellis units comprises:

a branch metric calculator to calculate a branch metric; and

a plurality of add-compare-select (ACS) units connected according to a code topology, each of the ACS units performing a four-way min* function.

63. The system of claim 62 wherein extracted symbols include first, second, third, and fourth encoded bits.

64. The system of claim 61 wherein the SISO1 receives the first, second, and third encoded bits and the SISO2 receives the fourth encoded bit.

65. The system of claim 56 wherein the interleaver and de-interleaver are combined into a single unit comprising three planes of memory, each of the three planes of memory storing N extrinsic information symbols.