Neue Boolesche Orthogonalisierende Operative Methoden und Gleichungen

Description

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.

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.