Method of facilitating multiplication of floating-point numbers represented in residue number system

FIELD: information technology.

SUBSTANCE: remainder on base pi of a multiplicant is concurrently recorded in matrix memory elements of the i-th multiplier; the number of units bi in each column of the i-th matrix is concurrently counted; the binary number b1 is shifted by one bit to the right and summed with number b2; the obtained sum bs2 is shifted by one bit to the right and summed with number b3. Similarly, the obtained sums are shifted and summed with subsequent numbers to obtain a sum bs2*m-1, wherein the least significant bit of the number b1 is the first multiplication bit s1, the least significant bit of each obtained sum bsi is the i-th multiplication bit. The binary number bs2*m-1 is shifted, the least significant bit of the obtained number is the (2*m)-th bit of the determined product s2*m. If si is greater than pi, the obtained product si is corrected by successive subtraction of the base pi from si until si is less than pi, otherwise correction is not performed; powers of multipliers are simultaneously summed up and the resultant sum is the power of the determined product.

EFFECT: faster computation.

2 dwg

 

The invention relates to computing and is designed to build high-speed parallel-pipelined multipliers processing arrays positive floating-point numbers in the system of residual classes (JUICE).

The multiplication operation (hereinafter multiplication) in the JUICE is done in parallel on several grounds pitheir number n is determined by the range R of number representation: P=p1*p2*...*pnwhere * is the multiplication sign. Representation of a number in the JUICE provides the least non-negative residues Andisystem coprime bases pi(i∈[1, n]).

A real number in the system of residual classes represent positional order and the mantissa consists of a set of residues on the grounds pi.

Well-known iterative method for multiplying integers m-bit floating-point numbers, which is applicable to numbers presented in positional notation, and in the system of residual classes. In this way the multiplication is reduced to a sequence of plies stacked, which are executed sequentially. When shifts multiplier vacated bits are filled with zeros. If the first bit of m-bit multiplier is equal to one, then the rst term is mnimum, otherwise the rst term is equal to zero. If the second banaitis equal to one, the second summand is mnimum that is shifted by one digit to the left, otherwise the second term is zero. To the sum of the first and second components of the multiplicand is added, shifted by two digits to the left, if the second bit of the multiplier is equal to one, otherwise the added zero. Then to the resulting amount is added to the multiplicand, shifted by three digits to the left, if the third bit of the multiplier is equal to one, otherwise the added zero. And so on until the k-th digit of the multiplier, the accumulated amount of the multiplicand is added, shifted by k positions to the left, if the k-th bit of the multiplier is equal to one, otherwise the added zero. And so on up to m-th digit of the multiplier, the accumulated amount of the multiplicand is added, shifted by m bits to the left, if the m-th bit of the multiplier is equal to one, otherwise the added zero. In the end, the cumulative sum is the desired product of factors. The disadvantage of this method is that, first, when the iterative method of multiplication is m-1 operations totals, and taking into account the sequential method transfers the most significant bit number of cycles summation is equal to (m-1)*2*m. Secondly, the process of forming the sum is a serial process.

The technical result from the use of the proposed method organization multiplication of floating point numbers represented in the system of residual classes is, is to increase the computation speed due to the replacement of a series of m-1 arithmetic operations of addition 2*(m-1) in parallel executable operations of counting the number of single bit in the bit slices are generated from bits mnimogo. This operation is performed in parallel for all residues on the bases of the system of residual classes, forming cofactors. Based on the analysis and modification of the obtained values of the number of units in all bit slices is the formation of values in the binary number, which is the value of the required works. As a result, the number of clock cycles necessary for the formation of the value of the sum of an integer array of binary numbers - work, will be equal to (log2m)*2*m clock cycles. Thus, the proposed method ensures the operation of forming works faster-known iterative method in ((m-1)*2*m)/((log2m)*2*m)=(m-1)/log2m times, for example, when m=64 calculations will be performed 8 times faster.

