Wurzel in VHDL

Eine Wurzel zu ziehen kann recht aufwendig sein. Erschwert wird das Ganze, wenn es in VHDL geschehen soll. Hier eine Gegenüberstellung des Ressourcenverbrauchs einer rein kombinatorischen Lösung verglichen mit einer sequentiellen getakteten Variante in einem Xilinx Spartan3 XC3S200 FPGA.

Hier als Bezugspunkt die parallel implementierte kombinatorische Lösung:

library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use IEEE.NUMERIC_STD.ALL;

entity SQRT is
    Generic ( b  : natural range 4 to 32 := 16 ); -- Breite 
    Port ( value  : in   STD_LOGIC_VECTOR (15 downto 0);
           result : out  STD_LOGIC_VECTOR (7 downto 0));
end SQRT;

architecture Behave of SQRT is
begin
   process (value)
   variable vop  : unsigned(b-1 downto 0);  
   variable vres : unsigned(b-1 downto 0);  
   variable vone : unsigned(b-1 downto 0);  
   begin
      vone := to_unsigned(2**(b-2),b);
      vop  := unsigned(value);
      vres := (others=>'0'); 
      while (vone /= 0) loop
         if (vop >= vres+vone) then
            vop   := vop - (vres+vone);
            vres  := vres/2 + vone;
         else
            vres  := vres/2;
         end if;
         vone := vone/4;
      end loop;
      result <= std_logic_vector(vres(result'range));
   end process;
end;

Mit diesem Ansatz ergibt sich folgender Ressourcenbedarf:

So eine Wurzel braucht schon Platz...

Und jetzt zum Vergleich die Variante mit der getakteten Berechnung der Wurzel:

library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use IEEE.NUMERIC_STD.ALL;

entity SQRT is
    Generic ( b  : natural range 4 to 32 := 16 ); -- Breite 
    Port ( clk    : in   STD_LOGIC;
           start  : in   STD_LOGIC;
           value  : in   STD_LOGIC_VECTOR (15 downto 0);
           result : out  STD_LOGIC_VECTOR (7 downto 0);
           busy   : out  STD_LOGIC);
end SQRT;

architecture Behave of SQRT is
signal op  : unsigned(b-1 downto 0); -- 
signal res : unsigned(b-1 downto 0); -- 
signal one : unsigned(b-1 downto 0); -- 

signal bits : integer range b downto 0;
type zustaende is (idle, shift, calc, done);
signal z : zustaende;

begin
   process begin
      wait until rising_edge(clk);
      case z is 
         when idle => 
            if (start='1') then 
               z <= shift; 
               busy <= '1';
            end if;
            one <= to_unsigned(2**(b-2),b);
            op  <= unsigned(value);
            res <= (others=>'0');

         when shift =>
            if (one > op) then
               one <= one/4;
            else
               z   <= calc;
            end if;

         when calc =>
            if (one /= 0) then
               if (op >= res+one) then
                  op   <= op - (res+one);
                  res  <= res/2 + one;
               else
                  res  <= res/2;
               end if;
               one <= one/4;
            else
               z    <= done;
            end if;
            
         when done =>
            busy <= '0';
            -- Handshake: wenn nötig warten, bis start='0'
            if (start='0') then 
               z <= idle; 
            end if;
      end case;
   end process;
   
   result <= std_logic_vector(res(result'range));
end;

Das Design Summary zeigt jetzt einen deutlich kleineren Ressourcenverbrauch an, wobei der Verbrauch an Slices insgesamt nicht mal so sehr viel höher ist:

... aber es geht auch wesentlich kompakter

Die Wurzelberechnung basiert auf diesem C Code von Jack W. Crenshaw:

int sqrt(int num) {
    int op = num;
    int res = 0;
    int one = 1 << 30; // The second-to-top bit is set: 1L<<30 for long

    // "one" starts at the highest power of four <= the argument.
    while (one > op)
        one >>= 2;
   
    while (one != 0) {
        if (op >= res + one) {
            op -= res + one;
            res += 2 * one;
        }
        res >>= 1;
        one >>= 2;
    }
    return res;
}