Complex number multiplier

Details Complex number multiplier Complex number multiplier

2001-11-20

2004-11-30

Malzahn, D. H. (Department: 2124)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

Reexamination Certificate

active

06826587

ABSTRACT:

The present invention relates to a fast complex number multiplier which consumes little energy.
In current communication systems, the information is generally processed digitally. Digitization improves the quality and the performance of the transmission systems. Moreover, the increase in the bit rate of data transmitted and the development of ever more powerful software constrain the transmission systems to process a large amount of data in a record time, hence the importance of extremely high-performance calculation modules. One of these modules is the complex number multiplier found in practically any signal processing device such as mobile telephones, for example.
A multiplication of two complex numbers generally involves four real multiplication operations and two real addition and subtraction operations. Specifically, the multiplication of two complex numbers (A+jB) and (C+jD) can be broken down as follows:
(
A+jB
)(
C+jD
)=(
AC−BD
)+
j
(
AD+BC
)=
R+jI
With R=AC−BD, the real part of the product and I=AD+BC, the imaginary part of the product.
This breakdown clearly involves four real multiplications (AC; BD; AD and BC) and two real additions and multiplications (AC−BD and AD+BC).
A, B, C and D are binary numbers represented according to a two's complement convention.
For a positive number, the first bit, called the “sign bit”, is equal to zero, and the following bits code the absolute value of the relevant decimal number in natural binary.
For a negative number, the sign bit is equal to one, and the following bits code the absolute value of the relevant decimal number in two's complement binary.
The real multiplication operations (AC, AD, BD, and BC) are particularly complex to implement.
In the prior art, use is made of a factoring technique for reducing the number of multiplication operations in return for addition and subtraction operations. This factorization, called “transformation by reduction of force” ultimately yields three multiplication operations and five addition and subtraction operations. A difficult multiplication operation has been swapped for three new addition and subtraction operations.
R=AC−BD=
(
A−B
)
C+
(
C−D
)
B
I=AD+BC=
(
A+B
)
D+
(
C−D
)
B
The five addition and subtraction operations are A−B, A+B, C−D, (A−B)C+(C−D)B, (A+B)D+(C−D)B
The three multiplication operations are (A−B)C, (A+B)D, (C−D)B
The terms (A−B), (A+B) and (C−D) are called “premultiplication operations” since they are intended to feed real multipliers included in a complex number multiplier.
This method is of real benefit as regards energy consumption, since one less real multiplier is synonymous with a saving of space on the electronic circuit, hence with a decrease in energy consumption, the area used by a real multiplier generally being three times greater than that of a real adder.
However, the calculation execution time for a complex number multiplier using the transformation by reduction of force, is greater than a direct complex number multiplier performing the four multiplication operations and the two addition and subtraction operations. The complex number multiplier is consequently slower.
This speed limitation is due essentially to the propagation of the carry of the least significant bit (LSB) to the most significant bit (MSB) in the course of addition and subtraction operations.
Complex number multiplier devices are known which use the transformation by reduction of force while improving the speed of execution of calculation as compared with the direct method. Such a device has been described by B. W. Y. Wei, H. Du and H. Chen in “A Complex-Number Multiplier Using Radix-4 Digits”, pages 84-90, 12
th
“Symposium of Computer Arithmetic”, Bath, England, 19 to 21 Jul. 1995.
In this method, the numbers are put into a redundant binary format, having numerous advantages. For example, the bit of a base two redundant binary number can take three values: −1, 0 or 1, and enables the decimal number of value 5 to be represented, in redundant binary format, by:
[0101], [011{overscore (1)}], [1{overscore (1)}1], [1{overscore (1)}01] or [10{overscore (
1
)}{overscore (
1
)}]
A decimal number can thus be represented by five redundant binary numbers. This redundancy makes it possible to reduce the rules for adding two binary numbers by confining oneself, for each bit of the result, to considering only the two bits of like rank of the two operands. Thus, the additions and subtractions are performed without carry propagation. The execution time for such an addition or subtraction operation remains constant irrespective of the length of the operands. Moreover, this representation requires no specific device for taking account of the sign bit.
In the method proposed by Wei et al, the two's complement binary numbers A, B, C and D are delivered to the input of a first stage composed of two subtractors and an adder, then the latter generates at the output the results (A−B), (A+B) and (C−D) in a redundant binary format.
These results, also called “partial products”, are represented by a specific base two coding. The modules forming the first stage and performing the three addition and subtraction operations comprise inverters only.
These results then undergo a conversion from the base two to a base four in a second stage so as to reduce the length of the binary numbers forming these results and to feed three real number multipliers in a third stage.
The final result is supplied by two real adders which, from the results of the three real multipliers, generate a real part and an imaginary part. However, this device comprises very many components, this being penalizing in terms of energy dissipation.
The invention aims to afford a solution to this problem by reducing the number of logic gates required on the complex number multiplier so as to decrease consumption.
An aim of the invention is to reduce the execution time for multiplying two complex numbers.
In a general manner, the complex number multiplier comprises an input which is followed by four processing stages. The input makes it possible to receive the real part A and the imaginary part B of a first complex number, and the real part C and the imaginary part D of a second complex number, the numbers A, B, C, D being two's complement coded binary numbers.
The first processing stage comprises subtraction means able to perform the operations A−B and C−D, the result of each subtraction being a base two binary number with a redundant binary format and a borrow-save coding, and an adder module able to perform the operation A+B, the result of this addition being a base two binary number with a redundant format and a carry-save coding.
The second processing stage comprises conversion means able to convert the numbers delivered by the first processing stage into base four coded binary numbers with a redundant format.
The third processing stage comprises multiplication means able to perform the operations (A−B)C, (C−D)B and (A+B)D, the result of these operations being base two coded numbers with a redundant format.
Finally, the fourth processing stage comprises two adders for computing the real part and the imaginary part of the product of the two input complex numbers from the numbers delivered by the third processing stage, these real and imaginary parts being to the base two according to a redundant binary format.
This implementation is achieved in accordance with the transformation by reduction of force. The latter therefore involves three multiplication operations and five addition operations. All the results from the four stages of the complex multiplier are in redundant binary format. This format makes it possible to perform the addition and subtraction operations with a car

Affiliated with

Also associated with

Rating

Complex number multiplier does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Complex number multiplier, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Complex number multiplier will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3305703