Apparatus and Method for Trellis-Based Detection in a Communication System

• US 20120093266A1
• Filed: 10/14/2010
• Published: 04/19/2012
• Est. Priority Date: 10/14/2010
• Status: Active Grant

• Current Assignee: Nokia Technologies Oy (Nokia Corporation)
• Original Assignee: Nokia Corporation
• Inventors: Sun, Yang, Cavallaro, Joseph R., Lilleberg, Jorma
• Granted Patent: US 8,559,540 B2
• Time in Patent Office: Days
• US Class Current: 375/341
• CPC Class Codes: H03M 13/1102 Codes on graphs and decoding on graphs, e.g. low-density parity check [LDPC] codes
• CPC Class Codes: H03M 13/3905 Maximum a posteriori probability [MAP] decoding or approximations thereof based on trellis or lattice decoding, e.g. forward-backward algorithm, log-MAP decoding, max-log-MAP decoding
• CPC Class Codes: H03M 13/6525 3GPP LTE including E-UTRA
• CPC Class Codes: H04L 1/06 using space diversity
• CPC Class Codes: H04L 25/03216 using the M-algorithm
• CPC Class Codes: H04L 25/03891 Spatial equalizers MIMO diversity systems H04B7/0413

Abstract

An apparatus for trellis-based detection in a communication system including a processor and memory having computer program code configured to construct a trellis representing a transmitted signal formed from a plurality of symbols, each having a constellation size, transmitted by a number of transmit antennas, and form a log likelihood ratio at nodes of the trellis as a log-sum of a number of exponential terms corresponding to a hypothesized transmitted bit value of the plurality of symbols. The number of exponential terms is limited by a number of most likely paths of the trellis extending from each node of the trellis and the constellation size. The processor and memory including computer program code are further configured to form a list at each node of the trellis of a size limited to the number of the most likely paths of the trellis extending from each node of the trellis.

Claims

1. An apparatus, comprising:

a processor; and

memory including computer program code,

said memory and said computer program code configured to, with said processor, cause said apparatus to perform at least the following;

construct a trellis representing a transmitted signal formed from a plurality of symbols transmitted by a number of transmit antennas, each symbol having a constellation size, said trellis being formed of columns representing said number of transmit antennas and rows representing values of said plurality of symbols with nodes at intersections thereof;

form a log likelihood ratio at said nodes of said trellis as a log-sum of a number of exponential terms corresponding to a hypothesized transmitted bit value of 0 or 1 of said plurality of symbols, said number of exponential terms being limited by a function of a number of most likely paths of said trellis extending from each node of said trellis and said constellation size; and

form a list at each node of said trellis of a size limited to said number of said most likely paths of said trellis extending from each node of said trellis.

2. The apparatus as recited in claim 1 wherein said memory and said computer program code are further configured to, with said processor, cause said apparatus to select a mostly likely symbol representing at least a portion of said transmitted signal from said lists of said most likely paths of said trellis.

3. The apparatus as recited in claim 1 wherein said memory and said computer program code are further configured to, with said processor, cause said apparatus to form path weights as a sum of edge weights along paths of said trellis as Euclidean distances dependent on said transmitted signal.

4. The apparatus as recited in claim 3 wherein said transmitted signal is received by a number of receive antennas over a communication channel as described by a channel matrix, wherein said path weights are formed employing a unitary-upper triangular decomposition of said channel matrix.

5. The apparatus as recited in claim 1 wherein said number of exponential terms is equal to constellation size times said number of said most likely paths of said trellis divided by two.

6. The apparatus as recited in claim 1 wherein said number of said most likely paths of said trellis is less than or equal to said constellation size.

7. The apparatus as recited in claim 1 wherein said memory and said computer program code are further configured to, with said processor, cause said apparatus to employ a path reduction procedure to limit said most likely paths extending from said each node of said trellis.

8. The apparatus as recited in claim 1 wherein said memory and said computer program code are further configured to, with said processor, cause said apparatus to employ a path extension procedure to extend uncompleted paths of said trellis.

9. The apparatus as recited in claim 1 wherein said log-sum of said number of exponential terms is computed recursively using a Jacobean procedure.

10. The apparatus as recited in claim 1 wherein said log-sum of said number of exponential terms approximates a log-maximum a posteriori probability (Log-MAP) procedure.

11. A computer program product comprising a program code stored in a computer readable medium configured to:

construct a trellis representing a transmitted signal formed from a plurality of symbols transmitted by a number of transmit antennas, each symbol having a constellation size, said trellis being formed of columns representing said number of transmit antennas and rows representing values of said plurality of symbols with nodes at intersections thereof;

form a log likelihood ratio at said nodes of said trellis as a log-sum of a number of exponential terms corresponding to a hypothesized transmitted bit value of 0 or 1 of said plurality of symbols, said number of exponential terms being limited by a function of a number of most likely paths of said trellis extending from each node of said trellis and said constellation size; and

form a list at each node of said trellis of a size limited to said number of said most likely paths of said trellis extending from each node of said trellis.

12. The computer program product as recited in claim 11 wherein said program code stored in said computer readable medium is configured to select a mostly likely symbol representing at least a portion of said transmitted signal from said lists of said most likely paths of said trellis.

13. A method, comprising:

constructing a trellis representing a transmitted signal formed from a plurality of symbols transmitted by a number of transmit antennas, each symbol having a constellation size, said trellis being formed of columns representing said number of transmit antennas and rows representing values of said plurality of symbols with nodes at intersections thereof;

forming a log likelihood ratio at said nodes of said trellis as a log-sum of a number of exponential terms corresponding to a hypothesized transmitted bit value of 0 or 1 of said plurality of symbols, said number of exponential terms being limited by a function of a number of most likely paths of said trellis extending from each node of said trellis and said constellation size; and

forming a list at each node of said trellis of a size limited to said number of said most likely paths of said trellis extending from each node of said trellis.

14. The method as recited in claim 13 further comprising selecting a mostly likely symbol representing at least a portion of said transmitted signal from said lists of said most likely paths of said trellis.

15. The method as recited in claim 13 further including forming path weights as a sum of edge weights along paths of said trellis as Euclidean distances dependent on said transmitted signal.

16. The method as recited in claim 15 wherein said transmitted signal is received by a number of receive antennas over a communication channel as described by a channel matrix, wherein said path weights are formed employing a unitary-upper triangular decomposition of said channel matrix.

17. The method as recited in claim 13 wherein said number of exponential terms is equal to constellation size times said number of said most likely paths of said trellis divided by two.

18. The method as recited in claim 13 wherein said number of said most likely paths of said trellis is less than or equal to said constellation size.

19. The method as recited in claim 13 further comprising employing a path reduction procedure to limit said most likely paths extending from said each node of said trellis.

20. The method as recited in claim 13 further comprising employing a path extension procedure to extend uncompleted paths of said trellis.