The article discusses a two-stage method of minimizing Boolean functions for designing digital combinational circuits. At the first stage, the search for simple conjuncterms is carried out by the method of bitwise division of the set of initial conjuncterms. At this way tautology does not appear, low-rank conjuncterms are found without intermediate gluing. At the second stage, the search for the minimal set of simple conjuncterms is performed by the method of chain coverage of the table of simple conjuncterms. In the cyclic part, fragments of chain functions are found, the coverage of which is quite simple. To reduce the computational load at branching points of chains, a decision can be made about entering or removing the corresponding simple conjuncterm from the finite set based on the calculation of the complexity factor in the vicinity of the branching. The proposed method is heuristic.
[1] McCluskey E. J. Minimization of Boolean Functions. Bell System Technical Journal, 1956, 35, pp. 1417–1444.
[2] Quine W.V. The Problem of Simplifying Truth Functions. American Mathematical Monthly, 1952, 59, pp. 521–531.
[3] Закревский А. Д. Алгоритмы синтеза дискретных автоматов. М.: Наука, 1971. 512 с.
[4] Hwa Н. R. A method for generating prime implicants of a boolean expressions. IEEE Transactions on Electronic Computers. New York: The Institute of Electrical and Electronics Engineers, Inc., Jun. 1974. Vol. C-23, No. 6, pp. 637–641.
[5] Svoboda A. Ordering of implicants. IEEE Transactions on Electronic Computers. New York: The Institute of Electrical and Electronics Engineers, Inc., Feb. 1967, Vol. EC-16, No. 1, pp. 100–105.
[6] Рицар Б. Є. Мінімізація булових функцій методом розчеплення кон’юнктермів. Управляющие системы и машины, 1998, № 5, С. 14–22.
[7] Рицар Б. Є., Мінзюк В. В. Теоретико-множинна модифікація мінімаксного методу покриття булових функцій. Управляющие системы и машины, 2005, № 5, С. 43–47.
[8] Мінзюк В. В. Спосіб спрощення задачі покриття булових функцій. Вісник Національного університету “Львівська політехніка” Радіоелектроніка та телекомунікації, 2005, № 534, С. 24–28.
[9] Мінзюк В. В. Спосіб синтезування кон’юнктермів булових функцій. Вісник Національного університету “Львівська політехніка” Радіоелектроніка та телекомунікації, 2004, № 508, С. 256–262.
[10] Мінзюк В. В. Спосіб сортування цілих чисел для задач мінімізації булових функцій. Вісник Національного університету “Львівська політехніка” Радіоелектроніка та телекомунікації, 2011, № 705, С. 135–137.
[11] Мінзюк В. В. Модифікація методу порозрядного вирощування простих кон’юнктивних термів булових функцій. Збірник наукових праць Інституту проблем моделювання в енергетиці ім. Г. Є. Пухова. К.: ІПМЕ ім. Г. Є. Пухова НАН України, 2012, Вип. 65, С. 129–134.
[12] Мінзюк В. В. Метод пошуку простих кон’юнктивних термів булових функцій побітовим розбиттям множини. Збірник наукових праць Інституту проблем моделювання в енергетиці ім. Г. Є. Пухова. К.: ІПМЕ ім. Г. Є. Пухова НАН України, 2013, Вип. 66, С. 95–103.