Complex Multiply

A

Ann

I am trying to write a sunction for complex multiplication of 2
complex numbers

function complex_multiply(a : signed; b: signed; c : signed; d:
signed) return signed;
(a + bi)(c + di) = [ac - bd] + [ad + bc]i.

I am not sure on how I would return the real and imaginary part of the
result. As per my understanding functions can return only one value.
How do i represent the inputs and outputs? I want to write code in
VHDL to be implemented on an FPGA.
 
N

Nicolas Matringe

Ann a écrit :
I am trying to write a sunction for complex multiplication of 2
complex numbers

function complex_multiply(a : signed; b: signed; c : signed; d:
signed) return signed;
(a + bi)(c + di) = [ac - bd] + [ad + bc]i.

I am not sure on how I would return the real and imaginary part of the
result. As per my understanding functions can return only one value.
How do i represent the inputs and outputs? I want to write code in
VHDL to be implemented on an FPGA.

Hi
Define your complex number as an array of two signed numbers

type complex is array(0 to 1) of signed(your_range);

function complex_multiply(a : complex; b : complex) return complex;
(a(0) + a(1).i)(b(0) + b(0).i) = [a(0)b(0)-a(1)b(1)] + [a(0)b(1) +
a(1)b(0)]i

You could even overload the '*' operator for type complex

Nicolas
 
K

KJ

I am trying to write a sunction for complex multiplication of 2
complex numbers

function complex_multiply(a : signed; b: signed; c : signed; d:
signed) return signed;
(a + bi)(c + di) = [ac - bd] + [ad + bc]i.

I am not sure on how I would return the real and imaginary part of the
result. As per my understanding functions can return only one value.
How do i represent the inputs and outputs? I want to write code in
VHDL to be implemented on an FPGA.

Define a new complex record type...
type t_My_Complex_Type is record
Real: signed;
Imag: signed;
end record;

Now your function would be defined as

function complex_multiply(a, b : t_My_Complex_Type) return
t_My_Complex_Type is
variable RetVal: t_My_Complex_Type;
begin
RetVal.Real := a.real * b.real - a.imag * b.imag;
RetVal.Imag := a.real * b.imag + b.real * a.imag;
return(RetVal);
function complex_multiply;

If you're really feeling gutzy, you can instead call the function
"*" (with the double quotes) and you'll be defining an override for
the multiply operator so you could use your function like this...

C <= A * B;

instead of

C <= complex_multiply(A,B);

But I would suggest getting it working with the new type and seeing
how that all works first. Record types are synthesizable.

Kevin Jennings
 
N

Nicolas Matringe

KJ a écrit :
I am trying to write a sunction for complex multiplication of 2
complex numbers

function complex_multiply(a : signed; b: signed; c : signed; d:
signed) return signed;
(a + bi)(c + di) = [ac - bd] + [ad + bc]i.

I am not sure on how I would return the real and imaginary part of the
result. As per my understanding functions can return only one value.
How do i represent the inputs and outputs? I want to write code in
VHDL to be implemented on an FPGA.

Define a new complex record type...
type t_My_Complex_Type is record
Real: signed;
Imag: signed;
end record;

Right, that's cleaner (more readable) than my solution with an array.

Nicolas
 
F

FPGA

I am trying to write a sunction for complex multiplication of 2
complex numbers
function complex_multiply(a : signed; b: signed; c : signed; d:
signed) return signed;
(a + bi)(c + di) = [ac - bd] + [ad + bc]i.
I am not sure on how I would return the real and imaginary part of the
result. As per my understanding functions can return only one value.
How do i represent the inputs and outputs? I want to write code in
VHDL to be implemented on an FPGA.

Define a new complex record type...
type t_My_Complex_Type is record
   Real:  signed;
   Imag: signed;
end record;

Now your function would be defined as

function complex_multiply(a, b : t_My_Complex_Type) return
t_My_Complex_Type is
   variable RetVal: t_My_Complex_Type;
begin
  RetVal.Real := a.real * b.real - a.imag * b.imag;
  RetVal.Imag := a.real * b.imag + b.real * a.imag;
  return(RetVal);
