Beim Realisierungsaufwand unterscheiden wir
(a) materielle Kosten
(b) zeitliche Kosten.
Materielle Kosten fallen an als Entwurfskosten, und Herstellungskosten sowie als Betriebskosten durch Energieverbrauch einschließlich Kühlung. Die realen Zusammenhänge sind ziemlich komplex. Wir benutzen deshalb zwei einfache Modelle. Danach werden die materiellen Kosten bewertet durch
M1: die Anzahl der benutzten Verknüpfungsglieder
M2: die Gesamtzahl aller Verknüpfungseingänge
Dabei zählen Verknüpfungen der Art
2n 2n
und ∩
i=1 i=1
jeweils als ein Verknüpfungsglied mit n Eingängen. Invertierungen zählen nicht.
Zeitliche Kosten fallen zur Betriebszeit als Verarbeitungszeit der Verknüpfungsglieder an. Die Gesamtverarbeitungszeit einer Schaltfunktion ergibt sich als Summe der Verarbeitungszeiten der Verknüpfungen in der Verschachtelung des schaltalgebraischen Ausdrucks der Funktion.
Die Verarbeitungszeit von Verknüpfungsgliedern ist stark von der Technologie abhängig. Wir benutzen zwei einfache Modelle:
Z1: Alle Verknüpfungen sind gleichschnell
Z2: Die Verarbeitungszeit einer Verknüpfung ist proportional zur Anzahl der Eingänge
M1 und Z1 gelten ungefähr bei Bipolar-Technologien (TTL,ECL).
M2 und Z2 gelten ungefähr bei MOS-Technologien.
Im Gegensatz zu den materiellen Kosten, die immer anfallen, spielen die zeitlichen Kosten einer Schaltfunktion innerhalb eines Gesamtsystems nur dann eine Rolle, wenn die Funktion im sog. (Zeit-) kritischen Pfad liegt.
Neben den genannten Kosten können weitere - häufig gegenläufige - Gesichtspunkte bei der Realisierung von Bedeutung sein wie Testbarkeit und Energieverbrauch. Sie werden an dieser Stelle noch nicht betrachtet.
Beispiel
Die selbe Schaltfunktion in zwei verschiedenen Ausdrücken:
u∩v u∩w∩x → M1 = 3; M2 = 7; Z1 = 2; Z2 = 5
u∩(v w∩x) → M1 = 3; M2 = 6; Z1 = 3; Z2 = 6
Der Realisierungsaufwand nach diesen Modellen kann direkt aus dem schaltalgebraischen Ausdruck berechnet werden. Die Funktion aufwand(binexpr) tut dies für den Fall M2:
hilfe( 'aufwand' )
Eine Zählung der logischen Verknüpfungen entsprechend dem Modell M1/Z1 wird durchgeführt mit
aufwand({'h=~a|(b&c)'; 'x=h|a'; 'y=h&d'}, 'M1' ); % Gatterzahl und Schaltzeit
Für das Modell M2/Z2 ergibt sich bei dem selben Schaltnetz
aufwand({'h=~a|(b&c)'; 'x=h|a'; 'y=h&d'}, 'M2' ); % Inputzahl und Schaltzeit
Der tatsächliche Realisierungsaufwand ist stark von der Technologie und vom Entwurfsstil abhängig. Eine brauchbare Aufwandsabschätzung für Gate-Arrays in CMOS liefert z.B.
aufwand( {'h=~a|(b&c)'; 'x=h|a'; 'y=h&d'} ,...
[2 0 2.5 4 2; 2 0 2.5 4 2; 0 0 4 4 4]); % #Transistoren und Schaltzeit
Die folgenden Abschnitte behandeln nur eine graphische Methode zur Ermittlung einer zweistufigen disjunktiven bzw. konjunktiven Form. Von Quine und McCluskey wurde die Methode als Algorithmus zur Rechner-gestützten Minimierung weiterentwickelt. Häufig findet man bei relativ einfachen Ausdrücken aber noch bessere Lösungen durch intuitive direkte Umwandlung.
Beispiel
aufwand( '(a&~b&~c) | (a&b&~c) | (a&~b&c)' , 'M1' )
Hieraus folgt intuitiv mit dem Distributivgesetz:
= a&((~b | b)&c | ~b&c) = a&(c | ~b&c)
und weiter durch Anwendung der deMorgan-Gesetze der Ausdruck a&~(c&~(~b&c)) , also:
aufwand( 'a&~(c&~(~b&c))' , 'M1' )
Wir prüfen noch die Äquivalenz der beiden Ausdrücke:
compareexpression('(a&~b&~c)|(a&b&~c)|(a&~b&c)','a&~(c&~(~b&c))',{'a';'b';'c'})