Decoding signals represented by a trellis of block length N divided into windows of length L includes a step of decoding a forward recursion from a point P1 that is before the beginning of a window up to the beginning of the window and decoding a backward recursion from a point P2 that is after the end of a window back to the end of the window to define known states at the beginning and end of the window. A next step includes decoding the window using backward recursion from the known state at the end of the window back to the beginning of the window to define a set of backward recursion state metrics. A next step includes decoding using forward recursion starting from a known state at the beginning of the window and moving forward to the end of the window to define a set of forward recursion state metrics. A next step includes calculating a soft output at each stage of the window using the forward and backward recursion state metrics, and branch metrics at each stage, and outputting the soft output for that stage.