GB2185606A - Linear approximation circuit for curve generation - Google Patents

Abstract

A pipelined architecture linear approximation transform circuit using floating point number inputs, and slope (m) and intercept (b) information from lookup tables, for determining y = mx + b (where "b" can be negative or positive) to approximate a variety of curves by linear segments. Circuitry is also provided for rapidly calculating the square root or reciprocal of an input floating point number. <IMAGE>

Description

SPECIFICATION Linear approximation transform circuits In many electronic systems, such as graphic processing systems, it is useful to generate piecewise linear approximations of curves. For example, Figure 1 shows a curve, the first two portions of which are approximated by two linear segments each having a particular slope andY-axis intercept value. In the prior art, such calculations were performed either entirely in software, or with a board-level electronic circuit. How- ever, for very high speed systems, such as graphics processor, time is of the essence in performing such calculations. Therefore, it is desirable to have a dedicated circuit that can generate such linear approximations of curves.It is further desirable to be able to generate such mathematical functions as square root and reciprocal for use in such a system. In the present specification there is described a circuitwhich provides such functions. In the preferred embodiment there is provided an integrated circuit that has a pipelined architecture capable of performing a transformation in 300 nanoseconds, with a throughput rate of 100 nanoseconds at a clock frequency of 1 O M Hz.

In the accompanying drawings, by way of example only: Figure 1 is an example of a portion of a curve approximated by linearsegments.

Figure2 is a simplified block diagram of a circuit embodyingthe invention and showing its connection to external memory devices.

Figure 3 is a detailed block diagram of the circuit of Figure 2.

Like reference numbers in the various figures refer to like elements.

Acurve can be approximated by dividing it up into a series of linearsegments. Information about each of these segments in the form of a slope and aY-axis intercept value is stored in one or more electronic memory devices, such as a read only memory ("ROM"), that are coupled to the transform circuit of Figure 2.

Referring to Figure 2, a 32-bit number is input into the transform circuit. Twelve bits of the input number are used to address two different ROMS. The Intercept ROM generates a 23-bit integer representing the mantissa portion ofthe Y-intercept of a linear segment approximation of the desired curve. The Slope ROM uses the same input to output a 12-bit integer representing the slope of a linear segment approximation of the desired curve. lfthe input number is in the proposed IEEE 32-bitfloating pointnumberformat,then the 12 bits used are the 12 most significant bits of the 23-bit input mantissa. The 11 least significant bits are used for linear interpolation between theY-axis intercept values from the Intercept ROM. With this approach, any curve can be approximated using 212 line segments.This usually allows curve approximations which are accu rate to the two least significant bits.

Using these inputs to the transform circuit, the value of a curve can be approximated with the following expression: DataOut = Intercept + (Dataln x Slope)/211.

In the preferred embodiment ofthe transform circuit of Figure 2, this expression is evaluated using a multiplierand an adder. The 12 least significant bits ofthe input data and a 12-bit slope obtainedfromthe Slope ROM are multiplied. The 12 most significant bits ofthis result are added to the 23-bitY-axis intercept value obtained from the Intercept ROM.

The preferred embodiment of the present circuit has three major modes of operation. The first mode is the normal operating mode in which the input number is transformed based upon control inputs and the ROM inputs In the circuit, the 12 least significant bits of the input are routed into a multiplier along with the slope input from the Slope ROM. The 12 most significant bits ofthis result are passed to one inputofan adder circuit. The other input to the adder is derived from the output of a multiplexor. In this mode of operation,the multiplexor selects the Intercept ROM value to be added to the multiplier product. Simultaneously, the input exponent is adjusted based upon the type of transformation being performed.The output of the adder and the adjusted exponent are then combined and passed into an output register. The output of the output register passes through a multiplexor directly to the output connections of the circuit.

The second mode of operation is the No Operation ("NOOP") mode. In this mode, input data is passed through the circuit unchanged with three register delays. The multiplier operates as in the normal mode, but at the input to the adder the multiplier product is set to zero. The other input to the adder is derived again from the output of a multiplexor, but in this case control signals cause the original input data to be selected rather than the intercept data from the Intercept ROM. Thus the original data input is added to zero, which in effect passes the input data through the circuit unchanged. The exponent is passed through the exponent adjustment section with no change, and reassembled with the mantissa from the input data. This passes through the output register and the output multiplexorto the output connections of the circuit.