Description of device: the technique of multiplying the binary floating-point numbers represented in the system of residual classes on the grounds p1p2, ..., pk, ..., pnis that in the i-th multiplier, where i∈[1,n]containing: 2*m-1 unit-bit counters, 2*m-1 two adders, 2*m-1 shift registers and one is a matrix in the memory elements, the dimension of which is equal to (2*m-1) columns and m rows, where m is the bit width of the i-th base of the system of residual classes, is parallel to the account balance on the basis of pimnimogo in the memory elements of the matrix i-th multiplier, each i-th binary positional residue on the basis of pican be represented as a sequence of bits Ai(am,am-1,...,a2,a1), where m is the bit width of the remainder, i∈[1, n].

Is parallel to the account balance on the basis of pimnimogo in the cells of the matrix in the memory elements. In cells 1 through m of the first row of the matrix is written m-bit balance on the basis of pimnimogo in the case when the first digit of the multiplier is equal to one, otherwise zeros are written.

In cell 2 through m+1 the second row of the matrix is written m-bit balance on the basis of pimnimogo in the case where the second digit of the multiplier is equal to one, otherwise zeros are written.

And so on, in a cell with k (m+k-1) k-th row of the matrix is written m-bit balance on the basis of pimnimogo in the case when the k-th bit of the multiplier is equal to one, otherwise zeros are written.

And so on, in cells m (2*m-1) second row of the matrix is written m-bit balance on the basis of pimnimogo in the case when the m-th bit of the multiplier is equal to one, otherwise the recording is by zeros; in the other cells of the matrix are written with zeros.

In General, the placement mnimogo in the cells of the matrix in the memory elements is as follows:

Then made a parallel count of the number of units in 2*m-1 binary vectors which are the columns of the above matrix. The result is 2*m-1 binary numbers bj- values the number of units in the respective m-bit vectors, where j∈[1,2*m-1].

In parallel, counting the number of units in (2*m-1) columns of the matrix is formed (2*m-1) binary numbers - the number of units in the respective m-bit columns of the matrix, and the first binary number b1- the value of the number of units in the first m-bit column of the matrix, the second binary number b2- the value of the number of units in the second m-bit column of the matrix, ..., k-e binary number bk- the value of the number of units in k-ohms m-bit column of the matrix, ..., (2*m-1)-th binary number b2*m-1- the value of the number of units in (2*m-1)-th m-bit column of the matrix.

The low-order number b1is the first category of s1works m-bit residues on the basis of p1the original numbers. You then shift the binary number b1on one digit to the right, then the result is summed with the Chi is scrap b 2where the least significant bit of the received sumthe second category of s2works m-bit residues on the basis of pithe original numbers.

You then shift the binary numberon one digit to the right, then the result is summed with the number of b3Junior category of the amount receivedis the third category of s3works m-bit residues on the basis of pithe original numbers. And further calculations proceed in a similar way to calculate the sumJunior category which is the k-th category of skworks m-bit residues on the basis of pithe original numbers.

You then shift the binary numberon one digit to the right, then the result is summed with the number of bk+1Junior category of the amount receivedis (k+1)-th digit of sk+1works m-bit residues on the basis of pithe original numbers. And further calculations proceed in a similar way to calculate the sumJunior category which is (2*m-1)-th digit of s2*m-1works m-bit residues on the basis of pithe original numbers.

Then you shift DVO is knogo number , least significant bit of the result is (2*m)-th digit of the original text s2*m.

This will result in the formed product of s1m-bit residues on the basis of pithe original number is a number composed of a sequence of bits: s2, s2, ..., sk, ..., s2*m.

If simore pi, correction obtained the works of sifor absences beyond reason by successive subtraction of the sithe Foundation of the piup until siwill not be less than piotherwise the correction is not performed.

Simultaneously with the calculation works m-bit residues are summed magnitude factors, the amount received is the order of the original text.

