1
00:00:06,640 --> 00:00:12,340
‫Welcome to the booth algorithm explained lecture in this lecture I'll explain how bous algorithm works

2
00:00:12,460 --> 00:00:15,560
‫and how to design one in VHDL.

3
00:00:15,670 --> 00:00:17,350
‫What is buth hour.

4
00:00:17,620 --> 00:00:23,890
‫Well boose algorithm is a multiplication algorithm that is used to multiply two signed binary numbers

5
00:00:24,040 --> 00:00:26,560
‫in two's complement format.

6
00:00:26,560 --> 00:00:28,060
‫What is a band to this.

7
00:00:28,060 --> 00:00:34,810
‫This prevents you from having to use the embedded multipliers or DSP slices located on the actual FPGA

8
00:00:35,500 --> 00:00:41,170
‫when you're typically designing a signal processing system or any other type of interface with your

9
00:00:41,170 --> 00:00:47,020
‫FPGA and you need to do the multiplication sort of operation one you can use the embedded multipliers

10
00:00:47,140 --> 00:00:48,490
‫or the DSP slices.

11
00:00:48,490 --> 00:00:53,350
‫However if you're getting to a point where you're running out of those because you only have so many

12
00:00:53,740 --> 00:00:55,240
‫you can design your own.

13
00:00:55,260 --> 00:01:00,310
‫And that's what we'll be doing with this algorithm will show how you can perform this multiplication

14
00:01:00,370 --> 00:01:04,710
‫without actually having to use the on chip resources dedicated for that.

15
00:01:04,710 --> 00:01:14,200
‫And this algorithm includes shifting addition to perform the multiplication the set up for buth algorithm.

16
00:01:14,290 --> 00:01:18,030
‫We have an input multiplier and multiple kand that are.

17
00:01:18,040 --> 00:01:24,160
‫And this long and this end refers to a generic or an option that allows you when you're creating a design

18
00:01:24,160 --> 00:01:31,240
‫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

19
00:01:31,330 --> 00:01:35,790
‫and to figure all the output product is two bits.

20
00:01:35,830 --> 00:01:42,910
‫So whatever you select that end to be 8 bits your output your product is going to be 16 bits and we

21
00:01:42,910 --> 00:01:53,650
‫have three registers we'll be using a S and P or two and plus one incise the leftmost and it's of a

22
00:01:53,730 --> 00:02:02,500
‫are set to the multiplier the end plus one rightmost bits are set to 0 the leftmost and bits of S are

23
00:02:02,500 --> 00:02:06,140
‫set to the two s complement of the multiplier.

24
00:02:06,140 --> 00:02:14,620
‫The end plus 1 rightmost bits are set to zero the leftmost and bits of P are set to zero the bits from

25
00:02:14,720 --> 00:02:21,180
‫an to 1 are set to the multiplicand and zero is set to zero.

26
00:02:21,970 --> 00:02:27,790
‫Now after this set up we have certain steps we want to do to implement this algorithm.

27
00:02:28,000 --> 00:02:32,710
‫So we're going to loop through an number of times having many bits wide.

28
00:02:32,770 --> 00:02:38,350
‫We are we're in a loop that many different times and every time we loop through we're going to add a

29
00:02:38,350 --> 00:02:39,150
‫to.

30
00:02:39,370 --> 00:02:47,170
‫If the two least inefficient bits of P are 0 1 we're going to add s to p at the two least inefficient

31
00:02:47,170 --> 00:02:52,490
‫bits of P or 1 0 otherwise we're going to do nothing.

32
00:02:52,780 --> 00:02:54,870
‫And then you want a sign shift p.

33
00:02:54,960 --> 00:02:57,030
‫My one bit to the right.

34
00:02:57,420 --> 00:03:04,730
‫And then after we loop through end times the leftmost to end it's a p that is the product or Preuss

35
00:03:04,770 --> 00:03:06,680
‫multiplication.

36
00:03:06,960 --> 00:03:10,550
‫So we have a state machine let's just talk about that really quick.

37
00:03:10,590 --> 00:03:12,580
‫We have four different states.

38
00:03:12,660 --> 00:03:20,260
‫We have our initializations state our load state our right shift state in our Done state and our knit

39
00:03:20,310 --> 00:03:24,350
‫state is when we're setting up or waiting to start the multiplication.

40
00:03:24,480 --> 00:03:29,700
‫So once we get a start signal we'll have our start count go to one.

41
00:03:30,060 --> 00:03:30,960
‫We're on a load.

42
00:03:30,960 --> 00:03:36,750
‫We're going to take our inputs for a multiplier and multiplicand and then we're going to start performing

43
00:03:36,810 --> 00:03:43,980
‫our right shifting them we're going to keep right shifting in the right state until our count is equal

44
00:03:43,980 --> 00:03:45,310
‫to max count.

45
00:03:45,570 --> 00:03:52,440
‫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

46
00:03:52,590 --> 00:03:54,110
‫star is equal to zero.

47
00:03:54,300 --> 00:04:01,080
‫Then we'll go to the end state and wait for our next start count signal and it is keep looping through

48
00:04:01,460 --> 00:04:07,890
‫one multiplication as many number of times until we're the person turns every day off or the design

49
00:04:07,890 --> 00:04:09,190
‫is designed is done.

50
00:04:10,660 --> 00:04:14,030
‫So for example let's have a five bit number.

51
00:04:14,110 --> 00:04:23,170
‫Our multiplier is a negative 12 and represent that and by an error with two's complement is 1 0 1 0

52
00:04:23,170 --> 00:04:25,180
‫0 or multiplication.

53
00:04:25,240 --> 00:04:32,140
‫We're in a set to 13 and in two's complement binary is 0 1 1 0 1.

54
00:04:32,140 --> 00:04:40,190
‫So just as a sanity check we know that negative 12 times 13 is equal to negative 156.

55
00:04:40,190 --> 00:04:45,700
‫So to loop through our boost algorithm we know for instance 5 bits we're going to have to loop through

56
00:04:45,700 --> 00:04:46,880
‫five times.

57
00:04:46,900 --> 00:04:49,140
‫So we have step 0 5.

58
00:04:49,260 --> 00:04:54,950
‫We're looping through 1 2 3 4 5 0 like our initialization set up state.

59
00:04:55,140 --> 00:05:03,790
‫So our initialization state we set our multiplier with a register to the left most bits and then a rightless

60
00:05:03,790 --> 00:05:08,170
‫bits we set to zero and we do the same thing with our multiple.

61
00:05:08,170 --> 00:05:16,660
‫Can we put that in the s register then we have our p the product register where we copy the rightmost

62
00:05:16,660 --> 00:05:21,940
‫bits the multiplication into the P and then as we loop through each step we're looking at those least

63
00:05:21,950 --> 00:05:29,350
‫inefficient bits to determine if we're doing a product a P Plus R S registers or for doing a P plus

64
00:05:29,350 --> 00:05:32,260
‫or a registers or from not doing anything.

65
00:05:32,310 --> 00:05:37,740
‫And so if you loop through you can see that we're at 0 1 so far P plus S.

66
00:05:37,810 --> 00:05:43,030
‫We're going to format that operation and then do a shift that are step 2 we're taking since we have

67
00:05:43,030 --> 00:05:43,880
‫1 0.

68
00:05:43,900 --> 00:05:46,920
‫We're doing a P Plus a and then a shift.

69
00:05:47,300 --> 00:05:48,240
‫You can see our next.

70
00:05:48,240 --> 00:05:49,670
‫We have a one in a 1.

71
00:05:49,750 --> 00:05:55,850
‫So we're doing our P plus S and then a shift and then after that our fourth step we have a 0 1.

72
00:05:55,930 --> 00:06:03,340
‫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

73
00:06:03,340 --> 00:06:15,700
‫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

74
00:06:15,700 --> 00:06:16,930
‫complement form.

75
00:06:17,090 --> 00:06:19,770
‫So that is how you perform this bous algorithm.

76
00:06:19,810 --> 00:06:21,730
‫This is the example for a five bit.

77
00:06:21,730 --> 00:06:32,040
‫And so we would do an 8 bit or 16 bit the registers a X and we were all just increase in size accordingly.

78
00:06:32,890 --> 00:06:34,880
‫Now you understand how bous algorithm works.

79
00:06:34,900 --> 00:06:37,390
‫Let's go get start implementing this on the board.