Resolutionsregel: \(\quad ab\lor a\overline{b}=a(b\lor \overline{b})=a\land 1=a\)

Beispiel 1:

\[ \begin{aligned} f(x_2,x_1,x_0) &= \overline{x_2}x_1x_0\lor x_2x_1x_0\\ &= (\overline{x_2}\lor x_2)x_1x_0\\ &= x_1x_0 \end{aligned} \]

Beispiel 2:

\[ \begin{aligned} f(x_3,x_2,x_1,x_0) &= x_3\overline{x_2}x_1x_0\lor x_3\overline{x_2}\,\overline{x_1}x_0\lor x_3x_2x_1x_0\lor \overline{x_3}\,\overline{x_2}\,\overline{x_1}x_0\lor \overline{x_3}\,\overline{x_2}x_1x_0\\ &= x_3\overline{x_2}x_0\lor x_3x_1x_0\lor \overline{x_2}\,\overline{x_1}x_0\lor \overline{x_3}\,\overline{x_2}x_0\lor \overline{x_2}x_1x_0\\ &= \overline{x_2}x_0\lor x_3x_1x_0 \end{aligned} \]

• Polynom = DF = Sum of products (SoP)
• Sei \(M\) ein Polynom für \(f:B^n\to B^1\)
• \(M\) heißt Minimalpolynom (für \(f\)), wenn es kein Polynom geringerer Länge für \(f\) gibt.
• Die Länge eines Polynoms ist definiert als die Anzahl der Literale, die es enthält

• Zwei Knoten mit derselben Variable und denselben Nachfolgern (1-Kante und 0-Kante) werden zu einem Knoten zusammengelegt.
• Alle eingehenden Kanten zeigen danach auf den verbleibenden Knoten.

• Die beiden markierten \(x_0\)-Knoten haben dieselben Nachfolger und werden zusammengelegt.

• Zeigen beide ausgehenden Kanten eines Knotens auf denselben Nachfolger, ist der Test überflüssig: der Knoten wird entfernt.
• Alle eingehenden Kanten zeigen danach direkt auf den Nachfolger.

• Das OBDD ist nun reduziert: keine der beiden Regeln ist mehr anwendbar.

\[ f(x_3,x_2,x_1,x_0)=x_3x_2x_1x_0\lor \overline{x_3}x_2x_1x_0\lor x_3x_2x_1\overline{x_0}\lor \overline{x_3}x_2\overline{x_1}x_0 \]

\[ f(x_3,x_2,x_1,x_0)=x_3x_2x_1x_0\lor \overline{x_3}x_2x_1x_0\lor x_3x_2x_1\overline{x_0}\lor \overline{x_3}x_2\overline{x_1}x_0 \]

• Reduziertes OBDD: 5 statt 6 innere Knoten

\(\Rightarrow\) Variablenordnung bei OBDDs relevant!

• Blöcke müssen maximale Größe haben
• Die Blockgröße muss eine Zweierpotenz sein

\[ f(x_3,x_2,x_1,x_0)=x_3\overline{x_2}x_1x_0\lor x_3\overline{x_2}\,\overline{x_1}x_0\lor x_3x_2x_1x_0\lor \overline{x_3}\,\overline{x_2}\,\overline{x_1}x_0\lor \overline{x_3}\,\overline{x_2}x_1x_0 \]

• Blau: \(\overline{x_2}x_0\) (Block über den Rand)
• Orange: \(x_3x_1x_0\)

Vereinfachte Form:

\[ f=\overline{x_2}x_0\lor x_3x_1x_0 \]

\[ \begin{aligned} f={}&\overline{x_3}\,\overline{x_2}\,\overline{x_1}\,\overline{x_0}\lor x_3\overline{x_2}\,\overline{x_1}\,\overline{x_0}\lor \overline{x_3}x_2\overline{x_1}x_0\lor x_3x_2\overline{x_1}x_0\\ &\lor \overline{x_3}x_2x_1x_0\lor x_3x_2x_1x_0\lor \overline{x_3}\,\overline{x_2}x_1\overline{x_0}\lor x_3\overline{x_2}x_1\overline{x_0} \end{aligned} \]

• Blau: \(x_2x_0\)
• Orange: \(\overline{x_2}\,\overline{x_0}\) (die vier Ecken bilden einen Block)

Vereinfachte Form:

\[ f=x_2x_0\lor \overline{x_2}\,\overline{x_0} \]

Sei \(f:B^n\to B\) eine Boolesche Funktion. Ein Term \(M\neq 0\) heißt Implikant von \(f\), kurz \(M\leq f\), falls \(M(x)\leq f(x)\) für alle \(x\in B^n\) gilt, d.h.

\[ M(x)=1\Rightarrow f(x)=1 \qquad \forall x\in B^n \]

Ein Implikant \(M\) von \(f\) heißt Primimplikant (von \(f\)), falls keine echte Verkürzung von \(M\) noch Implikant von \(f\) ist.

Ein Primimplikant \(M\) heißt Kernimplikant (von \(f\)), falls \(M\) in jedem Minimalpolynom von \(f\) vorkommt.

\[ f=x_3x_2x_1x_0\lor \overline{x_3}x_2x_1x_0\lor x_3x_2x_1\overline{x_0}\lor \overline{x_3}x_2\overline{x_1}x_0 \]

\[ f=x_3x_2x_1x_0\lor \overline{x_3}x_2x_1x_0\lor x_3x_2x_1\overline{x_0}\lor \overline{x_3}x_2\overline{x_1}x_0 \]

• Primimplikanten: \(\overline{x_3}x_2x_0,\ x_2x_1x_0,\ x_3x_2x_1\)
• Kernimplikanten: \(\overline{x_3}x_2x_0,\ x_3x_2x_1\) \(\Rightarrow\) Minimalpolynom \(f=x_3x_2x_1\lor \overline{x_3}x_2x_0\)

0. Wertetabelle
1. Einsen ins KV-Diagramm
2. Alle Primimplikanten: maximale Blöcke
3. Minimale Überdeckung \(\Rightarrow\) Minimalpolynom

• Nullen weglassen

• Blöcke maximal, Größe \(2^k\), auch über den Rand

• Einsen mit nur einem Block \(\Rightarrow\) Kernimplikant

• Restliche Einsen mit möglichst wenigen Blöcken

\[ f=\overline{x_2}\,\overline{x_0}\lor x_2x_1x_0\lor \overline{x_3}\,\overline{x_1}x_0 \]

• Don’t Cares werden als 1 behandelt, wo sie größere Blöcke ermöglichen
• Blau: \(x_3\), Orange: \(\overline{x_1}x_0\)

Ergebnis: \(\quad f(x_3,x_2,x_1,x_0)=x_3\lor \overline{x_1}x_0\)

1. Minterme der einschlägigen Indizes nach Anzahl der Negationen gruppieren
2. Resolutionsregel \(ab\lor a\overline{b}=a\) auf Terme benachbarter Gruppen anwenden, solange möglich
3. Terme, die sich nicht weiter verkürzen lassen, sind die Primimplikanten
4. Implikationsmatrix aufstellen: Welcher Primimplikant deckt welchen Minterm ab?
5. Kernimplikanten wählen, restliche Minterme mit möglichst kurzen Primimplikanten abdecken

\[ \begin{aligned} f={}&\overline{x_3}\,\overline{x_2}\,\overline{x_1}\,\overline{x_0}\lor \overline{x_3}x_2\overline{x_1}\,\overline{x_0}\lor \overline{x_3}x_2x_1\overline{x_0}\lor x_3\overline{x_2}x_1x_0\\ &\lor x_3x_2\overline{x_1}\,\overline{x_0}\lor x_3x_2\overline{x_1}x_0\lor x_3x_2x_1\overline{x_0} \end{aligned} \]

Minterme gemäß Anzahl der Negationen:

Implikationsmatrix:

Kostengünstigste Darstellung:

\[ f=x_3\overline{x_2}x_1x_0\lor x_3x_2\overline{x_1}\lor x_2\overline{x_0}\lor \overline{x_3}\,\overline{x_1}\,\overline{x_0} \]

Anderes Beispiel:

