Sliding window turbo decoder

• US 6,829,313 B1
• Filed: 07/17/2000
• Issued: 12/07/2004
• Est. Priority Date: 07/17/2000
• Status: Active Grant

• Current Assignee: Google Technology Holdings LLC (Alphabet Inc.)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Xu, Shuzhan J.
• Primary Examiner(s): Liu, Shuwang
• Assistant Examiner(s): WANG, TED M
• Application Number:
  US09/617,194
• Time in Patent Office: 1,604 Days
• Field of Search: 375/341, 375/265, 375/262, 375/348, 375/259, 375/296, 375/340, 375/242, 714/781, 714/796, 714/776, 714/209, 714/786, 714/793, 714/795, 370/342
• US Class Current: 375/341
• CPC Class Codes: H03M 13/2975 Judging correct decoding, e.g. iteration stopping criteria
• CPC Class Codes: H03M 13/3905 Maximum a posteriori probability [MAP] decoding or approximations thereof based on trellis or lattice decoding, e.g. forward-backward algorithm, log-MAP decoding, max-log-MAP decoding
• CPC Class Codes: H03M 13/3961 Arrangements of methods for branch or transition metric calculation
• CPC Class Codes: H03M 13/3972 using sliding window techniques or parallel windows
• CPC Class Codes: H03M 13/41 using the Viterbi algorithm or Viterbi processors
• CPC Class Codes: H03M 13/4146 soft-output Viterbi decoding according to Battail and Hagenauer in which the soft-output is determined using path metric differences along the maximum-likelihood path, i.e. "SOVA" decoding
• CPC Class Codes: H03M 13/4169 using traceback H03M13/4192 takes precedence
• CPC Class Codes: H03M 13/45 Soft decoding, i.e. using symbol reliability information H03M13/41 takes precedence
• CPC Class Codes: H03M 13/6502 Reduction of hardware complexity or efficient processing

Abstract

Decoding signals represented by a trellis of a block length divided into windows includes a step of decoding a portion of the trellis using backward recursion starting from a point that is after the end of a window backwards to the end of the window, defining a learning period, to determine a known state metric at the end of the window. A length of the learning period for each window dependents on the signal quality such that a shorter learning period is chosen for a higher signal quality. The signal quality used is an intrinsic signal-to-noise ratio derived from the log-likelihood-ratio of the soft outputs of the decoded window. In particular, the intrinsic signal-to-noise ratio of the signal is defined as a summation of generated extrinsic information multiplied by a log-likelihood-ratio (LLR) value at each iteration.

Claims

1. A method of reducing calculations in the decoding of a received convolutionally coded signal represented by a trellis of a predetermined block length, the method comprising the steps of:

a) dividing the trellis into windows;

b) selecting a first window of the trellis having a known first state metric;

c) decoding a portion of the trellis using backward recursion starting from a point that is after the end of the window selected in the previous step backwards to the end of the window, defining a learning period, to determine a known state metric at the end of the window, wherein a length of the learning period is dependent on the quality of the signal such that a shorter learning period is chosen for a higher quality signal and a longer learning period is chosen for a low er quality signal;

d) decoding a portion of the trellis within the window using forward and backward recursion starting from the respective known state metrics at a beginning and end of the window defined in the previous step so as to determine the forward and backward recursion state metrics at each stage in the window;

e) calculating a soft output at each stage of the window using the forward recursion state metrics, the branch metrics, and the stored backward recursion state metrics;

f) determining the quality of the signal from the previous step;

g) adjusting the learning period to be shorter as the quality of the signal improves and longer if the quality of the signal worsens; and

h) selecting a next window of the trellis and proceeding with the steps c)-g) until the entire trellis is decoded.

2. The method of claim 1, wherein the adjusting step includes an upper and a lower boundary for the length of the learning period.

3. The method of claim 2, wherein the first decoding step includes an initial learning period being set at the upper boundary, and the adjusting step only allows for a shortening of the learning period as the quality of the signal improves.

4. The method of claim 1, wherein the adjusting step includes an initial learning period having a length of about five constraint lengths of the convolutional code.

5. The method of claim 1, wherein the adjusting step includes the adjustment in the learning period being proportional to the change in the quality of the signal found in the determining step.

6. The method of claim 1, wherein the quality of the signal in the determining step is determined from an intrinsic signal-to-noise ratio of the signal defined as a summation of generated extrinsic information multiplied by a quantity extracted from log-likelihood-ratio (LLR) value at each iteration generated in the second decoding step.

