Back to search

University of Victoria (Canada)

Variable ordering for ROBDD-based FPGA logic synthesis

Abstract

dc:description.abstract

The FPGA is becoming a more and more popular replacement for ASICs. Logic synthesis techniques for this technology have been adopted and modified from those used for regular ASICs. In this thesis, a technique using ROBDDs for logic synthesis for LUT-based FPGAs is investigated. The ROBDD is a useful representation for logic functions as it is a canonical form and it is relatively straight-forward to map this form to LUT-based FPGAs. A major problem with this representation, however, is that the variable ordering can have a very large effect on the size of the ROBDD. Another way of representing a function is with its autocorrelation coefficients. These provide information about areas of similarity in a function. This thesis presents methods of variable ordering for ROBDDs based on the autocorrelation coefficients of the function. The questions we investigate are whether this method of ordering consistently produces ROBDDs of a reasonable size, and whether these ROBDDs can be mapped to LUT-based FPGAs to result in a smaller number of logic blocks than on average.

Degree

thesis:*
Level thesis:degree_level
Master of Science M.Sc.
Department thesis:degree_department
Department of Computer Science
Year dc:date.issued
1995

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Crow, Jacqueline Elsie

Rights

dc:rights
Statement dc:rights
  • Available to the World Wide Web

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/1828/17568

Chain of custody

source
Harvested from
University of Victoria (Canada)
Base URL
dspace.library.uvic.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Crow, Jacqueline Elsie. Variable ordering for ROBDD-based FPGA logic synthesis. Master of Science M.Sc. thesis, 1995. https://hdl.handle.net/1828/17568