Reducing Computational Complexity in Determining the Distance From Each of a Set of Input Points to Each of a Set of Fixed Points
AssigneeTexas Instruments Incorporated
InventorChanaveeragouda V Goudar
Life of this patent
Estimating the term…
Abstract
An aspect of the present invention takes advantage of the fact that the coordinates of fixed points do not change, and thus the energy (sum of squares of the coordinates defining the vector) of each fixed point is computed and stored. The energy of each variable input point may also be computed. The distance between each pair of fixed and input points is computed based on the respective energies and the dot product.
Claims23
A method of computing the distance between each of L input points and R fixed points, wherein L and R are integers having a value greater than 1, the with one of said input points being represented by (Iw1, Iw2, . . . , Iwn) and jth one of said fixed points being represented by (Fj1, Fj2, . . . , Fjn), said method comprising:
- (a) computing the squares of the coordinates (Fj1, Fj2, . . . , Fjn) of each of said R fixed points;
- (b) computing the energy of a first input point, wherein the energy of a vector equals the sum of the squares of the coordinates (Iw1, Iw2, . . . , Iwn) of the vector;
- (c) computing a dot product sum of said first input point with a first fixed point, wherein said first input point and said first fixed point are contained in said L inputs points and said R fixed points respectively;
- (d) computing a distance of said first input point with said first fixed point based on said data of (a), said dot product sum and said energy of said first input point computed in (b),
- wherein (b)-(d) are repeated for multiple combinations of input points and fixed points combination.
A method of computing a weighted distance between each of L input points and R fixed points according to a weight vector, wherein L and R are integers having a value greater than 1, the with wth one of said input points being represented by (Iw1, Iw2, . . . , Iwn) and jth one of said fixed points being represented by (Fj(1), Fj(2), . . . , Fj(n)), said weighted vector being represented by (G(1), G(2), . . . , G(n)), and said weighted distance (WMSEw,j) between said wth input point and said jth fixed point being represented by:
- WMSE
- w
- ,
- j
- =
- ∑
- i
- =
- l
- n
-
- G
-
- (
- i
- )
-
- (
- I
- w
-
- (
- i
- )
- -
- F
- j
-
- (
- i
- )
- )
- 2
- said method comprising:
- computing a first aggregated value equaling:
- ∑
- i
- =
- 1
- 10
-
- W
- LSF
-
- (
- i
- )
-
- (
- I
- LSF
- l
-
- (
- i
- )
- )
- 2
- computing a second aggregated value equaling
- ∑
- i
- =
- 1
- 10
-
- W
- LSF
-
- (
- i
- )
-
- (
- C
- LSF
- r
-
- (
- i
- )
- )
- 2
- computing a third aggregated value equaling
- ∑
- i
- =
- 1
- n
-
- (
- -
- 2
- *
- G
-
- (
- i
- )
-
- I
- w
-
- (
- i
- )
- )
- .
- F
- j
-
- (
- i
- )
- and adding said first aggregated value, said second aggregated value and said third aggregated value to generate said weighted distance.
A computer readable medium carrying one or more sequences of instructions for causing a system to compute the weighted distance between each of L input points and R fixed points according to a weight vector, wherein L and R are integers having a value greater than 1, the with wth one of said input points being represented by (Iw1, Iw2, . . . , Iwn) and jth one of said fixed points being represented by (Fj(1), Fj(2), . . . , Fj(n)), said weighted vector being represented by (G(1), G(2), . . . , G(n)), and said weighted distance (WMSEw,j) between said wth input point and said jth fixed point being represented by:
- wherein execution of said one or more sequences of instructions by one or more processors contained in said system causes said one or more processors to perform the actions of:
- computing a first aggregated value equaling:
- ∑
- i
- =
- 1
- 10
-
- W
- LSF
-
- (
- i
- )
-
- (
- I
- LSF
- l
-
- (
- i
- )
- )
- 2
- computing a second aggregated value equaling
- ∑
- i
- =
- 1
- 10
-
- W
- LSF
-
- (
- i
- )
-
- (
- C
- LSF
- r
-
- (
- i
- )
- )
- 2
- computing a third aggregated value equaling
- ∑
- i
- =
- 1
- n
-
- (
- -
- 2
- *
- G
-
- (
- i
- )
-
- I
- w
-
- (
- i
- )
- ·
- F
- j
-
- (
- i
- )
- and adding said first aggregated value, said second aggregated value and said third aggregated value to generate said weighted distance.
A computer readable medium carrying one or more sequences of instructions for causing a system to compute the distance between each of L input points and R fixed points, wherein L and R are integers having a value greater than 1, the with one of said input points being represented by (Iw1, Iw2, . . . , Iwn) and jth one of said fixed points being represented by (Fj1, Fj2, . . . , Fjn), wherein execution of said one or more sequences of instructions by one or more processors contained in said system causes said one or more processors to perform the actions of:
- (a) computing the squares of the coordinates (Fj1, Fj2, . . . , Fjn) of each of said R fixed points;
- (b) computing the energy of a first input point, wherein the energy of a vector equals the sum of the squares of the coordinates (Iw1, Iw2, . . . , Iwn) of the vector;
- (c) computing a dot product sum of said first input point with a first fixed point, wherein said first input point and said first fixed point are contained in said L inputs points and said R fixed points respectively;
- (d) computing a distance of said first input point with said first fixed point based on said data of (a), said dot product sum and said energy of said first input point computed in (b),
- wherein (b)-(d) are repeated for multiple combinations of input points and fixed points combination.
A device comprising an encoder operable to:
- (a) receive L input points and R fixed points, wherein L and R are integers having a value greater than 1, the with one of said input points being represented by (Iw1, Iw2, . . . , Iwn) and jth one of said fixed points being represented by (Fj1, Fj2, . . . , Fjn);
- (b) compute the squares of the coordinates (Fj1, Fj2, . . . , Fjn) of each of said R fixed points;
- (c) compute the energy of a first input point, wherein the energy of a vector equals the sum of the squares of the coordinates (Iw1, Iw2, . . . , Iwn) of the vector;
- (d) compute a dot product sum of said first input point with a first fixed point, wherein said first input point and said first fixed point are contained in said L inputs points and said R fixed points respectively;
- (e) compute a distance of said first input point with said first fixed point based on said data of (a), said dot product sum and said energy of said first input point computed in (b),
- wherein (c)-(e) are repeated for multiple combinations of input points and fixed points combinations.
A apparatus for computing the distance between each of L input points and R fixed points, wherein L and R are integers having a value greater than 1, the with one of said input points being represented by (Iw1, Iw2, . . . , Iwn) and jth one of said fixed points being represented by (Fj1, Fj2, . . . , Fjn), said apparatus comprising:
- (a) means for computing the squares of the coordinates (Fj1, Fj2, . . . , Fjn) of each of said R fixed points;
- (b) means for computing the energy of a first input point, wherein the energy of a vector equals the sum of the squares of the coordinates (Iw1, Iw2, . . . , Iwn) of the vector;
- (c) means for computing a dot product sum of said first input point with a first fixed point, wherein said first input point and said first fixed point are contained in said L inputs points and said R fixed points respectively;
- and
- (d) means for computing a distance of said first input point with said first fixed point based on said data of said R fixed points, said dot product sum and said energy of said first input point.
Dependencies are inferred from the claim text.