Steuerungstasten

→ nächste Folie (auch Enter oder Spacebar).
← vorherige Folie
 d  schaltet das Zeichnen auf Folien ein/aus
 p  wechselt zwischen Druck- und Präsentationsansicht
CTRL  +  vergrößert die Folien
CTRL  -  verkleinert die Folien
CTRL  0  setzt die Größenänderung zurück

Das Weiterschalten der Folien kann ebenfalls durch das Klicken auf den rechten bzw. linken Folienrand erfolgen.

Notation

Typ Schriftart Beispiele
Variablen (Skalare) kursiv $a, b, x, y$
Funktionen aufrecht $\mathrm{f}, \mathrm{g}(x), \mathrm{max}(x)$
Vektoren fett, Elemente zeilenweise $\mathbf{a}, \mathbf{b}= \begin{pmatrix}x\\y\end{pmatrix} = (x, y)^\top,$ $\mathbf{B}=(x, y, z)^\top$
Matrizen Schreibmaschine $\mathtt{A}, \mathtt{B}= \begin{bmatrix}a & b\\c & d\end{bmatrix}$
Mengen kalligrafisch $\mathcal{A}, B=\{a, b\}, b \in \mathcal{B}$
Zahlenbereiche, Koordinatenräume doppelt gestrichen $\mathbb{N}, \mathbb{Z}, \mathbb{R}^2, \mathbb{R}^3$

Das Vereinigungstheorem

  • Das Vereinigungstheorem ist ein wichtiges Theorem zur systematischen Minimierung von Funktionen:
    $(a \land b) \lor (a \land\lnot b) = a$
  • Grundsatz zur Vereinfachung bei zweistufiger Logik (ODER-Verknüpfung von Monomen):
    Sind in der "1"-Menge zwei Monome, die die sich nur in einer Variablen unterscheiden, dann können diese zusammengefasst werden. Zur Abdeckung dieser beiden Elemente der "1"-Menge kann ein einzelnes Monom verwendet werden, in welchem diese Variable nicht mehr vorkommt.
  • Beispiel 1:
    $b$ $a$ $y$ DNF
    0 0 1  $(\overline{a} \land \overline{b})$
    01 0
    1 0 1  $\lor (\overline{a} \land b)$
    1 1 0
    Die Variable $b$ kommt nicht negiert und negiert vor, daher:
    $y = \overline{a} \overline{b} \lor \overline{a} b = \overline{a} $

Das Vereinigungstheorem

  • Beispiel 2:
    x2x1x0yDNF
    0000
    0010
    0101(¬x2∧x1∧¬x0)
    0110
    1000
    1010
    1101∨(x2∧x1∧¬x0)
    1110
    Die Variable $x_2$ kommt nicht negiert und negiert vor, daher:
    $y = \overline{x}_2 x_1 \overline{x}_0 \lor x_2 x_1 \overline{x}_0 = x_1 \overline{x}_0 $

Boolescher Würfel

  • Mit Hilfe des Booleschen Würfels kann einfach festgestellt werden, ob das Vereinigungstheorem angewendet werden kann
  • $n$-Eingangsvariablen $\equiv$ $n$-dimensionaler Würfel
bool_dice
1-Würfel
2-Würfel
3-Würfel
4-Würfel
$x_0$
0
1
$x_0$
$x_1$
00
10
01
11
$x_0$
$x_1$
$x_2$
111
000
101
$x_0$
$x_1$
$x_2$
$x_3$
0111
0000
1000
1111

