Kombinatorische Logik

ZIELE

  • Verständnis vom Aufbau und Funktionsweise von kombinatorischen Logiksystemen als Grundelemente des Datenpfades von RT Systemen

  • Verständnis vom Entwurf von arithmetischen Funktionsblöcken mit Basiszellen oder Basisblöcken

  • Aufbau und Funktionsweise von Datenpfadselektoren (für RTL)

  • Verwendung von Datenpfadselektoren als Programmierbare Digitallogik!

Kombinatorische Logik

  • Kombinatorische Logik besteht nur aus den Logikfunktionen und Gattern:

    • Disjunktion (Oder)
    • Konjunktion (Und)
    • Negation (Inverter)

  • Das Verhalten von Kombinatorischer Logik lässt sich vollständig mit Boolescher Algebra beschreiben → Zeit- und zustandsloses Modell

Technische kombinatorische Logik hat aber ein Zeitmodell durch Signallaufzeiten und Verzögerungen!

  • Werte aus der Vergangenheit bestimmen den aktuellen Wert der Ausgangsvariable(n) nicht. Im folgenden werden fundamentale Beispiele für Schaltnetze gezeigt.

  • D.h., ein Schaltnetz oder kombinatorische Logik ist eine logische Schaltung, deren Ausgangsvariable(n) nur von den am Eingang anliegenden Werten, den Eingangsvariablen, abhängt.

Signallaufzeit

Die Zeit, die ein Signal vom Eingang eines Logikgatters oder einer damit aufgebauten Logikschaltung bis zum Ausgang benötigt, nennt man Laufzeit.

  • Die Laufzeit bei elektronischen Schaltungen resultiert aus der verwendeten Transistortechnologie, und ist bei CMOS-Technologie in der Zeit begründet, um eine (parasitäre) Kapazität bei einem Logikpegelwechsel umzuladen. Insbesondere die Gate-Source Kapazität hat Einfluss auf die Schaltzeit des Transistors.

  • Jede steuerende Transistorstufe, jede Zuleitung besitzt einen ohmschen (und induktiven) Widerstand, der zusammen mit der technologischen Kapazität C ein RC-Glied bildet.

  • Eine Ausgangsstufe eines Logikgatters muss die effektive par. Kapazität umladen. Je mehr Logikgattereingänge auf einen Ausgang geschaltet sind, desto größer die belastende Kapazität, und umso größer die Verzögerungszeit (FANIN/FANOUT).

Signallaufzeit

figsigdelay2

Abb. 1. (Links) Parasitäre Kapazitäten und Signallaufzeit (Rechts) Ursache der Signalverzögerung durch Signalverhalten eines äquivalenten RC-Gliedes (rechts).

Signallaufzeit

Längster Kombinatorischer Pfad (LKP)

  • Es findet eine Akkumulation der einzelnen Signallaufzeiten entlang eines Signalpfades statt:

  • Die gesamte Laufzeit in einem Pfad ist dann:

\[\begin{gathered} T_{P}=\sum_{i=1}^{N(P)} \Delta T_{i} \\ P=e_1,e_2,.. \end{gathered} \]
  • Während dieser Zeit ist die kombinatorische Logikschaltung metastabil, d.h. die einzelnen Ausgänge können sich zeitlich mehrfach ändern (Hazards).

Komponenten und Schaltungen

  • Die Kombinatorische Logik bildet den RT Datenpfad

  • Wichtige Komponenten sind u.A.:

    1. Addierer
    2. Multiplizierer
    3. (Dividierer)
    4. Logische Bitoperatoren (trivial)
    5. Relationale Operationen
    6. Multiplexer, Demultipelxer

Addierer

Halbaddierer

Ein Halbaddierer besitzt zwei Eingangsvariablen a und b, und zwei Ausgangsvariablen, die Summe und der Übertrag Carry, mit folgender Funktionstabelle:

figadd1

Boolesche Gleichung des Halbaddierers

\[\begin{gathered} sum = \neg a \bullet b + a \bullet \neg b = a \oplus b \\ c_{out} = a \bullet b \end{gathered} \]

Addierer

Logikschaltung des Halbaddierers

figadd2

Volladdierer

Erweiterung eines Halbaddierers durch einen Volladdierer, der eine zusätzliche Eingangsvariable, den Übertrag einer weiteren Addiereinheit, enthält.

Addierer

Logikschaltung des Volladdierers

figadd3

Boolesche Gleichung des Volladdierers

Man erhält folgende boolesche Funktion für die Ausgangsvariablen Summe und Übertrag:

\[\begin{gathered} sum = \neg a \bullet \neg b \bullet c_{in} + \neg a \bullet b \bullet \neg c_{in} + a \bullet \neg b \bullet \neg c_{in} + a \bullet b \bullet c_{in} \\ = a \oplus b \oplus c \\ c_{out} = \neg a \bullet b \bullet c_{in} + a \bullet \neg b \bullet c_{in} + a \bullet b \bullet \neg c_{in} + a \bullet b \bullet c_{in} \end{gathered} \]

