Multiplication of signed integers.html (8065B)
1 <?xml version="1.0" encoding="UTF-8"?> 2 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> 3 <html><head><link rel="stylesheet" href="sitewide.css" /><meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/><meta name="exporter-version" content="Evernote Mac 6.13.1 (455785)"/><meta name="altitude" content="-0.00303243612870574"/><meta name="author" content="Alex Balgavy"/><meta name="created" content="2017-12-05 5:08:28 PM +0000"/><meta name="latitude" content="52.33420531735815"/><meta name="longitude" content="4.867411570802592"/><meta name="source" content="desktop.mac"/><meta name="updated" content="2017-12-05 9:49:03 PM +0000"/><title>Multiplication of signed integers</title></head><body><div>Meaning 2’s complement signed ints.</div><div>There’s the shorthand and then there’s the algorithm.</div><div><br/></div><div><span style="font-weight: bold;">Shorthand (same as decimal multiplication)</span></div><div><img src="Multiplication%20of%20signed%20integers.resources/screenshot_2.png" height="230" width="387"/><br/></div><div><br/></div><div><b>Booth’s algorithm:</b></div><div><b><br/></b></div><div>Involves recoding the multiplier (Y in “X times Y”) based on this table, going bitwise left to right.</div><div>If the last bit is a 1, there’s an implied 0 behind it.</div><div><br/></div><div><img src="Multiplication%20of%20signed%20integers.resources/screenshot_3.png" height="206" width="302"/></div><div><br/></div><div>Then you do a table, going bitwise right to left on recoded multiplier. If it’s zero, you shift. If it’s -1, you add -A and shift. If it’s +1, you add A and shift.</div><div><br/></div><div>For example, if given 001111 × 001111:</div><div><br/></div><div>A = 001111</div><div>B = 001111</div><div>-A = 110001</div><div><br/></div><div>Recoded multiplier (B): 0 +1 0 0 0 -1</div><div><table style="border-collapse: collapse; min-width: 100%;"><colgroup><col style="width: 130px;"/><col style="width: 130px;"/><col style="width: 130px;"/></colgroup><tbody><tr><td style="border: 1px solid rgb(219, 219, 219); background-color: rgb(255, 255, 255); width: 130px; padding: 8px;"><div>Product</div></td><td style="border: 1px solid rgb(219, 219, 219); background-color: rgb(255, 255, 255); width: 130px; padding: 8px;"><div>Step description</div></td><td style="border: 1px solid rgb(219, 219, 219); background-color: rgb(255, 255, 255); width: 130px; padding: 8px;"><div>Multiplier bit</div></td></tr><tr><td style="border: 1px solid rgb(219, 219, 219); background-color: rgb(255, 255, 255); width: 130px; padding: 8px;"><div>000000</div></td><td style="border: 1px solid rgb(219, 219, 219); background-color: rgb(255, 255, 255); width: 130px; padding: 8px;"><div>Initialise</div></td><td style="border: 1px solid rgb(219, 219, 219); background-color: rgb(255, 255, 255); width: 130px; padding: 8px;"><div>-</div></td></tr><tr><td style="border: 1px solid rgb(219, 219, 219); background-color: rgb(255, 255, 255); width: 130px; padding: 8px;"><div>110001</div></td><td style="border: 1px solid rgb(219, 219, 219); background-color: rgb(255, 255, 255); width: 130px; padding: 8px;"><div>Add -A</div></td><td style="border: 1px solid rgb(219, 219, 219); background-color: rgb(255, 255, 255); width: 130px; padding: 8px;"><div>-1</div></td></tr><tr><td style="border: 1px solid rgb(219, 219, 219); background-color: rgb(255, 255, 255); width: 130px; padding: 8px;"><div>1110001</div></td><td style="border: 1px solid rgb(219, 219, 219); background-color: rgb(255, 255, 255); width: 130px; padding: 8px;"><div>Shift</div></td><td style="border: 1px solid rgb(219, 219, 219); background-color: rgb(255, 255, 255); width: 130px; padding: 8px;"><div><br/></div></td></tr><tr><td style="border: 1px solid rgb(219, 219, 219); background-color: rgb(255, 255, 255); width: 130px; padding: 8px;"><div>11110001</div></td><td style="border: 1px solid rgb(219, 219, 219); background-color: rgb(255, 255, 255); width: 130px; padding: 8px;"><div>Shift only</div></td><td style="border: 1px solid rgb(219, 219, 219); background-color: rgb(255, 255, 255); width: 130px; padding: 8px;"><div>0</div></td></tr><tr><td style="border: 1px solid rgb(219, 219, 219); background-color: rgb(255, 255, 255); width: 130px; padding: 8px;"><div>111110001</div></td><td style="border: 1px solid rgb(219, 219, 219); background-color: rgb(255, 255, 255); width: 130px; padding: 8px;"><div>Shift only</div></td><td style="border: 1px solid rgb(219, 219, 219); background-color: rgb(255, 255, 255); width: 130px; padding: 8px;"><div>0</div></td></tr><tr><td style="border: 1px solid rgb(219, 219, 219); background-color: rgb(255, 255, 255); width: 130px; padding: 8px;"><div>1111110001</div></td><td style="border: 1px solid rgb(219, 219, 219); background-color: rgb(255, 255, 255); width: 130px; padding: 8px;"><div>Shift only</div></td><td style="border: 1px solid rgb(219, 219, 219); background-color: rgb(255, 255, 255); width: 130px; padding: 8px;"><div>0</div></td></tr><tr><td style="border: 1px solid rgb(219, 219, 219); background-color: rgb(255, 255, 255); width: 130px; padding: 8px;"><div>0011100001</div></td><td style="border: 1px solid rgb(219, 219, 219); background-color: rgb(255, 255, 255); width: 130px; padding: 8px;"><div>Add +A</div></td><td style="border: 1px solid rgb(219, 219, 219); background-color: rgb(255, 255, 255); width: 130px; padding: 8px;"><div>+1</div></td></tr><tr><td style="border: 1px solid rgb(219, 219, 219); background-color: rgb(255, 255, 255); width: 130px; padding: 8px;"><div>00011100001</div></td><td style="border: 1px solid rgb(219, 219, 219); background-color: rgb(255, 255, 255); width: 130px; padding: 8px;"><div>Shift</div></td><td style="border: 1px solid rgb(219, 219, 219); background-color: rgb(255, 255, 255); width: 130px; padding: 8px;"><div><br/></div></td></tr><tr><td style="border: 1px solid rgb(219, 219, 219); background-color: rgb(255, 255, 255); width: 130px; padding: 8px;"><div>000011100001</div></td><td style="border: 1px solid rgb(219, 219, 219); background-color: rgb(255, 255, 255); width: 130px; padding: 8px;"><div>Shift only</div></td><td style="border: 1px solid rgb(219, 219, 219); background-color: rgb(255, 255, 255); width: 130px; padding: 8px;"><div>0</div></td></tr></tbody></table><div>So the final result is 000011100001 (twice as many bits as the terms).</div></div><div><br/></div><div><b>Speeding up the process</b></div><div>Bit-pair recoding of multipliers using Booth recoding:</div><div><img src="Multiplication%20of%20signed%20integers.resources/screenshot.png" height="309" width="521"/></div><div><br/></div><div>For example, for the multiplier 111010:</div><div><br/></div><div><img src="Multiplication%20of%20signed%20integers.resources/screenshot_4.png" height="190" width="464"/></div><div><br/></div><div>To multiply by -1, make 2’s complement. To multiply by -2, add 2’s complement. So now the process is:</div><div><br/></div><div><img src="Multiplication%20of%20signed%20integers.resources/screenshot_1.png" height="400" width="276"/></div><div><br/></div><div>You could also do carry-save addition, which is a crazy-ass circuit where the carries are introduced into the next row at the correct weighted positions.</div><div>Then there’s 3-2 reducer addition: carry-save add summands in groups of 3 to get S and C vectors, group S and C vectors in 3s and carry-save add, etc. until there are only two vectors left. Those are added by carry-save.</div><div><br/></div><div>Also, 4-2 reducer addition:</div><div><ul><li>s, c, and c<sub>out </sub>represent arithmetic sum of five inputs</li><li>output s is the sum variable (XOR of five inputs)</li><li>c<sub>out</sub> is independent of c<sub>in</sub>, only function of four inputs.</li><li>steps:</li><ol><li>c<sub>out</sub> is 1 when two or more inputs are 1</li><li>other carry (c) is determined to satisfy arithmetic condition</li></ol></ul></div><div><br/></div><div><br/></div></body></html>