Method of efficient branch metric computation for a Viterbi convolutional decoder

A method of efficient branch metric computation for a Viterbi convolutional decoder wherein a reduced and optimized set of branch metrics is distributed among one or more base sets is provided. A sequence of data transformations and associations are defined according to the connections of the delay elements in the convolutional encoder to its outputs. Each encoder state is associated with one of the base sets and one of several groups of path metric equations. During the add portion of the add-compare-select phase of Viterbi decoding, a branch metric value is extracted from the base set associated with the encoder state being evaluated. The group of path metric equations associated with state being evaluated are evaluated using the extracted branch metric value. The results of the addition are then be processed according to the remaining steps of the Viterbi algorithm.

TECHNICAL FIELD 
This invention is related to the branch metric computation in the Viterbi 
algorithm on a general purpose digital signal processor. 
BACKGROUND OF THE INVENTION 
In wireless and wireline applications, particularly those with significant 
intersymbol interference, error detection and correction is performed 
using convolutional encoding and Viterbi Decoding. Convolutional encoding 
is performed by convolving a data input bit to hardware or software 
encoder with one or more previous input bits. An example of a conventional 
IS-95 rate 1/2, constraint length 9 convolutional encoder 10 is shown in 
FIG. 1a. The information bits are input to a series of delay elements 12 
such as a shift register that is tapped at various points. The tapped 
values are combined by an XOR function 14 to generate encoded data 
symbols. In the example encoder 10, two output bits, c.sub.0 and c.sub.1, 
are generated for every input bit. Thus, this encoder has a rate of 1/2. 
The constraint length represents the total span of values used by the 
encoder and is represented by the symbol K. A constraint length K=9 means 
that there are 2.sup.(9-1) =256 encoder states (since the ninth bit is the 
input bit). These states are designated represented as state S.sub.0 
(decimal 0, binary 00000000) to state S.sub.255 (decimal 255, binary 
11111111). 
FIG. 1b illustrates a typical application environment using convolutional 
encoding and Viterbi decoding. Source data 5 is input to convolutional 
encoder 10. Encoded data is output as a sequence of data symbols 20 which 
are formatted appropriately and transmitted over a communications link 22. 
The communications link 22 introduces noise into the data signal and 
therefore the transmitted data symbols may be corrupted by the time they 
reach their destination. Each received (and possibly corrupted) data 
symbol 24 is processed by a convolutional decoder 26 to generate decoded 
data 28 which corresponds to the most likely sequence of source data 5. 
The received data signals 24 are processed according to the Viterbi 
algorithm. The basis of the Viterbi algorithm is to decode the 
convolutionally encoded data symbols by using knowledge of the possible 
encoder state transitions from one given state to the next based on the 
dependance of a given data state on past data. The allowable state 
transitions are typically represented by a trellis diagram. The Viterbi 
algorithm provides a method for minimizing the number of state paths 
through the trellis by limiting the paths to those with the highest 
probability of matching the transmitted data sequence based on the 
received sequence. 
FIG. 2 is an illustration of the basic Viterbi algorithm butterfly 
computation. Four possible encoder transitions from a present state (PS) 
to a next state (NS) are illustrated, where the present state is 
equivalent to the numeric value of the data stored in the K-1 delay 
elements 12 of the encoder 10. When a bit is input to the encoder, the 
binary value is shifted to the right and the input bit is moved into the 
most significant bit position (shown in bold in the next state). As 
illustrated, NS.sub.0 can be reached with a 0 input bit from either 
PS.sub.0 or PS.sub.1. Similarly, NS.sub.128 can be reached with a 1 input 
bit from either PS.sub.0 or PS.sub.1. The Viterbi algorithm provides a 
process by which the most likely of the two possible transition paths can 
be determined and subsequently selected as the "survivor" path. Once a 
sequence of survivor paths has been determined, the most probable data 
input sequence can be reconstructed, thus decoding the convolutionally 
encoded data. 
This determination consists of three basic steps. In the first step, the 
received data symbol, typically an 8 or 16 bit digital value representing 
the magnitude of voltage or current of an input signal, is processed to 
determine the Euclidean distance between the received data symbol and all 
possible actual data symbols, uncorrupted by noise, which could result 
from a state transition from the present to a next state. This is known as 
a branch metric computation, the results of which are stored in memory for 
use during the next step. The branch metric computation provides a 
measurement of the likelihood that a given path from a present state to a 
next state is correct. The branch metric m for a transition from present 
state i to next state j at instant k may be represented as: 
##EQU1## 
where x.sub.n (k) is the received nth data symbol, C.sub.n,ij is the 
actual data symbol which would result from state transition of i to j in 
the absence of any transmission noise and is determined from the structure 
of the convolutional encoder, and the rate is 1/R. For a rate 1/R encoder, 
there are two possible encoder state transitions and therefore two branch 
metrics must be computed for each next state. Only the relative magnitudes 
of various branch metrics are important in Viterbi decoding. Since the 
same input data symbol is processed in each branch metric, the term 
.SIGMA.x.sub.n.sup.2 is the same for all states i and j and can therefore 
be removed. Further, .SIGMA.c.sub.n,ij.sup.2 is constant if a polar 
representation is used (i.e., a value of c.sub.n,ij =0 or 1 corresponds to 
-1 or +1 respectively). Removing these terms (and the leading -2 scaler 
value) results in a reduced Euclidean branch metric of: 
##EQU2## 
Thus, decoding data signals from a convolutional decoder of rate 1/R with 
a constraint length of K requires determining a total of 2.sup.K metrics 
values for each data input symbol. As used herein, the set of 2.sup.K 
metrics values is defined as the complete branch metric set for a 
particular data input symbol. 
One important property of a class of convolutional encoders commonly used 
is that the second half of the branch metric values are negatives of the 
first half. Thus, in FIG. 2, m.sub.0,128 =-m.sub.0,0 and m.sub.1,128 
=-m.sub.0,128. Therefore, only half of the branch metric set for a given 
data input symbol must be explicitly calculated by the decoder during 
Viterbi decoding. 
In the second step, the previously stored branch metric values for all 
possible state transitions are processed to determine an "accumulated 
distance" for each input path. The path with the minimum distance (i.e., 
maximum probability) is then selected as the survivor path. This step is 
known as Add-Compare-Select, or ACS. The ACS operation can be broken into 
two operations: (1) the Add operation, or path metric computation, and (2) 
the Compare-Select operation. The path metric Add operation is the 
accumulation of the present state cost (a value initialized by the user at 
the start of the Viterbi processing) with the branch metric values for a 
received data input symbol. As shown in FIG. 2, the two path metric 
operations for next state 00000000 are: 
EQU PS.sub.0 +m.sub.0,0 and PS.sub.1 +m.sub.1,0 (Equ. 3) 
The path metric operations for next state 10000000, since the second half 
metrics are the inverse of the first half, can be written as: 
EQU PS.sub.0 -m.sub.0,0 and PS.sub.1 -m.sub.1,0 (Equ. 4) 
The decoder computes and compares two values from the Add operation to 
determine the minimum (or maximum, depending on implementation) and stores 
one or more "traceback bits" to indicate the selected survivor path. 
The third step is known as traceback. This step traces the maximum 
likelihood path through the trellis of state transitions, as determined by 
the first two steps, and reconstructs the most likely path through the 
trellis to extract the original data input to the encoder. In this 
example, the survivor path is represented by the least significant bit of 
the present state, i.e., the traceback bit (shown in bold in FIG. 2). For 
example, if the path from present state S.sub.1 is chosen over the path 
from present state S.sub.0, the traceback bit is 1. Various methods of 
processing traceback data to determine the original data input to the 
encoder are well known to those skilled in the art. 
Because Viterbi decoding is so prevalent in digital signal processing 
applications, it is important that the convolutional decoder be able to 
process the Viterbi algorithm quickly and efficiently. Conventional 
implementations comprise a programmable digital signal processor and a 
decoder algorithm that computes all 2.sup.K metrics for a given data input 
symbol 24 at the start of a decoding process and stores the entire branch 
metric set in memory. However, this brute force technique requires a 
minimum of 2.sup.K calculations and thus can consume a comparatively large 
number of machine cycles. Further, storing the entire table can consume a 
relatively large amount of memory. Although conventional techniques 
achieve some reduction by storing only the first half of the branch metric 
values, since the second half is simply the inverse of the first half, 
there is still a great deal of redundancy in the metric data, resulting in 
a waste of storage area. 
According to the present invention, efficient branch metric computation for 
a Viterbi convolutional decoder is provided by processing a received data 
symbol to generate a reduced set of branch metrics for an encoder of 
constraint length K, instead of the entire set of 2.sup.K metrics, and 
storing the reduced set in memory for use in the Viterbi processing. The 
reduced metric set comprises a kernel of the unique metric values for a 
present data input symbol which exist in the complete metric set and may 
also include a small subset of precalculated metric values from the 
complete set. A sequence of K basic data transformations is defined 
according to the physical structure of the convolutional encoder and used 
to eliminate redundances in the complete metric set. By applying these 
transformations to the kernel metric values, all 2.sup.K metrics can be 
extrapolated. 
The reduced metric sequence for a data input symbol is stored in memory as 
one or more reduced base sets of metric values and a sequence of base set 
and polarity associations used during the add-compare-select (ACS) step of 
Viterbi processing. During the ACS operation, the branch metric value 
required for each state calculation is retrieved from the associated base 
set and a particular set of path metric operation is chosen or the sign of 
the retrieved branch metric value is calibrated according the to the 
associated polarity. This method of reducing the number of branch metrics 
which must be calculated and stored for each data input symbol results in 
a substantial savings in the number of cycles required to calculate the 
complete branch metric set as well as in the amount of storage required to 
store the predefined branch metric values.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT(S) 
According to the present invention, efficient branch metric computation for 
a Viterbi convolutional decoder 26 is achieved by first deriving a set of 
data transformations based on the physical structure of the convolutional 
encoder 10. These transformations are used to reduce the complete set of 
branch metric values needed to process a given data input symbol to a 
small number of base sets housing a subset of the complete branch metric 
set and a sequence of ACS associations which control how branch metric 
data stored in the base sets is used during the add-compare-select 
sequence of the Viterbi algorithm. 
The first step in reducing the branch metric set according to the present 
invention is to generate the K data transformations for the convolutional 
encoder 10 having constraint length K. The transformations (and 
associations, discussed below) are derived according to the presence of 
delay operators in the convolutional encoder that act on the digit 
positions of a data signal prior to encoding and the effect of these delay 
operators on the convolutionally encoded data output from the encoder. 
The physical or logical delay and output structure of a convolutional 
encoder 10 may be described by one or more polynomials. For the encoder of 
FIG. 1a, the representative polynomials are: 
EQU g.sub.0 =1+d+d.sup.2 +d.sup.3 +d.sup.5 +d.sup.7 +d.sup.8 (Equ. 5) 
EQU g.sub.1 =1+d.sup.2 +d.sup.3 +d.sup.4 +d.sup.8 (Equ. 6) 
where each delay operator d acts on a historic digit of the data to be 
encoded and may be implemented by a shift operation or through software. 
The input bit and the last delay state of a conventional 1/R encoder of 
constraint length K is always connected to the output XOR function. Thus, 
the representative polynomials are always of form g=1+ . . . +d.sup.K-1, 
where d.sup.K-1 is the output of the last delay state in the shift 
register. 
Input data shifted through an encoder 10 affects the encoded output bits 
depending on both on the value of the input data digit in the delay 
element 12 (i.e., a "0" or a "1" for binary data) and which delay elements 
12 are actually tapped to generate the output 14. In the (artificial) 
situation when the output 20 of the encoder 10 is evaluated for each 
encoder state in turn with both a 0 and a 1 input bit, delay elements 12 
do not effect the output until a "1" data value is stored in them. So, for 
example, the last delay element 12 in FIG. 1a, element d.sup.8, has an 
effect beginning with encoder state 1 since 0 is high. The effect of delay 
element d.sup.7 begins with encoder state 2, when bit 1 is high, and is 
the highest order delay state that has an effect until encoder state 4, 
when the effect of delay element d.sup.6 is introduced since bit 2 is 
high. Delay element d.sup.6 is the highest order delay state for states 
4-7, and so on. 
The set of sequential encoder states during which a given bit of the 
encoder state is the highest order state with an effect on the output is 
defined herein an encoder "stage." Thus, stage 2 corresponds to encoder 
states 4-7 since bit 2 is the highest order bit for these encoder states. 
Since the sequence of lower order bits in the binary representation of the 
encoder state repeats as each higher order bit is set in turn, the pattern 
of output bits for each stage can determined by transforming the pattern 
of previous output bits in accordance with how the delay element at the 
given stage affects the encoded data output. 
When the encoder is initialized to state 0 with a 0 input, it will always 
have an initial output of 0 for all output functions. The pattern of the 
output bits at each stage k, k=K-1 to 0 for each polynomial at the 
2.sup.K-1-k subsequent sequential states within that stage is: 
(a) the output bit sequence is the same as that for the previous 
2.sup.K-1-k sequential states if there is no connection to the function's 
XOR gate at that stage (i.e., the d.sup.k delay term is absent from the 
representative polynomial); and 
(b) the output bit sequence is the complement of that for the previous 
2.sup.K-1-k sequential states if there is a connection to the function's 
XOR gate at that stage (i.e., the d.sup.k th term is present in the 
polynomial). 
This pattern is used to produce a concise sequence of data transformations 
which can be applied to a reduced subset of metrics for a given received 
data symbol 24 to thereby generate the complete 2.sup.K branch metric set 
required to process the data symbol 24. 
To discuss producing the data transformations, it is useful to expand Equ. 
2 (above) for an encoder of rate 1/2. The result is the basic branch 
metric equation which is used during the processing of data symbols 24 in 
a Viterbi decoder 26: 
EQU m=x.sub.0 c.sub.0 +x.sub.1 c.sub.1 (Equ. 7) 
In polar form, the values of c.sub.0 and c.sub.1 are either -1 
(corresponding to a "0" value) or +1 (corresponding to a "1" value). 
Therefore, there are only four possible branch metric values, two of which 
are compliments of the other two. Thus, only two unique metric values, 
here identified as M.sub.0 and M.sub.1, must be determined for an input 
symbol. For convenience, M.sub.0 is defined as equal to -x.sub.0 -x.sub.1, 
and M.sub.1 is defined as equal to x.sub.0 -x.sub.1. As can be 
appreciated, these definitions are somewhat arbitrary and other 
definitions are also possible. For example, M.sub.1 could also be defined 
as being equal to -x.sub.0 +x.sub.1. The unique metric values (here 
M.sub.0 and M.sub.1) comprise the kernel of the complete set of branch 
metric values. 
This analysis will now be applied to the encoder of in FIG. 1a with a 
branch metric of Equ. 7. An input bit of 0 in state 0 (i.e., all stages 12 
of the shift register are "0"), results in output of 00, and therefore 
(using polar representation) the branch metric value is M.sub.0. (This 
definition is valid for all encoders of this class since, in this state, 
the initial output bits for a zero input will always be 00). For stage 
zero, i.e., encoder state 2.sup.0 =1, the output bits are 11, the 
complements of both bits in the previous 2.sup.0 =1 state because there is 
a connection to the XOR gates for g.sub.0 and g.sub.1 at the least 
significant bit. In other words, the polynomials of Equs. 5, 6 for g.sub.0 
and g.sub.1 both contain the d.sup.8 term, corresponding to bit 0 of the 
encoder state. This is true for every encoder of this class because the 
d.sup.K-1 term is always present. Because this value is a compliment of 
the previous value, the branch metric is -M.sub.0. 
The output bits for stage 1, covering the next 2.sup.1 states (i.e., states 
2-3), can be similarly generated by examining connections to the seventh 
delay element (i.e. the d.sup.7 polynomial terms). This term only exists 
in the equation for g.sub.0 and therefore the 7th delay state only affects 
the c.sub.0 output bit. Thus, the data transformations for stage 1 is that 
outputs for states 2 and 3 are equal to the outputs for states 0 and 1, 
with the first bit complemented. Transformations for the remaining states 
are similarly generated. The K data transformations for the convolutional 
encoder of FIG. 1 are summarized in the table of FIG. 3. The application 
of these transformations to the first 16 outputs of the encoder of FIG. 1a 
and the corresponding branch metric values is summarized in the table of 
FIG. 4. 
Once a set of data transformations for a given convolutional encoder are 
derived, they can be used to generate a substantially reduced data set of 
branch metric values comprising one or more base sets of metric values 
derived from the input data symbol and a sequence of ACS associations. 
Every branch metric value for each of the 2.sup.K-1 states needed during 
the add-compare-select operation of the Viterbi algorithm can be retrieved 
from the base sets with a minimum computational cost. Although only one 
base set is required, for a rate 1/2 encoder, two base sets are preferably 
used. 
According to the method of the present invention, the desired length L of 
the reduced one or more branch metric base sets must be chosen. The set 
size L should be a power of 2 in length, with a minimum length of 1 (if 
two or more sets are used), a minimum length of 2 if only one set is 
utilized, and a maximum length equal to the number of elements in the 
branch metric set, 2.sup.K. Each base set is preferably the same length. 
The smaller the set size, the fewer branch metric values which must be 
stored in memory but the greater the number of ACS associations which are 
necessary. However, as discussed below, an increase in the number of ACS 
associations will increase program complexity, but will not increase the 
execution time of the Viterbi ACS operation. Preferably, the set length L 
is equivalent to the length of the register used to store the traceback 
bits generated during ACS to simplify programming. In the preferred 
embodiment, the traceback register is 16 bits in length and the reduced 
set size L is therefore 16. Since two base sets are used in the preferred 
embodiment, only 32 metric values must be generated for an input symbol 
out of the complete set. 
Once the length L of the base data sets is chosen, the sequence and sign of 
kernel metric values that will be stored within the base data sets is 
generated. When the method according to the present invention is executed, 
the base sets will be populated with actual branch metric values generated 
by processing an input data symbol 24. This is discussed below. 
The first base data set is populated with a sequence of ordered branch 
metric values which here correspond to a set of 2L state metrics. In the 
preferred embodiment, the first L even state metrics are chosen. One 
method of generating this sequence is by applying the first log.sub.2 
(L)-1 data transformations derived for the convolutional encoder 10. For a 
base set size L=16, the first 32 metrics can be computed by applying the 
first 5 transformations (since 2.sup.5 =32), starting at the initial state 
of all zeros. For the transformations shown in FIG. 3 and 4, the sequence 
of branch metric values for base set 1 is: 
M.sub.0, M.sub.1, M.sub.0, M.sub.1, M.sub.1, M.sub.0, M.sub.1, M.sub.0, 
-M.sub.1, -M.sub.0, -M.sub.1, -M.sub.0, -M.sub.0, -M.sub.1, -M.sub.0, 
-M.sub.1 
Because the odd state metrics are always the inverse of the immediately 
preceding even state metric for this class of encoders, for example, as 
shown in FIG. 4, m.sub.1,0 =-m.sub.0,0, the sequence of metrics in base 
set 1 completely describes the sequence of the first 2L branch metric 
values. Other sets of ordered state metrics, e.g., the last L odd metrics 
could also be chosen. 
When two base sets are used, the contents of the second data set, i.e., 
base set 2, is derived from the first data set by replacing +M.sub.0 set 
entries with +M.sub.1 and -M.sub.0 set entries with -M.sub.1. Base set 2 
of the preferred embodiment will therefore contain the metric values in 
the sequence: 
M.sub.1, M.sub.0, M.sub.1, M.sub.0, M.sub.0, M.sub.1, M.sub.0, M.sub.1, 
-M.sub.0, -M.sub.1, -M.sub.0, -M.sub.1, -M.sub.1, -M.sub.0, -M.sub.1, 
-M.sub.0 
Base set 2 is derived in this manner because there are only four possible 
transformations for the two output bits C.sub.0, C.sub.1, of 1/2 encoder: 
compliment C.sub.0, compliment C.sub.1, compliment both C.sub.0 and 
C.sub.1, or do nothing. These transformations correspond to the physical 
connections in the encoder which define g.sub.0 and g.sub.1. As shown in 
FIG. 4, if both C.sub.0 and C.sub.1 are complimented, the resulting metric 
value is simply the inverse of the original. For example, C.sub.0 C.sub.1 
=00 is metric M.sub.0. Inverting both bits results in C.sub.0 C.sub.1 =11, 
equal to metric -M.sub.0. Thus, applying this transformation will not 
alter the specific M.sub.0, M.sub.1 sequence, but only switch the signs of 
the metric values. If the data transformation only compliments the first 
bit, however, +M.sub.0 entries are replaced with +M.sub.1 and -M.sub.0 
entries become -M.sub.1. If only the second bit is complimented, the 
+M.sub.0 entries become -M.sub.1 and -M.sub.0 entries become +M.sub.1. 
Thus, the data sequence of base set 1 and base set 2 combined provide the 
proper pattern of M0.sub.0, M.sub.1 metric entries for every sequence of 
2L metrics in the entire set, but differing sometimes only in the sign of 
the metric values. 
As defined herein, base set 2 is the branch metric compliment of base set 
1. A similar branch metric compliment relationship can be derived for 
encoders with rates other than 1/2 as will be apparent to those skilled in 
the art. The sequence of values for C.sub.0 and C.sub.1 and the 
corresponding metrics for base sets 1 and 2 are summarized in FIGS. 5a and 
5b, respectively. According to the preferred embodiment, two branch metric 
compliment base sets are utilized to limit the number of pointer registers 
which must be used during the decoding process, discussed below. However, 
as will be apparent to those skilled in the art, the method according to 
the invention may also be practiced with only a single base set, with a 
small increase in program complexity and/or hardware requirements. 
According to the invention, once the base sets have been populated with the 
actual branch metric values in the prescribed sequence, the proper metric 
value for any state can be determined by selecting the appropriate entry 
in the one or more base sets and then adjusting the sign of the metric 
value appropriately. The proper set to use and sign to apply for a 
particular encoder state are determined by the ACS associations for that 
state, the generation of which will now be discussed. 
During ACS processing, the operations PS.sub.0 +m.sub.0,0 and PS.sub.1 
+m.sub.1,0 must be evaluated by the decoder 26. Because the odd state 
metrics are the inverse of the immediately preceding even state metric, 
for example, as shown in FIG. 4, m.sub.1,0 =-m.sub.0,0, the two ACS 
addition operations can be reduced to: 
EQU PS.sub.0 +m and PS.sub.1 m (Equ. 8) 
where m is the appropriate value of the branch metric to use. The ACS 
associations link a given state to the base set from which the metric 
value m is taken and the polarity of the addition (e.g., whether the sign 
of the retrieved m should remain the same or be inverted). 
The two operations of Equ. 8 are defined herein as a positive polarity ACS 
addition group. A negative polarity group is one in which the sign of the 
retrieved metric m should be reversed. This is preferably accomplished not 
by changing the sign of m, but instead by reversing the ACS additions in 
the positive polarity group to form a negative polarity ACS addition group 
containing the operations: 
EQU PS.sub.0 -m and PS.sub.1 +m (Equ. 9) 
Those skilled in the art will recognize that more than two ACS addition 
groups may be required for encoder rates other than 1/R and that 
alternatively, only one ACS addition group be used and the sign of the 
retrieved metric m altered instead. The use of "positive" and "negative" 
to distinguish between the different ACS addition groups is for 
convenience only and is not intended to limit the number of possible 
groups used with encoders of different rates. 
The ACS associations are derived by dividing the complete branch metric set 
into segments of length 2L. An initial association is then defined and the 
last K-log.sub.2 (L)-1 transformations, i.e., those which were not used to 
derive the base sets, are evaluated in turn to recursively determine how 
the first 2L metrics (e.g., those represented by base set 1) are modified 
when the data transformations are applied. This process will associate 
each of the 2.sup.K /2L segments with a base set and a polarity. 
The first ACS association for a 1/2 rate encoder with two base sets deemed 
covers segment 1 (i.e., the first 2L, metrics). By default, this segment 
is associated with base set 1 with a positive polarity because the initial 
2L metrics are directly encoded in base set 1 and have the proper signs. 
This association is referred to as "Set 1/Positive." Each remaining ACS 
association is recursively derived from prior associations according to 
how C.sub.0 and C.sub.1 are modified by the data transformations that 
apply to the segment at issue. 
The second ACS association, covering segment 2, is derived from the data 
transformation used to generate the second 2L metric values. If both 
C.sub.0 and C.sub.1 are complimented, the base set association remains the 
same but the polarity of the ACS addition group to evaluate is switched 
for the reasons discussed above with respect to the derivation of the base 
set sequence. If only C.sub.0 is complimented, the associated base set is 
switched, but the polarity remains the same. If only C.sub.1 is 
complimented, both the base set association and the polarity are switched. 
Finally, if there is no transformation, such as for states 4-7 in FIGS. 3 
and 4, the ACS association for the segment does not change. Because of the 
recursive and exponential nature of the data transformations, each 
transformation must be applied to all of the preceding ACS associations to 
generate the next set of associations. Thus, the number of ACS 
associations doubles at each step. 
The ACS associations for the preferred embodiment of two base sets of size 
L=16 for the encoder of FIG. 1 will now be derived. The associations are 
summarized in FIG. 5c. As discussed above, base set 1 covers metrics 0-31 
and the first ACS (default) association for segment 1 is "Set 1/Positive". 
The data transformation for the next 2L metrics, numbers 32-63, 
compliments both output bits. Thus, the ACS association for segment 2 is 
"Set 1/Negative". The third data transformation also compliments both 
bits, but, since it applies to the next two segments of 2L metrics each, 
numbers 64-127, it is recursively applied to the ACS associations for the 
first and second segments to generate the ACS associations fo the third 
and fourth segments. Applying this transformation to the first ACS 
association gives "Set 1/Negative" as the third ACS association. Applying 
this transformation to the second ACS association gives "Set 1/Positive" 
as the fourth ACS association. The data transformation for metrics 128-255 
compliments C.sub.0. Thus, the next set of ACS associations be the first 
ones with switched base sets but the same polarity. Finally, the last 
transformation (for metrics 0-255 with a 1 input) compliments both C.sub.0 
and C.sub.1. Thus, the last eight ACS associations will be the first eight 
with inverted polarity. 
According to the invention, the base set sequences shown in FIGS. 5a and 5b 
and the ACS associations of FIG. 5c can be used to derive the proper 
branch metric value for any encoder state. To extract the metric value m 
for a given encoder state, the segment encompassing the state and the 
position of the state within the segment is determined. One method of 
doing this is with a modulus L function. Alternatively, the values may be 
directly coded or retrieved from look-up table. The segment the state is 
in determines the base set and polarity associations, defined by the ACS 
associations. The position within the segment determines which of the L 
values in the associated base set to extract. 
For example, state 8 is in segment 1 which is associated with base set 1. 
Thus, the ninth entry in base set 1, -M.sub.1, is the metric value for 
state 8. (The base sets are numbered starting at 0). Since the polarity 
for this state is positive, the sign of retrieved metric value is correct. 
State 88 is in segment 6. The ACS association for this segment is "Set 
2/negative." Thus, the ninth entry from base set 2 is used. The value is 
-M.sub.0. However, since the associated polarity is negative, the sign of 
the retrieved value must be switched. Preferably, this is accomplished by 
using the negative ACS addition group. As an alternative to providing a 
set of ACS addition groups of different polarity and selecting a 
particular ACS additions group according to the polarity association, the 
sign of the retrieved branch metric value may instead be calibrated by 
explicitly altering its sign when the associated polarity is negative. In 
this alternative implementation, only one set of path metric operations is 
required, e.g., Equ. 8. 
The method of branch metric reduction and Viterbi processing according to 
the invention is summarized in the flow charts of FIGS. 6a and 6b. The 
first step according to the present invention is to generate the K data 
transformations for the convolutional encoder of constraint length K 
according to the connections between the outputs and the delay elements. 
(FIG. 6a, Step 100). After the data transformations for a given 
convolutional encoder 10 are derived, they are used to generate the 
reduced data set pattern for branch metric values to store in one or more 
base sets of computed metric values and the ACS associations. The desired 
length L of the one or more branch metric base sets is chosen (Step 102) 
and the sequence of data that will be stored within the first base sets is 
generated. (Step 103). If more than one base set is used, the sequence of 
data for the remaining base sets is also generated. When two base sets are 
used, the second base set has a sequence which is the branch metric 
compliment of the first base set. (Step 104). Once the sequence of base 
set data has been established, the ACS associations between encoder states 
and the base sets and metric polarity are established. (Step 105). 
By default, the initial association is "Set 1/positive". (Step 106). The 
remaining association are defined by applying the data transformations to 
the previously defined associations to generate the next set of 
associations. The method of applying the transformations to determine the 
proper associations as discussed above is summarized in steps 200-214. 
According to the invention, the Viterbi branch metric computation comprises 
determining the kernel metric values M.sub.0 and M.sub.1 related to a 
given data input symbol (Step 110). These values are then used to generate 
a sequence of data according to the previously defined branch metric 
sequences which is stored in memory to form the base sets. (Step 112). 
Once the branch metric computation of the Viterbi algorithm is completed, 
the ACS sequence for the input data symbol must be performed. According to 
the present invention, all 2.sup.K metric values which must be processed 
by the decoder 26 during the Viterbi ACS sequence for states 0 to 
2.sup.K-1 are determined by using only the metrics values stored in base 
sets and the ACS associations. FIG. 6b illustrates a sequence of 
extracting the proper branch metric value from the base sets during the 
ACS portion of the Viterbi algorithm. This sequence is discussed herein as 
two nested loops. However, this representation is for convenience and 
other implementations that do not use nested loops are also possible as 
discussed below. 
The outer loop (from step 120 to step 144) steps through each of the 
segments S in turn. For each segment, the proper base set and polarity are 
determined from the corresponding ACS association. (Step 122). The 
polarity is examined (step 124) and the result used to select the proper 
ACS addition group to evaluate, i.e., positive polarity (step 126) or 
negative polarity (step 128) (Equations 8 and 9 respectively). 
The inner loop (from step 132 to step 142) performs the ACS operation of 
the Viterbi algorithm for each of the L ACS states corresponding to the 2L 
metrics in the current segment S using the selected ACS addition group. 
According to the invention, during the first execution of the inner loop 
for the current segment, the proper value of the branch metric m to use in 
evaluating the selected ACS addition group is the first metric value in 
the appropriate base set. Preferably, this value is selected by a pointer 
(step 134) which was initialized to the base address of set one or two 
when the inner loop was entered. (Step 130). In an alternate embodiment, 
the retreived branch metric value is calibrated according to the polarity 
instead of using the polarity to select a one of the ACS addition groups. 
(Not shown). 
The ACS Add operations in the selected group are then evaluated using the 
retrieved value of m. (Step 136). The remaining compare and select 
functions of the ACS operation are then executed using conventional 
techniques and the traceback bit is determined and stored. (Step 140). The 
base set pointer is then incremented (step 140) and the inner loop 
repeats, using each entry in the appropriate base set in turn (step 142). 
Those skilled in the art will recognize that the pointer value can be 
updated at any time after metric m is extracted from the base set. 
After the inner loop has evaluated all L ACS states for the particular 
segment, the program determines if all the segments have been processed 
(step 144). If not, the next segment S is selected (step 146) and the 
outer loop is repeated (starting at step 122). Once the ACS sequence for 
all segments has been executed, the stored traceback data can be used to 
extract the decoded data according to various techniques well known to 
those skilled in the art. 
Those skilled in the art will recognize that the ACS method illustrated in 
FIG. 6b may be implemented in many different ways. In particular, the 
selection of the proper base set and of the ACS addition group according 
to the ACS associations may be implemented "on the fly." Alternately, the 
outer and inner loops can be "merged" by directly coding the proper base 
set and addition group associations in several discrete segment-specific 
"inner" loops. In the preferred embodiment, the proper ACS associations 
are determined in advance and expressly coded in 2.sup.K /2L discrete 
inner loops, one for each of the 2.sup.K /2L segments. FIG. 7 is a listing 
of pseudo code for the Viterbi algorithm of the preferred embodiment. This 
algorithm incorporates the base set sequences and ACS associations as 
defined in FIGS. 5a,b, and c. The directly coded ACS associations are 
indicated in bold text. 
Those skilled in the art will recognize that the exact sequence of 
operations and method of coding may be varied without departing from the 
spirit and scope of the invention. Further, although the method of 
efficient branch metric computation for a Viterbi convolutional decoder of 
the present invention is discussed with reference to a IS-95 Rate 1/2, 
constraint length 9 convolutional encoder, the method is equally 
applicable to other 1/2 convolutional encoders. Those skilled in the art 
will also recognize that this invention can be applied to generic 
convolutional encoders of rate 1/N by defining the 2.sup.N-1 unique kernel 
metrics appropriately and adjusting the base set definitions and ACS 
associations as necessary. The method of the present invention can be also 
be applied to a generic M/N convolutional encoder by treating the encoder 
as M 1/N encoders operating in parallel.