Addierer

N-Bit Addierer

Ein Addierer zur Addition zweier N-Bit breiten Bitvektoren lässt sich mit verschiedenen Architekturen aufbauen, die unterschiedliche Eigenschaften besitzen. Alle Architekturen involvieren Volladdierer.

Ripple-Carry Addierer

  • Bei dieser Architektur werden N Volladdierer kaskadiert, wie in folgender Abbildung gezeigt ist.

  • Dabei findet eine Übertragsignal-Propagierung vom niederwertigsten zum höchstwertigen Bit statt, d.h. die Berechnung des N-ten Bits erfordert die Ergebnisse der vorherigen N-1 Addierer.

Addierer

figadd4

Abb. 2. Logikschaltung eines Ripple-Carray Addierers

Addierer

Aufgabe

  1. Implementiere einen 3-Bit Ripple-Carray Addierer in Retro mit elementaren Gattern (Und, Oder, XOR, Not)

  2. Teste die Schaltung mit einigen exemplarischen Eingangswerten. Wo befindet sich der längste kombinatorische Pfad und wie groß ist die Verzögerungszeit?

  3. Gibt es Hazards?

Addierer

Der Ripple-Carry-Addierer ist aufgrund der Signallaufzeit langsam, da die gesamte Laufzeit für das höchstwertige Bit den LKP bestimmt.

Carry-Lookahead Addierer

  • Der Carry-Lookahead Addierer besitzt verbesserte Laufzeiteigenschaften, da auf Kaskadierung verzichtet wird, indem die Carry-Signale direkt aus den Eingangsvariablen berechnet werden.

Boolesche Gleichung des Carry-Lookahead Addierers

\[\begin{gathered} s_i = a_i \oplus b_i \oplus c_i \\ c_{i+1} = a_i \bullet b_i + a_i \bullet c_i + b_i \bullet c_i \\ = a_i \bullet b_i + (a_i + b_i) \bullet c_i \\ c_{i+1} = g_i + p_i \bullet c i \end{gathered} \]

Addierer

  • Dabei ist g der so genannte generierende Term, und p der sog. Durchlaufterm.
  • Für einen N-Bit-Addierer kann man dann ableiten:
\[\begin{gathered} c_1 = g_0 + p_0 \bullet c_{in} \\ c_2 = g_1 + p_1 \bullet c_1 \\ = g_1 + g_0 \bullet p_1 + p_0 \bullet p_1 \bullet c_{in} \\ c_3 = g_2 + p_2 \bullet c_2 \\ = g_2 + g_1 \bullet p_2 + g_0 \bullet p_1 \bullet p_2 + p_0 \bullet p_1 \bullet p_2 \bullet c_{in} \\ \dots \\ c_{i+1} = \sum_{j=0}^{i}(g_j\prod_{k=j+1}^{i}P_k)+\prod_{k=0}^{i}P_k \bullet c_{in} \end{gathered} \]

Addierer

  • Jedes Carry-Signal als Eingang für einen Volladdierer hängt nur noch von den primären Eingangssignalen ab.

  • Nachteil: bei großem N werden große Anzahl von Und-Gattern benötigt. Daher wird meistens ein hierarchischer Aufbau mit Teilkomponenten für den Lookahead Addierer verwendet, mit den Bestandteilen:

    1. Mini-Addierer (Ripple-Carry):
      f : (a, b, c) → P, G, S
    2. Carry-Lookahead Generator:
      f : (P, G) → C

Addierer

figadd5

Abb. 3. Hybrider Aufbau aus kleinen Ripple-Carry Addierern und Carry-Lookahead Generatoren

Multiplizierer

  • Ein 1-Bit Multiplizierer besitzt folgende Funktionstabelle:

figmul1

  • Ein Multiplizierer für die Multiplikation von N-Bit × M-Bit breiten Zahlen A und B muss zunächst mathematisch behandelt und hergeleitet werden
    • Ausgangspunkt ist die gewichtetete Binärsummendarstellung von dezimalen Zahlen

Multiplizierer

\[\begin{gathered} A = \sum\limits_{i = 0}^{N - 1} {{a_i}{2^i}} ,B = \sum\limits_{i = 0}^{M - 1} {{b_i}{2^i}} \hfill \\ A \times B = \sum\limits_{i = 0}^{N - 1} {{a_i}{2^i}} \times \sum\limits_{j = 0}^{M - 1} {{b_j}{2^j}} = \sum\limits_i^{} {\sum\limits_j^{} {{a_i}{b_j}{2^{i + j}}} } \hfill \\ \end{gathered} \]
  • Dieses Produkt hat m × n Terme. Umformung zu einer Summe mit Laufindex k=i+j führt zu:
\[\begin{gathered} A \times B = \sum\limits_{k = 0}^{M + N - 1} {{P_k}{2^k}} \hfill \\ {P_0} = {a_0} \bullet {b_0},{P_1} = {a_1} \bullet {b_0} \otimes {a_0} \bullet {b_1} \hfill \\ {P_2} = {a_2} \bullet {b_0} \otimes {a_1} \bullet {b_1} \otimes {a_0} \bullet {b_2},{\text{ usw.}} \hfill \\ \end{gathered} \]

Multiplizierer

Basiszelle eines Multiplizierers

  • Einführung einer Basiszelle aus 1-Bit-Mulitplizierern und Volladdierern ermöglicht Aufbau des Multiplizierers mit einer systolischen Matrixstruktur.

figmul2

  • Ein Parallelmultiplizierer setzt sich daher aus Addition und 1-Bit-Multiplizierern zusammen. Ein 4 × 4 Multiplizierer benötigt dann:
    • 16 Und-Gatter
    • 8 Volladdierer (40 Gatter)
    • 4 Halbaddierer (16 Gatter)

Multiplizierer

Matrix-Struktur eines Multiplizierers

  • 2 x 2 Matrix unter Verwendung der Basiszelle

figmul3

Logische und Relationale Operationen

  • N-stellige Bitoperation (Konjunktion, Disjunktion, Negation) lassen sich durch 1-Bit Operationen direkt umsetzen:
\[Y = f(X)= (x_0 \bullet y_0, x_1 \bullet y_1, .., x_n \bullet y_n ) \]
  • Relationale Operationen:
    • Gleichheit, Kleiner, Größer, usw.

figcomp1

Multiplexer und Demultiplexer

  • Multiplexer sind elektronisch gesteuerte Auswahlschalter.
  • Ein Multiplexer legt eines von N Eingangssignalen auf eine Ausgangsleitung. Die Auswahl erfolgt durch eine anliegende Adresse → Datenselektor
  • Umgekehrten Vorgang mit Demultiplexer, der ein Eingangssignal auf N Ausgänge verteilt. Die Auswahl des Ausgangs erfolgt wieder durch Adressierung.
  • Verwendung von Multiplexer und Demultiplexer:

figmux1

Multiplexer und Demultiplexer

Boolesche Funktion eines 1-Bit Multiplexer

  • Ein 1-Bit-Multiplexer besteht aus einer Und-Verknüpfung mit einem Eingangssignal e und einem Selektorsignal a:
\[f(e,s) = e \bullet s \]

figmux2

Boolesche Funktion eines N-Bit Multiplexers

  • Ein N-Bit Multiplexer ist aus einer Oder-Verknüpfung einzelner 1-Bit Multipelxer aufgebaut:
\[f(e_0,e_1,..,e_i,s_0,s_1,..,s_i) = e_0 \bullet s_0 + e_1 \bullet s_1 + .. + e_i \bullet s_i \]

Multiplexer und Demultiplexer

Adressdekoder

  • Die einzelnen Selektorsignale ai müssen noch aus den eigentlichen Adresssignalen A dekodiert werden. Dazu wird ein Demultiplxer mit I=1 verwendet. Beispiel für N=2:

figmux5

Vollständiger BF des Multiplexers

\[\begin{gathered} f(E, A) = e_0 \bullet \neg a_0 \bullet \neg a_1 + e_1 \bullet a_0 \bullet \neg a_1 + \\ e_2 \bullet \neg a_0 \bullet a_1 + e_3 \bullet a_0 \bullet a_1 \end{gathered} \]

Multiplexer und Demultiplexer

  • Die Struktur besteht aus einer Und-Matrix mit N Eingangssignalen mit einer nachfolgenden Oder-Verknüpfung bzw. Oder-Matrix bei M Ausgangssignalen.

figmux3

Diese Und-Oder-Struktur ist charakteristisch für programmierbare Logikbausteine.

Multiplexer und Demultiplexer

  • Mit Multiplexern lassen sich beliebige logische Funktionen realisieren:
Eingangsvariablen der BF

Abbildung auf Adresssignale ai des Multiplexers

Ausgangsvariable der BF

Ausgangssignal Q des Multiplexers

Logikwerte

Gegeben durch Eingangssignale E

\[\begin{gathered} f(A) = S(A, E) \\ S \to \left\{ {\begin{array}{*{20}{c}} {{e_i},{\text{wenn }}{a_i} = 1} \\ {x = 0/1,{\text{sonst}}} \end{array}} \right. \end{gathered} \]

Multiplexer und Demultiplexer

figmux4

Abb. 4. Beispiel eines Multiplexers als Implementierung einer booleschen Funktion. Die E-Matrix wird zeilenweise Oder-verknüpft