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: