ДЕКОМПОЗИЦИЯ ЧАСТИЧНЫХ БУЛЕВЫХ ФУНКЦИЙ – ПОИСК ПОДХОДЯЩЕГО РАЗБИЕНИЯ
Abstract
Исследуется проблема последовательной двухблочной декомпозиции частичных булевых функций по нестрогому разбиению на множестве аргументов. Рассматривается ключевая комбинаторная задача: нахождение подходящего разбиения на множестве аргументов, т. е. такого, по которому функция разделима. Предлагается алгоритм, существенно ускоряющий поиск подходящего разбиения путем предварительного обнаружения его следов. Алгоритм формулируется в терминах булевых и троичных векторов и матриц с использованием эффективных параллельных операций над ними.
About the Author
А. Закревский
Объединенный институт проблем информатики НАН Беларуси
Belarus
References
1. Povarov, G.N. O funktsional'noi razdelimosti bulevykh funktsii / G.I. Povarov // Doklady AN SSSR. - T. 94, № 5. - 1954.
2. Ashenhurst, R.L. The decomposition of switching functions / R.L. Ashenhurst // Proc. International Symposium on the Theory of Switching. Part 1. - Cambridge: Harward University Press, 1959. - P. 75-116.
3. Curtis, H.A. Design of switching circuits / H.A. Curtis. - Van Nostrand, Princeton, N.-J., 1962.
4. Zakrevskii, A.D. Kombinatornyi poisk podkhodyashchikh razbienii pri dekompozitsii bulevykh funktsii / A.D. Zakrevskii // Vestnik Tomskogo gosudarstvennogo universiteta. Prilozhenie № 18. - 2006. - S. 4-9.
5. Zakrevskii, A.D. Dekompozitsiya chastichnykh bulevykh funktsii - proverka na razdelimost' po zadannomu razbieniyu / A.D. Zakrevskii // Informatika. - 2007. - № 1 (13). - S. 16-21.
6. Zakrevskii A.D. Universal'naya sistema dlya resheniya zadach tipa sinteza releinykh skhem / A.D. Zakrevskii // Trudy SFTI. - Vyp. 42. - 1963. - S. 9-37.
7. Kharari, F. Teoriya grafov / F. Kharari. - M.: Mir, 1973.
For citations:
. Informatics. 2007;(2(14)):45-52.
(In Russ.)
Views: 509