Tam Sayılar için Karekök Hesaplama İşleminin VHDL ile Gerçeklenmesi

Bitwise Karekök Algoritması

Bitwise karekök algoritması, pozitif bir tam sayının karekökünü donanımsal olarak hızlı ve basit bir şekilde hesaplamak için kullanılan yöntemlerden biridir. Bu algoritma, divide and conquer yaklaşımıyla çalışır ve sonucu bit bit oluşturur. Genellikle FPGA ve ASIC gibi sayısal donanımlarda tercih edilir.

Algoritmanın Ana Mantığı

1. Giriş olarak bir tam sayı (in_data) alınır.
2. Başlangıçta r_res = 0 ve r_bit = 2^(DATA_WIDTH - 2) olarak atanır.
3. Her döngüde r_res + r_bit hesaplanır ve r_data_in ile karşılaştırılır:
   • Eğer r_data_in ≥ r_res + r_bit ise:
     • Çıkarma yapılır: r_data_in <= r_data_in - (r_res + r_bit)
     • r_res <= (r_res >> 1) + r_bit
     • Bu adım karekökün yeni bitine 1 yazar.
   • Aksi halde:
     • r_data_in değişmez
     • r_res := r_res >> 1
     • Bu adım karekökün yeni bitine 0 yazar.
4. r_bit <= r_bit >> 2 ile iki bit sağa kaydırılır.
5. Döngü, r_bit = 0 olana kadar devam eder.

Örnek: 1521 Sayısı İçin Bitwise Karekök

Giriş: 1521₁₀ = 10111110001₂
DATA_WIDTH: 12 ⇒ Başlangıç r_bit = 2^10 = 1024
Hedef Kareköklü Sonuç: √1521 = 39 ⇒ 100111₂

Adım Adım Tablo

Adım	r_bit (₁₀ / ₂)	r_res (eski)	r_data_in (eski)	r_res + r_bit	Karşılaştırma	Yeni r_res	Yeni r_data_in	Karekök Bit
1	1024 / 10000000000	0	1521	1024	1521 ≥ 1024 ✅	1024	497	1
2	256 / 100000000	1024	497	1280	497 < 1280 ❌	512	497	0
3	64 / 1000000	512	497	576	497 < 576 ❌	256	497	0
4	16 / 10000	256	497	272	497 ≥ 272 ✅	144	225	1
5	4 / 100	144	225	148	225 ≥ 148 ✅	76	77	1
6	1 / 1	76	77	77	77 ≥ 77 ✅	39	0	1

Sonuç olarak

Karekök Bitleri: 1 0 0 1 1 1
Karekök (ondalık): 39

---

Yukarıda anlatılan karekök bulma işlemine ilişkin VHDL kodu aşağıda verilmiştir.

library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use IEEE.STD_LOGIC_UNSIGNED.ALL;
use IEEE.STD_LOGIC_ARITH.ALL;
 
entity sqrt_v1 is
    generic(
        DATA_WIDTH : integer := 25
    );
    Port (
        in_clk : in std_logic;
        in_rst : in std_logic;
        in_data : in std_logic_vector(DATA_WIDTH - 1 downto 0);
        in_data_vld : in std_logic;
        out_data : out std_logic_vector(DATA_WIDTH - 1 downto 0);
        out_data_vld : out std_logic
   
    );
end sqrt_v1;
 
architecture Behavioral of sqrt_v1 is
   
    function f_WIDTH_CNTRL (DATA_WIDTH : integer) return integer is
    begin
       if (DATA_WIDTH / 2) * 2 = DATA_WIDTH then
           return DATA_WIDTH;
       else
           return DATA_WIDTH + 1;
       end if;
    end f_WIDTH_CNTRL;
   
    function f_DATA_CNTRL(c_DATA_WIDTH, g_DATA_WIDTH : integer; in_data : std_logic_vector(DATA_WIDTH - 1 downto 0)) return std_logic_vector is
    begin
       if g_DATA_WIDTH = c_DATA_WIDTH then
           return in_data;
       else
           return ('0' & in_data);
       end if;
    end f_DATA_CNTRL;
   
    constant c_DATA_WIDTH : integer := f_WIDTH_CNTRL(DATA_WIDTH);
   
    type t_Cntrl is (IDLE, SHIFT_BIT, CHK_DATA, DONE);
    signal r_Cntrl : t_Cntrl := IDLE;
 
    signal r_data_in : std_logic_vector(c_DATA_WIDTH -1 downto 0) := (others => '0');
    signal r_res : std_logic_vector(c_DATA_WIDTH -1 downto 0) := (others => '0');
    signal r_bit : std_logic_vector(c_DATA_WIDTH -1 downto 0) := conv_std_logic_vector(2**(c_DATA_WIDTH - 2), c_DATA_WIDTH);
    signal r_data_vld : std_logic := '0';
   
   
 
begin
 
    out_data <= r_res(DATA_WIDTH - 1 downto 0);
    out_data_vld <= r_data_vld;
 
    process(in_rst, in_clk)
    begin
        if in_rst = '1' then
            r_Cntrl <= IDLE;
            r_data_in <= (others => '0');
            r_res <= (others => '0');
            r_bit <= conv_std_logic_vector(2**(c_DATA_WIDTH - 2), c_DATA_WIDTH);
            r_data_vld <= '0';
        elsif rising_edge(in_clk) then
            r_data_vld <= '0';
            case r_Cntrl is
                when IDLE =>                   
                    r_res <= (others => '0');
                    r_bit <= conv_std_logic_vector(2**(c_DATA_WIDTH - 2), c_DATA_WIDTH);
                    if in_data_vld = '1' then
                        r_data_in <= f_DATA_CNTRL(c_DATA_WIDTH, DATA_WIDTH, in_data);
                        r_Cntrl <= SHIFT_BIT;
                    end if;
                   
                when SHIFT_BIT =>
                    if r_bit > r_data_in then
                        r_bit <= "00" & r_bit(r_bit'high downto 2);                    
                    else
                        r_Cntrl <= CHK_DATA;
                    end if;
                   
                when CHK_DATA =>
                    if r_bit /= 0 then
                        if r_data_in >= (r_res + r_bit) then
                            r_data_in <= r_data_in - (r_res + r_bit) ;
                            r_res <= ('0' & r_res(r_res'high downto 1)) + r_bit;
                        else
                            r_res <= '0' & r_res(r_res'high downto 1);                             
                        end if;    
                        r_bit <= "00" & r_bit(r_bit'high downto 2);                        
                    else
                        r_data_vld <= '1';
                        r_Cntrl <= DONE;
                    end if;
                when others => NULL;
            end case;
           
        end if;
    end process;
 
 
end Behavioral;