JP3922380B2 - Extensible squarer and square calculation method - Google Patents

Description

  The present invention relates to squarers, and more particularly to expandable squarers.

  Square operation has been widely used in VLSI circuits, communication systems and radar systems. In the past, multipliers have been used to perform square operations. With complex computing systems or integrated circuits, hundreds of thousands of multipliers are required. This leads to an increase in cost.

  In order to solve this problem, a square calculation technique and a circuit have been developed. FIG. 1 is a table of booth multiplication. Referring to FIG. 1, y represents a multiplicand, x represents a multiplier, and i represents a bit number and an integer. The Booth method checks 3 bits for each operation and skips 2 bits. Thus, as shown in FIG. 1, one bit overlaps and an m / 2 column of partial product terms is generated.

FIG. 2 is a partial multiplication matrix of a prior art squarer. Referring to FIG. 2, A represents a bit code and the subscript represents a bit of the bit code. FIG. 2 shows a partial multiplication matrix of 4-bit data (A ₀ A ₁ A ₂ A ₃ ) square operation.

In addition, the Booth encoding method is also used for the square calculation. For example, before the Booth encoding method performs a square operation on 8-bit data, the 8-bit data is represented as follows.

-B ₇ 2 ⁷ + b ₆ 2 ⁶ + ... + b ₀ 2 ⁰ = B ₃ 2 ⁶ + B ₂ 2 ⁴ + B ₁ 2 ² + B ₀ 2 ⁰

Here, b represents a bit code of 8-bit data, and a subscript represents a bit of the bit code. B ₁ , B ₂ , B ₃ and B ₄ represent operations according to the Booth encoding method and are expressed as follows.

B _i = −2b _{2i + 1} + b _2i + b _2i−1

FIG. 3 shows a partially folded multiplication matrix according to the 8-bit Booth method. Referring to FIG. 3, the square value of 8-bit data can be expressed as follows.

(2B ₃ 2 ⁶ + 2B ₂ 2 ⁴ + 2B ₁ 2 ² ) × B ₀ 2 ⁰ + B ₀ × 2 ⁰
+ (2B ₃ 2 ⁴ + 2B ₂ 2 ² ) × B ₁ 2 ⁴ + B ₁ × 2B ₁ ⁴
+ (2B ₃ 2 ² ) × B ₂ 2 ⁸ + B ₂ × B ₂ 2 ⁸
+ B ₃ × B ₃ 2 ¹²

This equation can be simplified as follows.

(P ₀ 2 ³ + C ₀ ) + (P ₁ 2 ³ + C ₁ ) 2 ⁴ + (P ₂ 2 ³ + C ₂ ) 2 ⁸ + C ₃ 2 ¹²

Here, P and C are represented by the following equations.

C _i = B _i × B _i i = 1,. . . , 4

P _i = (− b ₇ 2 ^5-2i + b ₆ 2 ^4-2i +... + B _{2i + 2} 2 ⁰ + b _{2i + 1} 2 ⁰ ) × B _i
i = 0,. . . , 2

  These prior art methods require large sized circuits. This requirement conflicts with the trend of circuit integration.

  Accordingly, the present invention is directed to an expandable squarer that effectively reduces the size of the circuit.

  The present invention is also directed to the method of squaring for the expandable squarer described above for data squaring.

であり、ｂ_ｎ−１、ｂ_ｊ及びｂ_ｉ＋１は、ｎビットデータのｎ−１番目、ｊ番目及びｉ＋１番目のビットコードを表わし、ｉ、ｊ及びｋは、正の整数である。複数の演算ユニットは、バイナリ重みにしたがってｎビットデータのビットコードを受ける。最上位ビットのビットコードを受ける演算ユニットを除いて、演算ユニットの入力端子は、ビット拡張データを受けるために、これらに対応するビット拡張出力端子に結合される。演算ユニットの各々は、ビット拡張データにビットコードと２の二乗とを乗算し、ビットコードの二乗値を加え、被演算子（Ｓｉ）を発生する。
The present invention discloses an expandable squarer that performs a square operation on n-bit data. n is a positive integer not equal to 0. The expandable squarer includes a bit expansion circuit and a plurality of arithmetic units. The bit extension circuit has n−1 bit extension output terminals for outputting corresponding bit extension data, and the i-th bit extension data is:

B _n−1 , b _j and b _{i + 1} represent the (n−1) th, jth and i + 1th bit codes of n-bit data, and i, j and k are positive integers. The plurality of arithmetic units receive a bit code of n-bit data according to the binary weight. Except for the arithmetic unit that receives the bit code of the most significant bit, the input terminal of the arithmetic unit is coupled to the corresponding bit extended output terminal for receiving the bit extended data. Each of the arithmetic units multiplies the bit extension data by the bit code and the square of 2, adds the square value of the bit code, and generates an operand (Si) .

ここで、Ｓ_ｉは、ｉ番目のビットコードを受ける演算ユニットから発生された被演算子を表わし、Ｃ_ｎ−１は、最上位ビットのビットコードを受ける演算ユニットから発生された、最上位ビットのビットコードの二乗に等しい被演算子を表わす。
In an embodiment of the present invention, the expandable squarer further includes a multiplication operation unit with an addition operation unit that receives the output of the operation unit and calculates the output of the operation unit as follows.

Here, S _i represents an operand generated from the arithmetic unit that receives the i-th bit code, and C _n−1 is the most significant bit generated from the arithmetic unit that receives the bit code of the most significant bit. Represents an operand equal to the square of the bit code of.

  In some embodiments, the expandable squarer further comprises a decoder that generates a bit code according to the binary weights.

であり、ｂ_ｎ−１、ｂ_ｊ及びｂ_ｉ＋１は、ｎビットデータのｎ−１番目、ｊ番目及びｉ＋１番目のビットコードを表わし、ｉ、ｊ及びｋは、正の整数である。最上位ビットのビットコードを受ける演算ユニットを除いて、ビットコードの各々は、複数の計算を発生するために、ビット拡張データの１つに乗算される。前記計算は、複数の被演算子を発生するために、２を乗算され、これらに対応するビットコードの二乗値を加算される。ｎビットデータの二乗値は、以下の式にしたがって前記複数の被演算子を演算することによって発生される。

ここで、Ｓ_ｉは、ｉ番目のビットコードを受ける演算ユニットから発生された被演算子を表わし、Ｃ_ｎ−１は、最上位ビットのビットコードを受ける演算ユニットから発生された、最上位ビットのビットコードの二乗に等しい被演算子を表わす。
The present invention also discloses a square calculation method for calculating a square value of n-bit data. The method includes generating n-1 bit extension data, where the i th bit extension data is:

B _n−1 , b _j and b _{i + 1} represent the (n−1) th, jth and i + 1th bit codes of n-bit data, and i, j and k are positive integers. With the exception of the arithmetic unit that receives the bit code of the most significant bit, each bit code is multiplied by one of the bit extension data to generate a plurality of calculations. The calculation is multiplied by 2 to generate a plurality of operands , and the corresponding bit code square values are added. A square value of n-bit data is generated by calculating the plurality of operands according to the following equation.

Here, S _i represents an operand generated from the arithmetic unit that receives the i-th bit code, and C _n−1 is the most significant bit generated from the arithmetic unit that receives the bit code of the most significant bit. It represents the same operand of the square of the bit codes.

Therefore, the present invention uses the above formula. The arithmetic unit, the operand, according to the bit code and the bit extension data corresponding to these, produced in order to generate a square of n-bit data. With these equations, the expandable squarer of the present invention can be effectively reduced. Therefore, the overall system size is also reduced.

  In order to make the aforementioned and other objects, features and advantages of the present invention comprehensible, a preferred embodiment accompanied with figures is described in detail below.

  The following is a description of the square operation for 4-bit and 8-bit data.

The equation describing the 4-bit data is shown below.

B = −b ₃ 2 ³⁺ b ₂ 2 ² + b ₁ 2 ¹ + b ₀ 2 ⁰

Here, b represents a bit code of 4-bit data, and a subscript represents a bit of the bit code. The square operation for 4-bit data can be shown as a matrix in FIG.

FIG. 4 is an operation matrix of a square operation regarding 4-bit data according to an embodiment of the present invention. Referring to FIG. 4, this matrix can be represented by the following equation (1).

B ² = (− 2b ₃ 2 ³ + 2b ₂ 2 ² + 2b ₁ 2 ¹ ) × b ₀ 2 ⁰ + b ₀ × b ₀ 2 ⁰
+ (-2b ₃ 2 ² + 2b ₂ 2 ¹ ) × b ₁ 2 ² + b ₁ × b ₁ 2 ²
+ (-2b ₃ 2 ¹ ) × b ₂ 2 ⁴ + b ₂ × b ₂ 2 ^{4
_{+ B 3 × b 3 2 6}} (1)

Equation (1) can be simplified as follows.

S ₀ + S ₁ 2 ² + S ₂ 2 ⁴ + C ₀ 2 ⁶

Here, S and C can be expressed as shown in Equation (2).

S _j = (P _j 2 ² + C _f ) j = 0,. . . , 2
C _i = b _i × b _i i = 0,. . . , 2 (2)

Here, P _j is defined as follows.

P _i = (− b ₃ 2 ²⁻ⁱ + b ₂ 2 ¹⁻ⁱ + b _{i + 1} 2 ⁰ ) × b _i
i = 0,. . . , 2

Here, a part of this equation is represented by BE _i , and P _i is shown in equation (3).

P _i = BE _i × b _i (3)

The following is a description of the square operation for 8-bit data. The equation describing 8-bit data is shown below.

_{^{B = -b 7 2 7 + b}} 6 2 6 + b 5 2 5 + b 4 2 4 + b 3 2 3 + b 2 2 2 + b 1 2 1 + b 0 2 0

  The square operation for 8-bit data can be shown as a matrix in FIG.

FIG. 5 is an operation matrix of a square operation regarding 5-bit data according to an embodiment of the present invention. Referring to FIG. 5, this matrix can be represented by the following equation:

B ² = (-2b ₇ 2 ⁷ + 2b ₆ 2 ⁶ + 2b ₅ 2 ⁵ + 2b ₄ 2 ⁴ + 2b ₃ 2 ³ + 2b ₂ 2 ² + 2b ₁ 2 ¹ ) × b ₀ 2 ⁰ + b ₀ × b ₀ 2 ⁰
+ (-2b ₇ 2 ⁶ + 2b ₆ 2 ⁵ + 2b ₅ 2 ⁴ + 2b ₄ 2 ³ + 2b ₃ 2 ² + 2b ₂ 2 ¹ ) × b ₁ 2 ² + b ₁ × b ₁ 2 ²
+ (-2b ₇ 2 ⁵ + 2b ₆ 2 ⁴ + 2b ₅ 2 ³ + 2b ₄ 2 ² + 2b ₃ 2 ¹ ) × b ₂ 2 ⁴ + b ₂ × b ₂ 2 ^{4
_{+ (- 2b 7 2 4 +}} 2b 6 2 3 + 2b 5 2 2 + 2b 4 2 1) × b 3 2 6 + b 3 × b 3 2 6
+ (-2b ₇ 2 ³ + 2b ₆ 2 ² + 2b ₅ 2 ¹ ) × b ₄ 2 ⁸ + b ₄ × b ₄ 2 ⁸
+ (-2b ₇ 2 ² + 2b ₆ 2 ¹ ) × b ₅ 2 ¹⁰ + b ₅ × b ₅ 2 ¹⁰
+ (-2b ₇ 2 ¹ ) × b ₆ 2 ¹² + b ₆ × b ₆ 2 ¹²
+ B ₇ × b ₇ 2 ¹⁴

This equation can be simplified as follows.

S ₀ + S ₁ 2 ² + S ₂ 2 ⁴ + S ₃ 2 ⁶ + S ₄ 2 ⁸ + S ₅ 2 ¹⁰ + S ₆ 2 ¹² + C ₇ 2 ¹⁴

Here, S and C can be expressed as shown in Equation (2).

