Dies ist eine alte Version des Dokuments!

6. Sequential Logic

„I Know What You Did Last Cycle“

6.1 First Terminology

The most important term is the word state But what is a state? It is a unique situation, where the possible next steps (= possible next states), the inner behavior or the outputs are distinguishable from other situations. Here some practical examples:

• being happy or being sad, are two different states, since the inner behavior is different (this least often also to a different output). Similarly, an empty memory (or harddrive) is in a different state compared to an compared to a full one. Even a fresh deleted one is distingisable, since deletion

Sequential logic is used to describe logic cicruits which show internal states („stateful“), and therefore have at least one memory element (= flip-flop).

The following terminology is used in the upcoming explanations:

• The input vector $\vec{X}$ represents the $k$ inputs $X_0 ... X_{k-1}$
• The output vector $\vec{Y}$ represents the $l$ outputs $Y_0 ... Y_{l-1}$
• The state vector $\vec{Z}$ represents the $m$ inputs $Z_0 ... Z_{m-1}$
• The sign $(n)$ or $n$ marking the current point in time and therefore e.g. the current state $Z_0(n)$
• The sign $(n+1)$ or $n+1$ marking the next upcomming point in time and therefore e.g. the next state $Z_0(n+1)$
• Sequential logic circuits are also called Finite State Machines (FSM) or sometimes also shortened to „state machine“

The Abbildung 12 shows the different terms in an abstract diagram. The „current“ output values are here the values, which are shown after the delay time of the gates (about some nanoseconds).

The principle interior of the blackbox in Abbildung 12 was already shown in one practical application in the previous chapter: We saw, that we need the combination of an combinatorial logic and some storage components. Additionally, both have to be connected by feeding back some of the outputs back to the combinatorial logic. The output bits $\vec{Y}$ can result either from the combinatorial logic or the flip-flops. This is shown in Abbildung 13.

One simple example of a sequential logic is shown in Abbildung 4. There, the combnatorial logic is explicitely shown. Depending on the input $X$ the output $\vec{Y}$ shows an up-counting 2-bit value counting $0 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 0 \rightarrow ...$. This is a simple state machine which will be used in the net chapters

6.2 Classical State Machine Types

The up-counter in the previous sub-chapter was able to count from $0$ to $3$. But what can we do in order to count differently, like $ 7, 6, 1, 5$? In order to understand this, a simplier situation will be investigated. So, let's look how one can create a up-counter counting $1, 2, 3, 4$.

6.2.1 Moore Machine

The first idea might be to use what we already have: an up-counter, which faciliate 2 flip-flops in order to result into 2-bit output. The wanted new state machine needs 3 bits for the output, since the binary representation of our outputs are $%001$,$%010$,$%011$,$%100$.

An simple idea is to take the 2-bit up-counter and add an combinatorial logic in behind. This logic shall convert the 2-bit up-counter output $%00$ into $%001$, the $%01$ into $%010$, $%10$ into $%011$ and $%11$ into $%101$. This can be logic can be created by:

• writing down the truth table
• putting the values into a Karnaugh map
• extracting the formula with view onto the implicants
• generating the circuit with gates

When this is done, the result looks like Abbildung 5

This resembles a so called Moore Machine

6.2.2 Mealy Machine

When looking onto Abbildung 5 a bit more in detail, one can see, that the outputs $Y_0$ and $Y_1$ just equals output of the first combinatorial logic circuit. This is not surprising: the input logic circuit shows the $\vec{Z}(n+1)$ and this is for the counter always the stored value plus one, except when the maximum is reached.

With this information the state machine in Abbildung 5 can be simplified by using the outputs of the input circuit for $Y_0$ and $Y_1$. This is shown in Abbildung 6.

6.2.3 Medvedev Machine

The Abbildung 8 shows the principle differences in the architecture of the state machines.

6.3 State Diagram, State Transition Diagram

6.3.1 Motivation

The diagrams of different states are well known from physics for example the state diagram (or better: phase diagram) of water, where its three states are: solid ice, liquid water and gaseous steam. The possible state transitions are due to temperature increase or decrease.

In Abbildung 9 image (1) the states of water are shown on the temperature axis. When only the state transistions are relevant, the states are simplified to a circle, showing the state name and behaviour. The transitions are depict as arrows, where the needed condititon is written onto (See Abbildung 9 image (2) ). This diagram is called state transition diagram.

For matter not only the dimension „temperature“ is important, but also the „pressure“. The full phase diagram is shown in Abbildung 10 image (1). By this, another variable is available and more transistions. These can be drawn into the state transition diagram (Abbildung 10 image (2)).

6.3.2 Simple logic Example

In German, often one has to pay for entering the toilet. An example of such a entrance control system is shown in Abbildung 11. At this (artificial) example, one can pay either 50ct or 1€.
Once paid, the turnstile will release and one can enter. Once the turnstile was pushed the entrance is closed again.

The Abbildung 12 the state transition diagram is drawn.

• The two states are that (1) the turnstile is opened and one is able to go through and (2) the turnstile is closed and one cannot enter anymore.
• The transitions are given by the done actions: one can either insert a coin or push on the turnstile.

Important here are some additional considerations:

• For the state transition diagram one has to look for all possible transitions. So, also pushing a closed turnstile or inserting more coins have to taken into account.
• A state transition diagram is not complete without a legend and without an beginning/reset point. The reset point is given by an arrow with „reset“ written onto it

Out of this state transition diagram one can create a table-like representation, see Abbildung 13.

the inputs, outputs and states have to be encoded into binary, in order to investigate this table a bit more. How the binary value is connected to the outputs does not matter. We will choose the following coding:

• Encoding of the states: turnstile closed ≙ $Z=0$, turnstile opened ≙ $Z=1$,
• Encoding of the inputs: no coin inserted ≙ $Xc=0$, coin inserted ≙ $Xc=1$, turnstile not pushed ≙ $Xp=0$, turnstile pushed ≙ $Xp=1$,
• Encoding of the outputs: disallow entrance ≙ $Y=0$, allow entrance ≙ $Y=1$,

This table is shown in Abbildung 14 and is called state transition table.

Interestingly, the logic circuit for this state transition table was already part of the course: it is the RS flip-flop! When looking deeper onto the table in Abbildung 14 one can substitute $Xc$ with $S$ (as in Set) and $Xp$ with $R$ (as in Reset) to directly get the truthtable of the RS flip flop.

6.3.3 First Adaption for Up-Counter

In the previous sub-chapter (6.2) we had a look onto different implementations of an up counter and on this chapter the way to represent a state machine via a state transition diagram. So one question is: how does these up counter look like in the state transition diagram?

The Answer ist quite simple: there are 4 states, so 4 „circles“ are needed. These states need to have circular connections in order to get the wanted increase from $%00=0$, to $%01=1$, to $%10=2$, to $%11=3$ and then back to $%00=0$. The first state shall be $%00=0$, so after the reset the state machine will get entered there. Finally, the output vector is similar to the state vector. With a deeper look onto is: This is therefore in particular a Medvedev machine!

In Abbildung 15 both types of state machines are shown.

• In the Moore Machine the already seen „halving of the circle“ is used to show the distinct state vector in the upper half and the output vector in the lower half.
• In the Medvedev Machine only one value is written in the circle, since here the state vector is also the output vector.

The next step is to transform this into a up counter from $1...4$. For this simply the output has to be changed. This means the numbers in the „lower half of the circles“ have to be adapted (see in <imfref pic16>).

Looking on what we got, there is one part missing: the state machine does not have any input.. So the input vectors have to be added onto the transition (arrows). For an activateable counter, there only have to be one input $X$, which acts as an enable input.

Exercises