×

An iterative method for linear decomposition of index generating functions. (English) Zbl 1419.94099

Summary: Various methods for reducing hardware implementation cost of incompletely specified index generating functions have been proposed lately. Considering the methods based on linear decomposition, for the first time in this work, we provide necessary and sufficient conditions which describe the linear decomposition of these functions in general. These conditions are derived using the concept of functional degeneracy, and we show that the problem of linear decomposition can be translated into the problem of constructing suitable coordinate Boolean functions (which represent the generating functions) such that the linear decomposition is possible. In this context, we propose several design methods of such Boolean functions and furthermore we employ one particular design method to derive a new iterative semi-deterministic algorithm for linear decomposition. In addition, we provide a general result which describes all incompletely specified index generating functions for which the linear decomposition is (not) possible. Consequently, our results indicate that the functional degeneracy is a promising approach in derivation of new deterministic-like algorithms for linear decomposition of incompletely specified index generating functions.

MSC:

94D05 Fuzzy sets and logic (in connection with information, communication, or circuits theory)
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
65T50 Numerical methods for discrete and fast Fourier transforms

Software:

MiniSat; JBool
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Astola, J., Astola, P., Stanković, R., Tabus, I.: An algebraic approach to reducing the number of variables of incompletely defined discrete functions. In: 46th International Symposium on Multiple-Valued Logic, pp. 107-112 (2016) · Zbl 1429.06017
[2] Astola, J., Astola, P., Stanković, R., Tabus, I.: Index generation functions based on linear and polynomial transformations. In: 46th International Symposium on Multiple-Valued Logic, pp. 102-106 (2016)
[3] Bhattacharyya, A., Indyk, P., Woodruff, D.P., Xie, N.: The complexity of linear dependence problems in vector spaces. Innovations Comput. Sci., 496-508. ISBN 978-7-302-24517-9 (2011)
[4] Crama, Y., Hammer, P.L.: Boolean Functions: Theory, Algorithms, and Applications. Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge (2011) · Zbl 1237.06001 · doi:10.1017/CBO9780511852008
[5] Een, N., Sorensson, N.: An extensible SAT-solver. In: Giunchiglia, E., Tacchella, A. (eds.) Theory and Applications of Satisfiability Testing. Lecture Notes in Computer Science, SAT 2003, vol. 2919, pp 502-518. Springer, Berlin (2003) · Zbl 1204.68191
[6] Karpovsky, M.G., Stankovic, R.S., Astola, J.T.: Spectral Logic and Its Applications for the Design of Digital Devices. Wiley, Hoboken (2007)
[7] Kolomeec, N., Pavlov, A.: Bent functions on the minimal distance. IEEE Region 8, SIBIRCON, Irkutsk Listvyanka, Russia (2010)
[8] Lechner, R.J.: Harmonic analysis of switching functions. Recent Developments in Switching Theory, New York, Edited by: Amar Mukhopadhyay, pp. 121-228 (1971)
[9] Luba, T., Borowik, G., Jankowski, C.: Gate-based decomposition of index generation functions. Photonics Applications in Astronomy, Communications, Industry, and High-Energy Physics Experiments, vol. 10031 (2016)
[10] Mitchell, C.: Enumerating Boolean functions of cryptographic significance. J. Cryptol. 2(3), 155-170 (1990) · Zbl 0705.94010 · doi:10.1007/BF00190802
[11] Nagayama, S., Sasao, T., Butler, J.T.: An efficient heuristic for linear decomposition of index generation functions. In: 46nd International Symposium on Multiple-Valued Logic, pp. 96-101. Japan (2016)
[12] Nagayama, S., Sasao, T., Butler, J.T.: A balanced decision tree based heuristic for linear decomposition of index generation functions. IEICE Trans. Inf. Syst. E100.D (8), 1583-1591 (2017) · doi:10.1587/transinf.2016LOP0013
[13] Nečiporuk, E.I.: Network synthesis by using linear transformation of variables. Dokladi Akademii Nauk SSSR 123(4), 610-612 (1958) · Zbl 0089.12805
[14] Pagiamtzis, K., Sheikholeslami, A.: Content-addressable memory (CAM) circuits and architectures: A tutorial and survey. IEEE J. Solid State Circuits 41(3), 712-727 (2006) · doi:10.1109/JSSC.2005.864128
[15] Sasao, T.: Index generation functions: tutorial. J. Multiple-Valued Logic Soft Comput. 23(3-4), 235-263 (2014)
[16] Sasao, T.: Multiple-valued input index generation functions: optimization by linear transformation. In: 42nd International Symposium on Multiple-Valued Logic, pp. 185-190. Canada (2012)
[17] Sasao, T.: A reduction method for the number of variables to represent index generation functions: s-Min method. In: 45nd International Symposium on Multiple-Valued Logic, pp. 164-169. Canada (2015)
[18] Sasao, T.: Index generation functions: theory and applications. In: International Symposium on Communications and Information Technologies, pp. 585-590. Japan (2010)
[19] Sasao, T.: Linear transformations for variable reduction. ReedMuller Workshop (2011)
[20] Sasao, T.: On the numbers of variables to represent multi-valued incompletely specified functions. In: 13th Euromicro Conference on Digital System Design: Architectures, Methods and Tools. France (2010)
[21] Sasao, T.: On the numbers of variables to represent sparse logic functions. In: IEEE/ACM International Conference on Computer-Aided Design, pp. 45-51. San Jose, USA (2008)
[22] Sasao, T.: Index generation functions: recent developments. In: 41st IEEE International Symposium on Multiple-Valued Logic, pp. 235-263. Finland (2011)
[23] Sasao, T.: Memory-Based Logic Synthesis. Springer-Verlag, New York (2011) · doi:10.1007/978-1-4419-8104-2
[24] Sasao, T.: Linear decomposition of index generation functions. In: 17th Asia and South Pacific Design Automation Conference, pp. 781-788 (2012)
[25] Sasao, T.: Index generation functions: Minimization methods. In: 47th International Symposium on Multiple-Valued Logic, pp. 197-206 (2017)
[26] Sasao, T.: An application of autocorrelation functions to find linear decompositions for incompletely specified index generation functions. In: 43rd International Symposium on Multiple-Valued Logic, pp. 96-102 (2013)
[27] Sasao, T.: A linear decomposition of index generation functions: optimization using autocorrelation functions. J. Multiple-Valued Logic Soft Comput. 28(1), 105-127 (2017) · Zbl 1400.94201
[28] Sasao, T., Fumishi, I., Iguch, Y.: A method to minimize variables for incompletely specified index generation functions using a SAT solver. In: International Workshop on Logic and Synthesis, Mountain View, pp. 161-167 (2015)
[29] Sasao, T., Nakamura, T., Matsuura, M.: Representation of incompletely specified index generation functions using minimal number of compound variables. In: 12th Euromicro Conference on Digital System Design / Architectures, Methods and Tools, pp 765-772 (2009)
[30] Sasao, T., Matsuura, M., Nakahara, H.: A realization of Index generation functions using modules of uniform sizes. In: International Workshop on Logic and Synthesis, pp. 201-208. California (2010)
[31] Sasao, T., Urano, Y., Iguchi, Y.: A method to find linear decompositions for incompletely specified index generation functions using difference matrix. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. E97.A(12), 2427-2433 (2014) · doi:10.1587/transfun.E97.A.2427
[32] Sasao, T., Urano, Y., Iguchi, Y.: A lower bound on the number of variables to represent incompletely specified index generation functions. In: 44th International Symposium on Multiple-Valued Logic, pp. 7-12. Germany (2014)
[33] Abboud, A., Lewi, K., Williams, R.: Losing weight by gaining edges. In: 22th Annual European Symposium on Algorithms, Lecture Notes in Computer Science, vol. 8737, pp. 1-12. Poland (2014) · Zbl 1423.68197
[34] Simovici, D.A., Zimand, M., Pletea, D.: Several remarks on index generation functions. In: 42nd IEEE International Symposium on Multiple-Valued Logic, pp. 179-184. Canada (2012)
[35] Stanković, M., Stanković, R.: Variable reduction of index generating functions in Walsh-Hadamard domain. In: Proceedings Reed-Muller Workshop, pp. 80-85. Japan (2013)
[36] Troy Nagle, H., Carroll, B.D., David Irwin, J.: : An Introduction to Computer Logic (Prentice-Hall computer applications in electrical engineering series), 1st edn. Prentice-Hall, Englewood Cliffs (1975)
[37] Varma, D., Trachtenberg, E.: Design automation tools for efficient implementation of logic functions by decomposition. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 8(8), 901-916 (1989) · doi:10.1109/43.31549
[38] Wu, C.-K., Feng, D.: Boolean functions and their applications in cryptography. Advances in Computer Science and Technology (2016) · Zbl 1364.94010
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.