Device for determining sign of modular number

FIELD: information technology.

SUBSTANCE: device includes input registers for temporary storage of bits of the initial number, memory for storing products and a parallel adder.

EFFECT: faster operation of the device for determining the sign of a number and reducing equipment.

3 dwg

 

The invention relates to computing and can be used to determine the signs of modular numbers included in computing device operating in the system of residual classes. It is known device for determining the signs of the numbers represented in the system of residual classes (A.S. NO. 1552181, BI No. 11, 1990), consisting of a block 1 number determination interval, charts 3 and 4 compare, items, or 5 and 6. However, this device has the following disadvantages: low speed and large hardware costs. The closest to the technical nature of the claimed device is a device for determining the sign of the number represented in the system of residual classes (A.S. NO. 1674121, IB No. 32, 1991), containing the block number determination interval, the comparison circuit, group encryption and decryption, the adder and logic elements "or".

The disadvantages of the known devices are low speed determine the sign and large hardware costs.

The aim of the present invention is to improve performance and reduce hardware costs.

This objective is achieved in that in the known device introduced lookup tables (LUT) and a parallel adder.

Consider the method of determining the sign of the number with high performance and low cost equipment is tion. The method of rapid determination of the sign of modular numbers are based on the use of Chinese theorem rests numbers, which connects the position number And its representations in the residuals (α1α2, ..., αn), where αithe least non-negative residue numbers modulo p1p2, ..., pn.

The numbers αithe view on the selected modules are formed as follows

where- the integer quotient, pi- base (modules) - mutually Prime numbers. In number theory it is proved that if ∀i≠j(pipj)=1, then the representation (1) is only under the condition 0≤A < P, wherethe range of number representation, i.e. there exists a number A for which:

Famous Chinese theorem on residues that binds positional number And 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 (3) divided by a constant P, then we obtain an approximate value

whereconstants 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 (4), 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.

Consider the case where the operating range is divided into two intervalsare positive numbers, and - negative number.

It is known that when encoding additional code, 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 or for even P to each.

Ifthe 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.

The method of determination of such positional characteristics of modular code, as the definition of the sign showed, in contrast to the known, the simplicity of its computation, so as to implement is not in use 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 in applications 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, che is the translation of numbers from the JUICE in the round, because of 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.

To improve the efficiency of data processing in modular arithmetic consider the application of approximate methods for determining the sign of the number.

The definition of a symbol of modular numbers

It is known that to determine the sign of the numbers are the numbers of intervals in which there is a number that allows you to obtain an estimate of the investigated number on its value up to a value of the interval. The numerical range of P can be divided into piinterval value

As a second machine zero is chosen point numeric range. The number located in the sub-bandsandare integers of different signs.

If given the representation (α1α2,...,αn), in order to establish the sign of the number that it represents the residual to solve the problem of set this number to a specific interval. If pi=2 it is enough to solve the problem of supplies this number to the firstor secondhalf of the range of. This problem is solved by a comparison of this view with the viewprovided that p1=2. All known methods implement this algorithm is based on the use of absolute values, here we propose to use relative values, which greatly simplifies the conversion, while maintaining the basic functionality.

Figure 3 shows the diagram of a device for determining the sign of modular integers modulo p1p2, ..., pn.

The device consists of an input register 3 modules p1p2, ..., pnfor temporary storage of digits JUICE (each discharge JUICE is represented by a binary code), lookup tables (LUT) for storing works of art constants discharges JUICE.wheremultiplicative inversion, pimodule JUICE,,parallel adder for summing the the input of the tire 1 to the filing of the original number, the output bus for fixing the sign and entrance.

The operation of the device to determine the sign of the modular number is defined as follows.

The input registers (RGi) 3 input 1 of the device for determining the sign of the number served, the original number is represented in the system of residual classes A=(α1α2,...,αn). Output 2 is formed by the modular sign of the number. The outputs of the registers are address inputs lookup tables (LUT) (memory), the elements of which are stored values of. With outputs of 5 review table 4 selected values are received at the first inputs of the adder and to the second input 7 receives the value of. The result of the operation is the sign of the number is 0 - positive, 1 - negative.

Code number A for which you want to define a gap, which is equivalent to determining the sign of the number, is fed to the input registers RGiin binary code (each digit JUICE is encoded in binary code). The signals from the outputs of the registers are received at the inputs of the lookup table LUT. In the screening tables are stored works constants kiand residues αipresented in a natural f is RME binary fraction in the codebehind. The number of memory elements (N) lookup table is determined by the expression.

The output signals of the screening tables in additional binary code is fed to the input of the adder, which is already recorded constant of 0.5 during the initial installation. (Additional code is used for the subtraction operation to replace the operation of addition). The sign of the result of the addition interval: first or second, respectively, determines the sign of the number.

Example 4. Let the given system bases p1=2, p2=3, p3=5, p4=7. Then P=210. Constants kirespectively equal to k1=0,5, k2≈0,3333, k3or =0.6, k4≈0,5714.

