System and Method for Approximating Nonlinear Functions

The operation of many modern electronic systems requires the repetitive calculation of nonlinear functions. For example, many systems require the comparison of multi-dimensional vectors. In these systems, measured vector quantities are compared with stored vector quantities by calculating the Euclidean distance between the vectors. Many speech recognition systems, for example, operate through comparing vector quantities in this manner.

Prior methods for comparing vector quantities determine the Euclidean distance between the vectors according to the following equation: ##EQU1## Therefore, the distance between vectors A and B is the square root of the sum of n squares where n is the dimension of the vectors A and B. If the distance between the vectors is zero, then the measured vector matches the stored vector.

In digital signal processing applications, this distance is typically calculated by modifying the equation (1) to read as follows: ##EQU2## The first two terms under the radical represent the normalized magnitudes of the two vectors A and B. If the components of the vectors A and B are 8 bits in precision, the squared components will be 16 bits in precision. Therefore, the normalized magnitudes of the vectors A and B, the sum of the squared components, will be on the order of 24 bits in precision for a 256 component vector. The distance is calculated by multiplying each component of the A vector by its corresponding component in the B vector, summing these results in an accumulator, and then subtracting two times the accumulated sum from the sum of the squares of the magnitudes of the two vectors. This operation requires repeated multiplication in a multiplier that is at least 8 bit by 8 bit. This is a slow process and, if the vectors are close enough to be considered a match, the calculated distance between the vectors will be on the order of a two or three bit number. However, to calculate this distance, the sum of the multiplications needs to be computed to the same precision as the sum of the squared components, for example 24 bits. Calculating the distance between two similar vectors requires a large multiplier with precision that is not consistent with the precision of the result. In fact, this implementation will be slow and require considerable power.

Therefore, a need has arisen for a method and system of approximating nonlinear functions which quickly calculates a close approximation of the exact function and is realizable in a small area in an integrated semiconductor device.

In accordance with the present invention, a system and method for approximating nonlinear functions are provided which substantially eliminates or reduces disadvantages and problems associated with prior systems and methods.

More specifically, the present invention provides a method and system which approximates the exact value of nonlinear functions of two variables. A first quantity for the first variable is multiplied by up to three integer powers of two to form a limited number of multiples of the first quantity. A second quantity for the second variable is multiplied by up to three integer powers of two to form a limited number of multiples of the second quantity. First and second linear functions of the first and said second quantities are generated by combining the generated multiples of the first and second quantities. First and second approximations are generated by shifting the first and second functions in shifters. The appropriate approximation for the first and second variables is outputted by the system.

An important technical advantage of the present invention inheres in the fact that it uses adders, subtracters, multiplexers, and shifters to approximate nonlinear functions. The use of these small and fast circuit components increases the speed and reduces the expense in terms of semiconductor area with which nonlinear functions can be calculated. Additionally, the use of small, three or four bit adders and subtracters provides enough precision in the approximation for many modern electronic systems.

For a more complete understanding of the present invention and the advantages thereof, reference is now made to the following description taken in conjunction with the accompanying drawings in which like reference numbers indicate like features and wherein:

FIG. 1 illustrates a block diagram of a first system for approximating a function according to the teachings of the present invention;

FIG. 2 illustrates a block diagram of a second system for approximating a function according to the teachings of the present invention;

FIG. 3 is a graphical representation of an approximation used by the second system according to the teachings of the present invention;

FIG. 4 illustrates a block diagram of a first system for approximating the Euclidean distance between vectors constructed according to the teachings of the present invention;

FIG. 5 is a graphical representation of the approximation used in the first system for approximating the Euclidean distance according to the teachings of the present invention;

FIG. 6 illustrates a block diagram of a second system for approximating the Euclidean distance between vectors constructed according to the teachings of the present invention;

FIG. 7 is a graphical representation of the approximation used in the second system for approximating the Euclidean distance according to the teachings of the present invention;

FIG. 8 illustrates a block diagram of a third system for approximating the Euclidean distance between vectors constructed according to the teachings of the present invention;

FIG. 9 is a graphical representation of the approximation used in the third system for approximating the Euclidean distance according to the teachings of the present invention; and

