OPTIMIZATION PROBLEM FOR NUMBER OF LOGIC GATES NEEDED TO IMPLEMENT MULTIPLE BOOLEAN FUNCTIONS USING DECODER
Abstract. Background. Computer circuits enable almost every piece of electronics to function. An opportunity for their optimization was found in one of the ways to implement a circuit, which involves a decoder. Decoders are basic circuit components whose behavior makes it easy to implement multiple...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Odessa National Academy of Food Technologies
2024-12-01
|
| Series: | Автоматизация технологических и бизнес-процессов |
| Subjects: | |
| Online Access: | https://journals.ontu.edu.ua/index.php/atbp/article/view/3018 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832584124873834496 |
|---|---|
| author | M. Onai H. Skopyk |
| author_facet | M. Onai H. Skopyk |
| author_sort | M. Onai |
| collection | DOAJ |
| description | Abstract. Background. Computer circuits enable almost every piece of electronics to function. An opportunity for their optimization was found in one of the ways to implement a circuit, which involves a decoder. Decoders are basic circuit components whose behavior makes it easy to implement multiple Boolean functions. Functions are just rules by which informational signals are being processed in the circuit. To implement a function Logic gatEs (LEs) are used. LEs group multiple input signals and process them using binary logic operators like AND or NOR.
Purpose. Develop a computer program that, based on provided functions, will find a solution associated with approximately minimal number of logic gates.
Relevance. Prevalence of circuits increases the value of small optimizations, since any improvement gets multiplied by millions of circuits produced. Optimization at the logic level is being explored, which will retain value regardless of the physical properties of the circuit. Additionally, the theory of optimizing LE usage for circuits built on decoders is examined, which will alleviate future research.
Methods. Development of the theory arose from an understanding that input signals can be grouped using LEs consciously. This way, LE outputs can be used in more than one function, which results in reduction of total number of LEs. It becomes evident that the problem can be restated in terms of sets. Similarity to known NP-hard problems emerges, which prompts usage of existing solution approaches. Among them, the greedy algorithm is chosen for its simplicity in program implementation. The connection between the problem and digital circuitry is weakened by the introduction of special evaluation functions that work with sets. So, the problem is reduced to several mathematical rules, which then are used as the appropriate parts of the greedy algorithm. Development of knowledge necessary to create the target program is thus concluded.
Results. The target program is successfully implemented and can be seen in full at https://github.com/Gleb-05/MakeFuncForDC. A test is conducted on 1000 sets of four pseudorandom eight-term functions. It is estimated that the implementations proposed by the program require on average 0.75 of the initial number of LEs. The average running time is estimated at 2 milliseconds. In contrast, brute-force search for the same problem is theorized to run for years.
Conclusions. A working program that finds an almost optimal solution is successfully created and tested. Its performance makes it potentially useful in the industrial scale of circuit manufacturing. Since the program essentially offers workload management, its possible applications go beyond the domain of digital electronics. Additionally, the theory of optimizing the use of LEs is presented for the first time. It can be used as the basis for future research on the implementation of multiple Boolean functions using decoder. |
| format | Article |
| id | doaj-art-f9f0246134e3466db94791d80428f262 |
| institution | Kabale University |
| issn | 2312-3125 2312-931X |
| language | English |
| publishDate | 2024-12-01 |
| publisher | Odessa National Academy of Food Technologies |
| record_format | Article |
| series | Автоматизация технологических и бизнес-процессов |
| spelling | doaj-art-f9f0246134e3466db94791d80428f2622025-01-27T15:58:25ZengOdessa National Academy of Food TechnologiesАвтоматизация технологических и бизнес-процессов2312-31252312-931X2024-12-0116411011710.15673/atbp.v16i4.30183018OPTIMIZATION PROBLEM FOR NUMBER OF LOGIC GATES NEEDED TO IMPLEMENT MULTIPLE BOOLEAN FUNCTIONS USING DECODERM. Onai0H. Skopyk1National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”, Kyiv, UkraineNational Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”, Kyiv, UkraineAbstract. Background. Computer circuits enable almost every piece of electronics to function. An opportunity for their optimization was found in one of the ways to implement a circuit, which involves a decoder. Decoders are basic circuit components whose behavior makes it easy to implement multiple Boolean functions. Functions are just rules by which informational signals are being processed in the circuit. To implement a function Logic gatEs (LEs) are used. LEs group multiple input signals and process them using binary logic operators like AND or NOR. Purpose. Develop a computer program that, based on provided functions, will find a solution associated with approximately minimal number of logic gates. Relevance. Prevalence of circuits increases the value of small optimizations, since any improvement gets multiplied by millions of circuits produced. Optimization at the logic level is being explored, which will retain value regardless of the physical properties of the circuit. Additionally, the theory of optimizing LE usage for circuits built on decoders is examined, which will alleviate future research. Methods. Development of the theory arose from an understanding that input signals can be grouped using LEs consciously. This way, LE outputs can be used in more than one function, which results in reduction of total number of LEs. It becomes evident that the problem can be restated in terms of sets. Similarity to known NP-hard problems emerges, which prompts usage of existing solution approaches. Among them, the greedy algorithm is chosen for its simplicity in program implementation. The connection between the problem and digital circuitry is weakened by the introduction of special evaluation functions that work with sets. So, the problem is reduced to several mathematical rules, which then are used as the appropriate parts of the greedy algorithm. Development of knowledge necessary to create the target program is thus concluded. Results. The target program is successfully implemented and can be seen in full at https://github.com/Gleb-05/MakeFuncForDC. A test is conducted on 1000 sets of four pseudorandom eight-term functions. It is estimated that the implementations proposed by the program require on average 0.75 of the initial number of LEs. The average running time is estimated at 2 milliseconds. In contrast, brute-force search for the same problem is theorized to run for years. Conclusions. A working program that finds an almost optimal solution is successfully created and tested. Its performance makes it potentially useful in the industrial scale of circuit manufacturing. Since the program essentially offers workload management, its possible applications go beyond the domain of digital electronics. Additionally, the theory of optimizing the use of LEs is presented for the first time. It can be used as the basis for future research on the implementation of multiple Boolean functions using decoder.https://journals.ontu.edu.ua/index.php/atbp/article/view/3018digital electronicscombinational circuitcircuit implementationboolean algebradecoderdata protectioncost minimizationnp-hard problem |
| spellingShingle | M. Onai H. Skopyk OPTIMIZATION PROBLEM FOR NUMBER OF LOGIC GATES NEEDED TO IMPLEMENT MULTIPLE BOOLEAN FUNCTIONS USING DECODER Автоматизация технологических и бизнес-процессов digital electronics combinational circuit circuit implementation boolean algebra decoder data protection cost minimization np-hard problem |
| title | OPTIMIZATION PROBLEM FOR NUMBER OF LOGIC GATES NEEDED TO IMPLEMENT MULTIPLE BOOLEAN FUNCTIONS USING DECODER |
| title_full | OPTIMIZATION PROBLEM FOR NUMBER OF LOGIC GATES NEEDED TO IMPLEMENT MULTIPLE BOOLEAN FUNCTIONS USING DECODER |
| title_fullStr | OPTIMIZATION PROBLEM FOR NUMBER OF LOGIC GATES NEEDED TO IMPLEMENT MULTIPLE BOOLEAN FUNCTIONS USING DECODER |
| title_full_unstemmed | OPTIMIZATION PROBLEM FOR NUMBER OF LOGIC GATES NEEDED TO IMPLEMENT MULTIPLE BOOLEAN FUNCTIONS USING DECODER |
| title_short | OPTIMIZATION PROBLEM FOR NUMBER OF LOGIC GATES NEEDED TO IMPLEMENT MULTIPLE BOOLEAN FUNCTIONS USING DECODER |
| title_sort | optimization problem for number of logic gates needed to implement multiple boolean functions using decoder |
| topic | digital electronics combinational circuit circuit implementation boolean algebra decoder data protection cost minimization np-hard problem |
| url | https://journals.ontu.edu.ua/index.php/atbp/article/view/3018 |
| work_keys_str_mv | AT monai optimizationproblemfornumberoflogicgatesneededtoimplementmultiplebooleanfunctionsusingdecoder AT hskopyk optimizationproblemfornumberoflogicgatesneededtoimplementmultiplebooleanfunctionsusingdecoder |