Signal decoding methods and apparatus

1. A trellis decoder for decoding symbols of a received signal, said symbol comprising a sequence defined by transitions between states of a trellis, the trellis decoder comprising:

means for performing a forward recursion through said trellis to determine a first set of probabilities (α(X t )) each defining a probability of a said trellis state (X t ) responsive to one or more current or earlier received signal values (y 1:t );

means for providing a second set of (β(X t )) probabilities each defining a probability of one or more received signal values (y t+1:T ) given an earlier said trellis state (X t );

means to decode said received signal to determine probabilities (p(b t |y 1:T )) for symbols of a corresponding transmitted sequence of symbols from said first and second sets of probabilities; and wherein said decoder further comprises:

means to select states for determining said first set of probabilities responsive to one or more received signal values later than a said trellis state defining a probability in said first set.

2. A trellis decoder as claimed in claim 1 wherein said means for providing said second set of probabilities is operable to perform a backwards recursion through said trellis to determine said probabilities (β(X t )).

3. A trellis decoder as claimed in claim 1 wherein said means to select states employs a Gaussian approximation to determine a likelihood of a said trellis state from said one or more later received signal values for selecting said states.

4. A trellis decoder as claimed in claim 1 , wherein said selecting means is further configured to select states by selecting transitions from previous said trellis states.

5. A trellis decoder as claimed in claim 1 wherein said selecting means is configured to select a state responsive to a probability of said state given said one or more later received signal values.

6. A trellis decoder as claimed in claim 1 wherein said one or more later received signal values comprises signal values received over a fixed time lag interval.

7. A trellis decoder as claimed in claim 1 wherein a said received signal value comprises a vector of signals received over a MIMO channel.

8. A trellis decoder as claimed in claim 1 wherein said decoding comprises joint equalisation and decoding of a space-time and/or channel coded transmitted signal.

9. A trellis decoder as claimed in claim 1 wherein said means to select states comprises means for evaluating one or more log probability metrics dependent upon said one or more later received signal values.

10. A trellis decoder as claimed in claim 1 further comprising means for iterating said forwards and backwards recursion and symbol probability determining; and wherein said means to select states comprises means for determining a probability of a said trellis state responsive to an a priori symbol probability distribution.

11. A trellis decoder as claimed in claim 1 wherein said means to select states is configured to select states at a time (t) responsive to a probability distribution (p(X t |y 1:t+L′ )) of said states given received signal values from an initial time to a future time (t+L′).

12. A trellis decoder as claimed in claim 1 wherein said means to select states is configured to select states responsive to an approximation of a probability distribution (p(y t:t+L′ |X t−1 )) of received signal values from said time (t) to future time (t+L′) given a previous state (X t−1 ), said approximation comprising a multivariate normal distribution having a covariance matrix Σ t , and wherein said decoder further comprises means for extrapolating a value of an inverse of said covariance matrix from a value at one said trellis state to a value at a later said trellis state.

13. A trellis decoder as claimed in claim 1 wherein said means to select states is configured to select states at a time (t) responsive to a probability distribution, wherein said probability distribution is approximated by a multivariate normal distribution, said normal distribution being defined by a matrix (Σ t ; Σ t+j ), and wherein said means for selecting states further comprises means for extrapolating a value of an inverse of said matrix from a value at one said trellis state to a value at a later said trellis state.

14. A receiver including the decoder of claim 1 .

15. A trellis decoder as claimed in claim 1 wherein said means to select states is configured to select states at a time (t) responsive to a probability distribution (p(b t |X t−1 )y t:t+L′ )) of transitions from a previous selected state (X t−1 ) given received signal values from said time (t) to future time (t+L′).

16. A trellis decoder as claimed in claim 15 wherein said probability distribution (p(b t |X t−1 )y t:t+L′ )) is approximated by a product of probability distributions p(b t j |X t−1 ,y t:t+L′ ), where j indexes the jth component of a sequence of symbols transmitted together, and where said product is formed for index j running through said transmitted symbols.

17. A trellis decoder as claimed in claim 16 wherein said probability distribution p(b t j |X t−1 ,y t:t+L′ ) is approximated by a multivariate normal distribution with a covariance matrix Σ t,j the decoder further comprising means for extrapolating a value of an inverse of said covariance matrix from an inverse of a covariance matrix Σ t describing an approximation of a probability distribution (p(y t:t+L′ |X t−1 )) of received signal values from said time (t) to future time (t+L′) given a previous state (X t−1 ).

18. A method of decoding symbols of a received signal, said symbols comprising a sequence defined by transitions between states of a trellis, each said trellis state being associated with a time, the method comprising:

performing a forward recursion through said trellis to determine a first set of probabilities each defining a probability of a said trellis state responsive to prior values of said received signal;

obtaining a second set of probabilities each defining a probability of one or more received signal values given a prior said trellis state; and

decoding said received signal to determine probabilities for symbols of a corresponding transmitted sequence of symbols from said first and second sets of probabilities; the method further comprising:

selecting states for determining said first set of probabilities responsive to one or more received signal values later than a said trellis state defining a probability in said first set.

19. A method as claimed in claim 18 wherein said obtaining of said second set of probabilities comprises performing a backwards recursion through said trellis to determine said second set of probabilities.

20. A method as claimed in claim 18 wherein said received signal comprises a vector defining a MIMO signal.

21. A method as claimed in claim 18 wherein said selecting comprises evaluating one or more log probability metrics (Φ, θ).

22. A method of decoding a trellis coded signal using a BCJR-type procedure in which probabilities of transmitted symbols are determined by forwards and backwards iteration through a trellis having successive sets of states associated with successive received signal time intervals, a set of states defining a trellis stage, the method comprising reducing the number of states processed at a said trellis stage (X t ) by selecting states for evaluation for determining said probabilities based upon future received signal values (y t:t+L′ ) at said stage.

