Accession Number:

ADA109324

Title:

Good Layouts for Pattern Recognizers

Descriptive Note:

Corporate Author:

STANFORD UNIV CA DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1981-08-01

Pagination or Media Count:

16.0

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 PLAs have smaller areas than those of some other methods, but there are the problems of partitioning the circuit and then placing the individual PLAs. 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

Subject Categories:

  • Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE