TC Moduł 5: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Nie podano opisu zmian |
Nie podano opisu zmian |
||
| Linia 1: | Linia 1: | ||
{| border="0" cellpadding="4" width="100%" | {| border="0" cellpadding="4" width="100%" | ||
|valign="top" width="450px"|[[Grafika:TC_M5_Slajd1.png]] | |valign="top" width="450px"|[[Grafika:TC_M5_Slajd1.png]] | ||
|valign="top"| | |valign="top"|Redukcja argumentów | ||
|} | |} | ||
| Linia 8: | Linia 8: | ||
{| border="0" cellpadding="4" width="100%" | {| border="0" cellpadding="4" width="100%" | ||
|valign="top" width="450px"|[[Grafika:TC_M5_Slajd2.png]] | |valign="top" width="450px"|[[Grafika:TC_M5_Slajd2.png]] | ||
|valign="top"| | |valign="top"|Minimalizacja funkcji boolowskich jest podstawową procedurą syntezy logicznej w komputerowych systemach projektowania układów cyfrowych. Skuteczność i szybkość działania tej procedury może być decydująca o jakości implementacji sprzętowych wielu systemów cyfrowych o różnorodnych zastosowaniach. | ||
Niestety ze względu na heurystyczny sposób obliczeń w programie Espresso uzyskany wynik <math>F_M\,</math> może nie być pokryciem minimalnym, co przy wzrastającej złożoności układów realizowanych w nowoczesnych technologiach może okazać się istotną barierą. | |||
Niniejszy wykład omawia oryginalną metodę zmniejszania złożoności obliczeniowej algorytmów minimalizacji funkcji boolowskich. Istotą tej metody jest zastosowanie algorytmu redukcji argumentów, jako oddzielnej procedury poprzedzającej właściwą minimalizację. Redukcja argumentów jest procedurą do tej pory rzadko stosowaną w komputerowych systemach syntezy logicznej. Jedną z przyczyn takiej sytuacji jest brak świadomości, że złożone układy cyfrowe są – od strony pojedynczych wyjść - reprezentowane funkcjami boolowskimi o znacznie nadmiarowych zależnościach wejściowych. | |||
|} | |} | ||
| Linia 15: | Linia 20: | ||
{| border="0" cellpadding="4" width="100%" | {| border="0" cellpadding="4" width="100%" | ||
|valign="top" width="450px"|[[Grafika:TC_M5_Slajd3.png]] | |valign="top" width="450px"|[[Grafika:TC_M5_Slajd3.png]] | ||
|valign="top"| | |valign="top"|Celem wprowadzenia wróćmy do przykładu funkcji omawianej w poprzednim wykładzie. Jej tablica prawdy podana na planszy ma 7 argumentów. Ale na poprzednim wykładzie obliczyliśmy metodą ekspansji, że minimalne wyrażenie boolowskie tej funkcji zawiera wyłącznie 4 argumenty. Gdybyśmy to wiedzieli wcześniej, to zadanie minimalizacji moglibyśmy skutecznie uprościć. Wystarczyłoby w tym celu usunąć z tablicy prawdy tej funkcji kolumny odpowiadające nadmiarowym argumentom. Zatem problem obliczania od jakich argumentów funkcja istotnie zależy jest bardzo ważny w zmniejszaniu złożoności obliczeniowej procedur minimalizacji. | ||
|} | |} | ||
| Linia 22: | Linia 27: | ||
{| border="0" cellpadding="4" width="100%" | {| border="0" cellpadding="4" width="100%" | ||
|valign="top" width="450px"|[[Grafika:TC_M5_Slajd4.png]] | |valign="top" width="450px"|[[Grafika:TC_M5_Slajd4.png]] | ||
|valign="top"| | |valign="top"|W innym przykładzie funkcji 10 argumentowej, dla której programem Espresso zostało obliczone minimalne wyrażenie boolowskie zauważamy, że w wyrażeniu tym brak jest zmiennej <math>x_3\,</math>. Czyli według Espresso funkcja ta zależy od 9 argumentów. | ||
|} | |} | ||
Wersja z 18:53, 28 sie 2006
|
Redukcja argumentów |
|
Minimalizacja funkcji boolowskich jest podstawową procedurą syntezy logicznej w komputerowych systemach projektowania układów cyfrowych. Skuteczność i szybkość działania tej procedury może być decydująca o jakości implementacji sprzętowych wielu systemów cyfrowych o różnorodnych zastosowaniach.
Niestety ze względu na heurystyczny sposób obliczeń w programie Espresso uzyskany wynik może nie być pokryciem minimalnym, co przy wzrastającej złożoności układów realizowanych w nowoczesnych technologiach może okazać się istotną barierą. Niniejszy wykład omawia oryginalną metodę zmniejszania złożoności obliczeniowej algorytmów minimalizacji funkcji boolowskich. Istotą tej metody jest zastosowanie algorytmu redukcji argumentów, jako oddzielnej procedury poprzedzającej właściwą minimalizację. Redukcja argumentów jest procedurą do tej pory rzadko stosowaną w komputerowych systemach syntezy logicznej. Jedną z przyczyn takiej sytuacji jest brak świadomości, że złożone układy cyfrowe są – od strony pojedynczych wyjść - reprezentowane funkcjami boolowskimi o znacznie nadmiarowych zależnościach wejściowych. |
|
Celem wprowadzenia wróćmy do przykładu funkcji omawianej w poprzednim wykładzie. Jej tablica prawdy podana na planszy ma 7 argumentów. Ale na poprzednim wykładzie obliczyliśmy metodą ekspansji, że minimalne wyrażenie boolowskie tej funkcji zawiera wyłącznie 4 argumenty. Gdybyśmy to wiedzieli wcześniej, to zadanie minimalizacji moglibyśmy skutecznie uprościć. Wystarczyłoby w tym celu usunąć z tablicy prawdy tej funkcji kolumny odpowiadające nadmiarowym argumentom. Zatem problem obliczania od jakich argumentów funkcja istotnie zależy jest bardzo ważny w zmniejszaniu złożoności obliczeniowej procedur minimalizacji. |
|
W innym przykładzie funkcji 10 argumentowej, dla której programem Espresso zostało obliczone minimalne wyrażenie boolowskie zauważamy, że w wyrażeniu tym brak jest zmiennej . Czyli według Espresso funkcja ta zależy od 9 argumentów. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