Boolescher Würfel

  • Das Vereinigungstheorem fasst zwei Unterräume eines Würfels zu einem größeren zusammen
  • Beispiel:
    bool_dice_example
    $x_0$
    $x_1$
    00
    10
    01
    11
    $x_1$ $x_0$ $y$ DNF
    0 0 1  $(\overline{x_1} \land \overline{x_0})$
    01 0
    1 0 1  $\lor (x_1 \land \overline{x_0})$
    1 1 0
    Die Variable $x_1$ kommt nicht negiert und negiert vor, daher:
    $y = \overline{x_1} \,\overline{x_0} \lor x_1 \overline{x_0} = \overline{x_0} $
  • Zwei benachbarte Unterräume der Größe 0 (Knoten) werden zu einem Unterraum der Größe 1 (Kante) zusammengefasst.

Boolescher Würfel

full_adder
Volladdierer
  • Beispiel: 1-bit binärer Volladdierer
    (aus Kapitel 3.2)
    • Eingänge: Summanden $a$ und $b$, Carry-in $c_{\text{in}}$
    • Ausgänge: Summe $s$, Carry-out $c_{\text{out}}$
    bool_dice_example2
    $a$
    $b$
    $c_{\text{in}}$
    000
    001
    010
    100
    111
    $ab$
    $bc_{\text{in}}$
    $ac_{\text{in}}$
    $a$$b$$c_{\text{in}}$$s$$c_{\text{out}}$
    00000
    00110
    01010
    01101
    10010
    10101
    11001
    11111
  • Die DNF für das Carry-out aus Tabelle: $c_{\text{out}} = \overline{a}bc_{\text{in}} \lor a\overline{b}c_{\text{in}} \lor ab\overline{c}_{\text{in}} \lor abc_{\text{in}}$
  • Zweistufige Logik aus booleschem Würfel: $c_{\text{out}} = bc_{\text{in}} \lor ac_{\text{in}} \lor ab$

Boolescher Würfel

  • Das Verfahren kann rekursiv fortgeführt werden:
    • Zwei benachbarte Unterräume der Größe 0 (Knoten) werden zu einem Unterraum der Größe 1 (Kante) zusammengefasst. Dies ergibt für das Beispiel unten z. B. die beiden Kanten $ac$ und $\overline{a}c$, d.h. $y = ac \lor \overline{a}c$
    • Zwei benachbarte Unterräume der Größe 1 (Kanten) werden zu einem Unterraum der Größe 2 (Seite) zusammengefasst.
      Dies ergibt für das Beispiel: $y = c$
bool_dice_example3
a
$b$
$c$
000
001
010
100
111
$c$
  • D. h. $c$ ist wahr - bleibt unverändert. Die Variablen $a$ und $b$ variieren.

Boolescher Würfel

  • In einem Würfel mit drei Variablen gibt es folgende Unterräume:
    • 0-Würfel (Knoten), dies entspricht einem Term mit drei Literalen
    • 1-Würfel (Kante), dies entspricht einem Term mit zwei Literalen
    • 2-Würfel (Seite), dies entspricht einem Term mit einem Literal
    • 3-Würfel (Würfel), dies entspricht der Konstanten $1$
  • Im Allgemeinen gilt:
    Ein $m$-Subwürfel in einem $n$-Würfel ($m < n$) repräsentiert einen Term mit
    $n - m$ Literalen

Karnaugh-Veitch-Diagramme

  • Karnaugh-Veitch-Diagramme (KV-Diagramme) dienen zur übersichtlichen Darstellung und systematischen Vereinfachung boolescher Funktionen
    • Ziel: Umwandlung einer disjunktiven Normalform in einen minimalen disjunktiven logischen Ausdruck (minimale ODER-Verknüpfung von Monomen)
  • Sie wurden 1952 von Edward W. Veitch entworfen und 1953 von Maurice Karnaugh zu ihrer heutigen Form weiterentwickelt
  • Sie entsprechen einer flachen Abbildung des booleschen Würfels
    • Verbindungen an den Schnittkanten (rote gestrichelte Linien) müssen sich gedacht werden
    • Schwierig zu zeichnen, wenn mehr als 4 Variablen vorkommen
dice_wrap

Konstruktion von KV-Diagrammen

