Novel method to simplify Boolean functions

• Autorzy: Prasad V. C.

Identyfikatory

DOI

10.7494/automat.2018.22.2.29

Warianty tytułu

PL

Nowa metoda upraszczania funkcji boolowskich

• Języki publikacji: EN

Abstrakty

EN

Most methods for determining the prime implicants of a Boolean function depend on the minterms of the function. Deviating from this philosophy, this paper presents a method that dependson maxterms (the minterms of the complement of the function) for this purpose. Normally, maxterms are used to get prime implicates and not prime implicants. It is shown that all prime implicants of a Boolean function can be obtained by expanding and simplifying any product of sums form of the function appropriately. No special form of the product of the sums is required. What is more, prime implicants can generally be generated from any form of the function by converting it into a POS using well-known techniques. The prime implicants of a product of Boolean functions can be obtained from the prime implicants of individual Boolean functions. This allows us to handle big functions by breaking them into the products of smaller functions. A simple method is presented to obtain one minimal set of prime implicants from all prime implicants without using minterms. Similar statements also hold for prime implicates. In particular, all prime implicates can be obtained from any sum of a products form.Twelve variable examples are solved to illustrate the methods.

PL

Większość metod wyznaczania implikantów prostych funkcji boolowskiej wykorzystuje mintermy funkcji. Niniejszy artykuł prezentuje odmienną metodę, która stosuje do tego celu makstermy (mintermy dopełnienia funkcji). Jest to podejście niestandardowe, gdyż zazwyczaj na podstawie makstermów uzyskuje się implicenty proste, a nie implikanty proste. W artykule pokazano, że wszystkie implikanty proste funkcji boolowskiej mogą być otrzymane przez odpowiednie rozwinięcie i uproszczenie funkcji podanej w dowolnej postaci typu iloczyn sum. Nie jest przy tym wymagana żadna szczególna postać tego iloczynu. Co więcej, implikanty proste mogą być zwykle utworzone na podstawie funkcji w dowolnej postaci, przez przekształcenie jej do postaci typu iloczyn sum z wykorzystaniem znanych metod. Implikanty proste iloczynu funkcji boolowskich można uzyskać z implikantów prostych poszczególnych funkcji. To pozwala operować na dużych funkcjach przez rozbicie ich na iloczyn mniejszych. Artykuł pokazuje prostą metodę uzyskania jednego zbioru minimalnego implikantów prostych na podstawie zbioru wszystkich implikantów prostych bez korzystania z mintermów. Podobne stwierdzenia mają zastosowanie także w przypadku implicentów prostych. W szczególności, wszystkie implicenty proste mogą być otrzymane z dowolnej formy typu suma iloczynów. Zaproponowana w artykule metoda została zilustrowana licznymi przykładami.

Słowa kluczowe

EN

Boolean functions; digital electronics; prime implicants

PL

funkcje boolowskie; elektronika cyfrowa; implikanty proste

• Wydawca: Wydawnictwa AGH
• Czasopismo: Automatyka / Automatics
• Rocznik: 2018
• Tom: Vol. 22, no. 2
• Strony: 29--40
• Opis fizyczny: Bibliogr. 13 poz.

Twórcy

autor

Prasad V. C.

• Department of Electrical Engineering, Faculty of Engineering, Dayalbagh Educational Institute, Dayalbagh, Agra 282005, India (Retired from Indian Institute of Technology, Delhi)

Bibliografia

• [1] Marcus M.P., Switching Circuits for Engineers, Prentice-Hall, Englewood Cliffs, New Jersey 1969.
• [2] Givone D.D., Digital Principles and Design, International Edition, McGraw-Hill, New York 2003.
• [3] Kohavi Z., Jha N.K.,Switching and Finite Automata Theory, Cambridge University Press, NewYork 2010, www.cambridge.org/9780521857482.
• [4] Marcovitz A.B., Introduction to logic design, International Edition, McGraw-Hill, New York 2000.
• [5] Biswas N.N., Minimization of Boolean functions, IEEE Trans. On Computers, Vol. C-20/8, Aug.1971, pp. 925–929.
• [6] Suresh Ch., Minimization of switching functions – A fast technique, IEEE Trans. On Computers, Vol. C-24, 1975, pp. 735–756.
• [7] Rhyne N., McKinney P., A new technique for the fast minimization of switching functions, IEEETrans. On Computers, Vol. C – 26, 1977, pp. 757–764.
• [8] Gurunath B., Biswas N.N., An algorithm for multiple output minimization, IEEE Trans. On CADof Integrated circuits, Vol. 8, 1989, pp. 1007–1013.
• [9] Minato S., Fast generation of prime irredundant covers from Binary decision Diagrams, IEICETrans. Fundamentals, Vol. E 76 – A, No. 6, June 1993, pp. 967–973.
• [10] Tomaszewski S.P., Celix I.U., Antoniou G.E.,WWW – Based Boolean function minimization, Intl.J. Appl. Math. Comput. Sci., Vol. 13/1, 2003, pp. 577–583.
• [11] Prasad V.C., Efficient minimization of Boolean functions, International Journal Of Electrical Engi-neering Education, 45(4), Oct. 2008, pp. 321–327.
• [12] Prasad V.C.,Quality of minimal sets of prime implicants of Boolean functions, Intl. Journal ofElectronics and Telecommunications (Poland), Vol. 63/2, 2017, pp. 165–169.
• [13] Prasad V.C., Generalized Karnaugh Map method for Boolean functions of many variables, IETEJournal of Education (India), Vol. 58/1, 2017, pp. 11–19.