CN103699358B - A kind of Fast Modular square operation circuit being applicable to big number - Google Patents

Abstract

The invention discloses a fast modular square operation circuit suitable for large numbers. The circuit structure includes: a head-to-tail shift compensation circuit, two two-input AND gate arrays, and a one-stage carry-save adder (CSA) structure , a full adder (FA) unit, and a series of scan registers. The invention expands the square operation according to polynomial multiplication, compresses the original sum of m partial products into m/2 sum of partial products, and accumulates from high to low, so the square operation time is reduced to half of the original.

Description

A Fast Modular Square Operation Circuit for Large Numbers

technical field

The invention relates to the field of integrated circuit design, in particular to a fast modular square operation circuit suitable for large numbers.

Background technique

At present, the research on the square of large numbers usually adopts the Montgomery algorithm, and the time spent by the algorithm in the square operation process is proportional to the length of the input data.

In view of this, it is necessary to study a new square algorithm, by optimizing the partial product of the operation process, reducing the number of partial products, thereby reducing the running time of the entire square, and solving the above problems.

Contents of the invention

The object of the present invention is to provide a fast modular square operation circuit suitable for large numbers that can effectively reduce the time for modular square operation.

In order to achieve the above object, the technical solution adopted in the present invention is: comprising a leftward shift circuit, an m-bit two-to-one data selector array, an m-bit two-input AND gate array, an m-bit partial product generation circuit, a full adder FA Array, m+3-bit scan register, reduction circuit, and a shift-complement circuit with a johnson circular shift counter of m/2 bits; the input of the shift-complement circuit is m Bit square operation input item A, the output is the output Q of the m-bit register in the pinching head and tail shifting compensation circuit, and simultaneously outputs the register in the m/2-bit johnson circular shift counter in the pinching head and tail shifting compensation circuit The output Qc of the leftward shift circuit is the low m/2 bit of the square input item A; the input terminal of the m-bit partial product generation circuit is connected with the output end of the m-bit two-input AND gate array, and the m-bit partial product is generated The output terminal of the circuit is connected with the input terminal of the full adder FA array, and the full adder FA array is connected with the simple circuit through the m+3 scanning register; wherein, 160≤m≤15360.

In the leftward shift circuit, when each rising edge of the clock arrives, the value of the register in the leftward shift circuit is shifted to the left by one bit, and the lower bits are filled with zeros, and at the same time, the output terminal of the highest bit register is drawn out, which is defined as AL .

The m-bit optional one data selector array includes an m-bit optional one-two data selector, wherein the control signal of the m-bit optional one data selector is shifted cyclically by Johnson in the head-cutting and tail-shifting compensation circuit. Bit counter output Qc is generated; wherein, the control signal of the first two-to-one data selector and the second two-to-one data selector is the second digit value of Qc, the third two-to-one data selector and the fourth The control signal of the two-bit one-to-one data selector is the third digit value of Qc, and so on, the control signal of the m-3 two-to-one data selector and the m-2 two-to-one data selector is Qc The value of the m/2th bit of the m-1 bit of the two-alternative data selector and the control signal of the m-th bit of the second-alternative data selector are set to 1; the "0" terminal of the m-bit two-alternative data selector is connected The output AL of the shift circuit to the left, "1" is connected to the most significant bit of the output Q of the head-cutting and tail-shifting compensation circuit.

One port in the input end of the described m two-input AND gate is correspondingly connected with the m bit of the m-bit two-to-one data selector array, and the other input end is connected as follows:

The first AND gate is connected to the lowest bit of the output Q of the head-to-tail shift compensation circuit, the second AND gate is connected to the second bit of Q, and so on, the m-1th AND gate is connected to the second highest bit of Q The inverse code of the m-bit AND gate is connected to the second highest bit of Q; the output of the m-bit AND gate array is the final m-bit partial product output.

The m-bit partial product generation circuit, after the partial product is generated, is sent to m full adders FA as input, wherein the carry input of the lowest full adder is connected to the output of a two-to-one data selector, The "0" end of the two-to-one data selector is connected to the lowest bit Q[0] of the m-bit output Q of the head-clamping and tail-removing shift compensation circuit, and the "1" terminal inputs zero, and the control signal of the two-to-one data selector It is the second bit Qc[1] of the output Qc of the Johnson cyclic shift counter in the head-to-tail and shift-compensation circuit; the carry-in inputs of other full adders are all carry-in outputs from the lower bits.

