Interleaver for iterative decoder

• US 7,360,040 B2
• Filed: 09/21/2005
• Issued: 04/15/2008
• Est. Priority Date: 05/31/2002
• Status: Expired due to Fees

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Broadcom Corporation (Broadcom, Inc.)
• Inventors: Suzuki, Hiroshi, Krafft, Stephen Edward
• Primary Examiner(s): Bataille; Pierre
• Assistant Examiner(s): Birkhimer; Christopher D
• Application Number:
  US11/231,635
• Publication Number:
  US 20060036819A1
• Time in Patent Office: 937 Days
• Field of Search: 711/157, 711/211, 711/218, 711/219, 710/53, 341/81, 341/155, 341/161, 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 that is implemented to process a plurality of encoded symbols during decoding processing, the interleaver memory structure comprising:

a first multiplexor (MUX) that is operable to receive inputs that include sequential read addresses and sequential write addresses as inputs and whose select signal is a clock signal having even and odd cycles;

a second MUX that is operable to receive the sequential read addresses and the sequential write addresses as inputs and whose select signal is an inversion of the clock signal having even and odd cycles, wherein corresponding sequential read addresses and sequential write addresses that are provided to the first MUX and to the second MUX are offset by an odd value;

a first interleaver pattern memory that is operable alternatively to receive the sequential read addresses and the sequential write addresses from the first MUX;

a second interleaver pattern memory that is operable alternatively to receive the sequential write addresses and the sequential read addresses from the second MUX;

a first interleaver memory that is operable to;

receive first input data that is written therein according to a sequential write address provided by the first interleaver pattern memory; and

provide first output data that is read there from according to a sequential read address provided by the first interleaver pattern memory;

a second interleaver memory that is operable to;

receive second input data that is written therein according to a sequential write address provided by the second interleaver pattern memory; and

provide second output data that is read there from according to a sequential read address provided by the second interleaver pattern memory; and

a third MUX that is operable to receive inputs that include the first output data and the second output data and whose select signal is the clock signal having even and odd cycles.

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

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.

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

the first interleaver pattern memory is operable to receive a first sequential read address when the second interleaver pattern memory is operable to receive a first sequential write address; and

the first interleaver pattern memory is operable to receive a second sequential write address when the second interleaver pattern memory is operable to receive a second sequential read address.

4. 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.

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

a first AND gate, whose output governs the writing of the first input data to the first interleaver memory, that receives a first write command and the clock signal having even and odd cycles as inputs; and

a second AND gate, whose output governs the writing of the second input data to the second interleaver memory, that receives a second write command and the inversion of the clock signal having even and odd cycles.

6. 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;

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

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

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

the interleaver memory structure is employed by a soft-in soft-out (SISO) decoder;

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

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

8. 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.

9. The interleaver memory structure of claim 8, wherein:

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

10. The interleaver memory structure of claim 8, 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

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

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

the interleaver memory structure is employed by a soft-in soft-out (SISO) decoder included within a decoder that is operable to perform the decoding processing by employing a trellis to decode the plurality of encoded symbols;

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

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

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;

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;

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

a priori probability”

(app) information;

the first “

a priori probability”

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

the second “

a priori probability”

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

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

further comprising;

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.

12. 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).

13. 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

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 unidirectional communication system, a bi-directional communication system, a one to many communication system, and a fiber-optic communication system.

14. An interleaving method, the method comprising:

multiplexing sequential read addresses and sequential write addresses, that are offset by an odd value, based on a clock signal having even and odd cycles;

multiplexing the sequential read addresses and the sequential write addresses based on an inversion of the clock signal having even and odd cycles;

receiving first input data according to a first sequential write address;

providing first output data, that corresponds to the first input data, according to a first sequential read address;

receiving second input data according to a second sequential write address;

providing second output data, that corresponds to the second input data, according to a second sequential read address; and

multiplexing the first output data and the second output data based on the clock signal having even and odd cycles.

15. The method of claim 14, further comprising:

receiving the first sequential read address when receiving the first sequential write address; and

receiving the second sequential write address when receiving the second sequential read address.

16. The method of claim 14, further comprising:

alternatively receiving the first input data and providing the first output data; and

alternatively receiving second input data and providing the second output data.

17. The method of claim 14, wherein:

the method is operable to interleave extrinsic information corresponding to a plurality of encoded symbols that is encoded according to a rate control sequence having a plurality of rate controls arranged in a period; and

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

18. An interleaver memory structure that is implemented to process a plurality of encoded symbols during decoding processing, the interleaver memory structure comprising:

a first interleaver pattern memory that is operable alternatively to receive sequential read addresses and sequential write addresses;

a second interleaver pattern memory that is operable alternatively to receive the sequential write addresses and the sequential read addresses;

a first interleaver memory that is operable to;

receive first input data that is written therein according to a sequential write address provided by the first interleaver pattern memory; and

provide first output data that is read there from according to a sequential read address provided by the first interleaver pattern memory;

a second interleaver memory that is operable to;

receive second input data that is written therein according to a sequential write address provided by the second interleaver pattern memory; and

provide second output data that is read there from according to a sequential read address provided by the second interleaver pattern memory; and

a multiplexor (MUX) that is operable to receive inputs that include the first output data and the second output data and whose select signal is a clock signal having even and odd cycles; and

wherein 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.

19. The interleaver memory structure of claim 18, wherein:

the MUX is a first MUX; and

further comprising;

a second MUX that is operable to receive inputs that include the sequential read addresses and the sequential write addresses as inputs, whose select signal is a clock signal having even and odd cycles, and having a first output that is provided to the first interleaver pattern memory;

a third MUX that is operable to receive the sequential read addresses and the sequential write addresses as inputs, whose select signal is an inversion of the clock signal having even and odd cycles, and having a second output that is provided to the second interleaver pattern memory, wherein corresponding sequential read addresses and sequential write addresses that are provided to the first MUX and to the second MUX are offset by an odd value;

a first AND gate, whose output governs the writing of the first input data to the first interleaver memory, that receives a first write command and the clock signal having even and odd cycles as inputs; and

a second AND gate, whose output governs the writing of the second input data to the second interleaver memory, that receives a second write command and an inversion of the clock signal having even and odd cycles.

20. The interleaver memory structure of claim 18, wherein:

the interleaver memory structure is operable to interleave extrinsic information corresponding to a plurality of encoded symbols that is encoded according to a rate control sequence having a plurality of rate controls arranged in a period; and

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