TTCM decoder design

• US 7,107,512 B2
• Filed: 05/22/2003
• Issued: 09/12/2006
• 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: Cameron, Kelly Brian
• Primary Examiner(s): TORRES, JOSEPH D
• Application Number:
  US10/444,148
• Publication Number:
  US 20030226097A1
• Time in Patent Office: 1,209 Days
• Field of Search: 714/794, 714/795
• US Class Current: 714/794
• 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/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/4123 implementing the return to a predetermined state
• 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/006 Trellis-coded modulation
• 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

TTCM (Turbo Trellis Coded Modulation) decoder design. The design also adapts to any number of devices that perform decoding of Trellis Code Modulation (TCM) signals. After performing initial symbol processing within a data block to generate a number of check point values, the design selectively re-calculates some forward metrics (alphas) and backward metrics (betas), and the design is able to calculate extrinsic (ext) information for each symbol within the data block successively. The data block is subdivided into a number of sub-blocks that are intelligently processed to enable extremely fast processing. Generally speaking, the design performs initial processing starting from both block ends, and upon approaching the block middle, the design begins to process the block using skip backs to previous sub-blocks. The design employs a great deal of parallel and simultaneously processing to provide for very fast computation of the various values required to decode the block.

Claims

1. An apparatus, comprising:

a first alpha/beta metric calculation functional block that initially processes encoded symbols of a plurality of encoded symbols in a first direction within a block, the first direction extending from a block beginning towards a block middle, to calculate forward metrics (alphas) and selectively stores alpha check point values associated with the sub-blocks of the plurality of sub-blocks that are processed in the first direction onto a check point stack, wherein the block includes a plurality of encoded symbols arranged into a plurality of sub-blocks;

wherein the first alpha/beta metric calculation functional block also initially processes the encoded symbols of the plurality of encoded symbols in a second direction within the block, the second direction extending from a block end towards the block middle, to calculate backward metrics (betas) and selectively stores beta check point values associated with the sub-blocks of the plurality of sub-blocks that are processed in the second direction;

wherein, when the first alpha/beta metric calculation functional block substantially reaches the block middle when processing in the first direction, the first alpha/beta metric calculation functional block pushes each alpha value onto an alpha stack;

wherein, when the first alpha/beta metric calculation functional block substantially reaches the block middle when processing in the second direction, the first alpha/beta metric calculation functional block pushes each beta value onto a beta stack;

wherein, when the first alpha/beta metric calculation functional block reaches the block middle after processing in the first direction, a second alpha/beta metric calculation functional block skips back to a first sub-block that has been processed in the first direction by the first alpha/beta metric calculation functional block and recalculates alphas for each encoded symbol contained in the first sub-block while the first alpha/beta metric calculation functional block simultaneously calculates betas in the second direction for a sub-block adjacent to the first sub-block;

wherein, when the first alpha/beta metric calculation functional block substantially reaches the block middle after processing in the second direction, the second alpha/beta metric calculation functional block skips back to a second sub-block that has been processed by the first alpha/beta metric calculation functional block in the second direction and re-calculates betas for each encoded symbol contained in the second sub-block while the first alpha/beta metric calculation functional block simultaneously calculates alphas in the first direction for a sub-block adjacent to the second sub-block;

for each encoded symbol for which the second alpha/beta metric calculation functional block calculates a beta in the second direction for the sub-block adjacent to the first sub-block, an extrinsic value calculation functional block pops a corresponding alpha off of the alpha stack and calculates a corresponding soft symbol decision using the most recently corresponding calculated beta and most recently popped alpha; and

for each encoded symbol for which the second alpha/beta metric calculation functional block calculates an alpha in the first direction for the sub-block adjacent to the second sub-block, the extrinsic value calculation functional block pops a corresponding beta off of the beta stack and calculates a corresponding soft symbol decision using the most recently corresponding calculated alpha and most recently popped beta.

2. The apparatus of claim 1, further comprising an output processor that selectively receives a first soft symbol decision there from that corresponds to first encoded symbol within the sub-block adjacent to the first sub-block and calculates a best estimate for the first encoded symbol using the first corresponding soft symbol decision;

