Algorithms suitable for VLSI implementation /
| Main Author: | |
|---|---|
| Other Authors: | , , |
| Format: | Thesis Book |
| Language: | English |
| Published: |
1986.
|
| Subjects: | |
| Online Access: | Link to OAKTrust copy |
| Abstract: | The design and analysis of algorithms implementable in VLSI (very large scale integration) are studied. In particular, algorithms for the fundamental processes of multiplication and division of integers and for finding the greatest common divisor of two integers are examined. A design for a fast multiplier for 54-bit integers, implemented on a commercially available chip, is presented. The design is also analyzed for its performance for general n, and it is shown that, theoretically at least, the design achieves the best possible time for multiplication, O(log n). With respect to division, a binary algorithm is developed, and it is shown that the algorithm can be implemented in a systolic array of simple cells in the best possible area (area O(n) for n-bit inputs). A cellular array implementation of this algorithm is also described. For the greatest common divisor problem, it is shown that under reasonable design assumptions any chip which finds the greatest common divisor of two n-bit integers must have area A and time T satisfying AT^2α=Ω(n^1+α) for 0 [less than or equal to] α [less than or equal to] L The proof of this result is the first to use the concept of multiple information-flow barriers. |
|---|---|
| Item Description: | Typescript (photocopy). Vita. "Major subject: Computer Science." |
| Physical Description: | ix, 68 leaves : illustrations ; 29 cm |
| Bibliography: | Includes bibliographical references (leaves 65-67). |