Patent ID: 7116732

Claim:
A method for calculating path metric values of a convolutional encoder for use in decoding according to a Log-MAP algorithm a bit sequence encoded thereby and received through a noisy channel, the method comprising th steps of: (i) adding to a path metric value associated with a first encoder state a first transition metric value asociated with a transition of said encoder from said first encoder state to a first adjacent encoder state thereby providing a first path metric value for said first adjacent encoder state; (ii) substantially simultaneously with step (i) adding to a path metric value associated with a second encoder state concurrent with said first encoder state a second transition metric value associated with a transition of said encoder from said second encoder state to said first adjacent encoder state thereby providing a second path metric value for said first adjacent encoder state; (iii) comparing said first path metric value for said first adjacent encoder state to said second path metric value for said first adjacent encoder state and selecting a maximum of the first path metric value for said first adjacent encoder state to said second path metric value for said first adjacent encoder state to be the path metric value associated with said first adjacent encoder state; (iv) adding to the path metric value associated with said first encoder state said second transition metric value associated with a transition of said encoder from said first encoder state to a second adjacent encoder state concurrent with said first adjacent encoder state thereby providing a first path metric value for said second adjacent encoder state; (v) substantially simultaneously with step (iv) adding to the path metric value associated with said second encoder state said second transition metric value associated with a transition of said encoder from said second encoder state to said second adjacent encoder state thereby providing a second path metric value for said second adjacent encoder state; (vi) comparing said first path metric value for said second adjacent encoder state to said second path metric value for said second adjacent encoder state and selecting a maximum of the said first path metric value for said second adjacent encoder state and said second path metric value for said second adjacent encoder state to be the path metric value associated with said second adjacent encoder state; wherein said encoder states and said adjacent encoder states define a trellis butterfly and the sequence of steps (i), (ii) and (iii) are performed substantially simultaneously with the sequence of steps (iv), (v) and (vi) respectively.