TC Moduł 6

Dekompozycja funkcji boolowskich. Począwszy od drugiej połowy lat 80-tych intensywne prace badawcze prowadzone są nad metodami i algorytmami syntezy logicznej dla układów FPGA o architekturze TLU (Table Look-Up). Intensywność tych prac jest wynikiem z jednej strony dużej popularności struktur FPGA, a z drugiej, ich odmiennej budowy, którą w pierwszym przybliżeniu można scharakteryzować jako strukturę komórkową, w odróżnieniu od struktury bramkowej charakterystycznej dla układów Gate Array i Standard Cell. Dla układów FPGA potrzebne były całkiem nowe rozwiązania, które wypracowano wg klasycznego modelu tzw. dekompozycji funkcjonalnej, wprowadzonej jeszcze w latach 60. przez Ashenhursta i Curtisa.

---

Jednak droga od prostego i ograniczonego modelu Curtisa do metod, które mogłyby być odpowiednie do wysokich wymagań współczesnych technologii układów FPGA, jest bardzo długa i jak można sądzić z najnowszych publikacji badania nad dekompozycją funkcjonalną są ciągle w kręgu zainteresowań zarówno ośrodków uniwersyteckich, jak i firm opracowujących komputerowe systemy projektowania układów cyfrowych. Można stąd wnosić, że zagadnienia dekompozycji funkcjonalnej – do tej pory rzadko prezentowane w wydawnictwach książkowych – osiągnęły poziom i potrzebę ich rozpowszechnienia. Jest to istotne tym bardziej, że istniejące uniwersyteckie narzędzia komputerowe syntezy logicznej bezpośrednio wykorzystujące algorytmy dekompozycji dają bardzo dobre rezultaty w porównaniu do systemów komercyjnych.

---

Niech będzie dana funkcja boolowska $f:\{0,1{\}}^n\to \{0,1\}$ oraz pewien podział zmiennych na dwa rozłączne zbiory $B$ (bound set) i $A$ (free set). Tablicą dekompozycji funkcji $f$ (decomposition chart) nazywamy macierz dwuwymiarową o kolumnach etykietowanych wartościami zmiennych funkcji $f$ ze zbioru $B$ oraz o wierszach etykietowanych wartościami zmiennych funkcji $f$ ze zbioru $A$. Elementami macierzy $M$ są wartości, jakie przyjmuje funkcja $f$ na wektorach złożonych z odpowiednich etykiet i-tego wiersza i j-tej kolumny. Liczbę istotnie różnych kolumn tej macierzy ze względu na ich zawartość oznaczamy symbolem $\nu (A|B)$ (column multiplicity).

---

Twierdzenie [Curtis] Niech będzie dana funkcja boolowska $f$ oraz podział zbioru zmiennych wejściowych funkcji $f$ na dwa rozłączne zbiory $A$ i $B$, wówczas: $f(A,B)=h(g_1(B),..,g_j(B),A)⟺\nu (A|B)\le 2^j$ Schemat takiej dekompozycji jest przedstawiony na rysunku.

---

---

---

---

---

---