S _j = (P _j 2 ² + C _f ) j = 0,. . . , 6
C _i = b _i × b _i i = 0,. . . , 7 (2)

Here, P _j is defined as follows.

P _i = (− b ₇ 2 ⁶⁻ⁱ + b ₆ 2 ^5-i +... + B ₂ 2 ¹⁻ⁱ + b _{i + 1} 2 ⁰ ) × b _i
i = 0,. . . , 2

Here, part of this equation is represented by BE _{i, P i} is shown in Formula (3).

FIG. 6 is a flowchart illustrating a method of square calculation according to an embodiment of the present invention. In accordance with a square operation on 4 bit and 8 bit data, the present invention discloses a square operation on n bit data. Referring to FIG. 6, the present invention performs a square operation on n-bit data. The n-bit data can be expressed as follows.

B = −b _n−1 2 ⁿ⁻¹ + b _n−2 2 ⁿ⁻² +... + B ₀ 2 ⁰

Step S610 generates n-1 bit extension data BE, and the i-th extension data BE can be expressed as follows.

In step S620, all bit extension data is multiplied with their corresponding bit codes to generate a calculation P as shown in equation (3). In step S630, all computations P are multiplied by the squares of 2 to generate the operand S as shown below, and then add the squares of the corresponding bit codes.

S _j = (P _j 2 ² + C _j ) j = 0,. . . , N-2
_{C i = b i × b i} i = 0 ,. . . , N-1

Step S640 generates the result of the square operation of n-bit data by all operands S as follows.

  The bit code of the most significant bit of n-bit data can represent a sign bit that determines whether the n-bit data is positive or not. If n-bit data is negative, the bit extension data BE should be inverted before the operation.

FIG. 7 is a block diagram illustrating an expandable squarer for n-bit data according to one embodiment of the present invention. Referring to FIG. 7, the design of the expandable squarer follows the square calculation method. The bit extension circuit 701 includes n-1 bit extension output terminals for outputting n-1 bit extension data (BE _{0 to} BE _n-2 ) to the arithmetic units (A _{0 to} A _n-2 ). . Referring to FIG. 7, the extendable squarer further comprises an n-number of arithmetic units receives the n-bit code n-bit data according to a binary weighting _{(A 0 ~A n-1)} .

Referring to FIG. 7, the expandable squarer further includes a multiplication operation unit with a decoder 703 and an addition operation unit. The decoder 703 is coupled to the input terminals of the arithmetic units (A0 to An-1) that generate an n-bit code in the corresponding arithmetic unit. All arithmetic unit with respect square operation of n-bit data, generates operands in multiplication operation unit 705 with the addition operation unit according to the input data. After the decoder 703 decodes the n-bit data into the n-bit code (b0 to bn-1), the bit code (b0 to bn-1) is transmitted to the arithmetic units (A0 to An-1). Except for the arithmetic unit An-1 for receiving a bit code of the most significant bit, the other operation units, as shown in step S620 and S630 in FIG. 6, according to the bit extension data BE _i and bit code _{b i,} the Operators (S0 to Sn-2) are generated in a multiplication operation unit 705 accompanied by an addition operation unit. Arithmetic unit _{A n-1,} in order to generate and transmit the operand C _n-1 to the multiplication operation unit 705 with the addition operation unit, squaring the bit codes _{b n-1} which has received. The multiplication operation unit 705 accompanied by the addition operation unit generates the square of n-bit data according to the output from the operation units (A _{0 to} A _n−2 ), as shown in step S640.

