Method for implementing an add-compare-select butterfly operation in a data processing system and instruction therefor

A method for performing an add-compare-select butterfly operation for implementing a Viterbi decoder in a data processing system, the method comprising the steps of:

• fetching a first previous path metric for a first state and a corresponding first trellis value during a first single clock cycle;
• fetching a second previous path metric for a second state and a corresponding second trellis value during a second single clock cycle;
• adding a branch metric to the first previous path metric to obtain a first result;
• subtracting the branch metric from the second previous path metric to obtain a second result;
• comparing the first result to the second result, and selecting which is greater to become a first survivor metric, and refetching the first previous path metric during a third single clock cycle;
• storing the first survivor metric and a corresponding first trellis state, wherein the corresponding first trellis state is determined by left shifting the first trellis value and adding a first predetermined bit to a least significant bit of the left shifted first trellis value;
• subtracting the branch metric from the first previous path metric to obtain a third result;
• adding the branch metric to the second previous path metric to obtain a fourth result;
• comparing the third result to the fourth result, and selecting which is greater to become a second survivor metric;
• and
• storing the second survivor metric and a corresponding second trellis state, wherein the corresponding second trellis state is determined by left shifting the second trellis value and adding a second predetermined bit to a least significant bit of the left shifted second trellis value.

In a data processing system, a method for use in an add-compare-select operation of a Viterbi decoding algorithm, the method comprising the steps of:

• fetching a first previous path metric and a corresponding first trellis value;
• fetching a second previous path metric and a corresponding second trellis value;
• and
• examining the first and second previous path metrics and a branch metric to determine a survivor path metric;
• moving the survivor path metric from a first memory location to a second memory location;
• left shifting the first trellis value to obtain a left shifted first trellis value;
• adding a predetermined bit to a least significant bit location of the left shifted first trellis value to determine a corresponding first trellis state;
• and
• moving the corresponding first trellis state to the second memory location.

A method for performing an add-compare-select butterfly operation in a data processing system, the method comprising the steps of:

• fetching a first previous path metric and a corresponding first trellis value;
• fetching a second previous path metric and a corresponding second trellis value;
• examining the first and second previous path metrics and a branch metric based on a predetermined calculation, to determine a first survivor path metric;
• and
• storing the first survivor path metric in a predetermined memory location, performing a logical left shift on either the first trellis value or the second trellis value, as determined by the first survivor path metric, inserting a first predetermined logic bit at a least significant bit location of the first trellis value or the second trellis value to identify a corresponding first trellis state, and storing the corresponding first trellis state in the predetermined memory location, all within a single clock cycle of the data processing system.