JPH083813B2 - Divider for linear interpolator - Google Patents

Description

Description: TECHNICAL FIELD The present invention relates to a divider used in a linear interpolator to calculate a displacement amount between a large number of points that divide two points into a plurality of points. .

<Prior Art> A linear interpolator has been conventionally used in a graphic display device or the like. This linear interpolator divides a line segment connecting any two points at equal intervals and continuously calculates the coordinates of the end points and the intermediate division points. It is necessary to perform division in order to calculate the amount of displacement between them, and to sequentially cumulatively add the amounts of displacement based on the coordinate values of one end point. The processing speed of this linear interpolator has a great influence on the drawing speed of a graphic display device, for example, and is therefore required to be as high as possible.

By the way, as a divider for obtaining the displacement amount between the adjacent points, conventionally, as shown in FIG. 3, a shift register (21) to which dividend data is input and divisor data are input. Register (22), subtraction circuit (23) to which data from both registers is input, and subtraction circuit (23)
, A quotient register (24) for storing the quotient obtained by performing a number of subtraction trials is adopted.
The subtraction trial is continued until the quotient is obtained for the entire range of the number of digits that can be stored in the quotient register (24), regardless of the number of divisions between the arbitrary two points.

<Problems to be Solved by the Invention> With the divider having the above configuration, a quotient with higher precision than necessary is obtained, and the division time becomes long due to the large number of subtraction trials. There is. More specifically, in the linear interpolator, the number of cumulative additions is uniquely determined by the number of divisions between any two points. Therefore, when the fixed number of additions is performed, the integer part Although it is only necessary to perform division with an accuracy that does not cause an error in, the division is performed up to the highest precision that can be physically calculated, so the time required for division of the portion corresponding to more than necessary precision is wasted. Therefore, the division time was longer than necessary by the time corresponding to this useless portion.

<Object of the Invention> The present invention has been made in view of the above problems, and it is possible to reduce the number of times of subtraction trials and shorten the time required for division without impairing the accuracy required as a linear interpolator. It is an object of the present invention to provide a divider for a linear interpolator that can be used.

<Means for Solving the Problems> To achieve the above object, the divider for a linear interpolator of the present invention calculates and obtains the number of divisions determined based on the distance between the start and end points that require interpolation. Change the subtraction trial number of the divider to the minimum number that does not cause an error in the integer part on the end point side in a state where the amount of displacement between the start point and the end point is added from the start point side by the number of times corresponding to the divided number, The subtraction trial of the divider is performed with the changed number of subtraction trials.

However, the divider performs division on the basis of the dividend and the data obtained by converting the divisor into a floating-point format.
The division may be performed as many times as the number obtained by adding 2 to the exponent, and the division result may be stored in the quotient register.

The quotient register may input data sequentially from a predetermined digit portion corresponding to the digit of the division result.

<Operation> In a state where the number of divisions determined based on the distance between the start and end points requiring interpolation is calculated, and the amount of displacement between the start and end points is added from the start point side by the number of times corresponding to the obtained number of divisions. By changing the subtraction trial number of the divider to the minimum number that does not cause an error in the integer part on the end point side and performing the subtraction trial of the divider with the changed subtraction trial number, the distance between the start and end points can be varied. In a graphic display device in which various line segments are mixed, a division result can be obtained with the minimum precision required for each line segment, and the obtained division result can be stored in a quotient register.

The number of divisions is the division based on the data obtained by converting the dividend and the divisor into floating-point type expressions,
If the subtraction trial is performed the number of times that the exponent of the dividend is added and the division result is stored in the quotient register, the mantissa parts are divided by the number of times that the exponent of the dividend is added by 2 to obtain a straight line. The division result can be obtained with the minimum precision required for the interpolator, and the obtained division result can be stored in the quotient register.

If the quotient register inputs data in order from a predetermined digit portion corresponding to the digit of the division result, all input data shifts or input digit switching is performed by the number of times corresponding to the required number of digits. The division result can be stored in the quotient register.

