Implementation of a system of incompletely specified Boolean functions in a circuit of two-input gates by means of bi-decomposition

Capa

Citar

Texto integral

Acesso aberto Acesso aberto
Acesso é fechado Acesso está concedido
Acesso é fechado Somente assinantes

Resumo

The problem of bi-decomposition of a Boolean function is to represent a given Boolean function as a logic algebra operation over two Boolean functions. A meth-od based on bi-decomposition of Boolean functions is suggested to implement sys-tems of incompletely specified (partial) Boolean functions in the basis of two-input gates. This basis can be the basis of NOR gates, NAND gates or the basis of AND and OR gates with accessible input complements. The used method for bi-decomposition is reduced to the search for two-block weighted cover of a complete bipartite weighted graph with complete bipartite subgraphs (bi-cliques). The graph represents differences between the rows of Boolean matrices that specify the given system of partial Boolean functions. The system is given by two Boolean matrices, one of which represents the domain of Boolean space where the values of the given functions are specified, and the other the values of the functions on the elements of the domain. Every bi-clique in the obtained cover is assigned in a certain way with а set of variables that are the arguments of the function. This set is the weight of the bi-clique. Every of those bi-cliques defines a Boolean function whose arguments are the variables assigned to it. The functions obtained in such a way constitute the re-quired decomposition. The process of synthesis of a combinational circuit consists in successive application of bi-decomposition to the obtained functions. The meth-od for two-block covering the orthogonality graph of rows of ternary matrices is de-scribed.

Texto integral

Acesso é fechado

Sobre autores

Yu. Pottosin

United Institute of Informatics Problems, National Academy of Sciences of Belarus

Autor responsável pela correspondência
Email: pott@newman.bas-net.by
Belarus, Minsk

Bibliografia

  1. Perkowski M.A., Grygiel S. A Survey of Literature on Functional Decomposition, Version IV (Technical Report). Portland, USA: Portland State University, Department of Electrical En-gineering, 1995.
  2. Zakrevskij A.D. On a Special Kind Decomposition of Weakly Specified Boolean Functions // Second Intern. Conf. on Computer-Aided Design of Discrete Devices (CAD DD’97). Minsk, Belarus: National Academy of Sciences of Belarus, Institute of Engineering Cybernetics, 1997. V. 1. P. 36–41.
  3. Fišer P., Schmidt J. Small but Nasty Logic Synthesis Examples // Proc. 8th Intern. Workshop on Boolean Problems (IWSBP’8), Freiberg, Germany, 2008. P. 183–190.
  4. Бибило П.Н. Декомпозиция булевых функций на основе решения логических уравне-ний. Минск: Беларус. навука, 2009.
  5. Choudhury M., Mohanram K. Bi-decomposition of Large Boolean Functions Using Blocking Edge Graphs // 2010 IEEE/ACM Intern. Conf. on Computer-Aided Design (ICCAD’2010). San Jose: IEEE Press, 2010. Р. 586–591.
  6. Cheng D., Xu X. Bi-decomposition of Logical Mappings via Semi-Tensor Product of Matri-ces // Automatica. 2013. V. 49. N 7. Р. 1979–1985.
  7. Steinbach B., Posthoff C. Vectorial Bi-decomposition for Lattices of Boolean Functions // Further Improvements in the Boolean Domain / Cambridge. Cambridge Scholars Publishing, 2018. Р. 175–198.
  8. Jóžwiak L., Chojnacki A. An Effective and Efficient Method for Functional Decomposition of Boolean Functions Based on Information Relationship Measures // Design and Diagnos-tics of Electronic Circuits and Systams: Proc. of 3rd DDECS Workshop, Smolenice Castle, Slovakia, Bratislava: Institute of Informatics, Slovak Academy of Sciences, 2000. Р. 242–249.
  9. Закревский А.Д. Декомпозиция частичных булевых функций – проверка на раздели-мость по заданному разбиению // Информатика. 2007. № 1 (13). С. 16–21.
  10. Поттосин Ю.В., Шестаков Е.А. Применение аппарата покрытий троичных матриц для поиска разбиения множества аргументов при декомпозиции булевых функций // Вестн. Томск. гос. ун-та. Управление, вычислительная техника и информатика. 2011. № 3(16). С. 100–107.
  11. Taghavi Afshord S., Pottosin Yu.V., Arasteh B. An Input Variable Partitioning Algorithm for Functional Decomposition of a System of Boolean Functions Based on the Tabular Method // Discrete Applied Mathematics. 2015. V. 185. P. 208–219.
  12. Поттосин Ю.В. Метод бидекомпозиции частичных булевых функций // Информа-тика. 2019. Т. 16, № 4. С. 77–87.
  13. Поттосин Ю.В., Шестаков Е.А. Декомпозиция системы частичных булевых функ-ций с помощью покрытия графа полными двудольными подграфами // Новые инфор-мационные технологии в исследовании дискретных структур. Докл. второй Всерос-сийск. конф. Екатеринбург: УрО РАН, 1998. С. 185–189.
  14. Pottosin Yu.V. A Method for Bi-decomposition of Partial Boolean Functions // Приклад-ная дискретная математика. 2020. № 47. С. 108–116.
  15. Поттосин Ю.В. Эвристический метод алгебраической декомпозиции частичных булевых функций // Информатика. 2020. Т. 17, № 3. С. 44–53.
  16. Поттосин Ю.В., Шестаков Е.А. Параллельно-последовательная декомпозиция си-стемы частичных булевых функций // Прикладная дискретная математика. 2010. № 4(10). С. 55-63.
  17. Cortadella J. Timing-driven Logic Bi-decomposition // IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems. 2003. V. 22. N 6. Р. 675–685.
  18. Mishchenko A., Steinbach B., Perkowski M. An Algorithm for Bi-decomposition of Logic Functions // Proc. 38th Annual Design Automation Conf. (DAC’2001), Las Vegas, USA, 2001. Р. 103–108.
  19. Chang S.C., Marek-Sadowska M., Hwang T. Technology Mapping for TLU FPGA’s Based on Decomposition of Binary Decision Diagrams // IEEE Trans. Computer-Aided De-sign. 1996. V. 15. N 10. Р. 1226–1235.
  20. Поттосин Ю.В. Комбинаторные задачи в логическом проектировании дискретных устройств. Минск: Беларус. навука, 2021.
  21. Закревский А.Д., Поттосин Ю.В., Черемисинова Л.Д. Логические основы проекти-рования дискретных устройств. М.: Физматлит, 2007.
  22. Евстигнеев В.А., Касьянов В.Н. Толковый словарь по теории графов в информатике и программировании. Новосибирск: Наука. СО РАН, 1999.

Arquivos suplementares

Arquivos suplementares
Ação
1. JATS XML
Baixar
2. Formula

Baixar (62KB)
Metadados
3. Fig. 1. Circuit of OR-NOT elements

Baixar (118KB)
Metadados
4. Fig. 2. Circuit of AND and OR elements

Baixar (134KB)
Metadados

Declaração de direitos autorais © Russian Academy of Sciences, 2024