Interleaver for iterative decoder

• US 6,954,832 B2
• Filed: 03/08/2003
• Issued: 10/11/2005
• Est. Priority Date: 05/31/2002
• Status: Expired due to Fees

• Current Assignee: Avago Technologies General IP PTE Limited (Broadcom, Inc.)
• Original Assignee: Broadcom Corporation (Broadcom, Inc.)
• Inventors: Suzuki, Hiroshi, Krafft, Stephen Edward
• Primary Examiner(s): Anderson, Matthew D.
• Application Number:
  US10/384,430
• Publication Number:
  US 20030225985A1
• Time in Patent Office: 948 Days
• Field of Search: 711/167, 711/5, 711/127, 711/157, 341/81, 375/265
• US Class Current: 711/157
• CPC Class Codes: H03M 13/258 with turbo codes, e.g. Turbo Trellis Coded Modulation [TTCM]
• CPC Class Codes: H03M 13/27 using interleaving techniques
• CPC Class Codes: H03M 13/2767 Interleaver wherein the permutation pattern or a portion thereof is stored
• CPC Class Codes: H03M 13/2771 Internal interleaver for turbo codes H03M13/2714 and H03M13/2725 take precedence
• CPC Class Codes: H03M 13/2785 Interleaver using in-place interleaving, i.e. writing to and reading from the memory is performed at the same memory location
• CPC Class Codes: H03M 13/2957 Turbo codes and decoding
• CPC Class Codes: H03M 13/4161 implementing path management
• CPC Class Codes: H04L 1/005 Iterative decoding, including iteration between signal detection and decoding operation
• CPC Class Codes: H04L 1/0066 Parallel concatenated codes
• CPC Class Codes: H04L 1/0068 by puncturing
• CPC Class Codes: H04L 1/0071 Use of interleaving interleaving per se H03M13/27

Abstract

Interleaver for iterative decoder. A memory management scheme allows for single plane/single port memory devices to be used by the interleaver. The design is adaptable to soft-in soft-out (SISO) decoders that perform iterative decoding. The interleaver may be implemented within communication devices that implement two distinct SISOs that operate cooperatively or within communication devices that employ a single SISO (in a recycled embodiment) that functionally performs the analogous decoding operations that would be performed by the two distinct SISO implementation. The use of single plane/single port memory devices by the interleaver allows for a great deal of savings from many perspectives: the sizes of the required interleaver memory and the interleaver pattern memory are both cut in half using this approach, and a cost savings may also be realized, in that, cheaper, slower memories may be used since each respective interleaver memory is read only every other cycle.

Claims

1. An interleaver memory structure for facilitating the decoding of a plurality of encoded symbols, the interleaver memory structure comprising:

during a first clock cycle;

a first interleaver pattern memory receives a first sequential read address;

a second interleaver pattern memory receives a first sequential write address;

during a second clock cycle;

the first interleaver pattern memory receives a second sequential write address;

the second interleaver pattern memory receives a second sequential read address;

a first read address is received from the first interleaver pattern memory for use by a first interleaver memory;

a first write address is received from the second interleaver pattern memory for use by a second interleaver memory;

during a third clock cycle;

the first interleaver pattern memory receives a third sequential read address;

the second interleaver pattern memory receives a third sequential write address;

a second write address is received from the first interleaver pattern memory for use by the first interleaver memory;

a second read address is received from the second interleaver pattern memory for use by the second interleaver memory;

a first data is read from the first interleaver memory;

a second data is written to the second interleaver memory; and

wherein each of the first interleaver pattern memory, the second interleaver pattern memory, the first interleaver memory, and the second interleaver memory are implemented using single port memory structures.

2. The interleaver memory structure of claim 1, wherein:

during a fourth clock cycle;

the first interleaver pattern memory receives a fourth sequential write address;

the second interleaver pattern memory receives a fourth sequential read address;

a third read address is received from the first interleaver pattern memory for use by the first interleaver memory;

a third write address is received from the second interleaver pattern memory for use by the second interleaver memory;

a third data is written to the first interleaver memory; and

a fourth data is read from the second interleaver memory.

3. The interleaver memory structure of claim 1, wherein read accesses and write accesses are alternatively performed within each of the first interleaver memory and the second interleaver memory.