Example: multiply two binary trehmetsnyh (m=3) operand: the multiplicand a1=111, a multiplier and2=101 on the basis of p=10011. Write them in the form of a matrix of dimension m=3 rows and 2*m-1=5 columns, cells 1 and m=3 the first line is written to the multiplicand as the first bit mnimogo equal to one. In cell 2 through m+1=4 of the second row is written zeros as the second bit mnimogo equal to zero. In cells from 3 to 2*m-1=5, the third row is written to the multiplicand as the third bit of the multiplier is equal to one. In the other cells of the matrix are written with zeros:

Then simultaneously counts the number of ones in the columns of the matrix: b1=001, b2=001, b3=010, b4=001, b5=001. Since the least significant bit of b1equal to one, then bits of the s1=l.

The number of b1shifted by one digit to the right and the shiftadded to the number of b2=001. Sumits least significant bit is the second bit of the s2=1.

The number ofshifted by one digit to the right and the shiftadded to the number of b3=010. Sumits least significant bit is the third bit of the s3=0.

The number ofshifted by one digit to the right and the shiftadded to the number of b4=001. Sumits least significant bit is the fourth bit of the s4=0.

The number ofshifted by one digit to the right and the shiftadded to the number of b5=001. Sumits least significant bit is the fifth bit of the s5=0. The number ofshifted by one digit to the right and the least significant bit of the shiftis the sixth bit of the m of the s 6=1. Finally, the product of the operands s=(s6,s5,s4,s3,s2,s1)=100011. Since s>p, the necessary correction of the work, which consists in subtracting from s base p, i.e. s'=s-p=100011-10011=10000, since s'<p, then s' is the desired product of the source operands modulo R.

If taken during the addition of a pair of m-bit residue m of cycles of operation of the device, the time calculation works in the device on the basis of the described method is equal to R*2*m clock cycles, where p is the number of clock cycles necessary for counting bits in a binary vector, with p=log2m, while the time multiplying the iterative method is equal to 2*(m-1)*m clock cycles. Thus, the operating speed of the device on the basis of the described method (m-1)/log2m times higher than the operating speed of the device on the basis of the well-known iterative method for multiplication.

An example of building devices based on the organization's way of multiplying the floating-point numbers represented in the system of residual classes, can serve as its programming on programmable logic integrated circuits (FPGA).

Figure 1 presents a variant of the block diagram of a device that implements the calculation works balances in the General form, where: 1 - meter single-bit binary vectors; 2 - p-two-bit adder, where p=log2 n; 3 - shear p-bit register; a1-a2*m-1- m-bit information input schema; s1-s2*m-1- one-bit information output circuit; b1-b2*m-1- p-bit outputs of the counters 1;- bit outputs of the adders 2.

Figure 2 shows a variant of the structural scheme of the matrix in the memory elements for trenutnega balance (m=3), where: 1 - the logical element And; 2 - information trigger with one data input, one trigger input and one output data; 3 - information input trigger; 4 - input synchronization trigger; 5 - information trigger output; x1x2x3inputs scheme, which served the remainder mnimogo on Trenutna ground; y1,y2, y3inputs scheme, which served the remainder of the multiplier on Trenutna ground; a1,1÷a1,5, a2,1÷athe 2.5and3,1÷R3,5- the outputs of the matrix in the memory elements.

