Patent ID: 8358713

Claim:
A method for decoding a convolutionally encoded block output by an encoder and transmitted over a channel, the encoded block represented by a trellis having an initial stage and a final stage, each stage of the trellis having one or more possible states, the method comprising: receiving the block of a convolutionally encoded message at a receiver; performing Forward recursion to determine α state metrics for each stage from the initial stage to a middle of the trellis and storing the α state metrics in memory; performing Backward recursion to determine β state metrics for each stage from the final stage to the middle of the trellis and storing the β state metrics in the memory; after reaching the middle of the trellis, determining a first likelihood ratio using the stored α state metrics and currently computed β state metrics as the Backward recursion continues towards the initial stage of the trellis and simultaneously determining a second likelihood ratio using the stored β state metrics and currently computed α state metrics as the Forward recursion continues towards the final stage of the trellis; and outputting the first and second likelihood ratios; wherein the Forward recursion starts from a first bit of the received convolutionally encoded block, the Backward recursion starts from a last bit of the received convolutionally encoded block, and the Backward recursion is performed simultaneously with the Forward recursion on the same block of the received convolutionally encoded message.