Salah satu cara untuk menghitung logaritma basis 2

Komputasi logaritma adalah operasi yang cukup umum dalam pemrosesan sinyal digital. Lebih sering, mungkin, hanya konvolusi (perkalian dengan akumulasi) dan amplitudo dengan fase harus dipertimbangkan. Sebagai aturan, untuk menghitung logaritma pada FPGA, algoritma CORDIC digunakan dalam versi hiperbolik, hanya membutuhkan tabel dan operasi aritmatika sederhana. Namun, ini tidak selalu nyaman, terutama jika proyeknya besar, kristalnya kecil dan tarian dengan optimasi dimulai. Dengan situasi seperti itulah saya harus menghadapi suatu hari. Kedua port blok RAM (Cyclone IV) sudah bekerja dengan erat, tanpa meninggalkan jendela gratis. Saya tidak ingin menggunakan blok lain untuk CORDIC hiperbolik. Tetapi ada pengganda, yang mana jendela bebas yang layak diperoleh dalam diagram waktu. Setelah berpikir satu hari, saya menyusun algoritma berikut, di mana tabel tidak digunakan, tetapi ada multiplikasi, lebih tepatnya mengkuadratkan. Dan karena kuadrat sirkuit lebih sederhana daripada kasus umum perkalian, mungkin algoritma ini menarik bagi chip khusus, meskipun tentu saja tidak ada perbedaan untuk FPGA. Lebih detail di bawah potongan.

Menjelaskan apa itu, lebih mudah untuk bilangan real. Mari kita mulai dengan mereka. Kami melanjutkan ke implementasi integer nanti.

Biarkan ada nomor X. Temukan nomor Y sedemikian rupa $$$X = 2 ^ Y$ .
Kami juga berasumsi bahwa X terletak pada rentang dari 1 hingga 2. Ini tidak membatasi terlalu banyak pada umumnya, karena X selalu dapat ditransfer ke interval ini dengan perkalian atau pembagian dengan kekuatan dua. Untuk Y, ini berarti menambah atau mengurangi integer, yang mudah. Jadi X terletak pada interval dari 1 hingga 2. Kemudian Y akan terletak pada interval dari 0 hingga 1. Kita menulis Y sebagai fraksi biner tak terbatas:

$$

$$Y = {b_0} 2 ^ 0 + {b_1} 2 ^ {- 1} + ... + {b_n} 2 ^ {- n} + ...$$

Peluang $$${b_i}$ dalam catatan ini tidak ada yang lebih dari sekadar bit dari representasi biner dari angka Y. Selain itu, karena Y kurang dari 1, jelas itu $$${b_0}$ = 0.

Mari kita kuadratkan persamaan pertama kita: $$$X ^ 2 = 2 ^ {2Y}$ dan seperti sebelumnya, kita menulis representasi biner dari 2Y . Jelas,

$$

$$2Y = {b_1} 2 ^ 0 + {b_2} 2 ^ {- 1} + ... + {b_n} 2 ^ {- (n-1)} + ...$$

Yaitu bit $$${b_i}$ tetap sama, hanya kekuatan dua bergerak. Kelelawar $$${b_0}$ tidak ada dalam tampilan karena sama dengan nol.

Ada dua kasus yang mungkin:

1) $$$X ^ 2> 2$ , 2Y> 1, $$${b_1} = 1$

2) $$$X ^ 2 <2$ , 2Y <1, $$${b_1} = 0$

Dalam kasus pertama, kita menganggap sebagai nilai baru X $$$X ^ 2/2$ di detik - $$$X ^ 2$ .

Akibatnya, tugas dikurangi menjadi yang pertama. X baru lagi terletak pada kisaran 1 hingga 2, Y baru dari 0 hingga 1. Tetapi kami mempelajari sedikit hasilnya. Mengambil langkah yang sama di masa depan, kita bisa mendapatkan bit Y sebanyak mungkin.

Mari kita lihat cara kerjanya dalam program C:

#include <stdio.h> #include <math.h> int main() { double w=1.4; double s=0.0; double a=0.5; double u=w; for(int i=0; i<16; i++) { u=u*u; if(u>2) { u=u/2; s+=a; } a*=0.5; } w=log2(w); double err=100*abs(2*(sw)/(s+w)); printf("res=%f, log=%f, err=%f%c\n",s,w,err,'%'); return 0; } 

Kami menghitung logaritma dengan akurasi 16 bit dan dibandingkan dengan apa yang diberikan perpustakaan matematika. Program membawa:

res = 0,485413, log = 0,485427, err = 0,002931%

Hasilnya bertepatan dengan perpustakaan dengan akurasi 0,003%, yang menunjukkan efisiensi algoritma kami.

Mari kita beralih ke implementasi integer.

Biarkan N-bit binary unsigned number mewakili interval [0, 1]. Untuk kenyamanan, kami mempertimbangkan nomor unit $$$2 ^ N$ tapi tidak $$$2 ^ N-1$ , dan sesuai nomor deuce $$$2 ^ {N + 1}$ . Kami akan menulis sebuah program dalam gambar dan rupa yang sebelumnya, tetapi bekerja dengan bilangan bulat:

 #include <stdio.h> #include <math.h> #define DIG 18 //  #define N_BITS 16 //    unsigned ONE=1<<(DIG-1); // unsigned TWO=ONE<<1; // unsigned SCALE=1<<(N_BITS+1); //  unsigned myLog(unsigned w) { unsigned s=0; unsigned long long u=w; for(int i=0; i<N_BITS+1; i++) { s<<=1; u=(u*u)>>(DIG-1); //    ! if(u&TWO) //      { u>>=1; s+=1; } printf("%X\n", (int)u); } return s; } int main() { double w=1.2345678; unsigned iw=(unsigned)(ONE*w); double dlog=log2(w); unsigned ilog=myLog(iw); unsigned test=(unsigned)(SCALE*dlog); int err=abs((int)(ilog-test)); printf("val=0x%X, res=0x%X, log=0x%X, err=%d\n",iw,ilog,test,err); return 0; } 

Setelah bermain dalam program dengan kedalaman bit berbeda (DIG), akurasi perhitungan (N_BITS), dan argumen logaritma (w), kami melihat bahwa semuanya dihitung dengan benar. Secara khusus, dengan parameter yang ditentukan dalam sumber ini, program menghasilkan:

val = 0x27819, res = 0x9BA5, log = 0x9BA6, err = 1

Sekarang semuanya siap untuk mengimplementasikan sepotong besi pada veril, melakukan hal yang persis sama dengan fungsi myLog di C. Variabel s dan u dalam fungsi kita dapat dicetak dalam satu lingkaran dan dibandingkan dengan apa yang diproduksi oleh simulator Verilog. Korespondensi dari variabel-variabel ini dengan implementasi besi sangat transparan dan dapat dimengerti. u adalah register yang berfungsi yang mengambil nilai baru X selama iterasi. s adalah register geser di mana hasilnya diakumulasikan. Antarmuka modul kami akan terlihat seperti ini:

 module logarithm( input clk, // input wr, //   input[17:0] din, //   output[nbits-1:0] dout, //   output rdy //  ); parameter nbits=16; //  

Input bus diadopsi 18-bit, masing-masing, lebar pengganda di Siklon IV. Angka-angka pada modul kami harus dinormalisasi. Yaitu dengan bit tinggi sama dengan satu. Dalam proyek saya, ini dilakukan secara otomatis. Tetapi dalam hal menerapkan normalizer, saya pikir itu tidak sulit bagi siapa pun. Keakuratan perhitungan diatur oleh parameter nbits, secara default sama dengan 16. Modul menghitung satu bit per siklus, dan untuk 16 siklus menghitung logaritma dengan akurasi 16 bit. Jika Anda membutuhkan lebih cepat dengan akurasi yang sama atau lebih tepatnya dengan kecepatan yang sama, saya harap tidak ada yang akan mengalami kesulitan membagi modul menjadi beberapa perangkat dan pipelining.


Jalankan tes dengan skrip ini:

 #!/bin/sh rm -f *.vvp rm -f *.vcd iverilog -o testbench.vvp logarithm.v testbench.v vvp testbench.vvp gtkwave testbench.vcd testbench.gtkw 

Menjalankan tes, kita melihat hasil akhir dari simulator - nilai = 27819, hasil = 9ba5. Verilog memberikan hal yang sama dengan C. Diagram waktu di sini cukup sepele dan tidak terlalu menarik. Karena itu, saya tidak membawanya.


Pastikan mereka cocok sedikit demi sedikit. Secara total, implementasi pada verilo mengulangi model C hingga sedikit, ini adalah hasil yang harus dicapai dengan mengimplementasikan algoritma dalam perangkat keras.

Itu mungkin saja. Saya harap seseorang akan menemukan pengalaman saya ini berguna.