044 045

(c r»i^r _t ¹,- ♦ s _t “»r, o) i - , --¹■ ₍ ¹, • >.; -

!

Rozdział

2

SYNTEZA UKŁADÓW KOMBINACYJNYCH

Układy kombinacyjne opisywane są tabelą lub zespołem funkcji logicznych wiążących każde wyjście układu z wejściami. Wyznaczenia jednego z tych opisów na podstawie zadanego słownego opisu działania układu nazywa się, jak pamiętamy, syntezą abstrakcyjną.

Przykład 2.1

Podać opis układu kombinacyjnego mnożącego dwie dwubltowe liczby binarne.

Układ posiada 4 wejścia (2x2) 14 wyjścia, gdyż największy wynik mnożenia dwu liczb dwubltowych wynosi:

(11)₂ x (11)₂ = (1001)₂ = (9)₁₀

Oznaczając wejścia przez x₁x₂ 1 y^y₂ ^oraz wyjścia przez ^z-]i^z2^,z3^,z4 otrzymujemy tabelę jak na rys. 2.1.

Jak widać, układ opisany jest przez 4 funkcje logiczne z^,z₂,zj,z^.Funkcje te zapisane w ZNPS 1 NF$ mają postać

z₁ = x₁r₂y₁y₂

*2 —    -y!2. ^x1^x2^y1^y2 ⁺ x1^x2^y1^y2 ⁼ X1^X2⁷1 ⁺ ^1^1^2

*3 ⁼ x1^x2^y1^y2 ⁺ x1^x2^y1^y2 ⁺ x1^x2^y1^y2 ⁺ x1^x2^y1^y2 ⁺ x1^x2^y1^y2 ⁺ + ⁱ₁^x2⁷1⁷2 ^{= +} x2^y1^y2 ⁺ x1^y1^y2 ⁺ x1^x2^y2 ^z4 “ ^x1^x2^y1^y2 ^{+ x}1^x2^y1^y2 ^{+ x}1^x2^y1^y2 ^{+ X}1^X2⁷1⁷2 ^{= X}2^y2

Układy kombinacyjne buduje się z elementarnych układów opisywanych prostymi funkcjami logicznymi. Te elementarne układy nazywają się funktoraml lub bramkami logicznymi. Następny etap syntezy, zwany syntezą strukturalną, polega na otrzymaniu układu o zadanym opisie poprzez odpowiednie połączenie możliwie małej Ilości funktorów² . Okazuje się (patrz p. 2.2),te schemat połączeń wynika bezpośrednio z wyrażenia definiującego funkcję lo-glozną oplauj^a projektowany układ. Pojawia się więc Istotny problem zapisywania funkcji logicznych w możliwie prostej postaci, zwany minimalizacją.

2.1. MINIMALIZACJA FUNKCJI LOGICZNYCH

Z problemem upraszczania wyrażeń logicznych spotkaliśmy się już w p. 1.3.1 (przykład 1.19). (Tutaj usystematyzujemy to zagadnienie 1 podamy dwie podstawowe algorytmiczhe metody minlmaliza-cji.

Omówimy metody upraszczania zapisów funkcji w przypadku, gdy postacią początkową jest ZNPS lub ZNPI, a postaciami końcowymi zapisy NFS 1 NPI o możliwie małej liczbie możliwie prostych Rys. 2.1. (Tablica ukła-

składników.    ^{du mnoi}5?®8⁰ liczb? ^4wu~

Dltowe

Minimalizacja funkcji logicznych polega na

wielokrotnym stosowaniu do upraszczanej funkcji tzw. reguł sklejania.

(2.1)

(2.2)

x Az + Ax = A (A + x)(A + x) = A

Wyrażenia podlegające sklejaniu noszą nazwę sąsiednich. Są one iloczynami lub sumami tych samych zmiennych różniącymi się tylko negacją jednej zmiennej. Np. sąsiednimi są wyrażenia x^x₂x^ 1 x^x₂x^ oraz z₁+x₂⁺ łz^+z^ i x₁+x₂+x^+x^; ich suma i iloczyn po zastosowaniu reguł sklejania wynoszą odpowiednio x^x₂ oraz

Stosując wielokrotnie³⁵ reguły sklejania do wyjściowych ZNPS można uzyskać postać minimalną, Jednakże proces ten należy przeprowadzać umiejętnie, aby nie doprowadzić do sytuacji, w której dalsze sklejanie nie jest Już możliwe, a nie otrzymano Jeszcze postaci minimalnej.

Przykład 2.2

Zminimalizować funkcję

y = x^x₂Xj + x^x₂Xj + x^x₂x^ + x^x₂x^ + x^x₂Xj

Nie wystarczy tu np. skleić składniki 2 i 3 oraz 5 i 7, bo otrzymamy wtedy

y = x₁x₂ + x₁Xj + x₁x₂x₃

do której to postaci nie da się już zastosować reguły sklejania, a jak za chwilę zobaczymy nie jest to postać minimalna.

1

lane metody syntezy strukturalnej, z wykorzystaniem multiplekserów 1 pamięci sta

2

łych BOM 1 PLA, omówione będą w rozdziale 4.

3

⁵ Przy .sklejaniu pamiętam; o tożsamościach x = x+xr...+x oraz x = x-x ... x, poka-zujących, że pojedynczy składnik można sklejaj z wieloma Innymi.