JOURNAL OF SOFTWARE (JSW)
ISSN : 1796-217X
Volume : 2    Issue : 5    Date : November 2007

Efficient Evaluation of Multiple-Output Boolean Functions in Embedded Software or Firmware
Vaclav Dvorak
Page(s): 52-63
Full Text:
PDF (608 KB)


Abstract
The paper addresses software and firmware implementation of multiple-output Boolean functions
based on cascades of Look-Up Tables (LUTs). A LUT cascade is described as a means of
compact representation of a large class of sparse Boolean functions, evaluation of which then
reduces to multiple indirect memory accesses. The method is compared to a technique of direct
PLA emulation and is illustrated on examples. A specialized micro-engine is proposed for even
faster evaluation than is possible with universal microprocessors. The presented method is flexible
in making trade-offs between performance and memory footprint and may be useful for embedded
applications where the processing speed is not critical. Evaluation may run on various CPUs and
DSP cores or slightly faster on FPGA-based micro-programmed controllers.

Index Terms
Embedded software, Boolean function evaluation, Binary Decision Diagrams, LUT cascades