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.

---

Sens fizyczny twierdzenia wyjaśnia przykład. Dla funkcji z tablicy na planszy kolumny są adresowane trzema zmiennymi $\{x1,x2,x3\}$ względem których funkcja $f$ jest symetryczna. Wiersze natomiast są adresowane zmiennymi $\{x4,x5\}$. Grupy kolumn o adresach $\{(0,0,1),(0,1,0),(1,0,0)\}$ i $\{(1,1,0),(1,0,1),(0,1,1)\}$ są odpowiednio równe. Zatem istnieje dekompozycja, w której zmienne $\{x_1,x_2,x_3\}$ są przeadresowywane na $\{g_1,g_2\}$. Wówczas funkcja $f$ może być wyspecyfikowana w tablicy, w której adresami kolumn są $\{g_1,g_2\}$, a wierszy odpowiednio wartości zmiennych $\{x_4,x_5\}$. Tablice te są jednocześnie tablicami prawdy funkcji reprezentujących składowe dekompozycji tzn. bloki g i h.

---

Znaczenie praktyczne dekompozycji wynika z konstrukcji typowych struktur programowalnych jakimi są układy FPGA. Nie wnikając w szczegóły (o układach FPGA powiemy więcej na wykładzie 12) budowę struktur FPGA można scharakteryzować następująco. Są to układy wyposażone w kilkadziesiąt (kilkaset) uniwersalnych komórek logicznych. Typowa komórka ma 4 wejścia i 1 wyjście, na którym realizowana jest dowolna funkcja boolowska 4 argumentów. Komórki umieszczone są w środowisku kanałów połączeniowych dzięki którym można je łączyć w dowolne struktury. Z powyższego wynika, że funkcja $f$ zdekomponowana na bloki g i h połączone jak pokazano na rysunku może być zrealizowana na trzech komórkach struktury FPGA. Później pokażemy, że proces realizacji funkcji boolowskich w strukturach FPGA uwzględniający metodę dekompozycji jest o wiele bardziej skuteczny niż metody przyjęte w systemach komercyjnych, w których w takim przypadku najpierw dokonuje sie minimalizacji funkcji, a dopiero potem sieć bramek jest odwzorowywana na komórki.

---

Niestety postępowanie takie w ogólnym przypadku funkcji nie w pełni określonych nie może być już tak bezpośrednie. Przykład takiej bardziej skomplikowanej sytuacji omówimy dokonując dekompozycji funkcji podanej w tabl. na planszy. Otóż w tym przypadku, ze względu na nieokreśloności funkcji, nie można bezpośrednio podjąć decyzji, które kolumny w tablicy dekompozycji są takie same. Wynika to z faktu, że kreskom reprezentującym punkty nieokreśloności funkcji można przypisać wartość albo 0 albo 1, w rezultacie zaliczając odpowiednią kolumnę do – być może innego zbioru kolumn identycznych. Jak się póżniej przekonamy funkcja ta ma dekompozycję $f=h(a,b,g_1(c,d,e),g_2(c,d,e))$ o schemacie blokowym jak na rysunku.

---

Niniejsza plansza przedstawia funkcje boolowskie odpowiadające składowym tej dekompozycji.

---

W celu obliczania dekompozycji funkcji boolowskich nie w pełni określonych wprowadzimy pojęcie zgodności kolumn (tablicy dekompozycji). Kolumny $\{k_r,k_s\}$ są zgodne, jeśli nie istnieje wiersz i, dla którego elementy $K_{ir}$, $K_{is}$ są określone i różne, tzn. odpowiednio: 0, 1 albo 1, 0.

---

Kolumny zgodne można „sklejać”. pokolorowane kolumny na planszy wyjaśniają proces sklejania.

---

Relacja zgodności jest zwrotna, symetryczna, ale nie jest przechodnia. Pary zgodne umożliwiają wyznaczenie maksymalnych zbiorów kolumn zgodnych. Zbiór $K=k_1,...,k_p$ nazywamy maksymalnym zbiorem kolumn zgodnych (maksymalną klasą zgodności), jeżeli każda para $k_i$, $k_j$ wzięta z tego zbioru jest zgodna oraz nie istnieje żaden inny zbiór kolumn zgodnych $K^{\prime }$, zawierający $K$.

---

Problem obliczania maksymalnych klas zgodnych można sprowadzić do znanego problemu obliczania maksymalnych klik w grafie lub do problemu kolorowania grafu. Najprostsza metoda polega na łączeniu par kolumn zgodnych w trójki, trójek w czwórki itd. Usuwając zbiory mniejsze zawarte w większych oblicza się Maksymalne Klasy Zgodności.

---

Taką najprostszą metodę obliczania MKZ nazywać będziemy metodą bezpośrednią. Wg niej trzy pary zgodne $(a,b)$, $(b,c)$, $(a,c)$ tworzą zbiór zgodny $(a,b,c)$. Z kolei cztery „trójki”: $(a,b,c)$, $(a,b,d)$, $(b,c,d)$, $(a,c,d)$ tworzą „czwórkę tzn. 4 elementowy zbiór zgodny $(a,b,c,d)$.

---

Zatem przystępując do obliczania dekompozycji należy najpierw obliczyć pary kolumn zgodnych. Dla funkcji, której tablica dekompozycji jest podana na planszy kolumny K0, K1 oraz K0, K2 są sprzeczne. Natomiast K0, K3 oraz K0, K4 są zgodne. W ten sposób wyznaczamy wszystkie pary kolumn zgodnych.

---

Dysponując parami kolumn zgodnych kolejno obliczamy „trójki”, a następnie „czwórki” zgodne: 0,3,4,6; 1,3,4,6; 1,4,5; 2,5,7. W zapisie formalnym: $\{K_0,K_3,K_4,K_6\}$, $\{K_1,K_3,K_4,K_6\}$, $\{K_1,K_4,K_5\}$, $\{K_2,K_5,K_7\}$.

---

Po wyznaczeniu maksymalnych zbiorów kolumn zgodnych (maksymalnych klas zgodności) należy wybrać minimalną liczbę klas (lub podklas) pokrywającą zbiór wszystkich kolumn. Z kolei w takiej rodzinie zbiorów należy usunąć kolumny powtarzające się. Ostatecznie uzyskujemy: $\{K_0,K_3,K_4,K_6\}$, $\{K_1,K_5\}$, $\{K_2,K_7\}$. Kolumny należące do jednej klasy zgodności można sklejać.

---

---

---

---