FIG. 10 illustrates a block diagram of a fourth system for approximating the Euclidean distance between vectors constructed according to the teachings of the present invention.

FIG. 1 illustrates a system indicated generally at 10 constructed according to the teachings of the present invention for approximating a nonlinear function. System 10 comprises a first multiple generating circuit 12 and a second multiple generating circuit 14. First multiple generating circuit 12 is coupled to receive an input m. First multiple generating circuit 12 generates a limited number of integer powers of two times m. Second multiple generating circuit 14 forms a limited number of integer powers of two times n. A first function generating circuit 16 is coupled to an output of first and second multiple generating circuits 12 and 14. First function generating circuit 16 generates a predetermined function of m and n. A second function generating circuit 18 is coupled to the output of first and second multiple generating circuits 5, 12 and 14. Second function generating circuit 18 generates a predetermined function of m and m. A first approximation generating circuit 20 is coupled to an output of first function generating circuit 16. A second approximation generating circuit 22 is coupled to an output of second function generating circuit 18. An approximation selecting circuit 24 is coupled to an output of first approximation generating circuit 20 and an output of second approximation generating circuit 22.

In operation, the system 10 approximates a nonlinear function according to a piecewise linear approximation. First multiple generator circuit 12 may comprise, for example, a combination of shifters coupled to generate a limited number of multiples of m. The output of first multiple generator circuit 12 may comprise, for example, m, 2 m and 4 m. Second multiple generator circuit 14 may comprise, for example, a second combination of shifters coupled to generate a limited number of multiples of n. The output of second multiple generator circuit 14 may comprise, for example, n, 2 n, and 4 n.

First function generating circuit 16 may comprise, for example, a combination of adders and subtracters for generating a first function from the multiples of m and n generated in first and second multiple generating circuits 12 and 14. The output of first function generating circuit 16 may comprise, for example, 8 m+n. Second function generating circuit 18 may comprise, for example, a second combination of adders and subtracters for generating a second function from the multiples of m and n generated in first and second multiple generating circuits 12 and 14. The output of second function generator circuit 18 may comprise, for example, 8 m+4 n-m.

First approximation generating circuit 20 may comprise, for example, a shifter for shifting the output of first function generating circuit 16 by 3 bits to the right so as to divide the output of first function generating circuit 16 by 8. The output of first approximation generating circuit 20 may comprise, for example, m+n/8. Second approximation generating circuit 22 may comprise, for example, a shifter for shifting the output of second function generating circuit 18 by 3 bits to the right so as to divide the output of second function generating circuit 18 by 8. The output of second approximation generating circuit 22 may comprise, for example, m+n/2-m/8.

Approximation selecting circuit 24 may comprise, for example, a multiplexer and a multiplexer control circuit. The output of the approximation selecting circuit 24 may comprise, for example, the larger of the outputs of first approximation generating circuit 20 and second approximation generating circuit 22. Alternatively, the output of approximation selecting circuit 24 may comprise the output of first approximation generating circuit 20 if the ratio of n to m is less than a predetermined breakpoint and the output of second approximation generating circuit 22 if the ratio of n to m is greater than the predetermined breakpoint.

FIG. 2 illustrates a circuit indicated generally at 30 constructed according to the teachings of the present invention for approximating a nonlinear function. Circuit 30 comprises first and second multiple generating circuits 32 and 34. First multiple generating circuit 32 is coupled to receive a quantity m. Second multiple generating circuit 34 is coupled to receive a quantity n. First, second, and third function generating circuits 36, 38, and 40 are coupled to an output of first multiple generating circuit 32 and an output of second multiple generating circuit 34. First approximation generating circuit 42 is coupled to first function generating circuit 36. Second approximation generating circuit 44 is coupled to second function generating circuit 38. Third approximation generating circuit 46 is coupled to third function generating circuit 40. Approximation selection circuit 48 is coupled to first, second, and third approximation generating circuits 42, 44, and 46.

In operation, first multiple generating circuit 32 may comprise, for example, a limited number of shifters. The shifters of first multiple generating circuit 32 multiply the quantity m by various integer powers of 2. Second multiple generating circuit 34 may comprise, for example, a limited number of shifters. The shifters of second multiple generating circuit 34 multiply the quantity n by various integer powers of 2.

