Metric calculations for map decoding using the butterfly structure of the trellis

1. A method of calculating branch metrics for a butterfly in a trellis of a MAP-genre decoding algorithm, the method comprising:

generating, in an electronic communication receiving device, first and second control signals by combining a butterfly index of the butterfly with polynomials describing tap positions of encoding equipment to whose operation the trellis relates;

initialising first and second branch metrics;

selecting one of the first and second branch metrics and incrementing it with a systematic sample; and

selecting one of the first and second branch metrics and incrementing it with a parity sample,

wherein the branch metric to be incremented with the systematic sample is selected by the first control signal and the branch metric to be incremented with the parity sample is selected by the second control signal.

2. The method according to claim 1 , wherein the branch metric incremented with the systematic sample is further incremented with an a priori information value.

3. The method according to claim 1 , wherein the polynomials describing said tap positions are forward and feedback polynomials and said forward and feedback polynomials are used in the derivation of said control signals.

4. A method of calculating state metrics for a trellis, the method comprising calculating first state metrics through the trellis in a first direction by a first state metric update process that, for each of at least one butterfly in the trellis, comprises calculating branch metrics for the butterfly using the method of the type claimed in claim 1 .

5. The method according to claim 4 , wherein said first state metric update process further comprises regenerating start and end states for at least one butterfly from a corresponding butterfly index or indices.

6. The method according to claim 4 , further comprising calculating second state metrics through the trellis in a second direction opposite to the first direction by a second state metric update process that, for each of at least one butterfly in the trellis, comprises calculating branch metrics for the butterfly.

7. The method according to claim 6 , wherein said second state metric update process further comprises regenerating start and end states for at least one butterfly from a corresponding butterfly index or indices.

8. The method according to claim 6 , wherein the second state metric update process, for each of at least one butterfly, comprises combining the branch metrics of the butterfly with the second state metrics of the starting states of the butterfly to produce candidate metrics for the second state metrics of the end states of the butterfly and selecting candidate metrics to become the second state metrics of the end states of the butterfly and the method further comprises combining, for each of at least one trellis stage, the candidate metrics of the stage with the first state metrics of the stage as a step in producing a log likelihood ratio for the stage.

9. A set of software instructions stored in a non-transitory computer readable medium for causing a data processing apparatus to perform the method according to claim 1 .

10. An apparatus for calculating branch metrics for a butterfly in a trellis of a MAP-genre decoding algorithm, the apparatus comprising:

means for generating first and second control signals by combining a butterfly index of the butterfly with polynomials describing tap positions of the encoding equipment to whose operation the trellis relates:

means for initialising first and second branch metrics;

means for selecting one of the first and second branch metrics and incrementing it with a systematic sample; and

means for selecting one of the first and second branch metrics and incrementing it with a parity sample,

wherein the branch metric to be incremented with the systematic sample is selected by the first control signal and the branch metric to be incremented with the parity sample is selected by the second control signal.

11. The apparatus according to claim 10 , wherein the branch metric incremented with the systematic sample is further incremented with an a priori information value.

12. The apparatus according to claim 10 , wherein the polynomials describing said tap positions are forward and feedback polynomials and said forward and feedback polynomials are used in the derivation of said control signals.

13. The apparatus for calculating state metrics for a trellis, the apparatus comprising means for calculating first state metrics through the trellis in a first direction and apparatus according to claim 10 for calculating branch metrics for said first state metric calculating means.

14. The apparatus according to claim 13 , wherein said first state metric calculation means is arranged to regenerate start and end states for at least one butterfly from a corresponding butterfly index or indices.

15. The apparatus according to claim 13 , further comprising means for calculating second state metrics through the trellis in a second direction opposite to the first direction and apparatus for calculating branch metrics for said second state metric calculating means.

16. The apparatus according to claim 15 , wherein said second state metric update calculation means is arranged to regenerate start and end states for at least one butterfly from a corresponding butterfly index or indices.

17. The apparatus according to claim 15 , wherein the second state metric calculation means is arranged to, for each of at least one butterfly, combine the branch metrics of the butterfly with the second state metrics of the starting states of the butterfly to produce candidate metrics for the second state metrics of the end states of the butterfly and to select candidate metrics to become the second state metrics of the end states of the butterfly and the apparatus further comprises means for combining, for each of at least one trellis stage, the candidate metrics of the stage with the first state metrics of the stage as a step in producing a log likelihood ratio for the stage.