Lower complexity computation of lattice reduction

• US 20070268981A1
• Filed: 05/22/2006
• Published: 11/22/2007
• Est. Priority Date: 05/22/2006
• Status: Active Grant

• Current Assignee: Nokia Corporation
• Original Assignee: Nokia Corporation
• Inventors: Heiskala, Juha
• Granted Patent: US 7,668,268 B2
• Time in Patent Office: Days
• US Class Current: 375/267
• CPC Class Codes: H04L 1/005 Iterative decoding, including iteration between signal detection and decoding operation
• CPC Class Codes: H04L 1/06 using space diversity
• CPC Class Codes: H04L 25/0204 of multiple channels

Abstract

A signal vector is received over a plurality of channels. A channel matrix H is determined that represents at least one of the plurality of channels. An iterative algorithm such as Lenstra-Lenstra-Lovasz is used to determining a change of basis matrix T that when multiplied with the channel matrix H converges to a matrix H*T that is more orthogonal than the channel matrix H. In one aspect the iterative algorithm is upwardly bounded in the number of iterations (e.g., 20 or 30 iterations) that it may perform for any specific channel realization to determine the change of basis matrix T. In another aspect the algorithm is initiated with a matrix derived from a previously determined change of basis matrix. Both aspects may be combined in a single method or device, or either employed separately.

Claims

1. A method for detecting a signal comprising:

receiving a signal vector over a plurality of channels;

determining a channel matrix H that represents at least one of the plurality of channels;

using an iterative algorithm, determining a change of basis matrix T that when multiplied with the channel matrix H converges to a matrix H*T that is more orthogonal than the channel matrix H, wherein the iterative algorithm is upwardly bounded in a number of iterations by a predetermined maximum value; and

using the channel matrix H and the change of basis matrix T to detect the received signal vector.

2. The method of claim 1, wherein the predetermined maximum value is equal to or less than about thirty iterations of the algorithm.

3. The method of claim 1, wherein the iterative algorithm comprises a Lenstra-Lenstra-Lovasz algorithm.

4. The method of claim 1, wherein determining the change of basis matrix T comprises initializing the iterative algorithm in a first iteration with an initialization channel matrix H′

_k derived from the current channel matrix H_k and a change of basis matrix T<sub>k−

1</sub> from a previous channel realization.

5. A program of machine-readable instructions, tangibly embodied on an information bearing medium and executable by a digital data processor, to perform actions directed toward determining a change of basis matrix T for use in decoding a received signal, the actions comprising:

receiving a signal vector over a plurality of channels;

determining a channel matrix H that represents at least one of the plurality of channels; and

using an iterative algorithm, determining a change of basis matrix T that when multiplied with the channel matrix H converges to a matrix H*T that is more orthogonal than the channel matrix H, wherein the iterative algorithm is upwardly bounded in a number of iterations by a predetermined maximum value.

6. The program of claim 5, wherein the predetermined maximum value is stored on the information bearing medium and is no greater than thirty iterations of the algorithm.

7. The program of claim 5, wherein the iterative algorithm is stored on the information bearing medium and comprises a Lenstra-Lenstra-Lovasz algorithm.

8. The program of claim 5, wherein determining the change of basis matrix T comprises initializing the iterative algorithm in a first iteration with an initialization channel matrix H′

_k derived from the current channel matrix H_k and a change of basis matrix T<sub>k−

1</sub> from a previous channel realization.

9. A receiver comprising:

a plurality of receive antenna ports;

a channel estimator having an input coupled to an output of each of the plurality of receive antenna ports and an input coupled to a processor and adapted to determine a channel matrix H for a channel realization;

a matrix generator having an input coupled to an output of the channel estimator and adapted to determine according to an iterative algorithm a change of basis matrix T that when multiplied with the channel matrix H converges to a matrix H*T that is more orthogonal than the channel matrix H;

a register coupled to the matrix generator and adapted to store an upward bound to the number of iterations the algorithm may perform; and

a memory and adapted to store the iterative algorithm, where the processor terminates further iterations of the algorithm for a current channel realization once the upward bound is reached.

10. The receiver of claim 9, further wherein the memory is adapted to store a previous change of basis matrix T_k−

1 from a previous channel realization, and the processor initiates a first iteration of the iterative algorithm with a value derived from the previous change of basis matrix T<sub>k−

1</sub>.

11. The receiver of claim 10, wherein the value derived from the previous change of basis matrix T_k−

1 comprises an initialization channel matrix H′

_k derived from multiplying a current channel matrix H_k with the previous change of basis matrix T<sub>k−

1</sub>.

12. A method for detecting a signal comprising:

receiving a signal vector over a plurality of channels;

for a first channel realization, determining a first channel matrix H₁ that represents at least one of the plurality of channels;

using an iterative algorithm, determining a first change of basis matrix T₁ that when multiplied with the first channel matrix H₁ converges to a first combined matrix H₁*T₁ that is more orthogonal than the first channel matrix H₁;

for a second channel realization, determining a second channel matrix H₂ that represents at least one of the plurality of channels;

initializing the iterative algorithm with a matrix derived from the first change of basis matrix T₁;

using the initialized iterative algorithm, determining a second change of basis matrix T₂ that when multiplied with the second channel matrix H₂ converges to a second combined matrix H₂*T₂ that is more orthogonal than the second channel matrix H₂; and

using the second channel matrix H₂ and the second change of basis matrix T₂ to detect a signal received in the second channel realization.

13. The method of claim 12, wherein the iterative algorithm is upwardly bounded in a number of iterations by a predetermined maximum value.

14. The method of claim 12, wherein the iterative algorithm comprises a Lenstra-Lenstra-Lovasz algorithm.

15. The method of claim 12, wherein the matrix derived from the first change of basis matrix T₁ comprises an initiating channel matrix H′

₂ such that H′

₂=H₂*T₁.

16. A program of machine-readable instructions, tangibly embodied on an information bearing medium and executable by a digital data processor, to perform actions directed toward determining a change of basis matrix T for use in decoding a received signal, the actions comprising:

receiving a signal vector over a plurality of channels;

for a first channel realization, determining a first channel matrix H₁ that represents at least one of the plurality of channels;

using an iterative algorithm, determining a first change of basis matrix T₁ that when multiplied with the first channel matrix H₁ converges to a first combined matrix H₁*T₁ that is more orthogonal than the first channel matrix H₁;

for a second channel realization, determining a second channel matrix H₂ that represents at least one of the plurality of channels;

initializing the iterative algorithm with a matrix derived from the first change of basis matrix T₁;

using the initialized iterative algorithm, determining a second change of basis matrix T₂ that when multiplied with the second channel matrix H₂ converges to a second combined matrix H₂*T₂ that is more orthogonal than the second channel matrix H₂; and

using the second channel matrix H₂ and the second change of basis matrix T₂ to detect a signal received in the second channel realization.

17. The program of claim 16, wherein the iterative algorithm is upwardly bounded in a number of iterations by a predetermined maximum value.

18. The program of claim 16, wherein the iterative algorithm comprises a Lenstra-Lenstra-Lovasz algorithm.

19. The program of claim 16, wherein the matrix derived from the first change of basis matrix T₁ comprises an initiating channel matrix H′

₂ such that H′

₂=H₂*T₁.

20. A receiver comprising:

a plurality of receive antenna ports;

a channel estimator having an input coupled to an output of each of the plurality of receive antenna ports and an input coupled to a processor and adapted to determine a first channel matrix H₁ for a first channel realization and a second channel matrix H₂ for a second channel realization;

a matrix generator having an input coupled to an output of the channel estimator and adapted to determine according to an iterative algorithm a first change of basis matrix T₁ for a first channel realization that when multiplied with the first channel matrix H₁ converges to a first combined matrix H₁*T₁ that is more orthogonal than the first channel matrix H₁, and for adapted to determine, according to the iterative algorithm initialized with a matrix deriving from the first change of basis matrix T₁, a second change of basis matrix T₂ for the second channel realization that when multiplied with the second channel matrix H₂ converges to a second combined matrix H₂*T₂ that is more orthogonal than the second channel matrix H₂.