The sum bit output of the m-bit full adder FA is sent to the input end "0" of the scan register; the "1" end of the lowest bit scan register is connected to the output end of a two-to-one data selector, and the two-to-one data The input "0" terminal of the selector is connected to the lowest bit A[0] of the square operation input item A, and the "1" terminal inputs zero, and the control signal of the two-choice data selector is Sel, which is shifted by pinching the head and removing the tail The lowest bit and the highest bit of the output terminal Qc of the Johnson counter in the complement circuit are XORed; the "1" end of the second bit scan register inputs zero, and the "1" end of the third bit scan register enters the first full adder The sum bit of FA, the "1" end of the fourth scan register is input to the sum bit of the second full adder FA, and so on, the "1" end of the m+2 scan register is input to the m full adder The sum bit of FA, the "1" end of the m+3 scan register is input to the carry output of the m-th full adder FA.

The output terminal of the m+3-bit scanning register is sent to the reduction circuit for reduction.

Compared with the prior art, the present invention has the following beneficial effects:

The partial product generating circuit of the present invention compresses m partial products into m/2, and the final square operation adopts an operation from high to low, and the first partial product is generated and shifted to the left by two bits, and then sent to the reduction circuit for reduction and then combined with Add the second partial product to complete an accumulation, and so on until the m/2th partial product is generated, complete m/2 accumulations, and finally complete the modular square operation.

Furthermore, the present invention expands the square operation according to polynomial multiplication, and compresses the original sum of m partial products into m/2 sum of partial products, and accumulates from high to low, so the square operation time is reduced to half of the original.

Description of drawings

Fig. 1 is the schematic diagram of circuit structure of the present invention;

Fig. 2 is a schematic diagram of the circuit structure of the partial accumulation and reduction of the present invention.

detailed description

Below in conjunction with accompanying drawing and embodiment the present invention will be described in further detail:

Referring to Fig. 1 and Fig. 2, the present invention comprises shifting circuit to the left, m-bit two-to-one data selector array, m-bit two-input AND gate array, m-bit partial product generating circuit, full adder FA array, m+3 A bit scan register, a reduction circuit, and an m/2-bit johnson circular shift counter with a head-to-tail shift-complement circuit; the input to the head-to-tail shift-to-compensation circuit is an m-bit square operation input Item A, the output is the output Q of the m-bit register in the shift compensation circuit for pinching the head and removing the tail, and outputs the output Qc of the register in the m/2 johnson circular shift counter in the shift compensation circuit for pinching the head and removing the tail simultaneously; The input of the left shift circuit is the low m/2 bits of the square input item A; for the left shift circuit, when each rising edge of the clock arrives, the value of the register in the left shift circuit is shifted to the left by one bit, and the low bit is complemented Zero, at the same time lead out the output terminal of the highest register, defined as AL. The input end of the m-bit partial product generation circuit is connected to the output end of the m-bit two-input AND gate array, and one port of the input end of the m-bit two-input AND gate is connected to the m-bit corresponding to the m-bit two-to-one data selector array , and the other input terminal is connected as follows: the first AND gate is connected to the lowest bit of the output Q of the head and tail shift compensation circuit, the second AND gate is connected to the second bit of Q, and so on, the mth The -1-bit AND gate is connected to the inverse code of the second highest bit of Q, and the m-th bit AND gate is connected to the second highest bit of Q; the output of the m-bit AND gate array is the final m-bit partial product output. The output end of the m-bit partial product generation circuit is connected to the input end of the full adder FA array, the full adder FA array is connected to the reduction circuit through the m+3-bit scanning register, and the output end of the m+3-bit scanning register is sent to the reduction circuit The circuit is reduced; among them, 160≤m≤15360.

