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

FIELD: information technology.

SUBSTANCE: method comprises steps of: concurrently writing the remainder on base p1 of a multiplicand in memory elements; concurrently counting the number of units bi in each column of the i-th matrix; shifting the binary number b1 one bit to the right; summing with a number b2; shifting the obtained sum b 2 s one bit to the right and summing with a number b3. Similarly, the obtained sums are shifted and summed with subsequent numbers to obtain a sum b 2 * m 1 s , wherein the least significant bit of the number b1 is the first multiplication bit s1, the least significant bit of each obtained sum b i s is the i-th multiplication bit. The binary number b 2 * m 1 s is shifted; the least significant bit of the obtained number is the (2*m)-th bit of the determined product s2*m. If s is greater than p1, the obtained product s is corrected by successive subtraction of the base p1 from s until s is less than p1, otherwise correction is not performed; similarly, products of m-bit residues on the rest of the bases are calculated and corrected; the 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 is performed in parallel on several grounds pitheir number n is determined by the range of P representations of numbers: P=p1*p2*...*pn. Representation of a number in the JUICE provides the least nonnegative residues of Aisystem coprime bases pi(i∈[1,n]).

The 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 multiplication of integers, floating-point, 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 bit of the multiplier is equal to one, then the second term is mnimum, shifted to od the n discharge to the left, otherwise, the second term is zero. To the sum of the first and the second term is added to the multiplicand, 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 n 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 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 is the number of clock 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 organization's way of multiplying the floating-point numbers represented in the system of residual classes, is to increase the computation speed due to the replacement of a series of m-1 arithmetic operations is adding 2*(m-1) in parallel executable operations of counting the number of single bit in the bit slices, formed from the digits 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 work unit: 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 p1mnimogo in the cells of the matrix in the memory elements, the matrix size is (2*m-1) columns and m rows, where m is the bit width of the first Foundation of the system of residual classes. In cells 1 through m of the first row of the matrix is written m-bit balance based on the Yu p imnimogo 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 pi mnimogo 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 p1mnimogo 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 bitwise balance on the basis of p1mnimogo in the case when the m-th bit of the multiplier is equal to one, otherwise zeros are written.

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:

