# 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

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 α_{i}the smallest non-negative deductions number, relative to the modules of the system of residual classes p_{1}p_{2}, ..., p_{n}the following expression

where_{i}modules JUICE,_{i}relative to p_{i}and

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

where_{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

Example 1. Let the given system bases p_{1}=2, p_{2}=3, p_{3}=5, p_{4}=7, volume range P=2·3·5·7=210. Suppose that in a given JUICE will contain only positive numbers. _{1}=25 and_{2}=30, presented in Soko grounds p_{
1}p_{2}p_{3}p_{4}then there is A_{1}=(1,1,0,4), A_{2}=(0,0,0,2). For this, you will find constants

(2) we get

As_{2}>A_{1}there is a 30>25.

Consider the case where the operating range is divided into two intervals_{1}and A_{2}is performed by calculating A_{1}-A_{2}and determine the sign of the difference. In the system of residual classes is not enough to determine the sign by_{1}-A_{2}can go beyond the range of

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

Let_{1}>A_{2}. On the basis of (2) we define_{1}=(0,1,0,0) and A_{2}=(0,2,0,0) - additional code is a negative number. Find

The number of A_{2}included in the negative range, that is,

Therefore the comparison will lead to incorrect results (A_{1}<A_{2}.

To determine the correct comparison should check the signs of a_{1}and A_{2}and then the comparison algorithm will be:

1. To determine the signs of a_{1}and A_{2}.

2. If A_{1}and A_{2}without signs, the positive sign of the difference between the relative values mean more.

3. If A_{1}and A_{2}have the same sign, then checked

4. If A_{1}and A_{2}have different signs, then_{1}<A_{2}and_{1}>A_{2}.

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 of

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 constants

If_{ic}denotes the residual digits after the shift polarity.

Example 3. To compare modular integers of different signs A_{1}and-A_{2}. The system bases the JUICE is the same as in example 1: p_{1}=2, p_{2}=3, p_{3}=5, p_{4}=7.

Let the number A_{1}=17=(1,2,2,3), A_{2}=-19=(1,1,4,5). Then additional code of A_{2}=(p_{1}-1,p_{2}-1,p_{3}-4.p_{4}-5)=(1,2,1,2). You want to compare numbers A_{1}and A_{2}.

Checking the sign of A_{1}. To determine the sign of A_{1}compare it with the constant of_{1}in relation to the value of the number K is defined as

View constants_{1}included in the first interval and is positive.

Checking the sign of A_{2}is similar:_{
2}included in the second interval, it is obvious that it is negative. For correct comparison of the numbers A_{1}and A_{2}you must hold the shift polarity of the integers A_{1}and A_{2}as A_{2}is negative. After shifting the received

We define the relative value of

Find the difference of relative values, then_{1}>A_{2}.

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 JUICE

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 C_{i}and 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 of

Example 4. Let the given system bases p_{1}=2, p_{2}=3, p_{3}=5, p_{4}=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,

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

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 [log_{2}n]+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 constants

**Same patents:**

FIELD: information technology.

SUBSTANCE: method comprises steps of: concurrently writing the remainder on base p_{1} of a multiplicand in memory elements; concurrently counting the number of units b_{i} in each column of the i-th matrix; shifting the binary number b_{1} one bit to the right; summing with a number b_{2}; shifting the obtained sum _{3}. Similarly, the obtained sums are shifted and summed with subsequent numbers to obtain a sum _{1} is the first multiplication bit s_{1}, the least significant bit of each obtained sum _{2*m}. If s is greater than p_{1}, the obtained product s is corrected by successive subtraction of the base p_{1} from s until s is less than p_{1}, 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 p_{i} of a multiplicant is concurrently recorded in matrix memory elements of the i-th multiplier; the number of units b_{i} in each column of the i-th matrix is concurrently counted; the binary number b_{1} is shifted by one bit to the right and summed with number b_{2}; the obtained sum b^{s} _{2} is shifted by one bit to the right and summed with number b_{3}. Similarly, the obtained sums are shifted and summed with subsequent numbers to obtain a sum b^{s} _{2*m-1}, wherein the least significant bit of the number b_{1} is the first multiplication bit s_{1}, the least significant bit of each obtained sum b^{s} _{i} is the i-th multiplication bit. The binary number b^{s} _{2*m-1} is shifted, the least significant bit of the obtained number is the (2*m)-th bit of the determined product s_{2*m}. If s_{i} is greater than p_{i}, the obtained product s_{i} is corrected by successive subtraction of the base p_{i} from s_{i} until s_{i} is less than p_{i}, 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

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=a_{n-1}…a0, B=b_{n-i}…b_{0} - n -bit binary numbers given by binary signals a_{0},…, a_{n-1} b_{0}…, b_{n-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 (1_{1}, …, 1_{8}), eight 2AND elements (2_{1},…, 2_{8}), four NOT elements (3_{1},…,3_{4}). 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