Publication detail

Space-Time Trade-offs in SW Evaluation of Boolean Functions

DVOŘÁK, V.

Original Title

Space-Time Trade-offs in SW Evaluation of Boolean Functions

English Title

Space-Time Trade-offs in SW Evaluation of Boolean Functions

Type

conference paper

Language

en

Original Abstract

Fast evaluation of multiple-output Boolean functions with the smallest memory footprint is often required in embedded systems. The paper describes a novel method of linked tables for representation and evaluation of Boolean functions and compares it with traditional methods; PLAs from the MCS-51 micro-controller are used for comparison. Traditional methods use masks to emulate PLA one way or another. The suggested method of linked tables is based on iterative disjunctive decomposition and leads only to a series of table look-ups. Linked tables are also shown to be equivalent to specific "in-line" decision diagrams. They proved to be most flexible in making trade-offs between performance and memory space. The method of linked tables may be quite useful for embedded microprocessor or microcontroller software as well as   for digital system simulation.

English abstract

Fast evaluation of multiple-output Boolean functions with the smallest memory footprint is often required in embedded systems. The paper describes a novel method of linked tables for representation and evaluation of Boolean functions and compares it with traditional methods; PLAs from the MCS-51 micro-controller are used for comparison. Traditional methods use masks to emulate PLA one way or another. The suggested method of linked tables is based on iterative disjunctive decomposition and leads only to a series of table look-ups. Linked tables are also shown to be equivalent to specific "in-line" decision diagrams. They proved to be most flexible in making trade-offs between performance and memory space. The method of linked tables may be quite useful for embedded microprocessor or microcontroller software as well as   for digital system simulation.

Keywords

Multiple-output Boolean functions, fast sw evaluation, PLA emulation, linked tables, LUT cascades

RIV year

2007

Released

23.04.2007

Publisher

IEEE Computer Society

Location

New York

ISBN

0-7695-2807-4

Book

Proceedings of The Second International Conference on Systems

Pages from

344

Pages to

349

Pages count

6

BibTex


@inproceedings{BUT28597,
  author="Václav {Dvořák}",
  title="Space-Time Trade-offs in SW Evaluation of Boolean Functions",
  annote="Fast evaluation of multiple-output Boolean functions with the smallest memory
footprint is often required in embedded systems. The paper describes a novel
method of linked tables for representation and evaluation of Boolean functions
and compares it with traditional methods; PLAs from the MCS-51 micro-controller
are used for comparison. Traditional methods use masks to emulate PLA one way or
another. The suggested method of linked tables is based on iterative disjunctive
decomposition and leads only to a series of table look-ups. Linked tables are
also shown to be equivalent to specific "in-line" decision diagrams. They proved
to be most flexible in making trade-offs between performance and memory space.
The method of linked tables may be quite useful for embedded microprocessor or
microcontroller software as well as   for digital system simulation.",
  address="IEEE Computer Society",
  booktitle="Proceedings of The Second International Conference on Systems",
  chapter="28597",
  howpublished="print",
  institution="IEEE Computer Society",
  year="2007",
  month="april",
  pages="344--349",
  publisher="IEEE Computer Society",
  type="conference paper"
}