Geri Dön

Asenkron ardışıl devrelerde durum kodlama

State assignment of asynchronous sequental logic circuits

  1. Tez No: 66568
  2. Yazar: HÜLYA HACIOĞLU
  3. Danışmanlar: PROF. DR. AHMET DERVİŞOĞLU
  4. Tez Türü: Yüksek Lisans
  5. Konular: Elektrik ve Elektronik Mühendisliği, Electrical and Electronics Engineering
  6. Anahtar Kelimeler: Asenkron makineler, Bilgisayar programları, Devre tasarımı, Kodlama teknikleri, Induction machinery, Computer programs, Circuit design, Coding technique
  7. Yıl: 1997
  8. Dil: Türkçe
  9. Üniversite: İstanbul Teknik Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Elektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: Belirtilmemiş.

Özet

ÖZET 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.

Özet (Çeviri)

SUMMARY STATE ASSIGNMENT OF ASYNCHRONOUS SEQUENTIAL LOGIC CIRCUITS 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 vmHamming 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. IXDefinition 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). XIExample 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<f={ 14,35} 14: n6={12,34} tc2={14,35} 7i9={l,34} 7t5={24,35} 71t={12,5} 7t4={25,34} n8={34,5} Compairing each pair of partitions it is seen that, 7C9 £ n&, 7tg ^ n* and n 10 ^712. Hence, Tig, TC9 and 7Tio are eliminated. The PM defined by the remaining partitions is shown in Fig.l.b. The compatible partition pairs which are obtained from PM are, (1,2), (1,3), (2,3), (2,5), (2,7), (3,4), (4,6), (5,7), (6,7). Definition 9: A set of partitions tcj, tij,..., rcq is called a compatible class if each pair in the set is compatible; if a compatible class can not be enlarged then it is called a maximal compatible class. \ II 12 13 14 1 2 3 4 5 Figure l.a) Tracey's B Machine b) Corresponding PM Definition 10: A set of minimum number maximal compatible classes which include all partitions is called a minimal cover. A minimal cover gives the minimum number of state variables to prevent critical races. Order of complexities of the known algorithms to obtain all maximal compatibles and then, to obtain a minimal cover are of non-polynomial order. In other words when the number of elements in PM, is increased, the time and memory requirement increase Xllexponantially. Therefore, improvement of the algorithm in the determination of maximal compatible classes and minimal cover is very important. In order to obtain all maximal compatible classes from compatible partition pairs, a Pairs Table (PT) is arranged. The PT corresponding to example 1 is given in Fig.2.a. As it can be seen, if a pair is compatible we write 1 to the corresponding position; otherwise we write 0. The important fact is that, m and tcj are treated as if they are different partitions. Hence, the number of partitions whose complements appear should be as few as possible. To our knowledge, in handling the complements of the partitions is not treated in the literature. In the following, a way to reduce the number of complemented partitions is proposed. Consider all compatible pairs like (i, j ) in which one of the partitions is complemented. Let partition i appear n. times in these pairs. Determine the appearance numbers nj's. If the largest number is nj then use ny Then, remove the pairs which contain Tij and apply the same thing for the remaining pairs; repeat it until no pair is left. By this way, the number of complemented partitions can be reduced. As an example, let the compatible pairs which contain complemented partitions be, (1,2), (1,3), (1,4),(1,5), (1,6), (2,6), (2,7). (1) The number of appearance of the partitions are as follows. 7tj : 5, 712: 3, 713: 1, 7C4: 1, 715: 1, t%: 2, 7*7 : 1. Since the appearance of 71 1 is maximum the complement of 711 is taken and the new pairs are, (f,2), (F,3), 0,4), (f,5), (f,6), (2,6), (2,7). If the same thing is applied to the remaining pairs which are written in bold face then the result is (f,2), 0,3), 0,4), 0,5), 0,6), (2, 6), (2, 7). (2) It is seen that in (1), the complement of six partitions appear, while in (2), the complement of only two partitions appear. Thus the number of the complemented partitions are reduced to a minimum. After deciding which partitions' complement must be taken and then modifiying compatible row pairs containing complements, maximal compatible classes must be found. xmDetermination of Maximal Compatible Classes As indicated above, a one in PT corresponds to a compatible pair and a zero to an incompatible. To obtain the main compatible classes, we assume that all partitions form one compatible classes C0. Then considering each incompatible pair, we seperate C”into smaller blocks, and eventually obtain all maximal compatible classes. Let us consider a zero in PT, which corresponds to the incompatible pair (i, j). Then, C0={(l,2,...,n)}, is seperated into Ci={(l, 2,..., i-l,i+l,...,n), (1, 2,...j-l,j+l,...,n )}. If this seperation is repeated for all zeros in PT then the set of maximal compatible classes, Cm, is obtained. In this case, if the number of zeros in PT is k, elements of Cm are obtained from the leaves of a tree which may have at most 2k leaves. To decrease the computation time and memory space, it is necessary to obtain Cm from a tree whose number of leaves is as few as possible. In the given algorithm a method to minimize the number of leaves is proposed, as explained below. Instead of taking care of the effect of each zero in PT seperately we take care the effect of all zeros associated with a certain partition. Let the number of total zeros in the row and column corresponding to partition i is Vj. Determine all Vi for all partitions and consider a maximal one, say Vj. Then if the Vj partitions which are incompatible with j are 1, 2,..., Vj and j=Vj+l, then Ci is, Ci={(l, 2,..., j-1, j+1,...,m), (j, j+1, j+2,...,m)}. Now, remove the row and column from PT, which correspond to i and continue in the same way until no zero left in the remaining PT. This procedure decreases the number of leaves considerably. Moreover, we decrease the number of leaves by the use of pruning in each step : Let us assume that Cm is obtained in s steps. Obviously, s is equal to or less than the number of rows in PT. At the end of step t, l<t < s, if the blocks defined by leaves are bi, b2,..., bq, we compare each pair and if bj <bk then bj is eliminated. Thus, at the end of the s th step, the uneliminated blocks give the elements of Cm. For the example 1, as it is seen from Fig. 2.a, the number of zeros associated with the partitions are as follows. Vi =5, V2 =3, V3 =4, V4 =6, V5 =5, V6 =5, V7= 4, y? =6. Maximal ones are V4 =y^=6. We choose 714; then, Ci={(l, 2,3,5,6,7,4), (4,6)}. Removing the row and the column corresponding to 4, the PT which is shown in Fig. 2b is obtained. In the following steps, choosing tl$, 7t4, 713, and m the corresponding Q's are obtained as follows: C2={(1,2,3,5,7,4\ (4,6), (6,7)}, C3={(1, 2,3,5,7), (3, 4), (6,7), (4,6)}, C4={(1,2,3), (1,2,5,7), (3, 4), (6,7), (4,6)}, C5={(1,2,3), (1,2), (2,5,7), (3, 4), (6,7), (4,6)}. It can be seen that pruning can only be done in step 5, where eliminating (1,2), Cm is obtained as, Cm={(l,2,3), (2,5,7), (3, 4), (6,7), (4,6)}. (3) The algorithm to obtain Cm is tested in big circuits, it is seen that it is fast and requires less memory space. xivDetermination of Maximal Incompatible Classes A minimal cover obtained from Cm gives us a state coding which prevents critical races. For large circuits it may take a very long computer time to find a minimal cover. For example, in the case of TraceyD (Smith4) machine, number of maximal compatible classes in Cm is 1 179, there is at most 23 partitions in a block and the number of rows of PT is 91, 32 of them being complements. Hence, it may take very long time to obtain a minimal cover ifa fast algorithm is not used-. One fast algorithm to find a near-minimal cover is given below. Take a maximal block of Cm and remove the partitions covered by that block. Then, find another block which covers maximal number of partitions from the remaining ones; continue until all partitions are covered. Let Cm be, Cm={(l,2,3), (1,3,4), (2,3,5), (5,6), (6,7), (2,7)} and apply the above algorithm to find a cover. The order of a legitimate choise is: (1,2,3), (5,6), (1,3,4), and (2,7). But the resulting cover Cci = {(1,2,3), (5,6), (1,3,4), (2,7)} is not a minimal one; because CC2 = {(1,3,4), (2,3,5), (6,7)} is a minimal cover. Therefore, this procedure is fast but may not give the minimal cover. A cover of TraceyD machine which contains 5 maximal compatible classes is found by using the above algorithm. The corresponding state codes are 1:00000; 2:10111; 3:01000; 4:10011; 5:01001; 6:00010; 7:01010; 8:11010; 9:00001; 10:11110; 11:10110; 12:1 101 1. Thus, first time this machine is coded with 5 state variables, which indicates the efficiency of the proposed method; previously it is coded with at least 6 state variables [8], [9]. In [4] it is coded 5 state variables but coded machine is not normal. In this Thesis a new algorithm is proposed to obtain a minimal cover from Cm by the use of the set of maximal incompatible class Cm. Cm is obtained from the PT just like Cm as explained below, (i) If (i, j ) is a compatible pair then the element in the position (i,j) is zero; now replace it by one. (ii) Remove the rows and columns from PT, which correspond to complemented partitions, (iii) The block of C0 contains all partitions but not any complemented one. (iv) In the modified PT consider the ones rather than zeros and obtain C“. xvFor the example 1 the modified PT is shown in Fig.2.c and Cm is obtained as Cm={(l,4,5), (1,4,7), (1,5,6), (3,5,6), (2,4), (2,6), (3,7)}. Let a block of Cm, say Bm, contains maximum number of partitions and number of partitions contained in it be m. Let the number of blocks in a minimal cover be s then m ^ s and most of the time either m = s or m is quite close to ”s. Tracey finds a minimal cover by using Petrick function in which each partition is represented by a product term. In this Thesis a much simpler Petrick function is proposed which has only m product terms. For example 1 Tracey' s Petrick function is, Pt=(123)(257)(123+34)(34+46)(257)(46+67)(257+67). Our Petrick function is, P=(123) (34+46)(257)=(123)( 34)(257)+(123)(46)(257) where the second term gives the minimal cover with 3 state variables. Considering these blocks and PM, state codes are found as: 1:000; 2:100; 3:111; 4:001; 5:110. Our method is much faster and requires less memory space; furthermore this method can be used in other similar covering problems. However the minimal cover may not be obtained in one step. If some partitions are not covered, try to find a block which contains all missing partitions; thus a minimal cover is obtained. If it is necessary to add more than one block to the existing set than write a small Petrick function for the uncovered partitions. Race-free state assignment method which is described in this Thesis is based on Tracey' s method. Hence in the coded circuit all transitions are direct which increases the speed of the circuit. The main drawbacks of the Tracey's method are: (i) The number of state variables may be larger comparing the methods where the transitions may not be direct [4]. (ii) For large circuits, computation time and memory requirement may be large. The coding method developed in this Thesis reduces computation time and memory requirement. Some coded machines are given in Table 1. The machine Fisher2, Fisherö, Fisher8 and Fisher9 are also examined in [4]. Considering computation time and number of state variables, both methods give similar results. In this Thesis, the complements of the partitions are handled in an efficient way which may increase the speed and reduce the number of state variables. Furthermore the covering techniques which are devoloped in this Thesis are general, hence can be used in other covering problems. xviTable 1 Experimental results xvu

Benzer Tezler

  1. Tez No

    55648

    Programlanabilir lojik kontrolörler için tasarım yöntemleri

    Başlık çevirisi yok

    ERDAL ÖZKAN

    Yüksek Lisans

    Türkçe

    Türkçe

    1996

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik Üniversitesi

    DOÇ.DR. SALMAN KURTULAN

  2. Tez No

    75538

    Yeni bir hata değişik delta ağ maddeli arttırılmış delta ağı (ADA)

    Başlık çevirisi yok

    M.EBRU KOLUSAYIN

    Yüksek Lisans

    Türkçe

    Türkçe

    1998

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik Üniversitesi

    Kontrol ve Bilgisayar Mühendisliği Ana Bilim Dalı

    DOÇ. DR. MEHMET BÜLENT ÖRENCİK

  3. Tez No

    2988

    Asenkron motörlerde yumuşak yol verme

    Başlık çevirisi yok

    HALİL HALEFŞAN SUMEN

    Yüksek Lisans

    Türkçe

    Türkçe

    1987

    Makine MühendisliğiMarmara Üniversitesi

    PROF. DR. İLHAMİ ÇETİN

  4. Tez No

    10502

    Optimum design of single phase capacitor start motors

    Başlık çevirisi yok

    İLHAMİ GÜLER

    Yüksek Lisans

    İngilizce

    İngilizce

    1990

    Elektrik ve Elektronik MühendisliğiOrta Doğu Teknik Üniversitesi

    Elektrik-Elektronik Mühendisliği Ana Bilim Dalı

    PROF. DR. H. BÜLENT ERTAN

  5. Tez No

    10418

    Vektör kontrollu asenkron motor sürücü düzeneklerin analizi ve optimizasyonu

    Analysis and optimization of induction motor drive systems using vector control methods

    İSMAİL KAYA

    Yüksek Lisans

    Türkçe

    Türkçe

    1990

    Elektrik ve Elektronik MühendisliğiKaradeniz Teknik Üniversitesi

    Elektrik-Elektronik Mühendisliği Ana Bilim Dalı

    DOÇ. DR. A. OĞUZ SOYSAL

Geri Dön