Method and apparatus for decoding a bit sequence

A method for calculating Log-Likelihood Ratio values for state transitions 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 the steps (i) to (iii) which are performed in respect of only those transitions corresponding with a parity bit of a first value, and steps (iv) to (vi) which are performed in respect of only those transitions corresponding with a parity bit of a second value:

• (i) adding to a forward path metric value associated with a first encoder state of a given trellis butterfly a first transition metric value associated with a forward transition of said encoder from said first encoder state to a first adjacent encoder state of said butterfly;
• and, the backward path metric value associated with said first adjacent encoder state to provide a first sum;
• (ii) substantially simultaneously with step (i) adding to the forward path metric value associated with a second encoder state of said trellis butterfly concurrent with said first encoder state, said first transition metric value associated with a forward transition of said encoder from said second encoder state to a second adjacent encoder state of said trellis butterfly concurrent with said first adjacent encoder state;
• and, the backward path metric value associated with said second adjacent encoder state to provide a second sum;
• (iii) comparing said first sum and said second sum and selecting a maximum value of the said first sum and said second sum to be a first maximum value;
• (iv) adding to the forward path metric value associated with said second encoder state;
• a second transition metric value associated with a forward transition of said encoder from said second encoder state to said first adjacent encoder state;
• and, the backward path metric value associated with said first adjacent encoder state to provide a third sum;
• (v) substantially simultaneously with step (iv) adding to the forward path metric value associated with said first encoder state;
• said second transition metric value associated with a forward transition of said encoder from said first encoder state to said second adjacent encoder state;
• and, the backward path metric value associated with said second adjacent encoder state to provide a fourth sum;
• (vi) comparing said third sum and said fourth sum and selecting a maximum value of the said thirds sum and said fourth sum to be a second maximum value;
• the sequences of steps (i), (ii) and (iii) being performed substantially simultaneously with the sequence of steps (iv), (v) and (vi) respectively and steps (i) to (vi) being repeated for the encoder states of all other concurrent trellis butterflies to provide a set of first maximum values and a set of second maximum values, wherein a maximum element of said set of second maximum values is subtracted from a maximum element of said set of the first maximum values to provide a Log-Likelihood ratio.

A decoder comprising a plurality of Log-MAP decoders wherein, each Log-MAP decoder comprises branch metric calculating apparatus for calculating transition metric values (γ), according to a method for calculating Log-Likelihood Ratio values for state transitions 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 the steps (i) to (iii) which are performed in respect of only those transitions corresponding with a parity bit of a first value, and steps (iv) to (vi) which are performed in respect of only those transitions corresponding with a parity bit of a second value:

• (i) adding to a forward path metric value associated with a first encoder state of a given trellis butterfly a first transition metric value associated with a forward transition of said encoder from said first encoder state to a first adjacent encoder state of said butterfly;
• and, the backward path metric value associated with said first adjacent encoder state to provide a first sum;
• (ii) substantially simultaneously with step (i) adding to the forward path metric value associated with a second encoder state of said trellis butterfly concurrent with said first encoder state;
• said first transition metric value associated with a forward transition of said encoder from said second encoder state to a second adjacent encoder state of said trellis butterfly concurrent with said first adjacent encoder state;
• and, the backward path metric value associated with said second adjacent encoder state to provide a second sum;
• (iii) comparing said first sum and said second sum and selecting a maximum value of the said first sum and said second sum to be a first maximum value;
• (iv) adding to the forward path metric value associated with said second encoder state;
• a second transition metric value associated with a forward transition of said encoder form said second encoder state to said first adjacent encoder state;
• and, the backward path metric value associated with said first adjacent encoder state to provide a third sum;
• (v) substantially simultaneously with step (iv) adding to the forward path metric value associated with said first encoder state;
• said second transition metric value associated with a forward transition of said encoder from said first encoder state to said second adjacent encoder state;
• and, the backward path metric value associated with said second adjacent encoder state to provide a fourth sum;
• (vi) comparing said third sum and said fourth sum and selecting the maximum value of the said third sum and said fourth sum to be a second maximum value;
• the sequence of steps (i), (ii) and (iii) being performed substantially simultaneously with the sequence of steps (iv), (v) and (vi) respectively and steps (i) to (vi) being repeated for the encoder states of all other concurrent trellis butterflies to provide a set of first maximum values and a set of second maximum values, wherein a maximum element of said set of second maximum values is subtracted from a maximum element of said set of first maximum values to provide a Log-Likelihood Ratio,
• wherein said first value of parity bits output from encoder is +1 and said second value thereof is −1
• γ(−1,+1)=4×SNR×yp
• and
• γ(+1,−1)=4×SNR×ys+y,
• wherein SNR is the signal-to-noise ratio associated with said received bit sequence, yp and ys are the received parity and systematic bits respectively corresponding with said bits output from the encoder, and the term z represents at least an estimate of the a priori probability of the encoder transition;
• and
• wherein the encoder transition associated with the output therefrom of a systematic and a parity bit of values −1 and −1 respectively is assigned a first transition metric value of
• γ(−1,−1)=0;
• the encoder transition associated with the output therefrom of a systematic and a parity bit of values −1 and +1 respectively is assigned a second transition metric value of
• γ(−1,+1)=s1;
• the encoder transition associated with the output therefrom of a systematic and a parity bit of values +1 and −1 respectively is assigned a third transition metric value
• γ(+1,−1)=s2;
• the encoder transition associated with the output therefrom of a systematic and a parity bit of values +1 and +1 respectively is assigned a transition metric value γ(+1,+1) equal to the sum of said first and second transition metric values;
• where the terms s1 and s2 are dependent on the signal-to-noise ratio associated with the received bit sequence, the received parity and systematic bits corresponding with the bits output from the encoder, and at least an estimate of the a priori probability of the encoder transition.

A decoder comprising a plurality of Log-Map decoders wherein each Log-MAP decoder comprises path metric calculating apparatus for calculating path metric values of said encoder according to 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 the steps of:

• (i) adding to a path metric value associated with a first encoder state a first transition metric value associated 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 and 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 values 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 the 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 first path metric value for said second adjacent encoder state to 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.

A decoder comprising a plurality of Log-MAP decoders wherein each Log-MAP decoder comprises a Log-Likelihood ratio unit for calculating Log-Likelihood Ratio values of a convolutional encoder according to a method for calculating decoding according to a Log-MAP algorithm a bit sequence encoded thereby and received through a noisy channel, the method comprising the steps (i) to (iii) which are performed in respect of only those transitions corresponding with a parity bit of a first value, and steps (iv) to (vi) which are performed in respect of only those transitions corresponding with a parity bit of a second value:

• (i) adding to a forward path metric value associated with a first encoder state of a given trellis butterfly a first transition metric value associated with a forward transition of said encoder from said first encoder state to a first adjacent encoder state of said butterfly;
• and, the backward path metric value associated with said first adjacent encoder state to provide a first sum;
• (ii) substantially simultaneously with step (i) adding to the forward path metric value associated with a second encoder state of said trellis butterfly concurrent with said first encoder state;
• said first transition metric value associated with a forward transition of said encoder from said second encoder state to a second adjacent encoder state of said trellis butterfly concurrent with said first adjacent encoder state;
• and, the backward path metric value associated with said second adjacent encoder state to provide a second sum;
• (iii) comparing said first sum and said second sum and selecting a maximum value of the said first sum and said second sum to be a first maximum value;
• (iv) adding to the forward path metric value associated with said second encoder state;
• a second transition metric value associated with a forward transition of said encoder from said second encoder state to said first adjacent encoder state;
• and, the backward path metric value associated with said first adjacent encoder state to provide a third sum;
• (v) substantially simultaneously with step (iv) adding to the forward path metric value associated with said first encoder state;
• said second transition metric value associated with a forward transition of said encoder from said first encoder state to said second adjacent encoder state;
• and, the backward path metric value associated with said second adjacent encoder state to provide a fourth sum;
• (vi) comparing said third sum and said fourth sum and selecting a maximum value of the said third sum and said fourth sum to be a second maximum value;
• the sequence of steps (i), (ii) and (iii) being performed substantially simultaneously with the sequence of steps (iv), (v) and (vi) respectively and steps (i) to (vi) being repeated for the encoder states of all other concurrent trellis butterflies to provide a set of first maximum values and a set of second maximum values, wherein a maximum element of said set of second maximum values is subtracted from a maximum element of said set of first maximum values to provide a Log-Likelihood Ratio.