Method for solving equations of the type z = ((x1**y1) op (x2**y2) op ... op (xn**ym))**(1/k).

0001<maths id="math0001" num=""><img file="EP0218971A2_D0001.tif" /></maths>The invention relates to a working method for solving the type<maths id="math0002" num=""><img file="EP0218971A2_D0002.tif" /></maths>

0002The invention is based on the object of successively approximating the type equation by means of an iteration method<maths id="math0003" num=""><img file="EP0218971A2_D0003.tif" /></maths>bring about using digital computers. According to the invention, this object is achieved in that the processing of the independent and dependent variables x_" x₂ ... xn. z to determine the radical of the explicit or implicit form of the equation<maths id="math0004" num=""><img file="EP0218971A2_D0004.tif" /></maths>by potentiating and / or by performing elementary calculation operations and using digital building blocks of a computer, such that in a further computer programmed with an approximation formula an approximate initial solution value for the dependent variable z is calculated and in a comparator the radian determined in the digital computer with the potentiated value of an independent or dependent variables is compared and that the approximation is carried out by iteration of the comparison process in the comparator using a recursive loop, such that that from the approximate value formed in the programmable computer, two different initial values ​​are formed for a counter and a buffer and that the counter loaded with the specified word length of the solution addresses the most significant bit of the initial value written into the buffer via a demultiplexer and that the recursive iteration of this process continues until a termination criterion is met.

0003In particular, this working method can solve the equation important for picture element generators in display control units<maths id="math0005" num=""><img file="EP0218971A2_D0005.tif" /></maths>can be achieved with any specified accuracy requirements.

0004Both the equation in its general form _e.g.^k = x₁^y1 op x₂^y2 op ... opx_n^ym as well as the equation derived from it for a particular application<maths id="math0006" num=""><img file="EP0218971A2_D0006.tif" /></maths>can be solved with an arrangement for carrying out the working method, the technical hardware being a circuit component consisting of digital components (multiplier, adder) for the mathematical preparation of the radical of the equation in an explicit form, a comparison circuit (comparator) and a recursive iteration loop for successive approximation including circuit part and a sequence control.

0005According to an advantageous development of the invention, the recursive iteration loop consists of a demultiplexer controlled by a counter, which is connected to the output of a comparator, a latch, the output of which is fed back to an arithmetic unit for arithmetic processing of the equation.

0006The invention and further details of the invention are explained, for example, with reference to FIGS. 1 to 4. Show it<ul id="ul0001" list-style="none"><li>1 shows the block diagram of a circuit arrangement for carrying out the method for equations in the general form<maths id="math0007" num=""><img file="EP0218971A2_D0007.tif" /></maths></li><li>FIG. 2 is a block diagram to solve the equation<maths id="math0008" num=""><img file="EP0218971A2_D0008.tif" /></maths>after reshaping into an implicit form.</li><li>3 shows another embodiment for solving the equation<maths id="math0009" num=""><img file="EP0218971A2_D0009.tif" /></maths>in explicit form.</li><li>FIG. 4 shows a block diagram for a further exemplary embodiment for solving the equation<maths id="math0010" num=""><img file="EP0218971A2_D0010.tif" /></maths></li></ul>

0007To carry out the working procedure for solving the equation in the general form, it is necessary to potentiate a transformation.<maths id="math0011" num=""><img file="EP0218971A2_D0011.tif" /></maths>With the help of the circuit arrangement according to FIG. 1, that value z is sought by successive approximation, which potentiates the expression with k

0008<maths id="math0012" num=""><img file="EP0218971A2_D0012.tif" /></maths> corresponds. On the input side, the circuit arrangement consists of a number of programmable read-only memory modules (PROM x, ... PROM x_n), to which the independent variables x1, x₂, x_n be fed. The values ​​potentiated x in the multipliers₁^y 1, x₂^Y2nd , x_n^y2, x _n^ym are further processed in a subsequent arithmetic unit PO1 according to a predefined basic calculation type and the result is fed to a comparator KR1. The comparative value for the comparator is stored in a programmable PROM Z^K as an approximation of the dependent variable z in the power of k. The essential part of the iteration circuit is formed from a demultiplexer DEM1 with a counter ZL1, a memory SP1 and a register REG1. The iteration loop closes from the output of the memory SP1 via the permanent memory PROM Z^k and the comparator KP1 of the circuit. The individual steps of the working process are determined by a sequence control ABS1. The output of the register REG1 should deliver that value z which potentiates the expression x1 with k^y1, op x x2 Y2 op ... op xx_n^ym corresponds. For this purpose, the counter ZL1 is loaded with the required z-word width I before the computer operation begins. The required word length w of the counter ZL1 is therefore w = Idl.

0009The counter ZL1 uses the demultiplexer DEM1 to address the most significant bit of the word z to be written in the memory SP1 _A, which is initially set to logic "1. All low-order bits remain in the logic" 0 "state. The approximate initial value created in arithmetic logic unit 5 <maths id="math0013" num=""><img file="EP0218971A2_D0013.tif" /></maths>serves the comparator KP1 together with the programmable read-only memory PROMX, ... PROMX_n and the expression PO1 generated <maths id="math0014" num=""><img file="EP0218971A2_D0014.tif" /></maths> 1 op xx₂^y2nd op ... op, x_n^Ym to determine a comparison result.