kv_construct
$x_0$
$x_0$
$x_3$
$x_0$
$x_3$
$x_2$
$x_0$
$x_1$
$x_2$
$x_1$
$x_0$
$x_0$
$x_1$
$x_2$
$x_1$
$x_4$

Konstruktion von KV-Diagrammen

  • Das KV-Diagramm einer boolesche Funktion $y= \mathrm{f}(x_0, x_1, \dots, x_{n-1})$ der Stelligkeit $n$ hat $2^{n}$ Zellen
  • Bereiche, in denen eine Variable $x_i$ den Wert 1 hat, sind durch einen Strich gekennzeichnet
  • Beim Hinzufügen einer neuen Variablen $x_i$ wird das bisherige KV-Diagramm durch abwechselndes vertikales und horizontales Spiegeln erzeugt
  • Dabei verdoppeln sich jeweils die Anzahl der Zellen
  • Benachbarte Zellen unterscheiden sich in genau einer Variablen
  • Zellen an der linke und rechten (bzw. oberen und untern) Kante des Diagramm sind ebenfalls benachbart (warp-around)
  • Bei 5 Variablen ist der Bereich für $x_0$ räumlich gespalten
  • Allgemein gilt: Bei $n>4$ Variablen sind die Bereiche für $n-4$ Variablen räumlich gespalten
  • D. h. wirklich intuitiv ist die Nutzung nur bis zu 4 Variablen

Übertragen von Wahrheitstafeln in das KV-Diagramm

  • Für eine Funktion $y = \mathrm{f}(x_1, x_0)$ wird folgendes Diagramm konstruiert:
x1x0yKV-Zelle
0010
0101
1012
1103
10011203
$x_0$
$x_1$
  • Für eine Funktion $y = \mathrm{f}(x_2, x_1, x_0)$ wird folgendes Diagramm konstruiert:
x2x1x0yKV-Zelle
00000
00101
01012
01103
10014
10115
11016
11117
0001151412031716
$x_0$
$x_1$
$x_2$

Übertragen von Wahrheitstafeln in das KV-Diagramm

  • Für eine Funktion $y = \mathrm{f}(x_3, x_2, x_1, x_0)$ wird folgendes Diagramm konstruiert:
x3x2x1x0yKV-Zelle
000 00 0
0 00 10 1
00 10 0 2
0 01 1 13
0 100 04
010 11 5
01 101 6
01 110 7
10 000 8
10 011 9
101 01 10
1 01 1011
1100 112
110 10 13
11 10 114
111 1015
00011504021307161100110151140819013112
$x_0$
$x_1$
$x_2$
$x_3$

Karnaugh-Veitch-Diagramme

  • Zur Konstruktion der bisherigen Diagramme wurde von einer Wahrheitstafel ausgegangen
  • Nun soll aus einem Diagramm eine minimale Oder-Verknüpfung von Monomen abgelesen werden
  • Dazu werden die verwendeten Monome so gewählt, dass möglichst viele "Einsen" gemeinsam abgelesen werden
  • Ein Monom entspricht dabei einem rechteckigen Block im KV-Diagramm
  • Somit werden möglichst große Blöcke gesucht, welche die 1-Menge im KV-Diagramm überdecken
  • Die Blöcke im KV-Diagramm entsprechen Unterräumen im Booleschen Würfel
0011150402030706
$x_0$
$x_1$
$x_2$

$y = \overline{x}_2 \overline{x}_1 x_0 \lor x_2 \overline{x}_1 x_0 = \overline{x}_1 x_0$

Überdecken von 1-Mengen in KV-Diagrammen

0001151402030706
$x_0$
$x_1$
$x_2$

$y = x_2 \overline{x}_1 x_0 \lor x_2 \overline{x}_1 \overline{x}_0 = x_2 \overline{x}_1$

0001150402031706
$x_0$
$x_1$
$x_2$

$y = x_2 x_1 x_0 \lor x_2 \overline{x}_1 x_0 = x_2 x_0$

