Vehicle navigation system with non-overflow digital filter

A vehicle navigation system uses a one-multiplier Gray-Markel filter. The sign parameter of each stage of the filter is selected by an algorithm which limits the maximum signal passing through the filter, thereby preventing overflow.

BACKGROUND OF THE INVENTION 
This invention relates to digital signal processing, and has particular 
relation to one-multiplier Gray-Markel filters used in vehicle navigation 
systems. 
A one-multiplier Gray-Markel filter has one or more stages, each of which 
includes a multiplier, a delay element, and three summers. The first 
summer is driven by the filter input and the delay element, the second 
summer is driven by the filter input and the multiplier, and the third 
summer is driven by the multiplier and the delay element. The third summer 
always acts as an adder, but the first summer acts as a subtracter (filter 
input minus delay element output) when the second summer acts as an adder, 
and acts as an adder when the second summer acts as a subtracter (filter 
input minus multiplier output). Each stage therefore has a sign parameter. 
The sign parameter of a stage is +1 when the second summer acts as an 
adder, and is -1 when the second summer acts as a subtracter. 
The conventional art is embodied in the seminal article, A. H. Gray, Jr. 
and J. D. Markel, "Digital Lattice and Ladder Filter Synthesis", IEEE 
Trans. AU, AU-21, pp. 491-500, December, 1973. In that art, the average 
energy of the signal passing through the filter must be kept below some 
preselected maximum. That article set out an algorithm for selecting the 
sign parameter of each stage so that this average energy criterion is met. 
This criterion is appropriate in, for example, voice synthesis and 
compression. Overall voice quality is improved when this criterion is 
selected, even though the filter overflows from time to time. Each 
overflow is so brief that it is hardly noticeable, and is rapidly damped 
out by subsequent input signals. 
This is not the case in vehicle navigation. Errors do not damp out; they 
accumulate. This is especially true when the navigation signal is part of 
a servo loop, used to control the vehicle, and not just locate it. In this 
case, the maximum signal passing through the filter must be kept below the 
preselected maximum. 
SUMMARY OF THE INVENTION 
The present invention describes and claims a navigation system in which a 
Gray-Markel filter is used, and in which the sign parameter of each stage 
of the filter is selected by an algorithm which limits the maximum signal 
passing through the filter (thereby preventing overflow), even at the cost 
of increasing the average energy of the signal.

