Electrical and Computer Engineering ETDs

Min-Hung Chao

Publication Date

7-8-1974

Abstract

An algorithm is proposed that solves the internal state assignment, input state assignment, and output circuit simplification problems of synchronous sequential machines. With few modifications, it can be applied to machines using various type of memory elements and is capable of solving the state assignment problems of large sequential machines.

The algorithm is first presented in a form for use on machines realized with D-type flip-flops; it is then genera­lized so that it can be applied to machines using trigger, S-R, or J-K flip-flops directly.

The features of merit in a state table that could be used to obtain internal state assignment with reduced dependency are investigated first, methods to find two-block partitions that possess these features in a state table are suggested, and the value of each feature in the internal state assignment is defined, A systematic procedure is then introduced which evaluates a limited number of the two-block partitions at a time to determine a variable in the internal state assignment. The algorithm therefore can be used in solving assignment problems of large sequential machines. During the evaluation, the algorithm is used in considering each column in the state table separately. Schemes in which use was made of this characteristic to perform the input state assignment and to obtain output circuit simplification are shown. Throughout the algorithm, the case of an in­completely specified machine is taken into consideration.

Finally, necessary modifications to generalize the algorithm are described, arid comparisons of 11 state tables solved by use of the algorithm and other published techniques are made. The algorithm is used to obtain solutions for each state table realized with both D-type and J-K flip-flops; for other techniques, only the solution of each state table realized with the specific type of flip-flop with which they are designed are shown. Results obtained through use of the algorithm compare favorably with those obtained through other means, but the labor required to obtain them is comparably less

Document Type

Dissertation

Language

English

Degree Name

Electrical Engineering

Level of Degree

Doctoral

Department Name

Electrical and Computer Engineering

First Committee Member (Chair)

Ronald Clifford DeVries

Second Committee Member

Gustave A. Efroymson

Third Committee Member

Dale Sparks

Download

Share

COinS