Viterbi decoder utilizing compressed survival metrics for reduced memory size requirements

1. A method in a Viterbi decoder for decoding received encoded bit pairs, the method comprising:

first storing in a survivor metric register file, for each received bit pair at a corresponding time instance, a survivor metric that specifies a corresponding probability of the received bit pair and a previous surviving bit sequence having been generated by a convolutional encoder according to a corresponding possible encoder state, the first storing step including selectively subtracting from each survivor metric, prior to storage thereof, by a prescribed subtraction operator based on a prescribed event, and storing the subtracted survivor metric as the stored survivor metric;

second storing in a state history table memory, for each of the received bit pairs at the corresponding time instance, a prior encoder state entry configured for identifying a surviving predecessor state relative to a corresponding encoder state; and

outputting at least one decoded bit pair based on execution of a backtracing operation that includes accessing a prescribed number of the prior encoder state entries for the respective prescribed number of time instances, the accessing including identifying one of the encoder states, stored at a corresponding first time instance, as an initial backtracing state based on having the corresponding survivor metric specifying a highest probability relative to the other survivor metrics at the corresponding first time instance.

2. The method of claim 1 , wherein the selectively subtracting step includes:

retrieving, as the prescribed subtraction operator, a maximum previous survivor path metric having been calculated during an immediate prior instance; and

subtracting from each survivor metric by the maximum previous path metric for each corresponding time instance as the prescribed event.

3. The method of claim 1 , wherein the selectively subtracting step includes:

retrieving, as the prescribed subtraction operator, a minimum positive previous survivor path metric having been calculated during an immediate prior instance; and

subtracting from each survivor metric by the minimum previous path metric for each corresponding time instance as the prescribed event.

4. The method of claim 1 , wherein the selectively subtracting step includes:

retrieving a prescribed threshold representing the prescribed subtraction operator;

detecting whether the prescribed event has occurred during the corresponding time instance based on determining whether any of the survivor metrics have exceeded the prescribed threshold during the corresponding time instance; and

subtracting from each of the survivor metrics by the prescribed threshold based on determining at least one of the survivor metrics having exceeded the prescribed threshold.

5. A Viterbi decoder including:

an add-compare-select logic circuit configured for generating, for each received bit pair at a corresponding time instance, a survivor metric that specifies a corresponding probability of the received bit pair and a previous surviving bit sequence having been generated by a convolutional encoder according to a corresponding possible encoder state, the add-compare-select logic configured for selectively subtracting from each survivor metric, prior to storage thereof, by a prescribed subtraction operator based on a prescribed event;

a survivor metric register file configured for storing the respective subtracted survivor metrics for the respective possible encoder states;

a state history table memory configured for storing, for each of the received bit pairs at the corresponding time instance, a prior encoder state entry configured for identifying a surviving predecessor state relative to a corresponding encoder state; and

a state machine configured for outputting at least one decoded bit pair based on execution of a first backtracing operation that accesses a prescribed number of the prior encoder state entries for the respective prescribed number of time instances, the first backtracing operation configured for identifying one of the encoder states, stored at a corresponding first time instance, as an initial backtracing state based on having the corresponding survivor metric specifying a highest probability relative to the other survivor metrics at the corresponding first time instance.

6. The decoder of claim 5 , wherein the add-compare-select logic circuit includes:

subtraction operator module configured for outputting the prescribed subtraction operator at the prescribed event; and

subtractor means configured for subtracting from each survivor metric by the maximum previous path metric for each corresponding time instance as the prescribed event.

7. The decoder of claim 6 , wherein the subtraction operator module includes a register configured for storing a maximum previous survivor metric having been calculated by the add-compare-select logic circuit during an immediate prior instance, the subtraction operator module outputting the maximum previous survivor metric to the subtractor means during the corresponding time instance.

8. The decoder of claim 7 , wherein the subtraction operator module includes a register configured for storing a minimum positive previous survivor metric having been calculated by the add-compare-select logic circuit during an immediate prior instance, the subtraction operator module outputting the maximum previous survivor metric to the subtractor means during the corresponding time instance.

9. The decoder of claim 7 , wherein the subtraction operator module includes:

a register configured for storing a prescribed threshold representing the prescribed subtraction operator; and

comparator means configured for detecting whether the prescribed event has occurred during the corresponding time instance based on determining whether any of the survivor metrics have exceeded the prescribed threshold during the corresponding time instance;

the subtraction operator module configured for outputting the prescribed threshold to the subtractor means, for subtraction from each of the survivor metrics by the prescribed threshold, based on determining at least one of the survivor metrics having exceeded the prescribed threshold.