FIG. 8 is a block diagram illustrating an expandable squarer for 16-bit data according to one embodiment of the present invention. Referring to FIG. 8, the expandable squarer of the present invention uses modular technology to reduce the size of the circuit for large data operations. Extendable squarer in Figure 8, comprises a bit expansion circuit 801, a decoder 803, and a multiplication operation unit 805 with the addition operation unit. The difference is that the arithmetic unit can be replaced by an arithmetic module 810, for example. Other items are the same as those described in FIGS. The detailed description will not be repeated.

  The 16-bit expandable squarer in FIG. 8 is implemented by modular technology, but the present invention is not limited to this. One skilled in the art will appreciate that modular technology can be used for 4-bit and 8-bit expandable squarers. The number of arithmetic units in the arithmetic module is not particularly limited.

  Thus, an expandable squarer designed according to the square operation of the present invention can perform an n-bit square operation. The present invention squares n-bit data directly to design an expandable squarer. Thus, the cost of the expandable squarer is reduced. In addition, the expandable squarer can be adapted to modular technology to reduce the size of the circuit. Therefore, the cost of the entire system is reduced.

  Although the invention has been described in terms of exemplary embodiments, it is not limited thereto. Rather, the appended embodiments should be broadly configured to include other variations and embodiments of the invention that can be made by those skilled in the art without departing from the scope of equivalents of the invention. is there.

It is a table of booth multiplication. 2 is a partial multiplication matrix of a prior art squarer. This is a partially folded multiplication matrix by the 8-bit Booth method. 3 is an arithmetic matrix of a square operation regarding 4-bit data according to an embodiment of the present invention. 3 is an arithmetic matrix of a square operation regarding 5-bit data according to an embodiment of the present invention. 4 is a flowchart illustrating a method of square calculation according to an embodiment of the present invention. FIG. 3 is a block diagram illustrating an expandable squarer for n-bit data according to one embodiment of the present invention. FIG. 4 is a block diagram illustrating an expandable squarer for 16-bit data according to one embodiment of the present invention.

Claims (7)

In an expandable squarer that performs a square operation on n-bit data, n is a positive integer not equal to 0, and the expandable squarer is
A bit expansion circuit having n-1 bit expansion output terminals for outputting corresponding bit expansion data, wherein the i-th bit expansion data is:

B _n−1 , b _j and b _{i + 1} are n−1th, jth and i + 1th bit codes of n-bit data, and i, j and k are positive integers. When,
A plurality of arithmetic units, each of which receives a bit code of n-bit data in accordance with a binary weight except for the arithmetic unit that receives the bit code of the most significant bit, and is coupled to the bit extension output terminal The input terminals of the arithmetic unit correspond to those for receiving the bit extension data, and each of the arithmetic units generates the operand (Si) in order to generate the operand (Si) . An expandable squarer characterized by multiplying a square and adding a square value of the bit code. The expandable squarer according to claim 1, wherein the output of the arithmetic unit is received and the output of the arithmetic unit is

And a multiplication operation unit with an addition operation unit that performs an operation as follows: S _i represents an operand generated from the operation unit that receives the i-th bit code, C _n−1 represents C _n-1, the extendable squarer characterized generated from the arithmetic unit which receives the bit code of the most significant bits, to represent the operands is equal to the square of the bit code of the most significant bit.   2. The expandable squarer of claim 1, further comprising a decoder that generates a bit code according to binary weights.   2. The expandable squarer according to claim 1, wherein the bit code of the most significant bit of the n-bit data represents a sign bit for determining whether or not the n-bit data is positive. . In a square operation method for calculating a square value of n-bit data, n is a positive integer including an n-bit code, and the square operation method is:
generating n-1 bit extension data, wherein the i th bit extension data is

And _{a, b n-1, b j} and _{b i + 1} is, n-1-th n-bit data, a j-th and (i + 1) th bit code, i, j and k are positive integers, steps,
Each of the bit codes, except for the arithmetic unit receiving the bit code of the most significant bit, multiplying one of the bit extension data to generate a plurality of calculations;
Multiplying the plurality of calculations by 2 and adding the corresponding square values of bit codes to generate a plurality of operands;
The plurality of operands ,

And generating a square value of the n-bit data,
S _i represents an operand generated from the arithmetic unit receiving the i-th bit code, and C _n−1 represents the most significant bit generated from the arithmetic unit receiving the most significant bit code. A method of squaring, characterized in that it represents an operand equal to the square of the bit code.   6. The method of squaring operation according to claim 5, wherein the bit code of the most significant bit of the n-bit data represents a sign bit for determining whether or not the n-bit data is positive. .   6. The square calculation method according to claim 5, wherein when the n-bit data is negative, the bit extension data is inverted before the calculation.

Images