First function generating circuit 36 may comprise, for example, a combination of adders and subtracters for generating a first function from the multiples of m and n generated in first and second multiple generating circuits 32 and 34. The output of first function generating circuit 36 may comprise, for example, the function 8 m+4 n-m. Second function generating circuit 38 may comprise, for example, a combination of adders and subtracters for generating a second function from the multiples of m and n generated in first and second multiple generating circuits 32 and 34. The output of second function generating circuit 38 may comprise, for example, the function 8 m+n-m. Third function generating circuit 40 may comprise, for example, a combination of subtracters and adders for generating a third function from the multiples of m and n generated in first and second multiple generating circuits 32 and 34. The output of third function generating circuit 40 may comprise, for example, the function 32 m+20 n-7 m.

First approximation generating circuit 42 may comprise, for example, a shifter for shifting the output of first function generator 36 by 3 bits to the right so as to divide the output of first function generating circuit 36 by 8. Second approximation generating circuit 44 may comprise, for example, a shifter for shifting the output of second function generating circuit 38 by 3 bits to the right, so as to divide the output of second function generating circuit 38 by 8. Third approximation generating circuit 46 may comprise, for example, a shifter for shifting the output of third function generating circuit 40 by 5 bits to the right so as to divide the output of third function generating circuit 40 by 32.

Approximation selecting circuit 48 may comprise, for example, a multiplexer and a multiplexer control circuit. Approximation selecting circuit 48 outputs the appropriate approximation for the input m and n. In one embodiment, approximation selection circuit 48 outputs the larger of the outputs of first, second, and third approximation generating circuits 42, 44, and 46. Alternatively, approximation selecting circuit 48 outputs the appropriate approximation based on a comparison of the ratio of the inputs, n and m, with first and second predetermined breakpoints. If the ratio of n to m is less than the first predetermined breakpoint, approximation selecting circuit 48 outputs the output of the first approximation generating circuit 42. If the ratio of n to m is greater than the first predetermined breakpoint and less than the second predetermined breakpoint, approximation selecting circuit 48 outputs the output of second approximation generating circuit 44. If the ratio of n to m is greater than the second predetermined breakpoint, approximation selecting circuit 48 outputs the output of third approximation generating circuit 46. A third embodiment of approximation selecting circuit 48 is best understood by reference to FIG. 3.

FIG. 3 is a graphical representation of an approximation that may be used in the second system for approximating a nonlinear function according to the teachings of the present invention. In FIG. 3, a nonlinear function 50 having three regions namely, region A, region B, and region C is illustrated. The X component of FIG. 3 represents the ratio of n/m. The Y component of FIG. 3 represents the value of the nonlinear function 50 and the corresponding value for X. First approximation component 52 corresponds to the output of first approximation generator circuit 42. Second approximation component 54 corresponds to the output of second approximation generating circuit 44. Third approximation component 56 corresponds to the output of third approximation generating circuit 46. In this embodiment, approximation selection circuit 48 outputs first approximation component 52 if the ratio of n/m falls within the region A. Approximation selection circuit 48 outputs the second approximation component 54 if the ratio of n/m falls within region B. Approximation selection circuit 48 outputs the third approximation component 56 if the ratio of n/m falls within region C.

FIG. 4 illustrates a circuit indicated generally at 60 constructed according to the teachings of the present invention for approximating the Euclidean distance between two vectors, A and B. Circuit 60 comprises a memory circuit 62 that receives and stores the individual components that make up the vectors A and B. A preprocessor circuit 64 reads the corresponding components of the vectors A and B, calculates the difference between the corresponding components, and stores these difference values in memory 62. Routing logic 66 is coupled to memory 62 to read two of the stored difference values the first pass through the circuit 60 and one stored difference value in subsequent passes.

The two outputs of the routing logic 66, x and y, are coupled to subtracter 68 and to first and second multiplexers 70 and 72. The carry bit of subtracter 68 is also connected to multiplexers 70 and 72 which, in combination with subtracter 68, sort the outputs of routing logic 66 such that the output of multiplexer 72, m, is the maximum value of x and y, and the output of multiplexer 70, n, is the minimum value of x and y.

