US Patent 7698624 Scheduling pipelined state update for high-speed trellis processing

Methods, apparatuses, and systems are presented for extracting information from a received signal resulting from a process capable of being represented as a finite state machine having a plurality of states, wherein transitions between the states can be represented by a trellis spanning a plurality of time indices, involving calculating branch metrics taking into account the received signal, calculating state metrics at each time index by taking into account the branch metrics and using a pipelined process, wherein the pipelined process is used to calculate state metrics at a first time index, wherein the pipelined process is then used to calculate state metrics at one or more non-adjacent time indices, and wherein the pipelined process is then used to calculate state metrics at an adjacent time index, and generating at least one output taking into account state metrics for states associated with at least one selected path through the trellis.