Anti-Lock Braking System Containing Look-Up Table for Determining Wheel Velocity and Acceleration

This application is related to and incorporates by reference U.S. patent application Ser. No. 08/191,823 by Roger L. Miller entitled "DISASTER AVOIDANCE CLOCK FOR ANTI-LOCK BRAKING SYSTEM", U.S. patent application Ser. No. 08/190,812 by Roger L. Miller and Timothy T. Regan entitled "FAILSAFE VOLTAGE REGULATOR WITH WARNING SIGNAL DRIVER" and U.S patent application Ser. No. 08/190,881, now U.S. Pat. No. 5,372,910, by Roger L. Miller and Thomas P. Harper entitled "ANTI-LOCK BRAKING SYSTEM"; all filed on the same date and assigned to the same assignee as the present application.

This invention relates to use of a look-up table in place of a divider in a digital circuit, and in particular to use of a look-up table to determine a velocity in a low cost anti-lock braking system.

In many digital systems it is necessary to perform divisions where either the dividend or divisor is a fixed quantity. For example, some heart rate monitors measure a time T between two heart beats and determine a heart rate which is the multiplicative inverse 1/T or T.sup.-1 of the time. Another example digital system is an anti-lock braking system which uses a velocity (d/.DELTA.T) which may be determined from a fixed distance d traveled in a measured time .DELTA.T. Because the distance d is fixed, the multiplicative inverse .DELTA.T.sup.-1 of the time .DELTA.T is proportional to the velocity, and anti-lock braking systems may calculate and use the multiplicative inverse .DELTA.T.sup.-1 in place of the velocity.

Prior art digital systems typically determine multiplicative inverses by dividing, using a math block with a hardware divider. Hardware dividers are fast enough for most applications including anti-lock braking system but are expensive because hardware dividers require a large area in an integrated circuit. Other systems use software divide techniques instead of hardware. However, software divides can be too slow for some anti-lock braking system applications. To speed up a software divide, two or more processors working in parallel can be employed, but using more than one processor increases system cost. Accordingly, fast and inexpensive circuits are needed for dividing.

In accordance with the present invention, a digital circuit divides a constant dividend by a variable divisor using a look-up table which, in response to an address signal depending on the divisor, provides a signal indicating the quotient.

In one embodiment, the dividend has a fixed value of one, and the look-up table stores values indicating multiplicative inverses of a predetermined range of divisors. In operation, the circuit factors the divisor as a product of a power of two (2.sup.N) and a factor within the predetermined range of divisors. An address signal indicating the factor is applied, and the look-up table provides a signal which indicates the inverse of the factor. The signal from the look-up table is then converted to the proper scale using the exponent N. The factoring and converting can be accomplished using either logical shifts or addition so that no multiply (or divide) is required.

In one embodiment of the invention, a value to be inverted is factored by storing an integer representation of the value to be inverted in a register then shifting the value in the register left until the most significant non-zero bit of the integer representation is shifted into a carry bit of the register. The shifted value in the register indicates a factor between one and two, (the carry bit representing one and the remaining bits in the register representing a fraction added to one). The number of shifts indicates a power of two which when multiplied by the factor, provides the value to be inverted. The look-up table stores values corresponding to inverses of values between one and two. An inverse value corresponding to the factor is read from the look-up table and shifted to the proper scale as indicated by the number of shifts.

In another embodiment, the entries in the look-up table are compressed to reduce the amount of data stored. Most significant bits which are constant or only change once for all values in the look-up table are not stored but are appended during conversion. The look-up table can be further compressed by only storing values for every other value within the range of the look-up table and incorporating into the stored values a code bit which indicates how to generate values that were not stored in the look-up table.

FIG. 1 shows a block diagram of a rate sensor in accordance with the present invention.

FIG. 2 shows a flow diagram of a process for providing a signal indicating a multiplicative inverse using a look-up table and look-up table compression techniques.

FIG. 1 shows a block diagram of a rate sensor in accordance with the present invention. The rate sensor shown is employed in an anti-lock braking system to provide a digital signal indicating the rotational velocity of a tire. Typical anti-lock braking systems periodically determine the velocity and acceleration of a rotating automobile tire. If a brake locks during braking, the tire stops rotating and skids as the automobile keeps moving. An anti-lock braking system determines from the velocity and acceleration when a skid occurs and temporarily releases the brake. The temporary release of the brake stops the tire from skidding and therefore increases traction between the tire and road and reduces the overall stopping distance of the automobile. In a typical anti-lock braking system, the velocity must be sensed at least once every 5 ms. Accordingly, the tire travels only a short distance between consecutive sensing of velocity, and fast velocity and acceleration calculations are required.

