L5.2 Explicit functional description

Loading...

From the course by Universitat Autònoma de Barcelona

Digital Systems: From Logic Gates to Processors

201 ratings

Universitat Autònoma de Barcelona

Digital Systems: From Logic Gates to Processors

201 ratings

This course gives you a complete insight into the modern design of digital systems fundamentals from an eminently practical point of view. Unlike other more "classic" digital circuits courses, our interest focuses more on the system than on the electronics that support it. This approach will allow us to lay the foundation for the design of complex digital systems. You will learn a set of design methodologies and will use a set of (educational-oriented) computer-aided-design tools (CAD) that will allow you not only to design small and medium size circuits, but also to access to higher level courses covering so exciting topics as application specific integrated circuits (ASICs) design or computer architecture, to give just two examples. Course topics are complemented with the design of a simple processor, introduced as a transversal example of a complex digital system. This example will let you understand and feel comfortable with some fundamental computer architecture terms as the instruction set, microprograms and microinstructions. After completing this course you will be able to: * Design medium complexity digital systems. * Understand the description of digital systems using high-level languages such as VHDL. * Understand how computers operate at their most basic level (machine language).

From the lesson

Sequential circuits (I)

<b><font size=4 color=#B22222><b>Click on "v More" to read the purpose of this module</b></font> </b><br/><br/>This is the first module dedicated to Sequential Circuits (Digital Systems with Memory).<br/> <b>To solve the quizzes you will need VerilUOC_Desktop</b>. Remember that the first week includes a complete description of VerilUOC_Desktop. In particular, VerilChart is presented in the second video.

L5.1 Sequential circuits10:54

L5.2 Explicit functional description15:59

Meet the Instructors

Elena Valderrama
Professor
Departamento de Microelectrónica y Sistemas Electrónicos. UAB.
Jean-Pierre Deschamps
Professor
Lluis Terés
Professor
Centro Nacional de Microelectrónica del CSIC
Merce Rullan
ProfesoraTitular
Departamento de Microelectrónica y Sistemas Electrónicos. UAB.
Joaquín Saiz Alcaine
Ingeniero Informático
Departamento de Microelectrónica y Sistemas Electrónicos. UAB.
David Bañeres
Profesor Agregado
Estudios de Informática, Multimedia y Telecomunicación. UOC.
Juan Antonio Martínez
Collaborator
APSI - UAB

[MUSIC]

This lesson deals with the description of sequential circuits.

In the case of combinational circuits

the straight forward method was to define tables.

What about sequential circuits specification?

In this case, state transition graphs are used.

They consist of a set of vertices,

vertices that correspond to the internal states,

and of a set of directed edges that define the state transitions.

Consider a sequential machine, and assume that it has three internal states

that we call Q0, Q1, and Q2.

So, they will be encoded with two bits.

The inputs are numbers belonging to the set 0, 1, 2, 3,

and will be encoded also with 2 bits.

The working of the circuit is defined by he following graph,

with 3 vertices, one for each state, and a set of directed edges.

For example, if the current state is Q2, and if the inputs represent

number 2, then the next stage will be Q1, and so on.

The change of internal state will occur when there is a clock pulse

of the synchronization signal.

Now, what about the outputs?

In the case of the outputs, there are two possibilities.

If we choose the Moore model, then the

output values are defined by the current state.

In this example, there is only one output bit

Y and its value is directly associated with the state.

For example, if the current state is Q0,

then the value of the output is 1; if the current state is Q2,

the current value of the output is also 1,

and if the current state is Q1, the output is equal to 0.

But if the Mealy model is chosen, then the output values

are defined not only by the current state, but also by the input values.

So, the value of Y, in the second example,

is associated with the edge that defined the state transition,

that means that, for example, if the current state is Q2,

and if the input value is 1, then

the next state will be Q1, and the output will be Y = 1.

Now, let us see an example.

The objective is to define a circuit, that controls a robot "vacuum cleaner".

It's input, there is only one input, it is an OB

input signal, equal to 1 if an obstacle (some object)

is detected in front of the robot.

There is a sensor that detects whether there

is an object, or not, in front of the robot.

And the inputs control the movement of the robot.

It can move forward;

it can rotate 90 degrees to the right;

and it can rotate 90 degrees to the left.

They are three possibilities that will be encoded with two bits.

The specification now:

in case that an obstacle is detected in front of

the robot, the first time, it turns to the right

until there is no more obstacle in front of the robot,

and after that, it moves forward.

The second time that an obstacle is detected, it

turns to the left, until there is no more obstacle,

and after that it

moves forward, and so on.

Thus the sequential circuit has one input OB equal

to 1 when there is an obstacle, and two outputs:

RR equal to 1 when it rotates to the right,

and RL equal to 1 when it rotates to the left.

If both are equal to 0, that means that the robot moves forward.

We can define the circuit with a 4-state sequential machine.

Those 4 states correspond to the following situations:

SAL: when the robot moves forward

and the preceding, rotation was to the left;

SAR when the robot moves forward

but the preceding (or the latest) rotation was to the right;

SRR when it rotates to the right, and SRL when it rotates to the left.

So we get this circuit with one input, two outputs,

and a memory that stores the four possible states.

Now, let us define the transitions between the internal states.

There are four internal states:

SAR, SRL, SAL, and SRR.

Assume that the

current state is SAR.

That means that it is moving forward

and the preceding rotation was to the right.

If there is no obstacle,

then this state doesn't change.

If there is an obstacle, the next state will be SRL,

that means that it moves to the left because

the preceding movement (or rotation) was to the right.

Now it must rotate to the left, and as long as it detects the obstacle,

it keeps moving or rotating to the left.

If there is no more obstacle, then

the new state will be SAL,

that means that it moves forward

and the preceding movement (or preceding rotation) was to the left,

and it remains in this state as long as there is no detected obstacle,

and so on. If there is an obstacle,

it goes to this state,

and if there is no obstacle

any more, the next state will be SAR.

Thus this is the final result.

Now, an exercise:

define the state transition graph of a sequential circuit with one

binary input X, one binary output Y.

It generate an output equal to

1 if the input sequence it has received

up to the current time includes an odd number of 1's;

for example, if the preceding sequence was 001011,

then it must generate 1, but if the

next input bit is 1, then it will generate 0 because now

there is an even number of 1's within the input sequence.

Let us see a solution.

We define two states S0 and S1.

S0 is the state of the circuit when the equence received

up to now (up to the current time) has an even number of 1's.

And S1 is the state of the circuit when the sequence received up to now

has an odd number of 1's.

Then, if the state is S0, that means that the

sequence received up to the current time had an even number of 1's,

and if the input is 0, the parity of the number of 1's doesn't change.

So, the circuit remains in the same state.

But, if the new input value is 1,

then there was an even number of 1's within the input sequence;

with this additional 1, now there is an odd number

of 1's within the input sequence, so that the next state is S1.

The same, if the current state is S1, and if

the next input value is zero, the parity doesn't change, so

that the system remains in the same state, but if the

input value is 1, then the parity of the number of

1's changes (it changes from odd to even)

and the circuit changes its internal state to S0.

In this case, it's a Moore machine, obviously, because

if the state is S0, then the output is 0

and in the state is S1, the output must be equal to 1.

Instead of a graph,

"next state" and "output" tables can be used

to define the working of a sequential circuit.

The "next state" table defines the next state in

function of the current state and of the input values.

And an output table defines the value of

the outputs in function of the current state,

in the case of the Moore model,

and in function of the current state and of

the input values, in the case of the Mealy model.

Let us see, an example:

this is the graph that defined the control circuit of the robot.

The same information can be defined with those two tables.

In this table, as you can see, we consider

all states, and all combinations of input values.

For example, state SAR and input 0,

state SAR and input 1, and so on.

And in every case, we define which is the next state of the sequential circuit.

As it's a Moore model, the output table has as many rows as internal states.

The number of rows, in

general, is the number

of states, multiplied

by the number of input value

combinations.

As regards the preceding quiz, the correct solutions are 2 and 5.

Why?

They are three states and there is

only one input signal X, so there are

two input value combinations,

so that the number of values is six.

And as regards the number of columns,

there are three columns, because there is one

column that corresponds to the state, the current state,

another one to the input X and the third one that corresponds to the next

state.

And finally, as it is

a Mealy machine,

the next state table

and the output table have the same number of rows and columns.

Summary.

We have defined exhaustive

functional specification of sequential machines.

For that the main concept is that of state transition graph.

It has been used (or it is used) to define both Moore and Mealy machines,

and another way to specify the

sequential circuit function is to use next state tables and output

tables.

Explore our Catalog

Join for free and get personalized recommendations, updates and offers.

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.

© 2019 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play