The technique of multiplying the binary floating-point numbers represented in the system of residual classes on the grounds p1, R2, ..., pk, ..., pnconsists in the fact that in the i-th multiplier, where i∈*[1, n]containing: 2*m-1 unit-bit counters, 2*m-1 two adders, 2*m-1 shift registers and one matrix on the memory elements, the dimension of which is equal to (2*m-1) St is vcov and m rows, where m is the bit width of the i-th base of the system of residual classes, is parallel to the account balance on the basis of pimnimogo in the memory elements of the matrix i-th multiplier, and in cells 1 through m of the first row of the matrix is written m-bit balance on the basis of pimnimogo in the case when the first digit of the multiplier is equal to one, otherwise, zeros are written into the cells 2 through m+1 the second row of the matrix is written m-bit balance on the basis of pimnimogo in the case where the second digit of the multiplier is equal to one, otherwise it writes zeros, ..., in cells with k (m+k-1) k-th row of the matrix is written m-bit balance on the basis of pimnimogo in the case when the k-th bit of the multiplier is equal to one, otherwise it writes zeros, ..., in cells m (2*m-1) m-th row of the matrix is written m-bit balance on the basis of pimnimogo in the case when the n-th digit of the multiplier is equal to one, otherwise it writes zeros in all remaining cells of the matrix are written with zeros, and then executed simultaneously counting the number of units using the unit-bit counter in the first column of the first matrix, the second column of the i-th, ..., k-th column of the i-th, ..., (2*m-1)-th column of the i-th matrix; as a result, the parallel counting the number of units in (2*m-1) columns of the i-th matrix is formed (2*m-1) binary numbers - values to the number of units in the respective m-bit columns of the first matrix, and the first binary number b1- the value of the number of units in the first m-bit column of the first matrix, the second binary number b2- the value of the number of units in the second m-bit column of the i-th matrix, ..., k-th binary number bk- the value of the number of units in k-m m-bit column of the i-th matrix, ..., m-th binary number b2*m-1- the value of the number of units in (2*m-1)-m m-bit column of the i-th matrix; the low-order number b1is the first category of s1works m-bit residues on the basis of pithe original numbers; then you shift the binary number b1on one digit to the right, then the result is summed with the number of b2where the least significant bit of the received sumthe second category of s2works m-bit residues on the basis of pithe original numbers; then you shift the binary numberon one digit to the right, then the result is summed with the number of b3Junior category of the amount receivedis the third category of s3works m-bit residues on the basis of pithe original numbers; and so on calculations proceed in a similar way to calculate the sumJunior category which is the k-th s kworks m-bit residues on the basis of pithe original numbers; then you shift the binary numberone digit to the right, then the result is summed with the number of bk+1Junior category of the amount receivedis (k+1)-th digit of sk+1works m-bit residues on the basis of pithe original numbers; and so on calculations proceed in a similar way to calculate the sumJunior category which is (2*m-1)-th digit of s2*m-1works m-bit residues on the basis of pithe original numbers; then you shift the binary number, least significant bit of the result is (2*m)-th digit of the original text s2*m; this will result in the formed product of sim-bit residues on the basis of pithe original number is a number composed of a sequence of bits: s1, s2, ..., sk, ..., s2*m; if simore pi, correction obtained the works of sifor absences beyond reason by successive subtraction of the sithe Foundation of the piup until siwill not be less than piotherwise the correction is not made simultaneously with the calculation made in the Denia m-bit residues are summed magnitude of cofactors, the amount received is the order of the original text.



 

Same patents:

FIELD: information technology.

SUBSTANCE: invention can be used in digital computers as well as digital signal processing devices and cryptographic applications. The device has logic elements NOT, AND, OR.

EFFECT: high speed of operation of the adder due to parallel execution of the modulo addition operation.

1 dwg, 1 tbl

FIELD: information technology.

SUBSTANCE: apparatus has input registers, projection generating circuits, memory units, adders, an analysis circuit, AND logic elements, a flip-flop and a projection counter.

EFFECT: high speed of determining functional characteristics and cutting hardware costs.

1 dwg

FIELD: information technology.

SUBSTANCE: homogeneous computing environment cell has an XOR element, an AND element and two flip-flops.

EFFECT: faster operation and reliability.

3 cl, 6 dwg, 3 tbl

FIELD: information technology.