4. The interleaver memory structure of claim 1, wherein the first sequential read address and the first sequential write address are offset by an odd value.

5. The interleaver memory structure of claim 1, wherein the second sequential write address and the second sequential write address are offset by an odd value.

6. The interleaver memory structure of claim 1, further comprising:

a first multiplexor (MUX) that receives the first sequential read address and the first sequential write address as inputs during the first clock cycle and provides the first sequential read address to the first interleaver pattern memory;

a second MUX that receives the first sequential read address and the first sequential write address as inputs during the first clock cycle and provides the first sequential write address to the second interleaver pattern memory;

wherein the first MUX receives the second sequential read address and the second sequential write address as inputs during the second clock cycle and provides the second sequential write address to the first interleaver pattern memory; and

wherein the second MUX receives the second sequential read address and the second sequential write address as inputs during the second clock cycle and provides the second sequential read address to the second interleaver pattern memory.

7. The interleaver memory structure of claim 1, wherein the interleaver memory structure is employed by a soft-in soft-out (SISO) decoder that includes a top SISO and a bottom SISO;

wherein the top SISO provides extrinsic information that is fed back to the bottom SISO in an interleaved order during a first SISO operation; and

wherein the bottom SISO provides extrinsic information that is fed back to the top SISO in a de-interleaved order during a second SISO operation.

8. The interleaver memory structure of claim 1, wherein the interleaver memory structure is employed by a soft-in soft-out (SISO) decoder;

wherein the SISO decoder is implemented as a single, recycled SISO decoder;

wherein the SISO provides extrinsic information that is fed back to the SISO in an interleaved order during a first SISO operation; and

wherein the SISO provides extrinsic information that is fed back to the SISO in a de-interleaved order during a second SISO operation.

9. The interleaver memory structure of claim 1, wherein the plurality of encoded symbols is encoded according to a rate control sequence having a plurality of rate controls arranged in a period.

10. The interleaver memory structure of claim 9, wherein a rate control of the plurality of rate controls includes a modulation that includes a constellation having a mapping.

11. The interleaver memory structure of claim 9, wherein a first rate control of the plurality of rate controls includes a first modulation that includes a first constellation having a first mapping;

and

wherein a second rate control of the plurality of rate controls includes a second modulation that includes a second constellation having a second mapping.

12. The interleaver memory structure of claim 1, wherein the interleaver memory structure is employed by a soft-in soft-out (SISO) decoder;

wherein the SISO decoder is part of a decoder that employs a trellis to decode the plurality of encoded symbols;

wherein the plurality of encoded symbols is encoded according to a rate control sequence having a plurality of rate controls arranged in a period;

wherein the SISO decoder includes a top SISO and a bottom SISO;

wherein the top SISO, based on a plurality of trellis metrics, calculates a first plurality of extrinsic values for each encoded symbol of the plurality of encoded symbols according to the respective rate control;

wherein the interleaver memory structure interleaves the first plurality of extrinsic values to generate a first “

a priori probability”

(app) information;

the bottom SISO, based on the plurality of trellis metrics, calculates a second plurality of extrinsic values for each encoded symbol of the plurality of encoded symbols according to the respective rate control;

wherein the interleaver memory structure de-interleaves the second plurality of extrinsic values to generate a second “

a priori probability”

(app) information;

wherein the first “

a priori probability”

(app) information is fed back to the bottom SISO;

wherein the second “

a priori probability”

(app) information is fed back to the top SISO;

wherein the top SISO and the bottom SISO operate cooperatively to perform at least one iteration of iterative decoding to generate a plurality of soft symbol decisions, each soft symbol decision of the plurality of soft symbol decisions corresponds to an encoded symbol of the plurality of encoded symbols; and

an output processor, communicatively coupled to the bottom SISO, that generates a hard symbol decision for each soft symbol decision of the plurality of soft symbol decisions thereby making a best estimate for each encoded symbol of the plurality of encoded symbols.

13. The interleaver memory structure of claim 1, wherein the plurality of encoded symbols is encoded according to at least one of TTCM (Turbo Trellis Coded Modulation), PC-TCM (Parallel Concatenated Trellis Coded Modulation), and Trellis Code Modulation (TCM).

