Lojik fonksiyonların bilgisayarla basitleştirilmesi için algoritmalar

Abstract

ÖZET Bir lojik fonksiyonu gerçekleştiren lojik devrenin karmaşıklığı, Boole fonksiyonunun cebirsel ifadesinin karmaşıklığı ile ilişkilidir. Boole fonksiyonunun basitleştirilmesi için Cebirsel îşlemİer, Karnaugh Çizelgesi ve Tablo yöntemleri kullanılmaktadır. Cebirsel işlemler kullanılarak, Boole fonksiyonunun minimum ifadesinin bulunması için izlenecek belirli yöntemler yoktur. Karnaugh yöntemi ise, değişken sayısının beş veya altıyı aşmadığı durumlarda uygundur. Bu yöntem ile altı veya daha fazla değişkenli fonksiyonlarda, en iyi çözümün bulunduğundan emin olmak güçtür. Tablo yöntemi ile bu güçlükler aşılabilmektedir. Bu yöntem, basitleşmiş fonksiyon ifadesini üretmek için, zincirleme gerçekleştirilen işlemler ve karşılaşlaştırma esasına dayandığından programlamaya son derece uygundur. Tablo yöntemi ilk olarak Quine tarafından bulunmuş ve daha sonra McCluskey tarafından geliştirilmiş olup, Quine-McCluskey yöntemi olarak da bilinmektedir. Bu tezde, Nripendra N. Biswas tarafından geliştirilen Tablo yöntemi kullanılmıştır. Bu yöntemde temel gerektirenler, birleşme tabloları oluşturulurken seçilmekte ve diğer asal gerektiren terimler ise seçilebilir asal gerektirenler tablosundan elde edilmektedir. Bundan dolayı, Quine-McCluskey yönteminde oluşturulması gereken, Asal gerekti ren/minterm tablosuna gerek kalmamaktadır. Bu algoritmayı gerçekleştirecek bilgisa yar programı, Pascal programlama dili ile yazılmıştır. IV

SUMMARY The complexity of the digital logic gates that implement a Boolean function is directly related to the complexity of the algebraic expression from which the function is implemented. Boolean function can be minimized by algebraic manipulations, map method and tabular method. There are no specific rules to follow that will guarantee the final answer for the algebraic manipulations of simplification. The map method of simplification is convenient as long as the number of variables does not exceed five or six. For functions of six or more variables, it is difficult to be sure that the best selection has been made. The tabulation method overcomes this difficulty. It is a specific step-by-step procedure that is guarranteed to produce a simplified standart form expression for a function. It can be applied to problem with many variables and has advantage of being suitable for machine computation. The tabulation method was first formulated by Quine and later improved by McCluskey. It is also known the Quine-McCluskey method. In this thesis, the tabular method which has been improved by Nripendra N. Biswas was used. This tabular method where the essential prime implicants are selected during the process of forming the combination tables and other essential terms are selected from what have been described as chains of selective prime implicants. Consequently, the need for successive prime implicant tables is eliminated. A computer program has been developed by using PASCAL programming language to implement this algorithm.