Układy logiczne

103000 - Wydział Elektroniki i Technik Informacyjnych

ULOG

2

Rewolucyjny rozwój technologii mikroelektronicznych spowodował, że projektowanie systemów cyfrowych może być realizowane wyłącznie za pomocą komputerowych narzędzi projektowania. Celem wykładu jest omówienie zaawansowanych metod syntezy logicznej niezbędnych do zrozumienia nowoczesnych narzędzi projektowania systemów cyfrowych. Dlatego głównymi zagadnieniami omawianymi na wykładzie są m.in. heurystyczne metody minimalizacji funkcji boolowskich, redukcja argumentów, synteza wielopoziomowa, dekompozycja funkcjonalna, kodowanie stanów oraz dekompozycja automatów. Ponadto wykład wskazuje na istotne związki układów logicznych z niektórymi zagadnieniami informatyki takimi jak maszynowe uczenie lub eksploracja wiedzy.

Rewolucyjny rozwój technologii mikroelektronicznych spowodował, że projektowanie systemów cyfrowych może być realizowane wyłącznie za pomocą komputerowych narzędzi projektowania. Celem wykładu jest omówienie zaawansowanych metod syntezy logicznej niezbędnych do zrozumienia nowoczesnych narzędzi projektowania systemów cyfrowych. Dlatego głównymi zagadnieniami omawianymi na wykładzie są m.in. heurystyczne metody minimalizacji funkcji boolowskich, redukcja argumentów, synteza wielopoziomowa, dekompozycja funkcjonalna, kodowanie stanów oraz dekompozycja automatów. Ponadto wykład wskazuje na istotne związki układów logicznych z niektórymi zagadnieniami informatyki takimi jak maszynowe uczenie lub eksploracja wiedzy.

Treść wykładu
Informacje ogólne i pojęcia podstawowe. Technologie współczesnej mikroelektroniki. Aspekty elektroniczne i technologiczne układów logicznych. Układy specjalizowane ASIC. Układy PLD/FPGA. Rola i znaczenie syntezy logicznej. Algebra Boole`a. Przekształcanie wyrażeń boolowskich. Podstawowe funktory logiczne (AND, OR, NAND, NOR, EXOR). Układy kombinacyjne. Synteza dwupoziomowa. Minimalizacja funkcji boolowskich (mapa Karnaugha, pojęcie implikantu). Realizacje bramkowe i w strukturach FPGA. (4g).

Heurystyczne metody komputerowe minimalizacji funkcji boolowskich. Metoda Espresso. Pojęcie kostki. Procedura ekspansji. Macierz blokująca. Pokrycie kolumnowe. Procedura Irredundant cover. Kofaktor. Tautologia. Pojęcie kostki względnie zasadniczej, bezwzględnie i względnie nadmiarowej. (4g).

Redukcja argumentów. Redukty funkcji boolowskich. Pojęcie zmiennej niezbędnej. Macierz porównań i funkcja wyróżniająca. (2g).

Synteza wielopoziomowa. Dekompozycja funkcji booloowskich. Metoda klasyczna. Tablica dekompozycji. Relacja zgodności. Maksymalne klasy zgodne. Graf zgodności i niezgodności. Związki z kolorowaniem grafu. Synteza logiczna dla struktur FPGA. (2g).

Dekompozycja metodą rachunku podziałów. Ogólne twierdzenie o dekompozycji. Obliczanie podziałów reprezentujących składowe dekompozycji. Metoda systematyczna. Relacja zgodności na zbiorze bloków podziału. Klasy zgodności. Pojęcie r-przydatności. Dekompozycja nierozłączna. Obliczanie zbioru wspólnego. Wyznaczanie zbioru wolnego i związanego. Zastosowania w syntezie układów z pamięciami. (4g).

Układy sekwencyjne. Pojęcie automatu skończonego. Synteza abstrakcyjna, strukturalna i kombinacyjna. Minimalizacja liczby stanów. Algorytmy minimalizacji: algorytmy maksymalnych klas zgodności i ich związek z kolorowaniem grafów. Synchroniczne układy sekwencyjne. Automaty elementarne (przerzutniki). Obliczanie funkcji wzbudzeń. (4g).

Kodowanie stanów wewnętrznych. Pojęcie podziału zamkniętego. Dekompozycja automatu: szeregowa i równoległa. (2g).

Układy asynchroniczne. Metody syntezy. Zjawiska fizyczne: wyścigi i hazardy. Bezpieczne kodowanie stanów. Zabezpieczanie automatu przed wyścigami krytycznymi. (2g).

Układy sekwencyjne z pamięciami. Kodowanie wstępne. Kodowanie wtórne. Synteza układu modyfikacji adresu. Obliczanie adresowania i zawartości pamięci mikroprogramu. (2g).

Układy cyfrowe. Cyfrowe bloki funkcjonalne. Podstawowe układy kombinacyjne: kodery, dekodery, multipleksery, demultipleksery, sumatory. Bloki sekwencyjne: rejestry, liczniki. Pamięci ROM. Bloki wykonawcze i sterujące. Przykład syntezy strukturalnej. (1g).

Synteza logiczna układów cyfrowych. Odwzorowanie technologiczne. Problemy implementacji komputerowej. Wady systemów komercyjnych. Struktury bramkowe. Struktury komórkowe. Synteza logiczna, strukturalna i behawioralna. (1g)

Algorytmy syntezy logicznej w inżynierii wiedzy. Redukcja atrybutów. Redukty tablic danych. Generacja reguł decyzyjnych metodą ekspansji. (2g).


Uwaga: plansze do wykładów dostępne w Internecie
http://www.zpt.tele.pw.edu.pl/pomoce.htm


Treść ćwiczeń
Algebra Boole`a. Upraszczanie wyrażeń boolowskich. Minimalizacja fukcji boolowskich: metoda Karnaugha, metoda ekspansji, obliczanie kostek względnie zasadniczych, względnie i bezwzględnie nadmiarowych. Obliczanie reduktów funkcji boolowskich.
Dekompozycja funkcji boolowskich. Przykład metody klasycznej wg tablic dekompozycji. Obliczanie podziału ?G. Dekompozycja nierozłączna.
Synteza układów sekwencyjnych. Minimalizacja liczby stanów. Obliczanie funkcji wzbudzeń - poglądowo. Kodowanie - obliczanie podziałów zamkniętych i wyznaczanie zależności funkcyjnych. Synteza układów modyfikacji adresu. Redukcja atrybutów. Uogólnianie reguł decyzyjnych.