SUBSTANCE: device for generating remainder on arbitrary modulus of a number has first and second registers, a group of AND elements, a unit of half-adders and a delay element, where the device also includes (K-1) half-adders, to whose second data inputs a modulus code is transmitted, and a number code "1" is transmitted to the first data input of the first half-adder and the second data input of the group of AND elements, the output of the i-th half-adder is connected to the second data input of the group of AND elements and with shift of one bit towards the most significant bits to the first data input of the i+1 half-adder, where i=1,…,K-2, the K-1 output of the half-adder is connected to the second data input of the group of AND elements.

EFFECT: cutting the size of equipment.

2 dwg

Doubler by module // 2445681

FIELD: information technologies.

SUBSTANCE: invention may be used in digital computing devices, and also in devices to generate elements of end fields and in cryptographic applications. The device comprises summators, multipliers, inverters and multiplexors.

EFFECT: expanded range of input number values.

1 dwg

FIELD: information technologies.

SUBSTANCE: device comprises n+1 single-digit parallel summators by module, where n - number of digits of summation numbers, at the same time each single-digit summator by module comprises two single-digit summators, two logical AND elements, a logical OR element, two logical NOT elements.

EFFECT: expansion of functional capabilities of the device by introduction of a summation operation by module.

2 cl, 2 dwg, 1 tbl

FIELD: information technology.

SUBSTANCE: apparatus for generating remainder for given modulo contains T units for generating partial remainders with a data input on n bits, an input for primary remainders on (n-p-1)·(p+1) bits, an initialisation input, a synchronous input and output on (p+q) bits, respectively, two parallel (p+2)- and (p+1)-bit registers with a synchronous input, a data input and output, respectively, a multiplexer with two data inputs, a control input and output, a comparator with two inputs and an output, a subtractor with minuend and subtrahend inputs, as well as a difference output.

EFFECT: high efficiency of generating a remainder on a given modulo for a stream of numbers by piping the process of calculating partial and resultant remainders based on precalculation of values of primary remainders.

2 dwg, 1 tbl, 2 cl

FIELD: information technology.

SUBSTANCE: apparatus has an input register, a switch, a multiplexer, a correction circuit, two half adders, two registers for recording intermediate results of modulus, 2 addition and three output registers.

EFFECT: high bitness of binary codes converted in residue number systems.

1 dwg

FIELD: information technologies.

SUBSTANCE: device comprises inlet registers of dividend and divisor, unit of division with zero balance, unit for conversion of residual code into code of generalised position system, read-only memory, unit of subtractor, multiplication unit, prohibition unit, units of comparison, key, summator.

EFFECT: expanded functional capabilities of device since division operation is performed at arbitrary values of dividend and divisor, and reduced volume of equipment.

1 dwg, 1 tbl

FIELD: information technology.

SUBSTANCE: invention relates to modular neurocomputer apparatus and is designed for detecting errors in code structures of the position-independent code of a polynomial system of residue classes (PSRC) presented in augmented Galois fields GF(2V). The device has a register, an interval polynomial calculation unit, a correcting adder, a spectral analysis unit which is a four-layer neural network. The first layer is designed for recording the interval polynomial which is presented in form of a binary code. The second layer is designed for calculating the first spectral components from control bases. The third layer is designed for inverting the obtained values. The fourth layer is designed fro calculating the correction value which is presented in a polynomial system of residue classes.

EFFECT: reduced hardware expenses.

2 dwg, 10 tbl

Σ(↓cdΣ) for subsequent logical decoding f1(cd↓) and generation of resulting sum in format ±[sΣ]f(2n) -"additional code" and functional structure for its realisation (versions of russian logics)" target="_blank">

FIELD: information technologies.

SUBSTANCE: invention may be used to build arithmetic devices for performance of arithmetic operations of multiplication of multiplicand arguments ±[mj]f(2n) and multiplier arguments ±[ni]f(2n) - "Additional code". In one of versions the structure is realised using logical elements CFU, OR-CFU.

EFFECT: increased efficiency of a process of transformation of arguments of partial products.

4 cl