\[ \begin{aligned} f={}&x_3\overline{x_2}x_1x_0\lor x_3\overline{x_2}x_1\overline{x_0}\lor x_3\overline{x_2}\,\overline{x_1}\,\overline{x_0}\lor \overline{x_3}x_2x_1x_0\lor \overline{x_3}x_2x_1\overline{x_0}\\ &\lor \overline{x_3}x_2\overline{x_1}x_0\lor \overline{x_3}x_2\overline{x_1}\,\overline{x_0}\lor \overline{x_3}\,\overline{x_2}x_1x_0\lor \overline{x_3}\,\overline{x_2}\,\overline{x_1}\,\overline{x_0} \end{aligned} \]

Minterme gemäß Anzahl der Negationen:

Implikationsmatrix:

Kernimplikant: \(\overline{x_3}x_2\) (einziger Primimplikant für die Minterme 5 und 6)

Kostengünstigste Darstellung: Hier nicht eindeutig!

Mögliche Minimalpolynome (jeweils mit Kernimplikant \(\overline{x_3}x_2\)):

\[ \begin{aligned} f_1 &= \overline{x_3}x_2\lor \overline{x_2}x_1x_0\lor x_3\overline{x_2}x_1\lor \overline{x_2}\,\overline{x_1}\,\overline{x_0}\\ f_2 &= \overline{x_3}x_2\lor \overline{x_2}x_1x_0\lor x_3\overline{x_2}\,\overline{x_0}\lor \overline{x_2}\,\overline{x_1}\,\overline{x_0}\\ f_3 &= \overline{x_3}x_2\lor \overline{x_3}x_1x_0\lor x_3\overline{x_2}x_1\lor \overline{x_2}\,\overline{x_1}\,\overline{x_0}\\ f_4 &= \overline{x_3}x_2\lor \overline{x_2}x_1x_0\lor x_3\overline{x_2}\,\overline{x_0}\lor \overline{x_3}\,\overline{x_1}\,\overline{x_0} \end{aligned} \]

• Alle vier Polynome haben die Länge 11.

Kernimplikant \(\overline{x_3}x_2\) gewählt \(\Rightarrow\) Minterme 4, 5, 6, 7 sind abgedeckt.

Wähle beliebigen Implikanten mit neuer Information!

\[ f_1=\overline{x_3}x_2\lor \overline{x_2}x_1x_0 \]

Minterme 3 und 11 sind nun ebenfalls abgedeckt.

Wähle beliebigen Implikanten mit neuer Information!

\[ f_1=\overline{x_3}x_2\lor \overline{x_2}x_1x_0\lor \overline{x_2}\,\overline{x_1}\,\overline{x_0} \]

Nur noch Minterm 10 ist offen.

Wähle beliebigen Implikanten mit neuer Information!

\[ f_1=\overline{x_3}x_2\lor \overline{x_2}x_1x_0\lor \overline{x_2}\,\overline{x_1}\,\overline{x_0}\lor x_3\overline{x_2}x_1 \]

\[ \begin{aligned} f_1 &= \overline{x_3}x_2\lor \overline{x_2}x_1x_0\lor x_3\overline{x_2}x_1\lor \overline{x_2}\,\overline{x_1}\,\overline{x_0}\\ f_2 &= \overline{x_3}x_2\lor \overline{x_2}x_1x_0\lor x_3\overline{x_2}\,\overline{x_0}\lor \overline{x_2}\,\overline{x_1}\,\overline{x_0} \end{aligned} \]

\[ \begin{aligned} f_3 &= \overline{x_3}x_2\lor \overline{x_3}x_1x_0\lor x_3\overline{x_2}x_1\lor \overline{x_2}\,\overline{x_1}\,\overline{x_0}\\ f_4 &= \overline{x_3}x_2\lor \overline{x_2}x_1x_0\lor x_3\overline{x_2}\,\overline{x_0}\lor \overline{x_3}\,\overline{x_1}\,\overline{x_0} \end{aligned} \]

• Warum minimieren?
  • Reduzierung von Eingangsvariablen und Schaltkreiselementen
  • Suche nach der optimalen Realisierung
• In diesem Kapitel vorgestellt: