Method and apparatus for implementing projections in signal processing applications

• US 20040030534A1
• Filed: 11/19/2001
• Published: 02/12/2004
• Est. Priority Date: 12/04/2000
• Status: Active Grant

• Current Assignee: III Holdings 1, LLC
• Original Assignee: TensorComm, Inc. (Rambus Inc.)
• Inventors: Narayan, Anand P., Thomas, John K.
• Granted Patent: US 6,856,945 B2
• Time in Patent Office: Days
• US Class Current: 702/189
• CPC Class Codes: G01S 19/21 Interference related issues ; Issues related to cross-correlation, spoofing or other methods of denial of service
• CPC Class Codes: G01S 19/22 Multipath-related issues
• CPC Class Codes: H04B 1/7103 the interference being multiple access interference
• CPC Class Codes: H04B 1/7105 Joint detection techniques, e.g. linear detectors
• CPC Class Codes: H04B 2001/70706 using a code tracking loop, e.g. a delay locked loop
• CPC Class Codes: H04B 2201/70715 with application-specific features

Abstract

A novel method and apparatus is provided for enabling the computation of a signal in a certain subspace, its projection that lies outside the subspace, and the orthogonal basis for a given matrix. More particularly, the present invention relates to the use of such a method or apparatus for real-time hardware applications since the method and apparatus may be utilized without matrix inversions or square root computations.

Claims

1. A method for generating a projection of a received signal (y), said signal comprising H, a signal of the source of interest;

S. the signals of all other sources and multi-path versions of the source of interest and composed of vectors s₁, s₂, s₃ . . . , s_p; and

noise (n);

the method comprising the steps of;

determining a basis matrix U composed of basis vectors u₁, u₂, . . . u_p;

storing elements of said basis matrix U; and

determining y_perp where;

y_perp=y−

U(U^TU)<sup>−

1</sup>U^Ty.

2. The method recited in claim 1, wherein said step of computing basis vectors comprises the steps of:

A. assigning s₁ as a first basis matrix U;

B. decomposing s₂ into a component which is in said basis matrix U and a component that is not (u₂); and

C. redefining the basis matrix U to incorporate basis vector u₂.

3. The method recited in claim 2, wherein said step of computing basis vectors further comprises the steps of:

repeating steps B and C for each element of S.

4. The method recited in claim 2, wherein said step of computing basis vectors further comprises the steps of:

comparing u_i to a predetermined threshold and if u_i is greater than said threshold, adding u_i to the basis and repeating steps B and C for each element of S, else ignoring the u_i and continuing to repeat steps B and C.

5. The method recited in claim 2, wherein said step of computing basis vectors further comprises the steps of:

computing 1/σ

_i, where u_i^Tu_i=σ

; and

storing u_i and 1/σ

_i

6. The method recited in claim 2, wherein said step of computing basis vectors further comprises the steps of:

computing

$u_i=s_i-u_1<br><br>\frac{1}{{\mathrm{\sigma <br><br>}}_1}<br><br>u_1^T<br><br>s_i-u_2<br><br>\frac{1}{{\mathrm{\sigma <br><br>}}_2}<br><br>u_2^T<br><br>s_i-\mathrm{\dots <br><br>}-u_{i-1}<br><br>\frac{1}{{\mathrm{\sigma <br><br>}}_{i-1}}<br><br>u_{i-1}^T<br><br>s_i;<br><br>$

storing u_i and 1/σ

_i; and

repeating said computing and storing steps if u_i is above a predetermined threshold, else ignoring this particular u_i.

7. The method recited in claim 1, wherein said step of determining y_perp comprises the step of calculating y_perp with the following formula:

8. The method recited in claim 1, wherein said step of determining y_perp comprises the step of calculating y_perp with the following formula:

9. The method recited in claim 1, further comprising the step of determining y_s where:

y_s=U(U^TU)<sup>−

1</sup>U^Ty.

10. A method for generating a projection from a received signal (y), said signal comprising H, a spread signal matrix of the source of interest;

S, the spread signal matrix of all other sources of interest and composed of vectors s₁, s₂, s₃ . . . , s_p; and

noise (n);

the method comprising the steps of;

A. assigning s₁ as a first basis vector u₁;

B. determining σ

_i, where u_i^Tu_i=σ

; and

C. storing u_i;

D. computing of inner products of the s_i+1 and the u₁ through u_i vectors;

E. multiplying said inner product with a respective scalar 1/σ

