CORDIC Algoritması ve FPGA Üzerinde Uygulaması

CORDIC yani COordinate Rotation DIgital Computer, bilgisayarlarda kullanılan ve trigonometrik fonksiyonları kısa yoldan en az hata ile hesaplamada kullanılan bir algoritmadır. Algoritmanın temeli, bir noktanın orjin etrafında gitgide azalan bir açı ile döndürülmesinden gelir. \mathbf{R}, dönüşüm matrisi olmak üzere yapılan işlemleri matematiksel olarak şu şekilde yazabiliriz:

\mathbf{v_i}=\begin{bmatrix}x_i\\y_i\end{bmatrix}

\begin{align*}\mathbf{v_{i+1}}=\mathbf{R}(\theta)\mathbf{v_i}=\begin{bmatrix}\cos(\theta)&-\sin(\theta)\\\sin(\theta)&\cos(\theta)\end{bmatrix}\begin{bmatrix}x_i\\y_i\end{bmatrix}\end{align*}

Dönüşüm matrisindeki \sin ve \cos ifadelerini \tan cinsinden yazalım.

\begin{align*}\sin(\theta)=\frac{\tan(\theta)}{\sqrt{1+\tan^2(\theta)}}\end{align*}

\begin{align*}\cos(\theta)=\frac{1}{\sqrt{1+\tan^2(\theta)}}\end{align*}

\begin{align*}\mathbf{R}(\theta)=\frac{1}{\sqrt{1+\tan^2(\theta)}}\begin{bmatrix}1&&-\tan(\theta)\\\tan(\theta)&&-1\end{bmatrix}\end{align*}

Elimizde i=0,1,2,\dots olmak üzere \tan(2^{-i}) ve \frac{1}{\sqrt{1+\tan^2(2^{-i})}} değerlerinden oluşan tablolarımız olsun. Bu tabloları kullanarak istediğimiz değerdeki \sin ve \cos değerlerini bulabiliriz.

\begin{align*}\mathbf{v_{i+1}}=K_{i}\mathbf{R}(2^{-i})\mathbf{v_{i}}\end{align*}

\begin{align*}\mathbf{v_{i+1}}=\frac{1}{\sqrt{1+\tan^2({\sigma}2^{-i})}}\begin{bmatrix}1&&-\tan({\sigma}2^{-i})\\\tan({\sigma}2^{-i})&&-1\end{bmatrix}\begin{bmatrix}x_{i}\\y_{i}\end{bmatrix}\end{align*}

\begin{align*}\mathbf{v_{i+1}}=\frac{1}{\sqrt{1+\tan^2(2^{-i})}}\begin{bmatrix}1&&-{\sigma}\tan(2^{-i})\\{\sigma}\tan(2^{-i})&&-1\end{bmatrix}\begin{bmatrix}x_{i}\\y_{i}\end{bmatrix}\end{align*}

\begin{align*}x_{i+1}=K_ix_{i}-{\sigma}K_i\tan(2^{-i})y_{i}\end{align*}

\begin{align*}y_{i+1}=K_iy_{i}+{\sigma}K_i\tan(2^{-i})x_{i}\end{align*}

Burada \sigma dönmenin yönünü belirtir. -1 ya da 1 değerlerinden birini alabilir. Bu işlemler ne kadar tekrar edilirse istenilen \sin ve \cos değerlerine o kadar yaklaşılır.

Bilgisayarlarda çarpma işlemi yapmak, kaydırma işlemi yapmaktan daha fazla zaman harcar. Bu yüzden tan(2^{-i}) yerine işlemleri daha kolay hesaplanabilecek hale getiren 2^{-i} ifadesini yazalım ve tan^{-1}(2^{-i}) değerlerini bir tabloda saklayalım.

\begin{align*}\mathbf{R}(\gamma)=\frac{1}{\sqrt{1+2^{-2i}}}\begin{bmatrix}1&&-2^{-i}\\2^{-i}&&-1\end{bmatrix}\end{align*}

\begin{align*}\gamma=tan^{-1}(2^{-i})\end{align*}

