Dekompozycja funkcjonalna zespołów funkcji boolowskich

Paweł Morawiecki

Abstract

In the thesis there are presented solutions that allowed to develop a fully automated Boolean function decomposition system dedicated to multi-output functions. The efficiency of the system is better or comparable to the leading academic and commercial systems. The proposed methods and algorithms solve many problems and limitations of the existing solutions. The main idea is to decompose function sets which are specified by separate truth tables. Functions specified in such a way can be described by different cube sets with different input variables what provides flexibility and computational efficiency. However completely separate decomposition of each function makes it impossible to utilize potential common information which may be present in these functions. That is why a crucial element in the proposed method is to keep the possibility of using common information while allowing functions to be specified by separate truth tables. It was achieved by a specially designed graph coloring procedure. The thesis is divided into two main parts. Basic terms and definitions concerning functional decomposition and implemented algorithms are described in the first part. It includes Boolean algebra, parts of graph theory and formal approach to functional decomposition for different function representations. The second part starts with description of existing systems and their limitations. Methods and algorithms designed and implemented by author are presented in the fourth chapter. It includes an idea of using common information between decomposed functions, application of Shannon expansion, input variable selection methods dedicated to large functions. Finally in the fifth and the sixth chapter we find the system scheme, experimental results and comparison to other systems.
Diploma typeDoctor of Philosophy
Author Paweł Morawiecki (FEIT / IT)
Paweł Morawiecki,,
- The Institute of Telecommunications
Title in PolishDekompozycja funkcjonalna zespołów funkcji boolowskich
Languagepl polski
Certifying UnitFaculty of Electronics and Information Technology (FEIT)
Disciplinetelecommunications / (technology domain) / (technological sciences)
Start date06-10-2009
Defense Date08-06-2010
End date22-06-2010
Supervisor Tadeusz Łuba (FEIT / IT)
Tadeusz Łuba,,
- The Institute of Telecommunications

Internal reviewers Andrzej Kraśniewski (FEIT / IT)
Andrzej Kraśniewski,,
- The Institute of Telecommunications
External reviewers Bolesław Czesław Pochopień (PolSL)
Bolesław Czesław Pochopień,,
- Silesian University of Technology
Pages124
Keywords in Englishdigital technology, FPGA programmable logic, logic gates, Boolean functions, graphs
Abstract in EnglishIn the thesis there are presented solutions that allowed to develop a fully automated Boolean function decomposition system dedicated to multi-output functions. The efficiency of the system is better or comparable to the leading academic and commercial systems. The proposed methods and algorithms solve many problems and limitations of the existing solutions. The main idea is to decompose function sets which are specified by separate truth tables. Functions specified in such a way can be described by different cube sets with different input variables what provides flexibility and computational efficiency. However completely separate decomposition of each function makes it impossible to utilize potential common information which may be present in these functions. That is why a crucial element in the proposed method is to keep the possibility of using common information while allowing functions to be specified by separate truth tables. It was achieved by a specially designed graph coloring procedure. The thesis is divided into two main parts. Basic terms and definitions concerning functional decomposition and implemented algorithms are described in the first part. It includes Boolean algebra, parts of graph theory and formal approach to functional decomposition for different function representations. The second part starts with description of existing systems and their limitations. Methods and algorithms designed and implemented by author are presented in the fourth chapter. It includes an idea of using common information between decomposed functions, application of Shannon expansion, input variable selection methods dedicated to large functions. Finally in the fifth and the sixth chapter we find the system scheme, experimental results and comparison to other systems.
PKT classification710900 - Teoria telekomunikacji. Zagadnienia podstawowe telekomunikacji
KBN classification35 - telekomunikacja
EU classification8030
Thesis file
doktorat Morawiecki.pdf 7.31 MB
Citation count*5 (2020-09-26)

Get link to the record

Back
Confirmation
Are you sure?