metody obliczania stałego punktu atan2 na FPGA

Potrzebuję przetwarzania atan2(x,y)na FPGA z ciągłym strumieniem danych wejściowych / wyjściowych. Udało mi się to zaimplementować za pomocą rozwijanego, potokowego jądra CORDIC, ale aby uzyskać wymaganą dokładność, musiałem wykonać 32 iteracje. Doprowadziło to do poświęcenia dość dużej liczby LUT temu jednemu zadaniu. Próbowałem zmienić przepływ, aby używać częściowo rozwiniętych jąder CORDIC, ale potem potrzebowałem zwielokrotnionej częstotliwości taktowania, aby wykonywać powtarzane pętle, zachowując ciągły przepływ wejścia / wyjścia. Dzięki temu nie mogłem dotrzymać terminu.

Teraz sięgam po alternatywne sposoby obliczeń atan2(x,y).

Pomyślałem o użyciu tabel przeglądowych bloków RAM z interpolacją, ale ponieważ istnieją 2 zmienne, potrzebowałbym 2 wymiarów tabel przeglądowych, a to jest bardzo zasobochłonne pod względem wykorzystania blokowych pamięci RAM.

Potem pomyślałem o użyciu faktu atan2(x,y)związanego atan(x/y)z dostosowaniem kwadrantu. Problem polega na tym, że x/ywymaga prawdziwego podziału, ponieważ ynie jest stały, a podziały na układy FPGA są bardzo wymagające pod względem zasobów.

Czy są jakieś nowatorskie sposoby implementacji atan2(x,y)na FPGA, które skutkowałyby mniejszym wykorzystaniem LUT, ale nadal zapewniałyby dobrą dokładność?

Możesz użyć logarytmów, aby pozbyć się podziału. Dla $(x, y)$ w pierwszej ćwiartce:

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

Rycina 1. Wykres $\text{atan}(2^z)$

Aby uzyskać wymaganą dokładność 1E-9, musisz zbliżyć $\text{atan}(2^z)$ w zakresie $-30 < z < 30$ . Możesz skorzystać z symetrii $\text{atan}(2^{-z}) = \frac{\pi}{2}-\text{atan}(2^z)$lub alternatywnie upewnij się, że$(x, y)$jest w znanej liczbie oktanowej. Aby przybliżyć$\log_2(a)$:

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

$b$ można obliczyć, znajdując lokalizację najbardziej znaczącego niezerowego bitu. $c$ można obliczyć przez przesunięcie bitowe. Konieczne byłoby przybliżenie$\log_2(c)$ w zakresie$1 \le c < 2$ .

Ryc. 2. Wykres $\log_2(c)$

Dla twoich wymagań dokładności wystarczy interpolacja liniowa i jednorodne próbkowanie, $2^{14} + 1 = 16385$ próbek $\log_2(c)$ i $30\times 2^{12} + 1 = 122881$ próbek $\text{atan}(2^z)$ dla $0 < z < 30$ . Ten drugi stół jest dość duży. Dzięki niemu błąd spowodowany interpolacją zależy w dużej mierze od $z$ :

Ryc. 3. największy błąd bezwzględny aproksymacji $\text{atan}(2^z)$ dla różnych zakresów $z$ (oś pozioma) dla różnych liczb próbek (od 32 do 8192) na przedział jednostkowy $z$ . Największy błąd bezwzględny dla $0 \le z < 1$ (pominięty) jest nieco mniejszy niż dla $\text{floor}(\log_2(z)) = 0$ .

$\text{atan}(2^z)$ tabela może być podzielony na wiele subtables które odpowiadają $0 \le z < 1$ i innym $\text{floor}(\log_2(z))$ z $z \ge 1$ , który jest łatwy do obliczenia. Długości tabeli można wybrać zgodnie z rys. 3. Indeks wewnątrz podtabeli można obliczyć za pomocą prostej manipulacji ciągiem bitów. Dla potrzeb dokładności $\text{atan}(2^z)$ będą zawierały łącznie 29217 próbek, jeśli rozszerzysz zakres $z$ do $0 \le z < 32$ dla uproszczenia.

Do późniejszego wykorzystania oto niezgrabny skrypt Pythona, którego użyłem do obliczenia błędów aproksymacji:

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])    

Lokalna maksymalna błędu z zbliżony funkcję $f(x)$ przez interpolację liniową f ( x ) z próbek f ( x ) , wykonane z jednolitego próbek z próbek przedział Δ x może być w przybliżeniu analitycznie:$\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},$$

$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)}.$$

Ponieważ funkcje są wklęsłe, a próbki pasują do funkcji, błąd jest zawsze w jednym kierunku. Lokalny maksymalny błąd bezwzględny można by zmniejszyć o połowę, gdyby znak błędu pojawiał się naprzemiennie tam iz powrotem raz na każdy interwał próbkowania. Dzięki interpolacji liniowej można uzyskać prawie optymalne wyniki, wstępnie filtrując każdą tabelę poprzez:

$$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}}$$

$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$

$$(\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.$$

$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.$$

$0 \le a < 1$

$\log_2(a)$

W tym artykule prawdopodobnie przedstawiono bardzo podobny algorytm: R. Gutierrez, V. Torres i J. Valls, „ Implementacja FPGA atan (Y / X) w oparciu o transformację logarytmiczną i techniki oparte na LUT ”, Journal of Systems Architecture , tom . 56, 2010. Streszczenie mówi, że ich implementacja przewyższa poprzednie algorytmy oparte na CORDIC pod względem prędkości, a algorytmy oparte na LUT pod względem wielkości powierzchni.