(0,0,...,a1,m,a1,m-1,...,a1,10,0,...,a2,m,a2,m-1,...,a2,1,00,0,..., a3,m,a3,m-1,...,a3,1,0,0...0,am-1,m,am-1,m-1,...,am-1,1,0,...,0am,m,am,m-1,...,am,1,0,...,0)

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 bi- values the number of units in the respective m-bit vectors, where i∈[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 a number is the number of units in the second m-bit column of the matrix, the k-th binary number bk- the value of the number of units in k-ohms m-bit column of the matrix, ..., m-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 number of b2where the least significant bit of the received amountb2sthe second category of s2works m-bit residues on the basis of p1the original numbers;

you then shift the binary numberb2son one digit to the right, then the result is summed with the number of b3Junior category of the amount receivedb3sis the third category of s3works m-bit residues on the basis of p1the original numbers.

And so on calculations proceed in a similar way to calculate the amount ofbks Junior category which is the k-th category of skworks m-bit residues on the basis of p1the original numbers.

You then shift the binary numberbksone digit to the right, then the result is summed with the number of bk+1Junior category of the amount receivedbk+1sis (k+1)-th digit of sk+1works m-bit residues on the basis of p1the original numbers.

And so on calculations proceed in a similar way to calculate the amount ofb2*m-1sJunior category which is (2*m-1)-th digit of s2*m-1works m-bit residues on the basis of p1the original numbers.

You shift the binary numberb2*m-1son one digit to the right, and the resulting number is the value of the high-order bit of the original text s2*m.

In the end, will be formed is produced in the conducting m-bit residues on the basis of p 1the initial numbers - the number of s1, s2, ..., sk, ..., s2*m.

Simultaneously with the calculation works m-bit residue of the initial numbers on the basis of p1similar remarks apply works m-bit residue of the initial numbers on the grounds p2p3, ..., pk, ..., pn.

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

Example: multiply two binary trehmetsnyh (m=3) operand: the multiplicand a1=111, a multiplier, a2=101 on the basis of p=10001. 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:

(001110000011100)

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

The number of b1shifted by one digit to the right and the shift ofb1'=000added to the number of b2=001. The sum ofb2s=001its least significant bit is the second bit of the s2=1.

The number ofb2sshifted by one digit to the right and the shift ofb2s'=000added to the number of b3=010. The sum ofb3s=010its least significant bit is the third bit of the s3=0.

The number ofb3sshifted by one digit to the right and the shift ofb3s'=001added to the number of b4=001. With the MMA b4s=010its least significant bit is the fourth bit of the s4=0.

The number ofb4sshifted by one digit to the right and the shift ofb4s'=001added to the number of b5=001. The sum ofb5s=010its least significant bit is the fifth bit of the s5=0.

The number ofb5sshifted by one digit to the right and the least significant bit of the shiftb5s'=001is the sixth bit of the s6=1. As a result, the operands of the product 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-10001=10010, since s'<p, then s' is the desired product of the source operands modulo p.

what if you take the time adding 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=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 of the work rests on the base in the General form, where 1 - meter single-bit binary vectors, 2 - R-two-bit adder, where p=log2n, 3 - shear p-bit register, a1-an- m-bit information input schema s1-sm- one-bit information output circuit, b1-bmp-bit outputs of the counters 1,b1s-bms- (p+1)-bit outputs of the adders 2.

Figure 2 shows a variant of the block diagram of matrix elements PA is ATI for trenutnega balance (m=3), where 1 is 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 output trigger, x1-x3inputs scheme, which served the remainder mnimogo on Trenutna base, y1-y3inputs scheme, which served the remainder of the multiplier on Trenutna the base, ai,jthe 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 p1p2, ..., pk, ..., pnconsists in the fact that multiplying device:
is parallel to the account balance on the basis of p1mnimogo in the cells of the matrix in the memory elements, the matrix size is (2·m-1) columns and m rows, where m is the bit width of the first Foundation of the system of residual classes, and
in cells 1 through m of the first row of the matrix is written m-bit balance on the basis of p1mnimogo in the case when the first digit of the multiplier is equal to one, otherwise it writes zeros,
in cell 2 through m+1 the second row of the matrix is written m-bit balance on the basis of p1mnimogo in the case where the second digit of the multiplier is equal to one, otherwise it writes zeros, which,
in cells with k (m+k-1) k-th row of the matrix is written m-bit balance on the basis of p1mnimogo 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 p1mnimogo in the case when the n-th digit of the multiplier is equal to one, otherwise it writes zeros,
in the other cells of the matrix are written with zeros,
then executed simultaneously counting the number of ones in the first column of the matrix, the second column of the matrix, ..., k-th column of the matrix, ..., (2·m-1)-th column of the matrix; the result of the 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-th binary number bk- the value of the number of units in k-m m-bit column of the 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 matrix;
the least significant digit of the numberb1is the first category ofs1works m-bit residues on the basis ofp1 the original numbers;
you then shift the binary numberb1on one digit to the right, then the result is summed with the number of b2where the least significant bit of the received amountb2sthe second category ofs2works m-bit residues on the basis ofp1the original numbers;
you then shift the binary numberb2son one digit to the right, then the result is summed with the number of b3Junior category of the amount receivedb3sis the third category ofs3works m-bit residues on the basis ofp1the original numbers;
and so on calculations proceed in a similar way to calculate the amount ofbksJunior category which is the k-th dischargeskworks m-bit residues on the basis ofp1the original numbers;
you then shift the binary numberbks on one digit to the right, then the result is summed with the numberbk+1,least significant bit of the received amountbk+1sis (k+1)-th dischargesk+1works m-bit residues on the basis ofp1the original numbers;
and so on calculations proceed in a similar way to calculate the amount ofb2m-1s,the least significant digit which is (2·m-1)-th digit of s2·m-1works m-bit residues on the basis ofp1the original numbers;
you then shift the binary numberb2m-1son one digit to the right, and the resulting number is the value of senior level search worksS2·m,
this will result in the formed product of the m-bit residues on the basis ofp1the initial numbers - the number of s1, s2, ..., sk, ..., S2·m;
in that case, ifsmorep1,correction the floor the military works by sfor absences beyond reason, by successive subtraction of thesthe Foundation of thep1up untilswill not be less thanp1,otherwise the correction is not made,
simultaneously with the calculation and correction of the works of m-bit residue of the initial numbers on the basis ofp1similarly evaluated and adjusted work m-bit residue of the initial numbers on the grounds p2p3, ..., pk, ..., pn;
simultaneously with the calculation works m-bit residues are summed orders somnogenic, the amount received is the order of the original text.



 

Same patents:

FIELD: information technology.

SUBSTANCE: device has an n-bit adder, an (n+1)-bit adder, a multiplexer and a register.

EFFECT: broader functional capabilities due to introduction of the modulo addition operation.

1 dwg

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

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: method includes stages, at which a divisor is recorded in parallel into matrix cells on memory elements, the first bit of the quotient becomes equal to the sum of module two of the least significant bit in the first column of the matrix and the first bit of the dividend, other bits of the quotient become equal to zero; the number of units b2 is counted in a vector equal to bit-by-bit logical multiplication of the appropriate bits of the second column of the matrix and bits of the quotient, at the same time the second bit of the quotient becomes equal to the sum of module two for the least significant bit b2 and the second bit of the dividend; similarly, the number of units bi is counted in a vector, which is equal to the bit-by-bit logical multiplication of the appropriate bits of the i column of the matrix and quotient bits, afterwards the sum ci of the vector bi and the vector bi-1 shifted by one bit to the right is calculated, at the same time the i bit of the quotient becomes equal to the sum of module two of the least significant bit ci and the i bit of the dividend, as a result the m-bit quotient of initial numbers will be generated.

EFFECT: increased speed of calculation.

2 dwg

FIELD: information technologies.

SUBSTANCE: device comprises a subblock of prediction of a sum of fractional parts, a counter of senior zeros of the sum of fractional parts, registers of fractional parts of numbers, input registers of number exponents, a counter of junior zeros of the summand fractional parts, a subblock of calculation of a shift of levelling and prediction of a shift of preliminary normalisation, a comparator of early loss of accuracy, a counter of junior zeros of a sum of fractional parts, a comparator of late loss of accuracy.

EFFECT: accelerated process of performance of a flow of independent commands of multiplication with accumulation with permitted exceptional situation of accuracy loss.

5 dwg, 1 tbl

Logic module // 2497181

FIELD: information technology.

SUBSTANCE: logic module has six closing switches and six opening switches.

EFFECT: enabling realisation of any three simple symmetric Boolean functions of three arguments - input binary signals or modulo 2 summation of the same three arguments.

1 dwg

FIELD: information technology.

SUBSTANCE: apparatus includes flip-flops, registers, ROM, subtractors, adders, multiplexers, shifters, a comparator unit, modulo two adders, AND and OR elements and a priority encoder.

EFFECT: high accuracy of stored results of interval computations in floating point format, while maintaining overall code length of the upper and lower boundaries of an arithmetic interval.

5 dwg

FIELD: information technology.

SUBSTANCE: apparatus includes an encoder, a decoder unit, ROM, shifters, subtractors, multiplexers, an adder, modulo two adders, an inverter, AND and OR elements.

EFFECT: high accuracy of stored results of interval computations in floating point format, while maintaining overall code length of the upper and lower boundaries of an arithmetic interval.

5 dwg

FIELD: information technologies.

SUBSTANCE: in one of versions the method includes parallel-serial processing of a signal in a block of triggers of an input register; in a matrix device; in a unit of logical elements, preferably logical elements "AND"; in a unit of triggers of an output register. At the same time the signal processing in the matrix device is performed in accordance with the geometric model of the signal processing, representing a combination of graphs that forms at least one right triangle, which is divided into three parts, with lines stretching from the tops of the triangle angles.

EFFECT: higher efficiency of signal processing with preservation of processing results validity.

29 cl, 5 dwg, 3 tbl

Logic processor // 2491613

FIELD: information technology.

SUBSTANCE: disclosed is a logic processor designed to execute eight simple symmetrical Boolean functions which depend on eight arguments - input binary signals, which can be used in digital computer systems as a code converting means, and also having nineteen computational cells (11,…,119), each having an OR element (2) and an AND element (3).

EFFECT: faster operation owing to faster execution of eight simple symmetrical Boolean functions which depend on eight arguments - input binary signals.

2 dwg

FIELD: information technology.

SUBSTANCE: system for adaptive prioritisation of antivirus scanning objects includes a rule setting device which sets rules for prioritising antivirus scanning objects, a rule database for storing prioritisation rules and providing rule data to a queuing device. The system also includes an analyser which determines parameters of antivirus scanning objects required for prioritisation and sends said parameters to the queuing device. The queuing device is designed to assign priority and a scanning method with defined parameters in accordance with set rules. The queuing device also constructs a queue in accordance with the assigned priorities and sends the queue to a malicious object detecting device. The malicious object detecting device performs antivirus scanning of the scanning queue in accordance with the scanning method assigned for each object and sends the scanning results to a scanning result analyser.

EFFECT: high speed of detecting the most common malicious objects.

5 cl, 6 dwg

FIELD: information technology.

SUBSTANCE: method for character string matching of a candidate character string with a plurality of character string records stored within a database involves identifying a set of reference character strings in the database. The reference character strings are identified using an optimised search for a set of dissimilar character strings. An n-gram representation of each of the reference character strings in the set of reference character strings is generated and an n-gram representation of the candidate character string is also generated. Further, similarity between n-gram representations of each of the reference character strings and the candidate character string is determined. The candidate character string in the database is indexed based on the determined similarities between the n-gram representation of the candidate character string and the reference character strings in the identified set.

EFFECT: high efficiency of obtaining approximate character string matching in a database without the need to calculate a similarity metric on the entire database.

20 cl, 10 dwg, 14 tbl

FIELD: information technology.

SUBSTANCE: device has memory units, adders, multiplexers, a remainder modulo calculating unit, a memory register, logic elements AND and NOR.

EFFECT: faster calculations.

4 dwg, 7 tbl

FIELD: peripheral devices.

SUBSTANCE: device has information input device, clock generator, connected to address counter with decoder, outputs of which are connected to inputs of recording device, inputs of which are connected to output of programming device, signal generator and multiplexers. Device for recording object sate is connected to output of decoder of cells address of device. Signal generator includes cells for recording checksum. First input of signals generator is connected to output of decoder of address of cells of checksum, second input - to output of recording device, first output - to first inputs of multiplexers, and second output - to first input of binary adder, by its output connected to third input of signal generator and checksum. Outputs of decoder of checksum cells address and decoder of object state recording device cells addresses are connected to second output of address counter, which is connected to second inputs of multiplexers. Recording device is programmable.

EFFECT: broader functional capabilities.

2 cl, 2 dwg

Up!