14. The interleaver memory structure of claim 1, wherein the interleaver memory structure is employed by a decoder that is implemented within a communication receiver;

and

wherein the communication receiver is contained within at least one of a satellite communication system, a High Definition Television (HDTV) communication system, a cellular communication system, a microwave communication system, a point-to-point communication system, a uni-directional communication system, a bi-directional communication system, a one to many communication system, and a fiber-optic communication system.

15. A soft-in soft-out (SISO) decoder that includes an interleaver memory structure for facilitating the decoding of a plurality of encoded symbols, the SISO decoder comprising:

a top SISO that, based on a plurality of trellis metrics, calculates a first plurality of extrinsic values for each encoded symbol of the plurality of encoded symbols;

wherein the interleaver memory structure interleaves the first plurality of extrinsic values to generate a first “

a priori probability”

(app) information;

a bottom SISO that, based on the plurality of trellis metrics, calculates a second plurality of extrinsic values for each encoded symbol of the plurality of encoded symbols according to the respective rate control;

wherein the interleaver memory structure de-interleaves the second plurality of extrinsic values to generate a second “

a priori probability”

(app) information;

wherein the first “

a priori probability”

(app) information is fed back to the bottom SISO;

wherein the second “

a priori probability”

(app) information is fed back to the top SISO;

wherein the top SISO and the bottom SISO operate cooperatively to perform at least one iteration of iterative decoding to generate a plurality of soft symbol decisions, each soft symbol decision of the plurality of soft symbol decisions corresponds to an encoded symbol of the plurality of encoded symbols; and

an output processor, communicatively coupled to the bottom SISO, that generates a hard symbol decision for each soft symbol decision of the plurality of soft symbol decisions thereby making a best estimate for each encoded symbol of the plurality of encoded symbols;

wherein the interleaver memory structure includes a first interleaver pattern memory, a second interleaver pattern memory, a first interleaver memory, and a second interleaver memory that are all implemented using single port memory structures;

during a first clock cycle;

a first interleaver pattern memory receives a first sequential read address;

a second interleaver pattern memory receives a first sequential write address;

during a second clock cycle;

the first interleaver pattern memory receives a second sequential write address;

the second interleaver pattern memory receives a second sequential read address;

a first read address is received from the first interleaver pattern memory for use by a first interleaver memory;

a first write address is received from the second interleaver pattern memory for use by a second interleaver memory;

during a third clock cycle;

the first interleaver pattern memory receives a third sequential read address;

the second interleaver pattern memory receives a third sequential write address;

a second write address is received from the first interleaver pattern memory for use by the first interleaver memory;

a second read address is received from the second interleaver pattern memory for use by the second interleaver memory;

a first data is read from the first interleaver memory;

a second data is written to the second interleaver memory; and

wherein each of the first interleaver pattern memory, the second interleaver pattern memory, the first interleaver memory, and the second interleaver memory are implemented using single port memory structures.

16. The SISO decoder of claim 15, wherein the plurality of encoded symbols is encoded according to a rate control sequence having a plurality of rate controls arranged in a period.

17. The SISO decoder of claim 16, wherein a rate control of the plurality of rate controls includes a modulation that includes a constellation having a mapping.

18. The SISO decoder of claim 16, wherein a first rate control of the plurality of rate controls includes a first modulation that includes a first constellation having a first mapping;

and

wherein a second rate control of the plurality of rate controls includes a second modulation that includes a second constellation having a second mapping.

19. The SISO decoder of claim 15, wherein:

during a fourth clock cycle;

the first interleaver pattern memory receives a fourth sequential write address;

the second interleaver pattern memory receives a fourth sequential read address;

a third read address is received from the first interleaver pattern memory for use by the first interleaver memory;

a third write address is received from the second interleaver pattern memory for use by the second interleaver memory;

a third data is written to the first interleaver memory; and

a fourth data is read from the second interleaver memory.

20. The SISO decoder of claim 15, wherein read accesses and write accesses are alternatively performed within each of the first interleaver memory and the second interleaver memory.

21. The SISO decoder of claim 15, wherein the first sequential read address and the first sequential write address are offset by an odd value.

