Asenkron ardışıl devrelerde durum kodlama

Abstract

Bu Tezde, asenkron ardışıl makinalanın tasarımı ve kritik yarışsız durum kodlama yöntemleri incelenerek, Tracey yöntemine dayanan bir kodlama yöntemi ve bu yönteme dayanan bir bilgisayar programı geliştirilmiştir. İkinci bölümde asenkron ardışıl devre tasarım adımlan incelenmiştir. Özellikle kritik yarşsız kodlama yöntemlerinin başlıcaları ele alınmış ve karşılaştırılmıştır. Üçüncü bölümde J.Tracey, R. Smith ve D.Fisher tarafından geliştirilen yöntemler incelenmiştir. Bu bölümde ayrıca bu Tezde geliştirilen bir durum kodlama yöntemi de verilmiştir. Geliştirilen yöntemde kullanılan ağaç yapılan, bu Tezde geliştirilen algoritmalar ile budanmış olarak elde edilerek programın hızı arttırılırken, kullanılan bellek miktarı önemli ölçüde azaltılmıştır. Bu Tezde geliştirilen yöntem Borland C++ derleyicisi ile kodlanarak, herhangi bir PC de çalıştırılabilen ve bellekte 125 kByte yer kaplayan, oldukça hızlı çalışan bir program elde edilmiştir. Bu program büyük makinaları makul sürede kodlayabilecek kadar hızlı çalışmaktadır. Elde edilen kodlar doğrudan geçiş özelliği göstermektedir. Bu Tezde geliştirilen program literatürde kullanılan zor örnekler üzerinde denenmiştir ve elde edilen sonuçlar diğer yöntemler ile durum değişkeni sayısı ve kodlama zamanı bakımından karşılaştırılmıştır. Bu program yardımıyla yapılan kodlamalarda gerekli durum değişkeni sayısı doğrudan geçişli durum kodlaması için minimaldir. Bu da programın bir üstünlüğünü oluşturmaktadır, öte yandan, literatürde incelenmiş olan büyük makinalanın bu program yardımıyla kısa sürede kodlanabilmesi, programın hızının da yüksek olduğunu göstermiştir. Bu Tezde geliştirilen algoritmalar, örtme tekniklerini veya ağaç yapılarını kullanmayı gerektiren her tür problemin çözümünde kullanılabilecek olan genel algoritmalardır.In this Thesis design of asynchronous sequential logic circuit and race free state assignment methods are concerned. Sequential logic functions may be implemented in either synchronous sequential logic circuit or asynchronous sequential logic circuit architectures. In synchronous circuits, clock pulses synchronize the operation of the circuit while in asynchronous circuits it is usually assumed that no such clocking is available. Asynchronous sequential logic circuits have several important intrinsic advantages over their synchronous sequential logic circuit counterparts. A desirable feature of asynchronous design is that the resulting circuit may take full adventage of basic device speed since the circuit does not have to wait for the arrival of clock pulses before effecting the transition. Moreover, asynchronous sequential logic circuits generally require less space to implement since the basic functional primitives are gates, not gates and memory, as is the case for synchronous sequential logic circuits. However, for a given sequential logic function, the asynchronous sequential logic circuit design prosess is much more complex and time consuming than that of synchronous sequential logic circuit. This is due in part to critical race problems mat are associated with asynchronous sequential logic circuit architectures; but through the appropriate state assignments, the race conditions can be avoided. In Chapter 2, asynchronous sequential circuit design steps are given. The first step in the design of an asynchronous sequential circuit is the construction of a flow table describing the circuit behavior from a word description of the function to be realized. In doing this, it is often relatively easy to construct first a primitive flow table which has exactly one stable state in each row. A flow table generated from a word description of a sequential function, such as a primitive flow table, usually contains more states than necessary to realize the specified function. For more economical realizations, it may be desirable to reduce the number of states in a flow table. After this step, reduced flow table is coded and hazard free circuit realization is found. The states of asynchronous sequential logic circuit can be coded by an n-digit binary data word y. State transitions occur in responce to changes in the asynchronous sequential logic circuit's input. Let ya and yb represent the present and next states, respectively. The vm Hamming distance Hd between y8 and yb is defined as the number of digit positions in which the corresponding digits of ya and yb are different. If Hd >0, a state transition occurs since ya * yb. During the time interval that the state is switching from ya to yb, one or more digits in y become unstable; that is, their actual state at any instant in time is not known. However, a potential problem may occur if more than one digit in y becomes unstable at any instant in time. This condition, known as a race, occurs when Hd >1. A race can be critical or noncritical. Cricital races may cause an asynchronous sequential logic circuit to malfunction because the next state might depend on the order in which the unstable digits in y change state. In Chapter 3, state assignment methods are examined for designing asynchronous sequential logic circuits. A state assignment method based on Tracey' s method is developed and this method is programmed in C++ programming language. Tracey has given three procedures for coding the states of asynchronous sequential logic circuits. Resulting codes insure that the circuit functions according to flow table specifications independent of variations in transmission delays within the circuit. The assignment methods produce codes that allow one to maximize the operating speed of the circuit. Large asynchronous sequential logic circuits can not be coded with Tracey method. Smith improved a method based on Trâcey' s method. Large asynchronous sequential logic circuits can be coded with Smith' s method but the number of state variables is not minimal. By using state assignment method improved by D.Fisher and S.Wu, large asynchronous sequential logic circuits can be coded. A race condition is classified as being either an intrinsic race or a generated race. Intrinsic races decompose into two subclasses : visible intrinsic races and hidden intrinsic races. Algorithms have been developed to identify and eliminate these races. A graph, referred to as Node- Weight Diagram facilitates the process of making state assignments and guarantees that no races are generated. This state assignment method adds cycles and states as needed, to avoid intrinsic races and always attempts to use the minimum or near-minimum number of state variables and states. The method which is developed in this Thesis is explained below, and results are given for computer program OPASKOD which is based on this method. If the present state is dj, present input is x and the next state is dj, then we write dj=g(x,di). Definition 1 : If states dj and dj are the same, it is said that the state dj is stable under x input, otherwise it is unstable. Definition 2 : When the binary code of the state dj differs from that of the state dj in two or more bit positions, it is said that there is a race from the state dj to state dj. IX Definition 3 : If a race condition exists and there is a possibility that unequal transmission delays may cause the circuit to reach a stable state other than the intended, the race is called critical, otherwise noncritical. Definition 4 : A flow table in which each unstable state leads directly to a stable state is called a normal flow table. The given method is valid for normal flow tables. If a given flow table is not normal, it can be normalized [5]. In normal flow tables, if there is an unstable state in an input column, then its stable state also exists. Partitions will be used in the developed method. Therefore some related definitions are given below. Definition 5 : A partition n on a set of states D is a collection of subsets of D such that their pairwise intersection is the null set. The disjoint subsets are called the blocks of 7t. If the set union of these subsets is D, the partition is completely specified; otherwise, the partition is incompletely specified. Elements of D that do not appear in n are called unspecified elements with respect to that partition. The state assignment will be made by the use of partitions which are defined by the columns of the flow table. The partitions defined by a certain column of the flow table are obtained as follows. Consider all transitions ai=[di, dj], a2=[dm, d"],...,ak=[dp, dq] and all single stable states aic+i=dr, aic+2=ds,...,ap=dt in the column Cj. As a special case, if there is only one stable state in Cj, i.e. p=l, then no critical race occurs at this column. Therefore, no partition is defined by this column. Otherwise, each pair of aj, aj, i*j may define a partition as explained below. (i) Let aj be transition [dp, dq] and aj be transition [dm, d"] then the corresponding partition u is 7i={dp,dq ; dm,d"}. (ii) Let aj=[dp,dq] and aj=dr then 7r={dp,dq ; dr}. (iii) Let aj=dr and aj=d| then rc={dr ; d|}. Since the number of ai is p then the number of partitions defined by Cj is at most = - - -. The procedure is repeated for all columns and all partitions to be 2.) 2 considered for state assignment are generated. Definition 6: Partition nt is less than or equal to tcj (ni<7tj), where 7tj and Ttj may be incompletely specified, if and only if all elements specified in 7tj are also specified in tij and each block of m appears in a unique block of Ttj. All pairs of partitions Ttj and 7tj are compared and if 7tj <7tj then 7tj is eliminated, because they do not effect the coding. Considering the remaining partitions and assuming that their number is m, state assignment is made as explained below. Coding Method Each partition 7tj has exactly two blocks in it. Hence let us code each block of 7tj by a state variable yi such if the code of a block is zero, the code of other is one and the state dj in a block and the block itself has the same code. As a result of this state assignment, it can be shown that there can not exist critical race even if more than one state variable change occur in a state transition [5], [9]. In the following it is shown that number of state variables can be reduced considerably. Definition 7: Let the number of the states be n and consider the matrix riixn, whose rows correspond to partitions and whose columns correspond to the states. The elements of row i, which correspond to Ttj is "0", "1" or "-"; an element of row i which correspond to an unspecified state is "-". "0" or "1" is the code of the corresponding state which is included in it,. The resulting matrix is called Partition Matrix (PM). As an example let n=5 and the m partitions are Tti={l,2 ; 3,4}, it2={ 1,2 ; 5}; then PM is 12 3 4 5 *1 *2 0 0 11- 0 0 - - 1 It is obvious that changing the codes of the blocks of iti, the resulting row will be [1 100-], which is the complement of row 1. In general a row of PM can be changed by the complement of it. Definition 8: Two rows of a PM, m and 7Cj, are compatible if and only if 7tj and Ttj agree wherever Ttj and Ttj are specified. Compatible rows Ttj and Ttj have an intersection defined as a row which agrees with both Ttj and Ttj wherever either is specified and contains optinal entries everywhere else. Comparing each pair of rows of the PM, all compatible partition pairs are obtained. On the other hand, if the row of itj and the complement of the row of Ttj are compatible, it is also indicated as (tc^Wj). Let the rows of PM be enumerated as l,2,...,m. Then, for example, (2,5) means 712 and 7i5 are compatible, on the other hand (3, 1) means 713 and the complement of the 7C5 are compatible. Obviously (3, J) implies (T, 5). XI Example 1: Consider Tracey's B machine which is given in Fig.l.a, where the bold written states are stable ones. II :m={14,23} I2:n3={l,25} 13: 7ti