Digital Signal Processing Tricks - Fast multiplication of complex numbers - Embedded.com

Digital Signal Processing Tricks – Fast multiplication of complex numbers

The multiplication of two complex numbers is one of themost common functions performed in digital signal processing.

It's mandatory in all discrete and fast Fourier transformation algorithms,necessary for graphics transformations, and used in processing digitalcommunications signals. Be it in hardware or software, it's always toour benefit to streamline the processing necessary to perform a complexmultiply whenever we can.

If the available hardware can perform three additions faster than asingle multiplication, there's a way to speed up a complex multiplyoperation.  The multiplication of two complex numbers, a + jb and c + jd, results in thecomplex product

R + jI = (a + jb)(c + jd) = (ac -bd) + j(bc + ad). (Eq. 13-14)

We can see that Eq. (13 -14) requires four multiplications and twoadditions. (From a computationalstandpoint we'll assume a subtraction is equivalent to an addition. )

Instead of using Eq. (13 -14), we can calculate the followingintermediate values

k1 = a(c + d) k2 = d(a + b)      (Eq. 13 -15)
k3 = c(b – a).

We then perform the following operations to get the final R and I

R = k1 – k2 , and I = k1 + k3. (Eq. 13 -16)

The reader is invited to plug the k values from Eq. (13 -15) intoEq.(13 -16) to verify that the expressions in Eq. (13 -16) are equivalenttoEq. (13 -14).

The intermediate values in Eq. (13 -15) required three additions andthree multiplications, while the results in Eq. (13 -16) required twomore additions.

So we traded one of the multiplications required in Eq. (13 -14) forthree addition operations needed by Eq. (13 -15) and Eq. (13 -16).

If our hardware uses fewer clock cycles to perform three additionsthan a single multiplication, we may well gain overall processing speedby using Eq. (13 -15) and Eq. (13 -16) instead of Eq. (13 -14) forcomplexmultiplication.

Usedwith the permission of the publisher, Prentice Hall, this on-goingseries of articles is based on copyrighted material from “UnderstandingDigital Signal Processing, Second Edition” by Richard G. Lyons. Thebook can be purchased on line.

Richard Lyons is a consultingsystems engineer and lecturer with Besser Associates. As alecturer with Besser and an instructor for the University of CaliforniaSanta Cruz Extension, Lyons has delivered digitasl signal processingseminars and training course at technical conferences as well atcompanies such as Motorola, Freescale, Lockheed Martin, TexasInstruments, Conexant, Northrop Grumman, Lucent, Nokia, Qualcomm,Honeywell, National Semiconductor, General Dynamics and Infinion.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.