Minmierung von Schaltnetzen

Beispielaufgabe zur Minimierung

Gegeben sei folgende Zustandstabelle:
a b c d y
1 0 0 0 0 0
2 0 0 0 1 1
3 0 0 1 0 0
4 0 0 1 1 1
5 0 1 0 0 0
6 0 1 0 1 1
7 0 1 1 0 0
8 0 1 1 1 1
9 1 0 0 0 0
10 1 0 0 1 1
11 1 0 1 0 0
12 1 0 1 1 0
13 1 1 0 0 0
14 1 1 0 1 0
15 1 1 1 0 0
16 1 1 1 1 0

Ausgangsignal: y
Eingangssignale: a,b,c,d  


Zusammengehörige Begriffe und Umsetzungsvarianten
Disjunktive Normalform Minterm
Mintermmenge		 Kombinationen mit y=1 Einsmenge Prinzip:
y=(.Λ.Λ...)v(.Λ.Λ...)v(.Λ.Λ...)v...
oder
y=(.·.·...)+(.·.·...)+(.·.·...)+....		 Minterm als NAND und Mintermmenge als NOR umsetzen
Konjunktive Normalform Maxterm
Maxtermmenge		 Kombinationen mit y=0 Nullmenge Prinzip:
y=(.v.v...)Λ(.v.v...)Λ(.v.v...)Λ...
oder
y=(.+.+...)·(.+.+...)·(.+.+...)·....		 Maxterm als NOR und Maxtermmenge als NAND umsetzen


Mathematische Vorgehensweise

Die korrekte Schreibweise mit y=(.Λ.Λ...)v(.Λ.Λ...)v(.Λ.Λ...)v... ist meist aufwendiger und unübersichtlicher, so dass hier die einfachere Schreibweise als y=(.·.·...)+(.·.·...)+(.·.·...)+.... im folgenden verwendet wird. Am Schluss muss nur beachtet werden, dass bei einer Nachrechnung mit eingesetzten Werten gilt:

y  =  a̅b̅c̅d + a̅b̅cd + a̅bc̅d + a̅bcd + ab̅c̅d 
    = d ( a̅b̅c̅ + a̅bc + a̅bc̅ + a̅bc + ab̅c̅)
    = d ( a̅b̅(c̅+c) + a̅b(c̅+c) + ab̅c̅)          mit (c̅+c)=1
    = d ( a̅b̅ + a̅b + ab̅c̅)
    = d ( a̅(b̅+b) + ab̅c̅)
    = d ( a̅ + ab̅c̅)
    = a̅d + dab̅c̅d

Scheinbar geht es hier nicht mehr weiter zu vereinfachen. Aber wenn ein passender Term von der ersten Zeile hinzu genommen wird, kann noch mehr vereinfaacht werden. Auf solche Tricks kommt in der Regel kaum Jemand von selbst und muss daher geübt bzw. auswendig gelernt werden.

y = a̅d + ab̅c̅d + a̅b̅c̅d
   = a̅d + (a+ a̅)b̅c̅d 
   = a̅d + b̅c̅d 

Wenn gesehen wird, dass in  a̅  auch  a̅b̅c̅ enthalten ist, dann könnte auch das zur weiteren Vereinfachung herangezogen werden um das gleiche Ergebnis zu erhalten.
y  = d ( a̅ + ab̅c̅)
    = d ( a̅ + ab̅c̅ +  a̅b̅c̅ )
    = d ( a̅ + (a+a̅) b̅c̅ )
    = d ( a̅ + b̅c̅ )
    = a̅d + b̅c̅d 
 
Bei der mathematischen Vorgehensweise hätte auch anders im ersten Schritt vereinfacht werden können:
y  =  a̅b̅c̅d + a̅b̅cd + a̅bc̅d + a̅bcd + ab̅c̅d 
    = d ( a̅b̅c̅ + a̅bc + a̅bc̅ + a̅bc + ab̅c̅)
    = d (  a̅b(c̅+c) + a̅b̅c + (a̅+a)b̅c̅)
    = d (  a̅b + a̅b̅c + b̅c̅)
    =  a̅bd + a̅b̅cd + b̅c̅d
Allerdings ist die weiter Berechnung hier deutlich schwieriger.    
 - Erweiterung mit: a̅b̅c̅d d.h. c̅+c ausklammern und eliminieren.
 - Dann in  a̅bd + a̅b̅d das b+b̅  ausklammern und eliminieren.
  Ergibt das gleiche Ergebnis.

Vereinfachung mittels KV-Diagramm

Aufstellen des KV-Diagramms:

a a  a̅  a̅
b 0 0 1 1 d
b 0 0 0 0 d̅
b̅ 0 0 0 0 d̅̅
b̅ 1 0 1 1 d
c̅ c c c̅

Zusammenfassen im KV-Diagramm

a a  a̅  a̅
b 0 0 1 1 d
b 0 0 0 0 d̅
b̅ 0 0 0 0 d̅̅
b̅ 1 0 1 1 d
c̅ c c c̅
Die grünen Felder zusammengefaßt ergeben:  a̅d


a a  a̅  a̅
b 0 0 1 1 d
b 0 0 0 0 d̅
b̅ 0 0 0 0 d̅̅
b̅ 1 0 1 1 d
c̅ c c c̅
Die blauen Felder zusammengefaßt ergeben:  b̅c̅d 

Insgesamt ergibt sich also ebenfalls: y =  a̅d + b̅c̅d