DETAILED DESCRIPTION OF THE DRAWINGS 
FIG. 1 shows a stage 10 of a one-multiplier Gray-Markel Filter. Each stage 
10 has a first input 12 which drives a plus input 14 of a first summer 16 
and a plus input 18 of a second summer 20. An output 22 of the first 
summer 16 drives an input 24 of a multiplier 26, which multiplies the 
number applied to the input 24 by a constant k. k lies between -1 and +1, 
inclusive. The output 28 of the multiplier 26 drives a variable input 30 
of the second summer 20. An output 32 of the second summer 20 drives a 
first output 34 of the stage 10. 
A second input 36 drives an input 38 of a delay element 40, an output 42 of 
which drives a first plus input 44 of a third summer 46. The output 28 of 
the multiplier 26 drives a second plus input 48 of the third summer 46. An 
output 50 of the third summer 46 drives a second output 52 of the stage 
10. The output 42 of the delay element 42 also drives a complement input 
54 of the first summer 16. It is called a complement input because it is a 
plus input when the variable input 30 of the second summer 20 is a minus 
input, and it is a minus input when the variable input 30 of the second 
summer 20 is a plus input. 
In FIG. 2, a zeroth stage 56 is cascaded with a first stage 58 to form a 
two-stage one-multiplier Gray-Markel filter 60. In this case: 
the first input 62 of the first stage 58 is the input of the filter 60; 
the first output 64 of the first stage 58 is the first input of the zeroth 
stage 56; 
the first output 66 of the zeroth stage 56 is connected to the second input 
of the zeroth stage 56; 
the second output 70 of the zeroth stage 56 is the second input of the 
first stage 58; and 
the first stage 58 has a second output 72. 
Additional stages may be cascaded as desired. Regardless of the number of 
stages, the first output and second input of the zeroth stage 56 are tied 
together. The first input 62 of the highest stage (the first stage 56 in a 
two stage filter) is, as noted above, the input of the filter 60. The 
second inputs 68, 70 of each stage 56, 58, and the second output 72 of the 
highest stage 58 are tapped by multipliers 74, 76, 78, the outputs of 
which are summed in a summer 80. The output 82 of the summer 80 is the 
output 84 of the filter 60. Any or all of the multipliers 74, 76, 78 may 
be omitted if desired, as may some of the taps 68, 70, 72 driving them. 
The conventional (average energy limitation) method for determining the 
sign parameter follows: 
Let k(m) be the multiplication factor in the multiplier 26 of the mth stage 
of a one-multiplier Gray-Markel filter which has M stages, 0 through M-1, 
inclusive. We seek S(m), the sign parameter of the mth stage. Define: 
EQU q(m)=((1+.vertline.k(m).vertline.)/(1-.vertline.k(m).vertline.)).sup.1/2.(1 
) 
and let the m*th stage have the k(m) of the largest magnitude, that is, 
EQU m*=arg[max{.vertline.k(m).vertline.}],0.ltoreq.m.ltoreq.M-1,(2) 
Now let: 
EQU Q(m*)=1, (3) 
and let: 
EQU S(m*)=sgn(k(m*)) (4) 
We recursively define S(m+1) and Q(m+1) for m=m*, and increasing all the 
way to m=M-2, as follows: 
##EQU1## 
Q(M-1) need not be computed once S(M-1) has been computed, but it does no 
harm to compute it if the user finds it convenient to do so, as, for 
example, for ease of programming. 
We likewise recursively define S(m-1) and Q(m-1) for m=m*, and decreasing 
all the way to m=1, as follows: 
##EQU2## 
As before, Q(0) need not be computed once S(0) has been computed, but may 
be computed if convenient. 
FIG. 3 shows how FIGS. 3a-3c are arranged. FIGS. 3a-3c together form a flow 
chart showing this prior art algorithm. An important feature of this 
algorithm is that S(m)=sgn(k(m)) sometimes and S(m)=-sgn(k(m)) sometimes. 
FIG. 4 is a flow chart showing the algorithm included in the present 
invention: S(m)=-sgn(k(m)), always. Applicant has performed computer 
simulations of many multi-stage one-multiplier Gray-Markel filters, and 
has never found a sign parameter assignment for all stages which matches 
the sign parameter assignment made under the average energy limitation 
algorithm of the prior art. 
FIG. 5 shows the complete invention. A vehicle 86 has a navigation sensor 
88 mounted on it. The sensor 88 produces a navigation signal 90 indicative 
of its position, orientation, linear velocity, rotational velocity, linear 
acceleration, rotational acceleration, or any combination of the 
foregoing. The sensor 88 may include a prefilter for digitizing, 
demodulating, or other prefiltering of the navigational signal. The 
navigation signal 90 is then applied to a one-multiplier Gray-Markel 
filter 92 with stages having sign parameters produced by the 
S(m)=-sgn(k(m)) rule. The Gray-Markel filtered signal 94 is then applied 
to a display 96. The display 96 may include a postfilter, and may display 
the signal 94 to a human operator, to other apparatus (whether in a servo 
loop or not), or both. 
FIG. 6 shows the details of one stage 110 of the improved Gray-Markel 
filter 92 included in FIG. 5. The numbering of the elements of FIG. 6 
follows that of FIG. 1, incremented by 100. 
Two significant differences distinguish the apparatus shown in FIG. 6 from 
that shown in FIG. 1. 
The first difference lies in the sign of present invention's input 154 to 
summer 116. In FIG. 1, the prior art sign of input 54 to summer 16 was 
always the inverse of the sign of the input 30 to summer 20. In the 
present invention shown in FIG. 6, the sign of input 154 to summer 116 is 
always the sign of k. 
The second difference lies in the sign of present invention's input 130 to 
summer 120. In FIG. 1, the prior art input 30 to summer 20 could have a 
sign which was either positive or negative, as the needs of the 
application might require. In FIG. 6, the present invention removes this 
freedom: the sign of input 130 to summer 120 is always the negative of the 
sign of k. 
All other inputs (114 to summer 116, 118 to summer 120, and both 144 and 
148 to summer 146) are positive in the present invention, just as their 
analogous inputs (14 to summer 16, 18 to summer 20, and both 44 and 48 to 
summer 46) are positive in the prior art. 
SCOPE OF THE INVENTION 
Particular embodiments of the present invention have been disclosed in some 
detail, but the true spirit and scope of the present invention are not 
limited thereto. Such spirit and scope are limited only by the appended 
claims, and their equivalents.