Getting Started with Logic Synthesis

Sum-of-products and product-of-sums expressions are common solutions to Boolean problems, but often they are far from parsimonious solutions. On the other hand, limiting oneself to the use of just AND-OR-NOT might not be the right approach to finding good solutions to more complex problems. With GeneXproTools you can use an extremely wide spectrum of logical functions (a total of 258 built-in functions plus all kinds of user defined functions) to design your logic circuits. And, for instance, if you are just interested in NAND-only or NOR-only circuits, you might try and find a solution to your problem using just this particular function instead of applying De Morgan's theorem to your sum-of-products solutions to design your circuits: as is often the case a more parsimonious expression can be found. And if you are interested in less conventional circuits, say a MUX-only circuit or a AND-XOR-NOT circuit, GeneXproTools has no problems working with just these functions to build your circuits. In this tutorial we briefly introduce the most important tools you have at your disposal in GeneXproTools to design all kinds of minimal logic circuits.

Loading Data (Truth Tables)

Data Sources & Formats

Loading Data Step-by-Step

Choosing the Fitness Function

Choosing the Function Set

Built-in Logical Functions

Built-in Logical Systems

User Defined Functions

Creating Derived Inputs/Variables

Exploring the Learning Algorithms

Monitoring the Modeling Process

Simplifying Logic Circuits

Model Evaluation & Testing

Comparing Actual & Predicted Values

Evaluating Performance

Modeling from Seed Circuits

Adding a Neutral Gene

Complexity Increase Engine

Generating the Model Code

Visualizing Logic Circuits as Expression Trees

Generating Code Automatically Using Built-in Grammars

Generating Code Automatically Using User Defined Grammars

Loading Data (Truth Tables)

Before designing a logic circuit with GeneXproTools you must first load the truth tables for the learning algorithm. The data screening engine of GeneXproTools checks the validity of all the truth tables and is operative every time you load your truth tables either for training or testing. Only the values of False and True (case insensitive) or "0" and "1" are valid as input.

GeneXproTools allows you to import your truth tables from Excel & databases, text files and GeneXproTools files.

Excel Files & Databases

The loading of data from Excel/databases requires making a connection with Excel/database and then selecting the worksheets or columns of interest. By default GeneXproTools will set the last column as the output or response variable, but you can easily set any of the other columns as response variable by selecting the variable of interest and then checking Response in the context menu.

Only the values of False and True (case insensitive) or "0" and "1" are valid as input. Note, however, that GeneXproTools uses 0's and 1's internally and, therefore, False and True are respectively converted into "0" and "1" and shown in this format.

For text files GeneXproTools supports three commonly used data matrix formats. The first is the standard Records x Variables (Response Last) format where records are in rows and variables in columns, with the output or response variable occupying the last column. In the small example below with eight records, Y is the function output and A, B, and C are the input or predictor variables:

A B C Y
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1

And the second is the Gene Expression Matrix format commonly used in DNA microarrays studies where records are in columns and variables in rows, with the function output occupying the first row. For instance, in Gene Expression Matrix format, the truth table above corresponds to:

Y 0 0 0 1 0 1 1 1
A 0 0 0 0 1 1 1 1
B 0 0 1 1 0 0 1 1
C 0 1 0 1 0 1 0 1

This kind of format is the standard for datasets with a relatively small number of records and thousands of variables. Note, however, that this format is not supported for Excel files and if your data is kept in this format in Excel, you must copy it to a text file and then use this file to load your data into GeneXproTools.

GeneXproTools uses the Records x Variables format internally and therefore all kinds of input format are automatically converted and shown in this format in the Data Panel and Scoring Panel.

GeneXproTools supports the standard separators (space, tab, comma, semicolon, and pipe) and detects them automatically. The use of labels to identify your variables is optional and GeneXproTools also detects automatically whether they are present or not. However, if you use them you will be able to generate more intelligible code with each variable clearly identified by its name.

GeneXproTools Files

GeneXproTools files can be very convenient to use as data source as they allow the selection of exactly the same datasets used in a particular run. This can be very useful especially if you want to use the same datasets across different runs.

Loading Data Step-by-Step

To Load Input Data for Modeling

1. Click the File Menu and then choose New.
   The New Run Wizard appears. You must give a name to your new run file (the default filename extension of GeneXproTools run files is .gep) and then choose Logic Synthesis in the Problem Category box and the kind of source file in the Data Source Type box. GeneXproTools allows you to work both with Excel & databases, text files and gep files.
