Maverick_ 15 1 мая, 2013 Опубликовано 1 мая, 2013 · Жалоба Реализовал функцию вычисления квадратного корня на 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 ПОЖАЛУЙСТА! Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Alex11 5 1 мая, 2013 Опубликовано 1 мая, 2013 · Жалоба Если в Вашей FPGA есть умножитель за такт, то можно реализовать метод последовательных приближений. Займет тактов по количеству разрядов, или, в крайнем случае, вдвое больше. Алгоритм тривиальный: устанавливаете в выходном числе старший бит, возводите его в квадрат и сравниваете с исходным числом. Если квадрат больше исходного - снимаете бит, если нет - оставляете. Ставите следующий бит и так до младшего разряда. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Maverick_ 15 1 мая, 2013 Опубликовано 1 мая, 2013 · Жалоба Если в Вашей FPGA есть умножитель за такт, то можно реализовать метод последовательных приближений. Займет тактов по количеству разрядов, или, в крайнем случае, вдвое больше. Алгоритм тривиальный: устанавливаете в выходном числе старший бит, возводите его в квадрат и сравниваете с исходным числом. Если квадрат больше исходного - снимаете бит, если нет - оставляете. Ставите следующий бит и так до младшего разряда. буду пробовать... а у Вас может есть готовая реализация на HDL? :) PS FPGA - Spartan 6 Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Alex11 5 1 мая, 2013 Опубликовано 1 мая, 2013 · Жалоба Нет, на HDL нету, я только программку такую делал. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Dimidrol 0 1 мая, 2013 Опубликовано 1 мая, 2013 · Жалоба А чем CORDIC из coregen не устраивает? Там корень весьма шустро считается. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Maverick_ 15 1 мая, 2013 Опубликовано 1 мая, 2013 · Жалоба А чем CORDIC из coregen не устраивает? Там корень весьма шустро считается. я знаю, сам пользовался им всегда :) Требования открытость и переносимость (максимальная) кода... Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
des00 25 1 мая, 2013 Опубликовано 1 мая, 2013 · Жалоба я знаю, сам пользовался им всегда :) Требования открытость и переносимость (максимальная) кода... ну как бы код кордика строк 100, я выкладывал на этом форуме на SV %) Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Maverick_ 15 1 мая, 2013 Опубликовано 1 мая, 2013 · Жалоба ладно, буду разбираться сам.... Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
des00 25 1 мая, 2013 Опубликовано 1 мая, 2013 · Жалоба ладно, буду разбираться сам.... Далеко от рабочего компа, но вот что-то локальное нарыл. Вроде то. если еще не опоздал, то кордик для преобразования из декартовой системы в полярную в приложении. cordic_script_des00.zip Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
FatRobot 1 1 мая, 2013 Опубликовано 1 мая, 2013 · Жалоба Метод последовательных приближений, аналогичый поразрядному делению. Это С, но, наверное, Вам важнее идея. Округление-сравнение в конце, понятное дело, можно не делать/ /* ******************************************************************************** * 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; } Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Leka 1 1 мая, 2013 Опубликовано 1 мая, 2013 · Жалоба http://electronix.ru/forum/index.php?showtopic=72901 ~~в конце ветки есть готовый код des00 Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Maverick_ 15 1 мая, 2013 Опубликовано 1 мая, 2013 · Жалоба пока модернизировал так -- 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; Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Timmy 1 2 мая, 2013 Опубликовано 2 мая, 2013 · Жалоба Погуглите "non restoring square root algorithm", эта штука для ASIC и FPGA вообще шикарная. Я делал что-то похожее на VHDL, но похуже, так как требует два сложения последовательно в одном такте . И достаточно сложно для понимания. Если интересно, могу выложить. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Maverick_ 15 2 мая, 2013 Опубликовано 2 мая, 2013 · Жалоба Погуглите "non restoring square root algorithm", эта штука для ASIC и FPGA вообще шикарная. Я делал что-то похожее на VHDL, но похуже, так как требует два сложения последовательно в одном такте . И достаточно сложно для понимания. Если интересно, могу выложить. интересно, выкладывайте :) Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Maverick_ 15 2 мая, 2013 Опубликовано 2 мая, 2013 · Жалоба Погуглите "non restoring square root algorithm", эта штука для ASIC и FPGA вообще шикарная. Я делал что-то похожее на VHDL, но похуже, так как требует два сложения последовательно в одном такте . И достаточно сложно для понимания. Если интересно, могу выложить. посмотрите вложение, думаю будет интересно... А если кобинаторику исправите на FSM какой-нибудь или конвеер - будет хорошо... :) Будет с чем сравнивать... ;) 281_G850.pdf Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться