Generalized viterbi decoding algorithms

Claim 1

A method of processing a coded information sequence received from a transmitter comprising, determining the value for a metric indicative of the relative quality for each of the L (>1) best candidates to be selected as the sequence actually transmitted, wherein said candidates each correspond to paths through a trellis structure having a plurality of stages and a plurality of states at each stage, wherein each path entering each state at each stage has a partial metric associated with it, wherein said determining comprises finding the L paths through said trellis which have the highest sum of partial metrics, said determining further comprises recognizing at each stage of the trellis the L paths entering each state that have the highest cumulative metric at that stage, and retaining such recognized paths as partial paths leading to the L paths through the trellis having the largest sum of partial metrics.

Claim 2

A method of processing a coded information sequence received from a transmitter comprising, determining the value for a metric indicative of the relative quality for each of the L (>1) best candidates to be selected as the sequence actually transmitted, wherein said candidates each correspond to paths through a trellis structure having a plurality of stages and a plurality of states at each stage, wherein each path entering each state at each stage has a partial metric associated with it, wherein said determining comprises finding the L paths through said trellis which have the highest sum of partial metrics, said determining further comprises recognizing at each stage of the trellis the L paths entering each state that have the highest cumulative metric at that stage, and retaining such recognized paths as partial paths leading to the L paths through the trellis having the largest sum of partial metrics.

Claim 20

A method of processing received coded information sequences from a transmitter which received sequences correspond to respective paths through a trellis structure having a plurality of stages and a plurality of states at each stage comprising determining the value for a metric indicative of the relative quality for the best candidate to be selected as the sequence actually transmitted, and on L-1 subsequent evaluations of said metric for paths traversing the complete trellis associated with said sequences received from said transmitter, determining the metric value for the L-1 next best candidates, said subsequent evaluations comprising evaluating metrics for partial paths that remerge for the first time at a stage j of said trellis with the path for the best candidate after having diverged from said path for the best candidate, and retaining the partial paths having the best metric at stage j and discarding all others, and at the final stage selecting the path with the second best metric.

Claim 21

A method of processing received coded information sequences from a transmitter which received sequences correspond to respective paths through a trellis structure having a plurality of stages and a plurality of states at each stage comprising determining the value for a metric indicative of the relative quality for the best candidate to be selected as the sequence actually transmitted, and on L-1 subsequent evaluations of said metric for paths traversing the complete trellis associated with said sequences received from said transmitter, determining the metric value for the L-1 next best candidates, said subsequent evaluations comprising evaluating metrics for partial paths that remerge for the first time at a stage j of said trellis with the path for the best candidate after having diverged from said path for the best candidate, and retaining the partial paths having the best metric at stage j and discarding all others, and at the final stage selecting the path with the second best metric.