metode komputasi titik tetap atan2 pada FPGA

Saya membutuhkan komputasi atan2(x,y)pada FPGA dengan aliran input / output data yang berkelanjutan. Saya berhasil mengimplementasikannya menggunakan kernel CORDIC yang belum di-pipeline, tetapi untuk mendapatkan akurasi yang saya butuhkan, saya harus melakukan 32 iterasi. Hal ini menyebabkan sejumlah besar LUT dikhususkan untuk tugas yang satu ini. Saya mencoba mengubah aliran untuk menggunakan kernel CORDIC yang tidak dikontrol sebagian, tetapi kemudian saya membutuhkan frekuensi clock yang dikalikan untuk mengeksekusi loop berulang sambil tetap mempertahankan aliran input / output yang berkelanjutan. Dengan ini, saya tidak dapat menemukan waktu.

Jadi sekarang saya mencari cara komputasi alternatif atan2(x,y).

Saya berpikir tentang menggunakan tabel look-up blok-RAM dengan interpolasi, tetapi karena ada 2 variabel saya akan membutuhkan 2 dimensi tabel lookup, dan ini sangat sumber daya intensif dalam hal penggunaan block-RAM.

Saya kemudian berpikir untuk menggunakan fakta yang atan2(x,y)terkait atan(x/y)dengan penyesuaian kuadran. Masalahnya adalah ini x/yperlu pembagian yang benar karena ytidak konstan, dan pembagian pada FPGA sangat intensif sumber daya.

Apakah ada cara baru untuk menerapkan atan2(x,y)pada FPGA yang akan menghasilkan penggunaan LUT yang lebih rendah, tetapi masih memberikan akurasi yang baik?

Anda dapat menggunakan logaritma untuk menyingkirkan divisi. Untuk $(x, y)$ di kuadran pertama:

$$z = \log_2(y)-\log_2(x)\\ \text{atan2}(y, x) = \text{atan}(y/x) = \text{atan}(2^z)$$

Gambar 1. Plot $\text{atan}(2^z)$

$\text{atan}(2^z)$$-30 < z < 30$$\text{atan}(2^{-z}) = \frac{\pi}{2}-\text{atan}(2^z)$$(x, y)$$\log_2(a)$

$$b = \text{floor}(\log_2(a))\\ c = \frac{a}{2^b}\\ \log_2(a) = b + \log_2(c)$$

$b$$c$$\log_2(c)$$1 \le c < 2$

$\log_2(c)$

$2^{14} + 1 = 16385$$\log_2(c)$$30\times 2^{12} + 1 = 122881$$\text{atan}(2^z)$$0 < z < 30$$z$

$\text{atan}(2^z)$$z$$z$$0 \le z < 1$$\text{floor}(\log_2(z)) = 0$

$\text{atan}(2^z)$$0 \le z < 1$$\text{floor}(\log_2(z))$$z \ge 1$$\text{atan}(2^z)$$z$$0 \le z < 32$

Untuk referensi nanti, berikut ini adalah skrip Python kikuk yang saya gunakan untuk menghitung kesalahan aproksimasi:

from numpy import *
from math import *
N = 10
M = 20
x = array(range(N + 1))/double(N) + 1
y = empty(N + 1, double)
for i in range(N + 1):
    y[i] = log(x[i], 2)

maxErr = 0
for i in range(N):
    for j in range(M):
        a = y[i] + (y[i + 1] - y[i])*j/M
        if N*M < 1000: 
            print str((i*M + j)/double(N*M) + 1) + ' ' + str(a)
        b = log((i*M + j)/double(N*M) + 1, 2)
        err = abs(a - b)
        if err > maxErr:
            maxErr = err

print maxErr

y2 = empty(N + 1, double)
for i in range(1, N):
    y2[i] = -1.0/16.0*y[i-1] + 9.0/8.0*y[i] - 1.0/16.0*y[i+1]


y2[0] = -1.0/16.0*log(-1.0/N + 1, 2) + 9.0/8.0*y[0] - 1.0/16.0*y[1]
y2[N] = -1.0/16.0*y[N-1] + 9.0/8.0*y[N] - 1.0/16.0*log((N+1.0)/N + 1, 2)

maxErr = 0
for i in range(N):
    for j in range(M):
        a = y2[i] + (y2[i + 1] - y2[i])*j/M
        b = log((i*M + j)/double(N*M) + 1, 2)
        if N*M < 1000: 
            print a
        err = abs(a - b)
        if err > maxErr:
            maxErr = err

print maxErr

y2[0] = 15.0/16.0*y[0] + 1.0/8.0*y[1] - 1.0/16.0*y[2]
y2[N] = -1.0/16.0*y[N - 2] + 1.0/8.0*y[N - 1] + 15.0/16.0*y[N]

maxErr = 0
for i in range(N):
    for j in range(M):
        a = y2[i] + (y2[i + 1] - y2[i])*j/M
        b = log((i*M + j)/double(N*M) + 1, 2)
        if N*M < 1000: 
            print str(a) + ' ' + str(b)
        err = abs(a - b)
        if err > maxErr:
            maxErr = err

print maxErr

P = 32
NN = 13
M = 8
for k in range(NN):
    N = 2**k
    x = array(range(N*P + 1))/double(N)
    y = empty((N*P + 1, NN), double)
    maxErr = zeros(P)
    for i in range(N*P + 1):
        y[i] = atan(2**x[i])

    for i in range(N*P):
        for j in range(M):
            a = y[i] + (y[i + 1] - y[i])*j/M
            b = atan(2**((i*M + j)/double(N*M)))
            err = abs(a - b)
            if (i*M + j > 0 and err > maxErr[int(i/N)]):
                maxErr[int(i/N)] = err

    print N
    for i in range(P):
        print str(i) + " " + str(maxErr[i])    

$f(x)$$\hat{f}(x)$$f(x)$$\Delta x$

$$\widehat{f}(x) - f(x) \approx (\Delta x)^2\lim_{\Delta x\rightarrow 0}\frac{\frac{f(x) + f(x + \Delta x)}{2} - f(x + \frac{\Delta x}{2})}{(\Delta x)^2} = \frac{(\Delta x)^2 f''(x)}{8},$$

di mana adalah turunan kedua dari dan adalah maksimum lokal dari kesalahan absolut. Dengan yang di atas kita mendapatkan perkiraan:$f''(x)$$f(x)$$x$

$$\widehat{\text{atan}}(2^z) - \text{atan}(2^z) \approx \frac{(\Delta z)^2 2^z(1 - 4^z)\ln(2)^2}{8(4^z + 1)^2},\\ \widehat{\log_2}(a) - \log_2(a) \approx \frac{-(\Delta a)^2}{8 a^2\ln(2)}.$$

Karena fungsinya cekung dan sampel cocok dengan fungsinya, kesalahan selalu ke satu arah. Kesalahan absolut maksimum lokal dapat dikurangi setengahnya jika tanda kesalahan dibuat bergantian bolak-balik setiap interval pengambilan sampel. Dengan interpolasi linier, hasil yang mendekati optimal dapat dicapai dengan memfilter setiap tabel dengan:

$$y[k] = \cases{\begin{array}{rrrrrl}&&b_0x[k]&\negthickspace\negthickspace\negthickspace+ b_1x[k+1]&\negthickspace\negthickspace\negthickspace+ b_2x[k+2]&\text{if } k = 0,\\ &c_1x[k-1]&\negthickspace\negthickspace\negthickspace+ c_0x[k]&\negthickspace\negthickspace\negthickspace+ c_1x[k+1]&&\text{if }0 < k < N,\\ b_2x[k-2]&\negthickspace\negthickspace\negthickspace+ b_1x[k-1]&\negthickspace\negthickspace\negthickspace+ b_0x[k]&&&\text{if } k = N, \end{array}}$$

di mana dan adalah asli dan tabel yang difilter mencakup rentang dan bobotnya adalah . Pengkondisian akhir (baris pertama dan terakhir dalam persamaan di atas) mengurangi kesalahan pada ujung tabel dibandingkan dengan menggunakan sampel fungsi di luar tabel, karena sampel pertama dan terakhir tidak perlu disesuaikan untuk mengurangi kesalahan dari interpolasi antara itu dan sampel di luar tabel. Subtabel dengan interval pengambilan sampel yang berbeda harus difilter secara terpisah. Nilai bobot ditemukan dengan meminimalkan secara berurutan untuk meningkatkan eksponen$x$$y$$0 \le k \le N$$c_0 = \frac{9}{8}, c_1 = -\frac{1}{16}, b_0 = \frac{15}{16}, b_1 = \frac{1}{8}, b_2 = -\frac{1}{16}$$c_0, c_1$$N$ nilai absolut maksimum kesalahan perkiraan:

$$(\Delta x)^N\lim_{\Delta x\rightarrow 0}\frac{\left(c_1f(x - \Delta x) + c_0f(x) + c_1f(x + \Delta x)\right)(1-a) + \left(c_1f(x) + c_0f(x + \Delta x) + c_1f(x + 2 \Delta x)\right)a - f(x + a\Delta x)}{(\Delta x)^N} =\left\{\begin{array}{ll}(c_0 + 2c_1 - 1)f(x) &\text{if } N = 0, \bigg| c_1 = \frac{1 - c_0}{2}\\ 0&\text{if }N = 1,\\ \frac{1+a-a^2-c_0}{2}(\Delta x)^2 f''(x)&\text{if }N=2, \bigg|c_0 = \frac{9}{8}\end{array}\right.$$

untuk posisi interpolasi antar sampel , dengan fungsi cekung atau cembung (misalnya ). Dengan bobot tersebut diselesaikan, nilai bobot akhir pengkondisian ditemukan dengan meminimalkan nilai absolut maksimum:$0 \le a < 1$$f(x)$$f(x) = e^x$$b_0, b_1, b_2$

$$(\Delta x)^N\lim_{\Delta x\rightarrow 0}\frac{\left(b_0f(x) + b_1f(x + \Delta x) + b_2f(x + 2 \Delta x)\right)(1-a) + \left(c_1f(x) + c_0f(x + \Delta x) + c_1f(x + 2 \Delta x)\right)a - f(x + a\Delta x)}{(\Delta x)^N} =\left\{\begin{array}{ll}\left(b_0 + b_1 + b_2 - 1 + a(1 - b_0 - b_1 - b_2)\right)f(x) &\text{if } N = 0, \bigg| b_2 = 1 - b_0 - b_1\\ (a-1)(2b_0+b_1-2)\Delta x f'(x)&\text{if }N = 1,\bigg|b_1=2-2b_0\\ \left(-\frac{1}{2}a^2 + \left(\frac{23}{16} - b_0\right)a + b_0 - 1\right)(\Delta x)^2f''(x)&\text{if }N=2, \bigg|b_0 = \frac{15}{16}\end{array}\right.$$

untuk . Penggunaan prefilter tentang separuh kesalahan aproksimasi dan lebih mudah dilakukan daripada optimasi penuh tabel.$0 \le a < 1$

Gambar 4. Kesalahan perkiraan dari 11 sampel, dengan dan tanpa prefilter dan dengan dan tanpa pengkondisian akhir. Tanpa akhir pengkondisian prefilter memiliki akses ke nilai-nilai fungsi tepat di luar tabel.$\log_2(a)$

Artikel ini mungkin menyajikan algoritma yang sangat mirip: R. Gutierrez, V. Torres, dan J. Valls, " FPGA-implementasi atan (Y / X) berdasarkan transformasi logaritmik dan teknik berbasis LUT, " Journal of Systems Architecture , vol . 56, 2010. Abstrak mengatakan implementasi mereka mengalahkan algoritma berbasis CORDIC sebelumnya dalam kecepatan dan algoritma berbasis LUT dalam ukuran jejak.