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}\rightarrow \{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)\ \iff \ \nu (A|B)\leq 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},\ldots ,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'$, 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ć.

---

W celu wyjaśnienia „sklejania” kolumny należące do różnych klas zgodności wyróżniono kolorami, a wszystkie kolumny należące do jednej klasy sklejono w jedną kolumnę uzyskując tablicę z mniejszą liczbą kolumn. dodatkowo w uzyskanej „mniejszej” tablicy wprowadzono kolumnę wypełnioną kreskami, dla podkreślenia podobieństwa do tablicy Karnaugha. Oczywiście tak uzyskana tablica reprezentuje funkcję h.

---

Z kolei w celu obliczenia składowych typu g, posłużymy się pokolorowanymi tablicami pokazanymi na planszy.

---

W rezultacie uzyskaliśmy realizację pierwotnej funkcji 5 argumentów w dwóch blokach, g oraz h, w taki sposób, że wyjścia bloku g są jednocześnie dodatkowymi wejściami do h. Najistotniejsze jest jednak to, że bloki te mają mniejszą liczbę zmiennych wejściowych. Warto podkreślić, że uzyskane wyniki wystarczą już do realizacji tej funkcji w strukturze FPGA. Albowiem (typowe) komórki takiej struktury realizują dowolna funkcję boolowska 4 zmiennych. Co nie przeszkadza, że w zależności od potrzeb technologii można składowe dekompozycji poddawać dalszym zabiegom syntezy, na przykład minimalizacji...

---

Uzyskując w rezultacie wielopoziomową strukturę bramek.

---

Przystępujemy do obliczania funkcji g. W tym celu przepisujemy te funkcje z tablicy uzyskanej w procesie dekompozycji do odpowiednich tablic Karnaugha. I (pomijając już szczegóły) uzyskujemy następujące wyrażenia boolowskie: $g_{1}={\bar {c}}d{\bar {e}}+cde$ $g_{2}={\bar {c}}d{\bar {e}}+ce+{\bar {d}}e$

---

W celu obliczenia funkcji h, w poprzednio uzyskanej tablicy zmieniamy kolejność wierszy, a dla tak powstałej tablicy Karnaugha obliczamy minimalne wyrażenie funkcji h: $h={\bar {a}}{\bar {g}}_{2}+bg_{2}+ag_{1}$

---

W metodzie dekompozycji jednym z najważniejszych algorytmów jest algorytm obliczania maksymalnych klas zgodności. Powstaje pytanie: czy nie można stosowanej do tej pory metody bezpośredniej zastąpić czymś skuteczniejszym?

---

W celu sprawniejszego obliczania MKZ wprowadzimy dwie nowe metody: metodę wg par zgodnych metodę wg par sprzecznych

---

Niech E będzie relacją na zbiorze $V=\{v_{1},...,v_{n}\}$, tzn. zbiorem par zgodnych (sąsiednich) $v_{i},v_{j}:i,j\in {1,...,n}$ oraz $i\neq j$. Obliczenie (maksymalnych) klas zgodności w zbiorze $V$ przy danej E sprowadza się do wykonania następujących czynności. Zapisujemy elementy $v$ w rodzinach $S_{j}$ zgodnie z zasadą $v_{i}\in S_{j}$ tylko wtedy, gdy $v_{j}$, $v_{i}$ jest parą zgodną oraz $i<j$. Jeżeli $RKZ_{k}$ jest rodziną klas zgodności uzyskaną w k-tym kroku algorytmu, to rodzinę $RKZ_{k+1}$ uzyskujemy, obliczając przecięcie każdej $KZ\in RKZ_{k}$ ze zbiorem $S_{k+1}$. Wyróżniamy przy tym następujące przypadki: $S_{k+1}=\varnothing$ i wtedy $RKZ_{k+1}$ jest powiększona o klasę $KZ=\{k+1\}$; $KZ\cap S_{k+1}=\varnothing$ wtedy klasa $KZ$ nie ulega zmianie; $KZ\cap S_{k+1}\neq \varnothing$ wtedy powstaje nowa klasa Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle KZ’ = KZ \cap S_{k+1} \cup \{k+1\}} .

---

