Abstract
Researchers have thoroughly studied decomposition in many different contexts, such as switching theory or data mining. In recent years, a renewed interest in this problem was caused by memory-based pattern matching circuits, particularly in the synthesis of Index Generation Functions. In this case, function is a composition of a linear function L and a general function G. The function L is implemented using ExOR gates, while G is usually realized using embedded memories.
In this paper, we show that the linear function reduces the number of variables to represent an index generation function, thus reducing memory size. However, as another efficient technique for logic synthesis using memories, a functional decomposition can be applied. The decomposition is a methodology of expressing a function of n variables as a bunch (collection) of functions of fewer variables. This paper presents an exact method of searching for a functional decomposition with a minimum number of variables by using the theory of r-admissibility. Therefore, the method proposed can be used for ROM-based synthesis, particularly for pattern matching and communication circuits.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Borowik, G.: Optimization on the complementation procedure towards efficient implementation of the index generation function. Appl. Math. Comput. Sci. 28(4), 803–815 (2018). https://doi.org/10.2478/amcs-2018-0061
Borowik, G., Łuba, T., Klempous, R.: Comparison of algorithms for dimensionality reduction and their application to index generation functions. In: 2020 IEEE 15th International Conference of System of Systems Engineering (SoSE), pp. 283–288 (2020). https://doi.org/10.1109/SoSE50414.2020.9130484
Sasao, T.: Index generation functions. In: Logic Synthesis for Pattern Matching, EPFL Workshop on Logic Synthesis & Verification (2015)
Sasao, T., Matsuura, K., Iguchi, Y.: An algorithm to find optimum support-reducing decompositions for index generation functions. In: Design, Automation & Test in Europe Conference & Exhibition (DATE), 2017, pp. 812–817 (2017). https://doi.org/10.23919/DATE.2017.7927100
Sasao, T.: Memory-Based Logic Synthesis, 1st edn. Springer-Verlag, New York (2011). https://doi.org/10.1007/978-1-4419-8104-2
Białas, M.: Implementation of software supporting the reduction and classification of data. Engineering Thesis, Warsaw University of Technology, Warsaw (2018)
Borowik, G., Luba, T.: Fast algorithm of attribute reduction based on the complementation of Boolean function. In: Klempous, R., Nikodem, J., Jacak, W., Chaczko, Z. (eds.) Advanced Methods and Applications in Computational Intelligence. Topics in Intelligent Engineering and Informatics, vol. 6, pp. 25–41. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-319-01436-4_2
Brzozowski, J.A., Łuba, T.: Decomposition of Boolean functions specified by cubes. J. Multi-Valued Log. Soft Comput. 9, 377–417 (2003)
Sasao, T.: Index generation functions: minimization methods. In: 2017 IEEE 47th International Symposium on Multiple-Valued Logic (ISMVL), pp. 197–206, May 2017. https://doi.org/10.1109/ISMVL.2017.22
Łuba, T., Selvaraj, H.: A general approach to Boolean function decomposition and its applications in FPGA-based synthesis. VLSI Des. 3(3–4), 289–300 (1995)
Rokach, L., Maimon, O.: Data mining using decomposition methods. In: Maimon, O., Rokach, L. (eds.) Data Mining and Knowledge Discovery Handbook, pp. 981–998. Springer, Boston (2010). https://doi.org/10.1007/978-0-387-09823-4_51
Borowik, G., Łuba, T., Poźniak, K.: New trends in logic synthesis for both digital designing and data processing. In: Romaniuk, R.S. (ed.) Photonics Applications in Astronomy, Communications, Industry, and High-Energy Physics Experiments 2016, vol. 10031, pp. 1371–1381. International Society for Optics and Photonics, SPIE (2016). https://doi.org/10.1117/12.2249240
Łuba, T.: Decomposition of multiple-valued functions. In: Proceedings 25th International Symposium on Multiple-Valued Logic, pp. 256–261 (1995). https://doi.org/10.1109/ISMVL.1995.513540
Mazurkiewicz, T., Łuba, T.: Linear and non-linear decomposition of index generation functions. In: 2019 MIXDES – 26th International Conference “Mixed Design of Integrated Circuits and Systems”, pp. 246–251 (2019). https://doi.org/10.23919/MIXDES.2019.8787031
Sasao, T.: A reduction method for the number of variables to represent index generation functions: s-min method. In: 2015 IEEE International Symposium on Multiple-Valued Logic, pp. 164–169, May 2015. https://doi.org/10.1109/ISMVL.2015.40
Wąsicki, D.: Gate based synthesis of Index Generation Functions. Master Thesis, Warsaw School of Computer Science, Warsaw (2019)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Borowik, G., Łuba, T., Wąsicki, D., Chmaj, G. (2021). Synthesis of Index Generation Function Using Linear and Functional Decomposition. In: Selvaraj, H., Chmaj, G., Zydek, D. (eds) Proceedings of the 27th International Conference on Systems Engineering, ICSEng 2020. ICSEng 2020. Lecture Notes in Networks and Systems, vol 182. Springer, Cham. https://doi.org/10.1007/978-3-030-65796-3_11
Download citation
DOI: https://doi.org/10.1007/978-3-030-65796-3_11
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-65795-6
Online ISBN: 978-3-030-65796-3
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)