0001051402030716
$x_0$
$x_1$
$x_2$

$y = x_2 \overline{x}_1 \overline{x}_0 \lor x_2 x_1 \overline{x}_0 = x_2 \overline{x}_0$

0001151402031716
$x_0$
$x_1$
$x_2$

$y = x_2$

Überdecken von 1-Mengen in KV-Diagrammen

  • Die Blöcke dürfen sich überlappen
  • Blöcke haben immer Zweierpotenzen als Höhe und Breite. In diesem Beispiel ist es daher nicht möglich, ein 3 x 1 Block zu verwenden. Stattdessen ergeben sich zwei 2 x 1 Blöcke.
0011151402030706
$x_0$
$x_1$
$x_2$

$y = \overline{x}_1 x_0 \lor x_2 \overline{x}_1$

  • Es gibt häufig mehrere Möglichkeiten die 1-Menge zu überdecken. Es wird immer diejenige ausgewählt, die auf möglichst wenige Oder-Verknüpfungen führt (d.h. möglichst große Blöcke und davon wenige)
0001151402131716
$x_0$
$x_1$
$x_2$

$y = x_1 x_0 \lor x_2$

Überdecken von 1-Mengen in KV-Diagrammen

  • Es ist zu erkennen, dass bei größeren Blöcken das Vereinigungstheorem wiederholt angewendet wird, indem immer größere Blöcke aus benachbarten Blöcken gebildet werden
  • In dem Beispiel rechts werden aus zwei 2 x 1 Blöcken ein 2 x 2 Block
    $\begin{eqnarray} y &=& \overline{x}_3 x_2 \overline{x}_1 x_0 \lor \overline{x}_3 x_2 x_1 x_0 \lor \overline{x}_3 x_2 \overline{x}_1 \overline{x}_0 \lor \overline{x}_3 x_2 x_1 \overline{x}_0\\ &=& \overline{x}_3 x_2 x_0 \lor \overline{x}_3 x_2 \overline{x}_0\\ &=& \overline{x}_3 x_2 \end{eqnarray} $
  • und in diesem Beispiel aus zwei 2 x 2 Blöcken ein 4 x 2 Block:
    $\begin{eqnarray} y &=& \overline{x}_3 x_2 \overline{x}_1 x_0 \lor \overline{x}_3 x_2 x_1 x_0 \lor \overline{x}_3 x_2 \overline{x}_1 \overline{x}_0 \lor \overline{x}_3 x_2 x_1 \overline{x}_0 \\ &\lor& x_3 x_2 \overline{x}_1 x_0 \lor x_3 x_2 x_1 x_0 \lor x_3 x_2 \overline{x}_1 \overline{x}_0 \lor x_3 x_2 x_1 \overline{x}_0\\ &=& \overline{x}_3 x_2 x_0 \lor \overline{x}_3 x_2 \overline{x}_0 \lor x_3 x_2 x_0 \lor x_3 x_2 \overline{x}_0\\ &=& \overline{x}_3 x_2 \lor x_3 x_2\\ &=& x_2 \end{eqnarray} $
00011514020317160100110150140809013012
$x_0$
$x_1$
$x_2$
$x_3$
00011514020317160100111151140809113112
$x_0$
$x_1$
$x_2$
$x_3$

Überdecken von 1-Mengen in KV-Diagrammen

Die Blöcke können auch über die Ränder hinweg gebildet werden.

  • Beispiel 1:

    $y = x_1 \overline{x}_0 \lor x_2 \overline{x}_1 x_0$
00011504120307161100110151140809113012
$x_0$
$x_1$
$x_2$
$x_3$
  • Beispiel 2:

    $y = \overline{x}_1 \overline{x}_0 \lor x_2 \overline{x}_1 \lor x_3 x_2 x_0$
10011514020307060100111150141809113112
$x_0$
$x_1$
$x_2$
$x_3$

