Podręcznik
7. Przetwarzanie równoległe, potokowe i sieci systoliczne
7.2. Arytmetyka rozłożona
Co to jest arytmetyka rozłożona i do czego służy? Jest to równoległo-szeregowa metoda - czy raczej koncepcja - układowej realizacji układów obliczających wartość kombinacji liniowej.
| \( y = \displaystyle\sum_{i=1}^k{a_i}{x_i} \) | (*) |
gdzie a1, a2, ..., ak są stałymi (reprezentowanymi przez słowa binarne), a x1, x2, ..., xk danymi wejściowymi (reprezentowanymi również przez słowa binarne).
Na wyrażenie (*) można patrzeć jak na iloczyn skalarny dwóch wektorów z przestrzeni Rn: (a1, a2, ..., ak) i (x1, x2, ..., xk).
Metoda dobrze nadaje się do realizacji filtrów cyfrowych NOI, SOI, do obliczania DFT i do realizacji cyfrowych filtrów adaptacyjnych (wymiana zawartości pamięci daje nowy filtr cyfrowy).
Rozwiązania układowe arytmetyki rozłożonej dobrze nadają się do realizacji iloczynu skalarnego (a1, a2, ..., ak) z takim „przesuwającym” się wektorem:
\(\quad\)x1, x2, x3, ..., xk
\(\qquad\)x1, x2, x3, ..., xk
\(\qquad\quad\) x1, x2, x3, ..., xk
a to właśnie robią filtry FIR.
Wyjaśnimy koncepcję arytmetyki rozłożonej na przykładzie. Niech liczby a1, a2, ..., ak ∈ Q, x1, x2, ..., xk ∈ Q będą reprezentowane w zapisie U2. Załóżmy, że dla każdego chcemy obliczyć zdefiniowane tak:
| y |
(**) |
Takim właśnie równaniem różnicowym opisywana jest tzw. sekcja bikwadratowa filtru NOI (nieskończona odpowiedź impulsowa).
Przyjmijmy, że wartości bezwzględne wszystkich sygnałów nie przekraczają jedności i są przedstawione za pomocą B+1 bitów w zapisie U2, tzn.:
| \( x(k) = -x^0_k + \displaystyle\sum_{j=1}^Bx^j_k2^{-j} = \overset{B+1 bitów}{ \overbrace{(x^0_k, x^1_k, x^2_k, ..., x^B_k)}}\) |
słowo binarne reprezentuje x(k) ( „rozpisujemy sygnały na bity”)
| \( y(k) = -y^0_k + \displaystyle\sum_{j=1}^By^j_k2^{-j} = {(y^0_k, y^1_k, y^2_k, ..., y^B_k)}\) |
gdzie \(x_k^j, y_k^j\) ∈ {0,1}. Nasze wyrażenie (**) na y(n) możemy teraz zapisać następująco:
| \( y(n) = -\overset{\text {bity znaków}}{\overbrace{x_n^0a_0 + x_{n-1}^0a_1 + a_2x_{n-2}^0 + b_1y^0_{n-1} + b_2y^0_{n-2}}} +\) | (***) |
| \(+ \displaystyle\sum_{j=1}^{B}2^{-j}(a_0x_n^j + a_1x^j_{n-1} + a_2x^j_{n-2} + b_1y_{n-1}^j + b_2y^j_{n-2})\) |
Niczego nadzwyczajnego nie zrobiliśmy, poza zmianą kolejności sumowania.
Zauważmy, że w wyrażeniach w nawiasach a0, a1, a2, b1, b2 są stałe, zatem każdy „nawias” jest wartością pewnej funkcji pięciu zmiennych.
| \(f (e_1, e_2, e_3, e_4, e_5) = a_0e_1 + a_1e_2 +a_2e_3 + b_1e_4 + b_2e_5\) |
gdzie e1, e2, ..., e5 ∈ {0,1}. Nasza funkcja \(f\) może przyjmować tylko 32 wartości. Funkcję tę można zrealizować jako układ kombinacyjny lub zapamiętać w pamięci PROM.
Zatem przepisując (***) z użyciem nowego oznaczenia dostajemy:
| \(y(n) = -f(x^0_n, x^0_{n-1}, x^0_{n-2}, y^0_{n-1}, y^0_{n-2}) + \displaystyle\sum_{j=1}^{B}2^{-j} f (x^j_{n}, x^j_{n-1}, x^j_{n-2}, y^j_{n-1}, y^j_{n-2})\) |
Widać, że wyeliminowaliśmy w ten sposób mnożenie, a y(n) obliczać możemy przez sumowanie i przesuwanie odpowiedniej wartości funkcji \(f\).