Neue Boolesche Orthogonalisierende Operative Methoden und Gleichungen

Language
de
Document Type
Doctoral Thesis
Issue Date
2016-08-31
Issue Year
2016
Authors
Can, Yavuz
Editor
Publisher
FAU University Press
ISBN
978-3-944057-70-5
Abstract

Orthogonality is a special property of Boolean functions because an orthogonal function can be easily transformed in another form and so it simplifies the handling for further calculations as the Boolean Differential Calculus. With the use of the Ternary-Vector-List to represent a Boolean function the Boolean Differential Calculus on orthogonal Ternary-Vector-Lists will be facilitated. Furthermore, the advantages in terms of computation times and memory usage will be used. In this work two logical operation methods called 'orthogonalizing difference-building ⊝' and 'orthogonalizing OR-ing v' are newly presented. The orthogonalizing difference-building ⊝ is used to calculate the difference of two product terms or of two functions of the disjunctive normal form which is provided in orthogonal form. On the basis of orthogonalizing difference-building a further logical operation method called orthogonalizing OR-ing v is going to be introduced. Orthogonal OR-ing is used to calculate the orthogonal union of two product terms. It also enables the calculation of the orthogonalizing OR-ing of two orthogonal Boolean functions of disjunctive normal form to get orthogonal results. Additionally, the implemented algorithms of both new operation methods has faster computing times in comparison to the according compositions. By reducing of two calculation steps to one step the requested memory space is reduced. Further calculation steps in the Ternary-Vector-List arithmetic is facilitated by the inherent orthogonalization. Furthermore, two new Boolean equations for the orthogonalization of Boolean functions respectively of Ternary-Vector-Lists of the disjunctive based on these new methods are set up. They provide the mathematical solution of orthogonalization for the first time. In addition, the new equations can be used as a part in the calculation procedure of getting suitable test patterns for combinatorial circuits for verifying feasible logical faults in the Ternary-Vector-Lists arithmetic. The implemented algorithms ORTH[⊝] and ORTH[ v ] based on the new equations are analyzed in computation time and memory request in compare to other methods known from the literature. The algorithms ORTH[⊝] and ORTH[ v ] reduce the computation time to a factor of approximately 2.5 with increasing dimension to 50 and increasing length of Ternary-Vectors-List of 25 Ternary-Vectors. Further advantage is the smaller number of the terms in the orthogonalized result which reduces the number of further calculation steps. ORTH[⊝] and ORTH[ v ] reduce the number of Ternary-Vectors by approximately 50% and enable faster calculation of the Boolean Differential Calculus due to the fewer number of operations. Thus, the additional computation time and the memory usage will be reduced. With this reduction further reductions of Ternary-Vectors is continued in the calculation procedures until the determining of test pattern. Thereby, smaller set of suitable test pattern will be provided for combinatorial circuits for verifying feasible logical faults. The minor set of test pattern and the algorithms providing faster computation time are important factors when the test time and the resulting test costs should be minimized. The scope of the new mathematical methods of orthogonalization are not limited by the area of determining of test pattern. Similar advantages can be expected for the applications in cryptology, but this is not scope of this thesis. Possibly the new methods can be used in the area of the application of Boolean functions and their orthogonalization, such as in the logic, 4 the Boolean algebra, the reliability theory, SAT-Solver, the game theory and the combinatorics.

Abstract

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 _g 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.

Series
FAU Studien aus der Elektrotechnik
Series Nr.
5
Notes
Parallel erschienen als Druckausgabe bei FAU University Press, ISBN 978-3-944057-69-9
DOI
Faculties & Collections
Zugehörige ORCIDs