_i and thereby creating a first intermediate product

F. scaling each respective basis vector u_i by multiplying each respective first intermediate product with each respective basis vector u_i;

G. obtaining a vector sum from step F;

H. subtracting said vector sum from s_i+1 to obtain the next basis vector u_i+1;

I. comparing u_i+1 to a predetermined value and if equal to or less than said value, discarding the u_i+1 and going to step N;

J. storing u_i+1;

K. determining an inner product of u^T_i+1u_i+1;

L. determining the reciprocal of step K which is 1/σ

_i+1;

M. storing 1/σ

_i+1;

N. incrementing i;

O. conducting steps D through N until i=p, where p is the total number of said sources of interest;

P. determining y_perp where;

y_perp=y−

U(U^TU)<sup>−

1</sup>U^Ty.

11. The method recited in claim 10, wherein said computing step (D) is conducted in series.

12. The method recited in claim 10, wherein said computing step (D) is conducted in parallel.

13. The method recited in claim 10, wherein said multiplying step (E) is conducted in series.

14. The method recited in claim 10, wherein said multiplying step (E) is conducted in parallel.

15. The method recited in claim 10, wherein said scaling step (F) is conducted in series.

16. The method recited in claim 10, wherein said scaling step (F) is conducted in parallel.

17. The method recited in claim 10, wherein said storing step (C) also stores σ

_i.

18. The method recited in claim 10, wherein said storing step (C) also stores 1/σ

_i.

19. The method recited in claim 10, wherein said inner product step (K) is conducted in series.

20. The method recited in claim 10, wherein said inner product step (K) is conducted in parallel.

36. The method recited in claim 10, further comprising the step of determining y_s where:

y_s=U(U^TU)<sup>−

1</sup>U^Ty.

21. A method for generating a projection from a received signal (y), said signal comprising H, a spread signal matrix of the source of interest;

S, the spread signal matrix of all other sources of interest and composed of vectors s₁, s₂, s₃ . . . , s_p; and

noise (n);

the method comprising the steps of;

A. assigning s₁ as a first basis vector u₁;

B. determining σ

_i, where u_i^Tu_i=σ

; and

C. storing u_i;

D. computing of inner products of the s_i+1 and the u₁ through u_i vectors;

E. multiplying said inner product with a respective scalar 1/σ

_i and thereby creating a first intermediate product;

F. scaling each respective basis vector u_i by multiplying each respective first intermediate product with each respective basis vector u_i;

G. serially subtracting said intermediate product from s_i+1;

H. utilizing the result from step G and subtracting the next incoming value of

$u_i<br><br>\frac{1}{{\mathrm{\sigma <br><br>}}_i}<br><br>u_i^T<br><br>s_{i+1}$

 

until all the values are processed;

I. obtaining the next basis vector u_i+1 from step H;

J. comparing u_i+1 to a predetermined value and if equal to or less than said value, discarding u_i+1 and going to step O;

K. storing u_i+1;

L. determining an inner product of u^T_i+1u_i+1,

M. determining the reciprocal of step K which is 1/σ

_i+1;

N. storing 1/σ

_i+1;

O. incrementing i;

P. conducting steps D through O until i=p, where p is the total number of said sources of interest;

Q. determining y_perp where;

y_perp=y−

U(U^TU)<sup>−

1</sup>U^Ty.

22. The method recited in claim 21, wherein said computing step (D) is conducted in series.

23. The method recited in claim 21, wherein said computing step (D) is conducted in parallel.

24. The method recited in claim 21, wherein said multiplying step (E) is conducted in series.

25. The method recited in claim 21, wherein said multiplying step (E) is conducted in parallel.

26. The method recited in claim 21, wherein said scaling step (F) is conducted in series.

27. The method recited in claim 21, wherein said scaling step (F) is conducted in parallel.

28. The method recited in claim 21, wherein said storing step (C) also stores σ

_i.

29. The method recited in claim 21, wherein said storing step (C) also stores 1/σ

_i.

30. The method recited in claim 21, wherein said inner product step (L) is conducted in series.

31. The method recited in claim 21, wherein said inner product step (L) is conducted in parallel.

37. The method recited in claim 21, further comprising the step of determining y_s where:

y_s=U(U^TU)<sup>−

1</sup>U^Ty.

32. An apparatus for generating a projection from a received signal (y), said signal comprising H, a signal of the source of interest;

S, the signals of all other sources and composed of vectors s₁, s₂, s₃ . . . , s_p; and

