Pulse or digital communications – Testing
Reexamination Certificate
2000-04-20
2003-12-16
Vo, Don N. (Department: 2631)
Pulse or digital communications
Testing
Reexamination Certificate
active
06665335
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 computing the amount of shift between two signals.
DESCRIPTION OF THE RELATED ART
A great variety of systems may be characterized by the property that they generate a series of signals which are shifted and noise-perturbed versions of some known template signal. For example, radar systems operate by repeatedly transmitting a known pulse template and receiving the pulse reflections generated by objects (such as aircraft) which intercept the field of view of the radar beam. The pulse reflections are delayed versions of the transmitted pulse and are corrupted by various forms of noise such as multipath noise. The time-delay between the transmitted pulse and the pulse reflection is a measure of an object's distance.
The problem of estimating the shift (e.g. time-delay) between two signals x(n) and y(n) is one of the most fundamental problems in signal processing. Perhaps the most popular method for solving the shift estimation problem involves the use of cross-correlation. The cross-correlation method involves computing a cross-correlation
R
xy
(
τ
)
=
∑
n
x
(
n
+
τ
)
y
(
n
)
,
(A1)
for shift values &tgr; spanning a range of expected values. The shift-value &tgr;
max
for which the cross-correlation R
xy
(&tgr;) is maximized is taken to be an estimate for the shift between signals x(n) and y(n).
The problem of shift estimation is just as relevant for periodic signals, or more generally, for signals defined on the integers modulo N, where N is a positive integer. (Physically realizable discrete-time signals are finite in duration and may be naturally interpreted as being defined on the integers modulo N.) Given two signals f and g defined on the integers modulo N, where signal g is known to be a shifted version of signal f the circular cross-correlation
R
fg
(
d
)
=
∑
n
=
0
N
-
1
f
(
[
n
+
d
]
N
)
g
(
[
n
]
N
)
(A2)
may be evaluated for shift value d equal to 0, 1, 2, . . . , N−1. The shift-value d
max
for which the circular cross-correlation R
fg
(d) is maximized may be taken as an estimate for the circular shift between signals f and g. Thus, the circular cross-correlation method requires N
2
multiplies and N(N−1) additions in order to generate a shift estimate between two functions. More efficient methods do exist. All of them are complicated and cannot reduce the numerical complexity significantly.
It can be shown that the circular cross-correlation of signals f and g may be expressed as a circular convolution, i.e.
R
fg
(
d
)
=
∑
k
=
0
N
-
1
f
(
[
d
-
k
]
N
)
u
(
[
k
]
N
)
,
(A3)
where signal u denotes the time-reversal of signal g, i.e.
u
([
k]
N
)=
g
([−
k]
N
). (A4)
Thus, the discrete Fourier transform {circumflex over (R)}
fg
of circular cross-correlation function R
fg
equals the product of the discrete Fourier transforms {circumflex over (f)} and û of signals f and u respectively, i.e.
{circumflex over (R)}
fg
={circumflex over (f)}·û.
(A5)
Thus, the circular cross-correlation function R
fg
may be computed indirectly as suggested by the following expression:
R
fg
=IDFT
(
{circumflex over (f)}·ĝ
), (A6)
where IDFT denotes the inverse discrete Fourier transform operator. If Fast Fourier Transforms (FFTs) are used to compute the pair of forward DFTs and the inverse DFT, this method for computing the circular cross-correlation function R
fg
has computational complexity of order &agr;N log
2
(N), where &agr; is a fixed number. Thus, this indirect method for computing the circular cross-correlation function is significantly more efficient than the exhaustive cross-correlation method as represented by equation (A2). However, according to Mitra et al., it is only useful for N>256, due to complex number overhead and due to the factor &agr;.
Given a signal h defined on the integers modulo N, the Discrete Fourier transform ĥ of signal h may be defined as
h
^
(
k
)
=
∑
n
=
0
N
-
1
h
(
n
)
·
exp
(
-
j2
π
nk
N
)
,
(A7)
where index k varies from 0 to N−1. Let f
d
denote the signal obtained by shifting the elements of signal f by d positions, i.e. f
d
([n]
N
)=f([n+d]
N
). Using the DFT definition (A7), it can be shown that the discrete Fourier transform {circumflex over (f)}
d
of shifted signal f
d
is given by
f
^
d
(
k
)
=
f
^
(
k
)
·
exp
(
j
dk2
π
N
)
,
(A8)
where k varies from 0 to N−1, and where {circumflex over (f)} denotes the discrete Fourier transform of signal f Expression (A8) implies that
Arg
[
f
^
d
(
k
)
]
-
Arg
[
f
^
(
k
)
]
=
dk2
π
N
+
2
π
r
,
(A9)
for some integer r, where Arg[z] denotes the principle angle of complex number z. Solving for shift parameter d gives the expression
d
=
N
2
π
k
{
Arg
[
f
^
d
(
k
)
]
-
Arg
[
f
^
(
k
)
]
}
+
Nr
k
.
(A10)
Expression (A10) may be used as the basis for a shift estimation method. Let g be a signal whose shift relative to template signal f is unknown. Let ĝ denote the discrete Fourier transform of signal g. Substituting the transform ĝ for the transform {circumflex over (f)}
d
in expression (A10) gives
d
=
N
2
π
k
{
Arg
[
g
^
(
k
)
]
-
Arg
[
f
^
(
k
)
]
}
+
Nr
k
.
(A11)
Since the integer value r is not known, there may be ambiguity in the value of shift parameter d. For example, the quantity
Nr
/
k
, and therefore, the right hand side of expression (A11), may attain k distinct values modulo N depending on the value of integer r. However, if k equals one, the shift estimation value d is determined unambiguously. Thus, another method for estimating the shift between signals f and g may be summarized by the formula
d
=
N
2
π
{
Arg
[
g
^
(
1
)
]
-
Arg
[
f
^
(
1
)
]
}
(
mod
N
)
.
(A11)
It is noted that this phase-difference method is much more efficient computationally than the exhaustive cross-correlation and FFT-based cross-correlation methods described above as shown in FIG.
1
. The computational effort for the phase-difference method is order N since only one DFT coefficient of the signal g needs to be computed. However, the performance (estimation accuracy) of the phase-difference method degrades at much lower noise levels than the cross-correlation methods as shown in FIG.
2
.
Furthermore, the phase-difference method and the cross-correlation methods provide no mechanism for improving estimation accuracy based on knowledge of the noise process which operates on the shifted template f to generate signal g.
Thus, there exists a substantial need for a system and method which could estimate the shift between two signals with a combination of computational efficiency and noise immunity. Furthermore, there exists a need for a shift estimation system and method which could take advantage of information about the underlying noise process to improve estimation accuracy.
There is an implied tradeoff between computational efficiency, and noise resistance as shown by FIG.
2
. Thus, there exists a need for a method which could explicitly determine the tradeoff.
SUMMARY OF THE INVENTION
The present invention comprises a system and method for estimating the shift between two signals. The shift between the signals may be interpreted as time-delay, spatial shift, rotation angle, etc. For example, the present invention may be used to estimate the shift in a signal g relative to a template signal f. The shift estimation system method comprises: (a) receiving a first signal g, where the first signal g may be represe
Rajagopal Ram
Wenzel Lothar
Hood Jeffrey C.
Meyertons Hood Kivlin Kowert & Goetzel P.C.
National Instruments Corporation
Vo Don N.
LandOfFree
System and method for estimating a shift between two signals... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for estimating a shift between two signals..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for estimating a shift between two signals... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3178534