Branch metric computation and add-compare-select operation in viterbi decoders

An apparatus for branch metric computation and add-compare-select operation in a rate 1/n Viterbi decoder with a constraint length of K, comprising:

• a branch metric generator receiving a data symbol including n decision metrics in Q-bit representation, for calculating a plurality of branch metrics each of which is a measure between said currently received data symbol and a corresponding branch label, and further pre-calculating a branch metric difference by subtracting a first branch metric of a transition from state Sp to state Su at instant i from a second branch metric of another transition from state Sq to state Su at instant i;
• and
• an add-compare-select unit receiving said first branch metric of said transition from state Sp to state Su, said second branch metric of said another transition from state Sq to state Su and said branch metric difference at instant i from said branch metric generator and calculating a path metric difference between a path metric of state Sp at instant i−1 and another path metric of state Sq at instant i−1, for respectively setting decision bits of states Su and Sv at instant i based on said branch metric difference at instant i and said path metric difference, comprising:
• a first adding means, according to said decision bit of state Su at instant i, for calculating a new path metric for state Su at instant i by selectively adding said another path metric of state Sq at instant i−1 and said second branch metric of said another transition from state Sq to state Su at instant i or adding said path metric of state Sp at instant i−1 and said first branch metric of said transition from state Sp to state Su at instant i;
• a second adding means, according to said decision bit of state Sv at instant i, for calculating another new path metric for state Sv at instant i by selectively adding said another path metric of state Sq at instant i−1 and said first branch metric of said transition from state Sp to state Su at instant i or adding said path metric of state Sp at instant i−1 and said second branch metric of said another transition from state Sq to state Su at instant i;
• and
• means for selectively outputting one of said new path metrics, which is a survivor path metric of a local winner state, by predetermining said local winner state between states Su and Sv at instant i based on said decision bits of states Su and Sv at instant i, and the sign of said path metric difference at instant i−1 or the sign of said branch metric difference at instant i;
• wherein states Sp and Sq at instant i−1 and states Su and Sv at instant i are organized in a butterfly trellis structure, and subscripts p, q, u and v are given by:
• p=0, 1, 2, . . . , 2K−2−1
• q=2K−2+p
• u=2p
• v=2p+1.

A rate 1/n Viterbi decoder with a constraint length of K, comprising:

• a dummy insertion unit for performing a dummy insertion procedure, which is inverse to a bit-stealing procedure in a transmitter, on a sequence of decision metrics in Q-bit representation according to a puncturing pattern and outputting a dummy insertion flag to indicate a position at which a dummy value is inserted into said decision metrics;
• a branch metric generator receiving n number of said decision metrics including said dummy value to group into a data symbol, for calculating a plurality of branch metrics each of which is a measure between said data symbol and a corresponding branch label, and further pre-calculating a branch metric difference for a pth sub-group of states including states Sp, Sq, Su and Sv by subtracting a first branch metric of a transition from state Sp to state Su at instant i from a second branch metric of another transition from state Sq to state Su at instant i, wherein said dummy value is ignored in response to said dummy insertion flag when said branch metrics are calculated for said data symbol;
• P add-compare-select units, in which a pth add-compare-select unit receives said first branch metric of said transition from state Sp to state Su, said second branch metric of said another transition from state Sq to state Su and said branch metric difference for the pth sub-group of states at instant i from said branch metric generator and calculates a path metric difference between a path metric of state Sp at instant i−1 and another path metric of state Sq at instant i−1, for setting a pair of decision bits for states Su and Sv at instant i based on said branch metric difference at instant i and said path metric difference, respectively generating new path metrics for states Su and Sv at instant i, further predetermining a local winner state between states Su and Sv at instant i based on said decision bits of states Su and Sv at instant i, and the sign of said branch metric difference at instant i or the sign of said path metric difference, and providing one of said new path metrics as output, which is a survivor path metric of said local winner state at instant i, to achieve a saving of half the output number of said new path metrics;
• and
• a survivor memory unit receiving said P survivor path metrics of said P local winner states and said P pairs of decision bits at instant i from said P add-compare-select units, for storing survivor path sequences and yielding a decoded bit sequence;
• wherein states Sp and Sq at instant i−1 and states Su and Sv at instant i are organized in a butterfly trellis structure, and subscripts p, q, u and v are given by:
• p=0, 1, 2, . . . , P−1
• q=P+p
• u=2p
• v=2p+1
• where P=2K−2.