Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2000-04-21
2004-01-06
Ngo, Chuong Dinh (Department: 2122)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06675187
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to processor elements and techniques, and more particularly to pipelined processing devices comprising arrays of processor elements for performing matrix computations.
BACKGROUND OF THE INVENTION
As advances in technology enable manufacturers to put more wires and transistors on a single integrated circuit, new opportunities arise for performing digital signal processing operations that previously would have been impractical.
An example of one such emerging application is the use of adaptive beamforming for arrays of antennas in a base station of a wireless communication system. The objective in this case is to allow more mobile users and higher data rates in a given cell. This is achieved by adding together the signals received by multiple antennas with time varying complex weights, in order to form a radiation pattern which points toward the mobile of interest and includes nulls on sources of interference. Various solutions for optimizing this type of problem are known and involve performing computations with matrices and vectors of complex numbers. See, e.g., S. Haykin, “Adaptive Filter Theory,” 3
rd
ed., Prentice Hall, 1996. Instead of only a single complex multiplication being called for at a given time, there is the need for massive numbers of complex multiplications.
Another emerging application of this type is multi-user detection for wireless system base stations using Direct Sequence Code Division Multiple Access (DS-CDMA) coding. In these algorithms, as described in, e.g., S. Moshavi, “Multi-User Detection for DS-CDMA Communications,” p. 124, IEEE Communications Magazine, October 1996, collective knowledge gained in real time about the various mobiles that are interfering with each other is used to un-entangle that interference and improve the detection of each individual mobile. These algorithms also involve intensive calculations with matrices of complex numbers.
The above-noted emerging applications for wireless base stations often use variations of well-known algorithms which make use of fundamental matrix computations. The four operations typically of most interest are:
1. Solution of a set of n linear equations with n unknowns. One possible approach is to triangulate the set of equations using QR decomposition via Givens rotations, and then solve the set of triangulated equations by back substitution.
2. Matrix inversion. One possible approach is to triangulate a set of equations using QR decomposition via Givens rotations, and then solve the set of triangulated equations for the inverse by multiple back substitutions.
3. Matrix-matrix multiplication.
4. Covariance and cross correlation. One often needs to compute such statistics on vectors of input signals in order to form matrices and vectors that are further processed.
Conventional techniques for performing each of these operations will be described in greater detail below.
In the case of determining the solution of a set of linear equations, the problem in matrix notation may be expressed as:
Ax=y
(1)
where A is a known square matrix of complex values, y is a known vector of complex values, and x is an unknown complex vector. There are numerous techniques for the numerical solution of such equations. However, some of these techniques suffer from numerical instabilities. A numerically robust technique for solving Equation (1) is known as QR decomposition or QR factorization via Givens rotations, and is described in, e.g., G. H. Golub and C. F. Van Loan, “Matrix Computations,” 3
rd
ed., Johns Hopkins Univ. Pr., 1996. This approach involves factoring the matrix A into the product:
A≡QR
(2)
where Q is a unitary matrix and R is a right upper triangular matrix. The meaning of “right upper triangular” is that all of the components of R below the main diagonal are zeroes. Then, both sides of Equation (1) are multiplied by the conjugate transpose (i.e., the Hermitian transpose) of Q, denoted Q
H
.
Q
H
Ax=Q
H
y
(3)
Substituting Equation (2) into Equation (3) gives:
Q
H
QRx=Q
H
y
(4)
Since Q
H
Q equals the Identity matrix, Equation (4) reduces to:
Rx=Q
H
y
(5)
Equation (5) is in a form that can be solved easily for each component of x using a technique known as “back substitution.” The term “back substitution” refers to an iterative method where first the bottom row of the matrices in Equation (5), which has the most zeroes and only one unknown, is solved. Then the solution is substituted into the next row above, and that row is then solved. This process continues until all the rows of the matrices in Equation (5) are solved.
An effective and numerically stable method for finding the unitary matrix Q
H
is as a product of individual so-called “Givens rotations,” each one of which zeroes out one element of the preceding matrix without disturbing the previously placed zeroes. See, e.g., W. Givens, “Computation of Plane Unitary Rotations Transforming a General Matrix To Triangular Form,” J. Soc. Indust. Appl. Math., Vol. 6, No. 1, p. 26, March 1958. Givens rotations are also known in the art as being useful for performing Recursive Least Squares adaptive algorithms.
An example illustrating the triangulation of a small matrix equation using Givens rotations will now be described, with reference to
FIGS. 1 through 5
. Equation (6) below is an expansion of Equation (1) showing the individual matrix and vector elements for the example.
(
a
11
a
12
a
13
a
14
a
21
a
22
a
23
a
24
a
31
a
32
a
33
a
34
a
41
a
42
a
43
a
44
)
(
x
1
x
2
x
3
x
4
)
=
(
y
1
y
2
y
3
y
4
)
(
6
)
FIG. 1
shows the stages of the corresponding Givens rotations. In the six stages shown in
FIG. 1
, zeroes are successively placed in a five by four array. The letters at the head of each array indicate that four of the columns are elements of the matrix A being transformed and the fifth column has elements of the vector y being transformed. The zeroes in bold type indicate the zeroes that are being placed in each stage. Equation (7) below shows in more detail how one does the first unitary transformation in stage one of FIG.
1
. More particularly, one applies a two by two complex unitary matrix to the first two rows to force one element to a zero, the other elements all being transformed to new values. The “*” symbol indicates the complex conjugate.
(
c
*
s
*
-
s
c
)
(
a
11
a
12
a
13
a
14
y
1
a
21
a
22
a
23
a
24
y
2
)
=
(
a
11
′
a
12
′
a
13
′
a
14
′
y
1
′
0
a
22
′
a
23
′
a
24
′
y
2
′
)
(
7
)
By multiplying out the matrices to find the element which is being forced to zero, one arrives at the equation:
−
sa
11
+ca
21
=0 (8)
together with the unitary constraint:
|
s|
2
+|c|
2
=1 (9)
These equations may be satisfied by:
c
=
a
11
&LeftBracketingBar;
a
11
&RightBracketingBar;
2
+
&LeftBracketingBar;
a
21
&RightBracketingBar;
2
and
(
10
)
s
=
a
21
&LeftBracketingBar;
a
11
&RightBracketingBar;
2
+
&LeftBracketingBar;
a
21
&RightBracketingBar;
2
(
11
)
The value of the non-zero transformed element a
11
′ is:
a
11
′
=
&LeftBracketingBar;
a
11
&RightBracketingBar;
2
+
&LeftBracketingBar;
a
21
&RightBracketingBar;
2
&LeftBracketingBar;
a
11
&RightBracketingBar;
2
+
&LeftBracketingBar;
a
21
&RightBracketingBar;
2
,
(
12
)
a real number. The matrix also “rotates” all other elements on the two rows.
It is well known that QR decomposition using Givens rotations, as described above, can be solved rapidly in a triangular shaped two dimensional systolic array. See, e.g., W. M. Gentleman and H. T. Kung, “Matrix triangularization by systolic arrays,” SPIE V. 298, p. 19, 1981.
FIGS. 2-5
show the beginning of the procedure for triangulating a five by four matrix equation on a triangular array of processor elements (PEs). The round boxes in
FIGS. 2 through 5
are special “head” elements that compute the c
LandOfFree
Pipelined linear array of processor elements for performing... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Pipelined linear array of processor elements for performing..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Pipelined linear array of processor elements for performing... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3261739