Algorytm ten zastosujemy do obliczenia MKZ przy założeniu, że parami zgodnymi są: (1,2), (1,3), (1,5), (2,3), (2,4), (2,5), (3,5), (3,6), (4,6). Najpierw obliczamy zbiory R.

---

Zapisując zbiory R w tabelce jak na planszy kolejno obliczamy klasy zgodności. Przykładowo: W pierwszym kroku wpisujemy zbiór {1}. Iloczyn {1} i $R_{2}=\{1\}$ powiększony o element 2 tworzy zbiór zgodny {1, 2} w kroku drugim. Analogicznie powstaje zbiór zgodny {1, 2, 3} w kroku trzecim. W kroku czwartym iloczyn {1, 2, 3} i $R_{4}$, powiększamy o element 4, stąd klasa {2, 4} do której należy dopisać już obliczony zbiór zgodny {1, 2, 3}. Wynik w postaci maksymalnych klas zgodności powstaje w kroku 6.

---

Algorytm obliczania MKZ wg par sprzecznych. Zapisać pary sprzeczne w postaci koniunkcji dwuskładnikowych sum. Koniunkcję dwuskładnikowych sum przekształcić do minimalnego wyrażenia boolowskiego typu suma iloczynów. Wtedy MKZ są uzupełnieniami zbiorów reprezentowanych przez składniki iloczynowe tego wyrażenia.

---

Wracając do poprzedniego przykładu wypisujemy pary sprzeczne: (1,4), (1,6), (2,6), (3,4), (4,5), (5,6). Dalej będziemy je zapisywali bardziej formalnie: (k1, k4), (k1, k6), (k2, k6), (k3, k4), (k4, k5), (k5, k6).

---

W celu obliczenia MKZ metodą par sprzecznych najpierw zapisujemy wyrażenie boolowskie typu „koniunkcja sum”. Następnie zmieniamy kolejność czynników (par). W otrzymanym wyrażeniu stosujemy zasady algebry Boole’a. Pozwalają one szybko wyznaczyć ostateczne wyrażenie typu „suma iloczynów”.

---

Odejmując od zbioru wszystkich elementów zbiory reprezentowane przez poszczególne składniki tego wyrażenia uzyskujemy maksymalne klasy zgodności, oczywiście takie same jak poprzednio.

---

Dysponując dwiema metodami obliczania MKZ-ów warto się zastanowić, który z nich stosować w konkretnym zadaniu. Duża liczba par zgodnych (w porównaniu do liczby par sprzecznych) sugeruje, że łatwiejsze powinny być obliczenia wg par sprzecznych. Z taką sytuacją mamy do czynienia dla par zgodnych podanych na planszy.

---

Jeszcze inny sposób obliczania zbioru kolumn, które można skleić polega na zastosowaniu algorytmu kolorowania tzw. grafu niezgodności Wierzchołkami grafu niezgodności są kolumny $k_{1},k_{2},...,$ a jego krawędzie łączą sprzeczne (niezgodne) pary kolumn.

---

Metodę omówimy na przykładzie par zgodnych i sprzecznych podanych na planszy.

---

Na podstawie par sprzecznych tworzymy graf niezgodności. Zgodnie z zadaniem kolorowania grafu należy teraz znaleźć minimalną liczbę kolorów, które pozwoliłyby pokolorować wierzchołki tego grafu tak, aby żadne dwa wierzchołki o tym samym kolorze nie były połączone krawędzią. I taką sytuację podano na planszy. Wierzchołki o tym samym kolorze reprezentują zbiry kolumn, które można skleić.

---

Chcąc porównać skuteczność obliczania klas zgodności za pomocą grafu niezgodności, zapiszemy teraz pary zgodne z planszy 32 na grafie zgodności. Jak widać trudno bezpośrednio z tego grafu odczytać MKZ.

---

Natomiast dla odpowiedniego grafu niezgodności pokazanego na planszy łatwo jest wyznaczyć pokolorowanie wierzchołków dwoma kolorami tak aby żadne dwa wierzchołki o tym samym kolorze nie były połączone krawędzią.

---

Więcej na temat dekompozycji funkcji boolowskich można znaleźć w książce „Synteza układów logicznych”.