1:00

an interative circuit, made up of n 1-bit adders.

1-bit adders are generally called "full adders".

The circuit computes X plus

Y plus an initial CARRY,

and the result, S is an (n+1)-bit

number, whose most significant

bit is the output CARRY of the last cell of

the last full adder. Second basic operation,

subtraction. Given to number X and Y, n-bit

numbers, and an initial BORROW, we want to compute

the difference X minus Y minus BORROW. In this case,

the result is smaller than or equal to 2**n - 1,

which is the case, when X has its maximum value 2**n - 1

and when both Y and the BORROW and are equal to 0.

But in this case, the result could also be negative.

And the minimum value of the difference is -2**n,

the value that we get when X is equal

to 0, Y is equal to the maximum value 2**n - 1

and when the BORROW is equal to 1.

Then, how can we represent D? If D is non-negative,

it's an n-bit number that can be

representated in binary, and if D

is negative but greater than or equal to -2**n

then it can be represented with an additional

bit whose weight is negative, that is to say that

Dn has a weight equal to -2**n.

3:14

Then, how works the classical pencil and paper

method to compute the difference between two numbers:

at each step, we are going to compute two bits,

a difference bit and a borrow,

an output borrow bit. Actually, the real value

of the difference can be equal to

1, 0, -1 or -2. Then,

we define the borrow, an output borrow,

and a bit d of the difference. If the

result, the real result, is 1 no problem: there is no borrow, and d =1.

If the result is 0, the same: dout = 0

and d = 0. Then, if the result is

negative, first case: the result is -1; then you

could write or say that -1 = -2 + 1.

So, we will choose a bit of the difference equals 1,

but then transmit the borrow to the next step,

with a weight equal to the present weight multiplied by 2,

so that in this case the borrow

- the output borrow - will be equal to 1. You must think

that this borrow actually has a negative weight.

This is 1 and this is -1 with the weight equal to 2.

It's the same as -2.

In the same way, in the case where the real result is -2, we will say that -2

is -2 + 0. So, here the bit

of the difference is 0, and the borrow is equal

to 1, actually it is a negative weight.

Observe now that d is equal to the real

difference computed modulo 2,

because when the real result is odd,

the corresponding bit is 1 and when the

real result is even, the corresponding

bit is 0. And the output borrow

bit is equal to 0, when the real

result is non-negative, and equal to 1 when the real result

is negative. Another comment: the value of

x - y - bin modulo 2 is exactly

the same as the value of x + y + bin modulo 2,

because modulo 2, -1 is the same as 1.

Both numbers are

odd numbers. Let us see an example:

First we compute 12 (decimal 12) minus 9; then

we compute in a step by step way: 0 minus 1 is equal

to -1. Then the difference bit is 1

and the borrow bit is also 1;

0 minus 0 minus 1 once again is equal to minus 1.

Then, here the difference bit is 1 and the borrow bit

is 1, with a negative weight;

next step: 1 - 1 = 0; next step: 1 - 1 = 0,

so that the result is this one (in decimal 3).

Now, let us compute, 9 minus 12: 1 - 0 = 1;

0 - 0 = 0; 0 - 1 is -1; then

here, the difference bit is 1 and there

is a borrow to the next step; 1 - 1 - 1 = -1;

once again, difference bit

equal to 1 and borrow equal to -1, so that

the result is this one, but now the first 1

has a negative weight, and this number

is equal to minus 16 plus 8

plus 4 plus 1 and

this is minus 3. This type of

representation is called

2's complement representation

of the negative number.

This is the algorithm: it's an iteration (a loop)

where at each step, we compute a difference bit,

the modulo 2 sum of the three incoming bits,

two bits of the operands and one borrow input,

and we compute the sign of the difference

x(i) minus y(i) minus b(i). Here

is the algorithm that we can modify. We can

replace this modular 2 sum by the

exclusive or sum of x(i), y(i) and b(i),

9:31

exactly in the same way as in the adders that we have seen

before and, as regards the borrow, the

computation of the output borrow, we see that it is

equal to 1 when (three cases): the bit

of x is 0 and the bit of y is 1, or when

the bit of x is 0 and the input borrow is 1,

or when both the bit of y and the input

borrow are equal to 1. In all of those cases,

the result of this operation is negative so that the borrow

must be equal to 1. The corresponding circuit is

this one: an iterative one made up on n identical

components, 1-bit subtractors, that are also called

full subtractors, and every component, every full

subtractor implements those Boolean functions.

11:14

some absolute value (the magnitude of the difference).