2. Then go to the Entire Dataset (or Training Set) window by clicking the Next button.
   Choose the path for the dataset by browsing the Open dialog box and choose the appropriate data matrix format. Irrespective of the data format used, GeneXproTools shows the loaded data in the standard Records x Variables (Response Last) format, with the output variable occupying the last column.
3. Then go to the Validation/Test Data window by clicking the Next button.
   Repeat the same steps of the previous point if you wish to use a specific validation/test set. The loading of a specific validation/test set is optional as GeneXproTools allows you to split your data into different datasets for training and testing/validation in the Dataset Partitioning window.
4. Click the Finish button to save your new run file.
   The Save As dialog box appears and after choosing the directory where you want your new run file to be saved, the GeneXproTools modeling environment appears. Then you just have to click the Start button to create a logic circuit as GeneXproTools automatically chooses from a gallery of templates default settings that will enable you to evolve a logic circuit with just a click.

Choosing the Fitness Function

For Logic Synthesis problems, in the Fitness Function Tab of the Settings Panel you have access to a a total of 21 built-in fitness functions, most of which combine multiple objectives, such as the use of different reference simple models, cost matrix, parsimony pressure, variable pressure, and a few more.

Additionally, you can also design your own custom fitness functions and explore the solution space with them. By clicking the Edit Custom Fitness button, the Custom Fitness Editor is opened and there you can write the code of your fitness function in JavaScript.

The kind of fitness function you choose will depend most probably on the cost function or error measure you are most familiar with. And although there is nothing wrong with this, for all of them can accomplish an efficient evolution, you might want to try different fitness functions for they travel the fitness landscape differently: some of them very straightforwardly in their pursuits while others choose less travelled paths, considerably enhancing the search process.

Choosing the Function Set

GeneXproTools allows you to choose your function set from a total of 258 built-in logical functions and an unlimited number of custom functions, designed using the JavaScript language in the GeneXproTools environment.

GeneXproTools offers a total of 258 built-in logical functions, including all the Boolean functions with one and two inputs, 92 functions with three inputs, and 146 functions with four inputs. This wide set of logical functions opens new doors to the creation of new logic circuits that might then be automatically redesigned using specific kinds of gates (All Gates, Not-And-Or Only, Nand Only, Nor Only, Mux System, Reed-Muller System) thanks to the built-in Logical Systems of GeneXproTools.

Sum-of-products and product-of-sums expressions are common solutions to Boolean problems, but often they are far from parsimonious solutions. On the other hand, limiting oneself to the use of just AND-OR-NOT might not be the right approach to finding good solutions to more complex problems or you might just be interested in a different kind of circuit. The broad palette of GeneXproTools functions offers you unlimited possibilities in terms of design. For instance, if you are just interested in NAND-only or NOR-only circuits, you might try and find a solution to your problem using just this particular function instead of applying De Morgan's theorem to your sum-of-products solutions to design your circuits, as most of the time a more parsimonious expression can be found if the circuit is built from scratch using these gates. And if you are interested in less conventional circuits, say a MUX-only circuit or a AND-XOR-NOT circuit, GeneXproTools has no problems working with just these functions to build your circuits, as it has no bias towards particular sets of functions.

For some problems, the basic Boolean operators AND-OR-NOT are more than enough to create elegant and efficient solutions. But for other problems more complex functions are necessary to discover more efficient circuits and when inside knowledge of the problem at hand is not producing the expected results, it might be interesting to experiment with different combinations of functions. The Function Selection Tools of GeneXproTools help you with experimenting with different function sets very quickly either through the Random button in the Functions Panel or by selecting certain sub-sets of functions.

Note that GeneXproTools automatically balances your function set according to the number of input variables in your data, therefore you just have to select the set of functions for your problem and then choose their relative proportions by choosing their weights.

Despite the great diversity of GeneXproTools built-in logical functions, some users sometimes want to model with different ones. GeneXproTools gives the user the possibility of creating custom functions (called Dynamic UDFs and represented as DDFs in the generated code) in order to design circuits with them. Note however that the use of custom functions is computationally demanding, slowing considerably the evolutionary process and therefore should be used with moderation.

By selecting the Functions Tab in the Functions Panel, you have full access to all the available functions, including all the functions you've designed and all the built-in logical functions. It's also in the Functions Panel that you add your custom functions (Dynamic UDFs or DDFs) to your modeling toolbox.

