M-algorithm with prioritized user ordering

• US 20060115026A1
• Filed: 12/01/2005
• Published: 06/01/2006
• Est. Priority Date: 12/01/2004
• Status: Active Grant

• Current Assignee: Collision Communications, Inc. (Concert Technology Corporation)
• Original Assignee: BAE Systems Information and Electronic Systems Integration Incorporated (BAE Systems Plc)
• Inventors: MacLeod, Robert B.
• Granted Patent: US 7,817,754 B2
• Time in Patent Office: Days
• US Class Current: 375/343
• CPC Class Codes: H04B 1/7105 Joint detection techniques, e.g. linear detectors
• CPC Class Codes: H04L 25/0204 of multiple channels
• CPC Class Codes: H04L 25/021 Estimation of channel covariance
• CPC Class Codes: H04L 25/0242 using matrix methods
• CPC Class Codes: H04L 25/03216 using the M-algorithm
• CPC Class Codes: H04L 25/0328 with interference cancellation circuitry adaptations for interference cancellation within a sequence estimator H04L25/03305; interference related aspects of direct sequence spread spectrum H04B1/7097; interference related aspects of frequency hopping spread spectrum H04B1/715; see also H04B1/10
• CPC Class Codes: H04L 25/03292 with channel estimation circuitry
• CPC Class Codes: H04L 25/03299 with noise-whitening circuitry
• CPC Class Codes: H04L 25/03331 Arrangements for the joint estimation of multiple sequences

Abstract

Performing approximate diagonalization of a correlation metric by user permutation to improve Multiuser Detector (MUD) processing. The system reorders the entries in the S-Matrix in order to move the bit decisions closer together in the decision tree. In one embodiment the reordering is a sequential pairwise correlation.

Claims

1. A system for reordering users of a multiuser detector, comprising:

Processing an incoming data stream to form an initial S-Matrix of K users;

Re-ordering said S-Matrix starting from a random column and forming a permuted S-Matrix array correlated from said random column; and

Using said permuted S-Matrix Array in said multiuser detector and outputting an array of bit decisions.

2. The system of claim 1, wherein said permuted S-Matrix array is a sequential pairwise correlation from each of a previous correlated column.

3. The system of claim 1, wherein said multiuser detector is an M-algorithm.

4. The system of claim 1, further comprising performing Cholesky factorization of said initial S-Matrix.

5. The system of claim 1, further comprising a refinement of said permuted S-Matrix array to confirm correlation.

6. The system of claim 1, wherein said permuted S-Matrix array is processed in a windowed multiuser detector.

7. The system of claim 6, wherein said S-Matrix is reordered prior to being processed in said windowed multiuser detector.

8. A method for performing approximate diagonalization of an S-Matrix of vector data arranged in a plurality of columns, comprising:

Selecting an initial column of data from said S-Matrix array;

Removing said initial column from said S-Matrix array thereby forming a remaining S-Matrix array;

Forming a permuted S-Matrix array starting with said initial column, wherein said forming comprises;

From said remaining S-Matrix Array, correlating a sequential column;

Removing said sequential column from said remaining S-Matrix Array;

Adding said sequential column to said permuted S-Matrix Array; and

Repeating said correlating, removing and adding for said remaining S-Matrix array thereby performing said approximate diagonalization.

9. The method of claim 8, wherein said initial column of data is a randomly selected column of data.

10. The method of claim 8, wherein said correlating is a pairwise correlation to said sequential column.

11. The method of claim 8, further comprising forming said S-Matrix Array from a subsection of a larger S-Matrix Array.

12. The method of claim 11, further comprising re-ordering said larger S-Matrix Array prior to forming said S-Matrix Array.

13. The method of claim 8, further comprising confirming said approximate diagonalization of the permuted S-Matrix array.

14. The method of claim 13, wherein said confirming comprises swapping each of said columns of data from said permuted S-Matrix array, determining if correlation is improved by said swapping, and replacing any said columns that provide improved correlation.

15. An advanced receiver apparatus for processing multiple received signals with interfering signals, comprising:

an ordering unit for ordering users indices;

a multi-user detector coupled to said ordering unit producing a plurality of surviving states;

a voting unit coupled to said multi-user detector for processing said surviving states and generating a set of soft estimates of channel symbols, wherein said surviving states are calculated by using a weighted average; and

a decoder section coupled to said voting unit and said multi-user detector, wherein said decoder section processes said soft estimates of channel symbols to produce a final output on a final iteration, and wherein said decoder produces said confidence values for intermediate iterations.

16. The receiver of claim 15, wherein said weighted average includes a plurality of partially discarded paths.

17. The receiver of claim 15, wherein said weighted average is a calculation of the Euclidean distance between a computed signal along a decision path and the actual received signal.

18. The receiver of claim 15, wherein said multi-user detector is an M-algorithm.

19. The receiver of claim 15, wherein said user ordering is a pairwise correlation.

20. The receiver of claim 19, wherein said user ordering combines said pairwise correlation with a power ordering.