Generic interpolation pipeline processor

• US 5,020,014 A
• Filed: 02/07/1989
• Issued: 05/28/1991
• Est. Priority Date: 02/07/1989
• Status: Expired due to Term

• Current Assignee: Honeywell Incorporated (Honeywell International Inc.)
• Original Assignee: Honeywell Incorporated (Honeywell International Inc.)
• Inventors: Miller, Michael S., Spaanenburg, Hendrik A. E.
• Primary Examiner(s): Shaw, Dale M.
• Assistant Examiner(s): NGUYEN, LONG
• Application Number:
  US07/307,354
• Time in Patent Office: 840 Days
• Field of Search: 364/723, 364/736
• 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 generic interpolation pipeline processor for use in a real-time video display system to find the coordinates of any point P(x,y) on a line between P₁ (x₁,y₁) and P₂ (x₂,y₂) according to the equation ##EQU1## The processor includes an apparatus for performing integer interpolation calculations using a single independent variable to calculate two dependent variables in parallel and further includes apparatus for merging division and multiplication operations so as to increase throughput as compared to a division pipeline followed by a multiply pipeline.

Claims

1. Interpolation processor circuit apparatus embedded in a semiconductor chip for use in a video display system wherein the interpolation processor circuit apparatus comprises:

(a) state machine means for controlling the operation of the interpolation processor apparatus wherein the state machine means includes a Join Endpoints input (JOIN), an Enable Input Registers output (ENIR), a Chip Select input (CSEL), first and second Input Data Valid inputs (IDV1 and IDV2), and an Enable Counter Load output (ENCNT);

(b) a prologue stage including

(i) a first input register means for receiving a first X coordinate,

(ii) a second input register means for receiving a second X coordinate,

(iii) a third input register means for receiving a first Y coordinate,

(iv) a fourth input register means for receiving a second Y coordinate,

(v) wherein the first, second, third and fourth register means are structured and arranged to be controlled by the state machine means so as to be loaded as enabled by the activation of the CSEL, IDV1 and IDV2 inputs of the state machine,

(vi) a first adder means coupled to the first and second input registers for summing the contents of the first and second input registers and providing an RX result at a first adder output,

(vii) a first output register for receiving the RX result from the first adder output,

(viii) a second adder means coupled to the third and fourth registers for taking the deference between the first Y coordinate and the second Y coordinate and providing an RY result at a second adder output,

(ix) a second output register coupled to receive the RY result from the second adder output,

(x) a first counter means coupled to the first input register means for generating a quantity CX at a first counter output where CX is initially equivalent to the absolute value of (x-x₁) where x is an independent variable and x₁ is the first X coordinate, and

(xi) a second counter means coupled to the third input register means for generating a quantity CY at a second counter output where CY is initially equivalent to the value of the first Y coordinate;

(c) a plurality of identical calculation stages wherein each calculation stage includes;

(i) means for adding RX and CX to generate a new value of CX at an output using the complement of the sign of RX as a carry input wherein a sign LS is generated from the addition of RX and CX,

(ii) means coupled to the output of the means for adding CX and RX, for determining whether to pass the new value of CX or the previous value of CX to the next calculation stage based on the sign LS wherein the first of said calculation stages has its means for adding RX and CX coupled to the first output register and the first counter output to receive values for RX and CX, and wherein the first and subsequent calculation stages each have RX and CX output registers coupled to pass values for RX and CX to the means for adding RX and CX in the next calculation stage;

(iii) means for adding RY and CY to generate a new value of CY at an output, and

(iv) means coupled to the output of the means for adding RY and CY for determining whether to pass the new value of CY to the next calculation stage or the previous value of CY based on the sign LS wherein the first of said calculation stages has its means for adding RY and CY coupled to the second output register and the second counter output to receive value for RY and CY, and wherein the first and subsequent calculation stages each have RY and CY output registers coupled to pass values for RY and CY to the means for adding RY and CY in the next calculation stage.

2. The apparatus of claim 1 wherein, in a calculation stage, the previous CX and CY values are passed to the next calculation stage after being multiplied by 2 if the sign LS is negative.

3. The apparatus of claim 1 wherein the value of CY comprises a digital word including a fractional portion having a most significant bit and an integer portion having a least significant bit and wherein the apparatus further comprises a prologue section following and connected to the plurality of calculation stages wherein the prologue section includes a means for rounding further including means for adding the most significant bit of the fractional portion of the CY word to the least significant bit of the integer portion.

4. The apparatus of claim 3 wherein the first and second Y coordinates comprise eight bit digital words.

5. The apparatus of claim 3 wherein the first and second Y coordinates comprise 16 bit digital words.

6. The apparatus of claim 1 wherein the independent variable x is generated by an X counter coupled to the JOIN signal from the state machine which is loaded with the value of the first X coordinate from the first input register if the JOIN signal is inactive.