Then, the proposed method is quite simple.

Compute, at the same time, the difference x - y and y - x.

If x - y is non-negative, then the sign

in equal to 0 and the result is this one.

In the contrary case,

if x - y is negative, then

y - x will be non-negative, and the

sign bit will be equal to 1. Here

is a possible solution: we use two

subtractors, that work in parallel; one computes x - y

and the other one computes y - x.

If the sign of x - y is 0, then the sign of

D is equal to 0, and we select as a magnitude

14:22

Actually, the computation of the partial products

is very easy: the multiplication

of X by bit (for example) Y(2) along

can be done with a set of AND gates. Here you have

the bits of X, here is the bit Y(i), Y(2) for example.

and then we get, at the output of the AND gates,

all the bits of X multiplied by Y(2) (for example).

And the multiplication

by the power of 2 amounts to adding some

number of 0's to the right of the corresponding number.

To multiply by 2 in binary is as multiplying by 10 in decimal;

it is just a matter of adding a 0 on the right side of the number.

Let us see an example: assume that we define

X = 101101 and Y = to 1011. Then,

first partial product: 1 multiplied by X is equal to X.

16:05

and, finally, 1 multiplied by X is 101101 with three 0's.

So, it's very easy to compute all those artial products, and then,

it's necessary to compute

the sum of all those products, and we get finally

the result of the multiplication. Thus, the

algorithm is this one: at each step (it's an iteration once

again) at each step we must compute the

sum of some value ACC plus the product of X

by a bit of the second operator Y, and multiply

this product by some power of 2,

and we already know that this amounts to shifting

or to adding 0's to the right of the number.

And the result of

this computation, is the new value of the variable ACC.

20:11

In order that the result is obtained

with an accuracy of p fractionary bits,

this computation must be realized with a precision of p + k

fractionary bits. This definition is

equivalent to this one: if we divided here by

Y, we get that X divided by Y is equal

to Q (the quotient) plus R

divided by Y, where the quotient is a multiple of

2**(-p), and where the error

(the error is the difference between the real value of the division of X

by Y and the quotient) this difference

is R divided by Y and, according to this condition, is

smaller than 2**(-p)).

21:42

the preceding remainder and the divisor.

If the difference is negative, then the corresponding quotient bit is 0

and the new remainder is 2 times the preceding one,

but if d is non-negative, then the quotient is 1, and the

new remainder is the difference. Then we get the result under this form:

Q is equal to the number, expressed in binary with the set

of quotient bits that have been computed, multiplied by

2**(-p). In other words, in binary Q is

0.q(1) q(2) ··· q(p)

and R is the last

obtained remainder when i is

equal to p, also multiplied by

this negative power.

22:57

Let us see an example. Assume that X is equal to 21,

Y equal 35, and we want an

accuracy of 6 factional units. Then we

compute, 2 times the remainder: 2 times 21

is equal to 42, is greater than Y. So

I can write that 42 is equal to 35 plus 7.

First quotient bit 1 and the new remainder is 7.

Next step: 2 times the preceding remainder, 2 times 7,

14, is smaller than the divisor;

so I can write that 14 is 0 times 35, plus

the difference 14, and we follow up: 2 times 14, 28,

is smaller than 35, so I write that 2 times 14 is

equal to 0 times 35 plus 28 and so on.

24:40

it's written under this form, that is to

say 100110, but with 0. here on the left side.

The remainder is 14

multiply by 2 to the power -6. In other words, 14

divided by 64. In binary: this number,

and you can check that, actually,

Q times the divisor, 35, plus

the remainder divided by 64 is

equal to 21 and that the remainder

satisfies this condition.

Corresponding circuit: once again

is an iterative circuit; at each step

we must compute a bit of the quotient

and a new remainder. It's

very easy: we must multiply the preceding remainder

by 2; that means to add

a 0 on the right side of this number, and then to compute the difference

between 2R and Y; if the sign is equal to 0,

that means that 2R is greater than or equal (that the result is non-negative)

in which case the quotient bit is equal to 1,

and the new value of the remainder is the difference.

In the other case, if the sign bit of this difference is equal to 1,

it means that the difference is negative, then the quotient bit is equal to 0

and the new value of the remainder is the preceeding value multiply by 2.

And that's all. Summary of this lesson:

We have described circuits that execute the

basic arithmetic operations, that means addition, subtraction,

multiplication and division, with natural operands

(non-negative integers), and we have given some information

about 2's complement representation of negative numbers.

[BLANK_AUDIO]