FPGA Central

How do i calculate sqrt(a^2 + b^2) in synthesizable VHDL?

The signals a and b are 32 bit signed fix point numbers (std_logic_vector
(31 downto 0)).

Marko S schrieb:
> How do i calculate sqrt(a^2 + b^2) in synthesizable VHDL?
> The signals a and b are 32 bit signed fix point numbers (std_logic_vector
> (31 downto 0)).

how accurate? how fast? latency?

a table with 64 Bits input, 32 Bits output will not fit into an FPGA
(but if you need the result with low latency, you might store some
precomputed data in an external ram)


or you could do something like max(a, b) + 0.5*min(a,b) ... and add a
newton raphson stage?


just for the sqrt(x) I once worked an idea to take len=ceil(log_2(x)) by
counting the length of x (leading 0s) ...
then you shift x>>(len/2) or something (+1?) ... this worked as a good
approximation and I added only one or two stages of a newton-raphson

The second approach was better in the first stage but uses more
cycles/ressources ... I'm not sure if the ressources balance on an FPGA
I did it for a TI-DSP - look at the thread "sqrt on C6414 DSP" on comp.dsp


bye,
Michael

Marko

a cordic algorithim in vectroing mode will calcualtes sqrt(a^2 - b^2)
which i am sure you can manipulate to get sqrt(a^2+b^2) by using signed
numbers and making b the negative (-6 as opposed to 6)

have a look at Ray Andrakas, survey of CORDIC algorithms for FPGA based
computers for infor on cordics, opencore.org also have a the vhdl for a
synthesisable cordic.

I ve just finished writing a excel function that performs the function
of a cordic if you want the vb for that then let me know and you can
have it test out your application before coding it.

good luck

Adam

Marko S schrieb:
> How do i calculate sqrt(a^2 + b^2) in synthesizable VHDL?

If you really need the results in random order, use cordic.
But often you can rearrange your computations to get away without the
root. That is your application?

Do you want to draw circles?

Kolja Sulimma

corerction the sqrt(a^2 - b^2) is for gven during the hyperbolic
extension, a normal cordic algorithim will provide sqrt(a^2 + b^2)

sorry about that

Ad

"Michael Schöberl" <[email protected]> wrote in message
news:4462f354$[email protected]..
> Marko S schrieb:
>> How do i calculate sqrt(a^2 + b^2) in synthesizable VHDL?
>> The signals a and b are 32 bit signed fix point numbers (std_logic_vector
>> (31 downto 0)).
>
> how accurate? how fast? latency?
>
> just for the sqrt(x) I once worked an idea to take len=ceil(log_2(x)) by
> counting the length of x (leading 0s) ...
> then you shift x>>(len/2) or something (+1?) ... this worked as a good
> approximation and I added only one or two stages of a newton-raphson
>
Hi Marko,
For square root, you could use modified Dijkstra's square root.

http://lib.tkk.fi/Diss/2005/isbn9512275279/article3.pdf

One clock per output bit. No multipliers.

HTH, Syms.

Thank you all. I will have a look at "Dijkstra's square root". I have 2000
clock cycles at 40 Mhz to complete the calculation (It should be enough). It
is used for calculating the AM envelop after demodulating the signal with a
coherent detector



You can se the principle of the detector at
http://www.cycom.co.uk/art1.html.





"Symon" <[email protected]> wrote in message
news:4462fbb4$0$15793$[email protected]..
> "Michael Schöberl" <[email protected]> wrote in message
> news:4462f354$[email protected]..
>> Marko S schrieb:
>>> How do i calculate sqrt(a^2 + b^2) in synthesizable VHDL?
>>> The signals a and b are 32 bit signed fix point numbers
>>> (std_logic_vector (31 downto 0)).
>>
>> how accurate? how fast? latency?
>>
>> just for the sqrt(x) I once worked an idea to take len=ceil(log_2(x)) by
>> counting the length of x (leading 0s) ...
>> then you shift x>>(len/2) or something (+1?) ... this worked as a good
>> approximation and I added only one or two stages of a newton-raphson
>>
> Hi Marko,
> For square root, you could use modified Dijkstra's square root.
>
> http://lib.tkk.fi/Diss/2005/isbn9512275279/article3.pdf
>
> One clock per output bit. No multipliers.
>
> HTH, Syms.
>