The m-bit 2-to-1 data selector array includes m 2-to-1 data selectors, wherein the control signal of the m-bit 2-to-1 data selector is output by the Johnson circular shift counter in the head-to-head and tail-to-tail shift compensation circuit Qc is generated; wherein, the control signal of the first two-to-one data selector and the second two-to-one data selector is the second digit value of Qc, the third two-to-one data selector and the fourth two-to-one data selector The control signal of a data selector is the third digit value of Qc, and so on, the control signal of the m-3 bit two-to-one data selector and the m-2-th bit two-to-one data selector is the mth value of Qc /2-digit value, the control signal of the m-1th bit 2-alternative data selector and the m-th bit 2-alternative data selector is set to 1; the "0" terminal of the m-bit 2-alternative data selector is shifted to the left The output AL of the bit circuit, "1" is terminated to the highest bit of the output Q of the head-cutting and tail-shifting compensation circuit.

The m-bit partial product generation circuit, after the partial product is generated, is sent to m full adders FA as input, wherein the carry input of the lowest full adder is connected to the output of a two-to-one data selector, and two to one The "0" terminal of the data selector is connected to the lowest bit Q[0] of the m-bit output Q of the pinch head and tail shift compensation circuit, and the "1" terminal inputs zero, and the control signal of the two-choice data selector is the pinch head The second bit Qc[1] of the output Qc of the Johnson circular shift counter in the tail shift complement circuit; the carry inputs of the other full adders are all carry outputs from the lower bits.

The sum bit output of the m-bit full adder FA is sent to the input terminal "0" of the scanning register; the "1" terminal of the lowest bit scanning register is connected to the output terminal of a two-to-one data selector, and the output terminal of the two-to-one data selector The input "0" terminal is connected to the lowest bit A[0] of the square operation input item A, and the "1" terminal inputs zero, and the control signal of the data selector is Sel, and the signal is determined by the head-to-tail shift compensation circuit The lowest bit and the highest bit of the output terminal Qc of the Johnson counter in the middle are XORed; the "1" end of the second scan register inputs zero, and the "1" end of the third scan register inputs the sum of the first full adder FA Bit, the "1" end of the fourth scan register is input to the sum of the second full adder FA, and so on, the "1" end of the m+2 scan register is input to the sum of the m full adder FA Bit, the "1" end of the m+3 scan register is input to the carry output of the m-th full adder FA.

The circuit implementation structure of the fast square algorithm suitable for the large-number modulus square operation of the present invention includes: a head-and-tail shift compensation circuit, a left shift circuit, a series of two-select-one circuits, a two-input AND gate array, a full-add tor FA array and a series of scan registers and reduction circuits. Wherein, an m/2-bit johnson circular shift counter is included in the head-cutting and tail-cutting shift compensation circuit. The input of the head-to-tail and shift-compensation circuit is an m-bit square input item A, and the output is the output Q of the m-bit register in the head-to-tail shift and complement circuit, and the m/2-bit johnson circular shift counter is output at the same time The output Qc of the register. The input of the left shift circuit is the low m/2 bits of the square input item A. When the rising edge of each clock arrives, the value of the register in the left shift circuit is shifted to the left by one bit, and the low bits are filled with zeros, and the highest The output terminal of the bit register is drawn, defined as AL. The control signal of the m-bit two-choice array is mainly generated by the output Qc of the Johnson circular shift counter in the head-cutting and tail-cutting shift compensation circuit. The control signal of the first and second bits is the second value of Qc, the control signal of the third and fourth bits is the third value of Qc, and so on... m-th The one-two control signal of the 3rd bit and the m-2th bit is the value of the m/2-th bit of Qc, and the one-two control signal of the m-1th bit and the m-th bit is set to 1. The "0" terminal of the m-bit two-choice array is connected to the output AL of the leftward shift circuit, and the "1" terminal is connected to the highest bit of the output Q of the head-cutting and tail-removing shift-compensation circuit. One of the input ports of the m-bit two-input AND gate is connected to the m-bit of the m-bit two-choice array, and the other input terminal is connected as follows: the first bit AND gate is connected to the output of the first-bit and tail-cutting shift compensation circuit The lowest bit of Q, the second AND gate is connected to the second bit of Q, and so on... The m-1th AND gate is connected to the inverse code of the second highest bit of Q, and the mth bit AND gate is connected to the second highest bit of Q. The output of the m-bit AND gate array is the final m-bit partial product output.

After the partial product is generated, it is sent to m full adders FA as input, among which, the carry input of the lowest full adder is connected to a two-choice output, and the "0" terminal of the two-choice one is connected to pinch the head and remove the tail shift The m-bit output Q of the bit complement value circuit is the lowest bit Q[0], and the "1" terminal inputs zero, and the control signal to select one of the two is the output Qc of the Johnson circular shift counter in the shift complement value circuit of pinching the head and removing the tail. The second bit Qc[1]; the carry inputs of the other full adders are all carry outputs from the lower bits. The sum bit output of the m-bit full adder is sent to the input terminal "0" of the scanning register. The "1" end of the lowest bit scanning register is connected to an output end of the alternative one, and the input "0" end of the alternative one is connected to the lowest bit A[0] of the input item A of the square operation, and the "1" end inputs zero, two The selected one control signal is Sel, which is generated by the XOR of the lowest bit and the highest bit of the output terminal Qc of the Johnson counter in the head-cutting and tail-cutting shift compensation circuit. The "1" terminal of the second scanning register inputs zero, the "1" terminal of the third scanning register inputs the sum bit of the first full adder FA, and the "1" terminal of the fourth scanning register inputs the second full The sum bit of the adder FA, and so on, the "1" end of the m+2 scan register is input to the sum bit of the m full adder FA, and the "1" end of the m+3 scan register is input to the m The carry output of the full adder FA. The output terminal of the m+3-bit scan register is sent to the reduction circuit for reduction.

In the present invention, the partial product generation circuit compresses m partial products into m/2, and the final square operation adopts the operation from high order to low order. Then add it to the second partial product to complete an accumulation, and so on until the m/2th partial product is generated, complete m/2 accumulations, and finally complete the modular square operation.

Table 1

Referring to Table 1, Table 1 is the partial product summation table of the square operation expanded according to polynomial multiplication. The whole process needs to sum m partial products, and the whole process requires m-1 clock cycles.

Table 2

With reference to Table 2, Table 2 is the optimized partial product sum table of the present invention, and the partial product is compressed into half of that in Table 1, and the whole process only needs m/2-1 clocks to complete the square operation.

table 3

A5A4 A5 (!A4) A7A1 A6A1 A5A1 A4A1 A3A1 A2A1+A2 0 A1 A6A5 A6 (!A5) A6A4 A6A3 A6A2 A5A2 A4A2 A3A2+A3 A7A6 A7 (!A6) A7A5 A7A4 A7A3 A7A2 A5A3 A4A3+A4 A8A7 A8 (!A7) A8A6 A8A5 A8A4 A8A3 A8A2 A8A1

With reference to table 3, table 3 adopts the square partial product summation form of this algorithm as an example with 8 binary numbers, takes 8 binary numbers as example, adopts algorithm of the present invention, the partial product is compressed into 4 items.

Operation process of the present invention:

Referring to Figure 1 and Figure 2, when initializing RS=0, all registers are set to 0; when working, RS=1, after the first effective clock edge, the shift compensation circuit output Q=[A _m ,A _m-1 ,A _m-2 ···A ₂ ,A ₁ ], Qc=[11···111]; after the second effective clock edge, the first partial accumulation is completed, and the head and tail are cut The shift compensation circuit output Q=[A _m-1 , A _m-2 ···A ₂ ,A _m/2+1 ,A _m/2 ], Qc=[11···110]; until the mth After /2 clock edges, m/2-1 partial accumulations are completed, and the output data is shifted to the left and stored in the register, so the lowest two bits of the register are 00; when the m/2+1 clock edge arrives, all parts The accumulation and addition are completed and the lowest bit of the input item A of the square operation is stored in the last two registers at the same time; in the process of partial accumulation and addition, the output values of m+3 scanning registers are scanned after the rising edge of each clock arrives. Send it to the reduction circuit. After the reduction is completed, wait for the next clock edge to arrive, and accumulate with the next part, and so on... until the m/2+1th clock edge, the register stops shifting, and at most two more clock edge, and finally complete the modular square operation process.

Claims (7)

