Image analysis – Pattern recognition – Classification
Reexamination Certificate
2000-04-27
2003-03-18
Chang, Jon (Department: 2623)
Image analysis
Pattern recognition
Classification
C382S253000
Reexamination Certificate
active
06535640
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to the field of signal processing, and in particular, to an improved system and method for identifying which signal vector in a collection of signal vectors is nearest (in the sense of some norm) to a given input signal vector.
DESCRIPTION OF THE RELATED ART
Many problems in engineering and the applied sciences reduce to the problem of distance minimization, i.e. the problem of identifying which vector in a particular collection of vectors is closest to a given input vector. For example, in the field of telecommunications, a transmitter may transmit a stream of symbols from a predefined set of symbols. Each of the predefined symbols may be associated with a corresponding bit pattern. A receiver may receive the stream of symbols corrupted with noise, and may perform a distance minimization to map each of the received symbols to one of the predefined symbols.
Another fundamental problem in the field of telecommunications is the so-called delay estimation problem. A transmitter may transmit a known template signal to a receiver. A receiving device may receive a delayed and noise-perturbed version of the known template signal. The receiving device may perform a distance minimization to estimate the time-delay between the received signal (i.e. the delayed noise-perturbed version of the template signal) and the template signal. Namely, the receiving device may generate an ensemble of time-delayed versions of the template signal, and may select the particular time-delayed version of the ensemble which is closest to the received signal in the sense of some vector norm. When the norm is the Euclidean norm, this distance minimization is equivalent to traditional autocorrelation.
In general, the distance minimization problem may be stated as follows. Given a collection X of vectors (e.g. signals, sequences, codes, symbols, etc.) and an input vector, identify the particular vector in the collection X which is closest to the input vector in the sense of some vector norm. In many situations, it is possible to assume that the input vector is within a distance r from exactly one of the vectors in the collection X, where distance r is less than or equal to ½ of the minimum distance between vectors in the collection X. This assumption will be referred to herein as the bounding assumption. An analysis of the noise mechanisms which perturb input vectors away from the collection X may give rise to an estimate for distance r.
Given a collection of N vectors P(0), P(1), P(2), . . . , P(N−1), and an input vector which obeys the bounding assumption with respect to the collection and a bounding radius r, one prior art method for identifying the closest vector in the collection to the input vector may be described as follows:
k=
0;
MORE: compute S(k)=∥P(k)−g∥
if (S(k)<r)
Output k as closest vector index;
Return;
else
k=k+1
goto MORE
endif
wherein ∥.∥ denotes a given vector norm. In other words, this prior art algorithm prescribes sequentially searching through the collection of vectors until the solution vector is identified. The solution vector is distinguished by having a distance from input vector g which is smaller than the bounding radius r. This sequential search algorithm identifies the solution vector in N/2 iterations on average, and at worst case in N iterations.
In many applications, the average convergence in N/2 iterations provided by the sequential search algorithm may be too slow, especially when N is large. Thus, there exists a need for a system and method which could more efficiently determine the signal vector from a collection of signal vectors which is closest to a given input vector.
Furthermore, the sequential search algorithm provides no mechanism for increasing the convergence rate when the bounding radius is small, i.e. when input vectors tightly cluster around vectors of the vector collection X. Thus, there exists a need for a system and method which could identify the solution vector (i.e. the vector with minimum distance to the input vector) with increased speed when the bounding radius r is small.
SUMMARY OF THE INVENTION
A signal analysis system and method according to the present invention may, at least in some embodiments, address the problems described above associated with determining the closest vector in a vector collection to a given input signal vector. The signal analysis system may comprise an input (e.g. a receiving device), a memory (e.g. one or more of RAM, ROM, non-volatile memory, etc.), and a processing unit. The memory may store a collection of vectors, and a table of mutual distances between pairs of the vectors in the collection. The memory may also store a software program for determining the closest vector in the vector collection to the input signal vector.
The input may be configured to receive an input signal from a communication medium (e.g. the Public Switched Telephone Network, an Ethernet bus, a PCI bus, the atmosphere, an optical fiber, a transducer, etc.). The input signal may comprise a sequence of samples, e.g., a sequence of samples of an analog signal.
The processing unit may be coupled to the memory, and may be configured to receive an input vector corresponding to the input signal and execute the software program for determining the closest vector. The processing unit may be further configured to execute the following methodology starting with index m=0 in order to determine the closest vector in the vector collection X(0) to the given input signal vector. The closest vector is referred to herein as the solution vector.
(1) select a vector P(k
m
) in the vector collection X(m);
(2) analyze the table of mutual distances to determine a filtered subset X(m+1) of the vector collection X(m), wherein the vectors of the filtered subset X(m+1) have a distance to the selected vector P(k
m
) which is greater than a first value FV
m
and smaller than a second value SV
m
, where the first value and the second value depend on index m;
(3) set m=m+1, i.e. increment index m;
(4) repeat (1), (2) and (3) zero or more times;
(5) identify a solution vector from the filtered collection, preferably after one or more iterations of (1), (2) and (3); and
(6) provide an output indication to a user in response to said identification of the solution vector.
Because of (3), the filtered subset X(m+1) becomes a new vector collection X(m) in a subsequent iteration of (1) and (2). The processing unit may repeat (1), (2) and (3) zero or more times until the selected vector P(k
m
) has a distance from the input signal which is less than a bounding radius value.
The processing unit may be further configured to (c) compute a distance S(m) between the selected vector P(k
m
) and the input vector, and (d) determine if the distance S(m) is smaller than the bounding radius value. The processing unit is configured to perform (c) and (d) after (1) and prior to (2). The processing unit may compute the first value FV
m
by subtracting the bounding radius value from the distance S(m), and compute the second value SV
m
by adding the bounding radius value to the distance S(m).
In the preferred embodiment, the memory stores a minimum distance data determination program. The processing unit may be configured to iteratively perform (1), (2), and (3) in response to execution of the minimum distance data determination program.
In a shift estimation or time-delay estimation application, the collection of vectors may represent shifted (e.g. delayed) versions of a known template signal, and input signal vector may represent a shifted and noise-perturbed version of the template signal, wherein the shift value (e.g. time-delay) is not known beforehand. The solution vector provides an estimate of the shift value. The output indication provided to the user may comprise an indication of the shift value or a data value computed in response to the shift value. For example, in a radar application, the shift value may be converted to an estimated ran
Nair Dinesh
Rajagopal Ram
Wenzel Lothar
Chang Jon
Hood Jeffrey C.
Le Brian
Meyertons Hood Kivlin Kowert & Goetzel P.C.
National Instruments Corporation
LandOfFree
Signal analysis system and method for determining a closest... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Signal analysis system and method for determining a closest..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Signal analysis system and method for determining a closest... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3077919