welcome back lets take a look at faster multipliers namely an order log n square multiplier so

this is fairly simple to construct so ah lets consider an n bit multiplier and n bit multiplicand

so if you write the multiplier and the multiplicand multiply here and the multiplicand here so

what we can do is we can construct n ah small n partial sums where reconstructing is partial

sum is very simple and also it can be done in parallel so whenever we have a one we write

ah the multiplicand as is if you have zero we just writes zeroes and every partial sum

is offset by one position to the left as compared to the partial sum before it so if you are

multiplying n bits will have n partial sums small n mind yo

so all and all of these partial sums can be generated in parallel so this partial sum

can be generated simultaneously with this which can be generated simultaneously with

this so generating all the partial since is very easy it takes a constant amount of time

so after that we need to add n numbers all right so for adding n numbers what we can

do is we can have a tree of adders so we can add the first and second here we can add the

third and fourth numbers here the n minus two th and then the n minus three th numbers

here and ah

so similarly we can have a tree of adders so ah if we take a look at the sizes of the

numbers the first partial sum is n bits long and ah the last partial sum is two n minus

one ah bits law rights so this is n over here and n minus one over here n minus one zeroes

so at each level adding even two n ah you know even numbers with two one bits with take

order of log two n time which is the same as order of log n time because we ignore constants

and even the base of the log is not important so after that we have ah log n levels right

because in each level we reduce the number of ah numbers that we need to add by a factor

of two so now if we we realize that we have log n levels and each level takes maximum

of log of two n time because they two n bit numbers which is the same as log n because

we have always ignore constance in our work

so the total time taken is the number of levels write the number of levels multiplied with

the time per level which is log n times log n which is order of log n square so this is

the complexity with a new multiply that we have and this is significantly better than

are previous complexity [vocalized noise] which was order of n log n right so log n

square is much much better than n log n so this is a [far/faster] faster multiplier in

that sense but we can do better we can do much better as it turns out so before we discuss

how we can do better it is important for me ah to mention ah that there is a new kind

of device that we should use we can use and we have to use its a carry save adder so what

they carry carry save adder does is that ah it takes three numbers a b and c and it generates

two numbers d and e such that a plus b plus c is equal to d plus e so essentially it takes

three inputs which are the three numbers and it produces two numbers is output such that

the sum of d and e in this case is a same as the sum of a plus b plus c so the way that

we can do it is like this so ah lets consider a one bit carry save adder or a c s a adder

so let us add three bits a b and c such that a plus b plus c is equal to two d plus c so

d and e are also single bits and this can be done so i will tell you why this can be

done so let us consider you know ah the smallest value is the a b and c and largest values

so the smallest values are zero zero and zero so we will have d is zero where the sum is

zero and we will have e is zero if we consider the largest values which are one one and one

then the sum is one plus one plus one three which is one one which is pretty much equal

to two times one plus one

so in this case d is one and e is one so what we can do is that if we add a plus b plus

c right so sincere adding three one bit numbers the potential output right can be a two bit

number as we just saw in this case if he lets say we can you know conveniently set so in

the two bit number ah the left bit is a carry bit and the right bit is the sum bit we said

this bit to d and this bit to e then the value of this number would be equal to two d plus

e which is exactly what we need so ah what we says that in the case of one bit c s a

adder d and e ah can be in a computed as follows that d can be the carry bit right the more

significant bit and e can be the sum bit which is the less significant bit the lesser ah

significant bit in that sense so are the

so let me just explain once again if you are adding three one bit numbers a b and c the

smallest value is zero and a largest value is one plus one plus one which is three which

is one one so the final result will fit in two bits if i keep the two bits over here

let me do one thing so let me call the sum bit which is this bit as e and let me call

the carry bit which is the most significant bit is d so as we can see the final result

can also be expressed as two d plus e which is exactly what we want to do right this is

exactly what we want to do so we basically have a plus b plus c is equal to two d plus

e

so if now if i take a look at the previous diagram what i have done is i have taken three

