Device for comparing numbers presented in residue number system

FIELD: information technology.

SUBSTANCE: device includes input registers, sign determining circuits, number polarity shifting circuits, look-up tables (memory) for storing constants and an adder, an XOR element and a number sign analysis circuit.

EFFECT: faster operation of the device and cutting hardware costs.

3 dwg

 

The invention relates to computer technology and can be used in blocks comparison of modular numbers of computing systems operating in the system of residual classes.

The known device for comparing n-bit numbers. (A.S. NO. 675420, B. I. No. 27, 1979) consisting of triggers, logic elements, nodes, storage, registers, decoders, memory matrices and counter. However, this device has great complexity and functionally may not be used for comparison of modular numbers.

The closest to the technical nature of the claimed device is a device for comparing numbers (A.S. NO. 541164, BI No. 48, 1977.), containing critical matrix blocks analysis article coefficients algebraic comparison, the units of analysis article coefficients comparison module, block the formation of character and logical elements "or".

The disadvantages of this device is low speed and complexity.

The aim of the present invention is to increase the speed of comparing numbers and reducing hardware costs.

This objective is achieved in that in the device are input lookup tables (memory), the shift circuit polarity and the adder. Consider a new method of comparison of modular numbers, with high performance and low hardware for the clear equipment

To simplify the comparison process is modular numbers consider an approximate method that allows absolutely correctly implement the basic classes of decision procedures: an analysis of the presence of a particular value in a particular category; check equality (inequality) of the two values; a comparison of the two values (more, less), which provide the solution of the main tasks that occur when a hardware or software implementation of real processes.

The essence of the approximate method comparison of modular numbers based on the use of relative values of the original number to the full range of Chinese theorem on residues that binds positional number A with its representation in the residuals (α1α2, ..., αn), where αithe smallest non-negative deductions number, relative to the modules of the system of residual classes p1p2, ..., pnthe following expression

wherepimodules JUICE,is the multiplicative inverse of Pirelative to piand.

If (1) divided by a constant P, then we obtain an approximate value

where constants of the selected system, and αi- the digits that can be represented in the JUICE, while the value of each amount will be in the interval [0, 1). The end result amount is determined after summation and drop the integer part to preserve the fractional part of the sum. The fractional part can be written as Amod1, because. The number of digits in the fractional part of the number is determined by the maximum possible difference between adjacent numbers. If necessary, an accurate comparison, you need to calculate the value of (2), which is equivalent to the conversion of JUICE in positional notation. To solve problems of basic decision-making procedures it is enough to know about the values of the integers A and B with respect to the dynamic range of P, which is easy enough, but correctly identifies the ratio A=B, A>B or A<B.

Example 1. Let the given system bases p1=2, p2=3, p3=5, p4=7, volume range P=2·3·5·7=210. Suppose that in a given JUICE will contain only positive numbers. ,,,. Compare two numbers A1=25 and2=30, presented in Soko grounds p 1p2p3p4then there is A1=(1,1,0,4), A2=(0,0,0,2). For this, you will find constants.

(2) we get

Asthen A2>A1there is a 30>25.

Consider the case where the operating range is divided into two intervalsare positive numbers, and- negative numbers. In traditional computers, the determination of absolute values of two numbers A1and A2is performed by calculating A1-A2and determine the sign of the difference. In the system of residual classes is not enough to determine the sign byas A1-A2can go beyond the range ofand this will lead to incorrect results.

Example 2. Option definitions are incorrect comparison based on the definition of the token.

Let, obviously, A1>A2. On the basis of (2) we defineand. The Foundation of the JUICE will choose the same as in the first example. Then A1=(0,1,0,0) and A2=(0,2,0,0) - additional code is a negative number. Find,.

The number of A2included in the negative range, that is,.

