Alasan CORDIC tinggal gratis di hati saya
Menghindari Floating Point dengan menggunakan Fixed Point
- Dengan menggunakan Fixed Point alih-alih Floating Point, bilangan riil dapat direpresentasikan
- Menggunakan bilangan bulat 32-bit, dengan 16 bit atas sebagai bagian integer dan 16 bit bawah sebagai bagian pecahan
- Dengan ini, nilai dari sekitar -32768.99997 hingga 32767.99997 dapat direpresentasikan
- Programmer dapat menyesuaikan presisi dengan menentukan posisi titik biner
- Untuk mengonversi Float ke Fixed Point, kalikan dengan 2^16 lalu cast ke
int32_t
- Untuk mengonversi Fixed Point ke Float, bagi dengan 2^16
- Penjumlahan dan pengurangan bekerja apa adanya, sedangkan perkalian dan pembagian perlu menyesuaikan Scaling Factor
Gambaran umum algoritma CORDIC
- CORDIC adalah singkatan dari "Co-ordinate Rotation Digital Computer", dikembangkan pada pertengahan 1950-an
- Ini adalah metode untuk memperoleh nilai sinus dan kosinus dengan memutar vektor pada lingkaran satuan secara bertahap dengan sudut-sudut kecil
- Mirip pencarian biner, mula-mula bergerak dengan sudut besar agar mendekati sudut target, lalu mengurangi sudut setengah demi setengah searah atau berlawanan arah jarum jam hingga konvergen
- Sudut rotasi maksimum ditetapkan 90 derajat (
π/2 radian), lalu diulang 16 kali agar konvergen mendekati sudut target
- Nilai y dari vektor yang telah konvergen kira-kira adalah sin(a), dan nilai x kira-kira adalah cos(a)
Menyederhanakan matriks agar hanya menggunakan perkalian konstanta
- Matriks rotasi memuat fungsi sinus, kosinus, dan tangen sehingga perhitungannya rumit
- Karena fungsi tangen berputar pada sudut tetap, nilainya dapat dihitung sebelumnya dan disimpan dalam tabel (sekitar 64 byte)
- Suku kosinus muncul pada setiap iterasi, tetapi karena nilai konvergensinya adalah konstanta (sekitar 0.6366), cukup dikalikan sekali saja di akhir
Hanya menggunakan operasi Shift dan Add
- Sudut yang digunakan pada fungsi tangen dipilih sebagai nilai 2^-i dengan menggunakan fungsi arctangent
- Dengan demikian, perkalian dapat diganti dengan operasi bit shift
- Nilai konvergensi suku kosinus juga dihitung ulang menjadi sekitar 0.60725, lalu ditetapkan sebagai nilai x dari vektor awal
- Setiap iterasi algoritma CORDIC kemudian disederhanakan sebagai berikut
- Jika z lebih besar atau sama dengan 0, putar berlawanan arah jarum jam (kurangi x dengan
y>>i, tambahkan x>>i ke y)
- Jika z lebih kecil dari 0, putar searah jarum jam (tambahkan
y>>i ke x, kurangi y dengan x>>i)
- Perbarui z dengan mengurangkan atau menambahkan nilai sudut dari tabel
- Dengan ini, perhitungan fungsi trigonometri dapat dilakukan hanya dengan perkalian konstanta, bit shift, dan operasi penjumlahan
Opini GN⁺
- CORDIC tampak sebagai algoritma yang berguna di lingkungan dengan sumber daya perangkat keras terbatas seperti sistem embedded atau FPGA. Ini terutama layak dipertimbangkan ketika operasi floating-point tidak didukung.
- Gagasan memilih sudut fungsi tangen secara strategis agar perkalian bisa diganti dengan bit shift sangat mengesankan. Ini contoh bagus perpaduan antara wawasan matematis dan pemahaman arsitektur komputer.
- Menarik juga bahwa algoritma ini dapat digunakan bukan hanya untuk fungsi trigonometri, tetapi juga untuk menghitung logaritma, eksponen, akar kuadrat, dan fungsi lain. Algoritma terkait seperti BKM juga patut dilihat.
- Namun, pada perangkat keras modern FPU sering kali sudah tertanam, dan penggunaan fixed-point dapat menimbulkan kehilangan presisi, jadi penerapannya perlu kehati-hatian.
- Jika sebuah sistem harus sering melakukan perhitungan serupa, mungkin layak juga mempertimbangkan desain perangkat keras khusus untuk CORDIC.
1 komentar
Komentar Hacker News
Algoritme CORDIC bisa dimanfaatkan bukan hanya untuk FPGA, tetapi juga untuk pengembangan game atau simulasi fisika terdistribusi. Perhitungan floating-point sulit menjamin perilaku deterministik lintas platform, sehingga menerapkan mesin fisika fixed-point dan mengimplementasikan fungsi trigonometri dengan CORDIC bisa menjadi salah satu solusinya.
CORDIC dapat digunakan untuk berbagai operasi, bukan hanya sinus dan kosinus, tetapi juga logaritma, eksponensial, akar kuadrat, magnitudo vektor, konversi koordinat polar-kartesius, rotasi vektor, dan lain-lain. Dengan menggunakan quaternion, operasi berbasis CORDIC tampaknya dapat dilakukan dengan lebih efisien dan akurat.
Ada yang berbagi pengalaman pernah belajar tentang implementasi fungsi trigonometri pada kalkulator di kelas pra-kalkulus SMA, lalu mengetahui bahwa yang digunakan ternyata bukan deret Taylor melainkan CORDIC, dan kemudian mencoba mengimplementasikannya sendiri dengan TI Basic.
Pada 2023, bahkan MCU murah seperti STM32G4 sudah dilengkapi FPU, sehingga floating-point bisa digunakan dengan leluasa alih-alih fixed-point. Namun, G4 juga memiliki periferal CORDIC yang diimplementasikan sebagai hardware khusus, yang tampaknya ditujukan untuk menghindari kehilangan presisi floating-point.
Sepertinya ada kesalahan pada penjelasan bahwa rotasi 22.75° sama dengan rotasi 45° lalu -22.5°. Kemungkinan yang benar adalah 22.5°.
Sistem octree Meagher diimplementasikan hanya dengan operasi integer, tanpa perkalian/pembagian integer. Ini memudahkan pembuatan hardware akselerasi grafis VLSI yang cepat dan dibuat khusus untuk representasi octree.
CORDIC bisa dipandang sebagai konsep yang mirip dengan barisan Farey untuk sudut (atau mediant, penjumlahan pecahan naif).
CORDIC juga pernah diimplementasikan pada kalkulator HP vintage yang dapat diprogram dengan CPU 4-bit. Metode aproksimasi menggunakan deret Taylor untuk fungsi sinus juga bisa diprogram.
Jika menyukai tulisan ini, ada baiknya juga membaca karya klasik Donald Knuth, "The Art of Computer Programming", yang menjelaskan algoritme matematika disertai contoh.
CORDIC adalah algoritme yang dulu sangat populer di bidang DSP.
Ini algoritme yang keren, dan tampaknya berguna untuk menjalankan jaringan saraf pada hardware berperforma rendah.