23. A method as claimed in claim 22 wherein said selecting comprises selecting transitions to said trellis stage from a previous trellis stage.

24. A method as claimed in claim 22 wherein said selecting includes selecting said states responsive to a probability of a said state given said future received signal values.

25. A method as claimed in claim 22 , wherein said future received signal values comprise received signal values over a lag time interval (L′).

26. A method as claimed in claim 25 wherein said lag time interval is determined by a memory time interval of a channel between a transmitter of said transmitted symbols and a receiver of said received signal.

27. A computer readable storage medium encoded with computer executable instructions, which when executed by a computer, cause the computer to perform a method of decoding symbols of a received signal, said symbols comprising a sequence defined by transitions between states of a trellis, each said trellis state being associated with a time, said method comprising:

performing a forward recursion through said trellis to determine a first set of probabilities each defining a probability of a said trellis state responsive to prior values of said received signal;

obtaining a second set of probabilities each defining a probability of one or more received signal values given a prior said trellis state; and

decoding said received signal to determine probabilities for symbols of a corresponding transmitted sequence of symbols from said first and second sets of probabilities; the method further comprising:

selecting states for determining said first set of probabilities responsive to one or more received signal values later than a said trellis state defining a probability in said first set.

28. A decoder for decoding symbols of a received signal, said symbols comprising a sequence defined by transitions between states of a trellis, each said trellis state being associated with a time, the decoder comprising:

a forward recursion unit configured to perform a forward recursion through said trellis to determine a first set of probabilities each defining a probability of a said trellis state responsive to prior values of said received signal;

an obtaining unit configured to obtain a second set of probabilities each defining a probability of one or more received signal values given a prior said trellis state;

a decoding unit configured to decode said received signal to determine probabilities for symbols of a corresponding transmitted sequence of symbols from said first and second sets of probabilities; and

a selecting unit configured to select states for determining said first set of probabilities responsive to one or more received signal values later than a said trellis state defining a probability in said first set.

29. A decoder for decoding a trellis coded signal using a BCJR type procedure in which probabilities of transmitted symbols are determined by forwards and backwards iteration through a trellis having successive sets of states associated with successive received signal time intervals, a set of states defining a trellis stage, the decoder including a system to reduce the number of states processed at a said trellis stage (X t ) by selecting states for evaluation for determining said probabilities based upon future received signal values (y t:t+L′ ) at said stage.

30. A receiver including the decoder of claim 28 .

31. A trellis decoder for decoding a trellis coded signal using a BCJR type procedure in which probabilities of transmitted symbols are determined by forwards and backwards iteration through a trellis having successive sets of states associated with successive received signal time intervals, a set of states defining a trellis stage, the decoder comprising: a received signal input for said trellis coded signal; an output for providing decoded signal data; program memory for storing processor control code; and a processor coupled to said received signal input, to said output and to said program memory for loading and implementing said code, said code comprising code to: reduce the number of states processed at a said trellis stage (X t ) by selecting states for evaluation for determining said probabilities based upon future received signal values (y t:t+L′ ) at said stage.

32. A trellis decoder for decoding symbols of a received signal, said symbols comprising a sequence defined by transitions between states of a trellis each said trellis state being associated with a time, the decoder including a state selector to select trellis states (X t ) at a time (t) based on a probability distribution of said states given received signal values from an initial time prior to said time (t) to a future time (t+L′).

33. A trellis decoder as claimed in claim 32 wherein said state selector is further configured to select said states by selecting transitions from a previous state (X t−1 ) based on a probability distribution of said transitions given said received signal values from said time (t) to said future time (t+L′).

34. A trellis decoder for decoding symbols of a received signal, said symbols comprising a sequence defined by transitions between states of a trellis each said trellis state being associated with a time, the decoder comprising:

a received signal input for said trellis coded signal;

an output for providing decoded signal data;

program memory for storing processor control code; and

a processor coupled to said received signal input, to said output and to said program memory for loading and implementing said code, said code comprising code to:

perform a forward recursion through said trellis to determine a first set of probabilities each defining a probability of a said trellis state responsive to prior values of said received signal;

obtain a second set of probabilities each defining a probability of one or more received signal values given a prior said trellis state; and

decode said received signal to determine probabilities for symbols of a corresponding transmitted sequence of symbols from said first and second sets of probabilities; the code further comprising code to:

select states for determining said first set of probabilities responsive to one or more received signal values later than a said trellis state defining a probability in said first set.

35. A trellis decoder as claimed in claim 34 wherein said code to obtain said second set of probabilities comprises code to perform a backwards recursion through said trellis to determine said second set of probabilities.

36. A method implemented on a decoder for determining a set of probabilities for states of a trellis corresponding to signal values received over a series of tune instants, the method comprising:

performing a forward recursion through the trellis over the series of time instants, the forward recursion comprising, for each time instant:

calculating a metric from at least a signal value received at a time later than the time instant for each possible trellis state at the time instant;

selecting a set of active states for the time instant from the possible trellis states at the time instant using the metric; and

calculating a set of probabilities only for each active state at the time instant.

37. A method implemented on a decoder for decoding symbols of a received signal, the symbols comprising a sequence defined by transitions between states of a trellis, each of the states of the trellis being associated with a time instant, the method comprising:

performing a forward recursion through the time instants of the trellis by:

calculating a metric from at least a signal value received at a time later than the time instant of the trellis state under consideration for trellis states at the time instant under consideration;

selecting a set of active states for the time instant under consideration from the possible trellis states at the time instant under consideration using the metric; and

calculating a set of probabilities of transitions to states at a time instant following the time instant under consideration only for each active state at the time instant under consideration.