noise (n);

the apparatus comprising;

means for determining a basis vector U;

means for storing elements of said basis vector U; and

means determining y_perp where;

y_perp=y−

U(U^TU)<sup>−

1</sup>U^Ty.

33. An apparatus for generating a projection from a received signal (y), said signal comprising H, a spread signal matrix of the source of interest;

S, the spread signal matrix of all other sources of interest and composed of vectors s₁, s₂, s₃ . . . , s_p; and

noise (n);

the apparatus comprising;

A. means for assigning s₁ as a first basis vector u₁;

B. means for determining σ

_i, where u_i^Tu_i=σ

; and

C. means for storing u_i;

D. means for computing of inner products of the s_i+1 and the u₁ through u_i vectors;

E. means for multiplying said inner product with a respective scalar 1/σ

_i and thereby creating a first intermediate product;

F. means for scaling each respective basis vector u_i by multiplying each respective first intermediate product with each respective basis vector u_i;

G. means for obtaining a vector sum from step F;

H. means for subtracting said vector sum from s_i+1 to obtain the next basis vector u_i+1;

I. means for comparing u_i+1 to a predetermined value and if equal to or less than said value, discarding this u_i+1 and going to step N.

J. means for storing u_i+1;

K. means for determining an inner product of u^T_i+1u_i+1;

L. means for determining the reciprocal of step K which is 1/σ

_i+1;

M. means for storing 1/σ

_i+1;

N. means for incrementing i;

O. means for conducting steps D through N until i=p, where p is the total number of said sources of interest;

P. means for determining y_perp where;

y_perp=y−

U(U^TU)<sup>−

1</sup>U^Ty.

34. An apparatus for generating a projection from a received signal (y), said signal comprising H, a spread signal matrix of the source of interest;

S, the spread signal matrix of all other sources of interest and composed of vectors s₁, s₂, s₃ . . . , s_p; and

noise (n);

the apparatus comprising;

A. means for assigning s₁ as a first basis vector u₁;

B. means for determining σ

_i, where u_i^Tu_i=σ

; and

C. means for storing u_i;

D. means for computing of inner products of the s_i+1 and the u₁ through u_i vectors;

E. means for multiplying said inner product with a respective scalar 1/σ

_i and thereby creating a first intermediate product;

F. means for scaling each respective basis vector u_i by multiplying each respective first intermediate product with each respective basis vector u_i;

G. means for serially subtracting said intermediate product from s_i+1;

H. means for utilizing the result from step G and subtracting the next incoming value of

$u_i<br><br>\frac{1}{{\mathrm{\sigma <br><br>}}_i}<br><br>u_i^T<br><br>s_{i+1}$

 

until all the values are processed;

I. means for obtaining the next basis vector u_i+1 from step H;

J. means for comparing u_i+1 to a predetermined value and if equal to or less than said value, going to step O;

K. means for storing u_i+1;

L. means for determining an inner product of u^T_i+1u_i+1, M. means for determining the reciprocal of step K which is 1/σ

_i+1;

N. means for storing 1/σ

_i+1;

O. means for incrementing i;

P. means for conducting steps D through O until imp, where p is the total number of said sources of interest; and

Q. means for determining y_perp where;

y_perp=y−

U(U^TU)<sup>−

1</sup>U^Ty.

35. A method for generating a projection of a received signal (y), said signal comprising H, a signal of the source of interest;

S, the signals of all other sources and multi-path versions of the source of interest and composed of vectors s₁, s₂, s₃ . . . , s_p; and

noise (n);

the method comprising the steps of;

determining a basis matrix U composed of basis vectors u₁, u₂, . . . u_p;

storing elements of said basis matrix U;

determining y_perp where;

y_perp=y−

U(U^TU)<sup>−

1</sup>U^Ty; and

determining y_s where;

y_s=U(U^TU)<sup>−

1</sup>U^Ty.

38. An apparatus for generating a projection from a received signal (y), said signal comprising H, a signal of the source of interest;

S, the signals of all other sources and composed of vectors s₁, s₂, s₃ . . . , s_p; and

noise (n);

the apparatus comprising;

means for determining a basis vector U;

means for storing elements of said basis vector U;

means for determining y_perp where;

y_perp=y−

U(U^TU)<sup>−

1</sup>U^Ty.

means for determining y_s where;

y_s=U(U^TU)<sup>−

1</sup>U^Ty.