[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.