7. The method of claim 6, wherein the determining step includes the extracted quantity being a hard decision of the LLR value.

8. The method of claim 6, wherein the determining step includes the extracted quantity being the LLR value itself.

9. The method of claim 1, further comprising the step of providing a turbo decoder with two recursion processors connected in an iterative loop, and at least one additional recursion processor coupled in parallel at the inputs of at least one of the recursion processors, all of the recursion processors concurrently performing iteration calculations on the signal, and wherein the quality of the signal in the determining step is derived from a log-likelihood-ratio generated by the at least one recursion processor.

10. The method of claim 9, wherein the providing step includes the at least one additional recursion processor being a Viterbi decoder, and the two recursion processors are soft-input, soft-output decoders.

11. The method of claim 1, wherein the decoding steps include a generalized Viterbi algorithm for the decoding steps.

12. The method of claim 1, wherein the calculating step uses a maximum a posteriori (MAP) algorithm to calculate the soft output at each stage, wherein the MAP algorithm includes one of the group of a log-MAP, MAP, max-log-MAP, and constant-log-MAP algorithm.

19. The radiotelephone of claim 11, wherein the processors use a generalized Viterbi algorithm.

20. The radiotelephone of claim 11, wherein the decoder uses a maximum a posteriori (MAP) algorithm to calculate the soft output at each stage, wherein the MAP algorithm includes one of the group of a log-MAP, MAP, max-log-MAP, and constant-log-MAP algorithm.

13. A method of reducing calculations in the decoding of a received convolutionally coded sequence of signals represented by a trellis of a predetermined block length, the method comprising the steps of:

a) dividing the trellis into windows;

b) selecting a first window of the trellis having a known first state metric;

c) decoding a portion of the trellis using backward recursion starting from a point that is after the end of the window selected in the previous step backwards to the end of the window, defining a learning period, to determine a known state metric at the end of the window, wherein a length of the learning period is dependent on an intrinsic signal-to-noise ratio of the signal such that the learning period is shortened as the intrinsic signal-to-noise ratio of the signal improves;

d) decoding a portion of the trellis within the window using forward and backward recursion starting from the respective known state metrics at a beginning and end of the window defined in the previous step so as to determine the forward and backward recursion state metrics at each stage in the window;

e) calculating a soft output at each stage of the window using the forward recursion state metrics, the branch metrics, and the stored backward recursion state metrics;

f) determining the intrinsic signal-to-noise ratio of the signal defined as a summation of generated extrinsic information multiplied by a log-likelihood-ratio (LLR) value at each iteration generated in the second decoding step;

g) adjusting the learning period from an initial upper boundary to be shorter as the quality of the signal improves but not more than a lower boundary; and

h) selecting a next window of the trellis and proceeding with the steps c)-g) until the entire trellis is decoded.

14. A radiotelephone with a receiver and demodulator with a soft-decision output decoder for serially processing windows of a convolutionally coded signal, represented by a trellis of predetermined block length divided into windows in a frame buffer, the soft-decision output decoder comprising:

a memory;

a learning recursion processor decodes a portion of the trellis using a learning backward recursion from a point that is after the end of a window backward to the end of the window, defining a learning period, to determine a known state metric at the end of the window;

a backward recursion processor subsequently decodes the portion of the trellis within the window using backward recursion from the known state at the end of the window back to the beginning of the window to define a set of known backward recursion state metrics within the window which can be stored in the memory;

a forward recursion processor decodes the portion of the trellis within the window using forward recursion starting from a known state at the beginning of the window and moving forward to define a set of known forward recursion state metrics within the window which can be stored in the memory; and

a decoder coupled to the memory calculates a soft output at each stage of the window using the forward and backward recursion state metrics and branch metrics at each stage, the decoder also determines a quality of the signal for each window and adjusts the learning period for processing a next window to be shorter as the quality of the signal improves and longer if the quality of the signal worsens.

15. The radiotelephone of claim 14, wherein an initial learning period is set at the upper boundary, and the decoder only allows for a shortening of the learning period, as the quality of the signal improves, to not less than a lower boundary.

16. The radiotelephone of claim 14, wherein the adjustment of the learning period is proportional to the change in the quality of the signal.

17. The radiotelephone of claim 14, wherein the quality of the signal in the is determined from an intrinsic signal-to-noise ratio of the signal defined as a summation of generated extrinsic information multiplied by a quantity extracted from log-likelihood-ratio (LLR) value at each iteration generated in the decoder.

18. The radiotelephone of claim 17, wherein the extracted quantity is one of the group of a hard decision of the LLR value and the LLR value itself.