1. T. Łuba, Synteza układów logicznych. Oficyna Wydawnicza Politechniki Warszawskiej, 2005.


2. J. Astola, R. Stanković. Fundamentals of Switching Theory and Logic Design. Dordrecht: Springer, 2006.


3. U. Stańczyk, K. Cyran, B. Pochopień. Theory of logic circuits - volume 1 Fundamental issues. Publishers of the Silesian University of Technology, Gliwice 2007.


4. S. Yanushkevich, V. Shmerko. Introduction to Logic Design. CRC Press, 2008.


5. C. Zieliński, Podstawy projektowania układów cyfrowych. PWN, Warszawa 2003.


6. T. Sasao. Switching Theory for Logic Synthesis. Kluwer Academic Publishers, 1999.


7. S. Hassoun, T. Sasao, R. Brayton (ed.), Logic Synthesis and Verification, Kluwer Academic Publishers, 2002.


8. G. De Micheli, Synthesis and Optimization of Digital Circuits. McGraw-Hill, New York, 1994. Również tłumaczenie polskie, Synteza i optymalizacja układów cyfrowych. Wydawnictwa Naukowo-Techniczne, Warszawa 1998.

103500 - Instytut Mikroelektroniki i Optoelektroniki

103500 - Instytut Mikroelektroniki i Optoelektroniki

103600 - Instytut Telekomunikacji

103600 - Instytut Telekomunikacji

103600 - Instytut Telekomunikacji

103600 - Instytut Telekomunikacji

103600 - Instytut Telekomunikacji

103600 - Instytut Telekomunikacji

103600 - Instytut Telekomunikacji

103600 - Instytut Telekomunikacji

103600 - Instytut Telekomunikacji

103600 - Instytut Telekomunikacji

103600 - Instytut Telekomunikacji

103600 - Instytut Telekomunikacji

103600 - Instytut Telekomunikacji

103600 - Instytut Telekomunikacji