2 Entwurf von Verknüpfungsnetzen

2.4 Schaltungsvereinfachungen

Werden Boolesche Funktionen in Form einer kanonischen Normalform (kDNF oder kKNF) realisiert, so ist meistens eine große Anzahl Gatter mit einer Vielzahl von Gattereingängen notwendig.

Eine Vereinfachung der Schaltungsimplementierung ist daher erforderlich. Wie eine Reduzierung des Schaltungsaufwandes vorgenommen werden kann, zeigen folgende Überlegungen:

• Benachbarte Felder eines KV-Diagramms unterscheiden sich in nur einem Argumentenwert, z.B x_i = 0 und x_i = 1. Ist für diese beiden Felder der Funktionswert (Feldinhalt) gleich, so ist das Argument x_i irrelevant (d.h. der Wert dieser beiden Felder hängt nicht von x_i ab). In der Funktionsbeschreibung können diese beiden Einzelfelder durch einen Feldverbund ersetzt werden, der beide Felder umfaßt. Dieser Feldverbund wird ohne das Argument xi beschrieben; der Parameter x_i wird eliminiert.
  

• Feldverbunde dieser Art können jetzt ihrerseits zu größeren Verbunden zusammengefaßt werden (2 -> 4, 4 -> 8, usw.). Mit jeder Verdoppelung des Feldverbundes wird ein weiteres Argument eliminiert. Durch Zusammenfassen von 2ⁿ Feldern zu einem Verbund werden also n Argumente eliminiert. Dies bedeutet natürlich auch, daß jeweils nur eine Anzahl von Feldern verbunden werden kann, die einer ganzzahligen Potenz der Zahl 2 entspricht (2ⁿ = 2,4,8,...).

Von der Seite der Booleschen Algebra betrachtet, bedeutet die Bildung von Feldverbunden nichts weiter als die wiederholte Anwendung der Beziehung

. (2.7)

Eine Boolesche Funktion, deren Beschreibung derartige Feldverbunde enthält, stellt natürlich keine kanonische Normalform mehr dar, sondern eine konjunktive (KNF) bzw. disjunktive Normalform (DNF).

Beispiel:

Das folgende Beispiel zeigt anschaulich am KV-Diagramm die Bildung derartiger Feldverbunde:

Abb. 2.21: Bildung von Feldverbunden.

In diesem Beispiel sind die folgenden 1-Feldverbunde möglich:

• Viererfeld m₀, m₁, m₄, m₅
• Zweierfeld m₁, m₃
• Zweierfeld m₄, m₆

Unter Berücksichtigung dieser Feldverbunde ergibt sich für die Funktionsrealisierung:

(zweistufig)

(2.8)

bzw. unter Einführung der Funktion XOR:

(dreistufig).

(2.9)

In diesem Beispiel sind offenbar keine 0-Feldverbunde möglich, so daß nur eine Realisierung in Form der kKNF möglich ist:

.

(2.10)