Good Layouts for Pattern Recognizers

Abstract

A system to lay out custom circuits that recognize regular languages can be a useful VLSI design automation tool. This paper describes the algorithms used in an implementation of a regular expression compiler. Layouts that use a network of programmable logic arrays (PLA's) have smaller areas than those of some other methods, but there are the problems of partitioning the circuit and then placing the individual PLA's. Regular expressions have a structure which allows a novel solution to these problems: dynamic programming can be used to find layouts which are in some sense optimal. Various search pruning heuristics have been used to increase the speed of the compiler, and the experience with these is reported in the conclusions. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Aug 01, 1981
Accession Number
ADA109324

Entities

People

  • Howard W. Trickey

Organizations

  • Stanford University

Tags

Communities of Interest

  • Advanced Electronics
  • C4I

DTIC Thesaurus Topics

  • Algorithms
  • Aspect Ratio
  • Compilers
  • Computer Programming
  • Computer Science
  • Computers
  • Dictionaries
  • Dynamic Programming
  • Heuristic Methods
  • Language
  • Pattern Recognition
  • Trees (Data Structures)

Fields of Study

  • Engineering

Readers

  • Computational Linguistics
  • Integrated Circuit Design and Technology.
  • Operations Research