Browsing by Subject "Computer arithmetic"
Now showing 1 - 2 of 2
Results Per Page
Sort Options
Item Improved algorithms for non-restoring division and square root(2012-12) Jun, Kihwan; Swartzlander, Earl E.; Driga, Mircea D; Neikirk, Dean P; Touba, Nur A; Schulte, Michael JThis dissertation focuses on improving the non-restoring division and square root algorithm. Although the non-restoring division algorithm is the fastest and has less complexity among other radix-2 digit recurrence division algorithms, there are some possibilities to enhance its performance. To improve its performance, two new approaches are proposed here. In addition, the research scope is extended to seek an efficient algorithm for implementing non-restoring square root, which has similar steps to non-restoring division. For the first proposed approach, the non-restoring divider with a modified algorithm is presented. The new algorithm changes the order of the flowchart, which reduces one unit delay of the multiplexer per every iteration. In addition, a new method to find a correct quotient is presented and it removes an error that the quotient is always odd number after a digit conversion from a digit converter from the quotient with digits 1 and -1 to conventional binary number. The second proposed approach is a novel method to find a quotient bit for every iteration, which hides the total delay of the multiplexer with dual path calculation. The proposed method uses a Most Significant Carry (MSC) generator, which determines the sign of each remainder faster than the conventional carry lookahead adder and it eventually reduces the total delay by almost 22% compared to the conventional non-restoring division algorithm. Finally, an improved algorithm for non-restoring square root is proposed. The two concepts already applied to non-restoring division are adopted for improving the performance of a non-restoring square root since it has similar process to that of non-restoring division for finding square root. Additionally, a new method to find intermediate quotients is presented that removes an adder per an iteration to reduce the total area and power consumption. The non-restoring square root with MSC generator reduces total delay, area and power consumption significantly.Item Total delay optimization for column reduction multipliers considering non-uniform arrival times to the final adder(2014-05) Waters, Ronald S.; Swartzlander, Earl E., Jr., 1945-Column Reduction Multiplier techniques provide the fastest multiplier designs and involve three steps. First, a partial product array of terms is formed by logically ANDing each bit of the multiplier with each bit of the multiplicand. Second, adders or counters are used to reduce the number of terms in each bit column to a final two. This activity is commonly described as column reduction and occurs in multiple stages. Finally, some form of carry propagate adder (CPA) is applied to the final two terms in order to sum them to produce the final product of the multiplication. Since forming the partial products, in the first step, is simply forming an array of the logical AND's of two bits, there is little opportunity for delay improvement for the first step. There has been much work done in optimizing the reduction stages for column multipliers in the second reduction step. All of the reduction approaches of the second step result in non-uniform arrival times to the input of the final carry propagate adder in the final step. The designs for carry propagate adders have been done assuming that the input bits all have the same arrival time. It is not evident that the non-uniform arrival times from the columns impacts the performance of the multiplier. A thorough analysis of the several column reduction methods and the impact of carry propagate adder designs, along with the column reduction design step, to provide the fastest possible final results, for an array of multiplier widths has not been undertaken. This dissertation investigates the design impact of three carry propagate adders, with different performance attributes, on the final delay results for four column reduction multipliers and suggests general ways to optimize the total delay for the multipliers.