and

wherein the output processor selectively receives a second corresponding soft symbol decision that corresponds to a second encoded symbol within the sub-block adjacent to the second sub-block and calculates a best estimate for the second encoded symbol using the second corresponding soft symbol decision.

3. The apparatus 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.

4. The apparatus of claim 3, wherein a rate control of the plurality of rate controls includes a modulation that includes a constellation having a mapping.

5. The apparatus of claim 3, 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.

6. The apparatus of claim 3, wherein the first alpha/beta metric calculation functional block and the second alpha/beta metric calculation functional block of the apparatus are included in a soft-in soft-out functional block (SISO) that is communicatively coupled to a metric generator that calculates a plurality of metrics for each symbol of the plurality of encoded symbols and provides the plurality of metrics to the SISO;

and

the metric generator calculates the plurality of metrics for each symbol of the plurality of encoded symbols based on its rate control.

7. The apparatus of claim 1, wherein the second alpha/beta metric calculation functional block performs skip-back processing for each remaining sub-block within the plurality of sub-blocks to re-calculate the respective alphas and betas therein.

8. The apparatus of claim 1, wherein first alpha/beta metric calculation functional block and the second alpha/beta metric calculation functional block of the apparatus are included in a soft-in soft-out functional block (SISO) that perform a first SISO operation and a second SISO operation during at least one iteration of iterative decoding to generate the soft symbol decisions.

9. The apparatus of claim 8, wherein, during the first SISO operation, the SISO calculates a first plurality of extrinsic values;

further comprising an interleaver/de-interleaver, communicatively coupled to the SISO, that interleaves the first plurality of extrinsic values to generate a first “

a priori probability”

(app) information that is fed back to the SISO during the first SISO operation;

wherein, during the second SISO operation, the SISO calculates a second plurality of extrinsic values;

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

a priori probability”

(app) information that is fed back to the SISO during the second SISO operation.

10. The apparatus of claim 1, wherein:

the apparatus is a communication device; and

the communication device 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.

11. An apparatus, comprising:

a soft-in soft-out functional block (SISO) that, based on a plurality of metrics, calculates a first plurality of extrinsic values for each encoded symbol of the plurality of encoded symbols;

an interleaver/de-interleaver, communicatively coupled to the SISO, that interleaves the first plurality of extrinsic values to generate a first “

a priori probability”

(app) information;

wherein the SISO, based on the plurality of metrics, calculates a second plurality of extrinsic values for each encoded symbol of the plurality of encoded symbols;

wherein the interleaver/de-interleaver, that is communicatively coupled to the SISO, 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 SISO during a first SISO operation;

wherein the second “

a priori probability”

(app) information is fed back to the SISO during a second SISO operation;

wherein the SISO performs the first SISO operation and the second SISO operation during 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;

wherein the SISO initially processes the encoded symbols of the plurality of encoded symbols in a first direction within a block, the first direction extending from a block beginning towards a block middle, to calculate forward metrics (alphas) and selectively stores alpha check point values associated with the sub-blocks of the plurality of sub-blocks that are processed in the first direction;

wherein the SISO also initially processes the encoded symbols of the plurality of encoded symbols in a second direction within the block, the second direction extending from a block end towards the block middle, to calculate backward metrics (betas) and selectively stores betas check point values associated with the sub-blocks of the plurality of sub-blocks that are processed in the second direction;

wherein, when the SISO substantially reaches the block middle when processing in the first direction and in the second direction, the SISO pushes each alpha value onto an alpha stack, and the SISO pushes each beta value onto a beta stack;

wherein, when the SISO reaches the block middle after processing in the first direction, the SISO skips back to a first sub-block that has been processed in the first direction and re-calculates alphas for each encoded symbol contained in the first sub-block while simultaneously continuing to calculate betas in the second direction for a sub-block adjacent to the first sub-block and popping alphas off of the alpha stack and calculating soft symbol decisions for each encoded symbol within the sub-block adjacent to the first sub-block; and

