Перейти к содержанию
    

Реализовал функцию вычисления квадратного корня на VHDL

К сожалению алгоритм последовательный, в итоге вычисляет sqrt(2 147 395 600)=46300 - за 46300*3 =139 020 тактов.

Реализация:

LIBRARY IEEE;
USE IEEE.STD_LOGIC_1164.ALL;
USE IEEE.STD_LOGIC_ARITH.ALL;
USE IEEE.STD_LOGIC_UNSIGNED.all;
ENTITY square_root_2 IS
  GENERIC(n: NATURAL := 32);
PORT (
  x: IN STD_LOGIC_VECTOR(n-1 DOWNTO 0);
  clk, reset, start: IN STD_LOGIC;
  r: INOUT STD_LOGIC_VECTOR(n-1 DOWNTO 0);
  done: OUT STD_LOGIC
);
END square_root_2;

ARCHITECTURE behavior OF square_root_2 IS
  SIGNAL operand_1, operand_2, s, shifted_r, complemented_x: STD_LOGIC_VECTOR(n-1 DOWNTO 0);
  SIGNAL result: STD_LOGIC_VECTOR(n DOWNTO 0);
  SIGNAL greater: STD_LOGIC;
  SIGNAL ce_r, ce_s, ce_greater, load: STD_LOGIC;
  SIGNAL operation: STD_LOGIC_VECTOR(1 DOWNTO 0);
  TYPE states IS RANGE 0 TO 4;
  SIGNAL current_state: states;
  CONSTANT zero: STD_LOGIC_VECTOR(n-1 DOWNTO 0) := (OTHERS => '0');
BEGIN

  shifted_r <= r(n-2 DOWNTO 0)&'0';
  complemented_x <= NOT(x);
  WITH operation SELECT operand_1 <= r WHEN "00", s WHEN OTHERS;
  WITH operation SELECT operand_2 <= zero WHEN "00", shifted_r WHEN "01", complemented_x WHEN OTHERS;
  result <= '0'&operand_1 + operand_2 + NOT(operation(1));
  
  register_r: PROCESS(clk)
  BEGIN
    IF clk'EVENT AND clk = '1' THEN 
      IF LOAD = '1' THEN r <= (OTHERS => '0');
      ELSIF ce_r = '1' THEN r <= result(n-1 DOWNTO 0); 
      END IF;
    END IF;
  END PROCESS;

  register_s: PROCESS(clk)
  BEGIN
    IF clk'EVENT AND clk = '1' THEN 
      IF LOAD = '1' THEN s <= CONV_STD_LOGIC_VECTOR(1,32);
      ELSIF ce_s = '1' THEN s <= result(n-1 DOWNTO 0); 
      END IF;
    END IF;
  END PROCESS;

  ff_greater: PROCESS(clk)
  BEGIN
    IF clk'EVENT AND clk = '1' THEN 
      IF LOAD = '1' THEN greater <= '0';
      ELSIF ce_greater = '1' THEN greater <= result(n); 
      END IF;
    END IF;
  END PROCESS;

  control_unit_output: PROCESS(current_state, start, greater)
  BEGIN
    CASE current_state IS
      WHEN 0 => ce_r <= '0'; ce_s <= '0'; ce_greater <= '0'; load <= '0'; operation <= "00"; done <= '1';
      WHEN 1 => ce_r <= '0'; ce_s <= '0'; ce_greater <= '0'; operation <= "00"; 
                IF start = '1' THEN load <= '1'; done <= '0'; ELSE load <= '0'; done <= '1'; END IF;
      WHEN 2 => IF greater = '0' THEN ce_r <= '1'; ELSE ce_r <= '0'; END IF;
                ce_s <= '0'; ce_greater <= '0'; load <= '0'; operation <= "00"; done <= '0';
      WHEN 3 => ce_r <= '0'; ce_s <= '1'; ce_greater <= '0'; load <= '0'; operation <= "01"; done <= '0';
      WHEN 4 => ce_r <= '0'; ce_s <= '0'; ce_greater <= '1'; load <= '0'; operation <= "10"; done <= '0';
    END CASE;
  END PROCESS;

  control_unit_next_state: PROCESS(clk, reset)
  BEGIN
    IF reset = '1' THEN current_state <= 0;
    ELSIF clk'event AND clk= '1' THEN
      CASE current_state IS
        WHEN 0 => IF start = '0' THEN current_state <= 1; END IF;
        WHEN 1 => IF start = '1' THEN current_state <= 2; END IF;
        WHEN 2 => IF greater = '1' THEN current_state <= 0; ELSE current_state <= 3; END IF;
        WHEN 3 => current_state <= 4;
        WHEN 4 => current_state <= 2;
      END CASE;
    END IF;
  END PROCESS;

