Cordic Algoritması Hakkında

[z]

VHDL ile Cordic (sin & cos) Tasarımı...
http://www.alicavuslu.gen.tr/2014/12/23/vhdl-ile-cordic-tasarimi/

@Aliçavuşlu.

Cordic algoritması ile sin cos işleminin prensibini anlatabilirmisin?

[alicavuslu]

Cordic genellikle trigonometrik ve hiperbolik fonksiyonların değerlerinin hesaplanmasında kullanılan bir yöntem. Her yöntemde uygulayacağınız matematiksel yaklaşım değerleri farklılıklar gösterecektir. Sinüs ve cosinüs değerlerini elde edebilmek için uygulayacağınız döngü değerleri kadar sabit parametre değerlerini elde ediyoruz. 20 iterasyon için angles = atan(2.^-(0:19)); ve Kvalues adlandırdığımız 20 adet sabit değeri elde ediyoruz. Döngü sayısının artırılması daha iyi sonuç elde etmemizi sağlar.

Daha sonraki işlemlerde adım adım bulunması istenen açı değerine yaklaşım yapılmaktadır. İterasyon bitiminde ise algoritma açı değerleri sonuçlarını döndürmektedir. Daha öncede dediğim gibi iyi sonuç elde etmek için döngü sayısının fazla olmasını öneririm.

Detaylı bilgiyi aşağıdaki linkten elde edebilirsiniz. Umarım ifade edebilmişimdir.

https://en.wikipedia.org/wiki/CORDIC

[z]

Cordic konusuna defalarca baktım fakat anlayamadım. O yüzden sordum. Müsait bir zamanınızda algoritmayı sözel olarak açıklarsanız çok memnun olurum.

[alicavuslu]

Cordic algoritması, X-Y eksenlerindeki mevcut olan iki vektörün arasındaki açının vektörlerin koordinat sistemlerinde kaydırılması metodu olarak ifade edilebilir. Açı değeri X-Y eksenlerinde kaydırma ve toplama işlemleri ile hesaplanır. Cordic Algoritması gerçeklenmesi aşağıdaki şekilde gösterilmiştir.



Bir sonraki vektör pozisyonlarının hesaplama işlemleri aşağıda verilen matematiksel ifadedeki gibidir.



Yukarıda da bahsedildiği gibi eksenler arasında kaydırma işlemlerin yapılması için kullanılan Ө açı değerinin her iterasyonda hesaplama işlemi aşağıdaki gibi hesaplanmaktadır.



Cordic algoritmasının çalışma prensibini biraz da sayı tahmini uygulamasına benzetmekteyim. Başlangıç koşulundan başlayıp kontroller ile varmak istediğiniz sayıyı tahmin ediyorsunuz. Aşağıda bunu tanımlayan bir örnek mevcuttur.

[z]

AliÇavuşlu hocam ellerine sağlık. Teşekkürler.

Cordic algoritmasından ilk kez 90 lı yıllarda haberdar oldum. Okuduğumda hiç bir şey anlamadım. Bugüne kadar nerede Cordic görsem muhakkak okurum ama gene anlamam.

Şimdi de anlamadım. Bu Cordic'i  okuyarak değil ancak birinden dinleyerek anlayabilirim diyordum ki seni buldum.

Acelem yok. Soru cevap şeklinde gidebilirmiyiz?



Mesela 52 derecenin sinüsünü bulalım dendiğinde 52 derece grafikteki hangi açıya karşılık geliyor?

[alicavuslu]

Hocam tabloyu verirken eksik bilgi verdim. Kusura bakmayın. Tabloda 37.38 derece açıya yaklaşık değeri bulmaya çalışılmaktadır. 0-100 aralığında bir sayıyı programımıza tahmin ettirmek istediğimiz yazılımda ilk değerimiz 50 olur. Yukarı veya aşağı komuta göre sayıya 25 eklenir ya da çıkarılır. Benzer şekilde bir sonraki adımda 12.5 eklenir çıkarılır (Bu kısmı tam ifade edememiş olabilirim.).