In FIG. 1, a timer 110 includes a counter 114 which counts clock pulses from a clock circuit 118. Counter 114 monitors a wheel speed sensor which includes a gear 116 which rotates at a rate that is proportional to the rotational velocity of a tire. Iron teeth on gear 116 rotate between a magnet and coil 112 and periodically strengthen the magnetic field through coil 112. The changing magnetic field induces an AC voltage which is provided to counter 114 so that counter 114 is periodically reset according to the frequency of the AC voltage from coil 112. Just before counter 114 is reset, a capture register 120 captures from counter 114 a time count C. If wheel 116 stops moving so that clock-counter 114 is not reset within the desired sampling period, a maximum time value is provided to capture register 120 and error status signal may be set. In one exemplary anti-lock braking system, clock 118 provides a 1 MHz clock signal, and the time count C represents the number of microseconds required for gear 116 to rotate the fixed distance from one tooth to the next.

The time count C is typically stored in capture register 120 in an integer representation. An integer representation is a set of bits where each bit represents a different power of two, and the least significant bit (LSB) represents 2.sup.0. For example, a binary integer representation of thirteen is 1101 because 1.times.2.sup.3 +1.times.2.sup.2+ 0.times.2.sup.1 +1.times.2.sup.0 equals 13. An integer representation is a special case of a fixed point representation. In a fixed point representation, each bit represents a different power of two, but the LSB is not restricted to representing 2.sup.0. The LSB represents a power of two that depends on the format of the fixed point representation. For example, in one unsigned 4-bit binary fixed point representation, the LSB corresponds to 2.sup.-3 and 1101 represents 1.625 or (1.times.2.sup.0 +1.times.2.sup.- +0.times.2.sup.-2 +1.times.2.sup.-3).

The structure shown in timer 110 is only one example which can be employed in an anti-lock braking system. Other timers which are known or yet to be developed can be used in place of timer 110.

Capture register 120 stores the count C which indicates the time for wheel 116 to rotate one tooth. Capture register 120 can be a shift register, a memory location, or another storage device. From a fixed distance d that a tire travels while wheel 116 rotates from one tooth to the next and the time .DELTA.T required to travel the distance d, a velocity v may be determined. The velocity v is proportional to the multiplicative inverse of the time .DELTA.T or the time count C (i.e., v.varies..DELTA.T.sup.-1 .varies.C.sup.-1), so that the multiplicative inverse C.sup.-1 of count C can be used instead of the velocity v in calculations performed by the anti-lock braking system. For example, the anti-lock braking system can release braking depending on the inverse of the count or the rate of change in the inverse of the count. The velocity and acceleration in standard length and time units are not needed.

For fixed distance d, a velocity v=d/.DELTA.T can be determined using a look-up table that includes velocity values for every possible value of the time interval .DELTA.T. This would eliminate the need for a conventional multiplier or divider but, in many applications, such look-up tables would be too large to be practical. A mathematical property of division permits use of a smaller look-up table. If time interval .DELTA.T=2.sup.N *.DELTA.t, then the velocity v.sub..DELTA.T which corresponds to the time .DELTA.T and the velocity v.sub..DELTA.t which corresponds to the time .DELTA.t are related by the following equation.

Accordingly, if velocity v.sub..DELTA.l =d/.DELTA.t is known for values of time .DELTA.t between 1 and 2 (or values between any successive powers of two), velocity V.sub..DELTA.T for all other values of time .DELTA.T can be determined by multiplication of v.sub..DELTA.l by an appropriate power of two. In digital systems, multiplying by a power of two is equivalent to a binary shift of a fixed point representation, and neither a multiplier nor a divider is required.

In order to use a smaller look-up table, shift block 130 converts the count C into a factor X between 1 and 2 and an exponent N for a power of two, with C equal to X*2.sup.N. Such conversions are well known in the art and commonly implemented using many well known techniques for conversion of an integer representation to a floating point representation. Shift block 130 may, for example be implemented as software executed on a processor or as hardware which causes the value in register 120 to be factored.

In one embodiment, the count C is initially stored-in capture register 120 in an integer representation, and then shifted to the left. The shift block 130 counts the number of single bit logical left shifts required to shift the most significant non-zero bit of the count C into a carry bit. If the number of shifts is S and capture register 120 contains R bits, the exponent N is R-S. After shifting the count in register 120, the shifted value in register 120 indicates a fraction X' which is between 0 and 1. The carry bit is always one. Accordingly, the combination of the carry bit and the fraction X' indicates a factor X between 1 and 2. The fraction X' provides an address for a look-up table 140 and is approximately equal to the mantissa of the logarithm base 2 of the factor X.

