Một Phương Pháp Đại Số Nhóm Đối Với Phân Loại NPN Của Các Hàm Boolean

Theory of Computing Systems - Tập 63 - Trang 1278-1297 - 2018
Juling Zhang1,2, Guowu Yang1,3, William N. N. Hung4, Tian Liu5, Xiaoyu Song6, Marek A. Perkowski6
1Big Data Research Center, School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu, China
2School of Computer Science and Engineering, University of Xinjiang Finance and Economics, Urumqi, China
3Guangxi Key Laboratory of Hybrid Computation and IC Design Analysis, Guangxi University for Nationalities, Nanning, China
4Synopsys Inc., Mountain View, USA
5Key Laboratory of High Confidence Software Technologies, Ministry of Education, Peking University, Beijing, China
6ECE Department, Portland State University, Portland, USA

Tóm tắt

Việc phân loại các hàm Boolean đóng vai trò nền tảng trong thiết kế logic và tổng hợp mạch VLSI. Bài báo này xem xét một câu hỏi nền tảng trong phân loại hàm Boolean: có bao nhiêu lớp khác biệt cho các hàm Boolean với k đầu vào. Chúng tôi khai thác nhiều thuộc tính đại số nhóm để tính toán hiệu quả số lượng lớp tương đương duy nhất. Chúng tôi đã giảm độ phức tạp tính toán từ 2mm! xuống (m + 1)!. Chúng tôi trình bày phân tích cho phân loại NPN của các hàm Boolean với tối đa mười biến và tính toán số lượng lớp tương đương NP và NPN cho 3-10 biến. Đây là lần đầu tiên báo cáo số lượng phân loại NP và NPN cho các hàm Boolean với 9-10 biến. Chúng tôi chứng minh tính hiệu quả của phương pháp thông qua cả các chứng minh lý thuyết và các thí nghiệm số.

Từ khóa

#phân loại hàm Boolean #NPN #lớp tương đương #đại số nhóm #thiết kế mạch VLSI

Tài liệu tham khảo

Tsai, C.-C., Marek-Sadowska, M.: Boolean functions classification via fixed polarity reed-muller forms. IEEE Trans. Comput. 46(2), 173–186 (1997) Braeken, A., Borissov, Y., Nikova, S., Preneel, B.: Classification of Boolean functions of 6 variables or less with respect to some cryptographic properties. In: Proc. 32nd International Conference on Automata, Languages and Programming, ser. ICALP’05, pp. 324–334 (2005) Dautovic, S., Novak, L.: A comment on Boolean functions classification via fixed polarity reed-muller form. IEEE Trans. Comput. 55(8), 1067–1069 (2006) Rice, J.E., Muzio, J.C., Anderson, N.: New considerations for spectral classification of Boolean switching functions. VLSI Design 2011, 1:1–1:9 (2011) Benini, L., De Micheli, G.: A survey of Boolean matching techniques for library binding. ACM Trans. Des. Autom. Electron. Syst. 2(3), 193–226 (1997) Edwards, C.R., Hurst, S.L.: A Digital Synthesis Procedure Under Function Symmetries and Mapping Methods. IEEE Computer Society (1978) Jain, A., Bryant, R.E.: Inverter minimization in multi-level logic networks. In: Proc. International Conference on Computer-Aided Design, ser. ICCAD ’93, pp. 462–465 (1993) Devices, S.V., Stratix, V.: Device Handbook. Altera, San Jose (2012) Berlekamp, E., Welch, L.: Weight distributions of the cosets of the (32,6) reed-muller code. IEEE Trans. Inf. Theory 18(1), 203–207 (1972) Maiorana, J.A.: A classification of the cosets of the reed-muller code r (1, 6). Math. Comput. 57(195), 403–414 (1991) Borissov, Y., An, B., Nikova, S., Preneel, B.: Classification of the cosets of rm(1,7) in rm(3,7) revisited,” NATO ASI on ”Boolean Functions in Cryptology and Information Security (2007) Zhang, Y., Yang, G., Hung, W.N., Zhang, J.: Computing affine equivalence classes of Boolean functions by group isomorphism. IEEE Trans. Comput. 65(12), 3606–3616 (2016) Slepian, D.: On the number of symmetry types of Boolean functions of n variables. Can. J. Math. 5(2), 185–193 (1955) Huang, Z., Wang, L., Nasikovskiy, Y., Mishchenko, A.: Fast Boolean matching based on npn classification. In: International Conference on Field-Programmable Technology, pp. 310–313 (2013) Petkovska, A., Soeken, M., Micheli, G.D., Ienne, P., Mishchenko, A.: Fast hierarchical npn classification. In: International Conference on Field Programmable Logic and Applications, pp. 1–4 (2016) Abdollahi, A., Pedram, M.: Symmetry detection and Boolean matching utilizing a signature-based canonical form of Boolean functions. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 27(6), 1128–1137 (2008) Agosta, G., Bruschi, F., Pelosi, G., Sciuto, D.: A transform-parametric approach to Boolean matching. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 28(6), 805–817 (2009) Matsunaga, Y.: Accelerating sat-based Boolean matching for heterogeneous fpgas using one-hot encoding and cegar technique. In: Design Automation Conference, pp. 255–260 (2015) Harrison, M.A.: The number of equivalence classes of Boolean functions under groups containing negation. IEEE Transactions on Electronic Computers EC-12(5), 559–561 (1963) Dixon, J.D., Mortimer, B.: Permutation Groups. Springer, Berlin (1996) Cycle type of a permutation, http://groupprops.subwiki.org/wiki/Cycle_type_of_a_permutation Cycle index, http://en.wikipedia.org/wiki/Cycle_type Lipsett, R.: conjugacy classes in the symmetric group s n, http://planetmath.org/?op=getobj;from=objects;id=9613 Cycle type determines conjugacy class. http://groupprops.subwiki.org/wiki/Cycle_type_determines_conjugacy_class Brualdi, R.A.: Pearson Introductory combinatorics:united states edition (2009) Pólya, G.: Kombinatorische anzahlbestimmungen for gruppen, graphen und chemische verbindungen. Acta Mathematica 68, 145–254 (1937) Redfield, J.H.: The theory of group-reduced distributions. Am. J. Math. 49 (3), 433–455 (1927) Brualdi, R.A.: Introductory Combinatorics, 5th ed. Prentice Hall, January 2009, ch. 14 Sloane, N J A: The on-line encyclopedia of integer sequence, https://oeis.org/A000370 Bruijn, N.G.D.: Generalization of polya’s fundamental theorem in enumerative combinatorial analysis. Indag. Math. 62(3), 59–69 (1959)
Thông tin
Thông tin xuất bản

Theory of Computing Systems

Tập 63

1278-1297

Thông tin tác giả