Tabloyu incelediğimizde referans açı değerimiz 0'dır. -90 ve +90 derece aralığında tahmin etmemiz gerekmektedir. Tabloda bu kısım eksik gibi. 37.38 derecenin referans olarak bulunması istenmiş. Biz ilk olarak  45 dereceyi ekleme yapıyoruz. Daha sonra ise yukarıda 2. olarak verdiğimiz formülden hesaplanmış olan açı değerini çıkarıyoruz. Buda 26.6 derecedir. Yeni değerimiz 18.4 derece oldu. 3. adımda ise tekrar 2. formülde hesaplanan yeni 3. açı değeri 14, 18.4 dereceye eklenmektedir. Yeni değer 32.4 olamktadır. Yani algoritma o anki iterasyonda size 32.4 derecenin sonuçlarını vermektedir. İterasyon sayısının artması ile elde edeceğiniz açı değeri referans değerine çok fazla yaklaşacaktır. 7. iterasyonda 0.58 derecelik fark elde edilmiş. Örneğin 28 iterasyonda bu fark daha da azalacaktır.

Grafikte Y olarak ifade edilen değer sinüs, X olarak ifade edilen değer cosinüse karşılık gelmektedir.

Anlaşılmayan yerler varsa dilim döndüğünce ifade etmeye çalışırım...

[z]

Anlamaya başladım.

Öncelikle  1, 1/2,  1/4, 1/8, 1/16, 1/32, 1/64, 1/128 .... şeklinde yani

1, 0.5,  0.25, 0.125, 0.0625, ..... şeklinde değerlere ait ArcTan tablosu hazırlıyoruz.

ArcTan(1) ile 45 dereceyi
ArcTan(0.5) ile 26.565 dereceyi
ArcTan(0.25) ile 14.036 dereceyi
ArcTan(0.125)=7.125 dereceyi
.....

Tablomuzda saklıyoruz.

Böyle bir tablomuz var.

37.38 derecenin sinüsü hesaplanmak istensin.

1) İşleme 0 derece ile başlıyoruz.

45 derece eklersek yeni açımız 45 derecedir ve 45>37.38  olduğundan bu kez

1) 45-26.565=18.435 işlemini yapıyoruz.

18.435 < 37.38 bu durumda

18.435 + 14.036 = 32.471

32.471<37.38 bu durumda

32.471 + 7.125 = 39.596

39.596 > 37.38 bu durumda bir sonraki tablo değerini bu açıdan çıkartacağız.

Çok sağolasın.

Bundan sonra anlaşılması gereken kısım trigonometrik bağıntı kısmı. Yani yukarıdaki şekilde açıya tablodaki sıralanmış değerlerrle toplam yada fark alarak yaklaşırken
aranan sinüs değerinin nasıl hesaplandığı.

Gerçekten çok teşekkürler.

[alicavuslu]

Hocam açı hesaplama işlemlerini de 1. denklemdeki gibi yapıyoruz. Bu denklemde ise bir önceki adımdaki hesaplanan X ve Y vektör değerlerini hesaplanan fark açı deperi kadar kaydırma işlemi yapiyoruz. Yani şekle baktığımızda beta olan ilk açı değeri teta kadar artıyor ve yeni açı değeri alfa oluyor. Biz 1. denklem ile beta açısı ile konumlanmış vektörleri teta kadar kaydırarak alfa değerindeki değerlerde konumlandırıyoruz. Başlangıç değerleri burada X için 1 Y için de 0 değeri alınarak kaydırılıyor.

[z]

Qn acısını bılıyoruz ve deltateta kadar ilerleyip Qn+1 açısına ulaşıyoruz.

Aşağıdaki işlemlerle sonuca ulaştım. Ancak verdiğiniz bağıntıdan biraz farklı.



Yaptığım işlemlerde ve sonuçta bir terslik varmı?

Fakat Cordicde  çarpma vs olmaz sadece toplama ve kaydırma var deniyordu.

Benim bulduğumen son ifadeye göre

Xn+1 ve yn+1 değerelerini Xn, Yn ve Tan Delta teta dan hesaplayabiliyoruz.

TanDelta Theta tablosu zaten hazırlanmıştı yani aşağıdaki gibi mevcut.



En son asamada

Sinüs değerimizi   yn+1 / (Karekok( Yn+1^2 + Xn+1^2)) den mi hesaplayacağız?


!!!!!!!! Yoksa bir dakika Yn+1 doğrudan bizim sinüs değerimiz mi? !!!!!!!!!!!!


mesaj birleştirme:: 10 Eylül 2015, 14:11:54
Evet yahu burada çarpma yapmıyoruz. Tan Delta Theta değerleri 2^n-1 değerlerinden ibaret. Dolayısı ile sağa kaydırma yapmak yetiyor.

Topla kaydır, topla kaydır yada çıkart kaydır.

Ne yalan söyleyeyeyim 2003 yılından beri forma üyeyim. 

