İkili karar diyagramları yardımıyla lojik devre tasarımı

Abstract

IKILI KARAR DİYAGRAMLARI YARDIMIYLA LOJİK DEVRE TASARIMI ÖZET Bu Tezde, İkili Karar Diyagramları (Binary Decision Diagrams: BDD) incelenmiş ve İkili Karar Diyagramları yardımıyla bir Boole fonksiyonunun asal bileşenlerini hesaplayan bir bilgisayar programı geliştirilmiştir. Bu çalışmada Boole fonksiyonlarının İkili Karar Diyagramları ile gösterilimi ve verilen iki Boole fonksiyonun çarpımının, bir Boole fonksiyonunun tümleyeninin belirlenmesi gibi temel işlemlerin İkili Karar Diyagramları yardımıyla gerçeklenmesi incelenmiştir. Ayrıca İkili Karar Diyagramlarından yararlanılarak kısmen belirli ardışıl makinelerde durum indirgeme işleminin nasıl yapılabileceğine değinilmiştir. Literatürde BDD'ler ile ilgili Türkçe bir çalışmaya rastlanmamıştır. İkinci bölümde BDD'lerin tanımı ve özellikleri ile ilgili temel bilgiler verilmiştir. Üçüncü bölümde BDD'ler ile gerçekleştirilen algoritmalar ve bu algoritmaların karmaşık dereceleri halanda bilgiler verilmiştir. Dördüncü bölümde Boole fonksiyonlarının BDD gösterilimi, Boole fonksiyonlarının diğer gösterilimleri ile karşılaştırılmış ve BDD'lerin üstünlükleri açıklanmıştır. Beşinci bölümde BDD'lerin uygulama alanları verilmiştir. Altıncı bölümde BDD'ler yardımıyla bir Boole fonksiyonunun asal bileşenlerini belirleyen bir algoritma verilmiştir. Bu algoritma ve Kopenhag Enformasyon Teknolojisi Enstitüsünde geliştirilmiş olan BuDDy isimli yazılım paketi kullanılarak bir Boole fonksiyonunun asal bileşenlerini belirleyen bir program olan IPCP (Implicit Prime Computation Program: Kapalı Gösterilimle Asal Bileşen Hesaplayan Program) geliştirilmiştir. Bu programda bir Boole fonksiyonunun asal bileşenlerini veren BDD graflan oluşturulmaktadır. Bu program MCNC (Microelectronics Center of North Carolina) bençmarklan ile test edilmiştir. Test sonuçlan Tablo 6.2 ve 6.3 'de gösterilmiştir. Bu tablodan da görüldüğü gibi bir Boole fonksiyonunun asal bileşenleri BDD'ler yardımıyla hızlı bir şekilde bulunabilmektedir.