Look-up table 140 holds multiplicative inverse values Y corresponding to a domain of values X between 1 and 2. Look-up table 140 may be implemented as a portion of RAM, ROM, EPROM, EEPROM, or other memory which, in response to an address signal indicating the value X, provides to a decompressor 150 a value Y indicating the multiplicative inverse X.sup.-1 of the value X. The multiplicative inverse X.sup.-1 equals the special case of a quotient with dividend d equal to one. Decompressor 150 converts the value Y from look-up table 140 into the desired velocity (or multiplicative inverse) by combining Y with the exponent N provided by shift block 130. The actions of decompressor 150 depend on the representation of the values Y in the look-up table, and are disclosed in detail for specific embodiments below. Decompressor 150 is typically implemented in software.

In one embodiment, the value Y supplied by look-up table 140 is a floating point representation of the multiplicative inverse X.sup.-1 of the factor X, and decompressor 150 subtracts of the exponent N from an exponent of the floating point representation of the value Y to provide a floating point representation of the inverse C.sup.-1 of count C.

In another embodiment, the value Y supplied by look-up table 140 is a fixed point representation of the multiplicative inverse X.sup.31 1, and decompressor 150 shifts the value Y to the right N bits. Table 1 shows an example of a look-up table having for stored values Y which equal the multiplicative inverse X.sup.-1.

Both X and Y are shown as 4-bit binary values, and stored values Y are rounded to four bits of accuracy.

In still another embodiment, look-up table 140 provides a value Y in a compressed format which reduces the amount of memory required for look-up table 140, and decompressor 150 decompresses a value Y from look-up table 140 while combining the value Y with the exponent N.

In an example embodiment wherein look-up table 140 contains compressed values Y, capture register 120 initially holds a count C which is to be inverted. Count C is provided as a 16-bit integer between $0000 and $FFFF ("$" indicates hexadecimal) and capture register 120 is a 16-bit register. Other limits for the count C are possible. For example, a minimum count such as $1FF may be set to avoid determination of the multiplicative inverse of zero. Also, an upper limit of $7FFF permits use of conventional 16-bit signed integers capable of representing positive or negative values.

The integer representation of count C is shifted left S bits until the most significant bit (MSB) of the count C is shifted into the carry position. After S shifts capture register 120 contains a high byte X' which ranges from $00 to $FF. Rounding to nine bits of accuracy, factor X equals (1+X'/256), and the count value C equals X*2.sup.N where exponent N equals 16 minus S.

The carry bit combined with high byte X' expresses the factor X to nine significant bits in a fixed point format, with the carry bit being the integer part and byte X' being the fractional part. In this format, the factor X ranges from $100 to $1FF and represents values between 1 and 2. The most significant bit of X, the bit in the carry position, is always 1 and can be ignored when using look-up table 140. The byte X' indicates the factor X and is the address signal supplied to look-up table 140. In another embodiment, the byte X' is transformed before being applied as an address signal, for example by adding or subtracting an offset or shifting to provide an even address for retrieving values Y that are word size or larger.

All inverses X.sup.-1 for 1<X<2 are greater than 0.5 but less than 1. Therefore, fixed point representations of the inverses X.sup.-1 have a bit corresponding the power 2.sup.-1 set. Accordingly, fixed point values Y stored in look-up table 140 do not need to store the bit representing 2.sup.-1. Decompressor 150 can append the bit representing 24 before producing a final inverse value. This permits eight bits in look-up table 140 to provide an inverse to nine bits of accuracy.

A bit corresponding to 2.sup.-2 in a fixed point representation of the inverse X.sup.-1 is 0 for X greater than 4/3 and 1 for X less than 4/3. Accordingly, the bit corresponding to 2.sup.-2 can be removed from values Y stored in look-up table 140, and decompressor 150 can add the removed bit when decompressing a Y value. Decompressor 150 compares the value X to 4/3 and if X is less than 4/3, sets the bit in value Y corresponding to 2.sup.-2. If X is greater than 4/3, decompressor 150 clears the bit corresponding to 2.sup.-2.

Further, for the 256 possible 9-bit X values from $100 to $1FF, there are to 9-bit accuracy 256 different inverses X.sup.I. Values X which are kept to ten bits of accuracy differ from 9-bit values X by an appended least significant bit which is either 0 or 1. 10-bit values X with an appended bit equal to 0 are referred to herein as even. 10-bit values X with an appended bit equal to 1 are referred to herein as odd. If the appended bit is 0, the values from the table provide the correct inverse to nine bits of accuracy. If the appended bit makes X is odd, the inverse to 9-bits of accuracy is either the same as the inverse of the even value X or differs only in the least significant bit from the inverse of the even value X. Accordingly, if the difference in the inverses between neighboring even and odd values X can be determined, the look-up table can provide inverses for 512 10 -bit values X using 256 different values Y one for each value X between $100 and $1FF.