22. The SISO decoder of claim 15, wherein the second sequential write address and the second sequential write address are offset by an odd value.

23. The SISO decoder of claim 15, wherein the interleaver memory structure further comprises:

a first multiplexor (MUX) that receives the first sequential read address and the first sequential write address as inputs during the first clock cycle and provides the first sequential read address to the first interleaver pattern memory;

a second multiplexor (MUX) that receives the first sequential read address and the first sequential write address as inputs during the first clock cycle and provides the first sequential write address to the second interleaver pattern memory;

wherein the first MUX receives the second sequential read address and the second sequential write address as inputs during the second clock cycle and provides the second sequential write address to the first interleaver pattern memory; and

wherein the second MUX receives the second sequential read address and the second sequential write address as inputs during the second clock cycle and provides the second sequential read address to the second interleaver pattern memory.

24. The SISO decoder of claim 15, wherein the plurality of encoded symbols is encoded according to at least one of TTCM (Turbo Trellis Coded Modulation), PC-TCM (Parallel Concatenated Trellis Coded Modulation), and Trellis Code Modulation (TCM).

25. The SISO decoder of claim 15, wherein the SISO decoder is implemented within a communication receiver;

and

wherein the communication receiver is contained within at least one of a satellite communication system, a High Definition Television (HDTV) communication system, a cellular communication system, a microwave communication system, a point-to-point communication system, a uni-directional communication system, a bi-directional communication system, a one to many communication system, and a fiber-optic communication system.

26. An interleaver memory processing method, the method comprising:

during a first clock cycle;

providing a first sequential read address to a first interleaver pattern memory;

providing a first sequential write address to a second interleaver pattern memory;

during a second clock cycle;

providing a second sequential write address to the first interleaver pattern memory;

providing a second sequential read address to the second interleaver pattern memory;

receiving a first read address from the first interleaver pattern memory for use by a first interleaver memory;

receiving a first write address from the second interleaver pattern memory for use by a second interleaver memory;

during a third clock cycle;

providing a third sequential read address to the first interleaver pattern memory;

providing a third sequential write address to the second interleaver pattern memory;

receiving a second write address from the first interleaver pattern memory for use by the first interleaver memory;

receiving a second read address from the second interleaver pattern memory for use by the second interleaver memory;

reading a first data from the first interleaver memory; and

writing a second data to the second interleaver memory.

27. The method of claim 26, wherein:

during a fourth clock cycle;

providing a fourth sequential write address to the first interleaver pattern memory;

providing a fourth sequential read address to the second interleaver pattern memory;

receiving a third read address from the first interleaver pattern memory for use by the first interleaver memory;

receiving a third write address from the second interleaver pattern memory for use by the second interleaver memory;

writing a third data to the first interleaver memory; and

reading a fourth data from the second interleaver memory.

28. The method of claim 26, wherein read accesses and write accesses are alternatively performed within each of the first interleaver memory and the second interleaver memory.

29. The method of claim 26, wherein the first sequential read address and the first sequential write address are offset by an odd value.

30. The method of claim 26, wherein the second sequential write address and the second sequential write address are offset by an odd value.

31. The method of claim 26, wherein the plurality of encoded symbols is encoded according to a rate control sequence having a plurality of rate controls arranged in a period.

32. The method of claim 31, wherein a rate control of the plurality of rate controls includes a modulation that includes a constellation having a mapping.

33. The method of claim 31, wherein a first rate control of the plurality of rate controls includes a first modulation that includes a first constellation having a first mapping;

and

wherein a second rate control of the plurality of rate controls includes a second modulation that includes a second constellation having a second mapping.

34. The method of claim 26, wherein the plurality of encoded symbols is encoded according to at least one of TTCM (Turbo Trellis Coded Modulation), PC-TCM (Parallel Concatenated Trellis Coded Modulation), and Trellis Code Modulation (TCM).

35. The method of claim 26, wherein the method is performed within a decoder that is implemented within a communication receiver;

wherein the communication receiver is contained within at least one of a satellite communication system, a High Definition Television (HDTV) communication system, a cellular communication system, a microwave communication system, a point-to-point communication system, a uni-directional communication system, a hi-directional communication system, a one to many communication system, and a fiber-optic communication system.