US 4,031,370 AGrant
Generation of Mathematical Functions
Issue Date:1977-06-21
•29 Claims
•7 Drawing Sheets
Abstract
A method of interpolating a value of the dependent variable, y corresponding to a given value of an independent variable x, wherein y = f(x) and is described by a linear polynomial series of the 8'th order. The method uses a 4'th order polynomial interpolation method to obtain up to an 8'th order interpolation in 2 iterations of the 4'th order method. The method is suitable for implementation by a computer or by purpose-designed data processing apparatus. An embodiment of apparatus suitable for use in performing the method is also disclosed.
Metadata
Assignee
- Bell & Howell Limited
Inventor
- Reginald Catherall
Application Information
Application Number:US 6583490
Filing Date:1976-02-17
Priority Date:1975-02-26
Art Unit:236
Classifications
IPC:
G06F 738G06F 102
Field of Search:
235152;197
Patent Drawings (7 sheets)
Description
Background of the Invention
This invention relates to the generation of values of mathematical functions using iterative interpolation methods.
Discussion of the Prior Art
Many data processing situations arise in which it is required to have available the value of a function y = f (x) at any value of x within a given range. One way of meeting the requirement in data processing systems is to store in a memory values of the dependent variable y for given values of the independent variable, x and then to interrogate the memory to obtain the value of y for a given value of x. A disadvantage of such an arrangement is that it is possible to store only discrete values of x and if it is necessary to store a large number of such values the cost of the memory can be high.
In the specification of our co-pending British Pat. application No. 8045/75 of even date there is disclosed, inter alia, a method of interpolating a value of the dependent variable y for a given value of the independent variable, x of the function y = f (x), and apparatus for performing the method. The function y = f (x) is a linear polynominal in x. The method involves an iterative interpolation technique which can be regarded as interpolation by repeated bisection of a segment of the operative range of the independent variable x whereby an initial segment joining two point values of the function at the extremities of the range are bisected to form two new segments. One of the two new segments includes the given value of x for which the value of the dependent variable, y is required, and this is the new segment of interest. The new segment of interest can then be bisected in the same way, and so on such that the length of each segment is progressively halved and converges on the given value of x. In one aspect the method comprises the steps of linearly interpolating between the two point values which define a segment of interest to obtain a mid-point value and correcting the mid-point value by the addition of a correcting value or "residual need." The corrected mid-point value is then substituted for one of the two previous point values to define a new segment of interest and the step of interpolating and correcting the new mid-point value with a new correcting value is re-iterated until the value of y is obtained for the given value of x. The correcting values may be derived from the second order term of a polynomial series or a combination of the second order term with a progressively higher order term or terms of the series. The series used in the method is called a binary polynomial series.
Another method of and apparatus for interpolating the value of the dependent variable, y for a given value x of a function y = f (x) is disclosed in the specification of an earlier British Pat. No. 1,363,073 (U.S. Pat. No. 3,789,203) which describes the binary polynomials in some detail.
The methods disclosed in the aformentioned specifications are suitable for implementation on a suitably programmed aforementioned or by means of other apparatus (hardware) designed for the purpose.
The binary polynomial interpolation method has the property that it can provide interpolated values of y at the end points of the initial segment of interest and at a binary sequence of x values. The length of the sequence for which exact values of y are obtained is dependent upon the order of the polynomial interpolated, for example for a fourth order polynomial method interpolated over a normalised x range of values from 0 to 1 the value of y so obtained will be an exact fit at x values of 0, 1/4, 1/2, 3/4, and 1. Similarly for an eighth order polynomial method the interpolated value of y will be an exact fit at x values of 0, 1/8, 1/4, 3/8, 1/2, 5/8, 3/4, 7/8, and 1. Generally in the aforementioned methods it is found that the number of points of exact fit in the sequence is one more than the order of the polynomial interpolated. It will be understood that, in general, the accuracy of interpolation can be increased by increasing the order of the polynomial, but this is accompanied by a concommitant increase in complexity of such implementation.
When polynomial approximation is needed for a plurality of functions, it may be found that a given polynomial order will meet most of the requirements, but a small number of the functions will require a higher order approximation.
One way of dealing with this would be to implement the interpolation at the highest order necessary to meet the requirement of the most difficult function but the added complexity and cost may not be justified. Another way would be to use a technique known as "piecewise approximation" in which the range is sub-divided into a number of zones but this approach results in a significant increase of stored data when precision interpolation is required for a difficult function.
It is an object of the invention to provide a method of interpolating a value of a dependent variable, y which is a function of an independent variable, x in which hardware or software organised to provide nth order interpolation can be used to provide up to a 2nth order interpolation by double operation.
Summary of the Invention
According to the invention there is provided a method of interpolating a value of the dependent variable y corresponding to a given value of an independent variable x, wherein y is a function of x and is described by a linear polynomial series of the 2nth order and the terms of the series containing the (n+1)th to the 2nth polynomials are in the form of an expression which is a product of a common nth order polynomial of x, and the sum of the nth to the zero'th order polynomials respectively, each multiplied by its appropriate coefficient, using an nth order polynomial interpolation method to obtain up to a 2nth order approximation in 2 iterations of the nth order interpolation method, comprising the steps of determining the coefficients and using them to perform an nth order interpolation to obtain a specific coefficient for the common nth order polynomial at the given value of the independent variable x, modifying, as required the coefficients relevant to the nth and lower order polynomials to consolidate the term which comprises the common nth order polynomial multiplied by its specific coefficient and performing a second nth order interpolation using the modified coefficients at the given value of the independent variable x whereby the result of the second interpolation is the value of the dependent variable, y for the given value of the independent variable which would have been obtained by using a higher order interpolation method up to the 2nth order,
The method according to the invention may be implemented by programming a computer automatically to calculate the value of the required variable, or by means of data-processing apparatus designed for the purpose.
The invention also comprises a computer or data-processing apparatus when conditioned to carry-out the method.
The invention further comprises a method according to the invention in the form of a program stored in physical form such as on a programmed Read Only Memory.
Description of the Drawings
The invention will now be described by way of example with reference to the accompanying drawings, in which:
FIGS. 1 to 7 show graphs of polynomial expressions from the zero'th to the eighth order;
FIG. 8 shows a graph of a common factor fourth order polynomial expression useful in describing the invention;
FIG. 9 shows graphs of y = sin x and y = x over an x range 0.degree. to 90.degree. normalised to a range 0 to 1, a plot of the differences between the values y = sin x and y = x and a graph of a parabola of the form shown in FIG. 3 multiplied by a coefficient whereby its magnitude is equal to that of the differences curve at x = 1/2;
FIG. 10 shows a plot of the differences between the curve y = sin x and the curve of an expression y = 1/2(b+ a) + 1/2(b-a).sup.. 2(x-1/2) + K4x(1-x), that is a second order polynomial, together with a curve of the form shown in FIG. 4 multiplied by a coefficient whereby the difference between the two curves is reduced at values of x = 1/4 and x = 3/4 to values identical in amplitude and sign; and
FIG. 11 is a simplified block circuit diagram of an apparatus for implementing a method according to the invention disclosed in our aforementioned patent application No. 8045/75.
The derivation of the binary polynomials and methods of and apparatus for implementing the polynomials are developed in some detail in the aforementioned patent specifications. However a brief explanation of them may be useful for a better understanding of the method of the present invention.
When a polynomial approximation is used to interpolate values of y as a function of x it is common practice first to normalise the problem to a convenient x range, such as -1 to +1 or 0 to 1. In the following explanation it will be assumed that the x range is normalised to 0 to 1 and that the algorithms will be performed using a 2's complement binary code but it is emphasised that this is not a limitation of the method.
As aforementioned the iterative interpolation method using a binary polynomial series arrives at the required x value for which the value of y is to be obtained by repeated bisection of the x range, that is y is interpolated in a series of stages which establish a binary series of x values such that:
at the first stage (n=1) y is obtained at x/2
at the second stage (n=2) y is obtained at the odd quarter value of x in the segment containing the required x value.
at the third stage (n= 3) y is obtained at the odd eighth value of x in the segment containing the required x value.
Also as aforementioned the binary polynomial iterative interpolation method has the property that it provides interpolated values of y for a binary sequence of x values.
A fourth order binary polynomial series of the form:
where d.sub.n is the nth order coefficient and B.sub.n is a linear polynomial of x of the nth order will now be derived by way of example, using a well known function y = sin x over a range 0.degree. to 90.degree. normalised to an x range 0 to 1. Its extension to an eighth order polynomial series will then be stated in order to describe a specific method according to the invention.
Referring to FIG. 9, there is shown a curve 10 of the function y = sin x over an x range 0.degree. to 90.degree. normalised to an x range 0 to 1, and in the usual way the value of y at any given value x in the range will be depicted as y.sub.(n) = sin x.sub.(n) i.e. y.sub.(0) = sin 0 = 0; y.sub.(1/2) = sin .sub.(1/2) = sin 45 = 0.70711.. etc.
Two specific end point values, a, b, have been designated on the curve. Point a is the value of y.sub.(0) at the origin, that is the value of the x intercept and the point b is the value of y.sub.(1). The equation of a line drawn between points a and b may be expressed in the form y = 1/2(a+b) + 1/2(b-a).sup.. 2(x-1/2) = a + (b-a)x. A solution of this expression will only supply values y = x, i.e., a straight line 12. Linear interpolation between these two point values would give a value of y at x = 1/2 of
For a second interpolation two options are available and that is to step UP or DOWN, i.e. to interpolate
and the decision to interpolate y.sub.(1/4) or y.sub. (3/4) would be determined by the given x value for which the value of y is required.
It will be obvious that linear interpolation between two end points will provide answers in agreement with the polynomial expression y = mx + b (the equation for a straight line) but would be quite inadequate in the case of a nonlinear function such as y = sin x.
In FIG. 9, a curve 14 is a plot of the differences between the curves 10 and 12 and may be regarded as a residual need curve; that is, at any given value of y = f(x) it is the value (or residual need) which has to be added to the value obtained by linear interpolation of y = f(x) between two point values which bracket the given value of x. It will be seen that it approximates to a parabola which is a second order polynomial of the form B.sub.1 = K4x (1-x) where K is a coefficient and the second order polynomial x(1-x) is multiplied by a scaling factor 4 which gives a value of unity for the expression when x = 1/2.
Thus, a term describing a parabola multiplied by a coefficient K, when added to the linear terms described above would make the total expression a closer approximation to the desired sine function.
If the difference between the two values at x = 1/2 is called K; then K4x.(1-x) must equal the difference between y = sin x and y = x at x = 1/2, i.e. (0.70711 - 0.5) = 0.20711. K can be termed the residual need at x = 1/2. Thus for the polynomial expression to provide the correct value of y for sin x when x = 1/2, the quadratic term must supply a value equal to K and the polynomial series may be written.
y = 1/2(b+a) + 1/2(b-a).sup.. 2(x-1/2) + K.sup.. 4x(1-x) and it will be seen by inspection that for the function y = sin x, y will be correct at x values of 0, 1 and 1/2. For a second interpolation at x = 1/4 or 3/4, interpolation will give
It is therefore possible to state this as an algorithm of the form
where n is the stage in the algorithm, so that at the n'th stage:
Interpolation of a polynomial expression of the form
thus gives a much better approximation for the function y = sin x than linear interpolation between two end points but it will be noted that three values are required namely the values of y at x = 0 and 1, and the value of K to perform the interpolation and in general (n+a) quantities are required to perform an n'th order interpolation.
Continuing, it was mentioned that the curve 14 was not a true parabola. FIG. 3 shows a parabola of the form y = 4x(1-x) and curve 16 of FIG. 9 shows a parabola of the form K4x (1-x) where K=0.20711 . . . . The difference between the two curves 14 and 16 is shown at curve 18 in FIG. 10 and it will be seen that it is similar to that of a cubic (third order) curve. This difference curve 18 represents the error between the sine function and the above polynomial expression including the quadratic term. The reduced scale values for the ordinate y, will indicate the relative magnitudes in the errors depicted by curves 14 and 18.
Thus the addition of a cubic term to the polynomial expression will further considerably reduce the magnitude of this difference. Curve 18 is not symmetrical about the x axis and therefore to reduce the error the cubic, third order term should take the form ##EQU1## shown at FIG. 4. In this term 64/3 is the scaling coefficient, the expression x(1-x) is similar to the parabolic, second order term, and the factor (x-1/2) is used to ensure that the term makes zero contribution at x = 1/2, while the negative sign causes the necessary polarity inversion. The polynomial expression may now be written as ##EQU2## where the value of coefficient C is selected to reduce the difference between the curves 18 and 20 at x = 1/4 and x = 3/4, to values identical in amplitude and sign.
The difference between the true sine function and a function derived by interpolating the polynomial expression including the third order polynomial is shown as curve 22 in FIG. 10 and it will be noted that this is similar to that of a quartic (fourth order) curve (such as shown in FIG. 5), in which the errors are zero at x = 0, 1/2 and 1 and now considerably reduced, but not zero, at x = 1/4 and x = 3/4.
A fundamental rule of the binary polynomial series is that as each point of exact fit is established all subsequent polynomials must preserve this fit. That is, by employing the binary polynomial approximation including the second order term, an exact fit can be established for x = 0, x = 1/2 and x = 1. The third order polynomial B.sub.3 and all subsequent polynomials must therefore contain the term x(1-x(x-1/2). Continuing with an explanation of the rule of exact fit, the rule demands that the quartic, fourth order polynomial B.sub.4 must also contain the polynomial x(1-x) (x-1/2) as the established points of exact fit are still x = 0, 1/2 and 1. However, B.sub.4 must be of the fourth order and, in this example, the required form is obtained by adding a second factor (x-1/2). Thus, B.sub.4 contains x(1-x) (x-1/2).sup. 2 and FIG. 5 shows a curve of a fourth order polynomial of the form ##EQU3## where 256/3 is the scaling factor.
Thus the addition of a fourth order term of the form ##EQU4## with the value of the coefficient Q so chosen that an exact fit is obtained at the values of y for x = 1/4 and x = 3/4 will reduce the error still further.
The fourth order binary polynomial
can thus be rewritten. ##EQU5##
The algorithm can be written: ##EQU6##
The polarity operator ##EQU7## simply means that the coefficient it qualifies is subtracted if the interpolation is DOWN, that is to be performed for a lower segment of x, at the (n+1) th step and added if it is UP, that is to performed for the higher segment of x.
If y were expressed as an eighth order polynomial a fourth order appoximation would leave a residual need which could be expressed as a polynomial containing the fifth to eighth order polynomials.
Thus to implement the algorithm up to the fourth order polynomial it would be necessary to know the values of the coefficients a, b, K, C and Q which may conveniently be derived from a knowledge of five points values of y at specific values of x, namely at
The above polynomial series can be extended ad infinitum a convenient progression would be to extend the series to the eighth order and arrange that the coefficients d.sub.5 to d.sub.8 for the fifth to eighth order polynomials B.sub.5 to B.sub.8 in combination obtain exact fits for the function at the odd 1/8 values of x. To implement an eighth order polynomial interpolation it is necessary to know nine specific quantities such as the nine point values of y at specific values of x, namely at x = , 1/8, 1/4, 3/8, 1/2, 5/8, 3/4, 7/8, 1.
The coefficients d.sub.o, d.sub.1, K, C and Q of the binary polynomials are defined as those coefficients which give rise to an exact fit at the end points x = 0, 1 and the binary sequence of x values at 1/2, 1/4 and 3/4. It is assumed that the five point values y.sub.(0), y.sub.(1/4), etc. of the function to be approximated are known. The values of the coefficients d.sub.o, d.sub.1, K, C and then readily be determined on a simple alegbraic basis as more fully explained in the aforementioned patent specifications.
Method including flow charts and apparatus for interpolating such polynomials including a fourth order polynomial are fully described in the aforementioned specifications but for ease of explanation a statement of a fourth order Binary Polynomial Algorithm implemented by means of a method described in the aforementioned specifications is shown at Table 1 below for completeness.
In devising the particular algorithm statement to be described certain assumptions were made to provide a preferred implementation of the method for a particular application and certain options were taken but these assumptions and options should not, of course, be regarded as limitations of the scope of the invention. Some of these assumptions and options were:
1. Digital quantities representative of point values defining a segment and correcting terms are provided in fixed point notation 2's complement code.
2. Statements will be valid within an area bounded by the 0 to 1 range in both X and Y. It should be noted that bipolar coefficients and terms arise, despite the above unipolar limitations.
3. An "ideal" algorithm will directly generate any fourth order function which can be drawn in the area bounded by the 0 to 1 range of x and y, providing that between the x range limits, the function does not intersect either of the lines y = 0 or y =1.
Corner intersection (i.e. at x = 0 or x = 1) and tangential contact (i.e. of y = 0 or y = 1 lines) are both permitted.
Consider a function of x to be represented by a general polynomial expression:
where B.sub.n is a linear polynomial expression in x of the nth order, and d.sub.n is the relevant addressed coefficient specifying amplitude.
As aforementioned the concept of "Binary Polynomials" requires that points of exact fit be established and retained in a binary sequence of x values such as the following preferred sequence
and so on.
Each polynomial group achieves the exact fits at the next group of x values in binary sub-division.
The algebraic factors of each polynomial are either uniquely determined, or guided, by the requirements of exact fit. A numeric scaling factor is in each case chosen to give a polynomial peak value as near to unity as possible; this choice being consistent with the implementation of interpolation in a convenient add-shift organisation, wherein, for example, digital values are held in shift registers and division by a power of 2 is effected by shifting the digital number the appropriate number of places in its register.
Various options are available for the algebraic factors of a given Binary Polynomial. The first options arise for the B.sub.o and B.sub.1 pair of polynomials. It would have been possible to use the polynomial B.sub.o to achieve exact fit at x = 0 and the polynomial B.sub.1 to achieve exact fit at x = 1. The decision was not to take this course but to employ and B.sub.o and B.sub.1 pair simultaneously to obtain exact fits at x = 0 and x = 1. A similar situation arises for the B.sub.3 and B.sub.4 pair of polynomials. Ever increasing numbers of options arise for each higher order group through the possibilities of fit as a collective polynomial group, as pairs of polynomials, as individual polynomials, and in different fit sequence.
It is believed that general advantage can be obtained by retaining, for each polynomial, the condition of odd or even symmetry about the x domain centre, that is, the initial segment of x (see Binary Polynomial graphic forms illustrated at FIGS. 1 to 5 wherein the initial segment extends from x = 0 to x = 1 and the x domain centre is at x = 1/2).
This decision to retain such symmetry eliminates options from the B.sub.o /B.sub.1 and B.sub.3 /B.sub.4 pairs. A reduction of options also results within each of the higher order groups.
The polynomial y = d.sub.o B.sub.o + d.sub.1 B.sub.1 + d.sub.2 B.sub.2 + d.sub.4 B.sub.4 can thus be illustrated by the following Table 2:
The designated coefficients for the fourth order approximation may be readily derived from five function samples equispaced in the x domain:
The resulting fourth order approximation is: ##EQU8##
In general, the algorithm progresses from stage to stage, interpolating the stored function at a sequence of x values which constitute successive bisection of the x domain. The algorithm starts its operation holding point values of y at the x values 0 and 1, and values of the coefficients K, C, Q.
The first algorithm stage (n=1) always interpolates the stored function at x = 1/2 (y is determined at x = 1/2).
The second algorithm stage (n=2) interpolates y at the x value 1/4 or 3/4, depending upon whether the stage steps DOWN (x=1/4) or UP (x=3/4).
The third algorithm stage (n=3) similarly interpolates y at an x value 1/8, 3/8, 5/8 or 7/8, depending upon whether the stage steps DOWN or UP from the interpolated value at x = 1/4 or 3/4 and so on.
The DOWN or UP direction taken on a given algorithm stage, must therefore be determined. If the value of y is being calculated for a given value of x this is done by considering the 0 or 1 state respectively, which occurs for a particular bit of x. The n'th fractional fit of x determines the DOWN or UP direction taken at the (n+1)th stage of the algorithm.
An example will now be given which starts with a register holding a value of x as a 2's complement fractional number: ##STR7##
A single left shift is operated to remove the redundant polarity bit: ##STR8## A single left shift is operated upon each algorithm stage.
Before considering the algorithm statement of Table 1 in more detail, it should be explained that, as hereinbefore described with reference to Table 1 certain terms in the algorith require a polarity operator signifying subtraction or addition before updating the correcting term and, possibly another term or terms. Consider an `n`th stage algorithm term: ##EQU9## This stagement calls for the value of C.sub.n to be subtracted or added on the `n`th algorithm stage when updating the compensating term for the next stage (n+1) of the algorithm, in accordance with the "state" of a particular x bit, that is:
If the value of x is being determined for a given value of y (i.e. inverse interpolation) the interpolated value of y is compared with the given value of y to establish whether the next stage steps DOWN or UP, and a corresponding 0 or 1 is entered in the x register.
Referring now to the algorithm statement shown in Table 1, point of a and b at x = 0 and x = 1 defining the initial segment of x, and values of the second, third and fourth order coefficients K, C and Q respectively are stored for the first stage (n=1) of the algorithm, and y is to be determined for a given value of x. The algorithm then proceeds, stage by stage, as follows:
Stage 1, n = 1
i. y is interpolated at x = 1/2 by linearly interpolating between the point values a, b to obtain a midpoint value and corresponding the mid-point value by the addition of K to obtain y.sub.(n.sub.=1) = 1/2(a+b) + K
ii. The first fractional bit of x is examined as hereinbefore described to determine whether to step UP to the new segment between x = 1/2 and x = 1 or DOWN to the segment between x = 0 and x = 1/2 at the next stage (n+1) = 2.
iii. If the decision is to step DOWN (to interpolate at x = 1/4) a is retained and y.sub.(n.sub.=1) is substituted for b. (In general this may be stated as D:a.sub.n.sub.+1 = a.sub.n and b.sub.n.sub.+1 = y.sub.n. Similarly if the decision is to step UP (to interpolate at x = 3/4) b is retained but y.sub.(n.sub.=1) is substituted for a (U:a.sub.n.sub.+1 = y.sub.n and b.sub.n.sub.+1 = b.sub.n).
iv. K is updated (to K.sub.n.sub.+1 = K.sub.2) by dividing K by 4 and subtracting C if the decision is to step DOWN adding C if the decision is to step UP adding Q so that ##EQU10## and in general ##EQU11##
v. C is updated to [C.sub.(n.sub.+1) = C.sub.(n.sub.=2) ] by dividing C by 8 and subtracting Q/2 if decision is to step DOWN or adding Q/2 if decision is to step UP so that ##EQU12## in general ##EQU13##
vi. Q is updated to [Q.sub.(n.sub.+1) = Q.sub.(n.sub.=2) ] by dividing Q by 2 for use at (v) above and further dividing Q/2 by 8 to obtain Q.sub.(n.sub.=2) = Q/16 and in general ##EQU14##
Stage 2, n = 2
Depending upon the decision to step UP or DOWN, y.sub.(n.sub.=2) is interpolated at x = 1/4 or x = 3/4 to obtain y.sub.(n.sub.=2) = 1/2 (a.sub.2 + b.sub.2) + K.sub.2 and then steps (ii) to (v) are repeated prior to interpolation of y.sub.(n.sub.=3) at Stage 3. This process is repeated whereby the segment of x is successively bisected such that the point values a.sub.(n.sub.=1), b.sub.(n.sub.+1) converge upon the given value of x for which y is to be determined.
A method of determining the polynomial coefficients is described in detail in U.K Pat. Specification No. 1,363,073 (U.S. Specification No. 3,789,203).
FIG. 11 shows a simplified block circuit diagram of a data processing apparatus for implementing the algorithm. The apparatus 10 comprises a Serial Random Access Memory (RAM) 12 organised as a plurality of 20-bit shift registers, two 20-bit registers (SR) 14, 16 depicted as SRA and SRB respectively and a full adder 18.
The RAM 12 has its input 12a coupled to an input selector means 22 having a switch S1, shown as a simple mechanical switch, having a movable contact S1a selectively connectable to one of two fixed contacts S1b and S1c. Contact S1b is coupled to an input terminal 24 arranged to receive, in operation, the point values a and b and the correcting terms K, C and Q in the form of 20-bit words in 2's complement fractional binary code. The five binary words a, b, K, C and Q are fed to five 20-bit registers of the RAM 12 serially under the control of a master clock-pulse generator 26. The connections from the generator 26 to the various parts of the circuit 10 such as the RAM and to the clock pulse inputs of the shift registers and other control circuitry have been omitted as their design would be obvious to a competent logic designer and their explanation would only tend to confuse the present description. Contact S1c is coupled to the output 18c of the adder 18.
A shift-register input selector circuit 28 has outputs 28a and 28b respectively connected to the inputs 14a, 16a of the two shift registers 14 and 16. The selector circuit 28 has four inputs 28c, d, e, f; input 28c being connected to output 12b of the RAM 12, 28d to the output 18c of the adder 18, 28e to the output 14b of the shift register 14, and 28f to the output 16b of shift register 16. Any one of the inputs 28c to 28f can be selectively coupled to either of the outputs 28a and 28b.
The outputs 14b, 16b of the shift registers 14, 16 are coupled to the adder by way of an adder logic circuit 30 which can be controlled according to the UP/DOWN determination to add or subtract a selected one of its inputs from the other.
A 16-bit shift register 32 designated SRx is provided for storing the given value of x, set by an x input circuit 34, for which the value of y is to be obtained. The value of the independent variable x is stored in 2's complement fractional binary code. An UP/DOWN detector 36 is coupled to receive the most significant fractional bit of x, ignoring the polarity bit, and to set the adder logic circuit 30 accordingly when updating the correcting terms as hereinbefore described.
A comparator circuit 38 is provided having inputs connected to each stage of the SRx register 32 and is arranged to detect when all of the x bits are zero to provide an output signal to terminate the interpolation. As aforementioned the number in the SRx register 32 is shifted one place for each stage in the algorithm so that the first bit to be interrogated is the most significant bit after the polarity bit has been removed.
A 16-bit shift register 40, designated SRy, is connected to the output 18c of the adder to receive the interpolated value of y.
In operation digital numbers are written-in and read-out from the RAM 12 and are processed through the shift registers under the control of clock pulses from the generator 26. Division of a digital number in a shift register by a power of 2 is effected by shifting the number the appropriate number of places. The digital numbers are presented to the RAM and the shift registers SRA, SRB and SRy as 20-bit numbers although the final result taken from SRy may be confined to a 16-bit number. This is to obviate the need for correction of rounding errors during interpolation.
It is believed that operation of the circuit 10 to interpolate the value of the dependent variable y for a given value of the independent variable x can conveniently be described by a series of statements. In the statements, a shorthand is adopted using the references of FIG. 11, whenever possible, viz. "28c to 28a" means that the input 28c of the shift register selector circuit 28 is connected to the output 28a.
Operation:
1. S1a to S1b. Write a, b, K, C, Q into RAM as a series of 5 .times. 20-bit words.
Stage 1, n = 1
2. 28c to 28a - Read a from RAM and write into SRA.
3. 28c to 28b - Read b from RAM and write into SRB.
4. Shift a 1-bit in SRA = a/2.
5. Shift b 1-bit in SRB = b/2.
6. Adder logic 30a + 30b; 28d to 28b.
7. Add, output 18c = (a+b)/2 and write into SRB.
8. 28c to 28a - Read K from RAM and write into SRA.
9. Adder logic 30a + 30b; Add output 18c = (a+b)/2 + K = y.sub.1 = y.sub.(x.sub.=.sub.1/2) and S1a to S1c write y.sub.1 into RAM and into SRy.
Update coefficients
10. Interrogate first, most significant, fractional bit of x to determine whether the next stage of the algorithm steps UP (interpolate y at x = 3/4) or DOWN (interpolate y at x = 1/4).
If x bit = 1, step UP: If x bit = 0, step DOWN.
Update point values, a and b
11. i. If x = 1 step UP at Stage 2, retain b in RAM and substitute y for a;
11. ii. if x = 0 step DOWN at Stage 2; retain a in RAM and substitute y for b.
Update K
12. 28c to 28b - Read K from RAM and write into SRB.
13. Shift K 2-bits in SRB = K/4.
14. 28c to 28a - Read C from RAM and write into SRA.
15. i. If x = 1, step UP at Stage 2.
Adder logic 30a + 30b Add - output 18c = K/4 + C and 28d to 28b write (K/4 + C) from adder 18 into SRB,
Or
15. ii. If x = 0, step DOWN at Stage 2. Adder logic 30b - 30a Add - output 18c = K/4 - C and 28d to 28b write (K/4 - C) from adder 18 into SRB.
16. 28c to 28a - Read Q and write into SRA.
17. Adder logic - 30a + 30b. Add output ##EQU15## and S1a to S1c write K.sub.n.sub.=2 into RAM.
Update C
18. 28c to 28b. Read C from RAM and write into SRB.
19. 28c to 28a. Read Q from RAM and write into SRA.
20. Shift C 3-bits in SRB = C/8.
21. Shift Q 1-bit in SRA = Q/2.
22. i. If UP at step 10, Adder logic 30a + 30b Add - output 18c = C/8 + Q/2 = C.sub.2, and S1a to S1c - write C.sub.2 in RAM and 28e to 28a - Q/2 in SRA.
Or
22. ii. If DOWN at step 10, Adder logic 30b - 30a Add - output 18c = C/8 - Q/2 = C.sub.2, and S1a to S1c - write C.sub.2 in RAM and 28e to 28a - Q/2 in SRA.
Update Q
23. Shift Q/2 in SRA 3-bit = Q/16 = Q.sub.2
24. Adder logic 30a + 30b (zero). Add, output 18c = Q/16 = Q.sub.2 and S1a to S1c - write Q/16 into RAM.
Stage 2, n = 2 - Repeat steps 2 to 24.
Thus it will be seen that there is provided an iterative interpolation method wherein all of the algorithm stages are identical and each coefficient is entered to the appropriate register, in singularity, at the start of the algorithm (that is no delayed entry requirement) and only a single x-bit is required to control each stage of the algorithm.
When polynomial approximation is needed for a plurality of functions, it may be found that a given polynomial order will meet most of the requirements, but a small number of the functions will require a higher order approximation. The invention now to be described provides a method whereby hardware or software organised for nth order interpolation can be utilised to yield up to mnth order interpolation in m interpolations.
The description will concentrate upon a particular case of a fourth order interpolation method arranged to provide an eighth order interpolation in two operations.
However, the method may be used at higher or lower basic orders, applied to other polynomials, and operated for further extension of order by employing more than two recursions of interpolation.
As aforementioned to perform a fourth order interpolation it is preferable to have knowledge of the function to be interpolated in the form of five function values equispaced in the x range 0 to 1.
Thus in the example to be described it is preferable that function definition be made by way of nine function values equispaced in the x range 0 to 1.
The five function values y.sub.0, y.sub.1/4, y.sub.1/2, y.sub.3/4, and y.sub.1 will be stored in the normal manner for subsequent coefficient determination and interpolation of the fourth order approximation as described.
Assume that the eighth order polynomial interpolation to be performed is described by:-
where d.sub.n is the nth order coefficient and B.sub.n is a linear polynomial of x of the nth order. If the coefficients d.sub.o, d.sub.1, d.sub.2, d.sub.3, and d.sub.4 are determined from the five point values y.sub.(0), y.sub.(1/4), y.sub.(1/2), y.sub.(3/4), y.sub.(1), and a combined interpolation of the zero order to fourth order terms performed, the value of y so obtained would fall short of the eighth order polynomial definition to the extent of the "residual need" above the fourth order.
The residual need z, beyond the fourth order approximation, is
the residual need z may be factorised into an expression comprising the product of two constituents, of which one is a fourth order polynomial of x and the other is the sum of four polynomials ranging from the fourth to the first order inclusive each multiplied by its appropriate coefficient. Thus, factorising
where H.sub.1, H.sub.2, H.sub.3 and H.sub.4 are specific polynomials of the first, second, third and fourth order respectively.
For a specific value of x the constituent, containing the first to fourth order polynomials will be a numeric value and the expression for the residual need can be rewritten as
if it could be arranged that the polynomials H.sub.1, H.sub.2 H.sub.3 and H.sub.4 were in fact the same polynomials as B.sub.1, B.sub.2, B.sub.3 and B.sub.4 respectively, the value of g.sub.4 could readily be determined for a particular value of x. This would simply require that a loading of the coefficients O, d.sub.5, d.sub.6, d.sub.7, and d.sub.8 be made to a fourth order interpolation such as described with reference to FIG. 11 (normally loaded with d.sub.0, d.sub.1, d.sub.2, d.sub.3 and d.sub.4 respectively), and an interpolation operation performed.
Even if the polynomials H.sub.1, H.sub.2, H.sub.3 and H.sub.4 differ from B.sub.1, B.sub.2, B.sub.3 and B.sub.4, but of course remain of equivalent order, it is still possible to determine g.sub.4 by use of a fourth order interpolation method, but the five coefficients become combinations of d.sub.5, d.sub.6, d.sub.7 and d.sub.8 rather than the unique values.
The determination of the coefficient g.sub.4 will be described later.
For a given value of x the eighth order polynomial approximation can thus be rewritten as
if the common fourth order polynomial G.sub.4 is equivalent to the polynomial B.sub.4 then it would be necessary merely to modify the fourth order coefficient d.sub.4 by consolidating it with the specific fourth order coefficient g.sub.4 of the polynomial G.sub.4 and the expression would become
if the polynomials G.sub.4 and B.sub.4 are different then it may be necessary to modify more than one of the fourth or lower order coefficients d to consolidate the specific coefficient g.sub.4.
The binary polynomials and their relevant coefficient designations, previously selected for fourth order approximation in the 0 to 1 x range, are shown in the following Table 3:
and the polynomials and their coefficients for the fourth to eighth orders, in accordance with a preferred method according to the invention, are:-
It will be remembered that it is a fundamental rule of methods using the binary polynomial series that as each point of exact fit is established all subsequent polynomials must preserve this fit. Thus all polynomials above the fourth order must make zero contribution at the x valves 0, 1/4, 1/2, 3/4, and 1. All such polynomials must therefore contain
Just as it was preferred to consider the polynomials B.sub.3 and B.sub.4 as a pair which were arranged collectively to achieve exact fits for the function at values of x equal to 1/4 and 3/4; in the preferred method according to the invention the polynomials B.sub.5, B.sub.6, B.sub.7 and B.sub.8 will be considered as a group which is to be so arranged that collectively they achieve exact fit at the odd one eighth values of x.
When factorising the expression for the residual need z, it is first necessary to derive a fourth order polynomial which is common to the fifth to eighth order polynomials listed in Table 3. Following the fundamental rule, it is necessary to derive a common polynomial which will establish four of five required zeros at x, (1-x), (x-1/2), (x-1/4) and (x-3/4). In the development of the preferred method it was believed that only disadvantage would result from abandoning the principle of symmetry, whereby each polynomial retains "odd" and "even" symmetry about x = 1/2. This belief in symmetry thus enables the elimination of the factor (x-1/2) and so the x dependent part of ##EQU16## where the scaling factor 64 is chosen to make G.sub.4 = -1 at x = 1/2. FIG. 8 shows this common fourth order polynomial G.sub.4 in graphic form. It should be emphasised that the common fourth order polynomial could take other forms, provided of course, that it is of the fourth order and is common to each of the fifth to eighth order polynomials, but this is found to be a convenient one for the method.
Having derived the common fourth order polynomial the next step in factorising the expression for the residual need is to derive the polynomials H.sub.1 to H.sub.4 in the expression
and this is achieved by dividing the polynomials B.sub.5 to B.sub.8 listed in Table 3 by the established expression for G.sub.4, that is; ##EQU17## If the polynomials H.sub.1 to H.sub.4 were the same as the polynomials B.sub.1 to B.sub.5, the coefficients I, S, P and E could be regarded as equivalent to the coefficients d.sub.1 to d.sub.4 respectively of a fourth order polynomial and a fourth order polynomial interpolation performed as described to obtain the value of g.sub.4 at a given value of x. Clearly in this case they are not and so the coefficients must be modified. Examination of the polynomial expression derived above for g.sub.4 indicates that the third and fourth order polynomial expressions H.sub.3 and H.sub.4 are the same as the polynomials B.sub.3 and B.sub.4 respectively. Therefore the coefficient P and E can be used directly as the coefficients C and Q in a fourth order interpolation and will be designated Nc and Nq respectively. However, the second order term for H.sub.2 which is 4(x-1/2).sup.2 is not the same as that for B.sub.2 which is 4x(1- x) although they are not by definition, of the same order. It is necessary therefore to factorise the two polynomials to obtain a value of a coefficient for the x.sup.2 term which can be regarded as the coefficient K in the fourth order interpolation. It can be shown that the coefficient, which will be designated NK is -S. This will leave a first order term in x which will have to be "pushed down" to be considered with the H.sub.1 polynomial when deriving the zero'th and first order coefficients for a fourth order interpolation. Thus although H.sub.1 is the same as B.sub.1, the coefficients will be modified and it can be shown that (S-I)=N.sub.a is equivalent to a and (S+I)= N.sub.b is equivalent to b in terms of a fourth order interpolation.
Thus by examination of the polynomials up to the fourth order, interpolation of g.sub.4 for a given value of x will be obtained by loading into the RAM 12 of the apparatus of FIG. 11
S - i into a `a` register
S + i into the `b` register
-S into the `K` register
P into the `C` register
E into the `Q` register
Having derived the common fourth order polynomial G.sub.4, the polynomials H.sub.1 to H.sub.4 and their coefficients and used the coefficients to perform a fourth order interpolation to determine the specific coefficient g.sub.4, the next step in the method is to modify, as required, the zero'th to fourth coefficients d.sub.0 to d.sub.4 to consolidate the g.sub.4 G.sub.4 term before performing a second fourth order interpolation. This may be explained by initially considering as an example a fourth order interpolation in which a, b and C are made equal to zero, K is made equal to -g.sub.4 and Q is made equal to 3/4g.sub.4. By examination of the second and fourth order polynomials (Table 3) it can be shown that the interpolated result will be ##EQU18## as follows: Interpolation of a 4th order expression, in accordance with the statements of Table 3, is given by, ##EQU19##
In the particular case where ##EQU20##
Substituting for B.sub.2 and B.sub.4 ##EQU21##
The method is concerned only with the particular value of x for which, ##EQU22##
Hence, by substitution, the relevant particular value of y is g.sub.4.sup.. G.sub.4.
To consolidate the g.sub.4 G.sub.4 interpolation, the binary polynomial coefficients are derived from the five function values of y and x values of O, 1/4, 1/2, 3/4, and 1 as hereinbefore described and are then modified using the specific value of g.sub.4 determined for the given value of x. From the example in the immediately preceding paragraph the coefficients are modified as follows:
If these modified values of the coefficients are now used to perform a second fourth order interpolation, the result of the interpolation will yield a value of y which would have been obtained by using an eighth order interpolation.
A method of determining the polynomial coefficients up to the fourth order is described in U.K. Pat. Specification No. 1,363,073 (U.S. Pat. Specification No. 3,789,203). The additional calculations necessary to extend the method to perform an eighth order interpolation will now be described.
As stated previously, nine function values of y at x values of 0, 1/8, 1/4, 3/8, 1/2, 5/8, 3/4, 7/8, and 1 are preferred.
In addition to storing five of these values namely y(0), y(1/4), y(1/2), y(3/4) and y(1), for fourth order definition, four numbers Na, Nb, Nc and Nq must be calculated from the nine function values.
If the method is to be inplemented on a computer, a standard program is included with the main algorithm program. If the method is to be implemented on dedicated hardware and if a computer terminal or programmable calculator is available, a program is written to perform the calculation. Whenever an eighth order definition is required, the program is run to translate the nine function values into the four required higher order definition constants, Na, Nb, Nc and Nq.
Calculation of the four constants Na, Nb, Nc and Nq is as described in the following Example:
a. The interpolation values (w) of the fourth order approximation are determined at the odd eighth values of x, that is at x = 1/8, 3/8, 5/8 and 7/8. These values could be determined by a polynomial interpolation method but if fixed word length registers in purpose designed data processing apparatus are used, errors may be introduced. A convenient method of determining the values of w as follows: ##EQU23##
b. The residual needs (z) at the odd eighth values of x are then calculated as follows:
c. The higher order binary polynomial coefficients are calculated from the residual needs: ##EQU24##
d. The constants (N) are calculated from the binary polynomial coefficients:
and the fifth number required for the first interpolation loading is obtained within the interpolation routine as follows: ##EQU25##
Thus it will be seen that for a small sacrifice in time, an eighth order interpolation can be obtained by the use of a comparatively simple method or apparatus organised for fourth order interpolation only. In general the method can be directed to interpolating a value of a dependent variable y corresponding to a given value of an independent variable x, wherein y is a function of x and is described by a linear polynomial series of the mnth order, using an nth order interpolation method to obtain up to a mnth order approximation in m iterations of the nth order method.
For example to obtain up to a sixteenth order interpolation using fourth order interpolation would require four iterations of the fourth order interpolation. Expressed in simple terms seventeen function values of y at equal intervals of x would be the preferred function definition form and the method would involve the following steps:
1. factorising the thirteenth to sixteenth order polynomials to obtain an expression which is the product of a common twelfth order polynomial G.sub.12 and the sum of the twelfth to the nineth order polynomials each multiplied by its approximate coefficient,
2. determining the coefficients and using them to perform a fourth order interpolation to obtain a specific coefficient g.sub.12 at a given value of x
3. modifying, as required, the coefficients relative to the nineth to twelfth order polynomials to consolidate the g.sub.12 G.sub.12 term
4. using the modified coefficients to perform a second interpolation to obtain a value for g.sub.8 and then continuing with the steps of the method as described.
Dynamic range limitations may arise when the method of the invention is implemented in fixed point notation. These limitations arise because the higher order polynomials are largely determined by the lower order polynomials and will be influenced by the polynomials involved, the order of the basic interpolation method or apparatus, and the number of interpolation recursions employed. In most practical applications envisaged it is not believed that the limitations will be prohibitive but they result in a restriction in the amplitude of the higher order contributions to the total approximation.
FIGS. 6 and 7 show graphs of the fifth to eighth order polynomials used with apparatus designed to implement a fourth order algorithm in fixed point notation. It will be seen that the scaling factors are such that the peak amplitudes of these B.sub.5, B.sub.6, B.sub.7 and B.sub.8 polynomials are smaller than the values which would or could have been used, had free choice of the scaling factors been possible.
This limitation is unlikely to be of any consequence when the invention is implemented using floating point notation.
A further degree of fixed point scaling limitation arises for the fifth and sixth orders due to the necessity for both (S-I) and (S+I) to be within the .+-.1 range.
The largest potential contribution to limitation derives from polynomial conflict, which results in escalation of the (S-I), (S+I), P and E coefficients. This problem may or may not arise, dependent upon the profile of the residual need above fourth order approximation. The worst case is encountered when the curve fit demands large amplitudes (at the odd one eighth x values) which in combination are ill suited to the operated group of binary polynomials.
While the invention has been described in relation to a particular application it will be realised that its scope is not so limited. For example the method can be implemented by suitably programming a computer, or on data processing apparatus designed for the purpose. An example of one embodiment of such apparatus has been described in relation to FIG. 10 but many other arrangements are, of course, possible depending upon the application. For example, the apparatus can be designed to operate in bit-serial, word-serial; bit-serial, word parallel (FIG. 10); bit-parallel, word-parallel manner or any combination thereof.
Claims
I claim:
1. A method of interpolating a value of the dependent variable y corresponding to a given value of an independent variable x, wherein y is a function of x and is described by a linear polynomial series of the 2nth order wherein each term of the series comprises the product of a linear polynomial of x and a coefficient, and the terms of the linear polynomial series containing the (n+1)th to the 2nth polynomials are in the form of an expression which is a product of a common nth order polynomial of x, and the sum of the zero'th to the nth order polynomial each multiplied by its appropriate coefficient, using an nth order polynomial interpolation method to obtain up to a 2nth order interpolation in 2 iterations of the nth order interpolation method, the method comprising the steps of: determining the coefficients for each of the terms of the linear polynomial series; using the determined appropriate coefficients relevant to the (n+1)th to the 2nth polynomials to perform an nth order interpolation to obtain a specific coefficient for the common nth order polynomial at a given value of the independent variable x; modifying, as required the coefficients relevant to the nth and lower order polynomials of the series to consolidate the term which comprises the common nth order polynomial multiplied by its specific coefficient to provide modified coefficients; and performing a second nth order interpolation using the modified coefficients at the given value of the independent variable x; whereby the result of the second interpolation is the value of the dependent variable y for the given value of the independent variable x which would have been obtained by using a higher order interpolation method up to the 2nth order.
2. A method according to claim 1, in which the zero'th to the nth order polynomials of the said series containing the (n+1)th to the 2nth polynomials are the same as the zero'th to the nth order polynomials of the series and the said appropriate coefficients are used unmodified to perform the first said nth order interpolation.
3. A method according to claim 1, in which at least some of the zero'th to the nth order polynomials of the said series containing the (n+1)th to the 2nth polynomials are different from the zero'th to nth order polynomials of the series, but of the same order, and at least some of the said appropriate coefficients are modified before using them to perform the first said nth order interpolation.
4. A method according to claim 1 in which the said common nth order polynomial is the same as the nth order polynomial of the series and the step of modifying the coefficients relevant to the zero'th to the nth order polynomials in the series comprises the step of consolidating the coefficient of the nth order polynomial and the specific nth order coefficient obtained in the first said nth order interpolation.
5. A method according to claim 4 in which the series is a binary polynomial series.
6. A method according to claim 5 in which the binary polynomial series is an eighth order binary polynomial series and the value of the dependent variable is interpolated using two iterations of a fourth order interpolation method.
7. A method according to claim 5 in which the said common nth order polynomial is symmetrical about the x domain centre.
8. A method according to claim 5 in which the binary polynomial series is of the form y = d.sub.o B.sub.o +d.sub.1 B.sub.1 + . . . d.sub.8 B.sub.8 with d.sub.n and B.sub.n defined in accordance with the following Table: ##EQU26##
9. A method according to claim 8, comprising the step of factorising the higher-order terms of the series from the fifth to the eighth order to derive an expression of the form G.sub.4 = g.sub.4 G.sub.4, wherein G.sub.4 is the common fourth order polynomial, H.sub.1 to H.sub.4 are first to fourth order polynomials respectively, I, S, P and E are the coefficients of the fifth to eighth order polynomials respectively, and g.sub.4 = is a numeric term for the said given value of x.
10. A method according to claim 9, in which the said fifth to eighth order coefficients I, S, P and E are used in the first fourth order interpolation to obtain the specific coefficient g.sub.4 in such a way that values (S-I) and (S+I) represent the two point values defining the initial segment of the independent variable and the values -S, P and E represent the second, third and fourth correcting terms respectively.
11. A method according to claim 10, wherein the common fourth order polynomial, G.sub.4 is equal to the fourth order polynomial, B.sub.4 in the series and the said step of modifying the coefficients relevant to the fourth and lower order polynomials in the series comprises summing the coefficient d.sub.4 of the fourth order polynomial and the coefficient, g.sub.4.
12. A method according to claim 10, wherein the common fourth order polynomial G.sub.4 is not equal to the fourth order polynomial B.sub.4 in the series, and the step of modifying the coefficients relevant to the fourth and lower order polynomial in the series comprises subtracting the value of the specific coefficient g.sub.4 from the second order coefficient K and adding three-quarters of the value of the coefficient g.sub.4 to the fourth order coefficient.
13. A method according to claim 1 in which the said common nth order polynomial is different from the nth order polynomial of the series.
14. A method according to claim 1 in which n = 4.
15. A method according to claim 1 in which the nth order interpolation method comprises a method of obtaining a value of a dependent variable, y, for a given value of an independent variable, x, wherein y is a function of x and is described by a polynomial series of the form y = d.sub.o B.sub.o + d.sub.1 B.sub.1 + d.sub.2 B.sub.2 + d.sub.3 B.sub.3 + . . . + d.sub.2n B.sub.2n where Bn is a linear polynomial expression of x in the nth order and dn is the relevant coefficient, the interpolation method comprising the steps of; storing digital quantities representative of two point values defining an initial segment of the independent variable, and predetermined values of at least a second-order and a third-order correcting term, and carrying out the steps of, linearly interpolating between the two stored point values to obtain a digital mid-point value and to create two new segments, one of which is UP with respect to the mid-point value and one of which is DOWN, compensating the digital mid-point value by the addition of a compensating value comprising the second order correcting term to form a compensated digital mid-point value, determining whether the new segment of interest for the next stage of the method is UP or DOWN with respect to the compensated mid-point value, using the determined UP/DOWN information to effect replacement of one of said first and second digital quantities representative of the two stored point values by said compensated digital mid-point signal to create a new segment containing the correct value of the independent variable, modifying the compensating signal by dividing the digital value representative of the second-order correcting term by four, using the said UP/DOWN information to effect addition to or subtraction from the divided value of the second order correcting term of the value representative of the third-order correcting term in dependence upon whether the said new segment is UP or DOWN to form a new correcting term, modifying the digital value representative of the third-order correcting term by dividing it by eight, repeating the steps of linearly interpolating, compensating, determining, replacing and modifying to generate new digital quantities defining successively smaller segments having end points converging upon the correct value of the independent variable.
16. A method according to claim 15, in which the correcting terms comprise a fourth order correcting term and the step of modifying the compensating value further comprises the addition of the fourth-order correction term, and the step of modifying the digital value representative of the third-order correcting term comprises the step of using said UP/DOWN information to effect addition to or subtraction from the third-order term of half the value of the fourth-order term in dependence upon whether the said new segment is UP or DOWN, and the method further comprises the step of modifying the digital value representative of the fourth-order term by dividing it by sixteen.
17. A method according to claim 16, in which the said initial segment of the independent variable extends from x = 0 to x = 1 and the x domain centre is equal to 1/2.
18. A method according to claim 15 in which each polynomial expression is arranged to have one of odd and even symmetry about the x domain centre.
19. A method according to claim 15 arranged to obtain the value of the dependent variable y for a given value of the independent variable x, comprising the step of storing the said value of the independent variable x in binary form and examining the bits in turn, starting with the most significant bit and the step of determining whether the new segment is UP or DOWN for the (n+1)th stage of the method is effected by examining the nth bit of the independent variable to determine in accordance with the value of the said nth bit whether the new segment is UP or DOWN.
20. Apparatus for obtaining a value of one of a first variable y and a second variable x for a given value of the other variable, wherein y is a function of x and is described by a polynomial series of the form y = d.sub.o B.sub.o + d.sub.1 B.sub.1 + d.sub.2 B.sub.2 + d.sub.3 B.sub.3 + . . . d.sub.2n B.sub.2n, where B.sub.n is a linear polynomial expression of x in the nth order and d.sub.n is the relevant coefficient, the apparatus comprising storage means for storing digital quantities representative of two point values defining an initial segment of the independent variable, and predetermined values of correcting terms from the second-order to the 2nth order and means for performing an nth order interpolation comprising means for linearly interpolating between two stored end point values to obtain a digital mid-point value and to create two new segments, one of which is UP with respect to the mid-point value and one which is DOWN, means for compensating the digital mid-point value by adding to it a compensating value comprising a second order correcting term to form a compensated digital mid-point value, means for determining whether the new segment of interest for the next stage of the method is UP or DOWN with respect to the compensated mid-point value, means responsive to the determined UP/DOWN information to effect replacement of one of said first and second digital quantities representative of the two stored point values by said compensated digital mid-point signal to create a new segment containing the correct value of the independent variable, means for modifying the compensating signal by dividing the digital value representative of the second-order correcting term by four, using the said UP/DOWN information to effect addition to or subtraction from the divided value of the second order correcting term of the value representative of the third-order correcting term in dependence upon whether the said new segment is UP or DOWN to form a new correcting term, and means for modifying the digital value representative of the third-order correcting term by dividing it by eight, and control means for so controlling the apparatus as to iteratively cause it to generate new digital quantities defining successively smaller segments having end points converging upon the desired value of the independent variable.
21. Apparatus according to claim 20, in which the storage means is arranged to store a predetermined value of a fourth-order correcting term and the means for modifying effects modification of the compensating value by the addition to it of the fourth-order correction term, means for modifying the digital value representative of the third-order correcting term by using said UP/DOWN information to effect addition to or subtraction from the third-order term of half the value of the fourth-order term in dependence upon whether the said new segment is UP or DOWN, and means for modifying the digital value representative of the fourth-order term by dividing it by sixteen.
22. Apparatus according to claim 20 in which the said linear polynomial series is a binary polynomial series.
23. Apparatus according to claim 20 in which each polynomial expression is arranged to have odd or even symmetry about the x domain centre.
24. Apparatus according to claim 23, in which the said initial segment of the independent variable extends from x = 0 to x = 1 and the x domain centre is equal to 1/2.
25. Apparatus according to claim 20 comprising means for storing the said value of the independent variable x in binary form and means for examining the bits in sequence, starting with the most significant bit and the said means for determining whether the new segment is UP or DOWN for the (n+1)th stage of the method is arranged to examine the nth bit of the independent variable to determine in accordance with the value of the said nth bit whether the new segment is UP or DOWN.
26. Apparatus according to claim 25, in which the means for storing the said value of the independent variable is a shift register controlled by clock-pulses from said control means and the means for examining the bits of said independent variable is a detector arranged to detect the most significant fractional bit in the shift register at each stage of operation.
27. Apparatus according to claim 26 further comprising means for determining when all of the bits of the independent variable in the shift register are zero at the end of the first interpolation, means for restoring the value of the independent variable in the shift register and means responsive to the means for determining when all of the bits of the independent variable are zero at the end of the second interpolation and arranged to generate an output signal to terminate operation of the apparatus.
28. Apparatus according to claim 20, in which the storage means comprises a plurality of shift registers arranged to receive, in operation, digital values representative of the said two point values and said initial and modified correcting terms, the shift registers being controlled by clock-pulses from said control means.
29. Apparatus according to claim 20, in which the means for linearly interpolating two values includes means for summing the said two values and for providing a digital output signal representative of half of the sum of the said two values.
Patent Citations (2)
| Patent | Date | Inventor | Cited By |
|---|---|---|---|
| US3789203 | 1974-01-01 | Catherall et al. | |
| US3967100 | 1976-06-01 | Shimomura |