\begin{align*}\mathbf{v_{i+1}}=2^{-i}K_{i}\,\mathbf{v_{i}}\end{align*}

\begin{align*}x_{i+1}=K_i\,x_{i}-{\sigma}\,K_i\,2^{-i}\,y_{i}\end{align*}

\begin{align*}y_{i+1}=K_i\,y_{i}+{\sigma}\,K_i\,2^{-i}\,x_{i}\end{align*}

Her işlemde K_i değerini tekrar tekrar çarpmak yerine en son belirli iterasyon değeri için hesaplanmış K ile çarparak işlemleri bitirebiliriz.

\theta=27^{\circ} değeri için sin ve cos fonksiyonlarını n=4 iterasyonda hesaplamaya çalışalım.

n=0:
x_0=1\,,\,y_0=0
\alpha=0^{\circ}

n=1:
i=0
\sigma=sgn(\theta-\alpha)=sgn(27^{\circ}-0^{\circ})=1
x_1=x_0-2^{-0}\,y_0
y_1=y_0+2^{-0}\,x_0
x_1=1-0=1
y_1=0+1=1
\alpha=0^{\circ}+\tan^{-1}(0)=45^{\circ}

n=2:
i=1
\sigma=sgn(27^{\circ}-45^{\circ})=-1
x_2=x_1+2^{-1}\,y_1
y_2=y_1-2^{-1}\,x_1
x_2=1+0.5=1.5
y_2=1-0.5=0.5
\alpha=45^{\circ}-26.57^{\circ}=18.43^{\circ}

n=3:
i=2
\sigma=sgn(27^{\circ}-18.43^{\circ})=1
x_3=x_2-2^{-2}\,y_2
y_3=y_2+2^{-2}\,x_2
x_3=1.5-0.125=1.375
y_3=0.5+0.375=0.875
\alpha=18.43^{\circ}+14.04=32.47^{\circ}

n=4:
i=3
\sigma=sgn(27^{\circ}-32.47^{\circ})=-1
x_4=x_3+2^{-3}\,y_3
y_4=y_3-2^{-3}\,x_3
x_4=1.375+0.125\,\times\,0.875=1.484375
y_4=0.875-0.125\,\times\,1.375=0.703125
\alpha=32.47^{\circ}-7.125=25.345^{\circ}

\sin(27^{\circ})\,{\approx}\,K\,y_4=0.60883\,\times\,0.703125
\sin(27^{\circ})\,{\approx}\,0.4280

\cos(27^{\circ})\,{\approx}\,K\,x_4=0.60883\,\times\,1.484375
\cos(27^{\circ})\,{\approx}\,0.9037

Burada \alpha hesaplanan gerçek açıdır. Yaptığımız işlemler koordinat sisteminde aşağıdaki gibi olacaktır:

FPGA Üzerinde Uygulama:

Kullanılacak sayı formatı \sin ve \cos için UQ15, açı için Q1.14 olarak seçilmiştir. Donanımın tasarımı aşağıdaki gibi olacaktır:

Top-Level VHDL kodu:

library IEEE;
use IEEE.STD_LOGIC_1164.ALL;

entity CORDIC is
    port(Clk, Reset, S : in std_logic;                   --Clock, Reset ve S girişleri
        Angle : in std_logic_vector(15 downto 0);      --Hesaplanacak yeni açı girişi
        Sin, Cos : out std_logic_vector(15 downto 0)); --Sin, Cos çıkışları
end CORDIC; 

architecture Behavioral of CORDIC is

--Shifter    
component ArithmeticShifter
    port(DataIn : in std_logic_vector(15 downto 0);
        i : in std_logic_vector(3 downto 0);
        DataOut : out std_logic_vector(15 downto 0));
end component;    

--Toplayıcı-Çıkarıcı    
component Adder
    generic(W : integer := 8);
    port(Sigma : in std_logic;
        A, B : in std_logic_vector(W - 1 downto 0);
        O : out std_logic_vector(W - 1 downto 0));
end component;

--Çarpıcı(Q15 x Q15 = Q30)
component Multiplier
    port(A, B : in std_logic_vector(15 downto 0);
        O : out std_logic_vector(31 downto 0));
end component;

