LogicOpt (version 1.0.0)

logicopt: Truth Table Logic Optimization

Description

This function provides various options to optimize and analyze an input truth table that represents a sum of Boolean or multi-valued input product terms. This function leverages the powerful logic minimization algorithms from Espresso. These algorithms are a standard for optimizing large functions in digital logic synthesis and have been modified to handle general logic minimization problems to serve the R community. The input truth table is an R data frame or alteratively an Espresso format file. See examples section for more details.

Usage

logicopt(in_tt = NULL, n_in = 0, n_out = 0, find_dc = FALSE, input_sizes = NULL, exact_cover = TRUE, esp_file = "", mode = "espresso")

Arguments

in_tt

An R data frame table representing a sum of product terms (PTs) truth table. The PTs have one or more inputs with a positive integer value or a "-" which means the input is not specified. The outputs are Boolean and have possible values 1, 0, "-", or "~" and specify that the corresponding PT is part of the ON set, the OFF set, the DC (don't care) set, or is unspecified (not a part of any set) respectively. PTs should not be in both the ON set and OFF set. When logicopt optimizes, it attempts to find the fewest number of PTs in the ON set and uses PTs in the DC set to further reduce the solution.

n_in

Integer number of input columns in the truth table. Inputs must come first in the truth table.

n_out

Integer number of output columns in the truth table. Outputs must come after the n_in inputs of the truth table. The number of columns in the in_tt must be n_in + n_out.

find_dc

FALSE (default) means any unspecified input conditions are added to the OFF set for that output. TRUE means that any unspecified input conditions are added to DC set for that output. The DC set is used to further optimize the ON set. Don't cares can also be explicitly defined by using "-" for the output in the input truth table.

input_sizes

Integer vector which represents the number of possible values for each input. Default is NULL which means the size for each input will be determined automatically by the software by analyzing the input truth table and counting the number of values used. Specifying input_sizes is important when the input table has unspecified ("-") or unused input values and all possible values are not used.

exact_cover

Do an exact covering of prime implicant table. Option applies to QM based algorithms (mode = "qm", "multi-min", and "multi-full"). If FALSE, the covering algoirthm is heuristic and runs faster but may not find an exact solution. If TRUE, algorithm is exact and finds an exact minimum solution. Default is TRUE.

esp_file

File name for espresso format file to read and process. If esp_file is specified, the input truth table options (in_tt, n_in, n_out, input_sizes, and find_dc) are ignored. The mode and exact_cover options still apply.

mode

A string that specifies the mode to use for optimization:

• "espresso" -- Use the classic espresso algorithm to optimize the input truth table in_tt or the espresso format table in esp_file. Returns a single solution of the optimized ON set. This option should be used for very large truth tables.
• "qm" -- Use Quine-McCluskey (QM) algorithm to optimize in_tt or esp_file and return a single solution of the optimized ON set. Use with caution for large truth tables.
• "primes" -- Return set of prime implicants for in_tt or esp_file. Three solutions are returned in a single truth table. These represent the ESSENTIAL PRIMES, the PARTIALLY REDUNDANT PRIMES, and the TOTALLY REDUNDANT PRIMES. Use the print_primes_tt function to print the results.
• "multi-min" -- Use QM to find the minimum set of non-redundant solutions that cover all the ESSENTIAL PRIMES and the minimal set of PARTIALLLY REDUNDANT PRIMES. Solutions are ordered by size. The number of solutions found is capped at 50.
• "multi-full" -- Find additional coverings of prime implicants beyond what is found in multi-min. A exhaustive covering of all PARTIALLY REDUNDANT PRIMES is found. The number of solutions is capped at 50.
• "echo" -- Echo the ON, OFF, and DC sets for the in_tt or esp_file truth table without any optimization. Note the resulting truth table can be extremely large because it will cover the complete Boolean (or MV) space for all inputs and outputs. Use with caution.

Value

The logicopt function returns a list of two items: an truth table and a vector. The vector represents the size and number of solutions in the output truth table. For example, a vector [10] means there is a single solution in the truth table which has 10 rows. A vector [5 8 2] means there are three solutions in the truth table with 5, 8, and 2 rows respectively.

Examples

######################### EXAMPLE #1 ###############################
# create a truth table with 4 inputs A, B, C, D and 2 outputs X and Y
e.ex1 <- data.frame(
 A = c(0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1), 
 B = c(0,0,0,0,1,1,1,1,1,1,1,1,0,0,0,0), 
 C = c(0,0,1,1,0,0,1,1,0,0,1,1,0,0,1,1), 
 D = c(0,1,1,0,0,1,1,0,0,1,1,0,0,1,1,0), 
 X = c(1,1,1,1,0,1,1,1,"-",1,1,0,1,1,0,0), 
 Y = c("-",1,1,1,1,1,1,1,1,1,1,0,0,0,0,"-"))

# show the unoptimized equations
tt2eqn(e.ex1,4,2)

# optimize the truth table
tte <- logicopt(e.ex1,4,2)

# show the optimized equations
tt2eqn(tte[[1]],4,2)

# generate and print the prime implicants from optimized tte
ttp <- logicopt(tte[[1]],4,2,mode="primes")
print_primes_tt(ttp,TRUE,4,2)

######################### EXAMPLE #2 ###############################
# get path to an espresso format file 
file <- system.file("extdata/espresso/small2.esp", package="LogicOpt")

# get the espresso truth table without optimization
small2 <- logicopt(esp_file=file,mode="echo")

# print the unoptimized equations
print_multi_tt(small2,TRUE,4,3)

# optimize with espresso algorithm 
small2_opt <- logicopt(small2[[1]],4,3,mode="espresso")

# print the optimized equations
print_multi_tt(small2_opt,TRUE,4,3)

######################### EXAMPLE #3 ###############################
# load up truth table created from a QCA dataset 
data(l.represent.1)

# read documentation on how truth table was created 
?l.represent.1

# find the set of minimum solutions that cover QCA dataset (mode="multi-min")
# treat unspecified input conditions as don't cares (find_dc=TRUE)
# find a exact covering (exact_cover=TRUE)
lomm <- logicopt(l.represent.1,n_in=5,n_out=1,find_dc=TRUE,
  exact_cover=1,mode="multi-min")

# print the solutions in equation format
print_multi_tt(lomm,TRUE,5,1,QCA=TRUE)

######################### EXAMPLE #4 ###############################
# optimize a truth table from Genetic Programming  
inpath <- system.file("extdata/espresso/robot1_in.esp", package="LogicOpt")
robot1 <- logicopt(esp_file=inpath,mode="echo")

# unoptimized truth table has 273 rows (256 in ON set and 18 in OFF set)
robot1[2]

# optimize l.robot1
robot1_opt <- logicopt(robot1[[1]],8,3)

# optimized results have 13 rows that cover outputs zero, one, and minus
robot1_opt[2]

# print optimized equations (where each output is 1)
print_multi_tt(robot1_opt,TRUE,8,3)

######################### EXAMPLE #5 ###############################
# show how to use input_sizes 

# get vector of number of unique values for each input 
data(l.partybans.1)
pb_in_vals <- num_input_values(l.partybans.1,5) 
pb_in_vals

# optimize with mode=espresso
epb <- logicopt(l.partybans.1,5,1,find_dc=TRUE,mode="espresso")
epb
pb_in_opt_vals <- num_input_values(epb[[1]],5) 

# note how some input values have been optimized away and are no longer used! 
pb_in_opt_vals

# we need original input sizes to process the optimized truth table 
qmpb <- logicopt(epb[[1]],5,1,find_dc=FALSE, input_sizes=pb_in_vals,mode="qm")
print_multi_tt(epb,TRUE,5,1)
print_multi_tt(qmpb,TRUE,5,1)