Marko S wrote:
> Thank you all. I will have a look at "Dijkstra's square root". I have 2000
> clock cycles at 40 Mhz to complete the calculation (It should be enough). It
> is used for calculating the AM envelop after demodulating the signal with a
> coherent detector
>
>
>
> You can se the principle of the detector at
> http://www.cycom.co.uk/art1.html.
>
>
>
>
>
> "Symon" <[email protected]> wrote in message
> news:4462fbb4$0$15793$[email protected]..
>
>>"Michael Schöberl" <[email protected]> wrote in message
>>news:4462f354$[email protected]..
>>
>>>Marko S schrieb:
>>>
>>>>How do i calculate sqrt(a^2 + b^2) in synthesizable VHDL?
>>>>The signals a and b are 32 bit signed fix point numbers
>>>>(std_logic_vector (31 downto 0)).
>>>
>>>how accurate? how fast? latency?
>>>
>>>just for the sqrt(x) I once worked an idea to take len=ceil(log_2(x)) by
>>>counting the length of x (leading 0s) ...
>>>then you shift x>>(len/2) or something (+1?) ... this worked as a good
>>>approximation and I added only one or two stages of a newton-raphson
>>>
>>
>>Hi Marko,
>>For square root, you could use modified Dijkstra's square root.
>>
>>http://lib.tkk.fi/Diss/2005/isbn9512275279/article3.pdf
>>
>>One clock per output bit. No multipliers.
>>
>>HTH, Syms.
>>
>
>
>

You aren't really looking for square root, you are looking for vector
magnitude. Vector magnitude can be computed without computing the
square root. For arbitrary precision, you can use the cordic algorithm
in vectoring mode. It basically rotates the vector to the I axis using
a series of progressively smaller fixed angle rotations selected so that
each elemental rotation is done with a shift and add operation. After
rotating the vector the I axis, the magnitude is read directly from the
non-zero (I component) of the rotated vector. If you don't need a lot
of precision, there are table methods and linear approximations (the
most famous is "larger plus half smaller" that will often get you a good
enough answer with less computation. Either way, computing magnitude
using a square root is going about it the hard way (hardware-wise
anyway). For 32 bit arguments, CORDIC is going to be your best bet.

If you are targetting programmable hardware (which you most possible
are), you can get IP cores to work for you. Check out opencores.org or
Xilinx or Altera websites to find cores that provide functions you need.

Do you need the square root, or can you work with just the "sum of the
squares" (perhaps scaled)? If this is used for thresholding (amplitude
comparison), then the less-than/equal/greater-than relationship still holds.

JTW

"Marko S" <[email protected]> wrote in message
news:44630af8$0$15782$[email protected]..
> Thank you all. I will have a look at "Dijkstra's square root". I have 2000
> clock cycles at 40 Mhz to complete the calculation (It should be enough).
> It is used for calculating the AM envelop after demodulating the signal
> with a coherent detector
>
>
>
> You can se the principle of the detector at
> http://www.cycom.co.uk/art1.html.
>
>
>
>
>
> "Symon" <[email protected]> wrote in message
> news:4462fbb4$0$15793$[email protected]..
>> "Michael Schöberl" <[email protected]> wrote in message
>> news:4462f354$[email protected]..
>>> Marko S schrieb:
>>>> How do i calculate sqrt(a^2 + b^2) in synthesizable VHDL?
>>>> The signals a and b are 32 bit signed fix point numbers
>>>> (std_logic_vector (31 downto 0)).
>>>
>>> how accurate? how fast? latency?
>>>
>>> just for the sqrt(x) I once worked an idea to take len=ceil(log_2(x)) by
>>> counting the length of x (leading 0s) ...
>>> then you shift x>>(len/2) or something (+1?) ... this worked as a good
>>> approximation and I added only one or two stages of a newton-raphson
>>>
>> Hi Marko,
>> For square root, you could use modified Dijkstra's square root.
>>
>> http://lib.tkk.fi/Diss/2005/isbn9512275279/article3.pdf
>>
>> One clock per output bit. No multipliers.
>>
>> HTH, Syms.
>>
>
>

Thank you



Now I have read the CORDIC FAQ at dspGuru. I read how to calculate the
magnitude of a complex number with the CORDIC. And I have tried it in Excel.
So now I'm going to implement it in VHDL.



I have heard about CORDIC before but newer sat down to read about it.



Thank you all for your help on this.





"Ray Andraka" <[email protected]> wrote in message
news:KuK8g.18376$ZW3.2280@dukeread04...
> Marko S wrote:
>> Thank you all. I will have a look at "Dijkstra's square root". I have
>> 2000 clock cycles at 40 Mhz to complete the calculation (It should be
>> enough). It is used for calculating the AM envelop after demodulating the
>> signal with a coherent detector
>>
>>
>>
>> You can se the principle of the detector at
>> http://www.cycom.co.uk/art1.html.
>>
>>
>>
>>
>>
>> "Symon" <[email protected]> wrote in message
>> news:4462fbb4$0$15793$[email protected]..
>>
>>>"Michael Schöberl" <[email protected]> wrote in message
>>>news:4462f354$[email protected]..
>>>
>>>>Marko S schrieb:
>>>>
>>>>>How do i calculate sqrt(a^2 + b^2) in synthesizable VHDL?
>>>>>The signals a and b are 32 bit signed fix point numbers
>>>>>(std_logic_vector (31 downto 0)).
>>>>
>>>>how accurate? how fast? latency?
>>>>
>>>>just for the sqrt(x) I once worked an idea to take len=ceil(log_2(x)) by
>>>>counting the length of x (leading 0s) ...
>>>>then you shift x>>(len/2) or something (+1?) ... this worked as a good
>>>>approximation and I added only one or two stages of a newton-raphson
>>>>
>>>
>>>Hi Marko,
>>>For square root, you could use modified Dijkstra's square root.
>>>
>>>http://lib.tkk.fi/Diss/2005/isbn9512275279/article3.pdf
>>>
>>>One clock per output bit. No multipliers.
>>>
>>>HTH, Syms.
>>>
>>
>>
>>
>
> You aren't really looking for square root, you are looking for vector
> magnitude. Vector magnitude can be computed without computing the square
> root. For arbitrary precision, you can use the cordic algorithm in
> vectoring mode. It basically rotates the vector to the I axis using a
> series of progressively smaller fixed angle rotations selected so that
> each elemental rotation is done with a shift and add operation. After
> rotating the vector the I axis, the magnitude is read directly from the
> non-zero (I component) of the rotated vector. If you don't need a lot of
> precision, there are table methods and linear approximations (the most
> famous is "larger plus half smaller" that will often get you a good enough
> answer with less computation. Either way, computing magnitude using a
> square root is going about it the hard way (hardware-wise anyway). For 32
> bit arguments, CORDIC is going to be your best bet.

<[email protected]> wrote in message
news:[email protected] ups.com...
> If you are targetting programmable hardware (which you most possible
> are), you can get IP cores to work for you. Check out opencores.org or
> Xilinx or Altera websites to find cores that provide functions you need.
>

The Square root function is available as a free megafunction in Altera
Quartus. I have just used it as part of my new 32 bit embedded processor
design in a Stratix part.

A 32 bit square root with a 4 clock pipeline runs in excess of 40MHz in a C7
part.


Slurp