{"id":81,"date":"2018-07-18T09:43:37","date_gmt":"2018-07-18T09:43:37","guid":{"rendered":"http:\/\/csp2.epgpbooks.inflibnet.ac.in\/?post_type=chapter&p=81"},"modified":"2018-08-03T07:00:57","modified_gmt":"2018-08-03T07:00:57","slug":"81","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp2\/chapter\/81\/","title":{"rendered":"Fixed Point Arithmetic Unit II"},"content":{"raw":"
\r\n\r\n \r\n

The objectives of this module are to discuss Booth\u2019s multiplication technique, fast multiplication techniques and binary division techniques.<\/p>\r\n \r\n\r\nBooth\u2019s Multiplier<\/strong>\r\n\r\n \r\n

The major advantage of the Booth\u2019s technique as proposed by Andrew D. Booth is that it handles both positive and negative numbers. It may also have an added advantage of reducing the number of operations depending on the multiplier. The principle behind this is given below.<\/p>\r\n \r\n

Consider a positive multiplier consisting of a block of 1s surrounded by 0s. For example, 00111110. The product is given by :<\/p>\r\n \r\n

M x 00111110 = M x (25<\/sup> + 24<\/sup>+ 23<\/sup> + 22<\/sup> + 21<\/sup>) = M x 62, where M is the multiplicand. The number of operations can be reduced to two by rewriting the same as<\/p>\r\n \r\n

M x 01000010 = M x (26<\/sup> - 21<\/sup>) = M x 62<\/p>\r\n \r\n

In fact, it can be shown that any sequence of 1's in a binary number can be broken into the difference of two binary numbers:<\/p>\r\n\"\"\r\n\r\n \r\n

Hence, we can actually replace the multiplication by the string of ones in the original number by simpler operations, adding the multiplier, shifting the partial product thus formed by appropriate places, and then finally subtracting the multiplier. It is making use of the fact that we do not have to do anything but shift while we are dealing with 0s in a binary multiplier, and is similar to using the mathematical property that 99 = 100 \u2212 1 while multiplying by 99.<\/p>\r\n \r\n

This scheme can be extended to any number of blocks of 1s in a multiplier (including the case of single 1 in a block). Thus,<\/p>\r\n\"\"\r\n

Booth's algorithm follows this scheme by performing an addition when it encounters the first digit of a block of ones (0 1) and a subtraction when it encounters the end of the block (1 0). This works for a negative multiplier as well. When the ones in a multiplier are grouped into long blocks, Booth's algorithm\u00a0performs fewer additions and subtractions than the normal multiplication algorithm.<\/span><\/p>\r\n \r\n

As a ready reference, use the table below:\u00a0<\/span><\/p>\r\n \r\n\r\n\"\"\r\n\r\nFast multiplication<\/strong>\r\n\r\n \r\n

We saw the binary multiplication techniques in the previous section. This section will introduce you to two ways of speeding up the multiplication process. The first method is a further modification to the Booth\u2019s technique that helps reduce the number of summands to n \/ 2 for n-bit operands. The second techinque reduces the time taken to add the summands.<\/span><\/p>\r\n \r\n

Bit \u2013 pair recoding of multiplier<\/strong><\/p>\r\n \r\n

This is derived from the Booth\u2019s algorithm. It pairs the multiplier bits and gives one multiplier bit per pair, thus reducing the number of summands by half. This is shown below.<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n\r\n\"\"\r\n\r\n \r\n\r\n\"\"\r\n\r\n \r\n\r\n\"\"\r\n\r\n\"\"\r\n

Multiplication requiring only n<\/em>\/2<\/p>\r\n

summands Carry-save addition of summands<\/strong><\/p>\r\n\r\n<\/div>\r\n

<\/div>\r\n
Carry save adders (CSA) speed up the addition of the summands generated during the multiplication process. The inputs to a full adder are normally the two bits of the two numbers and the carry input from the previous stage. On the other hand, in the case of the CSA, all the three bits are taken from the three numbers. The carry generated is saved and added at the next level. A CSA takes in two inputs and outputs two outputs. This is shown below.<\/span><\/div>\r\n
\r\n\r\n \r\n\r\n\"\"\r\n\r\n \r\n

As the figure above shows, one CSA block is used for every bit. This circuit adds 3 8-bit numbers into two numbers.<\/p>\r\n \r\n

The important point is that c and s can be computed independently and each ci and si can be computed independent of all other ci\u2019s and si\u2019s. An example is given below.<\/p>\r\n \r\n\r\n\"\"\r\n\r\n \r\n\r\nThe multiplication process carried out using CSA is illustrated below.\r\n\r\n \r\n\r\n\"\"\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n

Thus, in order to speed up the multiplication process, bit-pair recoding of the multiplier is used to reduce the summands. These summands are then reduced to 2 using a few CSA steps. The final product is generated by an addition operation that uses CLA. All these three techniques help in reducing the time taken for multiplication.<\/p>\r\n \r\n\r\nBinary division<\/strong>\r\n\r\n \r\n

An example of binary division is shown below. We first examine the divisor and the dividend, decide that only if we consider the first three bits of the dividend the divisor will go and then proceed. The first two bits, though not shown, will have to be 0\u2019s. We then get a quotient bit of 1, do the subtraction, get the partial remainder and do the trial subtraction (mentally) and accordingly generate the quotient bit. This process is repeated till we exhaust all the dividend bits. This is illustrated below.<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n\r\n\"\"\r\n\r\n \r\n

Now, the same logic has to be adopted for machine implementation too. Only thing is that, it has to be done systematically, and to decide whether the divisor is less than or equal to the dividend, we have to do a trial comparison \/ subtraction. There are basically two types of division algorithms:<\/p>\r\n \r\n

    \r\n \t
  • Restoring division<\/li>\r\n \t
  • Non-restoring division<\/li>\r\n<\/ul>\r\n \r\n\r\nBoth these are for positive numbers. Negative numbers are handled the same way with the sign bits processed separately.\r\n\r\n \r\n\r\nRestoring division<\/strong>\r\n\r\n \r\n

    Take the first bit of the dividend and do a trial subtraction. If the subtraction produces a negative result, we generate a quotient bit of zero, restore, bring the next bit of dividend and continue. Otherwise, we simply continue with a quotient bit of 1. The algorithm, register organization and example are given below.<\/p>\r\n\r\n<\/div>\r\n

    \r\n\r\n\"\"\r\n\r\n<\/div>\r\n
    \r\n\r\n \r\n\r\nwhere <\/strong>N=Numerator, D=Denominator, n=#bits, P=Partial remainder, q(i)=bit #i of<\/em> quotient<\/em>\r\n\r\n<\/div>\r\n
    \r\n\r\n\"\"\r\n\r\n\"\"\r\n\r\n \r\n\r\nNon-restoring division<\/strong>\r\n\r\n \r\n

    This is a modification of the restoring algorithm. It combines the restore \/ no restore and shift left steps of two successive cycles and reduces the number of operations. The algorithm is given below.<\/p>\r\n\r\n

      \r\n \t
    • Do the first shift and subtraction<\/li>\r\n \t
    • Check sign of the partial remainder<\/li>\r\n \t
    • If it is negative, shift and add<\/li>\r\n \t
    • If it is positive, shift and subtract<\/li>\r\n \t
    • Fix the quotient bit appropriately<\/li>\r\n \t
    • If the final remainder is negative, add the divisor.<\/strong><\/li>\r\n<\/ul>\r\nAn example is discussed below.\r\n\r\n \r\n\r\n<\/div>\r\n\"\"\r\n\r\nRemainder<\/strong>\r\n\r\n \r\n

      To summarize, we have discussed the Booth\u2019s multiplication technique used for handling positive and negative numbers in the same manner. We also discussed carry save addition and saw how fast multiplication can be carried out. Finally, we discussed the restoring and non restoring division algorithms.<\/p>\r\n \r\n\r\nWeb Links \/ Supporting Materials<\/strong>\r\n

        \r\n \t
      • Computer Organization, Carl Hamacher, Zvonko Vranesic and Safwat Zaky, 5th.Edition, McGraw- Hill Higher Education, 2011.<\/li>\r\n \t
      • Computer Organization and Design \u2013 The Hardware \/ Software Interface, David A. Patterson and John L. Hennessy, 4th.Edition, Morgan Kaufmann, Elsevier, 2009.<\/li>\r\n<\/ul>","rendered":"
        \n

         <\/p>\n

        The objectives of this module are to discuss Booth\u2019s multiplication technique, fast multiplication techniques and binary division techniques.<\/p>\n

         <\/p>\n

        Booth\u2019s Multiplier<\/strong><\/p>\n

         <\/p>\n

        The major advantage of the Booth\u2019s technique as proposed by Andrew D. Booth is that it handles both positive and negative numbers. It may also have an added advantage of reducing the number of operations depending on the multiplier. The principle behind this is given below.<\/p>\n

         <\/p>\n

        Consider a positive multiplier consisting of a block of 1s surrounded by 0s. For example, 00111110. The product is given by :<\/p>\n

         <\/p>\n

        M x 00111110 = M x (25<\/sup> + 24<\/sup>+ 23<\/sup> + 22<\/sup> + 21<\/sup>) = M x 62, where M is the multiplicand. The number of operations can be reduced to two by rewriting the same as<\/p>\n

         <\/p>\n

        M x 01000010 = M x (26<\/sup> – 21<\/sup>) = M x 62<\/p>\n

         <\/p>\n

        In fact, it can be shown that any sequence of 1’s in a binary number can be broken into the difference of two binary numbers:<\/p>\n

        \"\"<\/p>\n

         <\/p>\n

        Hence, we can actually replace the multiplication by the string of ones in the original number by simpler operations, adding the multiplier, shifting the partial product thus formed by appropriate places, and then finally subtracting the multiplier. It is making use of the fact that we do not have to do anything but shift while we are dealing with 0s in a binary multiplier, and is similar to using the mathematical property that 99 = 100 \u2212 1 while multiplying by 99.<\/p>\n

         <\/p>\n

        This scheme can be extended to any number of blocks of 1s in a multiplier (including the case of single 1 in a block). Thus,<\/p>\n

        \"\"<\/p>\n

        Booth’s algorithm follows this scheme by performing an addition when it encounters the first digit of a block of ones (0 1) and a subtraction when it encounters the end of the block (1 0). This works for a negative multiplier as well. When the ones in a multiplier are grouped into long blocks, Booth’s algorithm\u00a0performs fewer additions and subtractions than the normal multiplication algorithm.<\/span><\/p>\n

         <\/p>\n

        As a ready reference, use the table below:\u00a0<\/span><\/p>\n

         <\/p>\n

        \"\"<\/p>\n

        Fast multiplication<\/strong><\/p>\n

         <\/p>\n

        We saw the binary multiplication techniques in the previous section. This section will introduce you to two ways of speeding up the multiplication process. The first method is a further modification to the Booth\u2019s technique that helps reduce the number of summands to n \/ 2 for n-bit operands. The second techinque reduces the time taken to add the summands.<\/span><\/p>\n

         <\/p>\n

        Bit \u2013 pair recoding of multiplier<\/strong><\/p>\n

         <\/p>\n

        This is derived from the Booth\u2019s algorithm. It pairs the multiplier bits and gives one multiplier bit per pair, thus reducing the number of summands by half. This is shown below.<\/span><\/p>\n<\/div>\n

        \n

         <\/p>\n

        \"\"<\/p>\n

         <\/p>\n

        \"\"<\/p>\n

         <\/p>\n

        \"\"<\/p>\n

        \"\"<\/p>\n

        Multiplication requiring only n<\/em>\/2<\/p>\n

        summands Carry-save addition of summands<\/strong><\/p>\n<\/div>\n

        <\/div>\n
        Carry save adders (CSA) speed up the addition of the summands generated during the multiplication process. The inputs to a full adder are normally the two bits of the two numbers and the carry input from the previous stage. On the other hand, in the case of the CSA, all the three bits are taken from the three numbers. The carry generated is saved and added at the next level. A CSA takes in two inputs and outputs two outputs. This is shown below.<\/span><\/div>\n
        \n

         <\/p>\n

        \"\"<\/p>\n

         <\/p>\n

        As the figure above shows, one CSA block is used for every bit. This circuit adds 3 8-bit numbers into two numbers.<\/p>\n

         <\/p>\n

        The important point is that c and s can be computed independently and each ci and si can be computed independent of all other ci\u2019s and si\u2019s. An example is given below.<\/p>\n

         <\/p>\n

        \"\"<\/p>\n

         <\/p>\n

        The multiplication process carried out using CSA is illustrated below.<\/p>\n

         <\/p>\n

        \"\"<\/p>\n<\/div>\n

        \n

         <\/p>\n

        Thus, in order to speed up the multiplication process, bit-pair recoding of the multiplier is used to reduce the summands. These summands are then reduced to 2 using a few CSA steps. The final product is generated by an addition operation that uses CLA. All these three techniques help in reducing the time taken for multiplication.<\/p>\n

         <\/p>\n

        Binary division<\/strong><\/p>\n

         <\/p>\n

        An example of binary division is shown below. We first examine the divisor and the dividend, decide that only if we consider the first three bits of the dividend the divisor will go and then proceed. The first two bits, though not shown, will have to be 0\u2019s. We then get a quotient bit of 1, do the subtraction, get the partial remainder and do the trial subtraction (mentally) and accordingly generate the quotient bit. This process is repeated till we exhaust all the dividend bits. This is illustrated below.<\/span><\/p>\n<\/div>\n

        \n

         <\/p>\n

        \"\"<\/p>\n

         <\/p>\n

        Now, the same logic has to be adopted for machine implementation too. Only thing is that, it has to be done systematically, and to decide whether the divisor is less than or equal to the dividend, we have to do a trial comparison \/ subtraction. There are basically two types of division algorithms:<\/p>\n

         <\/p>\n

          \n
        • Restoring division<\/li>\n
        • Non-restoring division<\/li>\n<\/ul>\n

           <\/p>\n

          Both these are for positive numbers. Negative numbers are handled the same way with the sign bits processed separately.<\/p>\n

           <\/p>\n

          Restoring division<\/strong><\/p>\n

           <\/p>\n

          Take the first bit of the dividend and do a trial subtraction. If the subtraction produces a negative result, we generate a quotient bit of zero, restore, bring the next bit of dividend and continue. Otherwise, we simply continue with a quotient bit of 1. The algorithm, register organization and example are given below.<\/p>\n<\/div>\n

          \n

          \"\"<\/p>\n<\/div>\n

          \n

           <\/p>\n

          where <\/strong>N=Numerator, D=Denominator, n=#bits, P=Partial remainder, q(i)=bit #i of<\/em> quotient<\/em><\/p>\n<\/div>\n

          \n

          \"\"<\/p>\n

          \"\"<\/p>\n

           <\/p>\n

          Non-restoring division<\/strong><\/p>\n

           <\/p>\n

          This is a modification of the restoring algorithm. It combines the restore \/ no restore and shift left steps of two successive cycles and reduces the number of operations. The algorithm is given below.<\/p>\n

            \n
          • Do the first shift and subtraction<\/li>\n
          • Check sign of the partial remainder<\/li>\n
          • If it is negative, shift and add<\/li>\n
          • If it is positive, shift and subtract<\/li>\n
          • Fix the quotient bit appropriately<\/li>\n
          • If the final remainder is negative, add the divisor.<\/strong><\/li>\n<\/ul>\n

            An example is discussed below.<\/p>\n

             <\/p>\n<\/div>\n

            \"\"<\/p>\n

            Remainder<\/strong><\/p>\n

             <\/p>\n

            To summarize, we have discussed the Booth\u2019s multiplication technique used for handling positive and negative numbers in the same manner. We also discussed carry save addition and saw how fast multiplication can be carried out. Finally, we discussed the restoring and non restoring division algorithms.<\/p>\n

             <\/p>\n

            Web Links \/ Supporting Materials<\/strong><\/p>\n

              \n
            • Computer Organization, Carl Hamacher, Zvonko Vranesic and Safwat Zaky, 5th.Edition, McGraw- Hill Higher Education, 2011.<\/li>\n
            • Computer Organization and Design \u2013 The Hardware \/ Software Interface, David A. Patterson and John L. Hennessy, 4th.Edition, Morgan Kaufmann, Elsevier, 2009.<\/li>\n<\/ul>\n","protected":false},"author":2,"menu_order":6,"template":"","meta":{"_acf_changed":false,"pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":["dr-a-p-shanthi"],"pb_section_license":""},"chapter-type":[],"contributor":[58],"license":[],"class_list":["post-81","chapter","type-chapter","status-publish","hentry","contributor-dr-a-p-shanthi"],"part":3,"_links":{"self":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp2\/wp-json\/pressbooks\/v2\/chapters\/81","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp2\/wp-json\/pressbooks\/v2\/chapters"}],"about":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp2\/wp-json\/wp\/v2\/types\/chapter"}],"author":[{"embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp2\/wp-json\/wp\/v2\/users\/2"}],"version-history":[{"count":5,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp2\/wp-json\/pressbooks\/v2\/chapters\/81\/revisions"}],"predecessor-version":[{"id":440,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp2\/wp-json\/pressbooks\/v2\/chapters\/81\/revisions\/440"}],"part":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp2\/wp-json\/pressbooks\/v2\/parts\/3"}],"metadata":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp2\/wp-json\/pressbooks\/v2\/chapters\/81\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp2\/wp-json\/wp\/v2\/media?parent=81"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp2\/wp-json\/pressbooks\/v2\/chapter-type?post=81"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp2\/wp-json\/wp\/v2\/contributor?post=81"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp2\/wp-json\/wp\/v2\/license?post=81"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}