29 votes 29 votes The maximum gate delay for any output to appear in an array multiplier for multiplying two $n$ bit numbers is $O(n^2)$ $O(n)$ $O(\log n)$ $O(1)$ Digital Logic gate1999 digital-logic normal array-multiplier + – Kathleen asked Sep 23, 2014 Kathleen 11.6k views answer comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments Shiva Sagar Rao commented Dec 4, 2020 reply Follow Share Similar question: https://gateoverflow.in/902/gate2003-11 0 votes 0 votes Overflow04 commented Sep 21, 2022 i edited by Overflow04 Sep 21, 2022 reply Follow Share this video will give inside idea about multiplication. You might also understand why n bit is required, if you understand this video(Starting 5 min is enough). https://youtu.be/vcvgvqnH7GA 0 votes 0 votes Overflow04 commented Sep 21, 2022 reply Follow Share just 5 min only to get idea of multiplication. 0 votes 0 votes Please log in or register to add a comment.
Best answer 27 votes 27 votes In an $N \times M$ array multiplier we have $N \times M$ AND gates and $(M-1),$ $N-bit$ adders are used. Total delay in $N \times M (N\geq M)$ array multiplier due to AND gate in partial products at all level is just $1$ unit AND gate delay as the operation is done parallel wise at each step. Now delays at level $1$ to $(M-1) = (M-1) \times $ delay due to $1$ unit of $N-bit$ adder. Therefore the maximum gate delay is $O(M)$ but here $M=N \therefore O(N).$ http://www.dauniv.ac.in/downloads/CArch_PPTs/CompArchCh03L06ArrayMult.pdf or archive Refer this article page 16. Correct Answer: $B$ Riya Roy(Arayana) answered Jul 31, 2015 • edited Jun 13, 2021 by S k Rawani Riya Roy(Arayana) comment Share Follow See all 10 Comments See all 10 10 Comments reply PEKKA commented Dec 15, 2016 reply Follow Share Not able to understand the solution :( Any simple way ? 0 votes 0 votes thor commented Jan 1, 2017 i edited by thor Jan 1, 2017 reply Follow Share someone explain? 0 votes 0 votes rahulsangwn commented Nov 19, 2017 reply Follow Share what about carry propagating from one adder to next adder according to this it will take O(n) in one level of computation?? 0 votes 0 votes Prateek kumar commented Dec 22, 2017 reply Follow Share Answer is right but need better explanation for this question 0 votes 0 votes register_user_19 commented Oct 30, 2018 reply Follow Share link change http://eee.guc.edu.eg/Courses/Electronics/ELCT706%20Microelectronics%20Lab/winter%202014/Multipliers.pdf page no. 8 3 votes 3 votes talha hashim commented Nov 2, 2018 reply Follow Share great explanation riya mam 0 votes 0 votes Saikumar_Baalu commented Dec 25, 2019 reply Follow Share Do we have array multiplier concept in gate 2020 syllabus 2 votes 2 votes Shiva Sagar Rao commented Dec 4, 2020 reply Follow Share Archive of link provided in answer: https://web.archive.org/web/20171031015528/http://www.dauniv.ac.in/downloads/CArch_PPTs/CompArchCh03L06ArrayMult.pdf 0 votes 0 votes shashankrustagi commented Dec 18, 2020 reply Follow Share Nice PDF, I learned booths algo from here. 1 votes 1 votes John_Smith commented Dec 11, 2023 i edited by John_Smith Dec 11, 2023 reply Follow Share @kshitij provided an excellent NPTEL video below to understand array multipliers – https://youtu.be/5-PI4T25OXIBased on what I understand from the video, your adders do not need to be carry look ahead adders. Yes, carry look ahead adders do speed up the process, but the speed up does not affect the asymptotic time complexity of the array multiplier circuit (which is what the question asks for), assuming the time taken to generate a sum or a carry by a single full adder/half adder circuit (inside a carry look ahead adder, or a ripple carry adders, or any such multi-bit adder circuit) to be \(O(1)\). You can very well use ripple carry adders in your array multiplier circuit, due to which its asymptotic time complexity equals the time for the last adder to generate the last carry bit to be placed in the product (i.e., \(P_{n+m-1}\), if we were to denote the product as \(P_{n+m-1} \ P_{n+m-2}\ ...\ P_0\); note that the size of the product is equal to the sum of the sizes of the multiplicand and the multiplier), because all the other operations in the array multiplier circuit is taking place simultaneously as the carry is getting propagated. And, the time for that carry to propagate is nothing but \(O(1)\) (to form the first partial product, and to produce the first carry from \(a_0b_1+a_1b_0\)) \(\ + \ \) \(O\big((n-1)+(m-1)\big)\) (since the carry traverses \((n-1)\) bits in the first adder, then falls off as one the last input bits in the second adder, falls off as one the last input bits in the third adder,…,one the last input bits in the \((m-1)\)th adder, and falls of into \(P_{n+m-1}\); it similar to going from \((1,1)\) to \((n-1,m-1)\) in a \((n-1)\times (m-1)\) sized grid, via \((n-1)\) left/right moves, followed by \((m-1)\) up/down moves) \(=O(n+m)\). So the asymptotic time complexity of the array multiplier circuit using any form of multi-bit adders is \(O(n+m)\). As \(n=m\) in the above question, we have the asymptotic time complexity of the array multiplier circuit as \(O(n+n)=O(n)\).P.S. Why isn’t using carry look ahead adder reducing the asymptotic time complexity of the array multiplier circuit? It’s because we forget that the (complex) carry generation circuitry of any \((i+1)\)th level adder cannot proceed unless the output from the \(i\)th level adder is available, so a similar logic as above works in this case as well. 0 votes 0 votes Please log in or register to add a comment.
4 votes 4 votes maximum Gate delay should be O(2n-1) = O(n) Digvijay Pandey answered May 15, 2015 Digvijay Pandey comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments Puja Mishra commented Dec 17, 2017 reply Follow Share 2n-1 ?? how ?? 0 votes 0 votes Aditya Tewari commented Dec 19, 2017 reply Follow Share see this https://gateoverflow.in/902/gate2003-11 1 votes 1 votes kshitij commented Jul 12, 2019 reply Follow Share https://youtu.be/5-PI4T25OXI Watch this NPTEL video. 2 votes 2 votes Please log in or register to add a comment.
1 votes 1 votes Answer is (b) $O(n)$. In $1\ unit$ we can find all the the partial products (if we assume we have enough space to store the partial products). Then for subsequent n-1 additions we will have n-1 unit so total is O(1+n-1) = O(n) Pratyush Priyam Kuan answered Sep 29, 2020 • edited Oct 24, 2020 by Pratyush Priyam Kuan Pratyush Priyam Kuan comment Share Follow See 1 comment See all 1 1 comment reply Divyanshu Shukla commented Oct 23, 2020 reply Follow Share answer is 0(n). 0 votes 0 votes Please log in or register to add a comment.