T06-Reversible-Logik-und-Fredkin

Reversible Logik & Fredkin-Gatter

Zusammenfassung

Reversible Logik ist ein Konzept aus dem Quantum Computing, bei dem keine Information verloren geht. Ein Gatter ist reversibel, wenn sich aus dem Output eindeutig der Input rekonstruieren lässt — die Abbildung muss bijektiv sein. Konsequenz: die Anzahl der Ein- und Ausgänge muss gleich sein, und die Anzahl der Einsen im Input bleibt im Output erhalten.

Das Fredkin-Gatter ist ein 3-Input/3-Output Gatter, das bedingt zwei Eingänge vertauscht. Es ist reversibel und funktional vollständig (universal): alle 16 Booleschen Funktionen in 2 Variablen lassen sich damit realisieren.

Motivation: Das Landauer-Prinzip besagt, dass beim Löschen eines Bits Information als Energie freigesetzt wird (). Reversible Gatter verhindern diesen Informationsverlust.

Exam-Relevanz

Aufgabe 4 — Fredkin-Gatter & reversible Berechnung (2 + 2 + 12 = 16 Punkte)

Teilaufgabe Punkte Inhalt
A4a 2P Landauer-Prinzip: Beispielfunktion (PLA) + Eingabe, bei der Information gelöscht wird
A4b 2P Nicht-reversibles Gatter finden: gleiche Anzahl I/O, aber Anzahl Einsen ändert sich. Woher stammt die Energie?
A4c 12P Alle binären Booleschen Funktionen auf Fredkin-Gatter zurückführen

A4c ist die schwerste Einzelaufgabe der Klausur (12 von 16 Punkten innerhalb einer Aufgabe). Die Klausur gibt 10 der 16 Funktionen vor; die restlichen 6 (Konstanten, AND, Identitäten, , ) sind nicht in der Tabelle.

Reversible Logik

Definition

Ein Gatter mit Eingängen und Ausgängen ist reversibel, wenn die Abbildung bijektiv ist. Dann gilt:

  • Aus dem Output lässt sich der Input eindeutig rekonstruieren.
  • Die Anzahl der Einsen im Input entspricht der Anzahl der Einsen im Output.

Landauer-Prinzip

Beim Löschen eines Bits Information wird Energie freigesetzt:

Dabei ist die Boltzmann-Konstante und die Temperatur. Irreversible Gatter (AND, OR, NOT alleine) verineben Information und setzen damit Energie frei.

Warum AND/OR nicht reversibel sind

AND hat 2 Eingänge, 1 Ausgang: , also nicht bijektiv. Zudem: Input und und ergeben alle Output — Information geht verloren.

OR analog: Input , , ergeben alle Output .

XOR hat zwar 2 Eingänge und 1 Ausgang (nicht reversibel allein), aber mit einem zusätzlichen Carry-Ausgang wird XOR zu einem reversiblen Gatter (Toffoli/CNOT-Familie).

Warum Fredkin reversibel ist

Das Fredkin-Gatter hat 3 Eingänge und 3 Ausgänge und ist bijektiv: der Input kann aus dem Output rekonstruiert werden, da das Kontrollsignal durchleitet und die Swap-Operation ihre eigene Inverse ist.

Fredkin-Gatter

Definition

Das Fredkin-Gatter hat 3 Eingänge und 3 Ausgänge :

  • Das Kontrollsignal wird durchgeleitet: .
  • Wenn : Inputs werden nicht vertauscht (, ).
  • Wenn : Inputs werden vertauscht (, ).

Logische Gleichungen

Wahrheitstabelle
0 0 0 0 0 0
0 0 1 0 1 0
0 1 0 1 0 0
0 1 1 1 1 0
1 0 0 0 0 1
1 0 1 1 0 1
1 1 0 0 1 1
1 1 1 1 1 1

Eigenschaften:

  • Reversibel: bijektive Abbildung .
  • Anzahl Einsen erhalten: in jeder Zeile hat gleich viele Einsen wie .
  • Universal: kann alle Booleschen Funktionen realisieren.

Universalität des Fredkin-Gatters

Schlüssel-Einsicht: Konstante Inputs

Setzt man einen Input auf eine Konstante (0 oder 1), verhält sich das Fredkin-Gatter wie ein bekanntes Gatter:

Mit (Null auf zweiten Daten-Input):

Mit (Eins auf zweiten Daten-Input):

Mit (Konstanten auf beiden Daten-Inputs):

ä

Abgeleitete Basis-Gatter

Gatter Fredkin-Realisierung Formel
NOT(a)
AND(a, b)
OR(a, b)

Da funktional vollständig ist, ist auch das Fredkin-Gatter universal.

XOR aus Fredkin-Gattern (geschachtelt)

Mit den obigen Definitionen:

ITE-Operator Analog

Der ITE-Operator (If-Then-Else) aus der BDD-Theorie ist strukturell identisch zum Fredkin-Gatter:

Vergleich mit den Fredkin-Ausgängen:

ist exakt ITE. Jede ITE-Realisierung lässt sich direkt als Fredkin-Realisierung übersetzen (verwende -Ausgang).

Die Übungsaufgabe Blatt 11 Aufgabe 5 verlangt, alle 16 binären Booleschen Funktionen auf ITE zurückzuführen — dieselbe Aufgabe wie A4c, nur mit ITE statt Fredkin. Die ITE-Lösungen übertragen sich 1:1 auf Fredkin via .

