Analysis of Multiplication Algorithms and Boolean Function Optimization

Preview (3 of 8 Pages)

100%

Purchase to unlock

Loading page image...

Analysis of Multiplication Algorithms and Boolean Function OptimizationQ3.14)Here in this algorithm let us assume that shifting and addition are two measure time consuming processso conditional statements can be ignored.FOR HARDWARE:As it is given that addition will always take place and for hardware shifting of both multiplier andmultiplicand 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 timeconsumed for every iteration. So irrespective to size of integer the algorithm will going to repeat itself32 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 timeconsuming 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 thentime 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 twodifferent steps and hence total measure time consuming steps are 3(addition + shift of multiplier + shiftof 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 be4*(addition step+ shift of multiplier +shift of multiplicand)*32 which is equal to 384 unit of time.If conditional statement checking is assumed to be time consuming then there will be 5 steps forsoftware 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 thentime consumed will b 12*8 which is 96 unit of time.Q 3.15)Inapproach there are 32 adders stacked vertically,Rather than use a single 32-bitadder 32 times, thishardware “unrolls the loop” to use 32 adders. Each adder produces a 32-bitsum and a carry out. Theleastsignificant bit is a bit of the product, and the carry out and the upper 31 bitsof the sum are passedalong tothe next adder.

Loading page image...

The numbers are stored in 32 bit register and as number is 8bit all other bit are set to zero. Once themultiplication start it will end after completing 32 steps and we get product in product register. As eachadder take 4 unit time there are total 32 adder hence total time consumed will be 32*4 = 128 unit. Notethat for all higher bit of number which are 0 every time adder will work and add zero.If we assume thatthe 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 infirst step number of adder are 16 in second sep number of adder are 8 in third number of adder are 4and in fourth number of adder are 2 and in last step only one adder is required. Totalnumberof adderrequired are 31. Each adder consume 4 unit of time in computation hence total time required for 32 bitnumber multiplication is 31*4 = 124 unit of time. If we assume that the number is 8 bit long andhardware is optimized as per number then adder require in first step will be 4 in next step 2 and 1 inlast. 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 +𝑎𝑏𝑐ഥ𝑑KMap Representation of result is:CD000111100110011001100011

Preview Mode

This document has 8 pages. Sign in to access the full document!

Report

Study Now!

Document Details

Related Documents

DevOps and Its Importance Study Notes

Veeam Certified Engineer VMCE-V12

Modules 1 - 3 Basic Network Connectivity and Commu

Notes CCNA

CCNA 200-301 Portable Command Guide 5th Edition 20

CCNA 200-301 Portable Command Guide 5th Edition 22

CCNA 200-301 Portable Command Guide 5th Edition 36

Foundations of Novell Networking Section 26

Modulo 7 DHCPv4

Build and troubleshooting Integration Challenge

Company

Explore

Study Tools