Scholars' Mine Doctoral Dissertations Student Theses and Dissertations 1972 A method for generating UTS assignments with an iterative state transition algorithm Dattatraya Govind Raj-Karne Follow this and additional works at: https://scholarsmine.edu/doctoral_dissertations Part of the Electrical and Computer Engineering Commons Department: Electrical and Computer Engineering Recommended Citation Raj-Karne, Dattatraya Govind, "A method for generating UTS assignments with an iterative state transition algorithm" (1972).edu/doctoral_dissertations/192 This thesis is brought to you by Scholars' Mine, a service of the Missouri S&T Library and Learning Resources. This work is protected by U. Unauthorized use including reproduction for redistribution requires the permission of the copyright holder. For more information, please contact scholarsmine@mst.
A METHOD FOR GENERATING UTS ASSIGNMENTS WITH AN ITERATIVE STATE TRANSITION ALGORITHM by DATTATRAYA GOVIND RAJ -KARNE , 193 7- A DISSERTATION Presented to the Faculty of the Graduate School of the UNIVERSITY OF MISSOURI -ROLLA In Partial Fulfillment of the Requirements for the Degree DOCTOR OF PHILOSOPHY in T2783 84 pages c.8~~ ii ABSTRACT There is a lack of systematic procedures that can be used to find uni-code totally sequential (UTS) assignments from a flow table de- scription of an asynchronous sequential circuit. Presented here is an iterative internal state assignment method. This method consists of three algorithms. The first generates a minimum variable initial assign- ment from a flow table description.
The second tests the validity of this assignment by constructing minimum length transition paths without crossover and the third augments this assignment by adding an internal state variable in the event that all transition paths cannot be construc- ted without crossover. The second and the third algorithms are used iteratively until a valid non-universal UTS assignment is produced. The iterative state assignment method is systematic in all its phases. Every phase of the method includes more than one algorithm to perform the same function.
The algorithm producing minimum length transition paths is very powerful in that it can also be used in conjunc- tion with other state assignment methods producing either universal or non-universal UTS assignments. After one obtains a valid UTS assignment an algorithm is provided to replace some or all of the totally sequential transitions with mixed mode transitions. This reduces the number of subtransitions in a given transition path and therefore speeds up the transition time considerably. iii ACKNOWLEDGEMENT The author wishes to express his appreciation and extend his sincere thanks to Dr.
Tracey for his guidance during this project. The author is indebted to him for the understanding and the personal interest shown by him during the entire period of the author's doctoral studies. The author wishes to thank Dr. Taylor for his quick and careful review of this dissertation.
The author also wishes to express his gratitude to his wife Anuradha and son Shrikant for their interest and constant encourage- ment rendered during the entire period of the author's graduate study. iv TABLE OF CONTENTS Page ABSTRACT ii ACKNOWLEDGEMENT •. iii LIST OF ILLUSTRATIONS. ISAM: AN ITERATIVE STATE ASSIGNMENT METHOD.
ALIAS: An Algorithm for Initial Assignment. TRAPAGAL: A Transition Path Generation Algorithm. AAA: An Algorithm to Augment an Assignment. ALSPT: An Algorithm to Speed up Transitions.
SUMMARY AND DISCUSSION. 70 v Table of Contents continued Page IV. RElATED AREAS OF FUTURE WORK 74 A. Routing and Transition Path Generation.
Unified State Assignment Techniques. INTRODUCTION Sequential switching circuits denote a class of devices whose outputs depend not only on the present inputs but also on previous in- puts. These circuits are further classified as being synchronous or a snychronous. In synchronous circuits 1 clock pulses synchronize the operation of the circuit while in asynchronous circuits 1 it is usually assumed that no such clock is available.
A desirable feature of asyn- chronous design is that the resulting circuit does not have to wait for the arrival of clock pulses before effecting a transition. However, the absence of clock pulses introduces the problem of insuring that the circuit functions according to specifications independent of variations in transmission delays of signals. The operation of an asynchronous sequential circuit can be de- scribed by means of a flow table. As shown in Figure 1 1 it is a two- dimensional array consisting of next-state entries 1 with its columns representing the input states and its rows representing the internal states of the circuit.
The flow table usually shovys the output states, too 1 but since this paper is concerned only with the internal operation of a sequential circuit 1 the output states are not shown in the flow table. The row in which the circuit is currently operating is often referred to as the pre sent internal state or just the pre sent state. For example 1 if the pre sent state of the circuit de scribed by Figure 1 is "a" and then 2 an input II is applied I the next-state or state that the circuit will go to is "b". If the next-state is the same as the present internal state 1 then the present internal state is said to be stable with respect to that input column and is denoted by a circled next-state entry.
Uncircled entries denote unstable internal states. Input States II I2 I3 a b ® c Internal b @ e @ States c @ e @ d @) a c e d @ b Figure I. Flow Table for an Asynchronous Sequential Circuit. The combination of input state and present internal state is called the total circuit state.
In some flow tables I particular total circuit states are never entered and the corresponding next-state entries are unspecified. The unspecified next-state entry is called a "don't care" state. Flow tables with "don't care" states are called incompletely specified flow tables. Since a "don't care" state is never entered in the synthesis of the actual circuit I it is permissible to assign any value to such a state to simplify the final design.
The material presented in this paper applies to completely specified and incompletely specified flow tables. Definition: An a synchronous sequential circuit is said to be oper- ating in fundamental mode if the inputs are never changed unless the 3 circuit is in a stable state. Definition: A transition from an unstable state to a stable state is called a direct transition if all internal state variables that are to under- go a change of state are simultaneously excited. One of the basic steps in the synthesis procedure of designing an asynchronous sequential circuit is obtaining an internal state assignment.
The internal state assignment consists basically of encoding each of the internal states of a sequential circuit with a binary n-tuple or set of n-tuples. The n-tuples are encoded by n internal state variables, y 1 , y 2 ,. With n internal state variables at most 2n internal states can be encoded. In an a synchronous circuit, the internal state assignment must be made so that each internal transition always leads to a definite and appropriate stable state independent of the relative speeds of the circuit elements.
Definition: A race exists in an asynchronous sequential circuit when- ever a transition between a pair of states requires simultaneous change of two or more internal state variables. If the result of a race leads to false operation of the circuit, it is designated as a critical race; other- wise, it is a non-critical race. Every internal state assignment must permit circuit operation free of critical races. One basic approach for doing this is to allow no races at all, thereby eliminating critical races.
The second approach is to obtain an assignment that permits races, where all races are non-critical. 4 Based on these two approaches, two main types of internal state assign- ment techniques have evolved. In an assignment for an a synchronous sequential circuit where each unstable state leads directly to a stable state, all internal state vari- ables that are to change state during a transition are excited simulta- neously at the beginning of the transition. Such assignments are called single transition time (STT) assignments [ l].
Further, if only a single coding is associated with each internal state, it is called a uni-code single transition time (USTT) assignment [11]. A uni-code totally sequential (UTS) assignment also assigns a unique binary code to each internal state but all transitions between an unstable state and a stable state are accomplished through the change of a single internal state variable at a time. It is clear that races may exist in USTT assignments 1 but not in UTS assignments. Single transition time assignment techniques have received con- siderable attention from researchers over the last decade [1~2 1314 ~5].
As a result, there are well-known established methods for generating the USTT assignments and the corresponding next-state equations. Totally sequential assignment techniques 1 on the other hand, have re- ceived considerably less attention. The main contributions in this area are due to Hazeltine [ 6] I Maki [ 7, 8] , and Saucier [ 9]. Definition: A transition path for a flow table with a UTS assignment is an ordered set of adjacent internal states traversed in going from an 5 unstable state Sa to a stable state Sb.
The transition path includes Sa and sb. Definition: The distance d between two internal states S and Sb -- a is the number of bit positions in which the binary code of S differs from a the binary code of Sb. Definition: Let the distance between two internal states be d. If d state variables are excited 1 each one only once I in effecting a transi- tion between the states I then the transition is called a minimum length (ML) transition and the transition path is called a minimum length tran- sition path.
Definition: A eros sover is pre sent when transition paths for any two transitions sa -+ sb and sc-> sd 1 such that sb -1- sd 1 within the same flow table column have at least one internal state common. Definition: A k-set of a flow table column consists of k-1 unstable states leading to the same stable state together with that stable state. Definition: A UTS assignment is a valid UTS assignment if and only if it is possible to construct all transition paths such that the transition paths among the states of one k-set do not crossover transition paths among the states of any other k-set within the same flow table column. Definition: A state assignment is said to be universal if its validity depends only on the number of flow table rows; otherwise I it is non- universal.
Definition: Let s be the minimum number of interna 1 state variables 0 to uniquely code an r-row flow table. Ann variable assignment for this 6 flow table is called a near-minimal assignment if s < n < s +£so } - o- - o - 1 2 where [x} indicates the smallest integer< x. Hazeltine's [ 6] method consists of attempting to construct transi- tion paths between all stable states and their corresponding unstable states on per column basis. There is a trial and error associated with obtaining the assignment and the transition paths.
This method gener- ates a non-universal internal state assignment and transition paths are non -minimum length. Maki [ 7] not only developed a method to generate universal assign- ments but also suggested a new improved bound on the number of internal state variables for such assignments. Even though Maki did not provide a proof in support of this bound no counterexample has yet been found. For a particular class of flow tables, Maki has also developed an algo- rithm to generate transition paths for all transitions I on per column basis.