[PDF] State assignments for non-normal asynchronous sequential circuits

View - Download State assignments for non-normal asynchronous sequential circuits

Previous PDF

Next PDF

Scholars' Mine Scholars' Mine

Masters Theses Student Theses and Disser

tations 1969

State assignments for non-normal asynchr

onous sequential State assignments for non-normal asynchr onous sequential cir cuits cir cuits Gar y Keith Maki F ollow this and additional works at: https:/ /scholarsmine.mst.edu/masters_theses P art of the Electrical and Computer Engineering Commons Depar tment: Depar tment: Recommended Citation Recommended Citation

Maki, Gar

y Keith, "State assignments for non-normal asynchronous sequential circuits" (1969). Masters

Theses. 5356.

https:/ /scholarsmine.mst.edu/masters_theses/5356 This thesis is br

ought to you by Scholars' Mine, a service of the Missouri S&T Library and Learning Resources. This work is pr

otected by U. S. Copyright Law. Unauthorized use including reproduction for redistribution requires the permission of the cop

yright holder. For more information, please contact scholarsmine@mst.edu.

STATE FOR NON-NORMAL

ASYNCHRONOUS SEQUENTIAL CIRCUITS

by

GARY KEITH MAKI 1943

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

ELECTRICAL ENGINEERING

1969

·r 7-!L&if/

ii

ABSTRACT

There is a lack of procedures that can be used to find good internal state assignments for asynchronous sequential circuits operating in the non-normal mode. Presented here, are two generalized state assignments, which are functions only of the number of rows in a flow table. The suggested bounds for the generalized state assignments are m + [log 2 m] and m + [m/2] internal state variables for a 2m-row flow table, where [ 1 means "next lowest integer". Both general- ized state assignments produce group (linear) codes. The algorithms for generating these internal state assignments are easy and straight-forward to implement. It is shown that each of these state assignments satisfactorily encode certain classes of flow tables. Even though a general proof has not been found to show that these assignments are standard, worst- case situations have been constructed, and it has never been necessary to increase the suggested bounds. An internal state assignment procedure for obtaining non-standard or non-generalized state assignments is also presented. The internal state assignments, using the pro- posed method, are obtained in a systematic manner; and generally require fewer internal state variables than other procedures presently available. iii

ACI\l-JQI·JLEDGEBENT

The author is deeply indebted to Dr. James H. Tracey for his assistance and guidance during the entire graduate program and in the preparation of this thesis. Thanks also to Dr. Stephen Szygenda and Ross Heitzmann for their careful and prompt reading of this paper. The author wishes to express his gratitude to his wife, Alice, for her support and assistance during these four years of graduate work. After being the bread winner for four ye::.rs, she is well-deserving of a rest.

TABLE OF CONTENTS

ABSTRACT • ï ï ï . . . . . . . . . . . . . . . .

ACKNOWLEDGEMENT

LIST OF FIGURES

Chapter

I. II.

INTRODUCTION

GENERALIZED STATE ASSIGNMENT 1

A. B. c.

Preliminaries •

Characteristics of Assignment 1

Principal-Column Partitions •

III. GENERALIZED STATE ASSIGNMENT 2

A. Characteristics of Assignment 2

B. Principal-Column Partitions •

IV. TRANSITION PATHS -GENERAL CASE ï ï

v. NON-GENERALIZED STATE ASSIGNMENT ï

VI. SUMMARY

iv Page ii iii v 1 10 10 14 26
52
52
56
71
83
103

BIBLIOGRAPHY • ï ï ï ï ï ï ï ï ï ï ï ï ï ï ï ï ï ï ï ï ï 105

VITA • ï . • ï ï ï ï ï ï ï ï ï ï ï ï ï . • ï ï ï . . • ï 106

LIST OF FIGURES

Figure

1-1 Flow table example

1-2 Non-normal flow table

2-1 Flow table to illustrate column partitions

2-2 First step in generating an assignment

2-3 Complete code for an B-row flow table

2-4 State assignment for a 25-row flow table

2-5 Flow table with a principal-column partition

2-6 Principal-column partition for a 24-row flow

2-7 Subgroup H for 24-row flow table and column

table 2-8 2-9 partition of Figure 2-6

Subgroup H for a principal-column partition of a

2 5 -row flow table

Transition paths for a maximum-distance principal

column partition from Figure 2-6

2-10 Comparison of H with S = 111100 and H' with

s = 101011 m 2-11 3-1 3-2 3-3 3-4 3-5 3-6 m

Comparison of pi's for H with pi's for H'

Comparison of the bounds associated with Huffman's assignment, Assignment 1 and Assignment 2

Subgroup H for S = 101110101

m

Set of pi's for principal-column partitions when

m is even, and when m is odd if y is not excited m

Set of pi's for principal-column partitions for

rn odd with ym excited p.'s for principal-column partition with sm = 101110101 5

State assignment for 2 -row flow table

v Page 2 4 10 17 17 18 26
35
38
39
42
46
47
52
59
62
63
64
67

Figure

3-7 3-8 4-1 4-2 4-3 5-l 5-2 5-3 5-4 5-5 5-6

Subgroup H for principal-column partition with

sm = 1111000

Transition paths for less than maximum-distance

principal-column partition 2 4 -row state assignment

Maximum distance example for 2

4 -row flow table

Maximum distance example for 2

5 -row flow table

States of a 4-cube

States of Figure 5-l in a 5-cube with y

5 = y 1 e yquotesdbs_dbs17.pdfusesText_23

[PDF] design of experiments pdf

[PDF] design of iir and fir digital filters

[PDF] design of iir filters

[PDF] design of machine tools by basu pdf

[PDF] design pattern tutorialspoint

[PDF] design pattern bits

[PDF] design pattern java

[PDF] design pattern library c++

[PDF] design pattern online test

[PDF] design pattern textbook

[PDF] design patterns by tutorials pdf

[PDF] design patterns by tutorials source code

[PDF] design patterns cheat sheet pdf

[PDF] design patterns classification

[PDF] design patterns exam questions