END behavior;

тестбенч

LIBRARY IEEE;
USE IEEE.STD_LOGIC_1164.ALL;
USE IEEE.STD_LOGIC_ARITH.ALL;
USE IEEE.STD_LOGIC_UNSIGNED.all;
ENTITY test_square_root_2 IS END test_square_root_2;

ARCHITECTURE test OF test_square_root_2 IS
  COMPONENT square_root_2 IS
   -- GENERIC(n  : NATURAL );
  PORT (
    x: IN STD_LOGIC_VECTOR(31 DOWNTO 0);
    clk, reset, start: IN STD_LOGIC;
    r: INOUT STD_LOGIC_VECTOR(31 DOWNTO 0);
    done: OUT STD_LOGIC
  );
  END COMPONENT;
  SIGNAL clk: STD_LOGIC := '0';
  SIGNAL reset, start, done: STD_LOGIC;
  SIGNAL r, x: STD_LOGIC_VECTOR(31 DOWNTO 0);
BEGIN
  DUT: square_root_2
-- GENERIC MAP(n => 32)
  PORT MAP(x => x, clk => clk, reset => reset, start => start, r => r, done => done);
  clk <= not(clk) after 5 ns;
  reset <= '1', '0' after 100 ns;
  x <= "01111111111111101010100000010000"; --, 
      -- "00000000000000000000000010001111" after 6000 ns, 
      --"00000000000000000000000001000000" after 12000 ns, 
      --"00000000000000000000000000111111" after 18000 ns;
  start <= '0', '1' after 2000 ns; --after 3000 ns,
-- '1' after 6100 ns, '0' after 6200 ns,
-- '1' after 12100 ns, '0' after 12200 ns,
-- '1' after 18100 ns, '0' after 18200 ns;
END test;

 

Прошу помочь найти алгоритм или реализацию параллельного вычисления квадратного корня, подойдет любой алгоритм/реализация который вычисляет быстрее приведенного.

PS Конечно хотелось бы алгоритм/реализацию вычисления квадратного корня за минимальное количество тактов, например до 100

ПОЖАЛУЙСТА!

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Если в Вашей FPGA есть умножитель за такт, то можно реализовать метод последовательных приближений. Займет тактов по количеству разрядов, или, в крайнем случае, вдвое больше. Алгоритм тривиальный: устанавливаете в выходном числе старший бит, возводите его в квадрат и сравниваете с исходным числом. Если квадрат больше исходного - снимаете бит, если нет - оставляете. Ставите следующий бит и так до младшего разряда.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Если в Вашей FPGA есть умножитель за такт, то можно реализовать метод последовательных приближений. Займет тактов по количеству разрядов, или, в крайнем случае, вдвое больше. Алгоритм тривиальный: устанавливаете в выходном числе старший бит, возводите его в квадрат и сравниваете с исходным числом. Если квадрат больше исходного - снимаете бит, если нет - оставляете. Ставите следующий бит и так до младшего разряда.

буду пробовать...

а у Вас может есть готовая реализация на HDL? :)

PS FPGA - Spartan 6

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

А чем CORDIC из coregen не устраивает? Там корень весьма шустро считается.

я знаю, сам пользовался им всегда :)

Требования открытость и переносимость (максимальная) кода...

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

я знаю, сам пользовался им всегда :)

Требования открытость и переносимость (максимальная) кода...

ну как бы код кордика строк 100, я выкладывал на этом форуме на SV %)

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

ладно, буду разбираться сам....

Далеко от рабочего компа, но вот что-то локальное нарыл. Вроде то. если еще не опоздал, то кордик для преобразования из декартовой системы в полярную в приложении.

cordic_script_des00.zip

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Метод последовательных приближений, аналогичый поразрядному делению.

 

Это С, но, наверное, Вам важнее идея.

 

Округление-сравнение в конце, понятное дело, можно не делать/

 

 

/*
********************************************************************************
*                         MODULE INCLUDE FILE AND VERSION ID
********************************************************************************
*/
#include "sqrt_l.h"

/*
********************************************************************************
*                         INCLUDE FILES
********************************************************************************
*/
#include "typedef.h"
#include "basic_op.h"

/*
********************************************************************************
*                         PUBLIC PROGRAM CODE
********************************************************************************
*/

