Fix point square root

Hi,
i am trying to implement a fixpoint square root in vhdl.
The radicant consists of integer as well as fractional bits like 4.23 - dec.
Does anyone know a synthesiable algorithm ?
Thanks in advance
Christian

Christian

On 25 Apr 2005 12:17:27 -0700, (Christian) wrote:

>Hi,
>i am trying to implement a fixpoint square root in vhdl.
>The radicant consists of integer as well as fractional bits like 4.23 - dec.
>Does anyone know a synthesiable algorithm ?
>Thanks in advance
>Christian

The first link here seems nice:
http://www.google.com/search?hl=en&q...nt+square+root

mk

mk<kal*@dspia.*comdelete> wrote in message news:<>. ..
> On 25 Apr 2005 12:17:27 -0700, (Christian) wrote:
>
> >Hi,
> >i am trying to implement a fixpoint square root in vhdl.
> >The radicant consists of integer as well as fractional bits like 4.23 - dec.
> >Does anyone know a synthesiable algorithm ?
> >Thanks in advance
> >Christian
>
> The first link here seems nice:
> http://www.google.com/search?hl=en&q...nt+square+root

Thanks for your reply ! I tried to translate the c source code into
vhdl code but i don't get the right results.
If anyone has an idea what i did wrong, this would be very nice

Christian

typedef long TFract; /* 2 integer bits, 30 fractional bits */
TFract
FFracSqrt(TFract x)
{
register unsigned long root, remHi, remLo, testDiv, count;
root = 0; /* Clear root */
remHi = 0; /* Clear high part of partial remainder */
remLo = x; /* Get argument into low part of partial remainder */
count = 30; /* Load loop counter */
Apple Computer, Inc. Media Technologies: Computer Graphics Page 1
Turkowski Fixed Point Square Root 3 October 1994
do {
remHi = (remHi<<2) | (remLo>>30); remLo <<= 2; /* get 2 bits of arg */
root <<= 1; /* Get ready for the next bit in the root */
testDiv = (root << 1) + 1; /* Test radical */
if (remHi >= testDiv) {
remHi -= testDiv;
root++;
}
} while (count-- != 0);
return(root);
}


library ieee;
use ieee.std_logic_1164.all;
use ieee.std_logic_arith.all;
use ieee.std_logic_unsigned.all;

entity SQUARE_ROOT is

port ( arg : in std_logic_vector(31 downto 0);

output : out std_logic_vector(31 downto 0)

);

end SQUARE_ROOT;

architecture BEHAVIOR of SQUARE_ROOT is

begin


process(arg)



variable root : std_logic_vector(31 downto 0):=
"00000000000000000000000000000000";
variable remHi : std_logic_vector(31 downto 0):=
"00000000000000000000000000000000";
variable remLo : std_logic_vector(31 downto 0);
variable testDiv : std_logic_vector(31 downto 0);

variable remHi_temp : std_logic_vector(31 downto 0);
variable remLo_temp : std_logic_vector(31 downto 0);
variable root_temp : std_logic_vector(31 downto 0);


begin


remLo:= arg;


LOOP1: for I in 1 to 30 loop

remHi_temp:= remHi(remHi'high-2 downto 0) & "00";

remLo_temp:= "000000000000000000000000000000" &
remLo(remLo'high downto remLo'high-1);

remHi:= remHi_temp or remLo_temp;

remLo:= remLo(remLo'high-2 downto 0) & "00";

root:= root(root'high downto 1) & '0';

root_temp:= root;

testDiv:= root_temp(root_temp'high downto 1) & '1';

if ( remHi >= testDiv) then

remHi:= remHi - testDiv;

root:= root + 1;

end if;


end loop LOOP1;

output <= root;

end process;

end BEHAVIOR;

Christian

(Christian) wrote in message news:<. com>...
> Hi,
> i am trying to implement a fixpoint square root in vhdl.
> The radicant consists of integer as well as fractional bits like 4.23 - dec.
> Does anyone know a synthesiable algorithm ?
> Thanks in advance
> Christian

There is a couple of pages about this in the march 2005 issue of ieee signal
processing magazine (dsp tips and tricks).
In short it's about "quick and dirty" sqrts (sacrifice accuracy for speed),
where you calculate (iterate) 1/sqrt(x) and finnish off with a multiplication
with x. One iterative scheme is p(n+1)=0.5*p(n)*(3-x*p(n)*p(n)).
Hope this helps /Pontus

Pontus Stenstrom