Modulo arithmetic overflow control for viterbi decoder
Assignee3DSP Corporation
InventorsMichael Chen, Mike Tomlinson
Life of this patent
Estimating the term…
Abstract
A method and apparatus for controlling overflow in Viterbi decoder is disclosed. The present invention allows the metrics to use short words, and to grow freely, by the use of natural wrap-back when overflow occurs. The metric compare process monitors the occurrence of wrap-back and produces results accordingly. In accordance with one aspect of the invention, a “partial subtractions” is used for the compare processes by checking the most-significant bit of each “partial subtraction” result, instead of the carry bit, to determine the comparison result. Based on the comparison result, the metric will be selected, or updated, at the next stage.
Claims17
In a communications channel, where data are encoded and transmitted across the communication channel for reception and decoding using a multi-state trellis Viterbi decoder, a method of conducting ADD, Compare and Select routine in said Viterbi decoder, comprising:
- a. designating a range, said range being adapted to represent the maximum of differences between any two nodes of said trellis;
- b. for a node at each stage, adding a first branch metric to a first state metric and generating a first metric;
- c. if said first metric overflows said range, representing said first metric in another value within said range according to a predetermined criteria;
- d. for said node at said stage, adding a second branch metric to a second state metric and generating a second metric;
- e. if said second metric overflows said range, representing said second metric in another value within said range according to a predetermined criteria;
- f. comparing said second metric with said first metric and generating a result having an MSB section and an LSB section;
- g. if said MSB section is a first predetermined value, then updating a node at the next stage with said second metric, and if said MSB section is a second predetermined value, then updating said node at the next stage with said first metric,
- h. repeating steps b)-g) for each node and for each stage.
In a communications channel between a transmitter and a receiver, said transmitter being adapted to encode and transmit data, said receiver being adapted to receive and decode data, a method of conducting ADD, COMPARE and SELECT routine in a Viterbi decoder with a multi-state trellis having a plurality of stages of nodes, each node having a state metric selected from one of two path metrics from a previous stage, each node having two branches leading to a next stage, said method comprising the steps of:
- a. adding a first state metric to a first branch metric of a first branch, and generating a first path metric, said first branch leading to a node in a next stage;
- b. translating said first path metric, if it overflows;
- c. adding a second state metric to a second branch metric of a second branch, and generating a second path metric, said second branch leading to said node in said next stage;
- d. translating said second path metric, if it overflows;
- e. comparing said first and second path metrics, and generating a comparison result having an MSB section and an LSB section;
- f. using said MSB section to determine which one of said first and second path metrics is larger, in accordance with a predetermined criteria;
- g. updating said node in said next stage based on the larger of said first and second path metrics;
- h. repeating steps a)-g) for each node at each stage of the trellis.
A method of decoding received signals using a Viterbi decoder in a communications channel, said Viterbi decoder having a multi-state trellis, the method comprising:
- a. at a node for each stage, adding first and second state metrics to first and second branch metrics to obtain first and second path metrics, respectively, for a node;
- b. at said node for said stage, comparing said first and second path metrics to obtain a result having at least one most significant bit (“MSB”);
- c. determining which one of said first and second path metrics is larger based on said at least one MSB;
- d. selecting one of said first and path branch metrics that is larger as a state metric of said node.
Dependencies are inferred from the claim text.