OKlibrary  0.2.1.6
Espresso.hpp File Reference

Documentation on how to build and use Espresso. More...

Go to the source code of this file.


Detailed Description

Documentation on how to build and use Espresso.

Installing Espresso

On the purpose of Espresso

Espresso is a program for the computation of small CNF/DNF representations of boolean functions.

Package history

What the installation yields

  • The executable espresso2.3.
  • Some documentation in directory /home/csoliver/OKplatform/system_directories/doc/internet_html/doc/doc/Boolean/Espresso/espresso-2.3.

Current state of installation

  • Recommended version = 2.3
  • Path to the executable:
    1. espresso program call = /home/csoliver/OKplatform/ExternalSources/Installations/Boolean/Espresso/2.3/espresso
    2. A symbolic link espresso2.3 is provided in the public bin-directory (/home/csoliver/OKplatform/bin).
  • Checking the installation:
    • Ready: YES
    • location = /home/csoliver/OKplatform/ExternalSources/Installations/Boolean/Espresso/2.3/espresso
    • version = 2.3

How to install

Make targets

espresso Build the recommended version of espresso, using the local gcc.
cleanespresso Remove the build directory.
cleanallespresso Remove build, installation and documentation directory.

Configuration

  • To install a different version, set variable espresso_recommended_version_number_okl accordingly.

Usage

  • Use espresso filename, where the file contains a boolean function in the (extended) PLA-format.
  • An example is to use the following "test.pla" file (see below) with espresso
    .i 3
    .o 1
    110 1
    111 1
    010 1
    001 0
    000 0
    100 1
    011 0
    101 0
       
    by calling
    > espresso2.3 test.pla
    .i 3
    .o 1
    .p 3
    1-0 1
    -10 1
    11- 1
    .e
      
  • The PLA file is a format for describing finite functions with a particular emphasis on boolean functions.
  • For simple usage one can assume that the ".i" line specifies the number of input variables, the ".o" line the number of output variables, and then each line specifies the entry in a truth table describing the associated boolean function.
  • If an entry is marked with a "-", this is simply shorthand for the expansion into multiple truth table entries where the "-" values take every possibility but the rest of the values remain unchanged.
  • For more information on the PLA format, see below or refer to the Espresso documentation at ExternalSources/sources/Boolean/Espresso/espresso.5.html .

The PLA format

  • A PLA file represents a partial finite function, f : {0,1}^n -> {0,1}^m, by encoding the DNF of the relational viewpoint of f.
  • By the relational viewpoint, we mean representing the boolean function which takes both input and output bits and returns true iff f maps the given input to the given output. More precisely, representing f' : {0,1}^(n+m) -> {0,1} such that f'((I,O)) = 1 if f(I) = O.
  • The "header" of the PLA file:
    • The number of input and output variables are specified first with lines of the form:
      .i n
      .o m
           
      where n and m are the positive integer number of input and output variables.
    • Additional lines such as ".type" (discussed below), and others discussed in the documentation, may also be specified in the "header" of the file.
  • The "clauses":
    • Each line after the header is:
      1. a sequence of characters I in {1,0,-} of size n; followed by
      2. a space; followed by
      3. a sequence of characters O in {1,0,-} of size m.
      where:
      • Each line encodes a DNF clause which is part of a DNF representation for the partial finite function using the relational viewpoint.
      • That is, each line encodes that f(I') = O', where I' and O' are the boolean vectors corresponding to the strings I and O for that line.
      • A "-" in I indicates that f(I') = O' for both values of the corresponding variable.
      • A "-" in O indicates that f(I') = O' but the output value, for the variable the "-" corresponds to, is undefined.
  • Additional options:
    • ".type X": specifies how to interpret total assignments left unspecified, where X is one of the following:
      • "f": unspecified assignments and those with undefined ouputs are assumed to be false (0).
      • "r": unspecified assignments and those with undefined outputs are assumed to be true (1).
      • "fd": unspecified assignments are assumed to be false (the default for espresso).
      • "fr": unspecified assignments are considered to be "don't care" values.
      • "fdr": there should be no unspecified values.
    • The PLA standard also allows one to provide names for variables, as well as other options which give Espresso information on how to minimise the finite function provided. These options are discussed in
  • Lines in a PLA file starting with the "#" symbol are comments.
  • Note here that there is a difference between "undefined" and "unspecified".
  • One can use "-" for an output bit to explicitly specify that the partial finite function defined by the PLA is undefined for the corresponding input bits. A total assignment is unspecified if there is no line in the PLA which defines its value (or "undefinedness").
  • The function output_fcl2pla is available at the Maxima level to translate a clause-set to a PLA file.
  • The PLA format also supports defining "multi-valued functions".
  • For more information, see the "the Espresso documentation at ExternalSources/sources/Boolean/Espresso/espresso.5.html with additional information in ExternalSources/sources/Boolean/Espresso/man_octtools_espresso.html.

Examples

  • The DNF {{1,2,3},{-1,4,-5}} becomes
    .i 5
    .o 1
    111-- 1
    0--10 1
       
  • The two bit adder (from the espresso documentation):
    # 2-bit by 2-bit binary adder (with no carry input)
    .i 4
    .o 3
    0000  000
    0001  001
    0010  010
    0011  011
    0100  001
    0101  010
    0110  011
    0111  100
    1000  010
    1001  011
    1010  100
    1011  101
    1100  011
    1101  100
    1110  101
    1111  110
       

Definition in file Espresso.hpp.