Word16 sqrt_l( Word32 x )
{
Word16       Est;
Word16       EstR;
Word16       Bit = 0x4000;
Word32       Temp;
UWord16      i;

Est = 0x0000;

for (i=0; i<14; i++)
{
	Est = add(Est, Bit);

	Temp = L_mult(Est,Est);

	if (Temp > x)
	{
		Est = sub(Est, Bit);
	}

	Bit = shr (Bit, 1);
}

/* Choose between estimate & rounded estimate for most accurate result */

EstR = add(Est, 1);

if (L_abs(L_sub(x,L_mult(EstR, EstR))) < L_sub(x,L_mult(Est,Est)))
{
	Est = EstR;
}

return Est;
}

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

пока модернизировал так

-- algorithm in C code
------------
--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;
--}
-----------



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

entity SQRT is
    Generic ( b  : natural range 4 to 32 := 16 ); 
    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 aaa is (idle, shift, calc, done);
signal z : aaa;

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';
            if (start='0') then 
               z <= idle; 
            end if;
      end case;
   end process;
   
   result <= std_logic_vector(res(result'range));
end;

 

тестбенч

 

LIBRARY ieee;
USE ieee.std_logic_1164.ALL;

-- Uncomment the following library declaration if using
-- arithmetic functions with Signed or Unsigned values
--USE ieee.numeric_std.ALL;

ENTITY test_sqrt IS
END test_sqrt;

ARCHITECTURE behavior OF test_sqrt IS 

    -- Component Declaration for the Unit Under Test (UUT)

    COMPONENT SQRT
    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 COMPONENT;
    

   --Inputs
   signal clk : std_logic := '0';
   signal start : std_logic := '0';
   signal value : std_logic_vector(15 downto 0) := (others => '0');

    --Outputs
   signal result : std_logic_vector(7 downto 0);
   signal busy : std_logic;

   -- Clock period definitions
   constant clk_period : time := 20 ns;

BEGIN

    -- Instantiate the Unit Under Test (UUT)
   uut: SQRT PORT MAP (
          clk => clk,
          start => start,
          value => value,
          result => result,
          busy => busy
        );

   -- Clock process definitions
   clk_process :process
   begin
        clk <= '0';
        wait for clk_period/2;
        clk <= '1';
        wait for clk_period/2;
   end process;


   -- Stimulus process
   stim_proc: process
   begin        
      start <= '0'; wait for 100 ns;    
      start <= '1';
        value <= "1111111000000001";
      wait for 10000 ns;
        start <= '0'; wait for 100 ns;    
      start <= '1';
        value <= "1110100010010000";
        wait for 10000 ns;
        start <= '0'; wait for 100 ns;    
      start <= '1';
        value <= "0000001001110001";
        wait for 10000 ns;
   end process;

END;

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Погуглите "non restoring square root algorithm", эта штука для ASIC и FPGA вообще шикарная. Я делал что-то похожее на VHDL, но похуже, так как требует два сложения последовательно в одном такте . И достаточно сложно для понимания. Если интересно, могу выложить.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Погуглите "non restoring square root algorithm", эта штука для ASIC и FPGA вообще шикарная. Я делал что-то похожее на VHDL, но похуже, так как требует два сложения последовательно в одном такте . И достаточно сложно для понимания. Если интересно, могу выложить.

интересно, выкладывайте :)

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Погуглите "non restoring square root algorithm", эта штука для ASIC и FPGA вообще шикарная. Я делал что-то похожее на VHDL, но похуже, так как требует два сложения последовательно в одном такте . И достаточно сложно для понимания. Если интересно, могу выложить.

посмотрите вложение, думаю будет интересно...

А если кобинаторику исправите на FSM какой-нибудь или конвеер - будет хорошо... :)

Будет с чем сравнивать... ;)

281_G850.pdf

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Присоединяйтесь к обсуждению

Вы можете написать сейчас и зарегистрироваться позже. Если у вас есть аккаунт, авторизуйтесь, чтобы опубликовать от имени своего аккаунта.

Гость
Ответить в этой теме...

×   Вставлено с форматированием.   Вставить как обычный текст

  Разрешено использовать не более 75 эмодзи.

×   Ваша ссылка была автоматически встроена.   Отображать как обычную ссылку

×   Ваш предыдущий контент был восстановлен.   Очистить редактор

×   Вы не можете вставлять изображения напрямую. Загружайте или вставляйте изображения по ссылке.

×
×
  • Создать...