--Register
component Reg
    generic(ResetValue : std_logic_vector(15 downto 0) := X"00");
    port(Clk, Reset : in std_logic;
        DataIn : in std_logic_vector(15 downto 0);
        DataOut : out std_logic_vector(15 downto 0));
end component;
    
    signal XiIn, XiOut : std_logic_vector(15 downto 0);
    signal XiShifterOut : std_logic_vector(15 downto 0);
    signal XiMultiplierOut : std_logic_vector(31 downto 0);
    signal YiIn, YiOut : std_logic_vector(15 downto 0);
    signal YiShifterOut : std_logic_vector(15 downto 0);
    signal YiMultiplierOut : std_logic_vector(31 downto 0);
    
    signal atanLUTOut : std_logic_vector(15 downto 0);
    signal AngleOut, AngleIn : std_logic_vector(15 downto 0);
    signal AngleAdderOut : std_logic_vector(15 downto 0);
    
    signal Sigma : std_logic;
    signal i : std_logic_vector(3 downto 0) := X"0";
    signal CounterAdderOut : std_logic_vector(3 downto 0);
    
begin

--Xi Registeri
--Reset Değeri = 1 (UQ1.15)
    Xi : Reg
        generic map(X"8000")
        port map(Clk, Reset, XiIn, XiOut);

--Xi için shifter        
    XShifter : ArithmeticShifter
        port map(XiOut, i, XiShifterOut);

--Xi için Toplayıcı çıkarıcı        
    Adder1 : Adder
        generic map(16)
        port map(Sigma, YiOut, XiShifterOut, YiIn);

--Yi Registeri
--Reset Değeri = 0 (UQ1.15)        
    Yi : Reg
        generic map(X"0000")
        port map(Clk, Reset, YiIn, YiOut);

--Yi için shifter                
    YShifter : ArithmeticShifter
        port map(YiOut, i, YiShifterOut);

--Yi için Toplayıcı çıkarıcı            
    Adder2 : Adder
        generic map(16)
        port map(not Sigma, XiOut, YiShifterOut, XiIn);

--Xi ve Yi'yi K katsayısı ile çarp        
    XiMultiplier : Multiplier
        port map(XiOut, X"4DBA", XiMultiplierOut);
        
    YiMultiplier : Multiplier
        port map(YiOut, X"4DBA", YiMultiplierOut);
        
--Q30 -> Q15 için shift işlemi    
    Shift : for j in 0 to 15 generate
        Sin(j) <= YiMultiplierOut(j + 15);
        Cos(j) <= XiMultiplierOut(j + 15);
    end generate;
    
--Açı Registeri
    AngleRegister : Reg
        generic map(X"0000")
        port map(Clk, Reset, AngleIn, AngleOut);
        
    AngleAdder : Adder
        generic map(16)
        port map(not Sigma, AngleOut, atanLUTOut, AngleAdderOut);
    
--Yeni açı girmek için multiplexer
    with S select
        AngleIn <= AngleAdderOut when '0',
                      Angle when others;
    
--Açının işaret bitini
    Sigma <= AngleOut(15);

--Atan tablosu (Q1.14)
    with i select
        atanLUTOut <= X"3201" when X"0",
                      X"1DAC" when X"1",
                      X"0FAD" when X"2",
                      X"07F5" when X"3",
                      X"03FE" when X"4",
                      X"0200" when X"5",
                      X"0100" when X"6",
                      X"0080" when X"7",
                      X"0040" when X"8",
                      X"0020" when X"9",
                      X"0010" when X"A",
                      X"0008" when X"B",
                      X"0004" when X"C",
                      X"0002" when X"D",
                      X"0001" when X"E",
                      X"0000" when others;

--Counter                          
    CounterAdder : Adder
        generic map(4)
        port map('0', i, X"1", CounterAdderOut);
    
    process(Reset, Clk)
    begin
        if Reset = '1' then
            i <= X"0";
        elsif rising_edge(Clk) then
            i <= CounterAdderOut;
        end if;
    end process;
    
end Behavioral;

Tasarımın diğer dosyalarına buradan ulaşabilirsiniz.

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir