‫Welcome to the booth algorithm explained lecture in this lecture I'll explain how bous algorithm works
‫and how to design one in VHDL.
‫What is buth hour.
‫Well boose algorithm is a multiplication algorithm that is used to multiply two signed binary numbers
‫in two's complement format.
‫What is a band to this.
‫This prevents you from having to use the embedded multipliers or DSP slices located on the actual FPGA
‫when you're typically designing a signal processing system or any other type of interface with your
‫FPGA and you need to do the multiplication sort of operation one you can use the embedded multipliers
‫or the DSP slices.
‫However if you're getting to a point where you're running out of those because you only have so many
‫you can design your own.
‫And that's what we'll be doing with this algorithm will show how you can perform this multiplication
‫without actually having to use the on chip resources dedicated for that.
‫And this algorithm includes shifting addition to perform the multiplication the set up for buth algorithm.
‫We have an input multiplier and multiple kand that are.
‫And this long and this end refers to a generic or an option that allows you when you're creating a design
‫if you want it to be forbit 8 bit 16 32 so on and so forth it just makes your design a little more customizable
‫and to figure all the output product is two bits.
‫So whatever you select that end to be 8 bits your output your product is going to be 16 bits and we
‫have three registers we'll be using a S and P or two and plus one incise the leftmost and it's of a
‫are set to the multiplier the end plus one rightmost bits are set to 0 the leftmost and bits of S are
‫set to the two s complement of the multiplier.
‫The end plus 1 rightmost bits are set to zero the leftmost and bits of P are set to zero the bits from
‫an to 1 are set to the multiplicand and zero is set to zero.
‫Now after this set up we have certain steps we want to do to implement this algorithm.
‫So we're going to loop through an number of times having many bits wide.
‫We are we're in a loop that many different times and every time we loop through we're going to add a
‫to.
‫If the two least inefficient bits of P are 0 1 we're going to add s to p at the two least inefficient
‫bits of P or 1 0 otherwise we're going to do nothing.
‫And then you want a sign shift p.
‫My one bit to the right.
‫And then after we loop through end times the leftmost to end it's a p that is the product or Preuss
‫multiplication.
‫So we have a state machine let's just talk about that really quick.
‫We have four different states.
‫We have our initializations state our load state our right shift state in our Done state and our knit
‫state is when we're setting up or waiting to start the multiplication.
‫So once we get a start signal we'll have our start count go to one.
‫We're on a load.
‫We're going to take our inputs for a multiplier and multiplicand and then we're going to start performing
‫our right shifting them we're going to keep right shifting in the right state until our count is equal
‫to max count.
‫And once we account to max count we'll go to the Done state where we're on a sit in the down state until
‫star is equal to zero.
‫Then we'll go to the end state and wait for our next start count signal and it is keep looping through
‫one multiplication as many number of times until we're the person turns every day off or the design
‫is designed is done.
‫So for example let's have a five bit number.
‫Our multiplier is a negative 12 and represent that and by an error with two's complement is 1 0 1 0
‫0 or multiplication.
‫We're in a set to 13 and in two's complement binary is 0 1 1 0 1.
‫So just as a sanity check we know that negative 12 times 13 is equal to negative 156.
‫So to loop through our boost algorithm we know for instance 5 bits we're going to have to loop through
‫five times.
‫So we have step 0 5.
‫We're looping through 1 2 3 4 5 0 like our initialization set up state.
‫So our initialization state we set our multiplier with a register to the left most bits and then a rightless
‫bits we set to zero and we do the same thing with our multiple.
‫Can we put that in the s register then we have our p the product register where we copy the rightmost
‫bits the multiplication into the P and then as we loop through each step we're looking at those least
‫inefficient bits to determine if we're doing a product a P Plus R S registers or for doing a P plus
‫or a registers or from not doing anything.
‫And so if you loop through you can see that we're at 0 1 so far P plus S.
‫We're going to format that operation and then do a shift that are step 2 we're taking since we have
‫1 0.
‫We're doing a P Plus a and then a shift.
‫You can see our next.
‫We have a one in a 1.
‫So we're doing our P plus S and then a shift and then after that our fourth step we have a 0 1.
‫So we do a shift and then on our very first step we're doing a key Senay and then a shift and then you
‫can see our product register the two in bits 1 1 0 1 1 0 0 1 0 0 is the value of negative 156 and twos
‫complement form.
‫So that is how you perform this bous algorithm.
‫This is the example for a five bit.
‫And so we would do an 8 bit or 16 bit the registers a X and we were all just increase in size accordingly.
‫Now you understand how bous algorithm works.
‫Let's go get start implementing this on the board.