Efficient implementation of an exact multiple-output boolean function minimization algorithm

The performance of the Svoboda-Nadler-Vora algorithm for exact multiple-output boolean function minimization is studied and compared with a heuristic minimization method. For this purpose, the algorithm has been implemented in optimized ANSI C code. This implementation introduces a new set of procedures to reduce the cost of prime implicant generation. The concept of weight as the number of 1 and don't care neighbors of a state is used to take advantage of the special cases when a state has only one neighbor or no neighbors at all. The cost of prime implicant generation is further reduced by using the fact that the input dependency of any given state is limited by which of its neighbors exist within an output that are 1 's or don't cares. A detailed example illustrates how the heuristic method can fail to find the absolute minimum of a boolean function.

Name thesis:degree_name

M.S.

Level thesis:degree_level

masters

Discipline thesis:degree_discipline

Electrical Engineering

Department dc:contributor.department

Electrical Engineering

Grantor dc:publisher

Virginia Polytechnic Institute and State University

Year dc:date.issued

1989

Author dc:creator

• Dueñas, César A.

Statement dc:rights

• In Copyright

Licence dc:rights.uri

• http://rightsstatements.org/vocab/InC/1.0/

Language dc:language.iso

en

Handle dc:identifier.uri

http://hdl.handle.net/10919/106530

OAI identifier oai:identifier

oai:vtechworks.lib.vt.edu:10919/106530