Podręcznik

Wyjątkowo skuteczna w redukcji argumentów okazała się metoda zaproponowana w [2.6], w której klasyczne rozwiązanie problemu transformacji CNF na DNF zostało zredukowane do obliczenia uzupełnienia CNF tej funkcji, gdzie uzupełnienie redukuje się do obliczenia pokrycia kolumnowego macierzy binarnej [??]. Zaproponowane podejście bardzo przyspiesza obliczenia, a wydajna reprezentacja algorytmu w pamięci operacyjnej maszyny obliczeniowej pozwala na osiągnięcie wyników, które nie mogą być osiągnięte przy użyciu innych publikowanych metod i systemów [2.1].  Z tych powodów, jak też ze względu na niezbędność stosowania algorytmu redukcji w realizacjach sprzętowych układów dystrybucji adresów IP, skanowania wirusów, itp., wykonano praktycznie użyteczne oprogramowanie Lightning, wykorzystujące zasadę uzupełniania. Zasadę tę wyjaśnimy posługując się funkcją z Przykładu 2.17 (tabl. 2.26a).

Rys.  2.14. Przykład obliczania uzupełnienia funkcji monotonicznej

Na rys. 2.14 podano również wyniki scalania macierzy cząstkowych uzyskanych na poszczególnych etapach:

            C₇ = x₇ [0 0 1 0 0 0 0] + Æ = [0 0 1 0 0 0 1]

            C₁ = x₁ [0 0 1 0 0 0 1] + Æ = [1 0 1 0 0 0 1]

$\mathbf{C}_{2} =x_{2} \cdot \begin{bmatrix} 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{bmatrix} +\begin{bmatrix} 1 & 0 & 1 & 0 & 0 & 0 & 1 \end{bmatrix} =\begin{matrix} \begin{array}{ c c c c c c c } 1 & 2 & 3 & 4 & 5 & 6 & 7 \end{array}\\ \begin{bmatrix} 0 & 1 & 1 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 1 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0 & 1\\ 1 & 0 & 1 & 0 & 0 & 0 & 1 \end{bmatrix} \end{matrix}$

Macierz uzyskana na najwyższym piętrze rozkładu, która została utworzona ze scalenia macierzy cząstkowych dla zmiennej x₂, reprezentuje – pozycją jedynek w poszcze­gólnych wierszach – redukty funkcji z Przykładu 2.19. Obliczone uzupełnienie należy interpretować w następujący sposób: jedynka w j-tej kolumnie oznacza, że minimalny redukt uwzględnia zmienną x_j. Do uzupełnienia należy dodać zmienne niezbędne x₄ oraz x₆. Minimalne redukty funkcji F są następujące i takie same jak w rozwiązaniu metodą klasyczną.

            {<i>x</i>₂,<i>x</i>₃,<i>x</i>₄,<i>x</i>₆}

            {<i>x</i>₂,<i>x</i>₄,<i>x</i>₅,<i>x</i>₆}                      

            {<i>x</i>₂,<i>x</i>₄,<i>x</i>₆,<i>x</i>₇}

            {<i>x</i>₁,<i>x</i>₃,<i>x</i>₄,<i>x</i>₆,<i>x</i>₇}

Redukcja argumentów oraz dekompozycja, to – zgodnie z opinią prof. Sasao wyrażoną w referacie [2.14] prezentowanym na konferencji EPFL Workshop on Logic Synthesis & Verification, Dec. 2015 –  jedno z najpilniejszych zadań syntezy logicznej.

W przypadku implementacji funkcji boolowskich w układach FPGA (Field Progammable Gate Array) redukcja argumentów, umożliwia realizację funkcji w układzie kombinacyjnym o mniejszej liczbie wejść.  Jest to szczególnie istotne dla struktur FPGA z wbudowanymi pamięciami, dla których liczba zmiennych wejściowych jest głównym czynnikiem decydującym o  złożoności implementacji. Jeszcze większe znaczenie redukcji argumentów dotyczy syntezy funkcji generowania indeksów. Funkcje generowania indeksów to silnie nieokreślone funkcje boolowskie:

f : Dⁿ ® {1,2,…,<i>k</i>}, gdzie Dⁿ Í {0,1}ⁿ , oraz  |Dⁿ| = k.                       

Wektory należące do zbioru Dⁿ nazywa się wektorami rejestrowanymi. Cechą charakterystyczną tych funkcji jest duża liczba zmiennych wejściowych, przy stosunkowo małej liczności zbioru  Dⁿ .  Konsekwencją tej własności jest  skuteczne redukowanie zmiennych wejściowych, umożliwiające realizację generatora indeksów w strukturze zaproponowanej przez Sasao (rys. 2.15). W tak zbudowanym generatorze indeksów wyróżnia się dwie pamięci: pamięć główną i pamięć pomocniczą, komparator i bramę AND.

Rys.  2.15. Generator indeksów

Blok selekcji zmiennych wybiera spośród wszystkich zmiennych podzbiór X₁, reprezentujący minimalną liczbę zmiennych (tzw. redukt) realizowanej Funkcji Generowania Indeksów (FGI). Liczność reduktu jest r. Jest to jednocześnie liczba wejść do pamięci głównej.  Na wyjściach pamięci głównej pojawia się indeks wektora wejściowego X = X₁ + X₂. Jest on reprezentowany wektorem binarnym o liczbie bitów $\displaystyle p=\lceil log_{2}( k+1) \rceil$. Indeks ten jest poprawnym indeksem wektora wejściowego wtedy, jeżeli jest to wektor rejestrowany. I tylko wtedy indeks ten pojawi się na wyjściach generatora.  W przypadku, gdy wektor wejściowy nie jest wektorem rejestrowanym  na wyjściach generator pojawi się 0. Sprawdzenie, czy wyjścia pamięci głównej reprezentują poprawny indeks jest realizowane w pamięci pomocniczej i  komparatorze. W pamięci pomocniczej są zapisane wektory reprezentowane zmiennymi należącymi do zbioru X₂. Wektory te są podawane na wejście komparatora i porównywane z rzeczywistym wektorem X₂ podawanym na drugie wejście komparatora. Oczywiście wektor pobrany z pamięci pomocniczej  będzie różny od rzeczywistego wektora X₂ w przypadku, gdy nie należy on do wektora rejestrowanego. Wtedy komparator sygnałem wyjściowym o 0 zablokuje pojawienie się na wyjściach bramy AND wektora wytworzonego w pamięci głównej.

Działanie tak skonstruowanego generatora indeksów można zaprezentować na przykładzie funkcji generowania indeksów analizowanej w referacie Sasao – tab. 2.29a. Dla funkcji tej wyznaczono 5-argumentowy redukt –  tab. 2.29b.

Tablica 2.29

Nietrudno zauważyć, że o skuteczności tak skonstruowanego generatora indeksów decyduje skuteczność  obliczania  reduktów. Stosując program  Lightning można obliczyć całą serię  reduktów 4-argumentowych. Jedno z tych rozwiązań podano w tab. 2.29c.