Therefore the comparison will lead to incorrect results (A1<A2.

To determine the correct comparison should check the signs of a1and A2and then the comparison algorithm will be:

1. To determine the signs of a1and A2.

2. If A1and A2without signs, the positive sign of the difference between the relative values mean more.

3. If A1and A2have the same sign, then checked.

4. If A1and A2have different signs, thenwhen A1<A2andwhen A1>A2.

Thus, comparison of signed numbers requires a preliminary analysis of characters to compare numbers.

It is known that additional coding is Odom, the negative part of the dynamic range is at the upper limit of the full range. Positive number of additional range are displayed on the area offor odd P and the area ofeven when P. Mapping the dynamic range of the corresponding area for the redundant code JUICE is shown in figure 1.

This circumstance can lead to the error of the comparison, since negative numbers are in the upper part of the full range and all negative numbers will give errors, which is not true due to the diversity of the dynamic range.

To overcome this difficulty it is necessary to produce a negative shift by residual rotation of the ring in the position indicated in figure 2. The dashed line shows the area that is moved to the beginning of the range.

The result is a negative number will be displayed in the initial part of the dynamic range.

Shown in figure 2, the rotation is called the offset polarity and can be done by adding before the comparison of modular numbers constantsfor odd P orfor even P for each A∈[0, P).

If the shift of polarity within the JUICE is a simple balance, which is determined by the formulain which αicdenotes the residual digits after the shift polarity.

Example 3. To compare modular integers of different signs A1and-A2. The system bases the JUICE is the same as in example 1: p1=2, p2=3, p3=5, p4=7.

Let the number A1=17=(1,2,2,3), A2=-19=(1,1,4,5). Then additional code of A2=(p1-1,p2-1,p3-4.p4-5)=(1,2,1,2). You want to compare numbers A1and A2.

Checking the sign of A1. To determine the sign of A1compare it with the constant of. Then the relative magnitude of numbers A1in relation to the value of the number K is defined as

.

View constants. Find the. Here. The difference is positive, i.e. the number oftherefore, the a1included in the first interval and is positive.

Checking the sign of A2is similar:.. The differential is negative and the number of A 2included in the second interval, it is obvious that it is negative. For correct comparison of the numbers A1and A2you must hold the shift polarity of the integers A1and A2as A2is negative. After shifting the receivedand.

We define the relative value ofand.

,

.

Find the difference of relative values, then- the difference is positive. Hence A1>A2.

Discusses methods to determine such positional characteristics of modular code, such as: the definition of a symbol numbers and the comparison of the numbers showed, in contrast to the known, the simplicity of calculation, because their implementation is not used, the calculation of the coefficients of the round, which requires large hardware and time costs. For this reason, this method is of particular importance and is one of the best decisions at the present time. These operations are essential for machine modular arithmetic and their use can provide significant benefits not only own the assets, in which the bulk of computing falls on the exact multiplication, exponentiation of large numbers in combination with addition and subtraction, but also in which often you will need to compare and determine the sign of the number. It is known that coding theorem Szabo says that there is no better method of determining positional characteristics that do not utilize their uniqueness than translating numbers from the JUICE in the round, because the magnitude of the numbers in modular representation depend essentially on all residue numbers. However, studies have been conducted to determine the approximate characteristics that solve the problem of formation of structures comparison, do not meet the approval of this theorem clogs. Thus we can conclude that theorem Szabo only works with exact methods.

The modular scheme comparison, based on the principles of the use of relative values is shown in figure 3 and includes: an input registers 1, 9 for storing a number corresponding to A and B which are received by the tire 15 and 16; the scheme of determining the signs of the numbers A and B, respectively, 2 and 8, the shift circuit polarity 3, 7, respectively, A and B, lookup tables 5, 7, the contents of the tables to store the product of constants and discharges JUICEand accordingly, table 5-1, 5-3, 5-n for integers A and 6-1, 6-2, 6-n for integers B, the adder 10: logical element exclusive-or 4; circuit analysis mark 11 exits: respectively, A=B 12, A>13 B, A<B 14. The operation of the device for comparison of modular numbers as follows.

The input registers 1, 9 buses 15, 16, respectively, receives the original numbers A and B represented in the JUICE that you wish to compare. The outputs of the registers are connected with 2, 3 and 7, 8, respectively, to determine the sign of the integers A and B and shift the polarity of the numbers A and B. the Output signals of the circuits determine the signs of the numbers 2 and 8, respectively A and B (0 - positive, 1 - negative number), is fed to the input of a logic gate exclusive-or 4, which in the case of different signs generates a signal to shift the polarity of the numbers corresponding to the constant Ciand submits to the input circuits 3 and 7, where the shift occurs polarity of numbers. The outputs of the systems diagrams shift polarity 3 and 7, respectively, for numbers a and b are the address inputs of the lookup tables 5 and 6

Memory elements, lookup tables (LUT table) 5-1, 5-2 5-n and 6-1, 6-2, 6-n, respectively, store the works ofandwelcome to the number β of the numbers presented in additional code, which is fed to the input of the adder 10, the torus is the sum of additional code. The resulting sum is fed to the measuring block 11, which is defined by: the equality A=B bus 12, A>B bus 13 and A<B bus 14.

Example 4. Let the given system bases p1=2, p2=3, p3=5, p4=7. To compare modular integers A=(1,2,2,3) and B=(1,2,1,2). The raw numbers are in registers RGA and RGB are received by the input circuits determine the sign SOSC and SOSC-Century In these schemes there is a comparison of the initial numbers with constant.

,

.

The difference is positive, that is,therefore , the number And included in the first interval, and is positive.

.

The difference is negative, so the number of B included in the second interval is negative.

The result of the analysis of the signs of the numbers A and B is formed on the gate output of the exclusive "or" which is fed to the input circuits of the shift polarity SSP and SSP-Century At the outputs of circuits shift the polarity of the generated data, respectively, A=(1,2,2,3)+(1,0,0,0)=(0,2,2,3) and B=(1,2,1,2)+(1,0,0,0)=(0,2,1,2). The output circuits of the shift polarity are address inputs lookup tables LUT-A and LUT-B, according to which the sampling values of the intercept is t in the conditions of example, these values will be equal to the LUT-A(0;0,3333·2;0,6·2;0,5714·3) and for LUT-B(0;0,3333·2;0,6·1;0,5714·2). Output signals lookup tables LUT-A and LUT-B is fed to the input of the adder. The resulting sum will get

.

The difference is positive, since the additional code is a positive number equal to the number itself, therefore A>B. Indeed, the number A=17, B=-19.

The results of the adder are analyzed in the diagram of the adder, thus:

if the difference is equal to 0, then A=B,

if the difference is positive, then A>B

if the difference is negative, then A<B.

If compare positive numbers, then are eliminated from the scheme scheme of determining the signs of the numbers. Then the logic depth of the circuit (number of series-connected elements) is n+3, where n is the number of summirovanii in the adder, while n is determined by the number of modules in the system.

If you use recursive doubling, then the logic depth is determined by the expression [log2n]+3. In known circuits, the logical depth with regard to the determination of the coefficients of SVR is defined as 2n+5.

A device for comparing the numbers represented in the system of residual classes, containing the analysis scheme marks, numbers, characterized in that it introduced the schema definitions associate the numbers A and B, schemes shift the polarity of numbers, lookup tables (memory) for storing constantsandthe adder and the input registers, the input of which receives the numbers A and B represented in the system of residual classes, the outputs of which are connected with the first inputs of the circuits of the shift polarity and input circuits determine the signs of the numbers, the outputs of which are connected to the "exclusive or", the output of which is connected with the second inputs of the circuits of the shift in polarity, the output of which is connected to the address inputs of the lookup tables, the outputs of which are connected with the adder, the output of which is connected with the circuit analysis comparing numbers, the outputs of which are the outputs of the comparison of the numbers represented in the system of residual classes A=B, A>B and A<B.



 

Same patents:

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 b2s 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 b2*m1s, wherein the least significant bit of the number b1 is the first multiplication bit s1, the least significant bit of each obtained sum bis is the i-th multiplication bit. The binary number b2*m1s 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

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: when switching timing channels, a computer selects free timing channels of incoming and outgoing communication lines which need switching and writes the address of the channels of the outgoing lines into memory cells belonging to channels of incoming communication lines. Intermediate paths of the digital switching system under investigation are not selected in advance, which significantly reduces the load on the computer.

EFFECT: reduced load on the computer by eliminating the process of searching for free time positions of intermediate paths of digital switching systems when establishing connections, simple process of establishing connections and shorter time for said process.

1 dwg

FIELD: information technologies.

SUBSTANCE: method to determine belonging of files to collections of available files on the basis of files comparison with the help of functionality templates includes stages, at which functionality templates are generated on the basis of information on the executed file. Then extracted noise information is deleted from functionality templates of the executed file. Then units of functionality templates of the executed file are reduced to normalised view. Then these units are compared to units of functionality templates of available files, and using comparison results, decision is made on belonging of the unit to one of functionality templates of available files. Creating functionality templates by available malicious software, newly arrived files may be compared with them, and automatic records may be added with condition of similarity; characteristic logical units are extracted from collections of malicious programs, and heuristic rules are created by these units; automatic descriptions are generated. Also the possibility appears to carry out clusterisation of objects, which helps to accelerate their further processing.

EFFECT: increased reliability and accuracy of malicious software detection, achieved by comparison of executed files by means of functionality templates.

14 cl, 16 dwg

FIELD: information technology.

SUBSTANCE: changes in elements are tracked in accordance with a defined group of properties, and each group is tracked independent of the other. For example, one group may contain large data elements, for example inputs, while the other group may include highly changeable properties, such as an execution control flag feature. Rate of synchronisation between a client and a server is increased by synchronising only selected parts of the element which have changed without controlling change in each separate property within the element. Accordingly, if change has been made with respect to a small information property (for example, an execution control flag feature) in a relatively large email message, such a change will not initiate a large load on the client working in cache mode, and will also not require considerable storage space and processing in order to track each separate property.

EFFECT: high rate of synchronisation between a client and a server.

20 cl, 6 dwg

FIELD: information technology.

SUBSTANCE: situations A≥B and A<B or A>B and A≤B or A=B and A≠B, where A=an-1…a0, B=bn-i…b0 - n -bit binary numbers given by binary signals a0,…, an-1 b0…, bn-1∈{0,1}, are detected and the relationship between bitness of the compared binary numbers and the maximum signal propagation delay time is excluded. The device has n groups of switches, each consisting of 6 switches.

EFFECT: broader functionalities of the device.

1 dwg, 1 tbl

FIELD: information technologies.

SUBSTANCE: invention may be used to build means of automatics, functional units of control systems. Device comprises two delay elements, two AND elements, four OR elements, two NOT elements.

EFFECT: reduced instrument costs.

1 dwg, 1 tbl

FIELD: information technology.

SUBSTANCE: invention can be used to design automation apparatus and functional parts of control systems. The comparator has 29 transistors grouped into nine groups and 14 resistors.

EFFECT: faster operation of the device.

1 dwg, 1 tbl

FIELD: information technology.

SUBSTANCE: invention relates to computer engineering and can be used as a means of information preprocessing. The device contains 4n inhibit circuits, 2n 2OR elements, 2n opening and 2n closing switches.

EFFECT: wider functional capabilities.

1 dwg

FIELD: computer engineering.

SUBSTANCE: invention relates to computer engineering and can be used for evaluating and comparing operating efficiency of same-type organisations with the objective of drawing up recommendations for improving quality of their operation. The device contains groups of input and output registers, a group of subtracting units, group of squaring devices, groups of delay elements, groups of adders, square-root extractor, groups of commutators, groups of display units, clock-pulse generator, pulse distributor, input registers and dividers.

EFFECT: increased functionalities of the device.

3 dwg

FIELD: computer engineering.

SUBSTANCE: invention relates to computer engineering and can be used in digital computer engineering systems as an information pre-processing device. The device contains 7n majority elements, each with three inputs, and 2n NOT elements.

EFFECT: increased functionalities o the device.

1 dwg, 1 tbl

FIELD: computer engineering.

SUBSTANCE: invention relates to computer engineering and can be used in digital comparators, associative processors and database machines. The technical outcome of the invention is increased functionalities of the device for comparing binary numbers due to recognition of relationships A>B, A=B, A<B, where A and B are four-bit binary numbers. The said device for comparing binary numbers contains eight 2OR elements (11, …, 18), eight 2AND elements (21,…, 28), four NOT elements (31,…,34). There is recognition of relationships A>B, A=B, A<B due to the given elements and a new connection circuit.

EFFECT: increased functionalities of the device.

1 dwg, 1 tbl

FIELD: computer science.

SUBSTANCE: device has coefficients memory elements, comparison blocks, keys, OR elements, indicators.

EFFECT: broader functional capabilities, higher efficiency.

1 dwg

Up!