0010This comparison shows that <maths id="math0015" num=""><img file="EP0218971A2_D0015.tif" /></maths> greater = x1^y1 op xx₂^y2nd op ... op xx_n^ym, the most significant bit of z_A in memory SP1 to logic "1"; otherwise it is set to logic "0". In preparation for the next calculation run, the counter ZL1 is decremented and switches the demultiplexer DEM1 to the next lower bit position 1 -1 of the memory SP1. The arithmetic operation is repeated in the same way until one of the two termination criteria counter ZL1 = 0 or<maths id="math0016" num=""><img file="EP0218971A2_D0016.tif" /></maths> = x, ^Y1 op x x. ^y2nd op ... op xx _n^ym is satisfied.

0011The determined value z_A is transferred to register REG1. In this way, all 1 bit of the searched value z can be determined with a counter of a maximum of 1 LSB.

00122 shows an exemplary embodiment of a circuit for solving the simplified equation

0013<maths id="math0017" num=""><img file="EP0218971A2_D0017.tif" /></maths>This embodiment differs from the working method for solving the more general equation in that an implicit equation for z is realized. After a simple mathematical conversion, the digital calculation is based on the following form.<maths id="math0018" num=""><img file="EP0218971A2_D0018.tif" /></maths>

0014For one of the independent variables (x,), the circuit on the input side consists of two adders AD1, AD2 for summing the bracketed expressions (z -x,) and (z + x,) which are fed to a replicated multiplier MUP1 for product formation. In order to reverse the sign of the independent variable x, for the arithmetic operation in the adder AD1, a reversal of the sign of the digital value is achieved by means of an upstream 2's complement generator KB.

0015The second independent variable x2 becomes a programmable read-only memory PROM <maths id="math0019" num=""><img file="EP0218971A2_D0019.tif" /></maths> fed for squaring. A comparison of the prepared parts of the implicit equation form is carried out in the comparator KP2.

0016At the same time, a further programmable read-only memory block PROM AW forms an approximate initial value of the dependent variable z on the two independent variable x and x2 according to the following relationship.

0017<maths id="math0020" num=""><img file="EP0218971A2_D0020.tif" /></maths><maths id="math0021" num=""><img file="EP0218971A2_D0021.tif" /></maths>

0018The iteration circuit connected to the output of the comparator KP2 again consists of a demultiplexer DEM2 with a counter ZL2, a memory SP2 and a register REG2. The counter ZL2 and the memory SP2 are loaded to reduce the computing time from the programmable read-only memory module PROM AN with an approximate starting value, so that only the remaining low-order bits of the value z_A must be calculated by recursive iteration. The value z taken off at the output of the memory SP2 is offered for summation in the adders AD1, AD2 via the feedback.

0019Here too, a sequence control ABS2 controls the sequence of steps of the working process.

0020In the embodiment shown in FIG 3, the implementation of the simplified equation<maths id="math0022" num=""><img file="EP0218971A2_D0022.tif" /></maths>serves, the structure of the circuit and the sequence of the individual calculation steps largely corresponds to the embodiment of FIG 1. The squaring of the independent variables x, and x₂ takes place in the programmable fixed memory PROM <maths id="math0023" num=""><img file="EP0218971A2_D0023.tif" /></maths>, PROM <maths id="math0024" num=""><img file="EP0218971A2_D0024.tif" /></maths> at the input of the circuit. The arithmetic unit consists of an adder AD3. In the multiplier MUP2, the dependent variables are squared. The output values ​​of the multiplier MUP2 and the adder AD3 are passed to the comparator KP3 to form a comparison result. As in the exemplary embodiment according to FIG. 2, the two independent variables form an approximate initial value in a read-only memory module PROM AW, which in turn is fed to the counter ZL3 and the memory SP3 and enables the computing time of the recursive iteration circuit to be reduced.

0021The exemplary embodiment according to FIG. 4 enables an effort-optimized solution of the equation<maths id="math0025" num=""><img file="EP0218971A2_D0025.tif" /></maths>

0022The digital components for arithmetic processing of the equation consist of a multiplexer MUX and a downstream multiplier accumulator MAC. At three inputs of the multiplexer MUX, the two independent variables x, and x, and the value z are fed via the feedback of the recursion loop. At the beginning of the arithmetic operation, the independent variable x is switched by the multiplexer MUX to the multiplier-accumulator MAC, which calculates the value xf and stores it internally in the accumulator. After switching the multiplexer MUX to x₂ the multiplier accumulator MAC calculates the corresponding value <maths id="math0026" num=""><img file="EP0218971A2_D0026.tif" /></maths> and add the two squared values <maths id="math0027" num=""><img file="EP0218971A2_D0027.tif" /></maths> and <maths id="math0028" num=""><img file="EP0218971A2_D0028.tif" /></maths>. The result is stored in a register REG. In a further computing step, the multiplexer MUX switches the feedback branch to the multiplier accumulator MAC, which, for example, stores the value stored in the memory SP4_A squared and fed to a comparator KP. The following arithmetic operations involving the iteration circuit with a demultiplexer DEM4 and an associated counter ZL4, the memory SP4 and a result register REG5 are similar to the steps described in the exemplary embodiment according to FIG. 1 for solving the general equation, with the difference that the one stored in the memory SP4 value_ZA is fed to the comparator KP4 via the multiplexer MUX and the multiplier-accumulator MAC.

Reference list

0023<tables id="tabl0001" num="0001"><img file="EP0218971A2_D0029.tif" /></tables>