Back to search

University of Saskatchewan

Frontiers For High-Level Synthesis of Digital Circuits

Abstract

dc:description.abstract

This thesis presents a novel approach to the synthesis of combinational and sequential digital circuits from recursive behavioral specifications based on the functional programming paradigm. Recursion removal is accomplished by computing the fixpoints of recursion equations. The techniques used for computing the fixpoints are based on domain theory and frontiers algorithms. Two-level combinational logic synthesis is a direct consequence of the application of the frontiers algorithm, which derives a correct sum-of-products expression. Multi-level logic synthesis is based on the iterative approach used for computing the fixpoints. Algorithms for common sub-expression identification and derivation of factored forms are presented. These algorithms rely on the frontiers approach, further strengthening the choice of a semantics-based approach. Sequential circuits are modeled as finite state machines. Sequential circuit synthesis uses the techniques established for combinational logic synthesis to derive the computational elements needed to realize the corresponding finite state machine. A significant advantage of the approach used here is that the structure of recursion in the original specification is immaterial for hardware synthesis, i.e. any recursive function can be synthesized without the use of a stack. Since the techniques used are semantics-based, synthesis from two denotationally equivalent specifications always results in the same two-level hardware.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy (Ph.D.)
Level thesis:degree_level
Doctoral
Discipline thesis:degree_discipline
Computer Science
Department thesis:degree_department
Computer Science
Grantor
University of Saskatchewan
Year dc:date.issued
1997

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Ghatraju, Laksmikanth
Advisor dc:contributor.advisor
  • McCrosky, C.

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/10388/11618

Chain of custody

source
Harvested from
University of Saskatchewan
Base URL
harvest.usask.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Ghatraju, Laksmikanth. Frontiers For High-Level Synthesis of Digital Circuits. Doctoral thesis, University of Saskatchewan, 1997. https://hdl.handle.net/10388/11618