wherein, when the SISO substantially reaches the block middle after processing in the second direction, the SISO skips back to a second sub-block that has been processed in the second direction and re-calculates betas for each encoded symbol contained in the second sub-block while simultaneously continuing to calculate alphas in the first direction for a sub-block adjacent to the second sub-block and popping betas off of the beta stack and calculating soft symbol decisions for each encoded symbol within the sub-block adjacent to the second sub-block.

12. The apparatus of claim 11, wherein the plurality of encoded symbols is encoded according to a rate control sequence having a plurality of rate controls arranged in a period.

13. The apparatus of claim 12, wherein the SISO is operable to calculate the soft symbol decisions for each encoded symbol within the sub-block adjacent to the first sub-block according to the respective rate control associated with each encoded symbol.

14. The apparatus of claim 12, wherein the SISO is operable to calculate the soft symbol decisions for each encoded symbol within the sub-block adjacent to the second sub-block according to the respective rate control associated with each encoded symbol.

15. The apparatus of claim 12, wherein a rate control of the plurality of rate controls includes a modulation that includes a constellation having a mapping.

16. The apparatus of claim 12, 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.

17. The apparatus of claim 11, wherein the interleaver/de-interleaver includes logically partitioned Random Access Memory (RAM) to support simultaneous read/write operations to at least two logically partitioned portions of the RAM.

18. The apparatus of claim 11, wherein the SISO is operable to perform skip-back processing for each remaining sub-block within the plurality of sub-blocks.

19. The apparatus of claim 11, further comprising an output processor that is operable to receive the plurality of soft symbol decisions and generates hard symbol decisions there from that are best estimates of the encoded symbols of the plurality of encoded symbols.

20. The apparatus of claim 11, wherein:

the apparatus is a communication device; and

the communication device 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.

21. A method, comprising:

processing the encoded symbols of the plurality of encoded symbols in a first direction within a block that includes a plurality of encoded symbols arranged into a plurality of sub-blocks, the first direction extending from a block beginning towards a block middle, to calculate forward metrics (alphas) and selectively storing alpha check point values associated with the sub-blocks of the plurality of sub-blocks that are processed in the first direction;

processing the encoded symbols of the plurality of encoded symbols in a second direction within the block, the second direction extending from a block end towards the block middle, to calculate backward metrics (betas) and selectively storing betas check point values associated with the sub-blocks of the plurality of sub-blocks that are processed in the second direction;

when reaching the block middle when processing in the first direction and in the second direction, storing each alpha value and each beta value;

when reaching the block middle after processing in the first direction, skipping back to a first sub-block that has been processed in the first direction and re-calculating alphas for each encoded symbol contained in the first sub-block while simultaneously continuing to calculate betas in the second direction for a sub-block adjacent to the first sub-block, retrieving the stored alphas, and calculating soft symbol decisions for each encoded symbol within the sub-block adjacent to the first sub-block; and

when reaching the block middle after processing in the second direction, skipping back to a second sub-block that has been processed in the second direction and re-calculating betas for each encoded symbol contained in the second sub-block while simultaneously continuing to calculate alphas in the first direction for a sub-block adjacent to the second sub-block, retrieving stored betas, and calculating soft symbol decisions for each encoded symbol within the sub-block adjacent to the second sub-block.

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

23. The method of claim 22, further comprising calculating the soft symbol decisions for each encoded symbol within the sub-block adjacent to the first sub-block according to the respective rate control associated with each encoded symbol.

24. The method of claim 22, further comprising calculating the soft symbol decisions for each encoded symbol within the sub-block adjacent to the second sub-block according to the respective rate control associated with each encoded symbol.

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

26. The method of claim 22, 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.

27. The method of claim 21, further comprising calculating two extrinsic values for an encoded symbol of the plurality of encoded symbols.

28. The method of claim 21, further comprising performing skip-back processing for each remaining sub-block within the plurality of sub-blocks.

29. The method of claim 21, further comprising:

calculating a soft symbol decision using an extrinsic value for an encoded symbol of the plurality of encoded symbols; and

generating a hard symbol decision using the soft symbol decision that is a best estimate of the encoded symbol of the plurality of encoded symbols.

30. The method of claim 21, wherein:

the method is performed within a communication device; and

the communication device 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.