To add a custom function to your function set, just check the checkbox on the Select/Weight column and select the appropriate weight for the function (the weight determines the probability of each function being drawn during mutation and other random events in the creation/modification of logic circuits). By default, the weight of each newly added function is 1, but you can increase the probability of a function being included in your logic circuits by increasing its weight in the Select/Weight column. GeneXproTools automatically balances your function set with the number of input variables in your data, therefore you just have to select the set of logical functions for your problem and then choose their relative proportions by choosing their weights.

To create a new custom function, just click the Add button on the Dynamic UDFs frame and the DDF Editor appears. You can also edit old functions through the Edit button or remove them altogether from your modeling toolbox by clicking the Remove button.

By choosing the number of arguments (minimum is 1 and maximum is 4) in the Arguments combobox, the function header appears in the code window. Then you just have to write the body of the function in the code editor. The code must be in JavaScript and can be conveniently tested for compiling errors by clicking the Test button.

In the Definition box, you can write a brief description of the function for your future reference. The text you write there will appear in the Definition column in the Functions Panel.

Dynamic UDFs are extremely powerful and interesting tools as they are treated exactly like the built-in functions of GeneXproTools and therefore can be used to model all kinds of relationships not only between the original variables but also between derived features created on the fly by the learning algorithm. For instance, you can design a DDF so that it will model four expressions XOR-ed together, that is, DDF = (expression 1) XOR (expression 2) XOR (expression 3) XOR (expression 4), where the value of each expression will depend on the context of the DDF in the program.

Creating Derived Inputs/Variables

Sometimes it is fundamental to use complex building blocks to build even more complex ones, and GeneXproTools allows you to design your own basic building blocks (called Static UDFs or just UDFs in GeneXproTools). These building blocks might represent any kind of logical expression (not just functions of 1-4 arguments like the DDFs described in the previous section) and are therefore ideal to design complex logic circuits composed of several simpler components.

Derived variables or new inputs can be easily created in GeneXproTools from the original inputs. They are created in the Functions Panel, in the Static UDFs Tab.

The code for the UDFs must be in JavaScript and is written in the Edit UDF window (in the Functions Panel, select the Static UDFs Tab and then click the Add button in the Static UDFs toolbox).

Historically, derived variables were called UDFs or User Defined Functions and in GeneXproTools they are represented as UDF0, UDF1, UDF2, and so on. Note however that UDFs are in fact new inputs derived from the original inputs in the training and test datasets. Like DDFs, they are implemented in JavaScript using the JavaScript editor of GeneXproTools.

These user defined inputs are then used by the learning algorithm exactly as the original inputs, that is, they are incorporated into the evolving circuits adaptively, with the most important being chosen and selected according to how much they contribute to the performance of each logic circuit.

Exploring the Learning Algorithms

GeneXproTools uses two different learning algorithms for Logic Synthesis. The first – the basic gene expression algorithm or simply Gene Expression Programming (GEP) – does not support the direct manipulation of random numerical constants (0's and 1's in this case), whereas the second – GEP with Random Numerical Constants or GEP-RNC for short – has a facility for handling them directly. These two algorithms search the solution landscape differently and therefore you might wish to try them both on your problems.

Taking into consideration not only the slightly higher complexity of the GEP-RNC algorithm but also the fact that both these algorithms produce equally elegant circuits, GEP is the default learning algorithm in GeneXproTools for Logic Synthesis problems. However, you can activate the GEP-RNC algorithm in the Settings Panel -> Numerical Constants by checking the Use Random Numerical Constants checkbox. In the Numerical Constants Tab you can also adjust the range of the constants (either 0 or 1 or both) and the number of constants per gene.

The GEP-RNC algorithm is slightly more complex than the basic gene expression algorithm as it uses an additional gene domain (Dc) for encoding the random numerical constants. Consequently, this algorithm includes an additional set of genetic operators (RNC Mutation, Constant Insertion, Dc Mutation, Dc Inversion, Dc IS Transposition, and Dc Permutation) especially developed for handling random numerical constants (if you are not familiar with these operators, please use the default Optimal Evolution Strategy by selecting Optimal Evolution in the Strategy combobox as it works very well in all cases; or you can learn more about the genetic operators in the Legacy Knowledge Base).

Monitoring the Modeling Process

While your circuits evolve, you can evaluate and visualize the actual design process through the real-time monitoring of different model fitting charts and statistics in the Run Panel, such as different Binomial Fitting Charts, the Classification Scatter Plot, the Classification Tapestry, the Confusion Matrix, the Classification Accuracy and the Fitness.

The evolutionary process can be stopped whenever you are satisfied with the results by clicking the Stop button or you can use one of the stop conditions of GeneXproTools for stopping the design process exactly when you see fit.