Beispiel: 1-bit binärer Volladdierer

full_adder
Volladdierer
  • Eingänge: Summanden $a$ und $b$, Carry-in $c_{\text{in}}$
  • Ausgänge: Summe $s$, Carry-out $c_{\text{out}}$
$a$$b$$c_{\text{in}}$$s$$c_{\text{out}}$
00000
00110
01010
01101
10010
10101
11001
11111
  • $s = \overline{a}\overline{b}c_{\text{in}} \lor \overline{a}b\overline{c}_{\text{in}} \lor a\overline{b}\overline{c}_{\text{in}} \lor abc_{\text{in}}$
  • $c_{\text{out}} = b c_{\text{in}} \lor a c_{\text{in}} \lor a b$
0011051412031706
$c_{\text{in}}$
$b$
$a$
0001150402131716
$c_{\text{in}}$
$b$
$a$

Weitere Beispiele mit 3 Variablen

$\mathrm{f}(x_2,x_1,x_0) = \bigvee\limits_{i \in \{0,4,5,7\}} m_i$

1001151402031706
$x_0$
$x_1$
$x_2$

$\mathrm{f}(x_2,x_1,x_0) = \overline{x}_1\overline{x}_0 \lor x_2 x_0$

$\mathrm{f}(x_2,x_1,x_0) = \bigvee\limits_{i \in \{0,4,5,6,7\}} m_i$

1001151402031716
$x_0$
$x_1$
$x_2$

$\mathrm{f}(x_2,x_1,x_0) = \overline{x}_1\overline{x}_0 \lor x_2$

$\mathrm{f}(x_2,x_1,x_0) = \bigvee\limits_{i \in \{0,1,4,5,6,7\}} m_i$

1011151402031716
$x_0$
$x_1$
$x_2$

$\mathrm{f}(x_2,x_1,x_0) = \overline{x}_1 \lor x_2$

$\mathrm{f}(x_2,x_1,x_0) = \bigvee\limits_{i \in \{0,1,3,4,5,6,7\}} m_i$

1011151402131716
$x_0$
$x_1$
$x_2$

$\mathrm{f}(x_2,x_1,x_0) = \overline{x}_1 \lor x_0 \lor x_2$

Weitere Beispiele mit 4 Variablen

  • Beispiel 1:
    • Aufgabe:
      $\mathrm{f}(x_3,x_2,x_1,x_0) = \bigvee\limits_{i \in \{0,3,4,8,9,10,11,12,13,14,15\}} m_i$
    • Lösung:
      $\mathrm{f}(x_3,x_2,x_1,x_0) = x_3 \lor \overline{x}_1 \overline{x}_0 \lor \overline{x}_2 x_1 x_0$
10010514021307061101111151141819113112
$x_0$
$x_1$
$x_2$
$x_3$
  • Beispiel 2:
    • Aufgabe:
      $\mathrm{f}(x_3,x_2,x_1,x_0) = \bigvee\limits_{i \in \{3,7,9,10,11,13,14,15\}} m_i$
    • Lösung:
      $\mathrm{f}(x_3,x_2,x_1,x_0) = x_1 x_0 \lor x_3 x_0 \lor x_3 x_1$
00010504021317061101111151140819113012
$x_0$
$x_1$
$x_2$
$x_3$

Don't cares in KV-Diagrammen

  • Don't cares können als Einsen oder Nullen behandelt werden, je nachdem, was mehr Vorteile bietet.
x3x2x1x0yKV-Zelle
000 00 0
0 00 10 1
00 10 1 2
0 01 1 13
0 100 04
010 1X 5
01 101 6
01 11X 7
10 000 8
10 010 9
101 01 10
1 01 1111
1100 012
110 10 13
11 10 014
111 1015
0001X5041213X7161101110150140809013012
$x_0$
$x_1$
$x_2$
$x_3$

$y = \overline{x}_3 x_1 \lor \overline{x}_2 x_ 1$

