T05-PLA-und-Gatter

PLA & Gatter

Zusammenfassung

Ein Programmable Logic Array (PLA) ist eine zweistufige Hardware-Realisierung einer Booleschen Funktion: Eine AND-Plane erzeugt Produktterme (Minterme/Implikanten), eine OR-Plane kombiniert diese zu Ausgängen. PLAs implementieren direkt die DNF (disjunktive Normalform). Die Gatter-Bibliothek (AND, OR, NOT, NAND, NOR, XOR, XNOR) bildet die Basis für mehrstufige Realisierungen, wobei NAND und Inverter in CMOS-Technologie direkt realisierbar sind. Der Pentium-FDIV-Bug (1994) war ein vergessener PLA-Eintrag im Dividierer. Die Klausur fragt PLA-Konstruktion, den Pentium-Bug und den Zusammenhang zwischen PLA-Größe und Geschwindigkeit ab (A3b/c/d, 9 Punkte).

Exam-Relevanz

Teil Punkte Thema
A3b 3 PLA aus Funktionstabelle bestimmen, kleinster PLA, Variablenlimit
A3c 3 Intel Pentium PLA: vergessene Einträge, PLA nach Korrektur kleiner
A3d 3 PLA-Größe vs. Geschwindigkeit, Bedeutung für ReTI-Hardware

Total A3b–d: 9 Punkte. Zusammen mit A3a (Widerspruchsbeweis, 7P) ergibt das die vollen 16P von Aufgabe 3.

Gatter-Bibliothek

Standardgatter (STD)

AND2

AND2
0 0 0
0 1 0
1 0 0
1 1 1

OR2

OR2
0 0 0
0 1 1
1 0 1
1 1 1

NOT (Inverter)

NOT
0 1
1 0

NAND2

NAND2
0 0 1
0 1 1
1 0 1
1 1 0

NOR2

NOR2
0 0 1
0 1 0
1 0 0
1 1 0

XOR2

XOR2
0 0 0
0 1 1
1 0 1
1 1 0

XNOR2

XNOR2
0 0 1
0 1 0
1 0 0
1 1 1

Funktionale Vollständigkeit

  • NAND allein ist funktional vollständig: Alle Booleschen Funktionen lassen sich ausschließlich mit NAND-Gattern realisieren.
  • Ebenso ist NOR allein funktional vollständig.
  • NOT aus NAND:
  • AND aus NAND:
  • OR aus NAND: (De Morgan)

CMOS-Technologie (Transistor-Level)

Complementary Metal Oxide Semiconductor: Verwendet p-Kanal- und n-Kanal-Transistoren komplementär.

Transistor leitet bei sperrt bei
p-Kanal
n-Kanal

CMOS-Inverter (NOT):

  • p-Kanal oben (zur Spannungsquelle = logische 1)
  • n-Kanal unten (zur Masse = logische 0)
  • Eingang an beiden Gates
  • Bei : n-Kanal leitet Ausgang = 0
  • Bei : p-Kanal leitet Ausgang = 1

CMOS-NAND (2 Eingänge):

  • n-Kanal-Transistoren in Reihe (seriell) Ausgang = 0 nur wenn beide leiten ()
  • p-Kanal-Transistoren parallel Ausgang = 1 wenn einer leitet ( oder )
  • Transistoranzahl: 4 (2 p-Kanal + 2 n-Kanal)

CMOS-NOR (2 Eingänge):

  • n-Kanal-Transistoren parallel Ausgang = 0 wenn einer leitet
  • p-Kanal-Transistoren in Reihe Ausgang = 1 nur wenn beide leiten
  • Transistoranzahl: 4

Wichtige Eigenschaft: Zu jedem p-Kanal-Transistor gibt es einen komplementären n-Kanal-Transistor. Es gibt niemals einen leitenden Pfad von zur Masse (kein Kurzschluss). Dadurch geringer Leistungsverbrauch (nur Umladung beim Schalten).

AND und OR gibt es nicht direkt in CMOS — sie werden aus NAND/NOR plus Inverter zusammengesetzt.

PLA (Programmable Logic Array)

Definition

Ein PLA ist eine zweistufige Hardware-Struktur zur Realisierung Boolescher Funktionen in DNF (disjunktiver Normalform).

Struktur

Eingänge x₁, x₂, ..., xₙ
    │    │        │
    ▼    ▼        ▼
┌─────────────────────┐
│     AND-Plane       │  ← erzeugt Produktterme (Implikanten)
│  (Product Terms)    │
└─────────────────────┘
    │    │        │
    ▼    ▼        ▼
┌─────────────────────┐
│      OR-Plane       │  ← kombiniert Produktterme zu Ausgängen
└─────────────────────┘
    │    │
    ▼    ▼
Ausgänge f₁, f₂, ..., fₘ

