0
\$\begingroup\$

I'm trying to predict/handle the bit growth that occurs when implementing a complex multiplier using Gauss' method. I am looking to implement this multiplier in VHDL. The FPGA I use has a limited number of DSP elements, and so I anticipate that should I implement this multiplier correctly, it would reduce the number of DSP required per complex multiplication by 1.

Should A = (a+ib) have bit width m, and B = (c+id) have bit width n, then classically:

C = A x B = (a+ib) x (c+id) = ac - bd + i(ad + bc)

will have bit width of m + n + 1 for both its real and imaginary parts respectively.

Now, should I use Gauss' method of complex multiplication whereby only three multiplications are performed, namely ac, bd and (a+b)(c+d), then:

C = A x B = (a+ib) x (c+id) = ac -bd + i[(a+b)(c+d) - ac-bd], Here, we'd find that the real part will have a bit width of m + n + 1 as before, but the imaginary part will now have a bit width of m + n + 3.

Please can someone confirm whether this is really the case (I've checked a few times but could be wrong), and then further give me an idea as to how to handle the additional bit growth in the imaginary term (since I require that it have the same bit with as the real).

Thank you in advance.

\$\endgroup\$

1 Answer 1

0
\$\begingroup\$

The term a+b have a bit width of m+1, c+d have a bit width of n+1, (a+b)*(c+d) have a bit width of m+n+2. The term ac+bd have a bit width of m+n+1. If we add/subtract two independent terms, one of a bit width m+n+2 and the other of a bit width m+n+1, the bit width of the result may be as large as m+n+3, but for the expression (a+b)*(c+d) - a*c - b*d we know that the result is a*d + b*c with a bit width of m+n+1. Therefore, we can safely restrict the register bitness by a value of m+n+2 and be sure that there will be no carry from the register senior bit. More than that, we know beforehand that the senior bit of the final result will be zero. The +1 bitness of the intermediate result (a+b)*(c+d) is a payment for one less multiplication and I'm not sure we can get rid of the (m+n+2)-bit register while keeping the advantages of improved complex multiplication.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.