Patent ID: 6901117

Claim:
A method of decoding a received convolutionally coded sequence of signals represented by a trellis of block length N, comprising the steps of: a) dividing the trellis into windows; b) selecting a window of length L of the trellis; c) decoding a portion of the trellis using forward recursion from a point P that is before the beginning of the window up to the beginning of the window, wherein P is chosen at a sufficient distance from the beginning of the window such that forward recursion determines a known state metric at the beginning of the window; d) decoding the portion of the trellis within the window using forward recursion from the known state at the beginning of the window defined in step c) up to the end of the window to define a set of known forward recursion state metrics within the window, and storing the set of known forward recursion state metrics in a memory; e) decoding the portion of the trellis within the window using backward recursion starting from a known state at the end of the window and moving backward; f) calculating the soft output at each stage of the backward recursion using the backward recursion state metrics, the branch metrics, and the stored forward recursion state metrics at each stage, and outputting the soft outputs for each stage in a last-in first-out format; and g) repeating steps b) through f) downwards through the blocks and wherein the repeated steps b) through c) occur concurrently with present steps c) through f), respectively, wherein the concurrent repeated and present steps share a memory by storing forward recursion state metrics within the next window of a repeated step as the memory is cleared by the backward recursion processing during present step.