A MAP decoder, or a turbo decoder having constituted MAP decoders, is configured with bi-directional sliding windows. A sliding window architecture is applied to the forward state metric (FSM) calculation of an encoded data block having a trellis with N time-steps. The data block is divided into smaller sub-blocks and a forward recursion of two or more of the sub-blocks are performed in parallel to obtain FSMs. Each sub-block overlaps with a previous sub-block by k time-steps, where k is an integer value greater than zero. This provides a good approximation of the FSMs at time-step k+t of the sub-block. The FSMs associated with the first k time steps of each sub-block, other than the first sub-block, are discarded. A reverse recursion of each sub-block is also performed to obtain reverse state metrics (RSM) for the sub-block. Likelihood ratios are then calculated based on the FSMs and RSMs.