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.