[MUSIC]
In our preceding lesson we have commented
the relation between algorithms and combinational circuits.
Such a relation also exists between algorithms and sequential circuits.
The relation between algorithms and digital circuits
is one of the bases of this course.
Actually, some systems are sequential by nature, which is the case of systems
including an explicit or an implicit reference to successive time intervals,
and several examples have been seen before:
for example, circuits that generate sequences, or circuits that detect
some specific sequences, or circuits that control sequences of events.
But algorithms without any time reference
can also be implemented by sequential circuits.
Let us see a first example. We are going
to specify the working of a circuit that computes
the integer square root of a natural number X using
for that what we could call the "naive algorithm".
It consists of computing all pair (R, S)
such that S is the square of R+1.
For that we can use this relation. Thus, given R
and S such that S is equal to the square of R+1 (for example
if R = 2, R+1 is 3, and the square of
R+1 is 9), then in function of R and S we compute the next value of R,
that is R+1, and the next value of S, that is to say
R + 2 square, and then the corresponding algorithm is this one.
This computation is the body of a loop, loop controlled by this condition
that means that as long as S is smaller
than or equal to X, then we execute this loop.
As an example assume that X = 47.
Then the execution of this loop generates uccessively
number R equal to 0, S to 1, R equal to 1,
S equal to 4, and so on, up to the time when
for the first time the condition does not hold true
because 49 is greater than 47.
And the conclusion is that the square root (the
integer square root) of 47 is equal to 6.
A fiirst comment: this is obviously not a good
algorithm as the number of steps is equal to
the square root itself.
That means that for great values of X, X of the order of 2**n, the number of
steps is of the order of the square root of
2**n. It is used just for didactic purposes.
Then, if we have this algorithm, with a loop,
the first idea is an iterative combinational circuit.
For that, as we don't know in advance how many times the loop will be executed,
we modified the algorithm and say that once the condition
stops holding true, the value of S and R won't change any more.
So, if the condition holds true, then we execute
the two operations that we have seen before, but if the condition doesn't
hold true then the new value of S is the current value
of S, and the same for R. Then the component, this component,
executes this loop body
and the connections between components correspond to this instruction,
that is to say, the next value of S,
the output of this circuit, is the current value
of S, that is to say, the input of
the next circuit, and the same for the other input.
Then, with this configuration, the first output of the circuit computes
either number i (if the component is component number i) or the square root.
Now,
what is the number of components in this
iIterative circuit?
We know that the number of step is equal to the square root of X.
Then as X is smaller than 2**n, and its
square root is smaller than the square root of 2**n,
the number of steps is of the order (the maximum number
of steps) is the square root of 2**n.
That means that (an example)
if we are computing the square root of numbers with 32 bits, the
number of steps could be as large as 2 to the power 16,
that is a number greater than 65,000 components.
So, this circuit in this case would have more
than 65,000 components, obviously a too large number of components.
A better idea is Sequential Implementation.
We know that combinational circuits implement functions. Sequential circuits
include a combinational circuit so they also implement functions.
But what else does implement a sequential system?
Basically two things.
Memory and time partition thanks to the synchronization external signal.
Then we could associate the memory elements to variable
R And S, and partition the time into intervals,
and assign the time intervals to each operation, or to each group of operations.
For example, during the first time interval, we
could initialize the values of variables R and S.
Then during the second time interval, the third time interval, and
so on, we could execute those operations.
Then we could also add a new variable END used here and here.
And, in this way, we get the following algorithm,
that is to say: we initialize the variables R and S;
as long as condition S lower than or equal to X, we execute this set of
operation, and the END variable is equal to "false";
once the condition doesn't hold any more, then the values of
S and R wouldn't change any more, and the variable END will be equal to "true".
The synchronization input is used (here or here) to modify
the values of R and S, replacing the value of
S by the next value of S and the value of R by the next value of
R, as they are computed by the algorithm and thus by the combinational circuit.
So, we get the following sequential circuit that
consists of a combinational circuit and the memory.
The memory stores variables R and S, and the
combinational circuit computes the next values of R and S.
So it's a sequential circuit whose internal state
is constituted by the values of R and S.
Observe that the corresponding state transition graph of this sequential
circuit would include as many vertices as pairs (R, S),
and for every vertex as many edges as values of X.
That means a huge number of vertices and a huge number of edges.
Obviously not a good way to specify the circuit.
Now, some comments about algorithm implementation,
either by means of a combinational circuit
or by means of a sequential circuit.
