Tailbiting decoder and method

• US 6,484,285 B1
• Filed: 02/07/2000
• Issued: 11/19/2002
• Est. Priority Date: 02/07/2000
• Status: Expired due to Fees

• Current Assignee: Ericsson, Inc. (Telefonaktiebolaget LM Ericsson)
• Original Assignee: Ericsson, Inc. (Telefonaktiebolaget LM Ericsson)
• Inventors: Dent, Paul W.
• Primary Examiner(s): Decady, Albert
• Assistant Examiner(s): Chase, Shelly A
• Application Number:
  US09/499,600
• Time in Patent Office: 1,016 Days
• Field of Search: 714/786, 714/791, 714/792, 714/794-796, 752/65, 753/41
• US Class Current: 714/791
• CPC Class Codes: H03M 13/35 Unequal or adaptive error protection, e.g. by providing a different level of protection according to significance of source information or by adapting the coding according to the change of transmission channel characteristics
• CPC Class Codes: H03M 13/39 Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes
• CPC Class Codes: H03M 13/413 tail biting Viterbi decoding
• CPC Class Codes: H03M 13/6516 Support of multiple code parameters, e.g. generalized Reed-Solomon decoder for a variety of generator polynomials or Galois fields

Abstract

An apparatus and method decode information signals which have been encoded using a tailbiting error-correction codeword. The method generally includes the steps of initializing a number of decoder states corresponding to all possible starting states of the encoder to have equal associated likelihood metrics. The metrics are updated to reflect a likelihood metric for each of the decoder states given the received information signals. Further information signals, representative of further coded symbols, are received and a decoder state having the highest associated likelihood metric is extended by updating the likelihood metric to produce new likelihood metrics for each possible hypothesized extended decoded information symbol, given the further received information signals. An assumed value for the extended decoder information symbol is appended to the symbol history for the extended decoder state. The method continues to receive further information signals and to extend the decoder state having the highest likelihood metric by hypothesizing additional information symbols to produce extended decoder states until a last information symbol coded in the tailbiting codeword has been hypothesized. Final metrics are computed for each of the corresponding extended decoder states and if one of the final metrics is indicative of the highest likelihood metric, then the symbol history of the associated decoder state is used as the decoded information.

Claims

1. A method for communicating digitally coded signals, said method comprising the steps of:

grouping said digitally coded signal into symbol blocks;

error-correction coding said symbol blocks to produce coded symbol blocks for transmission;

receiving transmitted coded symbol blocks;

computing likelihood values for said symbol blocks by successively extending partial symbol blocks having a greatest associated likelihood indication and updating likelihood values associated therewith until either (a) a likelihood value for a complete symbol block is obtained, or (b) a preset processing time expires;

upon obtaining a likelihood value for a complete symbol block, reconstructing the digitally coded signal using the obtained complete symbol block; and

upon the processing time expiring, reconstructing the digitally coded signal using previous or subsequently obtained complete symbol blocks.

2. The method of claim 1, wherein the digitally coded signal is a speech signal.

3. A method for decoding information signals which have been encoded by an encoder using a tailbiting error-correction codeword, said method comprising the steps of:

initializing a number of decoder states corresponding to all possible starting states of the encoder to have equal associated likelihood metrics;

receiving information signals representative of a first number of coded symbols and updating the associated likelihood metrics for each of the decoder states given the received information signals;

receiving further information signals representative of further coded symbols and extending a decoder state having a highest likelihood metric by updating the associated likelihood metric to produce new likelihood metrics for each possible hypothesized extended decoded information symbol, given the further received information signals, and appending an assumed value for the extended decoded information symbol to a symbol history for the extended decoder state;

continuing to receive further information signals and to extend the decoder state having a highest likelihood metric by hypothesizing additional information symbols to produce further extended decoder states until a last information symbol coded in a tailbiting codeword has been hypothesized;

when the last information symbol has been hypothesized, completing computation of final metrics for each of the corresponding extended decoder states by receiving and processing all remaining information signals depending on the tailbiting codeword;

determining if one of the final metrics is indicative of a highest likelihood metric of all final and partial metrics;

if one of the final metrics is indicative of the highest likelihood metric, then using the symbol history of the associated decoder state as the decoded information; and

if a partial metric is indicative of a higher likelihood metric than any final metrics, then continuing to extend the decoder state associated with the partial metric of highest likelihood until either all partial metrics are indicative of lower likelihood than a best final metric, or else further final metrics are calculated at least one of which is indicative of a higher likelihood than previously obtained final metrics.

4. The method of claim 3, wherein the starting states are initialized to have zero metrics.

5. The method of claim 3, wherein the received signals are soft values from a signal demodulator.

6. The method of claim 3, wherein metric updating comprises:

predicting a received signal value based on re-encoding the symbol history associated with a decoder state using a local copy of said encoder;

comparing a received signal value with the predicted received signal value to produce a delta metric; and

combining the delta metric with the previous decoder state likelihood metric to produce an updated likelihood metric.

7. The method of claim 6, wherein the delta metric is zero if a sign of the predicted received signal value matches a sign of the received signal value, and wherein if the signs do not match the delta metric is a non-zero value.

8. A Stack Decoder for decoding error-correction coded information symbols, said Stack Decoder comprising:

a receiver for receiving error correction coded information symbols and producing output signals corresponding to coded symbols;

a memory for storing a number of internal decoder states, each decoder state having an associated symbol history and a cumulative metric indicative of likelihood of probability;

processing means for successively extending by one new decoded symbol the associated symbol history of the decoder state having a metric indicative of highest likelihood and computing new metrics for the extended decoder states, said processing means comprising;

an encoder re-encoding the symbol history associated with each extended decoder state to develop a predicted signal;

a probability circuit receiving the predicted signal and the receiver output signal and adding zero to the decoder state metric to obtain a new metric for the decoder state if the predicted signal and the receiver output signal have the same sign, or adding a non-zero value to the decoder state metric to obtain a new metric for the decoder state if the predicted signal and the receiver output signal do not have the same sign; and

a comparison circuit receiving the new metrics associated with each possible decoder state and choosing the decoder state having a metric indicative of highest likelihood for extension.

9. A method for decoding a received signal suffering from InterSymbol Interference (ISI), said method comprising the steps of:

estimating a number of channel coefficients indicative of the ISI using a subgroup of known symbols in the received signal;

initializing a starting state in a memory with a starting metric value;

hypothesizing a first symbol adjacent to the known symbols and combining the first hypothesized symbol with the known symbols using the estimated channel coefficients as combining weights to develop a first signal prediction;

comparing the first signal prediction with a corresponding received signal value to develop a branch metric, and combining the branch metric with the starting metric to develop a new metric associated with a new memory state;

periodically determining the state having an associated metric indicative of highest likelihood probability;

successively extending the memory state of highest likelihood probability to obtain new states by hypothesizing a next symbol in sequence;

computing metrics for the new states based on the metric of the preceding state in association with a comparison of a corresponding signal prediction with a corresponding received signal sample; and

when a final metric indicative of highest likelihood probability has been calculated, using the hypothesized symbol history of the state corresponding thereto as the decoded received signal.

10. The method of claim 9, wherein the received signal comprises a block of symbols concatenated with a cyclic extension to form a cyclic block.

11. The method of claim 10, wherein decoding terminates when at least one of the memory states is extended to encompass all symbols in the cyclic block and the associated metric for the state is indicative of a likelihood greater than that of any other state by an adequate margin.

12. The method of claim 10, wherein successively hypothesized symbols correspond to instants lying in a clockwise direction away from the known symbols around the cyclic block.

13. The method of claim 10, wherein successively hypothesized symbols correspond to instants lying in a counterclockwise direction away from the known symbols around the cyclic block.

14. The method of claim 9, wherein successively hypothesized symbols correspond to time periods later than the known symbols.

15. The method of claim 9, wherein successively hypothesized symbols correspond to time periods prior to the known symbols.

16. A method of decoding cyclically extended signal segments containing a known symbol pattern and received through a multipath channel, said method comprising the steps of:

estimating channel coefficients for a multipath channel using known symbols in the received signal segments and initializing a memory to a starting state corresponding to the known symbols;

hypothesizing unknown symbols to be decoded and generating successor states branching from the starting state, each successor state having an associated likelihood metric based on the received signal and the estimated channel coefficients combined with a symbol history of the state;

continuing to process the received signal segment, in cyclic order using a cyclic extension to wrap around an end of the signal segment to a beginning of the signal segment until processing returns once more to the known symbols; and

terminating decoding by processing signal samples associated with the known symbols a second time, and reducing the number of states after each known symbol is reprocessed until a single terminal state is reached containing the decoded symbols.

17. A method of decoding a received signal including cyclically extended signal segments containing a known symbol pattern and received through a multipath channel, said method comprising the steps of:

estimating channel coefficients for the multipath channel using a known symbols pattern in the received signal and initializing a memory to a starting state corresponding to the known symbols;

hypothesizing unknown symbols to be decoded and generating successor memory states branching from the starting memory state, each successor memory state having an associated stored likelihood metric based on the received signal and the estimated channel coefficients combined with a symbol history of the state;

periodically determining the successor memory state having the metric indicative of highest likelihood and continuing to process the received signal in cyclic order to develop new successor states branching from the state of highest likelihood using a cyclic extension to wrap around an end of the signal segment to a beginning of the signal segment until processing returns once more to the known symbols;

when all unknown symbols have been hypothesized, processing all remaining signal samples that depend on the unknown and known symbols to produce a final metric for the memory state; and

terminating decoding if any final metric is indicative of a likelihood greater than any other state'"'"'s likelihood by more than a threshold.

18. The method of claim 17, further comprising the step of:

periodically determining if any metric is indicative of lower likelihood than a final metric and, if so, deleting the state associated with the metric of lower likelihood.