Skip to content
Solved Assignments

Analysis of Multiplication Algorithms and Boolean Function Optimization

Examines efficiency of multiplication algorithms and Boolean logic.

Preview 3 of 8 pages

See the first 3 pages exactly as they appear in the document.

  1. Page 1
    Read page 1 as text

    Analysis of Multiplication Algorithms and Boolean Function Optimization Q 3.14 ) Here in this algorithm let us assume that shifting and addition are two measure time consuming process so conditional statements can be ignored. FOR HARDWARE : As it is given that addition will always take place and for hardware shifting of both multiplier and multiplicand is possible in one step hence there are only two measure steps. So there are two measure steps and as each step consume 4 unit of time so there will be 8 unit of time consumed for every iteration. So irrespective to size of integer the algorithm will going to repeat itself 32 time so total time consumed for multiplication is 8*32 which is 256 unit of time. 4*(step 1a and shift step)*32 unit of time. Note: if we consider both conditional checking as time consuming step then total stem will be 4 and hence the time consumed will be more. If we assume that the number is 8 bit long hence we have to loop the calculation only 8 time and then time consumed will b 8*8 which is 64 unit. For Software : Addition is always going to take place and for software shifting of multiplicand and multiplier are two different steps and hence total measure time consuming steps are 3(addition + shift of multiplier + shift of multiplicand) . As one step consume 4 unit of time in one iteration three step will consume 3*4 unit of time . Irrespective to size of integer algorithm will repeat itself for 32 time. Hence total time consumed will be 4*(addition step+ shift of multiplier +shift of mul tiplicand) *32 w hich is equal to 384 unit of time . If conditional statement checking is assumed to be time consuming then there will be 5 steps for software and hence the time will increase. If we assume that the number is 8 bit long hence we have to loop the calculation only 8 time and then time consumed will b 12*8 which is 96 unit of time. Q 3.15) In approach there are 32 adders stacked vertically, Rather than use a single 32 - bit adder 32 times, this hardware β€œunrolls the loop” to use 32 adders. Each adder produces a 32 - bit sum and a carry out. The least significant bit is a bit of the product, and the carry out and the upper 31 bits of the sum are passed along to the next adder.

  2. Page 2
  3. Page 3
    Read page 3 as text

    The numbers are stored in 32 bit register and as number is 8bit all other bit are set to zero. Once the multiplication start it will end after completing 32 steps and we get product in product register. As each adder take 4 unit time there are total 32 adder hence total time consumed will be 32*4 = 128 unit. Note that for all higher bit of number which are 0 every time adder will work and add zero. If we assume that the number is 8 bit then we need only 8 adder and time taken will b 8*4 which is 32 unit. Q 3.16) In this approach in first step 16 adders are involved for each step the number of adders get halved. So in first step number of adder are 16 in second sep number of adder are 8 in third number of adder are 4 and in fourth number of adder are 2 and in last step only one adder is required. Total number of adder required are 31. Each adder consume 4 unit of time in computation hence total time required for 32 bit number multiplication is 31*4 = 124 unit of time. If we assume that the number is 8 bit long and hardware is optimized as per number then adder require in first step will be 4 in next step 2 and 1 in last. Hence total required 7 and total time consumed will be 7*4 = 28 unit of time. Additional Problem: Q1)Here the expression is : ( π‘Ž , 𝑏 , 𝑐 , 𝑑 ) = π‘Žπ‘ Μ… 𝑐 + 𝑐𝑑 + π‘Ž Μ… 𝑑 + 𝑏𝑑 . First convert all terms of expression into terms having 4literals. F= π‘Ž 𝑏 ΰ΄€ 𝑐 (d+ 𝑑 Μ… ) + cd(a+ π‘Ž ΰ΄€ )(b+ 𝑏 ΰ΄€ ) + π‘Ž ΰ΄€ 𝑑 (b+ 𝑏 ΰ΄€ )(c+ 𝑐 ΰ΄₯ ) + bd ( π‘Ž ΰ΄€ + π‘Ž )(c+ 𝑐 ΰ΄₯ ) F= π‘Ž 𝑏 ΰ΄€ cd + π‘Ž 𝑏 ΰ΄€ 𝑐 𝑑 Μ… + abcd + π‘Ž ΰ΄€ 𝑏𝑐𝑑 + π‘Ž 𝑏 ΰ΄€ 𝑐𝑑 + π‘Ž ΰ΄€ 𝑏 ΰ΄€ 𝑐𝑑 + π‘Ž ΰ΄€ 𝑏𝑐𝑑 + π‘Ž ΰ΄€ 𝑏 𝑐 ΰ΄₯ 𝑑 + π‘Ž ΰ΄€ 𝑏 ΰ΄€ 𝑐𝑑 + π‘Ž ΰ΄€ 𝑏 ΰ΄€ 𝑐 ΰ΄₯ 𝑑 +abcd + π‘Žπ‘ 𝑐 ΰ΄₯ 𝑑 + π‘Ž ΰ΄€ 𝑏𝑐𝑑 + π‘Ž ΰ΄€ 𝑏 𝑐 ΰ΄₯ 𝑑 Now removing all those terms which are appearing more than one time in expression: F= π‘Ž 𝑏 ΰ΄€ cd + π‘Ž 𝑏 ΰ΄€ 𝑐 𝑑 Μ… + π‘Ž ΰ΄€ 𝑏𝑐𝑑 + π‘Ž ΰ΄€ 𝑏 ΰ΄€ 𝑐𝑑 + π‘Ž ΰ΄€ 𝑏 𝑐 ΰ΄₯ 𝑑 + π‘Ž ΰ΄€ 𝑏 ΰ΄€ 𝑐 ΰ΄₯ 𝑑 +abcd + π‘Žπ‘ 𝑐 ΰ΄₯ 𝑑 K Map Representation of result is: CD 00 01 11 10 0 1 1 0 0 1 1 0 0 1 1 0 0 0 1 1

5 more pages in the full document

Unlock it once and it stays in your library, ready to chat with or turn into flashcards.

Unlock the full document

More Information Technology study materials

See all

Study this document with CramX

Once it is in your library, every tool can work from it.