Apparatus for performing a linear interpolation algorithm

Claim 2

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.

Claim 3

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.

Claim 4

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.

Claim 5

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.

Claim 6

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.

Claim 7

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.

Claim 8

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.

Claim 9

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.

Claim 10

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.

Claim 11

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.