ДЕКОМПОЗИЦИЯ СИСТЕМ ПОЛНОСТЬЮ ОПРЕДЕЛЕННЫХ БУЛЕВЫХ ФУНКЦИЙ ПО ИХ ЗАДАНИЮ В ВИДЕ КОМПАКТНЫХ ТАБЛИЦ
Abstract
Рассматривается ряд табличных методов декомпозиции систем полностью определенных булевых функций. Особенностью этих методов является то, что исходная система задается в виде или компактной таблицы, или компактной таблицы с мнимыми значениями, которые, как правило, имеют меньшие размеры, чем карты Карно. Приводятся также результаты экспериментального исследования некоторых из этих методов на типовых примерах.
About the Authors
Ю. Поттосин
Объединенный институт проблем
информатики НАН Беларуси
Belarus
Belarus
Е. Шестаков
Объединенный институт проблем информатики НАН Беларуси
Belarus
Belarus
References
1. Hartmanis J., Stearns R.E. Algebraic Structure Theory of Sequential Machines. – Prentice-Hall, Englewood Cliffs, NJ, 1966.
2. Бибило П.Н., Енин С.В. Синтез комбинационных схем методом функциональной декомпозиции. – Мн.: Наука и техника, 1987. – 189 с.
3. Ashenhurst R.L. The decomposition of switching functions // Proceedings of on International Symposium on the Theory of Switching. April 2-5, 1957. – V.29. – Harvard Univ., 1959. – P. 74-116.
4. Curtis H.A. Generalized tree circuit – the basic building block of an extended decomposition theory // J. Assoc. Comput. Mach. – 1963. – № 10. – P. 562 581.
5. Curtis H.A. Simplified decomposition of Boolean function // IEEE Trans. on Comput. – V. 25, October 1967. – P. 1033 1044.
6. Karp R.M. Functional decomposition and switching circuit design // J. Soc. Industr. Appl. Math. – 1963. – V. 11. – №. 2. – P. 291 335.
7. Закревский А.Д. Логический синтез каскадных схем. – М.: Наука, 1981. – 416 с.
8. Шестаков Е.А. Декомпозиция системы полностью определенных булевых функций по покрытию аргументов // АВТ. – 1994. – №1. – C.12 20.
9. Поттосин Ю.В., Шестаков Е.А. Декомпозиция системы частичных булевых функций по ее табличному заданию // АВТ. – 1999. – №3. – С.36 47.
10. Шестаков Е.А. О декомпозиции систем полностью определенных булевых функций методом тождественных отображений // Идентификация образов. – Мн.: Ин-т техн. кибернетики НАН Беларуси, 1999. – С. 129 148.
11. Saucier G., Duff C., Poirot F. State assignment using a new embedding method based on an intersecting cube theory // Proceedings of the Design Automation Conference, June 1989. – P. 321-326.
12. Goldberg E.I. Methods of Boolean encoding of predicate arguments values. – Minsk, 1991. – 26 p. (Preprint / Inst. of engineering cybernetics, the Academy of Sciences of Belarus; № 3).
13. Goldberg E.I. Face embedding by componentwise construction of intersecting cubes. – Minsk, 1995. – 43 p. (Preprint / Inst. of Engineering Cybernetics, the Academy of Sciences of Belarus; № 1).
14. Кардаш С.Н. Декомпозиция системы булевых функций методом тождественных отображений // Проектирование систем логического управления: Сб. науч. тр. – Мн.: Ин-т техн. кибернетики АН БССР, 1986. – С. 22-31.
15. Шестаков Е.А. О декомпозиции систем булевых функций методом тождественных отображений. – Мн., 1988. – 16 с. (Препринт / Ин-т техн. кибернетики АН БССР; № 42).
16. Гольдберг Е.И. Декомпозиция ПЛМ. – Мн., 1991. – 32 с. (Препринт / Ин-т техн. кибернетики АН БССР; № 6).
17. Brzozowski J.A., Luba T. Decomposition of Boolean functions specified by cubes // Research Report CS-97-01. – Waterloo, Canada: University of Waterloo, 1997. – 36 p.
18. Brzozowski J.A., Lou J.J. Blanket algebra for multiple-valued function decomposition // Proceedings of the International Workshop on Formal Languages and Computer Systems. – Kyoto, Japan, March 18–21, 1997.
19. Pottosin Yu.V., Shestakov E.A. Decomposition of system of completely specified Boolean functions using their compact table representation // 4th International Workshop «Boolean Problems». – Freiberg (Sachsen), 2000. – P. 135-142.
20. Поттосин Ю.В., Шестаков Е.А. О табличном задании систем полностью определенных булевых функций // Информатика. – № 1. – 2004. – С. 139-147.
21. Закревский А.Д. О минимальном дизъюнктивном коде // Докл. АН БССР. – 1978. – Т.22. – № 6. – С. 516-518.
22. Кардаш С.Н. Алгоритм решения задачи о минимальном дизъюнктивном коде // Логическое проектирование дискретных устройств: Сб. науч. тр. – Мн.: Ин-т техн. кибернетики АН БССР, 1984. – С. 68-72.
Review
For citations:
, . Informatics. 2004;(2(02)):35-44. (In Russ.)
Views: 477
Email this article 