1. A fast modular square operation circuit applicable to large numbers, characterized in that: comprise a shift circuit to the left, an m-bit two-select-one data selector array, an m-bit two-input AND gate array, and an m-bit partial product generation circuit , full adder FA array, m+3-bit scan register, reduction circuit and a head-to-tail shift and complement circuit with an m/2-bit johnson circular shift counter; head-to-tail shift and complement The input of the circuit is an m-bit square operation input item A, and the output is the output Q of the m-bit register in the head-to-tail shift and complement circuit, and at the same time output the m/2-bit johnson cycle in the head-to-tail shift and complement circuit The output Qc of the register in the shift counter; the input to the left shift circuit is the low m/2 bit of the square input item A; the input end of the m bit partial product generation circuit is connected with the output end of the m bit two-input AND gate array, The output end of the m-bit partial product generation circuit is connected to the input end of the full adder FA array, and the full adder FA array is connected to the simple circuit through m+3 bit scan registers; wherein, 160≤m≤15360. 2. The fast modular square operation circuit suitable for large numbers according to claim 1, characterized in that: the leftward shift circuit, when each clock rising edge arrives, the value of the register in the leftward shift circuit Shift one bit to the left, fill the low bit with zero, and lead out the output terminal of the highest bit register, which is defined as AL. 3. the fast modular square operation circuit suitable for large numbers according to claim 1, characterized in that: the m-bit data selector array includes m-bit two-choice data selectors, wherein the m-bit The control signal of the two-to-one data selector is generated by the output Qc of the Johnson circular shift counter in the head-to-tail shift compensation circuit; wherein, the first two-to-one data selector and the second two-to-one data selector The control signal of the device is the second value of Qc, the control signal of the third data selector and the fourth data selector is the third value of Qc, and so on, m-3 The control signal of the two-to-one data selector and the m-2th two-to-one data selector is the m/2th digit value of Qc, the m-1-th two-to-one data selector and the m-th two-to-one data selector The control signal of the data selector is set to 1; the "0" terminal of the m-bit two-choice data selector is connected to the output AL of the left shift circuit, and the "1" terminal is connected to the output Q of the head and tail shift compensation circuit the highest bit. 4. the fast modular square operation circuit suitable for large numbers according to claim 1, characterized in that: a port in the input end of the two-input AND gate of the m position and an m-bit two-select-one data selector array The m bits of are connected correspondingly, and the other input terminal is connected as follows: The first AND gate is connected to the lowest bit of the output Q of the head-to-tail shift compensation circuit, the second AND gate is connected to the second bit of Q, and so on, the m-1th AND gate is connected to the second highest bit of Q The inverse code of the m-bit AND gate is connected to the second highest bit of Q; the output of the m-bit AND gate array is the final m-bit partial product output. 5. according to claim 1 or 4 described fast modular squaring circuit applicable to large numbers, it is characterized in that: described m bit partial product generation circuit, after partial product generation, sends into m full adders FA As the input, wherein, the carry input of the lowest full adder is connected to the output of a two-to-one data selector, and the "0" end of the two-to-one data selector is connected to the m bit of the head-to-tail shift compensation circuit Output the lowest bit Q[0] of Q, input zero at the "1" terminal, and the control signal of the data selector is the second bit Qc of the output Qc of the Johnson circular shift counter in the head-to-head and tail-to-tail shift compensation circuit [1]; The carry-in of other full adders is the carry-out from the lower bit. 6. the fast modular square operation circuit suitable for large numbers according to claim 1 is characterized in that: the sum bit output of the full adder FA of the m position is sent into the input terminal "0" end of the scanning register; The "1" terminal of the bit scan register is connected to the output terminal of a two-to-one data selector, and the input "0" terminal of the two-to-one data selector is connected to the lowest bit A[0] of the square operation input item A, and the "1" terminal Input zero, the control signal of the two-choice one data selector is Sel, and this signal is produced by the lowest bit and the highest bit of the output terminal Qc of the Johnson counter in the head-to-tail shift compensation circuit; the second scan register The "1" terminal inputs zero, the "1" terminal of the third scanning register inputs the sum bit of the first full adder FA, and the "1" terminal of the fourth scanning register inputs the sum bit of the second full adder FA , and so on, the "1" end of the m+2 scan register is input to the sum bit of the m full adder FA, and the "1" end of the m+3 scan register is input to the m full adder FA carry out. 7. The fast modular square operation circuit suitable for large numbers according to claim 1, characterized in that: the output terminal of the m+3-bit scanning register is sent to the reduction circuit for reduction.