Patent US4823299A successfully refreshed from Google Patents.
US4823299A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Systolic VLSI array for implementing the Kalman filter algorithm
Assignee: California Institute of Technology
•
Filing: 1987-04-01
•
Granted: 1989-04-18
•
Expires: 2007-04-01
Abstract
Abstract A method and apparatus for processing signals representative of a complex matrix/vector equation. More particularly, signals representing an orderly sequence of the combined matrix and vector equation, known as a Kalman filter algorithm, are processed in real time in accordance with the principles of this invention. The Kalman filter algorithm is rearranged into a Faddeeva algorithm, which is a matrix-only algorithm that is modified to represent both the matrix and vector portions of the Kalman filter algorithm. The modified Faddeeva algorithm is embodied into electrical signals which are applied as inputs to a systolic array processor. The processor performs triangulation and nullification on the input signals, and delivers an output signal which is a real-time solution to the input signals.
Inventors
- 👤 Jaw J. Chang
- 👤 Hen-Geul Yeh
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 06:32
CPC Classifications
H; H03; H03H; H03H17/00; H03H17/02; H03H17/0248; H03H17/0255; H03H17/0257
Claims Analysis
Total Claims: 18
Claim 1
Independent Claim
79 words
A method of solving equations having both matrix and vector terms in real time, said methiod comprising the steps of: mapping a first equation, having both matrix and vector terms, into an equivalent equation which contains matrix-only values that represent both the matrix and vector terms of said first equation; applying electrical signals representing the matrix-only values of the equivalent equation to a systolic processing array; and generating in the systolic array a real-time solution to said first equation.
Claim 2
Independent Claim
79 words
A method of solving equations having both matrix and vector terms in real time, said methiod comprising the steps of: mapping a first equation, having both matrix and vector terms, into an equivalent equation which contains matrix-only values that represent both the matrix and vector terms of said first equation; applying electrical signals representing the matrix-only values of the equivalent equation to a systolic processing array; and generating in the systolic array a real-time solution to said first equation.
Claim 3
Dependent Claim
56 words
A method in accordance with claim 1 wherein the equations having matrix and vector terms are characterized as a Kalman filter algorithm and wherein the mapping step is further comprised by the step of: converting every complex matrix and vector term of the Kalman filter algorithm into a matrix-only value for application to said systolic array.
Claim 4
Dependent Claim
67 words
A method in accordance with claim 2 wherein the Kalman filter algorithm includes several known equations, at least one which is not directly convertible into a systolic array form, and said converting step is further characterized by the additional steps of: dividing said one known equation into portions; and representing each portion by an equivalent matrix-only value of a size suitable for processing by said systolic array.
Claim 5
Dependent Claim
34 words
A method in accordance with claim 3 and comprising the additional step of: passing each matrix-only value through said systolic array in order to compute one final output term for said Kalman filter algorithm.
Claim 6
Dependent Claim
83 words
A method in accordance with claim 4 wherein said Kalman filter algorithm includes a fixed number of equations and wherein the representation thereof as a Faddeeva algorithm represents a fixed number of matrix-only values; and said passing step further comprises; temporarily storing output signals from the systolic array which are needed in other computations in said systolic array; inputting the temporarily stored output signals at appropriate times into said systolic array; and cyclically passing each of said matrix-only values through said systolic array.
Claim 7
Dependent Claim
36 words
A method in accordance with claim 5 wherein said fixed number of matrix-only values comprises a fixed number of passes through said systolic array and wherein said passes further comprise in order the following passes: ##STR6##
Claim 8
Independent Claim
101 words
A method of solving equations having matrix and vector terms in real time, said method comprising the steps of: mapping a first equation, having both matrix and vector terms, into an equivalent equation which is represented in matrix-only values that represent the matrix and vector terms of said first equation; applying signals representing the matrix-only values of the equivalent equation to a systolic processing array; and triangulating and nullifying the signals in said systolic processing array whereby a real time solution to the matrix and vector terms of said first equation appears as an output signal from said systolic processing array.
Claim 9
Independent Claim
101 words
A method of solving equations having matrix and vector terms in real time, said method comprising the steps of: mapping a first equation, having both matrix and vector terms, into an equivalent equation which is represented in matrix-only values that represent the matrix and vector terms of said first equation; applying signals representing the matrix-only values of the equivalent equation to a systolic processing array; and triangulating and nullifying the signals in said systolic processing array whereby a real time solution to the matrix and vector terms of said first equation appears as an output signal from said systolic processing array.
Claim 10
Independent Claim
90 words
A method of implementing a Kalman filter algorithm for a real-time solution, said method comprising the steps of: arranging the vector and matrix terms of said Kalman filter algorithm into matrix-only terms of a Faddeeva algorithm, which matrix-only terms represent both the matrix and vector terms of the Kalman filter algorithm; representing the terms of the Faddeeva algorithm as electrical signals; inputting the electrical signals into a systolic processing array; and processing the electrical signals in the systolic processing array to obtain a real-time solution to said Kalman filter algorithm.
Claim 11
Independent Claim
90 words
A method of implementing a Kalman filter algorithm for a real-time solution, said method comprising the steps of: arranging the vector and matrix terms of said Kalman filter algorithm into matrix-only terms of a Faddeeva algorithm, which matrix-only terms represent both the matrix and vector terms of the Kalman filter algorithm; representing the terms of the Faddeeva algorithm as electrical signals; inputting the electrical signals into a systolic processing array; and processing the electrical signals in the systolic processing array to obtain a real-time solution to said Kalman filter algorithm.
Claim 12
Independent Claim
117 words
A method of implementing the Kalman filter algorithm for a real-time solution to variable terms in the algorithm, said method resulting in an implementation of the Kalman filter algorithm and comprising the ordered steps of: (1) arranging the vector and matrix terms of said Kalman filter algorithm into a Faddeeva algorithm which includes matrix-only terms; (2) placing cell elements according to the size of the matrix to solve the matrix-only terms of the Faddeeva algorithm in a systolic array; (3) steering electrical signals, representing the matrix-only terms of the Faddeeva algorithm into cell elements of the systolic array; and (4) obtaining from the array, real-time output signals indicative of a real-time solution to said Kalman filter algorithm.
Claim 13
Independent Claim
117 words
A method of implementing the Kalman filter algorithm for a real-time solution to variable terms in the algorithm, said method resulting in an implementation of the Kalman filter algorithm and comprising the ordered steps of: (1) arranging the vector and matrix terms of said Kalman filter algorithm into a Faddeeva algorithm which includes matrix-only terms; (2) placing cell elements according to the size of the matrix to solve the matrix-only terms of the Faddeeva algorithm in a systolic array; (3) steering electrical signals, representing the matrix-only terms of the Faddeeva algorithm into cell elements of the systolic array; and (4) obtaining from the array, real-time output signals indicative of a real-time solution to said Kalman filter algorithm.
Claim 14
Dependent Claim
96 words
Apparatus for solving equations having a matrix and vector terms in real time, said apparatus comprising: means for mapping a first equation, having both matrix and vector terms, into an equivalent equation which contains matrix-only values that represent both the matrix and vector terms of said first equation; a systolic array, with an appropriate number of cell elements according to the size of matrix to provide a real-time solution of said matrix-only values, connected to said mapping means; and means for applying electrical signals representing the matrix-only values to said systolic processing array for solution thereof.
Claim 15
Dependent Claim
96 words
Apparatus for solving equations having a matrix and vector terms in real time, said apparatus comprising: means for mapping a first equation, having both matrix and vector terms, into an equivalent equation which contains matrix-only values that represent both the matrix and vector terms of said first equation; a systolic array, with an appropriate number of cell elements according to the size of matrix to provide a real-time solution of said matrix-only values, connected to said mapping means; and means for applying electrical signals representing the matrix-only values to said systolic processing array for solution thereof.
Claim 16
Dependent Claim
41 words
Apparatus in accordance with claim 10 wherein said systolic array further comprises: means for triangulating and nullifying the matrix-only values applied thereto, whereby a real-time solution to the matrix and vector equation appears as an output signal from said systolic array.
Claim 17
Dependent Claim
78 words
Apparatus in accordance with claim 11 wherein the size of the matrix and vector terms varies and the largest matrix term in the first equation is a matrix φ(k), and wherein said systolic array further comprises: a fixed size of 2n by 2n rows and columns, where n is a positive integer, in said array; and means for padding zeros in the non-used spaces of each matrix-only term which has a size in less than that of φ(k).
Claim 18
Dependent Claim
35 words
Apparatus in accordance with claim 12 and further comprising: means at the input of said systolic array for receiving 2n electrical signals; and output means for said systolic array for delivering an n-sized output signal.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1992-04-17 | 1992-10-17 | 1993-04-18 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1996-04-17 | 1996-10-17 | 1997-04-18 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2000-04-17 | 2000-10-17 | 2001-04-18 | $7700.00 | Window Closed / Lapsed |