Saeid Taghavi Afshord; Yuri Pottosin

Improved Decomposition for a System of Completely Specified Boolean Functions

Full Text (PDF, 320KB), PP.25-32

Views: 0 Downloads: 0

Author(s)

Saeid Taghavi Afshord ¹ Yuri Pottosin ²

1. Computer Engineering Department, Shabestar Branch, Islamic Azad University, Shabestar, Iran

2. United Institute of Informatics Problems, National Academy of Sciences of Belarus, Minsk, Belarus

* Corresponding author.

DOI: https://doi.org/10.5815/ijitcs.2014.01.03

Received: 26 Feb. 2013 / Revised: 10 Jul. 2013 / Accepted: 2 Oct. 2013 / Published: 8 Dec. 2013

Index Terms

Boolean Functions, Compact Table, Boolean Hypercube, Optimization, Encoding and Logic Synthesis

Abstract

Functional decomposition is an important and powerful technique in the logic synthesis. The ternary matrix cover approach is one of the existing methods of this type. This method is also used in decomposition of a system of completely specified Boolean functions. Before constructing the desired superposition, it needs to encode a table. There is a trivial encoding method. But to find a better solution, it is important to use a special approach, because the result of the encoding has a direct influence on the obtained functions. In this paper, an efficient algorithm to encode this table is presented. It uses the approach connected with the assembling Boolean hyper cube method. The proposed algorithm is explained in details with an example. The benefits and impacts of the suggested technique are also discussed.

Cite This Paper

Saeid Taghavi Afshord, Yuri Pottosin, "Improved Decomposition for a System of Completely Specified Boolean Functions", International Journal of Information Technology and Computer Science(IJITCS), vol.6, no.1, pp.25-32, 2014. DOI:10.5815/ijitcs.2014.01.03

Reference

[1]Martinelli A. Advances in Functional Decomposition: Theory and Applications. Doctoral Dissertation, Royal Institute of Technology (KTH), Stockholm, Sweden, 2006

[2]Morawiecki P, Rawski M, Selvaraj H. Application of Functional Decomposition in Synthesis of Boolean Function Sets. In: Proceedings of the 19th International Conference on Systems Engineering (ICSENG), Aug. 2008, Las Vegas, USA, 350-355.

[3]Perkowski M A, Grygiel S. A Survey of Literature on Functional Decomposition, Version IV. Technical report, Department of Electrical Engineering, Portland State University, Portland, USA, 1995

[4]Zakrevskij A, Pottosin Yu V, Cheremisinova L. Optimization in Boolean Space. Tallinn, Estonia, TUT Press, 2009

[5]Hassoun S, Sasao T. Logic Synthesis and Verification. The Springer International Series in Engineering and Computer Science, Kluwer Academic Publishers, 2001.

[6]Rawski M. Input Variable Partitioning Method for Decomposition-Based Logic Synthesis targeted Heterogeneous FPGAs. International Journal of Electronics and Telecommunications, 2012, vol 58 (1), 15–20.

[7]Muthukumar V, Bignall R J, Selvaraj H. An efficient variable partitioning approach for functional decomposition of circuits. Journal of Systems Architecture, 2007, vol. 53, no. 1, 53-67.

[8]Pottosin Yu V, Shestakov E A. Tabular Methods for Decomposition of Systems of Completely Specified Boolean Functions. Byelorusskaya Nauka, Belarus, 2006 (in Russian)

[9]Taghavi Afshord, S, Pottosin, Yu V. On Decomposing Systems of Boolean Functions via Ternary Matrix Cover Approach. International Journal of Advanced Science and Technology, June 2013, Vol. 55, 33-42.

[10]Pottosin, Yu V, Pottosina, S A. State assignment of a finite state machine for a low power implementing circuit. In: Proceedings of the 8th International Conference, Nov. 2011, University of Zilina, Zilina, Slovak Republic, 113-116.

International Journal of Information Technology and Computer Science (IJITCS)