Gehaxelts Blog

In diesem Blogpost soll es um die Bestimmung der Primimplikanten einer logischen Funktion nach Tison gehen.

Ich hatte dazu auf Google nichts treffendes gefunden, weswegen ich den Anfang machen möchte ;)

Theorie

Bei logischen Funktionen bzw. Schaltungen möchte man aus Kostengründen immer eine möglichst kleine Funktion haben, da die verschiedenen Logikgatter Geld kosten.

Beispiel:

$$\mbox{f(x)= } x_0x_1\overline{x_2}x_3 + \overline{x_0}x_1\overline{x_2}x_3 + x_0\overline{x_1}x_2x_3 + \overline{x_0}\overline{x_1}\overline{x_2}x_3$$

Wie man erkennt, kommt bis auf im ersten Term x_3 vor. Mit dem Absorptionsgesetz können wir die von x_3 überdeckten Terme entfernen.

$$\begin{align*} \mbox{f(x)= } &\rlap{/////////}x_0x_1\overline{x_2}x_3 + \rlap{/////////}\overline{x_0}x_1\overline{x_2}x_3 + \rlap{/////////}x_0\overline{x_1}x_2x_3 + \rlap{/////////}\overline{x_0}\overline{x_1}\overline{x_2}x_3 + x_3\\ \mbox{f(x)= } &x_3\\ \end{align*}$$

Wir konnten aus der sehr langen Funktion eine wesentlich kürzere erstellen, welche die gleiche Funktionalität hat und viel kostengünstiger ist.

Die Methode, die Tison entwickelt hat, macht diese Optimierung in wenigen Schritten. Diese funktioniert nur bei Funktionen, welche in der Disjunktiven Normalform (DNF) vorliegen. Das bedeutet, dass die Variablen in den Termen verundet und die Terme verodert sind.

Algorithmus:

• Vor beginn entfernt man alle Terme, die sich bereits überdecken.

• Man wählt eine Variable, welche in negierter und nicht negierte Form in den Termen vorkommt.

• Man bildet Paare aus den Termen mit negierte bzw. nicht negierte Variable.

• Man bildet die Überdeckungsterme der Paare und fügt diese der Ausgangsfunktion hinzu, falls der Term zu != 0 ausgewertet wird.

• Man entfernt die neu überdeckten Terme aus der Ausgangsfunktion

• Man wiederholt 2. bis 5. mit der nächsten negierten bzw. nicht negierten Variable bis keine neuen Paare mehr gebildet werden können.

Praxis

Dazu folgt noch ein Beispiel an der folgenden Funktion:

$$\mbox{f(x)= } (\overline{a} + b\overline{c}) + (a\overline{b} + cd) \cdot (ad + \overline{a}\overline{c}) + \overline{m}n$$

Diese liegt noch nicht in der Disjunktiven Normalform vor, weswegen wir das und zunächst auflösen:

$$\begin{align*} \mbox{f(x)= } &\overline{a} + b\overline{c} + a\overline{b}d + a\overline{b}\overline{a}\overline{c} + acd + \overline{a}c\overline{c}d + \overline{m}n\\ \mbox{f(x)= } &\overline{a} + b\overline{c} + a\overline{b}d + \rlap{////}a\overline{b}\overline{a}\overline{c} + acd + \rlap{////}\overline{a}c\overline{c}d + \overline{m}n\\ \mbox{f(x)= } &\overline{a} + b\overline{c} + a\overline{b}d + acd + \overline{m}n\\ \end{align*}$$

In der zweiten Zeile fallen die Terme raus, da es eine Kontradiktion gibt: a\overline{a} wird immer zu 0 ausgewertet.

Nun können wir den Algorithmus nach Tison anwenden:

1. Es gibt keine Terme mehr, die sich in der Ausgangsfunktion überdecken.

2./3. Wir nehmen uns als erstes die Variable a vor und bilden alle Paare. Tipp bei den Ergebnissen der Paare: Einfach die entsprechende Variable in negierte bzw. nicht negierte Form “abdecken” und den Rest als Verundung aufschreiben.

$$\begin{align*} \mbox{a: }& (\overline{a},a\overline{b}d)(\overline{a},acd)\\ &=\overline{b}d + cd\\ \end{align*}$$

4.5. Die beiden Ergebnisse hängen wir nun an die Ausgangsfunktion an und entfernen überdeckte Terme:

$$\begin{align*} \mbox{f(x)= } &\overline{a} + b\overline{c} + a\overline{b}d + acd + \overline{m}n + \overline{b}d + cd\\ \mbox{f(x)= } &\overline{a} + b\overline{c} + \rlap{///}a\overline{b}d + \rlap{///}acd + \overline{m}n + \overline{b}d + cd\\ \mbox{f(x)= } &\overline{a} + b\overline{c} + \overline{m}n + \overline{b}d + cd\\ \end{align*}$$

Das wiederholen wir für die Variablen b, c & d.

Variable b:

$$\begin{align*} \mbox{b: } &(b\overline{c},\overline{b}d)\\ &= \overline{c}d \end{align*}$$

Neue Funktion:

$$\begin{align*} \mbox{f(x)= } &\overline{a} + b\overline{c} + \overline{m}n + \overline{b}d + cd + \overline{c}d\\ \end{align*}$$

Variable c:

$$\begin{align*} \mbox{c: } &(cd,\overline{c}d)(cd,b\overline{c}\\ &= d + db \end{align*}$$

Neue Funktion:

$$\begin{align*} \mbox{f(x)= } &\overline{a} + b\overline{c} + \overline{m}n + \overline{b}d + cd + \overline{c}d + d + db\\ \mbox{f(x)= } &\overline{a} + b\overline{c} + \overline{m}n + \rlap{//}\overline{b}d + \rlap{//}cd + \rlap{//}\overline{c}d + d + \rlap{//}db\\ \mbox{f(x)= } &\overline{a} + b\overline{c} + \overline{m}n + d\\ \end{align*}$$

Hiermit sind wir am Ende, da weder Variable d, noch m noch n in negierte bzw. nicht negierter Form vorkommt und damit die Voraussetzung nicht erfüllt.

Am Ende nochmal die beiden Funktionen im Vergleich:

$$\begin{align*} \mbox{f(x)= } &(\overline{a} + b\overline{c}) + (a\overline{b} + cd) \cdot (ad + \overline{a}\overline{c}) + \overline{m}n\\ \mbox{f(x)= } &\overline{a} + b\overline{c} + \overline{m}n + d\\ \end{align*}$$

Die Terme der letzten Funktion sind alles Primimplikanten.

Fazit

Wenn man sich mit der Schaltungssynthese bzw. deren Optimierung beschäftigt, versucht man immer die “kleinste” Funktion zu finden. Das spart im besten Fall Gatter und somit Kosten.

Gruß

gehaxelt