<Example> Hereinafter, an example will be described in detail with reference to the accompanying drawings.

FIG. 1 is a block diagram showing an embodiment of a divider for a linear interpolator. The dividend data is input to the type conversion circuit (1) and the divisor data is input to the type conversion circuit (2). . Based on the dividend data A and the divisor data B, the two-type conversion circuits (1) and (2) convert the data corresponding to the codes Sa and Sb, the mantissa parts A ′ and B ′, and the exponent parts Na and Nb, respectively. It is to convert. The mantissa part A ′ from the type conversion circuit (1) is input to the shift register (3), and the mantissa part B ′ from the type conversion circuit (2) is input to the shift register (4). The output data from both the registers (3) and (4) is input to the adder circuit (5). The reason why the adder circuit (5) is used here is that addition and subtraction are substantially the same in a binary arithmetic operation, so that a carry input of 1 is always given and one input is complemented by 1 (negative). (Logical) input so that it operates as a subtraction circuit. Further, the exponent part data Na from the type conversion circuit (1) is input to the counter (6) for controlling the number of trials of subtraction, and the exponent part data Nb from the type conversion circuit (2) is the quotient register (7). ) Has been entered. Further, the output data from the adder circuit (5) is fed back to the shift register (3), and the carry output data from the adder circuit (5) is input to the shift register (3) and the quotient register (7). ing.

In the case of the linear interpolator divider having the above configuration, the dividend data A is separated into the code data Sa and the absolute value data by the type conversion circuit (1), and the absolute value data is converted into the mantissa data. Normalization is performed so that the integer part of A ′ becomes 1, and exponent part data Na is generated. Also for the divisor data B, the type conversion circuit (2) similarly generates code data Sb, normalized mantissa data B ′, and exponent data Nb. Then, the exponent data Na of the dividend data A is input to the counter (6) to control the number of subtraction trials by the adder circuit (5) to be (Na + 2). Under the control of the counter (6), the mantissa data A'and B'from the two-type conversion circuits (1) and (2) are respectively added through a shift register (3) and a divisor register (4). 5), the subtraction operation is performed once by one, and the adder circuit (5) is made to correspond to whether the carry output data from the adder circuit (5) is 1 or 0.
The subtraction result data from the shift register (3)
The carry output data is input to the quotient register (7) as a quotient while controlling whether it is input to or to shift the contents of the shift register (3). Then, by performing the subtraction operation by the adder circuit (5) the number of times (Na + 2) specified by the content of the counter (6), the digits from 2 ^(Na-Nb) digits to 2- ^{(Nb + 1)} digits are obtained. You can get the quotient with the number (Na + 2). In the above configuration, only the calculation result of the absolute value part is obtained, and it is unclear what the code is. However, the code data Sa, Sb output from the conversion circuits (1) and (2) are shown in the figure. The judgment can be made by inputting into the code judgment circuit.

In the linear interpolator, the quotient obtained as described above is made to correspond to the exponent part data Nb of the data B input as the divisor data, and is between 2 ^Nb and 2 ^{(Nb + 1)} −1. Since only the number of times is added, as described above, 2 ^(Na-Nb)
Even if the quotient obtained as data from a digit to 2- ^{(Nb + 1)} digits is added by the number of times described above, an error does not occur in the integer part, and accurate coordinates of each division point can be obtained. More specifically, if the quotient is expressed in fixed-point format, and the quotient operation is truncated at 2- ^{(Nb + 1)} digits, an error will occur after ^{2-(Nb + 2)} digits. . The censoring error e in this case is e <2- ^{(Nb + 1)} , and the cumulative addition error E when adding 2 ^{(Nb + 1)} −1 times is It can be seen that the error that the cumulative addition error gives to the integer part is smaller than 1.

Therefore, in order not to cause an error in the integer part by adding B times, it is sufficient to obtain the quotient up to the 2- ^{(Nb + 1) th} digit.