one bit numbers in produce two numbers with two d can be thought as capital d and small

we can be thought as thought as capital e so basically produce two numbers is a sum

of these two is equal to the sum of the these three now lets do this for more bits right

at the moment a b and c where only one bits each so lets consider wider versions of a

b and c so let us do a little bit of algebra to ah compute the two numbers to compute two

numbers d and e such that a plus b plus c is equal to d d plus e so way the way that

we will do it is that we will use the same logic that was used here and they will just

ah extend our results

so let us express a as a sum of ah you know its bit so any number a can be a expressed

as so lets me consider a right the let the bits in a b a one to a n so lets let the number

a be a n to a one so this can be expressed as

this number here ah is a similarly ah we can express b in the same way as a sum of parts

of two and each part is multiplied with the corresponding bit of b and we can do the similar

things the c then what we can do is we can group all the terms together as a i plus b

i plus c i and multiply them it two raise to the power i minus one so what we have seen

in the previous result for one bit this can be expresses two times two d i plus e i ah

times two to the power i minus one you know this is something that exactly we have seen

here so we can do the same you know the same thing sum of three bits is the same as sum

of two numbers once we do the same we can ah then so so this since you are seen in the

previous slide slide number seventy six i am not repeating once you have done this again

we can break up this expression over here so we will have two terms ah i equal to one

and ah two n d i times to the power i so this is one binary number rights which we can treat

as d and this is one more number which we can treat as e right so what we see here is

that we have replaced the sum of a of a and b and c a plus b plus c as two numbers d and

e rights so let me just get rid of the ink and you will be able to see it better or computing

d and e is also very easy ah the reason computing it is very easy is that we take ah so in parallel

we consider so since is hardware everything is parallel so we considered the corresponding

i th bit ah we add them so we get this d and e where e is the sum bit as we have seen just

before in the previous slide ah sorry yeah e is the sum bit and d is the carry bit rights

so as we have seen here we just add them up ah then ah all that we need to do is that

so so actually what we can do is that in a here we can take the two out and this written

d i times two i minus one so this is one binary number which is composed entirely out of the

sum bits where we by after adding individual bits and this is one more binary number which

is composed entirely out of the carry bits right carry that is obtained by adding the

three bits at the same positions so ones we get e e is as is but ones you get this number

which is left shift multiplied by two which means left shift it by one position and we

get the number d

so essentially computing both d and e can be done very quickly in constant time or an

order one time and the way it is done is that we consider the i th bit of all three numbers

a b and c we add three one bit numbers this can be done in parallel so will get a sum

bit and carry bit so we from one number just with the some bits of all the you know individual

sums right and one more number with the carry bits that we obtained by adding all triplets

of numbers right of the form a i b i and c i and then we just take the number that we

get and left shifted by one position which is to effect this multiplication by two and

one number becomes d and the other number becomes e

so this can be done ah so this particular step of extracting the i th bit adding the

three i th bit getting d i and e i all of this can be done in parallel so this takes

constant time then forming the number with these bits also takes constant time and left

shifting also takes constant time so its not an issue right by one position so thats a

reason getting d plus e from a plus b plus c the entire operation is a constant time

operation so i just summary of what we just discussed how do we generate d and e well

we add all the corresponding sets of bits a i b i and c i independently right simultaneously

independently and simultaneously

we said d i to the carry bit produced by adding a i b i and c i and we said e i to the sum

bit produced by adding a i b i and c i so since all the operations are done in parallel

it takes order of one time so lets now discuss the wallace tree multiplier the idea is like

this that we generate n partial sums so this as we have seen in the previous example can

be done very quickly so this can be done in order of one time where we generate the n

partial sums how do we do this we take a look at each bit in the multiplier if it is one

the partial sum is the multiplicand of course shifted by a certain number of positions to

the left otherwise the partial sum is zero that is the exactly what we do if the i th

bit in the multiplier is zero the partial sum is zero p i is zero otherwise that p i

is the multiplicand left shifted by i minus one positions if the i th bit in the multiplier

