Sequential systems

Combination system: The outputs at any instant of time are functions only of the input at that time.
Sequential system: The output at time t is a function of the input at time t , the output at time t-1 and the internal state.

Memory device:

•  Zi – output: Zi = fi(x(0),x(1),.....x(n-1),y(0),.....,y(n-1))
• Xi – input.
•  present state: {y(0), y(1), ...... , y(k-1)}
• next state: {Y(0), Y(1), ...... , Y(k-1)} such that Y(i) = gi(x(0),x(1),.....x(n-1),y(0),.....,y(n-1))
Representation of sequential circuits
• Boolean functions
• State diagram
• State table
• Timing diagram
Moore and Mealy Machine Design Procedure   ( Further reading)
There are two basic ways to organize a clocked sequential network:
• Moore machine: The outputs depend only on the present state. The outputs are computed by a combinational logic block whose only inputs are the flip-flops' state outputs. The outputs change synchronously with the state transition and the clock edge.

• Mealy machine: The outputs depend on the present state and the present value of the inputs.

The outputs can change immediately after a change at the inputs, independent of the clock. A Mealy machine constructed in this fashion has asynchronous -outputs.

Example: Sequential system that detects a sequence of 1111:

STEP 1:state diagram – Mealy circuit
The next state depends on the input and the present state.

Non overlapping detection:

Overlapping detection:

STEP 2:State table.

Converting the state diagram into a state table: (Overlapping detection)
It contains present state (p.s) and next state inputs (x=1 or x=0).

 p.s. n.s. x=0 n.s. x=1 a a/0 b/0 b a/0 c/0 c a/0 d/0 d a/0 d/1

STEP 3:STATE REDUCTION.
Definition: State Si is equivalent to state Sj if and only if for every input combination:

• The output of Si is equivalent to the output of Sj
• The next state of Si is equivalent to the next state of Sj
State equivalence is an equivalence relation since the following properties can be verified:
• Reflexivity: Si = Si for any state.
• Symmetry: if Si = Sj then Sj = Si.

• Transitivity: if Si = Sj and Sj = Sk, then we are quaranteed without even checking that Si = Sk (and, therefore, Si = Sj = Sk).

Reduction of completely specified state tables:
Example 1: reduce the state table

 p.s. x=0 x=1 a c/0 b/1 b d/0 b/1 c a/1 d/0 d b/1 c/0

(1) a = b if c = d and b = b ==> a = b if c = d
(2) c = d if a = b and c = d ==> c = d if a = b
From (1) and (2) we can conclude that a = b and c = d.

The reduced state table:

A = {a,b}
B = {c,d}

 p.s. x = 0 x = 1 A B/0 A/1 B A/1 B/0

Example 2:

 p.s. x = 0 x = 1 a b/1 h/1 b f/1 d/1 c d/0 e/1 d c/0 f/1 e d/1 c/1 f c/1 c/1 g c/1 d/1 h c/0 a/1

Implication table:

----------
b    (b,f)
(d,h)
x
-----------------
c
x      x
------------------------
d                  (c,d)
x      x    (e,f)
eq
------------------------------
e    (b,d)  (d,f)
(c,h)  (c,d)    x      x
x      x
--------------------------------------
f    (b,c)  (c,f)                (c,d)
(c,h)  (c,d)    x      x     eq
x      x
-------------------------------------------------
g    (b,c)  (c,f)                 (c,d)   (c,d)
(d,h)    x      x      x       eq     eq
x
-------------------------------------------------------
h                   (c,d)  (a,f)
x       x    (a,e)    x      x       x       x
x
--------------------------------------------------------
a       b      c     d       e       f       g

For example:
• c and f are not equivalent. (Writing x in their cell).
• g and b are equivalent iff c and f are identical. (we writh (c,f) in the gb cell). Cell cf contain x so we write x in gb.
The sets of equivalent pairs:{a} {b} {c,d} {e,f,g} {h}
Naming the sets: A = {a}  B = {b}  C = {c,d}  D = {e,f,g}  E = {h}

The reduced state table:

 p.s. x=0 x=1 A B/1 E/1 B D/1 C/1 C C/0 D/1 D C/1 C/1 E C/0 A/1

example 3: Reduction in the division method:

At the beginning all the states are at the same equivalence class.Now  we start to separate states which are not equivalent to the others.

F is not equivalent to the others:

x=0        x=1
-------------------------------
A1        B1/0      C1/0
B1        D1/0      E1/0
C1        G1 /0     E1/0
D1        H1/0      F2/0
E1        G1 /0     A1/0
F2        G1 /1     A1/0
G1        D1/0      C1/0
H1        H1/0       A1/0
at the end:
x=0        x=1
-------------------------------
A1        B4/0      C1/0
B4        D3/0      E1/0
C1        G4 /0     E1/0
D3        H5/0      F2/0
E1        G4 /0     A1/0
F2        G4 /1     A1/0
G4        D3/0      C1/0
H5        H5/0       A1/0

The classes are:
a = (A,C,E)    b = (B,G)   c = (D)   d = (F)   e = (H)

Step 4: Logical implementation. (detection overlapping  sequence of 1111)

Determination of logical states

a : y0= 0 y1= 0
b : y0= 0 y1= 1
c : y0= 1 y1= 0
d : y0= 1 y1= 1

y0  y1     x    Y0  Y1    z
---------------------------------
0      0     0     0     0     0
0      0     1     0     1     0
0      1     0     0     0     0
0      1     1     1     0     0
1      0     0     0     0     0
1      0     1     1     1     0
1      1     0     0     0     0
1      1     1     1     1     1

The implementation:

Y0 = x y1 + x y0 = x ( y0 + y1)
Y1 = y1' x + y0 y1 x = x (y0 + y1')
z = y0 y1 x