Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Dadda multiplier
open-in-new
<h2 id="description">Description</h2> <p>To achieve a more optimal final product, the structure of the reduction process is governed by slightly more complex rules than in Wallace multipliers. </p><p>The progression of the reduction is controlled by a maximum-height sequence d j {\displaystyle d_{j}} , defined by: </p> d 1 = 2 {\displaystyle d_{1}=2} , and d j + 1 = floor ( 1.5 d j ) . {\displaystyle d_{j+1}=\operatorname {floor} (1.5d_{j}).} <p>This yields a sequence like so: </p> d 1 = 2 , d 2 = 3 , d 3 = 4 , d 4 = 6 , d 5 = 9 , d 6 = 13 , … {\displaystyle d_{1}=2,d_{2}=3,d_{3}=4,d_{4}=6,d_{5}=9,d_{6}=13,\ldots } <p>The initial value of j {\displaystyle j} is chosen as the largest value such that d j < min ( n 1 , n 2 ) {\displaystyle d_{j}<\min {(n_{1},n_{2})}} , where n 1 {\displaystyle n_{1}} and n 2 {\displaystyle n_{2}} are the number of bits in the input multiplicand and multiplier. The lesser of the two bit lengths will be the maximum height of each column of weights after the first stage of multiplication. For each stage j {\displaystyle j} of the reduction, the goal of the algorithm is the reduce the height of each column so that it is less than or equal to the value of d j {\displaystyle d_{j}} . </p><p>For each stage from , … , 1 {\displaystyle ,\ldots ,1} , reduce each column starting at the lowest-weight column, c 0 {\displaystyle c_{0}} according to these rules: </p> <ol><li>If height ( c i ) ⩽ d j {\displaystyle \operatorname {height} (c_{i})\leqslant d_{j}} the column does not require reduction, move to column c i + 1 {\displaystyle c_{i+1}} </li> <li>If height ( c i ) = d j + 1 {\displaystyle \operatorname {height} (c_{i})=d_{j}+1} add the top two elements in a half-adder, placing the result at the bottom of the column and the carry at the bottom of column c i + 1 {\displaystyle c_{i+1}} , then move to column c i + 1 {\displaystyle c_{i+1}} </li> <li>Else, add the top three elements in a full-adder, placing the result at the bottom of the column and the carry at the bottom of column c i + 1 {\displaystyle c_{i+1}} , restart c i {\displaystyle c_{i}} at step 1</li></ol> <h2 id="algorithm-example">Algorithm example</h2> <p>The example in the adjacent image illustrates the reduction of an 8 × 8 multiplier, explained here. </p><p>The initial state j = 4 {\displaystyle j=4} is chosen as d 4 = 6 {\displaystyle d_{4}=6} , the largest value less than 8. </p><p>Stage j = 4 {\displaystyle j=4} , d 4 = 6 {\displaystyle d_{4}=6} </p> <ul><li> height ( c 0 ⋯ c 5 ) {\displaystyle \operatorname {height} (c_{0}\cdots c_{5})} are all less than or equal to six bits in height, so no changes are made</li> <li> height ( c 6 ) = d 4 + 1 = 7 {\displaystyle \operatorname {height} (c_{6})=d_{4}+1=7} , so a half-adder is applied, reducing it to six bits and adding its carry bit to c 7 {\displaystyle c_{7}} </li> <li> height ( c 7 ) = 9 {\displaystyle \operatorname {height} (c_{7})=9} including the carry bit from c 6 {\displaystyle c_{6}} , so we apply a full-adder and a half-adder to reduce it to six bits</li> <li> height ( c 8 ) = 9 {\displaystyle \operatorname {height} (c_{8})=9} including two carry bits from c 7 {\displaystyle c_{7}} , so we again apply a full-adder and a half-adder to reduce it to six bits</li> <li> height ( c 9 ) = 8 {\displaystyle \operatorname {height} (c_{9})=8} including two carry bits from c 8 {\displaystyle c_{8}} , so we apply a single full-adder and reduce it to six bits</li> <li> height ( c 10 ⋯ c 14 ) {\displaystyle \operatorname {height} (c_{10}\cdots c_{14})} are all less than or equal to six bits in height including carry bits, so no changes are made</li></ul> <p>Stage j = 3 {\displaystyle j=3} , d 3 = 4 {\displaystyle d_{3}=4} </p> <ul><li> height ( c 0 ⋯ c 3 ) {\displaystyle \operatorname {height} (c_{0}\cdots c_{3})} are all less than or equal to four bits in height, so no changes are made</li> <li> height ( c 4 ) = d 3 + 1 = 5 {\displaystyle \operatorname {height} (c_{4})=d_{3}+1=5} , so a half-adder is applied, reducing it to four bits and adding its carry bit to c 5 {\displaystyle c_{5}} </li> <li> height ( c 5 ) = 7 {\displaystyle \operatorname {height} (c_{5})=7} including the carry bit from c 4 {\displaystyle c_{4}} , so we apply a full-adder and a half-adder to reduce it to four bits</li> <li> height ( c 6 ⋯ c 10 ) = 8 {\displaystyle \operatorname {height} (c_{6}\cdots c_{10})=8} including previous carry bits, so we apply two full-adders to reduce them to four bits</li> <li> height ( c 11 ) = 6 {\displaystyle \operatorname {height} (c_{11})=6} including previous carry bits, so we apply a full-adder to reduce it to four bits</li> <li> height ( c 12 ⋯ c 14 ) {\displaystyle \operatorname {height} (c_{12}\cdots c_{14})} are all less than or equal to four bits in height including carry bits, so no changes are made</li></ul> <p>Stage j = 2 {\displaystyle j=2} , d 2 = 3 {\displaystyle d_{2}=3} </p> <ul><li> height ( c 0 ⋯ c 2 ) {\displaystyle \operatorname {height} (c_{0}\cdots c_{2})} are all less than or equal to three bits in height, so no changes are made</li> <li> height ( c 3 ) = d 2 + 1 = 4 {\displaystyle \operatorname {height} (c_{3})=d_{2}+1=4} , so a half-adder is applied, reducing it to three bits and adding its carry bit to c 4 {\displaystyle c_{4}} </li> <li> height ( c 4 ⋯ c 12 ) = 5 {\displaystyle \operatorname {height} (c_{4}\cdots c_{12})=5} including previous carry bits, so we apply one full-adder to reduce them to three bits</li> <li> height ( c 13 ⋯ c 14 ) {\displaystyle \operatorname {height} (c_{13}\cdots c_{14})} are all less than or equal to three bits in height including carry bits, so no changes are made</li></ul> <p>Stage j = 1 {\displaystyle j=1} , d 1 = 2 {\displaystyle d_{1}=2} </p> <ul><li> height ( c 0 ⋯ c 1 ) {\displaystyle \operatorname {height} (c_{0}\cdots c_{1})} are all less than or equal to two bits in height, so no changes are made</li> <li> height ( c 2 ) = d 1 + 1 = 3 {\displaystyle \operatorname {height} (c_{2})=d_{1}+1=3} , so a half-adder is applied, reducing it to two bits and adding its carry bit to c 3 {\displaystyle c_{3}} </li> <li> height ( c 3 ⋯ c 13 ) = 4 {\displaystyle \operatorname {height} (c_{3}\cdots c_{13})=4} including previous carry bits, so we apply one full-adder to reduce them to two bits</li> <li> height ( c 14 ) = 2 {\displaystyle \operatorname {height} (c_{14})=2} including the carry bit from c 13 {\displaystyle c_{13}} , so no changes are made</li></ul> <p>Addition </p><p>The output of the last stage leaves 15 columns of height two or less which can be passed into a standard adder. </p> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Booth%27s_multiplication_algorithm/CplEqXtt">Booth's multiplication algorithm</a></li> <li><a href="/facts/Fused_multiply%E2%80%93add/L26C9A1Y">Fused multiply–add</a></li> <li><a href="/facts/Wallace_tree/SK9nUedd">Wallace tree</a></li> <li><a href="/facts/BKM_algorithm/e0r1Wszn">BKM algorithm</a> for complex logarithms and exponentials</li> <li><a href="/facts/Kochanski_multiplication/9JeCs0CX">Kochanski multiplication</a> for <a href="/facts/Modular_arithmetic/0wtRa5dU">modular</a> multiplication</li></ul> <h2 id="further-reading">Further reading</h2> <ul><li>Savard, John J. G. (2018) [2006]. <a href="http://www.quadibloc.com/comp/cp0202.htm">"Advanced Arithmetic Techniques"</a>. <i>quadibloc</i>. <a href="https://web.archive.org/web/20180703001722/http://www.quadibloc.com/comp/cp0202.htm">Archived</a> from the original on 2018-07-03. Retrieved 2018-07-16.</li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Dadda, Luigi (May 1965). "Some schemes for parallel multipliers". Alta Frequenza. 34 (5): 349–356.Dadda, L. (1976). "Some schemes for parallel multipliers". In Swartzlander, Earl E. (ed.). Computer Design Development: Principal Papers. Hayden Book Company. pp. 167–180. ISBN 978-0-8104-5988-5. OCLC 643640444. <a href="978-0-8104-5988-5" target="_blank">978-0-8104-5988-5</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Townsend, Whitney J.; Swartzlander, Jr., Earl E.; Abraham, Jacob A. (December 2003). "A Comparison of Dadda and Wallace Multiplier Delays" (PDF). SPIE Advanced Signal Processing Algorithms, Architectures, and Implementations XIII. The International Society. doi:10.1117/12.507012. <a href="/wiki/Jacob_A._Abraham" target="_blank">/wiki/Jacob_A._Abraham</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> </ol>