Publication Details

Time- and Space-Efficient Evaluation of Sparse Boolean Functions in Embedded Software

DVOŘÁK, V. Time- and Space-Efficient Evaluation of Sparse Boolean Functions in Embedded Software. Proceedings of 14th Annual IEEE International Conference and Workshops on the Engineering of Computer-Based Systems. Los Alamitos: IEEE Computer Society, 2007. p. 178-185. ISBN: 0-7695-2772-8.
Czech title
Časově a prostorově účinné vyhodnocování řídkých boolovských funkcí vestavěným software
Type
conference paper
Language
English
Authors
Dvořák Václav, prof. Ing., DrSc.
Keywords

Multiple-output Boolean functions, software implementation, linked tables, LUT
cascades,  heuristic BDD minimization

Abstract

The paper addresses software implementation of large sparse systems of Boolean
functions. Fast evaluation of such functions with the smallest memory consumption
is often required in embedded systems. A new heuristic method of obtaining
compact representation of sparse Boolean functions in a form of linked tables is
described that can be used for BDD minimization as well. Evaluation of Boolean
functions reduces to multiple indirect memory accesses. The method is compared to
other techniques like a walk through a BDD or a list search and is illustrated on
examples. The presented method is flexible in making trade-offs between
performance and memory consumption and may be thus useful for embedded
microprocessor or microcontroller software.

Published
2007
Pages
178–185
Proceedings
Proceedings of 14th Annual IEEE International Conference and Workshops on the Engineering of Computer-Based Systems
Conference
14th IEEE Conference and Workshop on Engineering of Computer Based Systems, Tuscon, Arizona, USA, US
ISBN
0-7695-2772-8
Publisher
IEEE Computer Society
Place
Los Alamitos
BibTeX 
@inproceedings{BUT28595,
  author="Václav {Dvořák}",
  title="Time- and Space-Efficient Evaluation of Sparse Boolean Functions in Embedded Software",
  booktitle="Proceedings of 14th Annual IEEE International Conference and Workshops on the Engineering of Computer-Based Systems",
  year="2007",
  pages="178--185",
  publisher="IEEE Computer Society",
  address="Los Alamitos",
  isbn="0-7695-2772-8",
  url="https://www.fit.vut.cz/research/publication/8324/"
}
Files
Back to top