Konzept BDD / Software Fredkin / Hardware
Operator
If-Zweig (f=1)
Else-Zweig (f=0)
Konstante 0 Terminal-Knoten 0 Input 0
Konstante 1 Terminal-Knoten 1 Input 1

Siehe: k623-Binaere_Entscheidungsdiagramme_BDDs_ITE-Beispiel_Variablenordnung, Blatt11

Strategie für A4c (12P)

Vorgehen

  1. Basis-Gatter definieren: NOT, AND, OR als Fredkin-Ausdrücke (siehe oben).
  2. Einfache Funktionen first: 6 der 16 Funktionen sind mit einem einzigen Fredkin-Gatter + Konstanten realisierbar.
  3. Geschachtelte Funktionen: XOR, XNOR, NAND, NOR benötigen 2–3 Fredkin-Gatter (über NOT/AND/OR zusammengesetzt).
  4. Konstanten: 0 und 1 direkt als Konstante eintragen.
  5. Identitäten (, ): Fredkin mit oder leitet durch.
  6. Wiederverwendung: Funktionen dürfen auf zuvor definierte Funktionen zurückgreifen (keine zyklischen Definitionen!).

Hinweis aus der Klausur

Schauen Sie zuerst was passiert wenn Sie auf '0' oder '1' setzen.

Mit erhält man AND-artige Funktionen, mit erhält man OR-artige Funktionen.

Alle 16 Booleschen Funktionen — Vollständige Tabelle

Definitionen (Abkürzungen für geschachtelte Ausdrücke):

Nr Ausdruck Name Fredkin-Realisierung
0 0 0 0 0 False
1 0 0 0 1 AND
2 0 0 1 0
3 0 0 1 1 proj
4 0 1 0 0
5 0 1 0 1 proj
6 0 1 1 0 XOR
7 0 1 1 1 OR
8 1 0 0 0 NOR
9 1 0 0 1 XNOR
10 1 0 1 0 NOT
11 1 0 1 1
12 1 1 0 0 NOT
13 1 1 0 1
14 1 1 1 0 NAND
15 1 1 1 1 True

Verifikation der Single-Gate-Lösungen

— Nr. 2 () ✓

— Nr. 4 () ✓

— Nr. 3 (proj ) ✓

— Nr. 5 (proj ) ✓

— Nr. 11 () ✓

— Nr. 13 () ✓

Verifikation der geschachtelten Lösungen

XOR (Nr. 6): ✓

NOR (Nr. 8): ✓

XNOR (Nr. 9): ✓

NAND (Nr. 14): ✓

Klausur-Tabelle (10 vorgegebene Funktionen)

Die Klausur gibt folgende 10 Zeilen vor (die restlichen 6 — 0, 1, AND, , , , — fehlen):

Ausdruck Name Fredkin
1 0 0 1 XNOR
1 0 1 0 NOT
1 0 1 1
1 1 0 0 NOT
1 1 0 1
1 1 1 0 NAND
0 1 0 1 proj
0 1 1 0 XOR
0 1 1 1 OR
0 0 1 1 proj

Typische Klausuraufgabe

A4 (Exam und Probeklausur identisch):

Das Fredkin-Gatter wird definiert mit Kontrollsignal und zwei Daten-Inputs . Die drei Ausgänge sind .

  • A4a (2P): Geben Sie eine Beispielfunktion als PLA und eine Eingabe an, bei der Information gelöscht wird (Landauer-Prinzip). Beispiel: AND-Gatter, Input (1,0) → Output 0; aus 0 lässt sich nicht rekonstruieren, ob Input (0,0), (0,1) oder (1,0) war.
  • A4b (2P): Geben Sie ein nicht-reversibles Gatter mit gleichvielen Ein- und Ausgängen an, bei dem sich die Anzahl Einsen ändert. Beispiel: AND mit 2 Eingängen und 2 Ausgängen (zweite Ausgabe = 0): Input (1,1) → (1,0), Anzahl Einsen geht von 2 auf 1. Die Energie in herkömmlichen Gates stammt aus der Stromversorgung (VDD).
  • A4c (12P): Vervollständigen Sie die Tabelle mit 10 vorgegebenen Booleschen Funktionen. Geschachtelte Fredkin-Ausdrücke sind erlaubt. Sie dürfen zuvor definierte Funktionen wiederverwenden.

Siehe: Exam A4, probeklausur A4

Übungsblätter

Blatt Aufgabe Bezug Punkte
Blatt11 A5 ITE-Operator: alle 16 binären Booleschen Funktionen auf ITE zurückführen 4P

Die ITE-Übung (Blatt 11 A5) ist die direkte Vorbereitung für A4c. Da , übertragen sich alle ITE-Lösungen direkt auf Fredkin.

Quellen

Priorität

CRITICAL — A4c ist mit 12 Punkten die schwerste Einzelaufgabe der Klausur. Sie erfordert:

  1. Verständnis des Fredkin-Gatters (Swap-Mechanismus mit Kontrollsignal).
  2. Erkennen, dass konstante Inputs das Gatter zu AND/OR/NOT reduzieren.
  3. Systematisches Durchgehen aller 16 Funktionen.
  4. Geschachtelte Ausdrücke für XOR, XNOR, NAND, NOR.

Empfohlene Vorbereitung: Zuerst Blatt 11 A5 (ITE) lösen, dann die Lösungen auf Fredkin übertragen.