Information Technology Reference
In-Depth Information
the Reed-Muller system is the only one that performs better than the MUX
system in terms of compactness, requiring just 123 nodes to realize all the 20
functions (see Table 4.12). All the remaining systems are considerably more
verbose than the MUX system, with the classical Boolean system requiring a
total of 161 nodes (see Table 4.9), the NAND system a total of 234 (see
Table 4.10), and the NOR system a total of 242 nodes (see Table 4.11).
So, perhaps among the logical functions of three arguments, not just the
NLMs presented in Table 4.8 but also ULMs such as the MUX, the IF, the
MAJ, and MIN functions analyzed here, there are other compact universal
systems that can be exploited by the emergent FPGA technology in order to
build more efficient logical circuits. And helping us making these decisions
with amazing speed is the emerging technique of gene expression program-
ming as the parsimonious solutions designed by GEP can be automatically
translated into VHDL or Verilog and, therefore, can be immediately inte-
grated into an FPGA design.
4.3.3 Using User Defined Functions as Building Blocks
Sometimes finding a good parsimonious representation to a complex function
is so hard that the only way around it is trying to explore some pattern in its
definition. Indeed, most such functions are modular in nature and, by finding
simple modules and then use them as building blocks, it is possible most of the
times to design good parsimonious solutions (by good parsimonious solutions
it is meant solutions at least more parsimonious than the sum-of-products or
product-of-sums solutions).
Gene expression programming can be used not only to discover patterns
in logical functions by finding small building blocks, but also to integrate
these building blocks in the design of more complex functions. And, in GEP,
there are two different ways of designing more complex functions with smaller
building blocks: the first one is totally automatic and the system not only
discovers the building blocks but also uses them immediately to build more
complex solutions (we will see how this is done in chapter 6, Automatically
Defined Functions in Problem Solving); and the second, is much more pro-
saic and involves the well-known technique of using user defined functions
(UDFs). How gene expression programming can be used to create complex
structures composed of smaller UDFs is explained next with two modular
problems: the odd-
n
-parity functions and the
n
-exactly-one-on functions. But
let's first analyze how UDFs work and how they are implemented in GEP.