Terminologie KV-Diagramme

  • Implikant
    • Monom (bzw. zugehöriger Block), der eine Untermenge der 1-Menge (oder don't cares) abdeckt
      z.B. 1 x 1 Block, 2 x 1 Block, 2 x 2 Block, 4 x 2 Block, usw.
  • Primimplikant
    • Primimplikanten können nicht (mehr) mit anderen benachbarten Implikanten zusammengefasst werden, um einen größeren Block zu bilden
  • Essentieller Primimplikant
    • Ein Primimplikant ist essentiell, wenn er als einziger Primimplikant ein bestimmtes Element der 1-Menge abdeckt
    • Ein essentieller Primimplikant wird somit in jedem Fall für die Abdeckungen der 1-Menge benötigt
    • Don't cares werden genutzt, um Primimplikanten zu bilden, aber nicht, um einen Primimplikanten als essentiell anzusehen

Terminologie KV-Diagramme

implicants

Vorgehensweise zum Finden des minimalen booleschen Ausdrucks aus einem KV-Diagramm

  • Schritt 1: Finde alle Primimplikanten durch Zusammenfassen horizontaler und vertikaler benachbarter 1-en zu möglichst großen Blöcken
    • auch über die Ränder hinweg
    • Höhe und Breite der Blöcke müssen Potenzen von 2 sein, also 1, 2, 4, 8 usw.
  • Schritt 2: Überdecke die 1-Menge im KV-Diagramm mit einer minimalen Auswahl von Primimplikaten
    • Wird eine 1 nur von einem bestimmten Primimplikanten überdeckt, so ist dieser essentiell und ist Teil der Überdeckungsmenge
    • Alle 1-en, die von einem essentiellen Primimplikanten überdeckt werden, brauchen nicht mehr untersucht zu werden
    • Wenn noch 1-en existieren, die nicht durch essentielle Primimplikanten abgedeckt sind, wähle die kleinste Anzahl von Primimplikanten, die die verbleibenden 1-en abdecken. Dabei werden Primimplikanten bevorzugt, die zu großen Blöcken gehören

Quiz

  • Frage: Was ist die minimale Oder-Verknüpfung von Monomen für folgende boolesche Funktion?
    00110504021317161101111150140809113012
    $x_0$
    $x_1$
    $x_2$
    $x_3$
    • Antwort 1: $x_1 x_0$
    • Antwort 2: $\overline{x}_3\overline{x}_2x_0 \lor \overline{x}_3x_2x_1 \lor x_3\overline{x}_2x_1 \lor x_3x_2x_0$
    • Antwort 3: $x_1 x_0 \lor \overline{x}_3x_2x_1 \lor x_3\overline{x}_2x_1$

Am Online-Quiz teilnehmen durch Besuch der Webseite:
www.onlineclicker.org

Quiz

  • Frage: Was ist die minimale Oder-Verknüpfung von Monomen für folgende boolesche Funktion?
    X00115X40203X706010111115014X809113112
    $w$
    $z$
    $y$
    $x$
    • Antwort 1: $zw \lor y\overline{z}$
    • Antwort 2: $yw \lor \overline{z}\overline{w}$
    • Antwort 3: $x z w \lor y \overline{z}$

Am Online-Quiz teilnehmen durch Besuch der Webseite:
www.onlineclicker.org

Interaktiver KV-Diagramm-Rechner und Lernprogramm

  • Durch Klicken auf die Felder kann die boolesche Funktion verändert werden


    Variablen:      Don’t-Cares erlauben:     Ergebnis verstecken:

Entwurfsbeispiel: 2-Bit-Komparator

$a$ $b$ $c$ $d$ $l$ $e$ $g$ KV-Zelle
0 0 0 0 0 1 0 0
0 0 0 1 1 0 0 1
0 0 1 0 1 0 0 2
0 0 1 1 1 0 0 3
0 1 0 0 0 0 1 4
0 1 0 1 0 1 0 5
0 1 1 0 1 0 0 6
0 1 1 1 1 0 0 7
1 0 0 0 0 0 1 8
1 0 0 1 0 0 1 9
1 0 1 0 0 1 0 10
1 0 1 1 1 0 0 11
1 1 0 0 0 0 1 12
1 1 0 1 0 0 1 13
1 1 1 0 0 0 1 14
1 1 1 1 0 1 0 15
  • $l = (ab < cd)$       (less)
  • $e = (ab == cd)$   (equal)
  • $g = (ab > cd)$       (greater)
00110504121317160101110150140809013012
$d$
$c$
$b$
$a$
  • Abgelesene Lösung für $l$:
    $l = \overline{a}\overline{b} d \lor \overline{a}c \lor \overline{b}c d$

Entwurfsbeispiel: 2-Bit-Komparator

$a$ $b$ $c$ $d$ $l$ $e$ $g$ KV-Zelle
0 0 0 0 0 1 0 0
0 0 0 1 1 0 0 1
0 0 1 0 1 0 0 2
0 0 1 1 1 0 0 3
0 1 0 0 0 0 1 4
0 1 0 1 0 1 0 5
0 1 1 0 1 0 0 6
0 1 1 1 1 0 0 7
1 0 0 0 0 0 1 8
1 0 0 1 0 0 1 9
1 0 1 0 0 1 0 10
1 0 1 1 1 0 0 11
1 1 0 0 0 0 1 12
1 1 0 1 0 0 1 13
1 1 1 0 0 0 1 14
1 1 1 1 0 1 0 15
  • $l = (ab < cd)$       (less)
  • $e = (ab == cd)$   (equal)
  • $g = (ab > cd)$       (greater)
10011504020307061100111150140809013012
$d$
$c$
$b$
$a$
  • Abgelesene Lösung für $e$:
    $e = \overline{a}\overline{b}\overline{c}\overline{d} \lor \overline{a}b\overline{c}d \lor a\overline{b}c\overline{d} \lor a b c d$
  • Dies ist die minimale Oder-Verknüpfung von Monomen, aber es geht noch besser:
    $e = (\overline{a}\overline{c} \land (\overline{b}\overline{d} \lor bd)) \lor (a c \land (\overline{b}\overline{d} \lor b d)) = (\overline{a}\overline{c} \lor a c)(\overline{b}\overline{d} \lor b d) = (a \leftrightarrow c)(b \leftrightarrow d) $

Entwurfsbeispiel: 2-Bit-Komparator

$a$ $b$ $c$ $d$ $l$ $e$ $g$ KV-Zelle
0 0 0 0 0 1 0 0
0 0 0 1 1 0 0 1
0 0 1 0 1 0 0 2
0 0 1 1 1 0 0 3
0 1 0 0 0 0 1 4
0 1 0 1 0 1 0 5
0 1 1 0 1 0 0 6
0 1 1 1 1 0 0 7
1 0 0 0 0 0 1 8
1 0 0 1 0 0 1 9
1 0 1 0 0 1 0 10
1 0 1 1 1 0 0 11
1 1 0 0 0 0 1 12
1 1 0 1 0 0 1 13
1 1 1 0 0 0 1 14
1 1 1 1 0 1 0 15
  • $l = (ab < cd)$       (less)
  • $e = (ab == cd)$   (equal)
  • $g = (ab > cd)$       (greater)
00010514020307060100110151141819113112
$d$
$c$
$b$
$a$
  • Abgelesene Lösung für $g$:
    $g = b \overline{c}\overline{d} \lor a \overline{c} \lor ab\overline{d}$

Gibt es Fragen?

questions

Anregungen oder Verbesserungsvorschläge können auch gerne per E-mail an mich gesendet werden: Kontakt


Weitere Vorlesungsfolien

Impressum, Datenschutz,