is one so this can be done in parallel once we have n partial sums we can use a tree based

adder ah to ah affect the multiplication the way this is done is like this that we have

a similar tree ah as we had in the log n square multiplier ah so in this case ah what we do

is that we divider n partial sums into groups of three we have a carry save adder c s a

adder that takes in three inputs and that produces two outputs

so this adder produces two outputs and then the next adder one output is sent here and

one more adder is send to another carry save adder which takes two outputs from here and

ah the two outputs from the next ah partial sum adder rights from the next c s a carry

save adder so in this case if you have ah so basically each ah carry save adder here

is decreasing the number of ah inputs by three by two right so if there are ah three x inputs

here there are two x inputs in the next level so what we do is that we create a tree of

adders where we start with the partial sums and keep on adding them so recall that the

carry save adder takes three inputs and produces two outputs where the sum of the outputs is

the same as the sum of the inputs then what we do is that we keep on adding levels till

we finally have a case where we have only two outputs and a sum of these two if the

sum of all the partial sums

so the approximate number of levels that we will required is order of log of n to the

base three by two why three by two it is three by two because that every level where decreasing

the number of partial sums by a factor of three by two so we are just adding and so

ultimately ah we will reach a point for the sum of all the partial sums is just some of

these two numbers ones we of two numbers we can use a regular carry look ahead adder which

again takes in order log n time to add these two numbers so these two numbers will be much

larger and the they will have [vocalized noise] two n bits so thats ok the complexity relation

still holds and then will get the final product

so lets now compute the total time of this ah tree of c s a adders which is also called

a wallace tree multiplier so what we have is since we have the does you know tree over

here the tree has log off n to the base three by two levels and each level takes order one

time because one c s a adder runs in order one time so the total time that is required

is order of log of n to the base three by two which is the same as orders of log of

n and the reason being at the base of log does not matter because in a log to any base

and log to any other base the related via constant factors so those constant can be

ignored so once we have order of log n levels in the time per level is order one the total

time required to compute these two numbers lets call them x and y

so here ah what we have is x plus y is the sum of all the partial sums

and the sum of all the partial sums is essentially the product the result of the multiplication

which essentially we are producing two numbers ah whose sum is the final product final product

p so first thing that we do is be add this n partial sums to come up with two numbers

x and y say that x plus y is equal to p one ah till p n via ah a tree of carry save adders

and each carry save adder takes order one time and since we have log n such levels the

total time is log n and finally we need to add x and y with a carry look ahead adder

which again takes log n time so as we can see the final result we can get in order of

log n time

so this is the fastest possible multiplier and this is very very commonly and frequently

used in commercial circuits so as you can see this is very fast and the reason it is

fast is basically because of this carry save adder right in a had we not had the carry

save adder it would have been difficult but because we have this carry save adder which

is a very fast unit which can taken three inputs and produce two outputs for the sum

of the two outputs is the same as the sum of three inputs

ah we are quickly we know we can quickly reduce the sum of n numbers to sum of only two numbers

within log n time and then we add the two numbers we get the final product which is

the result of the multiplication so we have achieved our goal of having a log n time multiplier

so this slide only summarizes what we have discussed just a quick recap use an array

of c s a adders to add three numbers to produce two numbers so we reduce the set of numbers

by two third [ever/every] every level or divided by three by two after of log n to the base

three by two level so left to the only two numbers we use a carry look ahead adders to

add them so this takes log n time so the total time as a result is log n

so against the time complexity is log n this so i am skipping this slide because you have

already discuss the content all right so what have we done

what we have done is that we have focused on addition and multiplication in this ah

you know in the last three lectures so now will move to other things will move to division

floating point addition floating point multiplication and floating point division so ah because

this was a long chapter i divided the slides into two ah sub slides where two set up sub

slides so one is chapter seven part one and you know so you will find one slide as chapter

seven part one and other is chapter seven part two so what will do is when move to the

next slide set which is part two so will discuss these four topics in part two and ah so the

current part which is part one is over