Funktionsweise

  1. AND-Plane: Jeder Eingang und dessen Negation werden in die AND-Plane geführt. Jede "Zeile" der AND-Plane bildet einen Produktterm (ein Monom / Implikant), indem ausgewählte Literale UND-verknüpft werden. Ein fehlender Eingang in einer Zeile bedeutet "don't care" für diese Variable.

  2. OR-Plane: Die Produktterme werden in Spalten geführt. Jeder Ausgang ist die ODER-Verknüpfung ausgewählter Produktterme. So entsteht die DNF.

  3. Programmierung: Ein PLA wird "programmiert", indem Verbindungen in der AND-Plane und OR-Plane gesetzt oder weggelassen werden. In der Diagrammdarstellung sind gesetzte Verbindungen als Punkte markiert.

Beispiel

Für :

  • AND-Plane erzeugt zwei Produktterme: und
  • OR-Plane kombiniert sie:
  • Kosten (siehe unten): (Literale pro Term + 1) + Anzahl Ausgänge (Anzahl Produktterme + 1)

Warum "zweistufige Logik"?

Ein PLA hat genau zwei Logikebenen: AND und OR. Die Tiefe (depth) ist somit konstant 2 (bzw. 3 inklusive Inverter für negierte Literale). Dies steht im Gegensatz zu mehrstufigen Realisierungen mit beliebigen Gatter-Bibliotheken, die tiefere (aber potenziell kleinere) Schaltkreise erzeugen können.

PLA-Größe minimieren

  • Der kleinste PLA wird durch Minimierung der DNF erreicht (Minimalpolynom).
  • Verfahren: Karnaugh-Veitch-Diagramme oder Quine-McCluskey.
  • KV-Diagramme funktionieren gut bis ca. 4–6 Variablen (darüber wird es unübersichtlich).
  • Quine-McCluskey skaliert exponentiell () und ist für große nicht praktikabel.

Pentium-Bug

Was passiert ist

Der Intel Pentium FDIV-Bug (entdeckt 1994) war ein Fehler in der Gleitkomma-Divisionseinheit (FPU) des Intel Pentium-Prozessors. Bei bestimmten Operanden lieferte der FDIV-Befehl falsche Ergebnisse.

Ursache

Die Divisionseinheit verwendete ein PLA zur Implementierung der Lookuptabelle für den SRT-Divisionsalgorithmus. Intel hatte bei der Programmierung des PLA einige Einträge vergessen (fehlende Zeilen in der AND-Plane), wodurch für bestimmte Eingaben falsche Quotientenbits berechnet wurden.

Folgen

  • Intel musste ca. 5 Millionen Pentium-Prozessoren austauschen (Kosten: ~475 Millionen Dollar).
  • Der Vorfall ist ein klassisches Beispiel für die Wichtigkeit von Hardware-Verifikation.

Warum war der PLA nach der Korrektur kleiner?

Nach dem Bug-Fix wurde der PLA kleiner, nicht größer. Grund: Die fehlenden Einträge wurden nicht einfach hinzugefügt — stattdessen wurde die gesamte Tabelle neu minimiert. Durch die Minimierung der DNF (Reduktion auf wesentliche Primimplikanten) wurde die Anzahl der Produktterme reduziert, was zu einem kleineren PLA führte. Der ursprüngliche (fehlerhafte) PLA war also nicht minimal — er war schlecht optimiert und zusätzlich unvollständig.

Verbindung zu PLA/Hardware-Verifikation

  • Ein PLA muss alle Eingaben korrekt abdecken. Fehlende Einträge falsche Ausgaben für nicht abgedeckte Fälle.
  • Hardware-Verifikation (z.B. formale Verifikation, Äquivalenzchecking) hätte den Fehler gefunden.
  • Das Beispiel zeigt: Ein fehlerhafter PLA kann manchmal richtig rechnen (für die meisten Eingaben) und nur für spezielle Eingaben falsch — was den Fehler schwer erkennbar macht.

Kosten & Tiefe von Schaltkreisen

Schaltkreis-Definition

Ein Schaltkreis ist ein 5-Tupel über einer Zellenbibliothek BIB, wobei ein azyklischer gerichteter Graph ist.

Kosten

Die Kosten zählen die Anzahl der Gatterknoten (nicht die Eingänge oder Konstanten). Für PLAs gibt es spezifischere Kostenfunktionen:

PLA-Kostenfunktionen

Sei durch ein PLA realisiert mit Produkttermen.

— Anzahl der Verbindungen (Punkte) im PLA:

wobei die Anzahl der Literale im -ten Produktterm ist. Der erste Summand zählt die Verbindungen in der AND-Plane, der zweite die in der OR-Plane.

— Anzahl der Produktterme:

Kostenbeispiel

Gegeben und :

  • Produktterme: (2 Literale), (2 Literale), (1 Literal)
  • Produktterme, Ausgänge

Tiefe

ää

