Logic differential calculus in multi-valued logic design

• Autorzy: Yanushkevich S.

Warianty tytułu

PL

Logiczny rachunek różniczkowy w projektowaniu układów wielowartościowych

• Języki publikacji: EN

Abstrakty

EN

Logic Differential (LD) Calculus theory is one of the directions of algebra of logic. It is oriented toward solving the Logic Design problems. The achievements of industry on Multiple-Valued Logic (MVL) gates has stimulated research on generalization of LD Calculus. In the thesis, for the first time, LD Calculus methods are developed and generalized for MVL functions and applied to solve a class of MVL Design problems. The matrix mathematical methods underlies the approach, that allows to explain the achieved results from the unified positions, to generalize and formalize the relations with other areas (spectral techniques and arithmetical Logic). In the first Chapter the research area is analyzed. Basics of MVL and LD Calculus, achievements in theory, computational techniques and application of LD Calculus and arithmetical Logic are considered. The state of the design and technology of MVL gates and networks (history, technology) are explained. In the second Chapter the matrix approach to formalize LD Calculus operators is explained. It generalizes and develops the achieved results, and reduces the problem of implementation of these operators to the mapping of their flow graphs into linear systolic arrays. The notation of Boolean Difference is generalized towards MVL functions. The correctness of the generalization is proved by logic Taylor series. The problem of minimization of Reed-Muller expansions for incompletely specified logic functions is solved. The generalization of exact and heuristic Zakrevskij's strategy is offered. The efficiency of the algorithms is confirmed by testing on benchmarks and their extensions. Applications of LD operators (analysis of function properties, groupability, analysis of sensitivity of MVL combinational circuits) are considered. A new approach to solve Logic Differential equations is demonstrated in the third Chapter. The Logic Design problems solved by using the LD equations are considered. The proposed algorithms are shown to be implemented on the linear systolic arrays. The fourth Chapter is devoted to arithmetical analogues of LD operators. The correctness of the approach is proved using arithmetical analogue of logic Taylor expansion. The minimization algorithms for incompletely specified logic functions in the arithmetical polynomials domain and experimental results are considered. In the fifth Chapter the problem of generalization of D-algorithm to detect faults in MVL combinational networks is solved. Fault models of typical failures in MVL circuits implemented by various technologies are proposed. LD operators are used as formal tools to generalize D-algorithm. Hardware support of the algorithm is evaluated. The Parametric LD operators, as a significant part of the LD Calculus, are presented in the Appendix. The newness consists in the development of the operators toward the space of multi-valued data and solution a number of related applied problem.

PL

Teoria logicznego rachunku różniczkowego jest jednym z kierunków algebry logiki i zorientowania na rozwiązywanie problemów projektowania logicznego. Osiągnięcia przemysłu w zakresie elementów wielowartościowych stymulują badania nad rozwinięciem LRR. W niniejszej pracy, po raz pierwszy, metody LRR rozwinięte i uogólnione dla funkcji wielowartościowych i zastosowane w celu rozwiązania klasy problemów logicznego projektowania układów na bazie bramek wielowartościowych. U podstaw tego podejścia leżą matemateczne metody macierzowe, które pozwalają na wyjaśnienie osiągniętych rezultatów z jedynych pozycji, co umożliwia formalizację relacji z innymi dziedzinami badań: metodami spektralnymi i logiką arytmetyczną. W pierwszym rozdziale przedstawiono podstawy logiki wielowartościowej i LRR, rozpatrzono podejścia alternatywne oraz osiągnięcia w dziedzinie projektowania wielowartościowych układów i systemów stworzonych na ich podstawie. Sformułowano cele badań i obszar zagadnień rozwiązywanego problemu. W drugim rozdziale wyjaśniono macierzowe podejście do formalizacji LRR. Umożliwiło to uogólnienie osiągniętych rezultatów, zmniejszenie problemu implementacji wspomnianych operatorów w celu odwzorowania grafów na liniowe macierze systoliczne. Zapis boolowskich różniczek został uogólniony dla funkcji wielowartościowych. Prawidłowość tego uogólnienia jest dowiedziona przy pomocy szeregu Taylora. Rozwiązany został problem minimalizacji wielomianów Reeda-Mullera dla niezupełnych funkcji logicznych. Zaprezentowano uogólnienia dokładnej i heurystycznej strategii Zakrzewskiego. Efektywność algorytmów została potwierdzona poprzez przeprowadzenie szeregu eksperymentów na standardowych funkcjach testujących. Pokazane jest wykorzystanie operatorów LRR (analiza właściwości funkcji, analiza czułości wielowartościowych układów kombinacyjnych). Nowe podejście do rozwiązywania logicznych równań różniczkowych zostało przedstawione w rozdziale trzecim. Rozpatrzono problemy projektowania logicznego formalizowane poprzez te równania. Proponowany algorytm został przedstawiony jako implementacja liniowych macierzy systolicznych. Czwarty rozdział został poświęcony arytmetycznym analogiom operatorów LRR. Prawidłowość podejścia została udowodniona przy pomocy arytmetycznych analogii logicznego szeregu Taylora. Rozpatrzono algorytmy minimalizacji niezupełnych funkcji logicznych w klasie wielomianów arytmetycznych. W rozdziale piątym przedstawiono zagadnienie uogólnienia D-algorytmu do detekcji błędów wielowartościowych układów kombinacyjnych. Zaproponowano modele błędów typowych uszkodzeń w wielowartościowych układach różnych rodzajów technologii. Operatory LRR były użyte jako formalne narzędzia uogólnienia D-algorytmu. Oceniono także sprzętowe ulepszenie przedstawionego algorytmu. W załączniku, zostały przedstawione parametryczne operatory LRR. Nowość polega na uogólnieniu tych operatorów dla przestrzeni funkcji wielowartościowych, na tej podstawie proponowana metodyka rozwiązywania szeregu stosowanych zadań.

Słowa kluczowe

PL

logika wielowartościowa; rachunek różniczkowy; projektowanie układów logicznych

• Wydawca: Wydawnictwo Uczelniane Politechniki Szczecińskiej
• Czasopismo: Prace Naukowe Politechniki Szczecińskiej. Instytut Informatyki
• Rocznik: 1998
• Tom: Nr 537(1)
• Strony: 7--326
• Opis fizyczny: Bibliogr. 329, tab., rys.

Twórcy

autor

Yanushkevich S.