Drukuj ten rozdziałDrukuj ten rozdział

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:

\quadx1, x2, x3, ..., xk
\qquadx1, x2, x3, ..., xk
\qquad\quad x1, x2, x3, ..., xk

 

a to właśnie robią filtry FIR.

Istota rzeczy: zastępujemy mnożenie sumowaniem wyników częściowych zapisanych w pamięci. Metoda okazuje się tanią, prostą i oszczędną układowo i prosta w realizacji.

 

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:

yNie = a0xNie + a1x(n - 1) + a2x(n - 2) + b1y(n - 1) + b2y(n - 2) (**)

 

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.