Die Tiefe entspricht der Graph-Tiefe des azyklischen Graphen , also der maximalen Anzahl von Kanten auf einem Pfad von einem Eingang zu einem Ausgang.

  • Für ein PLA: (AND-Ebene + OR-Ebene), evtl. 3 mit Inverter-Ebene.
  • Für mehrstufige Schaltkreise: kann größer sein, aber die Kosten können kleiner sein.

Trade-off: Größe vs. Geschwindigkeit

  • Kleinere PLA schneller: Weniger Produktterme bedeuten kürzere Signalwege und weniger Gatter-Verzögerung. Die Tiefe bleibt zwar konstant 2, aber die Verzögerung innerhalb einer Ebene wächst mit der Anzahl der Verbindungen (Kapazität, Leitungslänge).
  • Größerer PLA langsamer: Mehr Produktterme mehr Verbindungen höhere Kapazität größere Verzögerung.
  • Für die ReTI-Implementierung in Hardware: Ein kleinerer PLA bedeutet weniger Chip-Fläche, geringerer Energieverbrauch und schnellere Ausführung. Dies ist besonders wichtig, da die ReTI als Modellrechner in Hardware gegossen werden soll — jede eingesparte Transistorfläche zählt.

Typische Klausuraufgabe

A3b — PLA aus Funktionstabelle (3 Punkte)

Gegeben sei eine Funktionstabelle für eine Boolesche Funktion. Erklären Sie in ca. 3 Sätzen, wie man daraus ein PLA bestimmt. Wie kann der kleinste PLA ermittelt werden? Bis zu wie vielen Variablen funktioniert solch eine Minimierung?

Antwort:

  1. Aus der Funktionstabelle werden die ON-Menge abgelesen und die Minterme als Produktterme in die AND-Plane des PLA eingetragen; die OR-Plane verknüpft alle Minterme zum Ausgang.
  2. Der kleinste PLA wird durch Minimierung der DNF (Minimalpolynom) bestimmt, z.B. mittels Karnaugh-Veitch-Diagramm oder Quine-McCluskey, wobei überflüssige Produktterme entfernt werden.
  3. KV-Diagramme funktionieren praktisch bis ca. 4–6 Variablen; Quine-McCluskey skaliert exponentiell und ist für große nicht praktikabel.

A3c — Intel Pentium PLA (3 Punkte)

Intel nutzte für einen Dividierer ein PLA und hatte dabei einige Einträge vergessen. Nach Korrektur war der PLA kleiner. Warum?

Antwort: Die fehlenden Einträge führten zu falschen Divisionsergebnissen (FDIV-Bug). Bei der Korrektur wurde das PLA nicht einfach ergänzt, sondern die gesamte Logik neu minimiert. Durch die Minimierung der DNF (Reduktion auf wesentliche Primimplikanten) wurde die Anzahl der Produktterme reduziert, was zu einem kleineren PLA führte. Der ursprüngliche PLA war also nicht minimal optimiert.

A3d — PLA Größe und Geschwindigkeit (3 Punkte)

Ist ein kleinerer PLA schneller oder langsamer? Warum? Was bedeutet ein kleinerer PLA für die Implementierung der ReTI in Hardware?

Antwort: Ein kleinerer PLA ist schneller, da weniger Produktterme und Verbindungen zu geringerer Kapazität und kürzeren Signalwegen führen. Die Tiefe bleibt zwar konstant (zweistufig), aber die Verzögerung innerhalb der Ebenen sinkt. Für die ReTI-Hardware-Implementierung bedeutet ein kleinerer PLA: weniger Chip-Fläche, geringerer Energieverbrauch und höhere Taktfrequenz.

Übungsblätter

Blatt Aufgabe Thema Punkte
Blatt05 2 Schaltkreis zeichnen, symbolische Simulation 5
Blatt05 3 CMOS-Realisierung: , max. 6 Transistoren 4
Blatt05 4 Eindeutigkeit der Belegung (Widerspruch + Induktion) 3
Blatt06 4 Gatter nur mit NAND realisieren (AND, NOT, OR, NOR, XOR, XNOR), Kosten 7
Blatt07 2 PLA aus Abbildung: Polynome, Kosten, Hypercube, KV-Diagramm 6

Quellen

Priorität

CRITICAL. A3b–d liefern 9 der 16 Punkte von Aufgabe 3 und sind konzeptionell (kein langes Rechnen). Beherrsche:

  1. PLA-Struktur (AND-Plane → OR-Plane) und DNF-Zusammenhang.
  2. CMOS-Grundlagen: p-Kanal leitet bei 0, n-Kanal bei 1; NAND = n seriell / p parallel.
  3. Pentium-Bug: vergessene PLA-Einträge, Neu-Minimierung kleinerer PLA.
  4. Kosten: = Verbindungen, = Produktterme. Tiefe = längster Pfad.
  5. Kleinerer PLA = schneller (weniger Kapazität, kürzere Wege).