Neue Boolesche Orthogonalisierende Operative Methoden und Gleichungen - Can, Yavuz (FAU University Press, 2016)
Orthogonalität ist eine besondere Eigenschaft Boolescher Funktionen. Die Orthogonalisierung einer Booleschen Funktion vereinfacht die Transformation in eine andere äquivalente Form. Mit dieser Arbeit werden zwei neue allgemeingültige, logische operative Verknüpfungsmethoden die 'orthogonalisierende Differenzbildung ⊝' und das 'orthogonalisierende Verodern v ' vorgestellt. Die orthogonalisierende Differenzbildung wird zur Ermittlung einer Differenz in orthogonaler Form zweier Produktterme oder zweier Funktionen eingesetzt. Das orthogonalisierendes Verodern wird zum Verodern zweier Produktterme oder zweier orthogonaler Funktionen angewendet, welches auch Ergebnisse in orthogonaler Form darbietet. Darüber hinaus weisen die algorithmischen Implementierung beider Verknüpfungsmethoden geringere Rechenzeiten mit zunehmender Dimension im Vergleich zu den herkömmlichen bekannten Operationen auf. Auch werden die Vorteile im Hinblick auf den Speicherplatzbedarf hierbei besser genutzt, weil kein zusätzlicher Algorithmus zur Orthogonalisierung benötigt wird. Zudem werden Anwendungen der orthogonalisierenden Differenzbildung in weiteren Verfahren gezeigt, wie z.B. die Bildung der orthogonalen Negierten einer Funktion der disjunktiven Normalform. Durch die inhärente Orthogonalisierung werden weitere Verarbeitungsschritte in der TVL-Arithmetik, wie das Boolesche Differentialkalkül, erheblich vereinfacht. Ternär-Vektor-Listen werden als rechnerinterne Darstellung für binäre Funktionen verwendet und sind für die Behandlung Boolescher Probleme vorteilhafter. Daneben werden in dieser Arbeit zwei neue mathematische Boolesche Gleichungen zur Orthogonalisierung Boolescher Funktionen bzw. Ternär-Vektor-Listen disjunktiver Normalformen hergeleitet, welche jeweils auf den neuen Verknüpfungen ⊝ und v basieren. Damit wird zum ersten Mal mathematisch die Problematik der Orthogonalisierung behandelt und einfache Gleichungen zur Berechnung der orthogonalen Form vorgestellt. Zudem werden die beiden neuen Methoden in der Bestimmung von Testbelegungen für kombinatorische Schaltnetzwerke zur Verifizierung möglicher logischer Fehler in der TVL-Arithmetik eingesetzt. Ihre implementierten Algorithmen weisen zudem Vorteile bezüglich Rechenzeit und Speicherplatzbedarf auf und ermöglichen damit die Berechnung von minimierterer Menge an Testbelegungen. Im Vergleich zu den Methoden aus der Literatur reduzieren die neuen Algorithmen ORTH[⊝] und ORTH[ v ] die Rechenzeit um einen Faktor von ca. 2,5. Zusätzlich haben die beiden neuen Algorithmen ORTH[⊝] und ORTH[ v ] die Eigenschaft bessere Lösungen zu liefern, das bedeutet, orthogonale TVLen geringerer Anzahl an Termen, d.h. eine Reduzierung um etwa 50%. Damit wird eine Weiterbehandlung der ermittelten orthogonalen TVL mit geringerer Anzahl an Operationen gewährleistet, welche zum einen weitere Rechenzeiten optimiert und zum anderen die Anzahl an Terme in den nachfolgenden Verfahrensschritten niedriger ausfallen lässt. Mit dieser Verminderung wird die Reduzierung an Termen bis zur Ermittlung der Testbelegungen fortgesetzt, so dass minimierte Testsätze zur Verifizierung von kombinatorischen Schaltungen am Ende der Berechnungslinie erhalten werden können. Mit der geringeren Rechenzeit der Algorithmen und der minimal ermittelten Menge an Testsätzen wird eine Einsparung in Testzeit und die damit verbundenen Testkosten erreicht werden können.
Keywords: Algorithmus; Boolesche Funktion; Disjunktive Normalform; Mengenlehre; Orthogonalisierung; Orthogonalität; Rechenzeit