A Caltech Library Service

Large operand division and an asynchrous approach to fault detection


Kramer, Kathleen A. (1991) Large operand division and an asynchrous approach to fault detection. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/pt8p-9g83.


Larger, faster ICs are creating a rash of new problems for the system designer. Designers faced with building larger and larger systems base their architectures on smaller systems that may scale poorly. As a result of VLSI, many new architectures are coming into favor, either because of the changing importance of design factors or because it is now possible to design bigger chips.

Efficient VLSI methods for implementing the basic arithmetic operations can push back many system-performance limitations. There is continued need for re-evaluation of arithmetic architectures, as the efficiency of implementation is related to both implementation technology and size of the operands. A new binary divider for n-bit integer operands, which produces the quotient and remainder in O(n) time using O(n) area, is presented. For very large operands, such as those required in Public Key Cryptography, the new divider is faster than comparable carry-save dividers and is more area-efficient than implementations using more redundant arithmetic.

A further problem faced by the designer of very large systems is their susceptibility to error. The system must be efficiently designed to function in the presence of errors, which become more likely as the size of the system increases. Qualities inherent in many asynchronous designs can be used to provide fault detection and therefore, fault tolerance. An approach to fault tolerance, one not possible with conventional, clocked, systolic arrays, is presented. This method of fault detection/correction exploits the inherent redundancy of architectures using four-state coding, a data-driven technique for implementing bit-level wave-front arrays.

Item Type:Thesis (Dissertation (Ph.D.))
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Electrical Engineering
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Goodman, Rodney M.
Thesis Committee:
  • Goodman, Rodney M. (chair)
  • Posner, Edward C.
  • McEliece, Robert J.
  • Abu-Mostafa, Yaser S.
Defense Date:9 January 1991
Record Number:CaltechETD:etd-06212007-143920
Persistent URL:
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:2678
Deposited By: Imported from ETD-db
Deposited On:18 Jul 2007
Last Modified:19 Apr 2021 22:26

Thesis Files

PDF (Kramer_ka_1991.pdf) - Final Version
See Usage Policy.


Repository Staff Only: item control page