Given the number of a=(1, 1, 2, 0). You want to determine the sign of the number A.

Solution. In the registers RG1=1, RG2=1, RG3=2, RG4=0. In accordance with these values of registers (address inputs LUT) on the outputs of which are formed of LUT values1=0,5, LUT2=0,3333·1=0,3333,, LUT4=0.

Thus, when the summation sign in the discharge of the accumulator is 0, which indicates that the number is in the first interval, sothat is A - positive.

The definition of a symbol is summation for n, where n is the number of bases (modules) JUICE. Time su the remuneration is determined by the logical depth of the unit (the number of series-connected elements) and time summation adder. To reduce the time summation diagram of the adder can be implemented on the principle of tree (recursive doubling). Additionally, the implementation of the adder can be performed on artificial neural networks.

Device for determining the sign of modular numbers, characterized in that it introduced the input registers for modules p1p2, ..., pnfor temporary storage of bits of JUICE, a parallel adder for summing thethe input bus for the filing of the original number, lookup tables for storing works constants discharges JUICErepresented in binary code, the inputs of which are generated from the output registers binary codes discharges JUICE αithe outputs are connected to inputs of the adder, the second input of which receives the constantwhose output is the output device.



 

Same patents:

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

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: computers.

SUBSTANCE: device has N blocks for calculating remainders, each of which has N devices for calculating remainders from bases of modular notation scale, including multiplication blocks, module adders of 3N numbers and tabular calculators.

EFFECT: higher speed of operation.

5 dwg, 1 ex

FIELD: computer science.

SUBSTANCE: device has harmonic signal generator, controlled phase changers, means for measuring phase of harmonic signal, phase changers for fixed phase values, transformers of binary number code to unary in accordance to first and second sub-modules, coder and table calculation means.

EFFECT: lower costs.

3 dwg

FIELD: computer science, possible use for engineering of signals processing microprocessors, and of digital filters.

SUBSTANCE: device uses neural-network technologies and polynomial residuals system, wherein as system base minimal polynomials pi(z), where input=1,2,...,n, are utilized, determined in expanded Galois fields GF(2V), while device has clock counter, two blocks for calculating sums of paired results of multiplication by arbitrary base, error correction block, modular adder and block for calculating sums of paired results of multiplication based on control base.

EFFECT: decreased hardware requirements, improved speed of operations.

2 dwg, 3 tbl

FIELD: automatics and computer science, possible use for engineering of computing structures functioning in modular computation system.

SUBSTANCE: device has encoder, controlled phase shifter, harmonic signal generator, phase shifters for fixed phase value, device for measuring the phase of harmonic signal, multiplexer, commutator, amplitude detector and harmonic signal amplifier.

EFFECT: simplified construction of device.

3 dwg

FIELD: computer science, in particular, modular neuron-computer means.

SUBSTANCE: network has input layer of neurons, neuron network of end ring for determining number rank, neuron network of end ring for calculating remainder at base n+1, n-neuron networks of end ring for calculating scaled number, neuron network for calculating difference in numbers between input remainders and base remainder.

EFFECT: decreased volume of equipment, increased speed of numbers rounding and expanded functional capabilities.

1 dwg

FIELD: cryptographic method and chip-card for encoding information, methods for creating electronic signatures.

SUBSTANCE: at least one calculation step is performed, providing for realization of E operation of modular exponentiation in accordance to formula E=xd(mod p·q), where d and mod p·q are components of a secret key, while parallel represent first simple multiplier, q is second simple multiplier, d is level coefficient, and x represents base, while operation E of modular exponentiation is performed in accordance to Chinese theorem about remainders.

EFFECT: decreased amount of computing operations and machine time costs during simultaneous increase of level of data protection from unsanctioned access.

4 cl

FIELD: computer science, possible use in computing devices functioning in system of remainder classes, and also communication equipment for transferring information in remainder classes system codes.

SUBSTANCE: device contains a group of constant memorizing devices, a group of registers, discharge-parallel modulus adder.

EFFECT: decreased volume of equipment and increased speed of operation when transforming a number from remainder classes system to positional code.

1 dwg

FIELD: computer engineering, possible use in digital computing devices, and also in devices for forming elements of finite fields.

SUBSTANCE: device contains adders, inverters, multipliers, multiplexer.

EFFECT: expanded functional capabilities due to expanded range of input number values.

1 dwg

Modulus multiplexer // 2299461

FIELD: computer engineering, possible use in digital computing devices, and also in devices for forming finite field elements.

SUBSTANCE: device contains multiplier, adders, inverters, constant multipliers, multiplexer.

EFFECT: expanded functional capabilities.

1 dwg

FIELD: computer engineering, possible use in digital computing devices for forming code series, creation of which is based on finite fields theory.

SUBSTANCE: device contains block for forming partial remainders, modulus multiplexers, modulus adders.

EFFECT: expanded functional capabilities due to creation of remainders by double modulus, by calculating partial remainders from polynomial powers with their following addition in acc to coefficients of polynomial powers.

3 dwg

Up!