Algoritma

CORDIC algoritması

Trigonometrik fonksiyonlar, sonsuz sayıda elemandan oluşan bir serinin açılımı şeklinde ifade edilebilir. Taylor serisi denilen bu serilerin ilk 8-10 elemanını hesaplayarak gerçek değerlere yeterince yakın sonuçlar elde edebiliriz.

Fakat bu seriler içerisinde çarpma işlemini barındırır ve çarpma işlemi bilgisayarlar için maliyetli bir işlemdir. Öyleyse bize çarpma/bölme gibi kompleks işlemleri barındırmayan başka bir metod lazım, CORDIC algoritması gibi.

CORDIC (for COordinate Rotation DIgital Computer) algoritması, isminden de anlaşılacağı gibi bir vektörü orijin etrafında döndürerek istenilen açı değerini yakalama üzerine dayalıdır.

Döndürme işlemi için aşağıda gördüğünüz matris-vektör çarpımı kullanılır. Formüldeki theta açıları, vektörün kaç derece döndürüleceğini söyler. Eşitliğin sağında döndürülecek vektör, solunda ise döndürme işlemi sonucu elde edilen vektör yer alır. Matrisin yanındaki cosinüs fonksiyonuna yazının sonunda değinilecektir.

Aşağıda matris vektör çarpımının açılmını ve koordinat sistemi üzerinde görselleştirilmesini görüyorsunuz.

Herhangi bir vektörü bu matris ile çarparak istediğimiz miktarda döndürebilirsiniz. Döndürme sonrası elde edilen vektörün x,y değerleri ile istenilen açıya ait trigonometrik fonksiyon kolayca hesaplanır.

Fakat matrislerin içerisinde tanjant fonksiyonları var. Amacımız zaten trigonometrik fonksiyonları hesaplamak olduğu için bu tanjantlardan kurtulmalıyız. Tanjant fonksiyonlarının sayısal karşılıklarını bir tablo içerisine yazıp, daha sonra formülde kullanmamız gerekecek.

Tabloyu oluştururken akla gelebilecek ilk yöntem, tüm açı değerlerini tabloya yerleştirmek olacaktır. Aşağıda resimde (1,0) vektörünü ve 1’den 90’a tüm açıların tanjant değerlerinin yazılı olduğu bir tablo görüyorsunuz. 1 derecelik açı mı lazım? Direkt tablodan 1’e karşılık gelen tanjant değerini al, matrise yaz ve vektörle çarp. İyi bir yöntem gibi görünse de, tüm açı değerlerini tabloya yazması ve küsüratlı açıları hesaplayamaması bu yöntemi geçersiz kılıyor.

Tüm açıları tabloya yazmayı denedik, olmadı. Onun yerine tabloya sınırlı sayıda açının tanjant değerini yazıp, bu açıları kullanarak istenilen açıyı elde etmeye çalışacağız.

Algoritmayı sayı tahmin oyununa benzetebilirsiniz. Karşınızdaki 1-100 arasında bir sayı tuttuğunda ilk tahmininiz 50, sayının daha mı düşük veya daha mı yüksek olmasına göre ikinci tahmininiz 25 (50 – 25) veya 75 (50 + 25) olur.

İstenilen açı değeri 60 olduğunda ilk 3 adım

Bu yöntem ile istenilen açıya yeterince yakın bir değer elde edebiliriz, üstelik küsüratlı açılarda da iş görüyor. Fakat yazımızın başında amacımızın çarpma işleminden kurtulmak olduğunu söylemiştik. Serilerdeki gibi bir dizi çarpma işlemi uyguluyoruz, bundan nasıl kurtulabiliriz? Cevap basit, tablodaki açıları tanjant değerleri özellikle 2’nin üssü olacak şekilde seçerek.

Çarpma işlemlerini shifting’e dönüştürdük.

Hatırlarsanız matrislerin başında bir cosinüs çarpanı vardı. Bu cosinüsler, matrisleri çarparken birikmeye başlar. cos(45)*cos(26.6)*cos(14)*cos(7.1) diye devam eden bu cosinüs topluluğu belli bir limit değere, 0.60725.. sayısına yaklaşmaktadır. Bu sayı K ile gösterilir ve eşitliğin sağ tarafındaki elde edilen vektör ile çarpılır.

C ile yazdığım cordic algoritmasına buradan ulaşabilirsiniz : https://github.com/farukcansaglam/cordic

Leave a Reply

Your email address will not be published. Required fields are marked *