US5933462A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Soft decision output decoder for decoding convolutionally encoded codewords
Assignee: Qualcomm Inc
•
Filing: 1996-11-06
•
Granted: 1999-08-03
•
Expires: 2016-11-06
Abstract
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 0 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.
Inventors
- 👤 Andrew J. Viterbi
- 👤 Nagabhushana T. Sindhushayana
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-03 10:56
CPC Classifications
H; H03; H03M; H03M13/00; H03M13/37; H03M13/39; H03M13/3905; H03M13/3911; H03M13/29; H03M13/2957; H03M13/3972; H03M13/41; H04; H04L; H04L1/00; H04L1/004; H04L1/0045; H04L1/0047; H04L1/005; H04L1/0054; H04L1/0055; H04L1/0056; H04L1/0059; H04L1/006
Claims Analysis
Total Claims: 27
Claim 1
Independent Claim
194 words
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 0 ; 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.
Claim 2
Independent Claim
194 words
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 0 ; 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.
Claim 3
Dependent Claim
46 words
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.
Claim 4
Dependent Claim
58 words
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.
Claim 5
Dependent Claim
45 words
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.
Claim 6
Dependent Claim
57 words
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.
Claim 7
Dependent Claim
21 words
The invention of claim 1 wherein said means for performing a dual maxima computation includes means for computing a likelihood ratio.
Claim 8
Dependent Claim
23 words
The invention of claim 6 wherein said means for computing a likelihood ratio includes means for computing the log of the likelihood ratio.
Claim 9
Dependent Claim
36 words
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.
Claim 10
Dependent Claim
39 words
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.
Claim 11
Dependent Claim
31 words
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.
Claim 12
Dependent Claim
48 words
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 .
Claim 13
Dependent Claim
353 words
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 0 , 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.
Claim 14
Dependent Claim
353 words
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 0 , 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.
Claim 15
Dependent Claim
21 words
The invention of claim 12 wherein said means for performing a dual maxima computation includes means for computing a likelihood ratio.
Claim 16
Dependent Claim
23 words
The invention of claim 13 wherein said means for computing a likelihood ratio includes means for computing the log of the likelihood ratio.
Claim 17
Dependent Claim
36 words
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.
Claim 18
Dependent Claim
39 words
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.
Claim 19
Dependent Claim
31 words
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.
Claim 20
Independent Claim
167 words
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.
Claim 21
Independent Claim
167 words
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.
Claim 22
Dependent Claim
15 words
The invention of claim 18 wherein the step f) includes the step of log mapping.
Claim 23
Dependent Claim
32 words
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.
Claim 24
Independent Claim
177 words
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.
Claim 25
Independent Claim
177 words
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.
Claim 26
Dependent Claim
15 words
The invention of claim 21 wherein the step f) includes the step of log mapping.
Claim 27
Dependent Claim
32 words
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.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-08-02 | 2003-02-01 | 2003-08-03 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-08-02 | 2007-02-01 | 2007-08-03 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-08-02 | 2011-02-01 | 2011-08-03 | $7700.00 | Window Closed / Lapsed |