Generalized viterbi algorithm with tail-biting

A method of decoding L information bits convolutionally encoded in a tail-biting scheme and transmitted with each transmitted bit corresponding to a state transition, comprising the steps of:

• a) sequentially receiving the L received bits from a beginning bit to an end bit;
• b) extending the L received bits by copying E bits from the beginning of the L received bits to the end resulting in L+E received bits;
• c) constructing a trellis diagram having a L+E stages each stage having a plurality of states, with stages pertaining to consecutive time periods and also pertaining to bits received during those time periods;
• d) determining a set of connected state transitions, known as a path, through the trellis up to stage L+E which has a state at an initial stage which is equal to a state at a final stage;
• e) determining a path metric associated with the path;
• f) repeating steps "d"-"e" for a plurality of paths and path metrics;
• g) determining a path which most closely correspond to the L+E received bits indicated by the associated path metric;
• h) determining a most likely path being a set of connected state transitions through the trellis up to stage L+E which most closely correspond to the L+E received bits, and also has a state at an initial stage which is equal to a state at a final stage;
• i) tracing back the most likely path through L levels to arrive at the state x of stage E;
• j) selecting a path which ends at state x of stage L+E, known as xpath;
• k) tracing back along xpath for E levels to end on state y at stage L, state y being a more reliable state than the state at stage L+E, state y is the most likely initial state and also being the most likely final state;
• l) determining a predetermined number of candidate paths and associated path metrics for the L+E received bits each initialized with the most likely initial state and the most likely final state;
• m) decoding a selected candidate path into decoded information bits;
• and
• n) utilizing the decoded information bits to produce a desired output.