Input file format for Espresso (PLA-file)
espresso(5)
DESCRIPTION
Espresso accepts as input a two-level description of a
Boolean function. This is described as a character matrix
with keywords embedded in the input to specify the size of
the matrix and the logical format of the input function.
Programs exist to translate a set of equations into this
format (e.g., eqntott(1OCTTOOLS), bdsyn(1OCTTOOLS), eqnto
pla(1OCTTOOLS)). This manual page refers to Version 2.3
of Espresso.
Comments are allowed within the input by placing a pound
sign (#) as the first character on a line. Comments and
unrecognized keywords are passed directly from the input
file to standard output. Any white-space (blanks, tabs,
etc.), except when used as a delimiter in an embedded com
mand, is ignored. It is generally assumed that the PLA is
specified such that each row of the PLA fits on a single
line in the input file.
KEYWORDS
The following keywords are recognized by espresso. The
list shows the probable order of the keywords in a PLA
description. [d] denotes a decimal number and [s] denotes
a text string. The minimum required set of keywords is .i
and .o for binary-valued functions, or .mv for multiple-
valued functions.
.i [d] Specifies the number of input variables.
.o [d] Specifies the number of output functions.
.mv [num_var] [num_binary_var] [d1] . . . [dn]
Specifies the number of variables (num_var),
the number of binary variables
(num_binary_var), and the size of each of the
multiple-valued variables (d1 through dn).
.ilb [s1] [s2] . . . [sn]
Gives the names of the binary valued vari
ables. This must come after .i and .o (or
after .mv). There must be as many tokens fol
lowing the keyword as there are input vari
ables.
.ob [s1] [s2] . . . [sn]
Gives the names of the output functions. This
must come after .i and .o (or after .mv).
There must be as many tokens following the
keyword as there are output variables.
.label var=[d] [s1] [s2] ...
Specifies the names of the parts of a multi
ple-valued variable. This must come after
.mv. There must be as many tokens following
the keyword as there are parts for this vari
able. Note that the variables are numbered
starting from 0.
.type [s] Sets the logical interpretation of the charac
ter matrix as described below under "Logical
Description of a PLA". This keyword must come
before any product terms. [s] is one of f, r,
fd, fr, dr, or fdr.
.phase [s] [s] is a string of as many 0's or 1's as there
are output functions. It specifies which
polarity of each output function should be
used for the minimization (a 1 specifies that
the ON-set of the corresponding output func
tion should be used, and a 0 specifies that
the OFF-set of the corresponding output func
tion should be minimized).
.pair [d] Specifies the number of pairs of variables
which will be paired together using two-bit
decoders. The rest of the line contains pairs
of numbers which specify the binary variables
of the PLA which will be paired together. The
binary variables are numbered starting with 0.
The PLA will be reshaped so that any unpaired
binary variables occupy the leftmost part of
the array, then the paired multiple-valued
columns, and finally any multiple-valued vari
ables. If the labels have been specified
using .ilb, then the variable names may be
used instead of the column number.
.symbolic [s0] [s1] . . . [sn] ; [t0] [t1] . . . [tm] ;
Specifies that the binary-valued variables
named [s0] thru [sn] are to be considered as a
single multiple-valued variable. Variable
[s0] is considered the most significant bit,
[s1] the next most significant, and [sn] is
the least significant bit. This creates a
variable with 2**n parts corresponding to the
decodes of the binary-valued variables. The
keywords [t0] thru [tm] provide the labels for
each decode of [s0] thru [sn]. ([t0] corre
sponds to a value of 00...00, [t1] is the
value 00...01, etc.). The binary-variables
may be identified by column number, or by
variable name when .ilb is used. The binary-
variables are removed from the function after
the multiple-valued variable is created.
.symbolic-output [s0] [s1] . . . [sn] ; [t0] [t1] . . .
[tm] ;
Specifies that the output functions [s0] ...
[sn] are to be considered as a single symbolic
output. This creates 2**n more output vari
ables corresponding to the possible values of
the outputs. The outputs may be identified by
number (starting from 0), or by variable name
when .ob is used. The outputs are removed
from the function after the new set of outputs
is created.
.kiss Sets up for a kiss-style minimization.
.p [d] Specifies the number of product terms. The
product terms (one per line) follow immedi
ately after this keyword. Actually, this line
is ignored, and the ".e", ".end", or the end
of the file indicate the end of the input
description.
.e (.end) Optionally marks the end of the PLA descrip
tion.
LOGICAL DESCRIPTION OF A PLA
When we speak of the ON-set of a Boolean function, we mean
those minterms which imply the function value is a 1.
Likewise, the OFF-set are those terms which imply the
function is a 0, and the DC-set (don't care set) are those
terms for which the function is unspecified. A function
is completely described by providing its ON-set, OFF-set
and DC-set. Note that all minterms lie in the union of
the ON-set, OFF-set and DC-set, and that the ON-set, OFF-
set and DC-set share no minterms.
The purpose of the espresso minimization program is to
find a logically equivalent set of product-terms to repre
sent the ON-set and optionally minterms which lie in the
DC-set, without containing any minterms of the OFF-set.
A Boolean function can be described in one of the follow
ing ways:
1) By providing the ON-set. In this case, espresso
computes the OFF-set as the complement of the ON-
set and the DC-set is empty. This is indicated
with the keyword .type f in the input file.
2) By providing the ON-set and DC-set. In this case,
espresso computes the OFF-set as the complement of
the union of the ON-set and the DC-set. If any
minterm belongs to both the ON-set and DC-set, then
it is considered a don't care and may be removed
from the ON-set during the minimization process.
This is indicated with the keyword .type fd in the
input file.
3) By providing the ON-set and OFF-set. In this case,
espresso computes the DC-set as the complement of
the union of the ON-set and the OFF-set. It is an
error for any minterm to belong to both the ON-set
and OFF-set. This error may not be detected during
the minimization, but it can be checked with the
subprogram "-Dcheck" which will check the consis
tency of a function. This is indicated with the
keyword .type fr in the input file.
4) By providing the ON-set, OFF-set and DC-set. This
is indicated with the keyword .type fdr in the
input file.
If at all possible, espresso should be given the DC-set
(either implicitly or explicitly) in order to improve the
results of the minimization.
A term is represented by a "cube" which can be considered
either a compact representation of an algebraic product
term which implies the function value is a 1, or as a rep
resentation of a row in a PLA which implements the term.
A cube has an input part which corresponds to the input
plane of a PLA, and an output part which corresponds to
the output plane of a PLA (for the multiple-valued case,
see below).
SYMBOLS IN THE PLA MATRIX AND THEIR INTERPRETATION
Each position in the input plane corresponds to an input
variable where a 0 implies the corresponding input literal
appears complemented in the product term, a 1 implies the
input literal appears uncomplemented in the product term,
and - implies the input literal does not appear in the
product term.
With type f, for each output, a 1 means this product term
belongs to the ON-set, and a 0 or - means this product
term has no meaning for the value of this function. This
type corresponds to an actual PLA where only the ON-set is
actually implemented.
With type fd (the default), for each output, a 1 means
this product term belongs to the ON-set, a 0 means this
product term has no meaning for the value of this func
tion, and a - implies this product term belongs to the DC-
set.
With type fr, for each output, a 1 means this product term
belongs to the ON-set, a 0 means this product term belongs
to the OFF-set, and a - means this product term has no
meaning for the value of this function.
With type fdr, for each output, a 1 means this product
term belongs to the ON-set, a 0 means this product term
belongs to the OFF-set, a - means this product term
belongs to the DC-set, and a ~ implies this product term
has no meaning for the value of this function.
Note that regardless of the type of PLA, a ~ implies the
product term has no meaning for the value of this func
tion. 2 is allowed as a synonym for -, 4 is allowed for
1, and 3 is allowed for ~.
MULTIPLE-VALUED FUNCTIONS
Espresso will also minimize multiple-valued Boolean func
tions. There can be an arbitrary number of multiple-val
ued variables, and each can be of a different size. If
there are also binary-valued variables, they should be
given as the first variables on the line (for ease of
description). Of course, it is always possible to place
them anywhere on the line as a two-valued multiple-valued
variable. The function size is described by the embedded
option .mv rather than .i and .o.
A multiple-output binary function with ni inputs and no
outputs would be specified as .mv ni+1 ni no. .mv cannot
be used with either .i or .o - use one or the other to
specify the function size.
The binary variables are given as described above. Each
of the multiple-valued variables are given as a bit-vector
of 0 and 1 which have their usual meaning for multiple-
valued functions. The last multiple-valued variable (also
called the output) is interpreted as described above for
the output (to split the function into an ON-set, OFF-set
and DC-set). A vertical bar | may be used to separate the
multiple-valued fields in the input file.
If the size of the multiple-valued field is less than
zero, than a symbolic field is interpreted from the input
file. The absolute value of the size specifies the maxi
mum number of unique symbolic labels which are expected in
this column. The symbolic labels are white-space delim
ited strings of characters.
To perform a kiss-style encoding problem, the keyword
.kiss should be included in the file. The third to last
variable on the input file must be the symbolic "present
state", and the second to last variable must be the "next
state". As always, the last variable is the output. The
symbolic "next state" will be hacked to be actually part
of the output.
EXAMPLE #1
A two-bit adder which takes in two 2-bit operands and pro
duces a 3-bit result can be described completely in
minterms as:
# 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
It is also possible to specify some extra options, such
as:
# 2-bit by 2-bit binary adder (with no carry input)
.i 4
.o 3
.ilb a1 a0 b1 b0
.ob s2 s1 s0
.pair 2 (a1 b1) (a0 b0)
.phase 011
0000 000
0001 001
0010 010
.
.
.
1111 110
.e
The option .pair indicates that the first binary-valued
variable should be paired with the third binary-valued
variable, and that the second variable should be paired
with the fourth variable. The function will then be
mapped into an equivalent multiple-valued minimization
problem.
The option .phase indicates that the positive-phase should
be used for the second and third outputs, and that the
negative phase should be used for the first output.
EXAMPLE #2
This example shows a description of a multiple-valued
function with 5 binary variables and 3 multiple-valued
variables (8 variables total) where the multiple-valued
variables have sizes of 4 27 and 10 (note that the last
multiple-valued variable is the "output" and also encodes
the ON-set, DC-set and OFF-set information).
.mv 8 5 4 27 10
.ilb in1 in2 in3 in4 in5
.label var=5 part1 part2 part3 part4
.label var=6 a b c d e f g h i j k l m n
o p q r s t u v w x y z a1
.label var=7 out1 out2 out3 out4 out5 out6
out7 out8 out9 out10
0-010|1000|100000000000000000000000000|0010000000
10-10|1000|010000000000000000000000000|1000000000
0-111|1000|001000000000000000000000000|0001000000
0-10-|1000|000100000000000000000000000|0001000000
00000|1000|000010000000000000000000000|1000000000
00010|1000|000001000000000000000000000|0010000000
01001|1000|000000100000000000000000000|0000000010
0101-|1000|000000010000000000000000000|0000000000
0-0-0|1000|000000001000000000000000000|1000000000
10000|1000|000000000100000000000000000|0000000000
11100|1000|000000000010000000000000000|0010000000
10-10|1000|000000000001000000000000000|0000000000
11111|1000|000000000000100000000000000|0010000000
.
.
.
11111|0001|000000000000000000000000001|0000000000
EXAMPLE #3
This example shows a description of a multiple-valued
function setup for kiss-style minimization. There are 5
binary variables, 2 symbolic variables (the present-state
and the next-state of the FSM) and the output (8 variables
total).
.mv 8 5 -10 -10 6
.ilb io1 io0 init swr mack
.ob wait minit mrd sack mwr dli
.type fr
.kiss
--1-- - init0 110000
--1-- init0 init0 110000
--0-- init0 init1 110000
--00- init1 init1 110000
--01- init1 init2 110001
--0-- init2 init4 110100
--01- init4 init4 110100
--00- init4 iowait 000000
0000- iowait iowait 000000
1000- iowait init1 110000
01000 iowait read0 101000
11000 iowait write0 100010
01001 iowait rmack 100000
11001 iowait wmack 100000
--01- iowait init2 110001
--0-0 rmack rmack 100000
--0-1 rmack read0 101000
--0-0 wmack wmack 100000
--0-1 wmack write0 100010
--0-- read0 read1 101001
--0-- read1 iowait 000000
--0-- write0 iowait 000000
EXAMPLE 4
This example shows the use of the .symbolic keyword to
setup a multiple-valued minimization problem.
.i 15
.o 4
.ilb SeqActive<0> CacheOp<6> CacheOp<5> CacheOp<4>
CacheOp<3> CacheOp<2> CacheOp<1> CacheOp<0>
userKernel<0> Protection<1> Protection<0>
cacheState<1> cacheState<0> PageDirty<0>
WriteCycleIn<0>
.ob CacheBusy<0> dataMayBeValid<0> dataIsValid<0>
WriteCycleOut<0>
.symbolic CacheOp<6> CacheOp<5> CacheOp<4> CacheOp<3>
CacheOp<2> CacheOp<1> CacheOp<0> ;
FET NA PHY_FET PR32 PRE_FET PW32 RA32 RD32
RD64 RDCACHE RFO32 RFO64 TS32 WR32 WR64 WRCACHE ;
.symbolic Protection<1> Protection<0> ;
PROT_KRO_UNA PROT_KRW_UNA PROT_KRW_URO PROT_KRW_URW ;
.symbolic cacheState<1> cacheState<0> ;
CS_Invalid CS_OwnPrivate CS_OwnShared CS_UnOwned ;
.p 22
0000001--010110 0001
0000001-1-00110 0001
00001011-01011- 0100
000010111-0011- 0100
0000--001--01-- 0100
0000-10--0-1--- 0100
0000-10-1--1--- 0100
00000-0--0-1--- 0100
00000-0-1--1--- 0100
0000-10--0--1-- 0100
0000-10-1---1-- 0100
00000-0--0--1-- 0100
00000-0-1---1-- 0100
---1----------- 1000
--1------------ 1000
-1------------- 1000
1-------------- 1000
-------0------- 1000
----1---------- 1000
-----0--------- 1000
------0-------- 1000
--------------1 1110
.e