TVL Resolvierung
Betreuer: M. Sc. Xingzhou Chen, M.Sc. Tobias Rumpel
Problemstellung: In der Digitaltechnik werden hauptsächlich Vektoren mit zwei Werten (0 und 1) verwendet, um Information darzustellen. Diese binären Vektoren bilden die Grundlage für die digitale Repräsentation von Daten und digitalen Schaltungen. Ternärvektorlisten (TVL) hingegen bestehen aus Vektoren mit drei Werten (0, 1 und −). Das Symbol „−“ stellt hierbei eine zusätzliche Informationsebene dar, die eine Kompaktierung binärer Listen (das sind binäre Funktionen) erlaubt. Die Resolvierung hat als eineindeutiges Ergebnis dann die Überdeckung der Belegungsmenge mit Primimplikanten (die Überdeckung mit den größten Überlappungen, die Überdeckung mit den kürzesten Termen). Durch diesen Vorgang kann z. B. die zugrunde liegende binäre Funktion minimiert werden, was zu einer Vereinfachung der digitalen Schaltungen führt. Es gibt verschiedene Möglichkeiten zur Realisierung dieses Verfahrens, wobei hier ein am Lehrstuhl entwickelter Algorithmus verwendet werden soll.
Problemlösung: Zunächst soll ein Konzept (Paperwork) ausgearbeitet werden, bevor die eigentliche Programmierung (Codework) beginnt. Dabei ist vorgesehen, den Algorithmus und seine Funktionen schrittweise zu implementieren. Zuerst sollen auch die Datenstrukturen für die Ternärvektoren (TV) erarbeitet werden, bevor der gesamte Prozess auf Ternärvektorlisten (TVL) angewendet wird. Der Prozess soll zudem mittels Binary Decision Diagrams (BDD) visualisiert werden. Um den Algorithmus möglichst speicher- und zeiteffizient umzusetzen, wird die Programmiersprache C (gcc in C11) verwendet.
Durchführung:
Die Durchführung ist in 5 Teilen geplant
- Einarbeiten in die Theorie der TVL
- Verstehen und Anwenden von TVL-Operationen
- Aufstellen einer Datenstruktur für Ternärvektoren (TVL)
- Verstehen und Darstellen des Algorithmus für die Resolvierung
- Programmieren des Algorithmus in C11
Beginn sofort - Geeignet für studentische Arbeiten (BA, MA, Forschungspraktikum)