function complex_multiply;

If you're really feeling gutzy, you can instead call the function
"*" (with the double quotes) and you'll be defining an override for
the multiply operator so you could use your function like this...

C <= A * B;

instead of

C <= complex_multiply(A,B);

But I would suggest getting it working with the new type and seeing
how that all works first.  Record types are synthesizable.

Kevin Jennings

It gave me errors. The result would be twice as long as the lengths of
a or b. So RetVal cannot be of type t_My_Complex_Type. I did the
following and it is compiling fine.

type t_My_Complex_Type is record
Real: signed(31 downto 0);
Imag: signed(31 downto 0);
end record;

type Result_Complex_Type is record
Real: signed(63 downto 0);
Imag: signed(63 downto 0);
end record;

function complex_multiply(a, b : t_My_Complex_Type) return
Result_Complex_Type is
variable RetVal: Result_Complex_Type;
begin
RetVal.Real := a.real * b.real - a.imag * b.imag;
RetVal.Imag := a.real * b.imag + b.real * a.imag;
return(RetVal);
end function complex_multiply;

How do i simulate this? What should be the type of a and b in the
simulation file. Should they be 64 bit vectors each ?
 
K

KJ

I am trying to write a sunction for complex multiplication of 2
complex numbers
function complex_multiply(a : signed; b: signed; c : signed; d:
signed) return signed;
(a + bi)(c + di) = [ac - bd] + [ad + bc]i.
I am not sure on how I would return the real and imaginary part of the
result. As per my understanding functions can return only one value.
How do i represent the inputs and outputs? I want to write code in
VHDL to be implemented on an FPGA.

Define a new complex record type...
type t_My_Complex_Type is record
Real: signed;
Imag: signed;
end record;

Now your function would be defined as

function complex_multiply(a, b : t_My_Complex_Type) return
t_My_Complex_Type is
variable RetVal: t_My_Complex_Type;
begin
RetVal.Real := a.real * b.real - a.imag * b.imag;
RetVal.Imag := a.real * b.imag + b.real * a.imag;
return(RetVal);
function complex_multiply;

If you're really feeling gutzy, you can instead call the function
"*" (with the double quotes) and you'll be defining an override for
the multiply operator so you could use your function like this...

C <= A * B;

instead of

C <= complex_multiply(A,B);

But I would suggest getting it working with the new type and seeing
how that all works first. Record types are synthesizable.

Kevin Jennings
It gave me errors. The result would be twice as long as the lengths of
a or b. So RetVal cannot be of type t_My_Complex_Type. I did the
following and it is compiling fine.

Well it depends on just how much precision you think you need in the
calculation. I'm guessing that 32 bits would've been enough. The range for
each of the elements of the complex type should be made to be large enough
to handle whatever range of complex numbers that you plan to be able to use.
That being the case, all that is needed then is to strip off the lower bits
of the result as shown below