Σ(Σ) for subsequent accumulative summation in adder ±f1(Σ) and functional design for realisation thereof (versions of russian logic)" target="_blank">

FIELD: information technology.

SUBSTANCE: invention can be used when building arithmetic devices for performing arithmetic operations of multiplying arguments of multipliers. In one version, the design is realised using AND logic elements.

EFFECT: faster process of converting arguments when generating resultant sum of partial products.

8 cl

FIELD: information technology.

SUBSTANCE: apparatus has a tetrad shift register, a second multiplier register, a partial product unit, a product carry unit, a first carry adder unit, an adder unit, a sum carry flip flop unit, a second carry adder unit, a result register in "1 out of 4" code, a result carry unit, a control unit, n-bit quaternary inputs in "1 out of 4" code of the first and second multipliers, where n is the number of quaternary bits of multipliers, a shift input and error feature outputs.

EFFECT: faster operation of the device.

7 dwg, 3 tbl

FIELD: physics.

SUBSTANCE: invention relates to computation and can be used to construct computing means in data processing and control systems. The device has a multiplicand register, a multiplier register, an adder, a result register and a "1-4" control circuit, a control device, a register for storing the result of multiplying the multiplicand by two, a register for storing the result of multiplying the multiplicand by three and two data transmission lines.

EFFECT: faster operation and higher reliability of the processed information, fewer hardware components used and low power consumption.

2 cl, 2 dwg

Doubler by module // 2445681

FIELD: information technologies.

SUBSTANCE: invention may be used in digital computing devices, and also in devices to generate elements of end fields and in cryptographic applications. The device comprises summators, multipliers, inverters and multiplexors.

EFFECT: expanded range of input number values.

1 dwg

FIELD: information technologies.

SUBSTANCE: multiplier is made in the form of two channels equivalent in structure to generate an intermediate sum of junior and senior digits, every of which contains logical AND functions to generate arguments of partial products, and summators.

EFFECT: simplified structure and increased efficiency of a parallel-series multiplier.

FIELD: information technology.

SUBSTANCE: input vector (x) is received during operation of the encoder. A first multi-precision operand (Ψ'k ) is generated based on the input vector to be encoded. A mantissa operand and an exponent operand are generated, both of which are representative of a second multi-precision operand which is based on the input vector to be encoded. Further, a part of Ψ'k is selected to be modified based on the exponent operand. A part of Ψ'k is modified based on the mantissa operand to produce a modified multi-precision operand (Ψ'k+1). Finally, a multi-precision codeword is generated based on the modified multi-precision operand for use in a corresponding decoder.

EFFECT: minimising computational complexity.

9 cl, 8 dwg, 3 tbl

FIELD: information technologies.

SUBSTANCE: for every two conventionally "i" and "i+1" arguments of an analogue signal of a multiplier and analogue signals of positional structure of multiplier arguments, structures of analogue signals arguments of partial products are formed by linear logical structures AND1, AND2; the position structure of analogue signals of provisional sum is formed by means of a linear logical structure AND3 and is combined by means of a linear logical function AND1 for subsequent logical summation in the functional structure of a summator with a structure of arguments of analogue signals of intermediate sums of high-order digits, which is formed by means of combination by a linear logical function OR2 of intermediate sums of conventionally "i+2" and "i+3" arguments of an analogue signal of a multiplier and analogue signals of a positional structure of multiplicand arguments formed by means of linear logical structures AND4, AND5, AND6.

EFFECT: higher efficiency of multiplication operations performance.

FIELD: computers.

SUBSTANCE: device has data input block, multiplied part register, multiplying part register, adder block, block for analyzing multiplying part digit, storage block, control block, threshold elements, neurons. Multiplication operation is performed by analyzing higher digits of multiplying part with displacement of multiplied part to the right. Combination blocks provide for parallel, digit-wise production of multiplication result digits.

EFFECT: simplified construction and operation.

10 dwg

Up!