When the evolutionary process stops, you can use the best-of-run circuit either for analysis or for deployment. And if you are still not happy with the results, you can continue to fine-tune your logic circuit by clicking any of the optimization buttons GeneXproTools provides: Continue, Simplify or Complexify. Particularly useful in Logic Synthesis is the simplification functionality which allows you to find more compact solutions to your logic circuits.

Simplifying Logic Circuits

The whole business of logic circuit design revolves around finding the most parsimonious circuits and GeneXproTools deals with this task excellently. No matter what form your circuits are in (sum-of-products, product-of-sums, NAND-only, NOR-only, AND-XOR-NOT-only, MUX-only, and so on), you can feed them to GeneXproTools and let it have a go at simplifying them. The results of the simplification process can be conveniently observed in the Run Panel where both the size and number of literals are plotted during simplification.

GeneXproTools allows you to simplify an existing logic circuit (either created with GeneXproTools or with another modeling technology) either by clicking the Simplify button in the Run Panel or by turning on the Parsimony Pressure in the Fitness Function Tab and then clicking Continue or Simplify in the Run Panel. GeneXproTools allows you to adjust the parsimony pressure you exert on the size of the evolving circuits, but bigger circuits can always appear during evolution if the gain in fitness trumps the smaller size. But if your logic circuit is already a perfect solution, its fitness can only improve by becoming more and more compact.

For logic circuits created outside GeneXproTools or for GeneXproTools circuits modified by the user in the Change Seed Window, the starting logic circuit is fed to the learning algorithm through the Change Seed Window where both the fitness and structural soundness of the circuit are tested.

Then, in the Run Panel, by clicking the Simplify button, an evolutionary process starts in which all the subsequent circuits will be descendants of the circuit you want to simplify. Keep in mind, however, that the simplification algorithms GeneXproTools uses are evolutionary in nature and logic circuits continue to be selected primarily by fitness. This means that their complexity might even increase temporarily if the gain in fitness outweighs the loss in simplicity. But if your logic circuit is already a perfect solution, its fitness can only improve by becoming more and more compact.

For logic circuits created in the GeneXproTools environment, you just have to select the circuit you want to simplify (either the best-of-run or an intermediate solution) and then click Simplify in the Run Panel and let the algorithm create better descendants not only in terms of fitness but also in terms of size.

Model Evaluation & Testing

While your logic circuits are being created by the learning algorithm, you can evaluate and visualize the actual design process through the real-time monitoring of different charts and statistics in the Run Panel such as the Classification Scatter Plot, the Classification Tapestry and the Confusion Matrix.

In the Results Panel you can further evaluate your logic circuits for both the training and validation datasets, using different model fitting charts and additional measures of fit, such as the sensitivity, specificity, recall, precision and Matthews correlation coefficient.

In the second, the target and predicted values are plotted using different Model Fitting Charts for easy visualization, including the Classification Tapestry, the Classification Scatter Plot and different Binomial Fitting Charts.

GeneXproTools allows a quick and easy assessment of a wide range of statistics for measuring the goodness of fit. Most of these measures of fit are immediately computed and shown in the Statistics Report every time you go to the Results Panel (namely, the classification error, classification accuracy, confusion matrix, sensitivity, specificity, positive predictive value, negative predictive value, recall, precision, F1 measure, Jaccard similarity, Matthews correlation coefficient, Pearson correlation coefficient, R-square and the root mean squared error).

These and other measures of fit (namely, mean squared error, mean absolute error, relative squared error, root relative squared error, relative absolute error) are also shown in the Report Panel for the active model, but you must evaluate them first in the Results Panel.

Modeling from Seed Circuits

The whole business of logic circuit design revolves around finding minimal logic circuits and GeneXproTools deals with this task excellently. No matter what form your circuits are in (sum-of-products, product-of-sums, NAND-only, NOR-only, AND-XOR-NOT-only, MUX-only, and so on), you can feed them to GeneXproTools and let it have a go at minimizing them. The results of the minimization process can be conveniently observed in the Run Panel where both the size and number of literals are plotted during minimization.

GeneXproTools allows the use of an existing logic circuit (either generated by GeneXproTools or by another modeling tool) as the starting point of an evolutionary process in order to create better circuits.

For logic circuits created outside GeneXproTools or for GeneXproTools circuits modified by the user in the Change Seed Window, the starting circuit or seed is fed to the algorithm through the Change Seed Window where both the fitness and structural soundness of the logic circuit are tested. The Change Seed Window accepts Karva Code only, so you must translate your logic circuit into Karva notation first in order to explore it in GeneXproTools.

