Trellis-based decoder with state and path purging

A method for trellis-based decoding, comprising:

• receiving a signal corresponding to a sequence of symbols transmitted over a channel;
• responsive to the signal, finding respective old state metrics for one or more of the possible states of the encoding system that correspond to a given symbol in the sequence;
• determining respective transition metrics for state transitions that link the one or more possible states for which the old state metrics were found to at least some of the possible states of the encoding system that correspond to a succeeding one of the symbols in the sequence;
• computing new state metrics for the at least some of the possible states that correspond to the succeeding symbol, responsive to the respective old state metrics and to the transition metrics;
• and
• decoding the sequence of symbols based on the new state metrics,
• wherein finding the respective old state metrics comprises storing the old state metrics in a data structure comprising one or more entries, wherein each of the entries comprises a pair of state metrics of a corresponding first pair of the possible states that corresponds to the given symbol, from which a second pair of the possible states that correspond to the succeeding symbol are reached by the transitions.

Decoder apparatus, adapted to receive a sequence of samples of a signal, corresponding to a sequence of symbols encoded by an encoding system with a plurality of possible states and transmitted over a channel, wherein the encoding system output can be represented by a trellis diagram, the decoder comprising:

• a memory, adapted to store respective old state metrics, determined responsive to the samples, for one or more of the possible states that correspond to a given symbol in the sequence of symbols, each such state metric indicative of a likelihood that the corresponding state lies on a trellis path of the transmitted symbols in the sequence;
• a branch metric processor, coupled to receive the sequence of samples, and adapted to determine, responsive to the samples, respective transition metrics for state transitions that link the one or more possible states that correspond to the given symbol to at least some of the possible states that correspond to a succeeding one of the symbols in the sequence;
• at least one add-compare-select processor, coupled to receive the transition metrics and further coupled to read the old state metrics from the memory, and to compute new state metrics for the at least some of the possible states that correspond to the succeeding symbol based on the respective old state metrics and the transition metrics, such that when two or more of the transitions are linked to the same one of the possible states that corresponds to the succeeding symbol, the transition having the highest likelihood of belonging to the trellis path of the transmitted symbols in the sequence is chosen, and further adapted to select a subset of the at least some of the possible states that correspond to the succeeding symbol having the greatest likelihood of belonging to the trellis path of the transmitted symbols in the sequence, as indicated by the corresponding new state metrics;
• and
• a decision device, adapted to decode the sequence of symbols based on the selected subset.

Decoder apparatus, adapted to receive a sequence of samples of a signal, corresponding to a sequence of symbols encoded by an encoding system with a plurality of possible states and transmitted over a channel, wherein the encoding system output can be represented by a trellis diagram, the decoder comprising:

• a memory, adapted to store respective old state metrics for one or more of the possible states of the encoding system that correspond to a given symbol in the sequence;
• a branch metric processor, coupled to receive the sequence of samples, and adapted to determine, responsive to the samples, respective transition metrics for state transitions that link the one or more possible states for which the old state metrics were found to at least some of the possible states of the encoding system that correspond to a succeeding one of the symbols in the sequence;
• at least one add-compare-select processor, coupled to receive the transition metrics and further coupled to read the old state metrics from the memory, and to compute new state metrics for the at least some of the possible states that correspond to the succeeding symbol, responsive to the respective old state metrics and to the transition metrics;
• and
• a decision device, adapted to decode the sequence of symbols based on the new state metrics,
• wherein the memory is configured to store the old state metrics in a data structure comprising one or more entries, wherein each of the entries comprises a pair of state metrics of a corresponding first pair of the possible states that corresponds to the given symbol, from which a second pair of the possible states that correspond to the succeeding symbol are reached by the transitions.

Trellis decoding apparatus, comprising:

• an input buffer adapted to receive a sequence of samples of a signal, corresponding to a sequence of symbols encoded by an encoding system with a plurality of possible states;
• a trellis decoder, adapted to decode the sequence by processing a variable number of trellis states for different symbols in the sequence, thereby generating output data at a variable decoding rate;
• and
• an output buffer, coupled to receive and buffer the output data so that the data could be read out of the apparatus at a substantially constant output rate.

A method for trellis decoding, comprising:

• receiving a sequence of samples of a signal, corresponding to a sequence of symbols encoded by an encoding system with a plurality of possible states;
• decoding the sequence using a trellis decoder with a variable computational effort, thereby generating output data at a variable decoding rate;
• and
• storing the output data in an output buffer, from which the data can be read out at a substantially constant output rate.