RetVal.Real := (a.real * b.real - a.imag * b.imag)(a'range);
RetVal.Imag := (a.real * b.imag + b.real * a.imag)(a'range);

How do i simulate this? What should be the type of a and b in the
simulation file. Should they be 64 bit vectors each ?

a and b need to be whatever width you need them to be to give you whatever
precision you need for your calculations. Whether that's 5 bits, 8 bits, 32
bits or something else I can't say since I don't know what precision you
need for your application.

Kevin Jennings
 
P

pontus.stenstrom

I am trying to write a sunction for complex multiplication of 2
complex numbers

function complex_multiply(a : signed; b: signed; c : signed; d:
signed) return signed;
(a + bi)(c + di) = [ac - bd] + [ad + bc]i.

I am not sure on how I would return the real and imaginary part of the
result. As per my understanding functions can return only one value.
How do i represent the inputs and outputs? I want to write code in
VHDL to be implemented on an FPGA.


Note that you can save a multiplier:
ac-bd = a(c-d) + d(a-b)
ad+bc = b(c+d) + d(a-b)
and if (c,d) is a constant, you can precompute (c-d) and (c+d).

Pontus
 
K

KJ

Slight correction to previous post. Instead of

RetVal.Real := (a.real * b.real - a.imag * b.imag)(a'range);
RetVal.Imag := (a.real * b.imag + b.real * a.imag)(a'range);

It should be

RetVal.Real := (a.real * b.real - a.imag * b.imag)
(a.real'range);
RetVal.Imag := (a.real * b.imag + b.real * a.imag)
(a.imag'range);

KJ
 
A

Ann

Slight correction to previous post.  Instead of

     RetVal.Real := (a.real * b.real - a.imag * b.imag)(a'range);
     RetVal.Imag := (a.real * b.imag + b.real * a.imag)(a'range);

It should be

     RetVal.Real := (a.real * b.real - a.imag * b.imag)
(a.real'range);
     RetVal.Imag := (a.real * b.imag + b.real * a.imag)
(a.imag'range);

KJ

Thanks a bunch. I will try this out.
 
J

Jonathan Bromley

Ann a écrit :
Define your complex number as an array of two signed numbers
type complex is array(0 to 1) of signed(your_range);

The problem with that approach, and also if you try
to use a record...

type complex_r is record
Re: signed(your_range);
Im: signed(your_range);
end record;

.... is that "your_range" must be fixed at the outset.

There is an alternative approach.

type complex_bit is record
Re: std_logic;
Im: std_logic;
end record;
type complex is array (natural range <>) of complex_bit;

Now I can choose the width of my complex numbers easily:

...
variable complex_8: complex(7 downto 0);
variable complex_16: complex(15 downto 0);
...

Doing arithmetic then becomes just a little messy, but
it's easy enough to write a package that does the job.
The key is a group of functions to extract real and
imaginary parts from the complex object, and to compose
complex values from existing real and imaginary parts:

function Re(c: complex) return signed is
variable result: signed(c'range);
begin
for i in c'range loop
result(i) := c(i).Re;
end loop;
return result;
end;
(and, of course, similarly for Im)

function to_complex(Re: signed; Im: signed := "0")
return complex is
constant width: positive := max(Re'length, Im'length);
variable norm_Re, norm_Im: signed(width-1 downto 0);
variable c: complex(width-1 downto 0);
begin
norm_Re := resize(Re, width);
norm_Im := resize(Im, width);
for i in c'range loop
c(i) := (norm_Re(i), norm_Im(i));
end loop;
return c;
end;

function to_complex(Re: integer; Im: integer; bits: positive)
return complex is
begin
return to_complex(to_signed(Re, bits), to_signed(Im, bits));
end;

These functions are pretty clumsy, but will synthesize to
nothing more than a bunch of wires, so that's OK. And then
you can easily overload the arithmetic operators...

function "+"(L, R: complex) return complex is
begin
return to_complex( Re(L) + Re(R), Im(L) + Im(R) );
end;

function "*"(L, R: complex) return complex is
begin
return to_complex( Re(L) * Re(R) - Im(L) * Im(R),
Im(L) * Re(R) + Re(L) * Im(R) );
end;

Once again, fully synthesisable. "*" will return an
appropriately widened result, and you can then pick
whatever bits you need from that wide product.

You'll also need resize(), ability to do arithmetic
between complex and scalar values (both integer and
signed), and a few other things. Writing a good
arithmetic package is non-trivial.

All this stuff can go into a package. If your synth
tool can cope with numeric_std and records, it can cope
with this. Yes, I know simulation will be a little slow
because of all the packing and unpacking of bits into
the complex data type, but I reckon that's a small price
to pay for the convenience and regularity of this sort
of thing:

...
use work.complex_pkg.all;
...
variable A, B, result : complex(7 downto 0);
variable product16 : complex(15 downto 0);
...
product16 := A*B;
result := product16(15 downto 8);

I have most of this done already; would people find it
useful if I were to work it up in detail? (Oh, and
would I get some of the credit for the assignments?)
--
Jonathan Bromley, Consultant

DOULOS - Developing Design Know-how
VHDL * Verilog * SystemC * e * Perl * Tcl/Tk * Project Services

Doulos Ltd., 22 Market Place, Ringwood, BH24 1AW, UK
(e-mail address removed)
http://www.MYCOMPANY.com

The contents of this message may contain personal views which
are not the views of Doulos Ltd., unless specifically stated.
 
J

Jonathan Bromley

That being the case, all that is needed then is to strip off the lower bits
of the result as shown below

RetVal.Real := (a.real * b.real - a.imag * b.imag)(a'range);
RetVal.Imag := (a.real * b.imag + b.real * a.imag)(a'range);

Urrrm, I don't think you can do that.

You can only subscript an object (variable or signal),
not an expression. You'll need a temporary variable,
or perhaps the resize() function if you can live with
the risk of MSBs getting lost by resize's truncation.
--
Jonathan Bromley, Consultant

DOULOS - Developing Design Know-how
VHDL * Verilog * SystemC * e * Perl * Tcl/Tk * Project Services

Doulos Ltd., 22 Market Place, Ringwood, BH24 1AW, UK
(e-mail address removed)
http://www.MYCOMPANY.com

The contents of this message may contain personal views which
are not the views of Doulos Ltd., unless specifically stated.
 
M

Mike Treseler

Jonathan said:
...All this stuff can go into a package. If your synth
tool can cope with numeric_std and records, it can cope
with this. Yes, I know simulation will be a little slow
because of all the packing and unpacking of bits into
the complex data type, but I reckon that's a small price
to pay for the convenience and regularity of this sort
of thing:

I reckon you are correct.

...
I have most of this done already; would people find it
useful if I were to work it up in detail?

It would be an excellent (and rare) example
of the details of packaging a useful type.

(Oh, and would I get some of the credit for the assignments?)

Oh yes. Automatic A on the midterm ;)

-- Mike Treseler
 
K

KJ

Urrrm, I don't think you can do that.
Well you also snipped out the wrong portion of my reply where I had my
correction...but you're correct even the correction was flawed, you do
need the resize function...good catch...So updating it yet again

RetVal.Real := resize(a.real * b.real - a.imag * b.imag,
a.real'length);
RetVal.Imag := resize(a.real * b.imag + b.real * a.imag,
a.imag'length);
or perhaps the resize() function if you can live with
the risk of MSBs getting lost by resize's truncation.

When choosing the number of bits of precision, one would choose
something large enough so that the result of all mathematical
operations that one is contemplating using will fit into that range as
well so there would be no truncation problems. That's no different
than when using 'integer' type. Proper sizing and numerical
representation though is something that needs to be done before any
coding.

Kevin Jennings
 
K

KJ

On Jan 18, 11:45 am, Jonathan Bromley <[email protected]>
wrote:

I have most of this done already; would people find it
useful if I were to work it up in detail?  

Demo of good techniques are always nice to see.
(Oh, and
would I get some of the credit for the assignments?)

I'll give you a star....then again, you turned in the assignment 4
days late, might have to dock you for that.

Kevin Jennings
 
K

KJ

Jonathan Bromley said:
On Mon, 14 Jan 2008 21:20:29 +0100, Nicolas Matringe wrote:

Yes, I know simulation will be a little slow
because of all the packing and unpacking of bits into
the complex data type, but I reckon that's a small price
to pay for the convenience and regularity of this sort
of thing:

Yet another alternative is to represent the complex as a single array of
std_logic with one half dedicated to 'real', the other half to 'imaginary'.
Now the 'Re' and 'Im' functions are simple one liners that strip out the
appropriate range of bits. Both alternatives provide the same end user
function of producing a complex type that can be of any size that does not
need to be determined a priori.

When debugging, both representations present a challenge for the user to
assemble the bits into a complex number but the single vector approach would
have a bit of an advantage if the number of bits happens to be a multiple of
4 since the number could be displayed in hex in a wave/variables window and
more easily split into the appropriate 'real' and 'imaginary' components of
the complex number.

Since the single vector representation concatenates two equally sized
elements, what the user specifies for a 'width' is the total number of bits
in the complex type (i.e. variable x: complex(15 downto 0) would be used to
get 8 bit precision on the real and imaginary parts).

Both should synthesize down to the same thing (but I haven't actually tested
this).

The single vector representation might also be a good candidate for a
protected type so that the user is completely insulated from details of the
internal representation...but I haven't tried synthesis tools on protected
types yet.

Putting your code into a loop for 2,000,000 iterations vsimk took 58
seconds. Using the single vector representation the same number of loops
took 19 seconds for a 3x sim time advantage.

Kevin Jennings
 
J

Jonathan Bromley

Yet another alternative is to represent the complex as a single array of
std_logic with one half dedicated to 'real', the other half to 'imaginary'.
Now the 'Re' and 'Im' functions are simple one liners that strip out the
appropriate range of bits. Both alternatives provide the same end user
function of producing a complex type that can be of any size that does not
need to be determined a priori.
Agreed.

When debugging, both representations present a challenge for the user to
assemble the bits into a complex number but the single vector approach would
have a bit of an advantage

You're right. I hadn't really thought about that hard enough.
I was intending to provide a bunch of "to-string" conversions
(after the manner of std_logic_textio) and also some
non-synthesisable conversions to/from math_complex, to
make debugging and testbench reporting more convenient.
Since the single vector representation concatenates two equally sized
elements, what the user specifies for a 'width' is the total number of bits
in the complex type (i.e. variable x: complex(15 downto 0) would be used to
get 8 bit precision on the real and imaginary parts).

Yes. I must admit that I see that as a significant drawback,
but obviously it's fairly easy to deal with.
Both should synthesize down to the same thing
(but I haven't actually tested this).

I'd be amazed if it wasn't the case. My experience on my
fixed-point package (superseded by the IEEE one) was that
you can do quite complicated things with constants,
subscript calculations and so on, and synthesis will
simply do The Right Thing.
The single vector representation might also be a good candidate for a
protected type so that the user is completely insulated from details of the
internal representation

I guess that would be true for either form...
...but I haven't tried synthesis tools on protected
types yet.

I don't think protected types are, or were intended
to be, synthesisable.
Putting your code into a loop for 2,000,000 iterations vsimk took 58
seconds. Using the single vector representation the same number of loops
took 19 seconds for a 3x sim time advantage.

Interesting, thanks for the experiment. I'm actually quite surprised
that the difference is so small; I'd have expected your representation
to be dramatically faster. I suspect the cost of the unsigned."+"
and unsigned."*" operations is swamping the effect of the
extract/compose functions; if you were to stub-out the complex
multiply with, for example, something that simply concatenated
the two operands:

return to_complex(Re(L) & Re(R), Im(L) & Im(R));

then you might more clearly see the performance hit from my
bit-pairs representation.
--
Jonathan Bromley, Consultant

DOULOS - Developing Design Know-how
VHDL * Verilog * SystemC * e * Perl * Tcl/Tk * Project Services

Doulos Ltd., 22 Market Place, Ringwood, BH24 1AW, UK
(e-mail address removed)
http://www.MYCOMPANY.com

The contents of this message may contain personal views which
are not the views of Doulos Ltd., unless specifically stated.
 
K

KJ

Jonathan Bromley said:
I'd be amazed if it wasn't the case. My experience on my
fixed-point package (superseded by the IEEE one) was that
you can do quite complicated things with constants,
subscript calculations and so on, and synthesis will
simply do The Right Thing.

I'd be surprised also if it wasn't...but I've also generated enough service
requests into synthesis tool providers to know that surprises pop up all
over the place...but you're right I wouldn't expect it to be any problem.
Now that synthesis tools can (or mostly) handle 'time' and 'real' for
computing constants the need to leave the synthesizable subset of the VHDL
language and use some other tool to compute a file that you then need to
import in some fashion is going down.
I don't think protected types are, or were intended
to be, synthesisable.

Yet, these two examples also demonstrate a reasonable reason why maybe they
should.
Interesting, thanks for the experiment. I'm actually quite surprised
that the difference is so small; I'd have expected your representation
to be dramatically faster. I suspect the cost of the unsigned."+"
and unsigned."*" operations is swamping the effect of the
extract/compose functions; if you were to stub-out the complex
multiply with, for example, something that simply concatenated
the two operands:

return to_complex(Re(L) & Re(R), Im(L) & Im(R));

then you might more clearly see the performance hit from my
bit-pairs representation.

Not too much different, vector of records using the above mentioned stub for
+ and * is 4x slower than single vector instead of 3x to compute proper
results.
Stubbing out on the vector of records completed in 49 seconds
Stubbing out on the flat single vector completed in 12 seconds.

Since the Achilles heal of the vector of records approach is that more
precision will proportionately increase the number of times through the
inner loops unravelling the real and imaginary parts in order to do the
math, it's worth investigating the simulation time hit.

Doubling the vector widths results in a 6x difference now.
Stubbing out on the vector of records (16 bit instead of 8 bit components)
completed in 79 seconds
Stubbing out on the flat single vector (16 bit instead of 8 bit components)
completed in 13 seconds.

Doubling the vector widths yet again results in a 10x difference now.
Stubbing out on the vector of records (32 bit instead of 16 bit components)
completed in 142 seconds
Stubbing out on the flat single vector (32 bit instead of 16 bit components)
completed in 14 seconds.

Kevin Jennings
 
K

KJ

KJ said:
Doubling the vector widths results in a 6x difference now.
Stubbing out on the vector of records (16 bit instead of 8 bit components)
completed in 79 seconds
Stubbing out on the flat single vector (16 bit instead of 8 bit
components) completed in 13 seconds.

Doubling the vector widths yet again results in a 10x difference now.
Stubbing out on the vector of records (32 bit instead of 16 bit
components) completed in 142 seconds
Stubbing out on the flat single vector (32 bit instead of 16 bit
components) completed in 14 seconds.

As one last sim time data point to add, using a record with integers for the
real and imaginary parts is 8x faster than the flat single vector...but that
of course restricts you to using a fixed integer range regardless of what
the data requirements are. But if there comes a day when records can be
parameterized then this would likely be the best approach.

Kevin Jennings
 
A

Ann

As one last sim time data point to add, using a record with integers for the
real and imaginary parts is 8x faster than the flat single vector...but that
of course restricts you to using a fixed integer range regardless of what
the data requirements are.  But if there comes a day when records can be
parameterized then this would likely be the best approach.

Kevin Jennings- Hide quoted text -

- Show quoted text -

Thank you all for all your comments. It really helped a lot. I wonder
how many yrs of experience it takes to know so much stuff.
 
A

Andy

Yet another alternative is to represent the complex as a single array of
std_logic with one half dedicated to 'real', the other half to 'imaginary'.
Now the 'Re' and 'Im' functions are simple one liners that strip out the
appropriate range of bits. Both alternatives provide the same end user
function of producing a complex type that can be of any size that does not
need to be determined a priori.

When debugging, both representations present a challenge for the user to
assemble the bits into a complex number but the single vector approach would
have a bit of an advantage if the number of bits happens to be a multiple of
4 since the number could be displayed in hex in a wave/variables window and
more easily split into the appropriate 'real' and 'imaginary' components of
the complex number.

Since the single vector representation concatenates two equally sized
elements, what the user specifies for a 'width' is the total number of bits
in the complex type (i.e. variable x: complex(15 downto 0) would be used to
get 8 bit precision on the real and imaginary parts).

Both should synthesize down to the same thing (but I haven't actually tested
this).

The single vector representation might also be a good candidate for a
protected type so that the user is completely insulated from details of the
internal representation...but I haven't tried synthesis tools on protected
types yet.

Putting your code into a loop for 2,000,000 iterations vsimk took 58
seconds. Using the single vector representation the same number of loops
took 19 seconds for a 3x sim time advantage.

Kevin Jennings

Taking that approach, and borrowing a page from the fixed point
package, you could define the single vector such that natural indices
indicated the real portion, and negative indices indicated the
imaginary portion, in case you wanted different widths for real and
imaginary.

Andy
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,755
Messages
2,569,537
Members
45,020
Latest member
GenesisGai

Latest Threads

Top