Patent ID: 6868132

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 backward recursion from a point P that is after the end of the window back to the end of the window, wherein P is chosen at a sufficient distance from the end of the window such that backward recursion determines a known state metric at the end of the window; d) decoding the portion of the trellis within the window using backward recursion from the known state at the end of the window defined in step c) back to the beginning of the window to define a set of known backward recursion state metrics within the window, and storing the set of known backward recursion state metrics in a memory; e) decoding the portion of the trellis within the window using forward recursion starting from a known state at the beginning of the window and moving forward; f) calculating a soft output at each stage of the forward recursion using the forward recursion state metrics, the branch metrics, and the stored backward recursion state metrics, and outputting the soft output at each stage; and g) repeating steps b) through f) until the entire block length N is decoded, wherein the repented selecting step includes selecting a next window starting at the end of the presently selected window, and wherein the related steps b) through e) occur concurrently with present steps c) through f), respectively, wherein the concurrent repeated and present steps share a memory by storing backward recursion state metrics within the next window of a repeated step as the memory is cleared by the forward recursion processing during a present step.