Low complexity implementation of a Viterbi decoder with near optimal performance

A decoder for decoding an input data stream, the input data stream being encoded using the convolution encoding technique, the convolution encoding technique being represented in the decoder as a trellis, the trellis having a set of states, each state including a survivor path sequence that stores information associated with a transition from a pre-defined number of prior states to a next state, each state having a respective state metric, the decoder comprising:

• a. a branch metric computation unit for calculating a plurality of branch metrics from the input data stream based on a pre-determined criterion, each branch metric being a value associated with the transition from a prior state to a next state;
• b. an add-compare-select and register exchange (ACSR) unit for performing a pre-determined set of operations on the plurality of branch metrics, the ACSR unit storing informational bits corresponding to the survivor path sequence for a current state;
• c. a saturation control unit for updating the state metric for each current state with a new metric if at least one of the state metrics crosses a predefined limit, wherein the new metric is obtained by subtracting a constant value from the state metric;
• and
• d. a decision unit for decoding the input data stream at one of sets of prior states based on a count of assertive and de-assertive bits in the Most Significant Bits (MSBs) of survivor path sequences of a set of current states, the one of the sets of prior states being present at a pre-determined time interval from the set of the current state.

A decoder for decoding an input data stream, the input data stream being encoded using the convolution encoding technique, the convolution encoding technique being represented in the decoder as a trellis, the trellis having a set of states, each state including a survivor path sequence that stores information associated with a transition from a pre-defined number of prior states to a next state, each state having a respective state metric, the decoder comprises:

• a. means for calculating a plurality of branch metrics from the input data stream based on a pre-determined criterion, each branch metric being a value associated with the transition from a prior state to the next state;
• b. means for computing, wherein the means for computing perform a pre-determined set of operations on the plurality of branch metrics, the computing means storing informational bits corresponding to the survivor path sequence for a current state;
• and
• c. means for deciding to decode the input data stream at one of sets of prior states based on a count of assertive and de-assertive bits in the Most Significant Bits (MSBs) of survivor path sequences of a set of current states, the one of the sets of prior states being present at a pre-determined time interval from the set of the current state.

A method for decoding an input data stream, the input data stream being encoded using the convolution encoding technique, the convolution encoding technique being represented in the decoding method as a trellis, the trellis having a set of states, each state including a survivor path sequence that stores information associated with a transition from a predefined number of prior states to a next state, each prior state having a respective prior state metric, the method comprising the steps of:

• a. calculating a plurality of branch metrics from the input data stream based on a predetermined criterion, each branch metric being a value associated with the transition from a prior state to the next state;
• b. generating at least one state metric for a current state based on the plurality of branch metrics by adding a prior state metric to a branch metric defined for a transition from the prior state to the current state;
• c. checking the state metric for each current state for crossing a predefined limit;
• d. subtracting a constant value from each state metric if at least one of the state metrics crosses the predefined limit;
• e. updating the state metric corresponding to each current states with a new metric, wherein the new metric is obtained by subtracting the constant value from the respective state metric;
• f. selecting one of the prior states that provides a minimum state metric for the current state;
• g. updating the survivor path sequence of the current state, the survivor path sequence being updated based on the information associated with the transition from the selected one of the prior states to the current state;
• and
• h. decoding the input data stream at one of sets of prior states, the decoding being performed based on a count of assertive and de-assertive bits in the Most Significant Bits (MSBs) of the survivor path sequences of the set of current states, the one of the sets of prior states being present at a pre-determined time interval from the set of the current state.

A method for decoding an input data stream, the input data stream being encoded using the convolution encoding technique, the convolution encoding technique being represented in the decoding method as a trellis, the trellis having a set of states, each state including a survivor path sequence that stores information associated with a transition from a predefined number of prior states and a next state, each prior state having a respective prior state metric, the method comprising the steps of:

• a. checking a state metric corresponding to each current state for crossing a predefined limit;
• b. subtracting a constant value from each current state metric if at least one of the state metrics crosses the predefined limit;
• c. updating the state metric for each current state with a new metric, wherein the new metric is obtained by subtracting the constant value from the state metric;
• d. updating the survivor path sequence of each state based on a predetermined criteria, wherein the predetermined criteria uses the current state metrics;
• and
• e. decoding the input data stream at one of sets of prior states, the decoding being performed based on a count of assertive and de-assertive bits in the Most Significant Bits (MSBs) of the survivor path sequences of the set of current states, the one of a sets of prior states being present at a pre-determined time interval from the set of the current state.