LOGIC DESIGN WITH BINARY DECISION DIAGRAMS SUMMARY Current technologies of digital logic design enable implementation of more complex digital circuits on silicon. While the digital designs are becoming more complex, it becomes more difficult to manipulate them on computer. In verification, synthesis or placement and routing phases of design flow many tools exist from which the designer can benefit to implement the product. It is becoming therefore more and more important to represent digital circuits in an efficient way to manipulate them. Computer models of digital hardware are normally compiled to multi-level circuits by current synthesizers and verification tools. Current digital logic design theory is incapable of manipulating multi-level circuits efficiently. On the other hand most researches on manipulation are heavily concentrated on two-level logic representa tions of Boolean functions. Therefore a program which translates a multi-level logic to two-level logic is strongly needed. Two-level logic representation output of these programs that is generated from multi level logic representations is easy to manipulate but requires huge memory space and it is time consuming. In order to increase productivity and to reduce design costs, representations which use less memory and time are required. Binary Decision Diagrams (BDDs) are a candidate for this problem. BDD is a canonical- representation of Boolean functions and order of complexity of algorithms which are used on BDDs are of polynomial order. Representation of Boolean functions on BDDs require less memory and time to manipulate them. These make BDDs superior to other conventional representations of Boolean functions. Therefore many verification, synthesis and physical design tools benefit from BDD representations of Boolean functions. Using computer program, BDDs of given circuits are created, then several operations are carried on BDD structures. The techniques that are based on the idea of operating on discrete sets by their char acteristic functions represented by BDDs are mostly called implicit techniques. Implicit manipulation of Boolean functions generally require less memory and time. BDDs are Directed Acyclic Graphs (DAGs) and are made up vertices and edges. Each vertex is assigned to a variable of the Boolean function and each has its own identity number in order to distinguish several vertices which belong to the same variable. A vertex has two child vertices, low(y) and highiy), respectively, that are connected to their parent vertex with edges. Edges are directed from parent vertex to child vertex. Root vertex is the vertex with no parent vertices. Terminal vertex is the XIvertex with no child vertices. There are two terminal vertices, which are 0 and 1, respectively, that give the Boolean function output. A BDD has one root vertex. The evaluation of Boolean function on BDDs are done by selecting edge connecting vertex v with its child vertex low(v), when assigning 0 to the variable that is assigned to the vertex v, or by selecting edge connecting vertex v with its child vertex high(y), when assigning 1 to the variable that is assigned to the vertex v. In this manner, a terminal vertex is reached and the value of this terminal vertex gives the function output for the values of variable that select edges and vertices. In order to use BDDs efficiently, some restrictions on BDD data structures can be useful. The restriction is that a path starting from root vertex to terminal vertices includes such vertices which are assigned to variables of Boolean function in increasing order. The class of these BDDs is called OBDDs (Ordered BDDs). This restriction makes possible to implement recursive algorithms based on variable order. Two BDD graphs are isomorphic if their subgraphs are also isomorphic. If an OBDD does not have isomorphic subgraphs, the OBDD of the Boolean function has a canonical representation. This class of BDDs are called ROBDD (Reduced OBDD). A ROBDD can be obtained by using Reduce Algorithm on OBDD. Reduce Algorithm takes an OBDD as input and generates a canonical OBDD graph which is a ROBDD. In literature ROBDDs are also named BDD. The operations on BDDs have polynomial time complexity. This feature makes BDDs attractive for Boolean function manipulation. Since time complexity is of order polynomial in the size of the BDD graphs, researches on BDDs are mainly concentrated on reducing the size of BDD representing Boolean functions. The size of BDD graph is measured by the number of vertices. The size of BDD graphs changes at each class of the function to be represented. For example adder circuits have BDD graph size polynomial in the number of inputs. There are also inherently complex functions whose BDD graph size have exponential complexity. Multiplier architectures are well-known example. Another parameter affecting BDD graph size is the order of variables. Variable ordering dramatically changes the size of BDD. Best variable ordering for adder architecture produces BDD graphs size linear in the number of inputs, whereas worst variable ordering for adder architecture produces BDD graphs size polynomial in the number of inputs. Finding the best variable ordering for minimum size of BDD graph is NP-Complete, therefore main variable ordering algorithms are heuristic. Several applications exist where BDDs are used. A typical application is two-level logic minimization. Two-level logic minimization problem is made up of two steps: 1. Find prime implicants of Boolean function 2. Find a minimum prime cover of Boolean function Implicit computation of prime implicants of Boolean functions are examined in [4, 16-20, 31]. In this application, Boolan function of interest is firstly converted into a BDD and using this BDD prime computation algorithm generates a BDD that stores prime implicants of the Boolean function. It can be shown that prime implicant set of xiia Boolean function can be obtained by the prime implicants of the cofactors of Boolean functions. Each vertex of a BDD shows a Boolean function. Child vertices of a vertex show cofactors of Boolean function that is represented by parent vertex. Therefore, prime implicant computation algorithm is built from Shannon expansion. Implicit prime computation algorithm assumes that a literal has three values: 1. The variable does not exist, 2. The variable itself might exist 3. The complement of the variable might exist. In order to represent these 3 cases in BDDs, 3 subgraphs must be defined for recursive call of each vertex. A recursive call to the prime computation algorithm determines which variable is assigned to the vertex. Since the data structure to represent BDDs of Boolean functions only supports two child vertices, a special coding must be used to define 3 child vertices in the same data structure. Therefore a coding technique called metaproduct has been used. The BDD which gives prime implicants is built on metaproduct variables. It has been shown that implicit prime computation algorithm produces redundant vertices. However, the cubes for the paths through redundant vertices in prime BDD are covered by the cubes of other paths in prime BDD. xiu