Kısmen belirli ardışıl makinelerde durum indirgeme yöntemlerinin karşılaştırılması ve bilgisayar programı geliştirilmesi

Abstract

Sonlu durumlu makinelerde durum indirgemesi problemi ardışıl devrelerin karmaşıklığının azaltılması için önemlidir. Bu tezde, kısmen belirli ardışıl makinelerde durum indirgeme için Puri'nin [10] algoritması ile ilgilenilmiştir. Algoritma iyileştirilerek etkili bir bilgisayar programı geKştirilmiştir. Puri'nin algoritması, asal uyumluları kullanarak bir tarama ağacı oluşturmaktadır. Tarama ağacı maksimal uyumsuzlara bağlı olarak, elde edilen alt sınıra göre küçük tarama uzayından etkili bir şekilde oluşturulur. Ayrıca yöntemde kullanılan iki budama kriteri ile tarama uzayında daha fazla durumun elenmesi sayesinde sonlu durumlu makineye ait minimal kapalı örtü kolayca bulunabilmektedir. SMST ( State Minimization with Search Tree ) programı asal uyumlulardan veya durum tablosundan minimal makinenin bulunması için geliştirilmiştir. Program iki farklı alt programın birleşiminden meydana gelir. Birinci program, durum tablosundan maksimal uyumlular, maksimal uyumsuzlar ve asal uyumlular sınıfının bulunmasında kullanılır. Asal uyumlular sınıfını kullanan ikinci programla da minimal makine bulunur. SMST, C++ programlama dilinde Borland C++ Builder - 4 kullanılarak geliştirilmiş ve 32 bitlik Windows programda derlenmiştir. Program tek çalıştırılabilir (*.exe) dosyadan oluşur ve derleme aşamasında sadece statik bağlayıcılar kullamldığmdan herhangi bir DLL dosyaya gerek duyulmamaktadır.

The problem of state reduction in a finite state machine (FSM) is important to reduce the complexity of a sequential circuit. In this thesis Puri's algorithm for state minimization of incompletely specified sequential machines is concerned. The algorithm is improved and an efficient computer program is developed. Puri's algorithm constructs a search tree from prime compatibles. It efficiently builds up a relatively small search space by utilizing a tight lower bound derived from maximal incompatibles. In addition, the two pruning criteria of this method provide further state elimination in the search space so that minimal closed cover of finite state machine can be found easily. A computer program called SMST (State Minimization with Search Tree) has been developed in order to find minimal machine from prime compatible blocks or state table. The program is composed of two different subprograms. The first one is used to find maximal compatibles, maximal incompatibles and prime compatibles class from the state table. The minimal machine is found by the second one by using prime compatibles class. SMST has been developed in C++ by using Borland C++ Builder -4 and has been compiled as a 32 bits MS Windows program. As we have used only static linking during compilation stage, the program consists of a single executable file and it does not require any other DLL (dynamic link library) file.