Report Number: CSL-TR-95-679
Institution: Stanford University, Computer Systems Laboratory
Title: Measuring the Complexity of SRT Tables
Author: Oberman, Stuart F.
Author: Flynn, Michael J.
Date: November 1995
Abstract: This paper presents an analysis of the complexity of quotient-digit selection tables in SRT division implementations. SRT dividers use a fixed number of partial remainder and divisor bits to consult a table to select the next quotient-digit in each iteration. The complexity of these tables is a function of the radix, the redundancy, and the number of bits in the estimates of the divisor and partial remainder. This analysis derives the allowable divisor and partial remainder truncations for radix 2 through radix 32, and it quantifies the relationship between table parameters and the number of product terms in the logic equations defining the tables. By mapping the tables to a library of standard-cells, delay and area values were measured and are presented for table configurations through radix 32. The results show that: 1) Gray-coding of the quotient-digits allows for the automatic minimization of the quotient-digit selection logic equations. 2) Using a short carry-assimilating adder with a few more input bits than output bits can reduce table complexity. 3) Reducing the number of bits in the partial remainder estimate and increasing the length of the divisor estimate increases the size and delay of the table, offsetting any performance gain due to the shorter external adder. 4) While delay increases nearly linearly with radix, area increases quadratically, limiting practical table implementations to radix 2 and radix 4.