Then, in the Run Panel, by clicking any of the optimization buttons GeneXproTools provides (Continue, Simplify and Complexify), an evolutionary process starts in which all the subsequent circuits will be descendants of the seed circuit you introduced. Note, however, that if your starting logic circuit has a very small fitness, you risk losing it early in the run as better logic circuits could be randomly created by GeneXproTools, leaving your seed behind.

For logic circuits created in the GeneXproTools environment, the seed (the active model) is fed automatically to the algorithm every time you click Continue, Simplify or Complexify in the Run Panel.

Adding a Neutral Gene

The addition of a neutral gene to a logic circuit (in logic terms, it’s like OR-ing an expression with zero or AND-ing with one) might seem at first sight the wrong thing to do as we are usually interested in creating minimal logic circuits. But one should look at this as modeling in progress as this allows us to tackle a complex problem incrementally.

Indeed, being able to introduce extra terms into your evolving circuits is a powerful modeling tool and GeneXproTools allows you to do that by selecting Add Neutral Gene in the Model menu or through the Change Seed Window. For instance, by choosing OR as linking function, you could use a different gene for each minterm of your circuit, and then try and evolve a more parsimonious solution from there.

When you click the Add Neutral Gene button in the Change Seed window, you will see a neutral gene being added to your logic circuit (in the example above, the last gene was OR-ed with itself). By doing this, you are giving the learning algorithm more room to play and, hopefully, a better circuit will evolve.

Neutral genes can also be introduced automatically as part of a modeling strategy when you turn on the Complexity Increase Engine of GeneXproTools, which is the topic of the next section.

Complexity Increase Engine

GeneXproTools also allows you to introduce neutral genes automatically during a run by activating the Complexity Increase Engine in the Settings Panel -> General Settings Tab.

Generating the Model Code

In the Model Panel you can see and analyze the code of your logic circuits not only in the programming language of your choice but also as a diagram representation or expression tree. GeneXproTools includes 18 built-in programming languages or grammars for Logic Synthesis. These grammars allow you to generate code automatically in some of the most popular programming languages around, namely Ada, C, C++, C#, Excel VBA, Fortran, Java, JavaScript, Matlab, Octave, Pascal, Perl, PHP, Python, Visual Basic, VB.Net, Verilog, and VHDL. But more importantly, GeneXproTools also allows you to add your own programming languages through user-defined grammars, which can be easily created using one of the built-in grammars as template.

GeneXproTools includes a parse tree generator that automatically converts the native Karva code of your logic circuits into diagram representations or expression trees, allowing a quicker and more complete understanding of their Boolean structure. By placing the cursor over each node of the expression tree, you have access to the label of each input and its index, the value of each constant and the definition of each function.

GeneXproTools supports a total of 18 built-in programming languages so that the logic circuits evolved by GeneXproTools in its native Karva code can be automatically translated into some of the most commonly used programming languages (Ada, C, C++, C#, Excel VBA, Fortran, Java, JavaScript, Matlab, Octave, Pascal, Perl, PHP, Python, Visual Basic, VB.Net, Verilog, and VHDL). Furthermore, for all languages, the generated code can be automatically transcribed to six different logical systems (All Gates, Not-And-Or Only, Nand Only, Nor Only, Mux System, Reed-Muller System) using six different Boolean grammars. This code can then be used in other applications to deploy the logic circuit.

GeneXproTools allows the design of User Defined Grammars so that the logic circuits evolved by GeneXproTools in its native Karva code can be automatically translated into the programming language that you need. Indeed, if you need to generate model code in a programming language other than the 18 built-in programming languages of GeneXproTools available for Logic Synthesis (Ada, C, C++, C#, Excel VBA, Fortran, Java, JavaScript, Matlab, Octave, Pascal, Perl, PHP, Python, Visual Basic, VB.Net, Verilog, and VHDL), you can easily create your own grammars to generate code automatically in as many languages as you need.

As an illustration, the All Gates VHDL grammar of GeneXproTools is shown here. Other grammars may be easily created using this or other GeneXproTools built-in grammars as reference.

Last modified: November 24, 2013


Cite this as:

Ferreira, C. "Getting Started with Logic Synthesis." From GeneXproTools Tutorials – A Gepsoft Web Resource.
https://www.gepsoft.com/tutorials/GettingStartedWithLogicSynthesis.htm