APPARATUS FOR PERFORMING A LINEAR INTERPOLATION ALGORITHM

• US 3,748,447 A
• Filed: 11/18/1971
• Issued: 07/24/1973
• Est. Priority Date: 11/18/1971
• Status: Expired due to Term

• Current Assignee: James D. Hajicek, Ralph E. Sipple
• Original Assignee: James D. Hajicek, Ralph E. Sipple
• Inventors: Hajicek, James D., Sipple, Ralph E.
• Primary Examiner(s): Botz, Eugene G.
• Assistant Examiner(s): Smith, Jerry
• Application Number:
  US05/199,953
• Time in Patent Office: 614 Days
• Field of Search: 235/151.11,150.31,152,197 318/570,573,600 444/1
• US Class Current: 708/290
• CPC Class Codes: G06F 17/17 Function evaluation by approximation methods, e.g. inter- or extrapolation, smoothing, least mean square method G06F17/18 takes precedence ; interpolation for numerical control G05B19/18

Abstract

A linear interpolation and numerical integration system employing U, X and Y arrays for computing additional sets of X and Y points in an X-Y coordinate system from a number of known sets of X and Y points. The U array is used to access 1P, Delta P and 2P values which constitute assigned points along the X axis and reference the known X points. Computation of the additional Y points is done in accordance with the expression:

Claims

1. In a data processor having a memory and an arithmetic means, an interpolation system for computing, from a number of known X and Y points on a curve in an X-Y coordinate system, a predetermined number of additional points, and comprising:

first general storage means for storing a plurality of operand control words for said interpolation procedure;

first sequencing means responsive to an interpolation instruction to read said plurality of operand control words from said memory into predetermined address locations of said first general storage means;

said operand control words defining the starting address of operand values in an array of such values, and a count of the number of such values in an array, with each operand control word having self-identifying tags;

said first sequencing means constructed to read said operand control words out of said first general storage means in predetermined order;

accessing means responsive to one of said operand control words being read out of said first general storage means to fetch a first 1P value, a first Delta P value and a first 2P value from memory and to store said 1P, Delta P and 2P values in predetermined addresses in said first general storage means, and where 1P is composed of an integer portion and a fractional portion F;

decrementing means for decrementing said count each time an operand value is accessed from memory;

means for fetching from memory the words stored at two predetermined sequential addresses by means of identification contained in said 1P value;

arithmetic means for computing the value of Yi in the expression;

Yi XK + F(XK 1 - XK) where F is said fractional portion of said 1P value;

means for changing the value of 1P after each computation of Y by adding Delta P to 1P to obtain a new value of F; and

means for comparing the value of 2P with 1P and for obtaining new values of 1P, Delta P and 2P when 2P becomes less than 1P.

2. An interpolation system in accordance with claim 1 and further comprising:

second general storage means;

second sequencing means constructed to control the entry of values accessed from memorY into predetermined addresses in said second general storage means;

said second sequencing means further constructed to read said values out from said second general storage means and into said arithmetic means;

means for supplying the fractional value F to said arithmetic means;

said arithmetic means constructed to respond to said values and to said fraction F to compute Yi; and

means for storing the computed values of Yi.

3. An interpolation system in accordance with claim 1 in which said first sequencing means is responsive to said interpolation instruction to read a first operand control word into said first general storage means;

said operand control word defining the starting address YSA and an indexing value YI for said starting address YSA to compute an updated address YA;

said first sequencing means constructed to read an operand out of said first general storage means once for each computation of a Yi value;

said accessing means responsive to the reading out of said operand control word from said first general storage means to fetch a Yb value from an address YA in memory which is defined by said operand control word;

a second general storage means; and

second sequencing means constructed to control the entry of Yb into a given address of said second general storage means;

said second sequencing means constructed to read Yb out of said second general storage means when Yi has been computed in said arithmetic means;

said arithmetic means further constructed to respond to the reading of Yb from said second general storage means to add Yb to the computed Yi value to produce a resultant Yr value;

said accessing means responsive to the completion of the computation of Yr and to the YA address to store Yr in YA.

4. An interpolation system in accordance with claim 1 in which said first sequencing means is constructed to respond to said interpolation instruction to read a first operand control word into said first general storage means;

said first operand control word defining the starting address YSA of a first operand in an array and an indexing value VI;

said first sequencing means constructed to read said starting address out of said first general storage means each time a computation of a Yi value is made;

said accessing means responsive to the reading of said address from said first general storage means to fetch a Yb value from that address YA in memory which is defined by the operand control word;

said arithmetic means responsive to said fetched Yb value to add said Yb value to the computed Yi value to produce a resultant Yr value;

said accessing means responsive to the completion of the computation of Yr and to the determined YA address to store Yr in YA.

5. In a data processor having a memory and an arithmetic means, an interpolation system for interpolating from a number of known X and Y sets of points on a curve in an X-Y coordinate system, a predetermined number of additional sets of points and comprising:

first general storage means for storing control words for performing said interpolation function;

means responsive to an interpolation instruction to read U array operand control words and X array operand control words from memory to said first general storage means;

said operand control words defining the starting addresses of the U array and the X array, and the count of the number of elements in said U array, and with each control word having self-identifying tags;

first sequencing means constructed to read said operand control words out of said first general storage means in predetermined order;

incrementing and fetching means respoNsive to the said U array operand control words being read out of said first general storage means to fetch a first 1P value, a first Delta P value and a first 2P value from main memory and to store said first 1P, Delta P and 2P values in said first general storage means, where 1P is composed of an integer portion and a fractional portion F;

decrementing means for decrementing said U array count each time a data element in the U array is accessed from memory;

said incrementing and fetching means constructed to add the integer portion of said 1P value to said starting address word to determine addresses XK and XK 1 and to fetch the words in addresses XK and XK 1 from memory;

said arithmetic means constructed to compute the value of Yi in the expression;

Yi XK + F(XK 1 - XK) where F is the fractional portion of 1P;

means for adding Delta P to the fractional portion of 1P after each computation of Yi to obtain a new value of F; and

means for obtaining new values of 1P, Delta P and 2P when 2P becomes less than 1P;

said arithmetic means being operationally independent of said fetching means to enable computation of Yi for a given cycle of operation while said fetching means are fetching the P and X values for the next subsequent computation of Yi.

6. An interpolation system in accordance with claim 5 and further comprising:

second general storage means;

second sequencing means constructed to control the entry of X array values accessed from memory into predetermined addresses in said second general storage means;

said second sequencing means further constructed to read said X array values out from said second general storage means and into said arithmetic means;

means for supplying the fractional value F to said arithmetic means;

said arithmetic means constructed to respond to said X values and to said fraction F to compute Yi; and

means for storing the computed values of Yi.

7. An interpolation system in accordance with claim 5 in which said first sequencing means is constructed to respond to said interpolation instruction to read a Y array operand control word into said first general storage means;

said Y array operand control word defining the starting address YSA of the Y array and an indexing value YI for said Y array;

said first sequencing means constructed to read said Y address out of said first general storage means each time a computation of a Yi value is made;

said accessing means responsive to the reading of said Y address from said first general storage means to fetch a Yb value from that address YA in memory which is defined by the Y array operand control word;

said arithmetic means responsive to said fetched Yb value to add said Yb value to the computed Yi value to produce a resultant Yr value;

said accessing means responsive to the completion of the computation of Yr and to the determined YA address to store Yr in YA.

8. In a data processor comprising a memory and an arithmetic means, an interpolation system for interpolating, from a number of known X and Y sets of points in an X-Y coordinate system, an additional number of X-Y sets of points by means of U and X operand control words containing the starting addresses of U and X data arrays and the count of U and comprising:

indexing and accessing means for accessing the successive U array addresses to obtain values of 1P, Delta P and 2P, where 1P has an integer portion and a fractional portion F;

said indexing and accessing means responsive to the integer portion of said 1P value and to the starting address contaIned in the X operand control word to access X addresses XK and XK 1;

said arithmetic means constructed to compute the value Yi in the following expression;

Yi XK + F(XK 1 - XK) and means for storing Yi;

said arithmetic means and said indexing means constructed to function and substantially independently of each other to enable the indexing and accessing of the X and U operand control words for a given cycle of operation to determine a given Yi, while the arithmetic means is performing the computations for the preceding cycle of operation to determine the immediately preceding Yi.