The third mode of operation is the Bypass mode, where input data is passed through the circuit unchanged with no register delays. In this case, the control signals are configured in such a way that the output multi plexor selects the original data input rather than the output ofthe output register. Therefore, the input data is passed directly to the output connections of the circuit.

The present circuit uses the proposed IEEE standard floating point format, which consists of 23 bits of mantissa, 8 bits of exponent, and a sign bit. In this format, a binary point is understood to exist between bit positions 22 and 23. Afloating point number is represented in one of the following ways: 1. If the exponent is nonzero,then: Number = [ ( 1 )(si#nl *2 lexponent-127l *(1 .data)j 2. Ifthe exponent is zero, but the data is nonzero (indicating a denormalized number), then: Number = [ (-1 )(si#n) *2#127) *(0.data) ] 3. If both the exponent and the data are zero, then: Number = 0.0 4.If the exponent is FF16 and the mantissa is zero, then: Numberisconsideredtobe: (+ or-)infinity.

5. If number is FF16 and the mantissa is nonzero,then: Number is considered to be: not a number.

In orderto simplify the present circuitry, a denormalized number is forced to zero, and any number with an exponent of FF16 is forced to (+ or-) infinity, depending on the sign bit.

Figure 3 shows a detailed block diagram of the Figure 2 circuit. In the preferred embodiment of the circuit, extra circuitry is added for the convenience of the end user.

The preferred embodiment ofthe present circuit has 75 input signal lines and 34 output signal lines. The input signal lines include 32 data inputlinesforafloating point number, 23 data input linesforan integer intercept value derived from the Intercept ROM, and 12 data input lines for an integer slope value derived from the Slope ROM. Input control signals includethefollowing: Holdin --this control signal is used to disable the clockto a data input register, causing the currentdata word to be clocked into the input register and blocking the next block signal to the input register, thus holding the prior input number in the input register.

HoldOut--this signal is used to disable the clock signal to a data output register, blocking the storage of any new data applied to the inputs of the output register.

Subtract Control (SUB) --this control signal is used to handle negative slopes for curves. When this signal is activated, the transform circuit performs a subtract operation on the input data.

Mode Control signal lines --two signal lines are provided to determine the operational mode ofthetrans- form circuit when data is input in the proposed IEEE 32-bitfloating point numberformat. One mode is the "NOOP" mode, in which data is passed unchanged through the circuit but with three register delays. A second mode passes the exponent of the input number unchanged through the circuit. A third mode approx imates the square root of the input number by dividing the exponent by two. Afourth mode approximates the reciprocal of the input number by taking the ones' compliment of the exponent of the input number.

Bypass --this signal line permits data to pass unchanged through the transform circuit with no internal register delays.

The output of the circuit includes 32 signals comprising the transformed value of the input number.

In the reciprocal and square root modes, certain input numbers cause the circuitry to "clamp" the outputto preset values. For example, if the exponent of the input number is equal to zero (representing a floating point input of zero in this system), the output is clamped to zero in the square root mode (exponent equals zero, mantissa equals zero), and to infinity in the reciprocal mode (exponent equals FFa6, mantissa equals zero). If the exponent ofthe input number is equal to FF1s (representing a floating point input of infinity), the output is clamped to infinity in the square root mode, and to zero in the reciprocal mode. The sign ofthe input remains unchanged except when clamping to zero. In this case, the sign bit is always set to zero.

The transform circuit of the present invention can logically be divided into two main sections, each having two pipeline stages. These are the mantissa interpolation section and the exponent adjust section. The man tissa interpolation section accepts the mantissa portion of the data input and the two ROM table inputs, and performs the interpolation function y = mx + b (where "b" can be negative or positive, as set by the SUB signal). The input data is the "x" value, and the transform circuit calculates the corresponding "y" value. The exponent adjust section uses the Mode Control input signals to determine what operation should be per formed on the exponent portion of the data input, depending on whether the circuit is in the square root, reciprocal, or logarithm mode.

Referring to Figure 3, all inputs to the circuit are initially stored in an input register 1. This data is then made available to the rest ofthe circuitforthe next clock cycle. An AND gate 7, controlled bythe HoldIn 1 signal, rngulates the clock input to the input register 1.

The mantissa interpolation section performs the mathematical operation necessary to interpolate the input data. This section also contains the control logic necessary to detect underflow and overflow conditions and 5 clamp the output result as needed, and to pass the input data through unchanged when the circuit is inthe NOOP mode.

In the first pipeline stage ofthe mantissa interpolation section, the two Mode Control signals are decoded into a reciprocal signal (RECIP), a square root signal (SORT), and a NOOP signal, by three AND gates2,3,4.

Two otherAND gates 5,6 are coupled to the exponent portion ofthe input number and are used to checkto ) see if the input number is zero or infinity, as indicated by the signals ZERO and MAX, respectively.

The NOOP signal is used to determine whether a transformation will take place in the circuit, or if the input data is to be passed through the circuit unchanged, but with pipeline delays. In particular, the NOOP signal is used to control a first multiplexor 10. If the NOOP signal is active, the multiplexor 10 passes the 23 bits ofthe mantissa ofthe input numberthrough to a first intermediary register 11. In the next clock cycle, the output of 5 the first intermediary register 11 is conditionally coupled to an adder/subtractor circuit 12 (through an AND gate 23). If the NOOPsignal is not active, then the 23 bits from the Intercept ROM are passed through to the intermediary register 11, and subsequentlyto the adder/subtractor 12 (again, through AND gate 23).

This stage of the mantissa interpolation section also accepts the 12 least significant bits ofthe input mantissa into a partial multiplier circuit 13, which shifts the input mantissa left one position to properly scale it (the shift may be performed simply by offsetting the coupling of the input mantissa signals by one bit position). The otherinputtothe shifter/multiplier circuit 13 is the 12 bitsfromthe Slope ROM. The partiall multiplier circuit 13 in the present embodiment does not perform the necessary full multiplication of its two input numbers in less than the system clock cycle time.Therefore, it has been necessary in the present embodiment to perform only a partial multiplication resulting in two partial products comprising 18 bits and 16 bits, which are stored in a second intermediary register 14. In the next clock cycle, these two partial products are summed in an adder circuit 15to producethefinal product.

The reciprocal signal (RECIP), the square root signal (SORT), and the NOOP signal generated in thisfirst section are stored in a third intermediary register 16foruse in the next pipeline stage during the next clock cycle. All three intermediary registers 11, 14, 16 could be replaced by a single large register if desired.

In the second pipeline stage of the mantissa interpolation section, the 12 most significant bits of the output product from the adder 15are coupled through an AND gate 20to adder/subtractorcircuit 12. The other input to the AND gate 20 is determined by a set of gates 12 that combine the MAX, RECIP, ZERO, and SORT signals to form a Clamp-to-Zero signal (CL0). A second set of gates 22 combine the same inputs in a different orderto form a Clamp-to-Infinity signal (CLI NF). Basically, the signals generated by the gating circuits 21,22 are defined in such a waythattaking the square rootofinfinity, orthe reciprocal of zero, will cause the CLINF signal to become active, and taking the square root of zero, orthe reciprocal of infinity, will cause the CL0 signal to become active.These two signals, along with the NOOPsignal, are combined to control the input of the product from the adder 15 through AND gate 20to the adder/subtractorcircuit 12. Thus, if only the NOOP signal is active, the "A" input to the adder/subtractorcircuit 12 is added to zero, and thus passes through that circuit unchanged. Ifthe CLIN F, CL0, or NOOP signals are active, the "B" input to the adder/subtractorcircuit 12 is set to zero. Similarly, the output ofthe first intermediary register 11 is gated by an AND gate which also is controlled by the CLINF and CL0 signals through a NOR gate 18. If eitherofthese signals is active, the "A" input of the adder/subtractor circuit 12 is effectively set to zero.Therefore, if either of the CLINF or CL0 signals is active, the output of the adder/subtractorcircuit 12 is clamped to zero.

The adder/subtractor circuit 12 can be set to the subtract mode if either the subtract signal SUB from the input register 1 (which is passed through the third intermediary register 16) is active, or the reciprocal signal RECIP is active. Otherwise, the adder/subtractor circuit 12 remains in its addition mode. This flexibility of the circuit allows negative slope curves to be processed.

The control signalstothe adder/subtractorcircuit 12 thus allow normal addition to occur, unless (a) a zero or infinity condition is detected, in which case the mantissa output of the adderwill be set to zero, or (b) if the input data is to pass through the circuit unchanged. In the case of a NOOP operation, the outputadder/ subtractorcircuit 12will simply be the input data mantissa. in all cases, the mantissa outputoftheadder/ subtractorcircuit 12 is coupled to an output register 30.

The exponent adjust section of the transform circuit manipulates the exponent of the input number in order to allow different types of curves to be approximated. The type of curve is determined by the Mode Control signals. For the reciprocal mode, the twos' compliment of the exponent is generated, which creates the reciprocal ofthe original exponent, thus approximating the reciprocal of the entire floating point number. In the square root mode, the exponent is divided by two, thus approximating the square root of the input number. In the logarithm mode and NOOP mode, the exponent is passed unchanged through the circuit. The exponent adjust section also performs exponent clamping for underflow and overflow conditions.If the result is to be zero, the exponent must be clamped to zero, and if the result is to be infinity, the exponent must be clamped to FF16. The exponent adjust operation is again done in two pipeline stages.

The first stage of the exponent adjust section comprises a subtractor circuit 17 that subtracts a constant "1271o" from the exponent ofthe input number in orderto removerthe exponent bias inherent in the prop osed IEEE 32-bit floating point number standard. The output of the subtractor circuit 17 is then stored in the third intermediary register 1 6 for use in the second stage ofthe exponent adjust section.

In the second pipeline stage, the exponent is passed through a series of multiplexors in orderto perform the required operations. First, the exponent and its ones' compliment (i.e., its inverse) are coupled to a first multiplexor 24 which is controlled by the reciprocal signal RECIP. Ifthis signal is active, the ones' compliment ofthe exponent is passed through the first multiplexor 24. Otherwise, the original exponent passes unchan- ged through the first multiplexor 24. The resulting output is then coupled to a second multiplexor 25 controlled by the square root signal SORT. One input to the second multiplexor 25 is simply the output of the first mu Itiplexor 24.The second input to the second multiplexor 25 consists of the most significant 7 bits ofthe 8-bit output from the first multiplexor 24, plus the most significant bit (bit 8), which is reduplicated. Effectively, the second input to the second mu Itiplexor is the exponent shifted right one place, which is equivalent in the binary number system to dividing the exponent by two. If the SORT signal is active, this second input will be passed through the second multiplexor 25. Otherwise, the unchanged output of the first multiplexor 24 will be passed through to a 3-to-1 multiplexor26. This 3-to-1 multiplexorcontrols exponent clamping. The other two inputs to this multiplexor are constants defined in such a way that when the exponent bias is restored further on in the stage, these input constants will result in exponents of zero and FF16, respectively.

The signals CLI NF and CLO control which input to the 3-to-1 multiplexor 26 is outputted. The resulting expo nent is then coupled to an adder circuit 27 which adds a constant " 1 2710" to the exponent, restoring the exponent to the form needed for the proposed IEEE 32-bit floating point number standard.

The number sign of the input data is also processed in the exponent adjust section. It simply passes unchanged through the first pipeline stage, and in the second stage it remains unchanged unless the CLOsignal is active. In this case, the sign is clamped to zero by means of an AND gate 28.

The output of AND gate 28, the adder circuit 27, and the adder/subtractorcircuit 12 comprises the final output member, which is assembled and temporarily stored in the output register 30. An AND gate 31 con trolsthe clock signal to the output register 30 by means ofthe HoldOut signal. When the HoldOutsignal is active, no new data can be inputto the output register30.

The outputofthe output register 30 is coupled to a output multiplexor 32, which is controlled by the Bypass signal. If this signal is active, the original input data is coupled to the outputs of the circuit through the output multiplexor 32 unchanged, and with no internal register delays. If the Bypass signal for the output multi plexor 32 is not active, then the final number stored in the output register 30 is passed to the outputconnec tion ofthe circuitthrough the output multiplexor 32.

While this invention has been described with reference to a preferred embodiment, it is not intended that this description be construed in a limiting sense. Various modifications of the preferred embodiment as well as other embodiments of the invention, will be apparentto persons skilled in the art upon reference to this description. For example, the basic inventive circuit could be readily adapted to a non-pipelined architecture.

It is therefore contemplated that the appended claims will cover any modifications or embodiments as fall within the true scope of the invention.

Claims (13)

1. A pipeline architecture, linear approximation transform circuit for approximating curves by generat ing a series of line segments using floating point number inputs, such numbers comprising a sign, an expo nent, and a mantissa, the circuit including: a. an input section for receiving and temporarily storing an input floating point number, and slope data and intercept data corresponding to the input member; b. a multiplier circuit, coupled to the input section, for multiplying a portion of the mantissa of the input number by the slope data and temporarily storing the resulting product; c. a summing circuit, coupled to the multiplier circuit, for summing the product and the intercept data; and d. an output circuit, coupled to the output of the summing circuit, fortemporarily storing and out putting the summed resultfrom the transform circuit.

2. The linear approximation transform circuit of Claim 1,further including: a. a first storage means coupled to the input section for storing line intercept data, for receiving a portion of the input number as an address, and for outputting line intercept data corresponding to said address to the input section; and b. a second storage means coupled to the input section for storing line slope data,for receiving a portion ofthe input number as an address,andforoutputting line slope data corresponding to said address to the input section.

3. The linear approximation transform circuitof Claim 1, further including selector means, coupled to the input section, the multiplier circuit, and the summing circuit, for transmitting the input data through the multiplier circuit, the summing circuit, and the output circu it without alteration.

4. The linear approximation transform circuit of Claim 1,furtherincluding an exponent adjustmentcir cuit, coupled to the input section and the output circuit, for approximating and outputting the reciprocal of the input number by inverting the exponent of the input number.

5. The linear approximation transform circuit of Claim 1,further including an exponent adjustmentcir cuit, coupled to the input section and the output circuit, for approximating and outputting the square root of the input number by dividing the exponent of the input number by two.

6. The linear approximation transform circuit of Claim 5, wherein the division by two is accomplished by shifting the exponent by one bit position.

7. The linearapproximation transform circuit of Claim 4, further including an infinity clamping circuit, coupled to the input section, the exponent adjustment circuit, and the summing circuit, for setting the man tissa of the summed resultto zero and the output exponent to a representation of infinity if the exponent exceeds the limits of the numbering system after adjustment or upon input.

8. The linear approximation transform circuit of Claim 4 further including a zero clamping circuit, coupled to the input section, the exponent adjustment circuit, and the summing circuit, for setting the man ì tissa of the summed result to zero and the output exponent to zero if the exponent equals zero after adjust ment or upon input.

9. A pipelined architecture, linear approximation transform circuitfor approximating curves by generat ing a series of line segments using floating point number inputs, such numbers comprising a sign, an expo nent, and a mantissa, the circuit including: a. an inputsectionfor receiving and temporarily storing an inputfloating point number, and slope data and intercept data corresponding to the input number; b. a first storage means coupled to the input section for storing line intercept data,for receiving a portion of the input number as an address, and for outputting line intercept data corresponding to said address to the input section;; c. a second storage means coupled to the input section for storing line slope data, for receiving a portion of the input number as an address, and for outputting line slope data corresponding to said address to the input section.

d. a multiplier circuit, coupled to the input section, for multiplying a portion ofthe mantissa ofthe input number by the slope data and temporarily storing the resulting product; e. a summing circuit, coupled to the multiplier circuit, for summing the product and the intercept data; f. an exponent adjustment circuit, coupled to the input section, for selectively approximating and outputting the reciprocal or the square root of the input number; g. an output circuit, coupled to the output of the summing circuit and of the exponent adjustment section, fortemporarily storing and outputting the summed and adjusted result from the transform circuit.

10. The linear approximation transform circuit of Claim 9, further including an infinity clamping circuit, coupled to the input section, the exponent adjustment circuit, and the summing circuit, for setting the man- tissa of the summed result to zero and the output exponentto a representation of infinity if the exponent exceedsthe limits of the numbering system after adjustment or upon input.

11. The linear approximation transform circuit of Claim 9, further including a zero clamping circuit, coupled to the input section, the exponent adjustment circuit, and the summing circuit, for setting the mantissa of the summed result to zero and the output exponent to zero if the exponent equals zero after adjust mentorupon input.

12. A linear approximation transform circu it for approximating curves by generating a series of line seg- ments using floating point number inputs, such numbers comprising a sign, an exponent, and a mantissa, the circuit including: a. an input section for receiving an input floating point number, and slope data and intercept data corresponding to the input number; b. a multiplier circuit, coupled to the input section, for multiplying a portion of the mantissa of the input numberbythe slope data product; c. a summing circuit, coupled to the multiplier circuit, for summing the product and the interceptdata; and d. an outputcircuit, coupled to the output of the summing circuit, foroutputting the summed result from the transform circuit.

13. A linear approximation transform circuit substantially as herein described with reference to the accompanying drawings.