Forum bugün bana bu konu ile en büyük katkıyı sağladı.

Sağolasın Aliçavuşlu.

Fotosunu verdiğim elişlemlerinde hata yamış olsam bile artık gerisini hallederim.

Cordic'i kim ortaya attıysa gerçekten zeki bir adammış.

Pratikteki uygulamaları sanırım yaygın olarak ilk kez HP yapmış ve hesap makinelerinde kullanmıştı.

Diğer firmalar seri açılım yaparken HP cordic kullanmıştı.

[alicavuslu]

Hocam yaptığınız işlem ile matris çarpımının sonucu aynı.



Dediğiniz gibi Yn+1 bizim sünüs, Xn+1 de cosinüs değerimizi vermektedir. Sadece işlem sonunda bu değerleri sabit bir katsayı ile çarpmamız gerekmektedir. Bu sayıda itersayonu çok fazla almanız durumunda  0.607252935 olmaktadır.

[z]

Bu  0.607252935 nerden geldi şimdi?

Neden çarpıyoruz?

Birde fazla üzerinde durmadım ama aşağıdaki matrisin önündeki cos terimi nerden çıktı?



Yukarıdaki ifadeye göre

Xn+1=Xn CosQ - Yn SinQ
Yn+1=Xn SinQ  + Yn CosQ

çıkmıyormu?

Halbuki ben

Xn+1=Xn - Yn tanQ
Yn+1=Yn + Xn tanQ

Buldum.

Edit: Galiba ben Delta Thetayı kullanıyorum. Senin verdiğin ifade bir önceki açı değeri Thetayı kullanıyor.

Sorun yok galiba.

[alicavuslu]

Cos teta her iterasyonda da kullanılabilir fakat genel kullanılmıyabiliyor. Aslında o ifadenin karşılığı aşağıda eşitliğin ilk tarafında gösterilen kısım. Bu eşitlik cos tetaya karşılık geliyor mu açıkçası hesaplayamadım. İkisi farklı çalışmadaki gösterim. Müsait bir zamanda onunda kontrolünü yaparım.



Fakat algoritma koşturulurken bu parametre kullanılmıyor. Bunu ayarlama parametresi gibi düşünebilirsiniz. Çıkışta sizi olmanız gereken eksene yaklaştırıyor. Bu sayıda aşağıdaki denklemdeki gibi hesaplanıyor. Açıkçası çokta üzerinde durmamızı gerektirecek bir nokta değil.

[z]

Neyse kafa yorarım.

Şimdi can alıcı bir konuya geliyoruz.

Sin fonksiyonunu noktadan sonra 10 digit doğrulukla hesaplamak istiyorsak

Ara işlemleri yaparken sabit bit uzunluğu ile çalışıyor olalım.

ikili sistem aritmetiğinde kullanmamız gereken bit uzunluğu en az ne olmalıdır?

Bu soru hep kafamı karıştıran bir soru olmuştur.

[alicavuslu]

Hocam VHDL kodları aslinda tam da bu sorunuza cevap olacak şekilde kodlandı. Generic kısımda tanımlanmış  MUL_COEFF ve DATA_SIZE sabitleri ile ayarlamalar yapabilirsiniz. Burada  MUL_COEFF örneklenmiş sinyalin bit uzunluğunu göstermektedir. Yani simülasyon sonuçlarını size yorumladığımda 20 bitlik bir uzunluktaki sonuç işleminde yaklaşık on binde birden daha az hata oranı elde etmektesiniz. Buda sizin için göz ardı edilebilecek bir hata oranı olmaktadır.16 bit için yaptığım simülasyonda da on binde 5 civarı hata çıkıyor. Ki buda göz ardı edilebilir. 12 bit için hata binde bir civarında. Göz ardı etmek pekte mantıklı olmayabilir. Geri beslemeli bir sistem için büyük sorun teşkil edebilir.

Bu değerler daha detaylı analiz edilip ifade edilmeli. Ben şimdlik sizin aklınızdaki soruları gidermek için cevaplamaya çalıştım.

[z]

Aslında sorumun cevabına nasıl matematiksel olarak yaklaşılacağını merak ediyorum.

Ve bu tartışma bana göre düşüncemi haklı çıkartttı.

Düşüncem, bu tip algoritma tartışmalarını;

ya donanım tasarımcıları ile yapacaksın (ki burada, VHDL tasarımcısı olarak sen oluyorsun),
ya da asm programlama yapanlarla,

tartışacaksın.