FIG. 2 is an electric circuit diagram showing the structure of the quotient register (7), and selectors (8a) (8b) ... Corresponding to the data of each digit.
(8n), and latch circuits (9a) (9b) ... (9n). The carry output data C from the adder circuit (5) in FIG. 1 is input to one input terminal of each of the selectors (8a) (8b) ... The output data from the digit latch circuit is input to the other input terminal of each selector. The clock signal CLK is input to the clock input terminals of the latch circuits (9a) (9b) ... (9n) through the buffer (11), and the load signal LD is also stored in the buffer (12).
Is input to the clear terminals of the above latch circuits (9a) (9b) ... (9n) through. Further, the store pointer SP determined by the exponent part data Na, Nb of FIG. 1 is inputted with the register (13) inputted by the load signal and the store pointer SP stored in this register (13). By inputting the decode signal to the select input terminals of the selectors (8a), (8b), ... (8n), only one predetermined selector corresponds to the carry output data C. It is input to the latch circuit.

Therefore, according to the decode signal from the decoder (14), the selector of 1 sequentially inputs the carry output data to the latch circuit, and the quotient is obtained as the data of 2 ^(Na-Nb) digits to 2- ^{(Nb + 1)} digits. , Which is obtained in the floating point type by the adder circuit (5) in FIG. 1, can be automatically converted to the fixed point type by using the quotient register in FIG. Moreover, the time required to store all the required quotient data in the quotient register is reduced in response to the fact that the number of subtraction trials is small and it is only necessary to perform the storing operation for the required digit. You can

In the quotient register having the above configuration, the storage start digit is set to 2- ^{(Nb + 1)} digits, and the stored data is shifted up every time the carry output data is stored, but the carry output data is set to 2 ^{(Na- The} configuration may be such that the ^Nb) digits are sequentially stored to the lower digits.

<Effect of the Invention> When performing linear interpolation, the displacement amount between the start and end points is added from the start point side by the number of times corresponding to the number of divisions determined based on the distance between the start and end points. By changing the subtraction trial number of the divider to the minimum number that does not cause an error and performing the subtraction trial of the divider with the minimum required precision with the changed subtraction trial number, the time required for division is shortened and the graphic display device In particular, there is a unique effect that the time required for linear interpolation, which is a heavy load, can be shortened.

In particular, when the quotient data is directly stored in a range of digits which is known in advance, it is possible to achieve an even higher speed.

[Brief description of drawings]

1 is a block diagram showing an embodiment of a divider for a linear interpolator, FIG. 2 is an electric circuit diagram showing an embodiment of a quotient register, and FIG. 3 is a block diagram showing a conventional example of a divider. (1) (2) ... Type conversion circuit, (3) (4) ... Shift register, (5) ... Addition circuit, (6) Counter, (7) ... Quotation register, Selectors (8a) (8b) ... (8n ), Latch circuit (9a) (9b) ... (9n), (13) ... register, (14) ... decoder

Claims (3)

[Claims] 1. A graphic display device for interpolating between the starting and ending points by calculating coordinates of each of the dividing points which divides the starting and ending points into a plurality of points and divides the starting and ending points into a plurality of equal intervals. A divider used for calculating a displacement amount between the start and end points used in a linear interpolator, and a division number calculating means for calculating a division number determined based on a distance between the start and end points, The number of trials for changing the number of trials for subtraction of the divider is changed to a number that does not cause an error in the integer part on the end point side after adding the displacement amount from the start point side by the number of times corresponding to the number of divisions. The subtraction trial of the divider by the number of subtraction trials
A divider for a linear interpolator, characterized in that the obtained division result is stored in a quotient register. 2. A divider performs a division based on a dividend and data obtained by converting a divisor into a floating-point format. Attempts are made to subtract the number of times 2 is added to the exponent of the dividend and the division result is obtained. The linear interpolator divider according to claim 1, which is stored in a quotient register. 3. The divider for a linear interpolator according to claim 2, wherein the quotient register inputs data in order from a predetermined digit portion corresponding to the digit of the division result.