FPGA Üzerinde CORDIC Algoritması ile Pipeline Tabanlı Magnitude ve Faz Açısı Hesaplama

CORDIC(COordinate Rotation Digital Computer) algoritması bir noktayı orjin etrafında döndürerek sin, cos, sinh, tan, tan1 gibi fonksiyonları ve hatta αeθ, x2+y2, x2y2 gibi fonksiyonların da hesaplanmasını sağlayan bir algoritmadır.

Bu yazımda x2+y2(Magnitude) ve tan1(yx)(Faz Açısı) hesaplaması üzerinde duracağım.

Kartezyen koordinat sisteminde bir (x0,y0) noktası olsun. Bu noktanın magnitude değeri x20+y20'dir.

α açısını azalttığımızda y0 değeri y0=x0tan(α) olduğundan dolayı 0'a yaklaşacaktır. y0 değeri 0'a yaklaşınca magnitude değeri de x2i=xi'ye yaklaşacaktır. α açısının değişmesi magnitude değerini etkilemediği için xix20+y20 diyebiliriz.

(x0,y0) noktasını orjin etrafında(z-ekseni etrafında) döndürmek için dönüşüm matrisi kullanılır.

Noktaları saat yönünün tersinde döndürmek istersek kullanacağımız dönüşüm matrisi:

Rz(θ)=[cos(θ)sin(θ)sin(θ)cos(θ)]

[xi+1yi+1]=[cos(θ)sin(θ)sin(θ)cos(θ)][xiyi]

xi+1=xicos(θ)yisin(θ)yi+1=yicos(θ)+xisin(θ)

xi+1=cos(θ)[xiyitan(θ)]yi+1=cos(θ)[yi+xitan(θ)]

Elimizde θ=tan1(2i),i:0n değerlerinin tutulduğu bir tablomuz olsun.

cos(θ)=122i+1=Gi

tan(θ)=2i

xi+1=Gi[xiyi2i]yi+1=Gi[yi+xi2i]

2i işlemi bilgisayarlarda basit bit kaydırma ile yapılabilir.

Koordinatları orjin etrafında saat yönünün tersinde döndürürken α açısı yani faz açısının değerini de her bir dönüşümden sonrada θ=tan1(2i) çıkarmamız gerekir.

zi+1=ziθ=zitan1(2i)

Eğer noktaları orjin etrafında saat yönünde döndürmek istersek:

xi+1=Gi[xi+yi2i]yi+1=Gi[yixi2i]zi+1=zi+tan1(2i)

Noktaları hangi yöne döndüreceğimizi yi'nin değeri ile anlayabiliriz. Eğer yi<0 ise (xi,yi) noktası koordinat sisteminin sağ alt çeyreğindedir ve saat yönünün tersinde dönüşüm yapmamız gerekir. y0 ise de saat yönünde dönüşüm yapmamız gerekir.

Genel olarak algoritmayı şu şekilde yazabiliriz:

xi+1=Gi[xidiyi2i]yi+1=Gi[yi+dixi2i]zi+1=ziditan1(2i)

di={+1,yi<01,diger

Gi değeri her iterasyonda gelen kazançtır. Bütün işlemler bittikten sonra xn değeri bütün iterasyonların ters kazancı olan Kn=1G ile çarpılarak kazanç 1'e düşürülür.

FPGA üzerinde uygulanması

Birden çok nokta ile çalışırken, her bir nokta için teker teker algoritmayı uygulamak fazla clock cycle'ı harcamamıza neden olur. Pipeline tasarım ile bu soruna çözüm üretilebilir.

Pipeline yapı CORDIC çekirdeklerinin birbirine seri bağlanması ile yapılır. Her bir çekirdek aşağıdaki gibidir:

Tasarımın VHDL kodu:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
----------------------------------------------------------
--                   CORDIC_VectorMode.vhd
--                       Bertan Taşkın
--                         2.6.2017
--
-- Pipeline tabanlı çalışmaya tasarlanmış, Vectör modunda
-- çalışan CORDIC çekirdeği modülü. İşlenecek veri boyutu
-- generic kısmındaki Data_Width ile belirlenir. Pipeline'ın
-- hangi adımında olduğu ise PipelineStage ile belirlenir.
-- Clock sinyalinin yükselen kenarı ile işlenmiş X,Y,Zin
-- verileri pipeline'daki bir sonraki çekirdeğe aktarılır.
--
-- Faz açısı 1 işaret biti ve Data_Width-1 kadar fraction
-- bitinden oluşur. Radyan cinsinden çıkış verir.
--
-- Data_Width değerinin alabileceği en yüksek değer integer
-- genişliği olan 32'dir.
--
--
----------------------------------------------------------
 
 
--Kütüphaneler
library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
USE ieee.numeric_std.ALL;
use ieee.math_real.all;
 
entity CORDIC_VectorMode is
    generic(Data_Width : integer := 16;                                    --İşlenecek Veri Genişliği
        PipelineStage : integer := 8);                                     --Çekirdeğin Bulunduğu Pipeline Seviyesi
         
    port(Clk : in std_logic;                                               --Clock Girişi
        Xin, Yin, Zin : in std_logic_vector(Data_Width - 1 downto 0);      --Önceki CORDIC Çekirdeğinden Gelen X, Y, Z Girişleri
        Xout, Yout, Zout : out std_logic_vector(Data_Width - 1 downto 0)); --Sonraki CORDIC Çekirdeğine Gidecek X, Y, Z Çıkışları
end CORDIC_VectorMode;
 
architecture Behavioral of CORDIC_VectorMode is
     
    signal XS, YS, ZS : signed(Data_Width - 1 downto 0);
     
    --Phase hesabında kullanılacak arctanjant değeri
    --[-0.5, 0.5] aralığına normalize ediliyor
    constant AtanReal : real := ARCTAN(real(2) ** real(-PipelineStage)) * real(2**(Data_Width - 1)) / MATH_PI;
    signal Atan : signed(Data_Width - 1 downto 0);
     
begin
 
    --İşlemlerin daha kolay yapılabilmesi için giriş
    --sinyalleri signed tipine dönüştürülüyor
    XS <= signed(Xin);
    YS <= signed(Yin);
    ZS <= signed(Zin);
     
    --Arctanjant değeri de signed tipine dönüştürülüyor
    Atan <= to_signed(integer(AtanReal), Data_Width);
     
    --CORDIC işleminin gerçekleştiği process
    process(Clk)
    begin
        --Clock sinyalinin yükselen kenarı ile Pipeline ilerler
        if rising_edge(Clk) then
             
            --Eğer Ys değeri 0'dan küçük ise koordinatlar saat yönünün
            --tersinde döndürülüyor
            if Ys < 0 then
                --Signed tipinden tekrar std_logic_vector tipine dönüştürülüyor
                Xout <= std_logic_vector(XS - shift_right(YS, PipelineStage));
                Yout <= std_logic_vector(YS + shift_right(XS, PipelineStage));
                Zout <= std_logic_vector(ZS - Atan);
                 
            --Değil ise saat yönünde döndürülüyor
            else
                Xout <= std_logic_vector(XS + shift_right(YS, PipelineStage));
                Yout <= std_logic_vector(YS - shift_right(XS, PipelineStage));
                Zout <= std_logic_vector(ZS + Atan);
            end if;
        end if;
    end process;
 
end Behavioral;

Quartus II tarafından oluşturulan RTL şeması:

Çekirdeklerin seri bağlanmış hali:

Tasarımın VHDL kodu:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
----------------------------------------------------------
--                   CORDIC_MagPha.vhd
--                     Bertan Taşkın
--                       2.6.2017
--
-- CORDIC algoritmasını kullanarak (X,Y) noktası için
-- magnitude'u ve faz açısını hesaplayan modül. Pipeline
-- yapıya sahiptir. İşlenecek veri boyutu generic kısmındaki
-- Data_Width ile belirlenir. Pipeline uzunluğu ise PipelineLength
-- ile belirlenir.
--
-- Modül pipeline tabanlı olduğundan dolayı, yeni veriler
-- PipelineStage kadar gecikmeli hesaplanır. Sıralı giren veri
-- sayısı ne kadar fazla olursa verimlilik de o kadar yüksek olur.
--
-- N veri için toplam işlem süresi = PipelineStage + N - 1 Cycle
--
-- Giriş verilerinde kesinlikle fraction part bırakılmalıdır.
-- Toplam pipeline adım sayısı, giriş verilerinin fraction bit
-- sayısından 1 fazlasından fazla olması yüksek pipeline
-- adımlarının hassasiyetini düşürür.
--
-- Magnitude = MagnitudeOut / 2^Fraction_Bit_Sayısı
--
-- Faz açısı 1 işaret bitinden ve Data_Width-1 fraction bitinden
-- oluşur. [-0.5, 0.5] aralığında radyan cinsindendir.
--
-- Faz açısı = PhaseOut / 2^(Data_Width-1) Radyan
--           = PhaseOut / 2^(Data_Width-1) * 180 Derece
--
----------------------------------------------------------
 
 
--Kütüphaneler
library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
USE ieee.numeric_std.ALL;
use ieee.math_real.all;
 
entity CORDIC_MagPha is
    generic(Data_Width : integer := 16;                               --İşlenecek Veri Genişliği
        PipelineLength : integer := 9);                               --Pipeline Uzunluğu(Derinliği)
         
    port(Clk : in std_logic;                                          --Clock Girişi
        X, Y : in std_logic_vector(Data_Width - 1 downto 0);          --X, Y Girişleri
        MagnitudeOut : out std_logic_vector(Data_Width - 1 downto 0); --Magnitude Çıkışı
        PhaseOut : out std_logic_vector(Data_Width - 1 downto 0));    --Faz açısı Çıkışı
end CORDIC_MagPha;
 
architecture Behavioral of CORDIC_MagPha is
     
    --CORDIC algoritmasının kazancını 1'e düşürecek Kn değerini
    --hesaplayan fonksiyon
    --Kn = pi i:0->n 1/kök(1+2^(-2i))
    function Kn(n : integer) return signed is
    variable X : signed(Data_Width - 1 downto 0) := (others=>'0');
    variable K : real := 1.0;
    begin
 
        --Her bir CORDIC çekirdeğinin kazancının tersi çarpılarak
        --Kn değeri hesaplanır
        a : for i in 0 to n loop
            K := K / SQRT((real(1) + real(2) ** real(-2 * i)));
        end loop;
         
        --K sayısı, Data_Width kadar fraction bit sayısına sahip
        --fixed-point sayıya dönüştürülüyor
        K := K * real(2**(Data_Width - 1));
         
        X := to_signed(integer(K), Data_Width);
         
        return X;
    end Kn;
     
--Vectör modundaki CORDIC çekirdeği
component CORDIC_VectorMode
    generic(Data_Width : integer := 16;                                    --İşlenecek Veri Genişliği
        PipelineStage : integer := 8);                                     --Çekirdeğin Bulunduğu Pipeline Seviyesi
         
    port(Clk : in std_logic;                                               --Clcok Girişi
        Xin, Yin, Zin : in std_logic_vector(Data_Width - 1 downto 0);      --Önceki CORDIC Çekirdeğinden Gelen X, Y, Z Girişleri
        Xout, Yout, Zout : out std_logic_vector(Data_Width - 1 downto 0)); --Sonraki CORDIC Çekirdeğine Gidecek X, Y, Z Çıkışları
end component;
     
    type VectorArray is array(PipelineLength downto 0) of std_logic_vector(Data_Width - 1 downto 0);
    signal XBus, YBus, ZBus : VectorArray;
     
begin
 
    --CORDIC algoritmasının doğru çalışması için girilen koordinatların
    --koordinat ekseninin sağ düzleminde(-pi/2 < açı < pi/2) olması gerekir.
    --Eğer X koordinatı negatif ise (X,Y) noktası koordinat ekseninin sol
    --tarafındadır. Bunu düzeltmek için sonucu değiştirmeyen (-X,-Y) noktası
    --ile işleme devam edilir.
    with X(Data_Width - 1) select
        XBus(0) <= not X when '1',
                      X when others;
                       
    with X(Data_Width - 1) select
        YBus(0) <= not Y when '1',
                      Y when others;
 
    --İşlem öncesi (X,Y) noktası döndürülmeyeceğinden Z açısı 0 ile başlar
    ZBus(0) <= (others=>'0');
 
    --Son CORDIC çekirdeğinden çıkan Magnitude değeri, algoritmadan
    --kaynaklanan kazancı 1'e çekmek için Kn ile çarpılır
    MagnitudeOut <= std_logic_vector(shift_right(signed(XBus(PipelineLength)) * Kn(PipelineLength - 1), Data_Width - 1))(Data_Width - 1 downto 0);
     
    --Faz açısında herhangi bir ek işleme gerek yoktur
    PhaseOut <= ZBus(PipelineLength);
 
    --CORDIC çekirdeklerinin üretilmesi
    --Bütün CORDIC çekirdekleri birbirine seri bağlanır(Pipeline yapısı)
    U1: for i in 0 to PipelineLength - 1 generate
        CORDIC_Core: CORDIC_VectorMode
            generic map(Data_Width, i)
            port map(Clk,
                XBus(i), YBus(i), ZBus(i),
                XBus(i + 1), YBus(i + 1), ZBus(i + 1));
    end generate;
 
 
end Behavioral;

RTL şeması:

Kaynak kullanımı:

8 biti fraction olmak üzere 16-bit veri genişliği ve 9 pipeline derinliğine sahip uygulamanın ModelSim ile gerçekleştirilen testi:

1.Veri:

Giriş: x0=(0300)16×28=3,y0=(0400)16×28=4

Çıkış: Mag=(0500)16×28=5,Pha=(25E8)16×215×180=53.305664

Gerçek değer: Mag=5,Pha=53.130102

2.Veri:

Giriş: x0=(0400)16×28=4,y0=(FBFF)16×28=4

Çıkış: Mag=(05A8)16×28=5.65625,Pha=(E022)16×215×180=44.813232

Gerçek değer: Mag=5.656854,Pha=45

3.Veri:

Giriş: x0=(FAFF)16×28=5,y0=(0C00)16×28=12

Çıkış: Mag=(0D02)16×28=13.007812,Pha=(CFF6)16×215×180=67.554931

Gerçek değer: Mag=13,Pha=67.380135

4.Veri:

Giriş: x0=(D9FF)16×28=38,y0=(F8FF)16×28=7

Çıkış: Mag=(26A4)16×28=38.640625,Pha=(0768)16×215×180=10.415039

Gerçek değer: Mag=38.639358,Pha=10.437475

Bir cevap yazın

E-posta hesabınız yayımlanmayacak.