A function of the maximum value, m, and the minimum value, n, is compared with a predetermined breakpoint. The function may comprise a ratio. In one embodiment, the output m of multiplexer 72 is coupled to shifter 74 which shifts the quantity m two bits to the right, effectively dividing m by four. The output of shifter 74, m/4, and the output of multiplexer 70, n, are coupled to subtracter 76 which effectively compares the ratio of n/m with 1/4 without actually dividing n by m using a novel technique detailed below.

The output of multiplexer 70, n, is coupled to a shifter 78 wherein the quantity n is shifted three bits to the right to be used in calculating the first of two approximations of the Euclidean distance. The output of shifter 78 and output of multiplexer 72, m, are coupled to adder 80. The output of adder 80 is the first approximation of the Euclidean distance comprising a function of m and n.

The output of subtracter 76 is also used in calculating the second of two approximations of the Euclidean distance by shifting it one bit to the right in shifter 82. The output of shifter 82 and output, m, of multiplexer 72 are coupled to adder 84 piece. The output of adder 84 is the second approximation of the Euclidean distance comprising a function of n and m.

The outputs of adders 84 and 80, the two approximations of the Euclidean distance calculated in this pass through the circuit 60, are coupled to multiplexer 86. The carry bit of subtracter 76 is coupled to control multiplexer 86 to output the appropriate of the two approximations of the Euclidean distance based on whether the ratio of n/m is greater than 1/4. The output of multiplexer 86 is added to the accumulator 88 and this value is fed back as an additional input to routing logic 66.

On subsequent passes through the circuit 60, the routing logic 66 will pass the current value of accumulator 88 and a difference value stored in memory circuit 62 as the values x and y. Once all of the difference values stored in memory circuit 62 have passed through routing logic 66, the approximation of the Euclidean distance between vectors A and B generated by the system of the present invention will be stored in accumulator 88.

In operation, circuit 60 calculates a piecewise linear approximation of equation (1) above. For simplicity, the distance formula may be represented as follows: ##EQU3## where a, b, c, and d are the differences between corresponding vector quantities. By substituting into equation (3) the quantity q equal to the square root of a.sup.2 +b.sup.2 the distance equation becomes: ##EQU4## A similar substitution into equation (4) of the quantity r equal to the square root of q.sup.2 +c.sup.2 modifies the distance equation (4) to become: ##EQU5## If similar substitutions are repeatedly made in the distance equation (5), the distance equation will ultimately be reduced to the form of: ##EQU6## in which y is one of the differences between corresponding components of the two vectors and x is the square root of the sum of the squares of all the other differences between corresponding components. Because each of the substitutions detailed above and the ultimate equation (6) are in the form of the square root of the sum of two squares, a first order approximation of the square root of the sum of two squares used iteratively will yield a close approximation to the exact distance between the vectors. The truth of this statement may be demonstrated by using 3-dimensional vectors. In three dimensions, the distance equation is: ##EQU7## wherein the quantities x, y, and z represent the difference between the corresponding vector components. This equation may be written in the form: ##EQU8## and if p.sup.2 equals x.sup.2 +y.sup.2 then: ##EQU9## Because the quantities x and y are known, the value P may be approximated using an approximation for the square root of the sum of two squares which is a function of the two squared quantities, x and y. Once a value for P is determined, the quantities P and z are known. Using the same approximation for the square root of the sum of two squares as a function of the two squared quantities, now P and z, the distance D of equation (9) may be determined. This iterative technique for approximating the Euclidean distance between vectors is equally applicable to vectors of any dimension.

As discussed above, the Euclidean distance D of equation (3) is iteratively calculated by approximating an equation of the form: ##EQU10## this equation can be rewritten in the form: ##EQU11## if x is the larger of the two quantities x and y, then the number under the radical will be equal to 1 plus a number which is less than 1. Therefore, the product P will be equal to x times a number between 1 and the square root of 2 depending on the ratio of y to x.

FIG. 5 graphically represents the approximation used in the first system for approximating Euclidean distance according to the present invention. In FIG. 5, the quantities n and m have been substituted for y and x respectively. Curve 90 represents the equation: ##EQU12## which is the exact calculation of the normalized square root of the sum of two squares. Curve 92 represents one approximation used in the teachings of the present invention. For values of n/m between zero and the predetermined breakpoint 94, which according to one embodiment comprises one-quarter, the approximation curve 92 follows a first approximation component 96. First approximation component 96 according to one embodiment comprises a function of m and n according to the following equation: ##EQU13## It should be noted that first approximation component 96 may comprise a constant.

For values of n/m greater than the predetermined breakpoint 94, the approximation curve 92 follows the second approximation component 98 according to the following equation: ##EQU14##

The circuit 60 of FIG. 4 produces the approximation curve 92 of FIG. 5 by first sorting the outputs, x and y, received from routing logic 66. Subtracter 68 calculates the difference between the outputs x and y of routing logic 66 and produces a carry bit. Based on this carry bit produced by subtracter 68, multiplexer 22 outputs the maximum value, m, of the values x and y, while the multiplexer 70 outputs the minimum value, n, of the values x and y. Once the values n and m are obtained, the ratio of n/m is compared with the predetermined breakpoint 94 of FIG. 5 using shifter 74 and subtracter 76. In subtracter 76, the quantity m/4 is subtracted from the quantity n and a carry bit is produced. This process is represented by the equation:

If D is greater than zero, equation (15) may be rewritten as:

whereas if D is less than zero, equation (15) may be rewritten as:

The carry bit of subtracter 76, therefore, will determine how the ratio of n/m compares with 1/4, without actually dividing n by m, and will determine which approximation component of curve 92 of FIG. 5 will be used to approximate curve 90 during this pass through the circuit 60.

The circuit 60 of FIG. 4 calculates the first approximation component 96 by shifting the quantity n three bits to the right in shifter 78, effectively dividing n by eight, and adding the quantity m to that shifted quantity in adder 80. Meanwhile, the circuit 60 calculates the second approximation component 98 by shifting the output of subtracter 76 one bit to the right in shifter 82 and adding the quantity m to the output of shifter 82 in adder 84. Based on the carry bit of subtracter 76, the multiplexer 86 will either output the output of adder 80 or the output of adder 84 to accumulator 88 depending on how the ratio of n/m compares with the predetermined breakpoint 94.

FIG. 6 illustrates a second system for approximating Euclidean distance between vectors indicated generally at 100 and constructed according to the teachings of the present invention. Circuit 100 is an alternative embodiment of circuit 60 of FIG. 4. Circuit 100 comprises all of the components of circuit 60 and three additional components for calculating an alternative breakpoint. In this embodiment, the breakpoint comprises one-third. The output n of multiplexer 70 is coupled to a shifter 102 which shifts the quantity n by 1 bit to the left, effectively multiplying n by 2. The output n of multiplexer 70 is also coupled to an input of an adder 104. The output of shifter 102 is also coupled to an input of adder 104. The output of adder 104, 3 n, and the output of multiplexer 72, m, are coupled to a subtracter 106 which effectively compares the ratio of n/m with one-third without actually dividing n by m in a similar manner as described with respect to FIGS. 4 and 5. In this embodiment, the carry bit of subtracter 106 is coupled to control multiplexer 86. Unlike the embodiment of FIG. 4, the carry bit of subtracter 76 is not coupled to control the multiplexer 86.

FIG. 7 graphically represents the approximation used in the second system for approximating Euclidean distance according to the present invention. As with FIG. 5, curve 90 represents the exact calculation of the normalized square root of the sum of two squares. Curve 108 represents one approximation used in the teaching of the present invention. For values of n/m between zero and the predetermined breakpoint 110 which according to this embodiment comprises 1/3, the approximation curve 108 follows the first approximation component 96. For values of n/m greater than the predetermined breakpoint 110, the approximation curve 108 follows the second approximation component 98.

The circuit of FIG. 6 produces the approximation curve 108 of FIG. 7 in the same manner as the circuit of FIG. 4 with the exception of the calculation of the breakpoint 110. Once the values n and m are obtained in multiplexer 72 and multiplexer 70, the ratio of n/m is compared with the predetermined breakpoint 110 of FIG. 7 using shifter 102, adder 104, and subtracter 106. In subtracter 106, the quantity m is subtracted from the quantity 3 n and a carry bit is produced. This process is represented by the equation:

if D is greater than zero, equation (18) may be rewritten as

whereas if D is less than zero equation (18) may be rewritten as

The carry bit of subtracter 106, therefore, will determine how the ration of n/m compares with 1/3, without actually dividing n by m, and will determine which approximation component of curve 108 of FIG. 7 will be used to approximate curve 90 during this pass through the circuit 100.

FIG. 8 illustrates a third system for approximating the Euclidean distance between vectors indicated generally at 120 and constructed according to the teachings of the present invention. Circuit 120 is an alternative embodiment of circuit 100 comprising three approximations of the Euclidean distance and two breakpoints. Circuit 120 is substantially identical to circuit 100 with the addition of 10 components for calculating the third approximation and the second breakpoint.

In this embodiment, the second breakpoint comprises 3/4. The output m of multiplexer 72 is coupled to a shifter 122 wherein the quantity m is shifted one bit to the left so as to multiply the quantity m by two. The output of shifter 122 and the output m of multiplexer 72 are coupled to an adder 124. The output n of multiplexer 70 is coupled to a shifter 126 wherein the quantity n is shifted two bits to the left so as to multiply the quantity n by four. The output of adder 124, 3 m, is subtracted from the output of shifter 126, 4 n, in subtracter 128 which effectively compares the ratio of n/m with 3/4 without actually dividing n by m using the novel technique detailed above. The carry bit of subtracter 128 is coupled to multiplexer 86.

In this embodiment, a third approximation of the Euclidean distance is calculated. The output of n of multiplexer 70 is coupled to shifter 130 wherein the quantity n is shifted 4 bits to the left so as to multiply the quantity n by 16. The output of shifter 130 and shifter 126 are added in an adder 132. The output m of multiplexer 72 is subtracted from the output of shifter 78 in subtracter 134. The output of subtracter 134 is subtracted from the output of adder 132 in subtracter 136. The output of subtracter 136, 20 n-7 m, is coupled to a shifter 138 wherein the quantity 20 n-7 m is shifted 5 bits to the right so as to divide the quantity 20 n-7 m by 32. The output of multiplexer 72 and the output of shifter 138 are coupled to an adder 140. The output of adder 140 is coupled to an input of multiplexer 86. The output of adder 140 comprises the third approximation of the Euclidean distance.

FIG. 9 graphically represents the approximation used in the third system for approximating Euclidean distance according to the teachings of the present invention. Curve 142 represents one approximation used in the teachings of the present invention. For values of n/m between zero and the first predetermined breakpoint 110, which according to this embodiment comprises 1/3, the approximation curve 142 follows a first approximation component 96. For values of n/m greater than the first predetermined breakpoint 110 and less than the second predetermined breakpoint 144, the approximation curve 142 follows the second approximation component 98. For values of n/m greater than the second predetermined breakpoint 144, the approximation curve 142 follows the third approximation component 146 according to the following equation: ##EQU15##

The circuit 120 of FIG. 8 produces the approximation curve 142 of FIG. 9 in the same manner as the circuit 100 of FIG. 6 with the addition of calculating the second predetermined breakpoint 144 and the third approximation component 146.

Once the values of n and m are obtained, the ratio of n/m is compared with the second predetermined breakpoint 144 of FIG. 9 using shifter 122, adder 124, shifter 126, and subtracter 128. In subtracter 128, the quantity 3 m is subtracted from the quantity 4 n and a carry bit is produced. This process is represented by the equation:

If D>O , the equation (22) may be rewritten as:

whereas if D<0, equation (22) may be rewritten as:

The carry bit of subtracter 128, therefore, will determine how the ratio of n/m compares with 3/4 without actually dividing n by m, and, in combination with the carry bit of subtracter 106, will determine which approximation component of curve 142 of FIG. 9 will be used to approximate curve 90 during this pass through the circuit 120.

The circuit 120 of FIG. 8 calculates the third approximation component 146 in adder 140 by adding the output m of multiplexer 72 to the output, ##EQU16## of shifter 138.

FIG. 10 illustrates a circuit indicated generally at 150 constructed according to the teachings of the present invention for approximating the Euclidean distance between two vectors, A and B. The circuit 150 comprises a memory circuit 152 which receives and stores the individual components that make up the vectors A and B. Preprocessor circuit 154 reads the corresponding components of vectors A and B, calculates the difference between the corresponding components of the vectors, and stores these difference values in memory 152. Routing logic 156 is coupled to memory 152 to read two of the stored difference values the first pass through the circuit 150 and one stored difference value on subsequent passes. The two outputs of the routing logic 156, x and y, are coupled to subtracter 158 and to first and second multiplexers 160 and 162. The carry bit of subtracter 158 is also connected to the multiplexers 160 and 162, which in combination with subtracter 158, sort the outputs, x and y, of routing logic 156 such that the output of multiplexer 160, n, is the minimum value of x and y, and the output of multiplexer 162, m, is the maximum value of x and y.

A function of the outputs, x and y, of routing logic 156 is compared with a predetermined breakpoint. The function may be a ratio. In one embodiment, output x of routing logic 156 is coupled to shifter 164 and subtracter 166. Output y of routing logic 156 is coupled to shifter 168 and subtracter 170. The remaining input of subtracter 170, is coupled to the output of shifter 164. The remaining input of subtracter 166 is coupled to the output of shifter 168. Subtracters 166 and 170 effectively compare the ratios of x/y and y/x with 1/4 using the same novel technique detailed above.

The output of multiplexer 160, n, is coupled to shifter 172 wherein the quantity n is shifted three bits to the right to be used in the first of two approximations of the Euclidean distance. The output of shifter 172 and the output, m, of multiplexer 162 are coupled to adder 174. The output of adder 174 is the first approximation of the Euclidean distance comprising a function of n and m.

The output of subtracters 166 and 170 are also used in calculating alternative second approximations of the Euclidean distance by shifting the outputs of subtracters 166 and 170 one bit to the right in shifters 176 and 178 respectively. The output of shifter 178 and the output, m, of multiplexer 162 are coupled to adder 180 wherein a first alternative second approximation of the Euclidean distance as a function of n and m is calculated. The output of shifter 176 and the output, m, of multiplexer 162 are coupled to adder 182 wherein a second alternative second approximation of the Euclidean distance as a function of n and m is calculated.

The outputs of adders 174, 180, and 182 are coupled to multiplexer 184 that outputs the appropriate approximation of the Euclidean distance depending on the carry bits generated by subtracters 158, 166 and 170 which are coupled to multiplexer 184. The output of multiplexer 184 is added to the current value of accumulator 186 and the output of the accumulator 186 is fed back as an additional input to the routing logic 156. On subsequent passes through circuit 150, the routing logic 156 will pass the current value of the accumulator 186 and a difference value stored in memory 152 as the values x and y. Once all of the difference values stored in memory 152 have passed through the routing logic 156, the approximation of the Euclidean distance between vectors A and B generated by the system of the present invention is stored in accumulator 186.

In operation, circuit 150 calculates a first order approximation of equation (1) in much the same manner as circuit 60 of FIG. 4. The only difference between the operation of circuit 60 and circuit 150 inheres in the comparison of the ratio of the maximum value, m, to the minimum value, n, with a predetermined breakpoint 94. In circuit 60, this comparison is carried out in subtracter 76 and shifter 74 after the values x and y received from routing logic 76 are sorted in multiplexers 70 and 72. In circuit 120, this comparison is accomplished prior to sorting the values x and y of routing logic 156. Alternative comparisons are made using subtracter 170 In combination with shifter 164 and subtracter 166 in combination with shifter 168. Multiplexer 184 is controlled by carry bits from subtracters 158, 166, and 170 to output the appropriate approximation of the Euclidean distance.

Although the present invention has been described in detail, it should be understood that various changes, substitutions, and alterations can be made hereto without departing from the spirit and scope of the invention as defined by the appended claims.