Soft decision output decoder for decoding convolutionally encoded codewords

• US 5,933,462 A
• Filed: 11/06/1996
• Issued: 08/03/1999
• Est. Priority Date: 11/06/1996
• Status: Expired due to Term

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Sindhushayana, Nagabhushana T., Viterbi, Andrew J.
• Primary Examiner(s): Pham, Chi H.
• Assistant Examiner(s): Corrielus, Jean B
• Application Number:
  US08/743,688
• Time in Patent Office: 1,000 Days
• Field of Search: 375/262, 375/265, 375/341, 375/254, 375/285, 375/346, 375/348, 375/377, 455/63, 455/296, 371/43.4, 371/43.6, 371/43.7, 371/43.8, 371/43.1, 360/51
• US Class Current: 375/341
• CPC Class Codes: H03M 13/2957 Turbo codes and decoding
• 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/3911 Correction factor, e.g. approximations of the exp(1+x) function
• 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: H04L 1/005 Iterative decoding, including iteration between signal detection and decoding operation
• CPC Class Codes: H04L 1/0054 Maximum-likelihood or sequential decoding, e.g. Viterbi, Fano, ZJ algorithms
• CPC Class Codes: H04L 1/0055 MAP-decoding
• CPC Class Codes: H04L 1/006 Trellis-coded modulation

Abstract

A soft decision output decoder and decoding method. The decoder decodes a sequence of signals output by an encoder and transmitted over a channel. The soft decision output decoder includes a first "generalized" Viterbi decoder for decoding the sequence of signals received over the channel during a forward iteration through a trellis representing the encoder output having a block length T. The first "generalized" Viterbi decoder begins at an initial state t₀ and provides a plurality of forward iteration state metrics α for each state at each time interval over a window of length 2L, where L is on the order of a few constraint lengths and 2L is less than a block length T. A second "generalized" Viterbi decoder decodes the sequence of signals received over the channel during a backward iteration through the trellis. The second decoder starts at a second time t2L and provides a plurality of backward iteration state metrics β for each state at each time interval. A processor then performs a dual maxima computation at each state using the forward state metric, the backward state metric and the branch metric for same to provide a measure of the likelihood that a particular sequence of data was transmitted by the encoder. The processor computes a log of the likelihood ratio using the forward and backward state metrics and the branch metrics for a selected state. This is achieved by first computing a max function as an approximation of the measure of the likelihood that a particular sequence of data was transmitted by the encoder. By performing forward and backward Viterbi decoding with dual maxima computations at each node within a window moved over the trellis, the inventive decoder provides the performance benefits associated with a LOG-MAP decoder while avoiding the excessive memory requirements of same.

Claims

1. A system for decoding a sequence of signals output by an encoder and transmitted over a channel, said encoder output represented by a trellis having a block length T, said system comprising:

first means for Viterbi decoding said sequence of signals received over said channel during a forward iteration through said trellis, said first means providing a plurality of forward iteration state metrics (x for each state at each time interval over a window of length 2L, where L is a number of constraint lengths and 2L is less than block length T, wherein said forward iteration begins at an initial state t₀ ;

second means for Viterbi decoding said sequence of signals received over said channel during a backward iteration through said trellis, said second means providing a plurality of backward iteration state metrics β

for each state at each time interval starting at a second time; and

third means for performing a dual maxima computation at each state using the forward state metrics, the backward state metrics and the branch metrics for same to provide a measure of the likelihood that a particular sequence of data was transmitted by said encoder.

2. The invention of claim 1 wherein said first means includes means for multiplying a forward state metric α

_t-1 (s'"'"') for a previous state s'"'"' by a branch metric γ

_t (s'"'"',s) to provide said forward state metric α

_t (s) for a selected state s.

3. The invention of claim 2 wherein said first means includes means for summing products of the forward state metrics α

_t-1 (s'"'"') for each previous state s'"'"' by a branch metric γ

_t (s'"'"',s) between each previous state s'"'"' and the selected state s to provide said forward state metric α

_t (s) for the selected state s.

4. The invention of claim 1 wherein said second means includes means for multiplying a backward state metric β

_t+1 (s'"'"') for a subsequent state s'"'"' by a branch metric γ

_t (s,s'"'"') to provide said branch metric β

_t (s) for a selected state s.

5. The invention of claim 4 wherein said second means includes means for summing products of the backward state metrics β

_t+1 (s'"'"') for each subsequent state s'"'"' by a branch metric γ

_t (s,s'"'"') between each subsequent state s'"'"' and each selected state s to provide said branch metric β

_t (s) for the selected state s.

6. The invention of claim 1 wherein said means for performing a dual maxima computation includes means for computing a likelihood ratio.

7. The invention of claim 6 wherein said means for computing a likelihood ratio includes means for computing the log of the likelihood ratio.

8. The invention of claim 1 wherein said third means includes means for computing a max function as an approximation of the measure of the likelihood that a particular sequence of data was transmitted by said encoder.

9. The invention of claim 8 wherein said third means includes means for providing a correction factor for said approximation to provide a more exact measure of the likelihood that a particular sequence of data was transmitted by said encoder.

10. The invention of claim 9 wherein said correction factor includes an exponential function of the forward state metric and the backward state metric and the branch metric for a selected state.

11. The invention of claim 1 wherein said second means includes means for providing a second backward iteration through said trellis, said second means providing a second plurality of backward iteration state metrics β

for each state at each time interval starting at a third time t_3L.

12. A soft decision output decoder comprising:

means for receiving a sequence of transmitted codewords;

means for providing a trellis for decoding of said sequence of codewords, said trellis having a block length T;

first means for decoding said sequence of signals received over said channel during a forward iteration through said trellis, said first means providing a plurality of forward iteration state metrics α

for each state at each time interval over a window of length 2L, where L is a number of constraint lengths and 2L is less than a block length T, wherein said forward iteration begins at an initial state t₀, said first means including means for summing products of forward state metrics α

_t-1 (s'"'"') for each previous state s'"'"' by a branch metric γ

_t (s'"'"',s) between each previous state s'"'"' and the selected state s to provide a forward state metric α

_t (s) for the selected state s;

second means for decoding said sequence of signals received over said channel during a backward iteration through said trellis, said second means including;

means for summing products of the backward state metrics β

_t+1 (s'"'"') for each subsequent state s'"'"' by a branch metric γ

_t (s,s'"'"') between each subsequent state s'"'"' and each selected state s to provide a first plurality of backward iteration state metrics β

_t (s) for each selected state s at each time interval starting at a second time t_2L and

means for summing products of the backward state metrics β

_t+1 (s'"'"') for each subsequent state s'"'"' by a branch metric γ

_t (s,s'"'"') between each subsequent state s'"'"' and each selected state s to provide a second plurality of backward iteration state metrics β

_t (s) for each selected state s at each time interval starting at a third time t_3L ; and

third means for performing a dual maxima computation at each state using the forward state metrics, the backward state metrics and the branch metrics for same to provide a measure of the likelihood that a particular sequence of data was transmitted by said encoder.

13. The invention of claim 12 wherein said means for performing a dual maxima computation includes means for computing a likelihood ratio.

14. The invention of claim 13 wherein said means for computing a likelihood ratio includes means for computing the log of the likelihood ratio.

15. The invention of claim 12 wherein said third means includes means for computing a max function as an approximation of the measure of the likelihood that a particular sequence of data was transmitted by said encoder.

16. The invention of claim 15 wherein said third means includes means for providing a correction factor for said approximation to provide a more exact measure of the likelihood that a particular sequence of data was transmitted by said encoder.

17. The invention of claim 16 wherein said correction factor includes an exponential function of the forward state metric and the backward state metrics and the branch metric for a selected state.

18. A method for decoding a convolutionally encoded codeword including the steps of:

a) providing a trellis representative of an output of an encoder used to encode said codeword, said trellis having a block length T;

b) assigning an initial condition to each starting node of the trellis for a forward iteration through the trellis;

c) assigning an initial condition to each starting node for a backward iteration through the trellis;

d) computing a forward metric for each node in a window of length L on the trellis during a forward iteration, where the window length L is less than the block length T;

e) computing, during a backward iteration, a backward metric for each node in a window of length L on the trellis starting at a time 2L from a point at which the forward iteration is initiated;

f) computing a dual maxima for each node using the forward metric and the backward metric to decode said codeword; and

g) repeat steps d)-f) over entire block.

19. The invention of claim 18 wherein the step f) includes the step of log mapping.

20. The invention of claim 18 wherein the step e) includes a step of initiating a second backward iteration starting at time 3L from a point at which the forward iteration is initiated.

21. A method for decoding a convolutionally encoded codeword including the steps of:

a) providing a trellis representative of an output of an encoder used to encode said codeword, said trellis having a block length T;

b) assigning an initial condition to each starting node of the trellis for a forward iteration through the trellis;

c) assigning an initial condition to each starting node for a backward iteration through the trellis;

d) using a Viterbi algorithm to compute a forward metric for each node in a window of length L on the trellis during a forward iteration, where the window length L is less than the block length T;

e) using a Viterbi algorithm to compute, during a backward iteration, a backward metric for each node in a window of length L on the trellis starting at a time 2L from a point at which the forward iteration is initiated;

f) computing a dual maxima for each node using the forward metric and the backward metric to decode said codeword; and

g) repeat steps d)-f) over entire block.

22. The invention of claim 21 wherein the step f) includes the step of log mapping.

23. The invention of claim 21 wherein the step e) includes a step of initiating a second backward iteration starting at time 3L from a point at which the forward iteration is initiated.