Storing in a look-up table only even or only odd values of the inverse is not restricted to 9 bits of accuracy. When values X have one more bit of accuracy than the inverses X.sup.-1 have, the inverses X.sup.-1 can be determined using a look-up table with half the number of entries as there are values X. For example, to ten bits of accuracy, there are 512 different values X between 1 and 2 but the inverse X.sup.-1 to nine bits of accuracy can be determined using only 256 entries.

To use values Y for only even values X or only odd values X, some method is required for determining if the neighboring value X has the same approximate inverse or an inverse that differs by one in the least significant bit. One method for indicating whether the inverse differs is providing in each value Y a code bit to indicate whether the inverse for the neighboring value X is the same. For example, with fixed point representations of the inverse, the bit representing 2.sup.-1 is always set and would typically not be provided in the look-up table. The bit representing 2.sup.-2 is 0 for X greater than 4/3 and 1 for X less than 4/3. Accordingly, the bit representing 2.sup.-2 can be replaced with a code bit that, for example, is 1 if the inverses X.sup.-1 and (X+1).sup.-1 for neighboring even and odd values X and X+1 differ and is 0 if the neighboring even and odd values are the same to the accuracy to be provided. Decompressor 150 changes values from look-up table 140 according to the code bit then reconstructs the correct 2.sup.-2 bit by comparing the factor X to 4/3 (or comparing X' to $55).

Table 2 contains a list of 8-bit values Y corresponding to X values between $100 and $1FF.

From the 256 8-bit values Y in Table 2, 9-bit inverses for 512 10-bit factors X can be determined as described above.

Using both compression techniques described above, decompressor 150 reconstructs the inverse X.sup.-1 from the value Y provided by the look-up table and combines the inverse X.sup.-1 with the exponent N. Such decompression or conversion would typically be implemented in software executed by a microprocessor or a microcontroller. A COP888 assembly language program which implements the above described decompression is in the appendix. The instruction set for the COP888 is publicly known and described in the "1992 Embedded Controller Data Book" available from National Semiconductor, Inc.

FIG. 2 shows a flow diagram of a process for providing a signal indicating a multiplicative inverse using a look-up table and compression techniques similar to those described above. In step 205, a look-up table is provided with the 256 values Y shown in Table 2. Each 8-bit value Y indicates a 9-bit fixed point representation of a multiplicative inverse X.sup.-1 of an even factor X between 1 and 2 ($100 and $1FF). Of the eight bits Y.sub.7 -Y.sub.0 in the values Y, bits Y.sub.6 to Y.sub.0 correspond to 2.sup.-3 to 2.sup.-9 respectively in a fixed point representation of the inverse X.sup.-1. Bit Y.sub.7 indicates whether a neighboring odd factor has the same inverse as the even factor.

In step 210, an exponent N is initialized to the number of bits which a register can hold. The count C is measured and stored into the register during step 215. Steps 220, 225, and 230 implement a loop which counts the number of single bit left shifts required to shift the most significant non-zero bit of the count C in to the carry position. In step 235, the eight MSBs of the shifted count provide an address to select a value Y from the look-up table.

The value Y is then decompressed as follows. If the bit following the high byte X' of the shifted count is one, then the factor X is odd, and step 245 is executed before step 250, otherwise step 245 is skipped. In step 245, if bit Y.sub.7 is one then one is subtracted from the least significant bit of Y, but if the most significant bit Y.sub.7 is zero then Y is unchanged.

In step 250, a bit indicating 2.sup.-2 is reconstructed from the shifted count. If the high byte X' of the shifted count is greater than $55 then bit Y.sub.7 is cleared (step 260), otherwise bit Y.sub.7 is set to one (step 255). Finally, a bit corresponding to 2.sup.-1 is set providing nine bits of accuracy (step 265), and the Y value is shifted according to the exponent N (step 270).

Although the present invention has been described with reference to particular embodiments, the description is only an example. Many other embodiments are possible. In particular, even though much of preceding disclosure was directed to determination of velocity in an anti-lock braking system, the present invention is not so limited. The circuits and processes described may be used in any digital system which determines a multiplicative inverse or determines a quotient of a fixed dividend. For example, if timer 110 in FIG. 1 is replaced by a timer which measures the time between heartbeats, the circuitry and methods disclosed above can determine a heart rate. Further, the quantity inverted need not be a time. Timer 110 can be replaced, for example, by a sensor which provides a distance for a slope determination. Also, although the above embodiments employ look-up tables which provide values Y for a factor X between 1 and 2, look-up table ranges for the factor X may be between any two successive powers of two. Also, although much of the disclosure was directed to circuits and methods which determine multiplicative inverses, methods and circuits disclosed may be used to determine the quotient of a fixed dividend by a variable divisor. In view of this disclosure, other applications and variations of the present invention will be apparent to those skilled in the art.