{"id":{"repo_id":"vt","oai_identifier":"oai:vtechworks.lib.vt.edu:10919/106530"},"canonical_url":"https://search.dev.ndltd.org/etd/vt/oai:vtechworks.lib.vt.edu:10919/106530","repository":{"repo_id":"vt","name":"Virginia Tech","base_url":"https://vtechworks.lib.vt.edu/oai/request"},"display":{"title":"Efficient implementation of an exact multiple-output boolean function minimization algorithm","abstract":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Dueñas, César A."],"institution":"Virginia Polytechnic Institute and State University","degree_name":"M.S.","degree_level":"masters","degree_discipline":"Electrical Engineering","degree_department":"Electrical Engineering","school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":1989,"date_issued":"1989","date_published":"1989","updated_at":"2026-07-22T22:20:09Z","subjects":[],"languages":["en"],"rights":["In Copyright"],"rights_urls":["http://rightsstatements.org/vocab/InC/1.0/"],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/10919/106530","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.department","label":"Department","values":["Electrical Engineering"]},{"key":"dc:creator","label":"Author","values":["Dueñas, César A."]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2021-11-05T20:16:20Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2021-11-05T20:16:20Z"]},{"key":"dc:date.issued","label":"Date","values":["1989"]},{"key":"dc:publisher","label":"Institution","values":["Virginia Polytechnic Institute and State University"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"dc:type.dcmitype","label":"Dc Type Dcmitype","values":["Text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["masters"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["Virginia Polytechnic Institute and State University"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["In Copyright"]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://rightsstatements.org/vocab/InC/1.0/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/10919/106530"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["M.S."]},{"key":"dc:format.mimetype","label":"Dc Format Mimetype","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Efficient implementation of an exact multiple-output boolean function minimization algorithm"]}]}],"canonical_facts":{"dc:contributor.department":["Electrical Engineering"],"dc:creator":["Dueñas, César A."],"dc:date.accessioned":["2021-11-05T20:16:20Z"],"dc:date.available":["2021-11-05T20:16:20Z"],"dc:date.issued":["1989"],"dc:description.abstract":["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."],"dc:description.degree":["M.S."],"dc:format.mimetype":["application/pdf"],"dc:identifier.uri":["http://hdl.handle.net/10919/106530"],"dc:language.iso":["en"],"dc:publisher":["Virginia Polytechnic Institute and State University"],"dc:rights":["In Copyright"],"dc:rights.uri":["http://rightsstatements.org/vocab/InC/1.0/"],"dc:title":["Efficient implementation of an exact multiple-output boolean function minimization algorithm"],"dc:type":["Thesis"],"dc:type.dcmitype":["Text"],"thesis:degree_discipline":["Electrical Engineering"],"thesis:degree_level":["masters"],"thesis:degree_name":["M.S."],"thesis:institution_name":["Virginia Polytechnic Institute and State University"]},"updated_at":"2026-07-22T22:20:09Z"}