Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Giảm thiểu Mô hình Quyết định Nhị phân cho Các Hệ thống Hàm Boolean Được Định nghĩa Không Hoàn chỉnh Sử dụng Mở rộng Cofactor Đại số
Tóm tắt
Tiêu chí tối ưu hóa chính trong việc tổng hợp các mạch tổ hợp từ các phần tử logic trong thư viện là số lượng hằng số trong các biểu diễn đa cấp đại số của các hệ thống hàm Boolean hoàn toàn định nghĩa. Sau khi thu được các mô hình quyết định nhị phân của các hệ thống hàm Boolean được định nghĩa không hoàn chỉnh (một phần), đề xuất thực hiện tối ưu hóa logic bổ sung dựa trên việc tìm kiếm các biểu diễn đại số của các hàm con (cofactor) một cấp của mô hình quyết định nhị phân dưới hình thức là một phép hợp hoặc phép giao của các hàm con khác ở cấp độ đã cho của mô hình quyết định nhị phân. Phương pháp đề xuất cho phép giảm số lượng hằng số bằng cách thay thế các công thức khai thác Shannon (phân tích) bằng các công thức đơn giản hơn trong quá trình chuyển đổi sang một biểu diễn đa cấp của một hệ thống các hàm được định nghĩa hoàn toàn, theo đó mạch logic tổ hợp được tổng hợp.
Từ khóa
Tài liệu tham khảo
D. E. Knuth and D. J. Fuller, Art of Computer Programming, Vol. 4A: The Combinatorial Algorithms, Part 1 (Addison-Wesley, Reading, MA, 2011).
Yu. G. Karpov, Model Checking. Verification of Parallel and Distributed Software Systems (BKhV-Peterburg, St. Petersburg, 2010).
Handbook of Satisfiability, Ed. by A. Biere, M. Heule, H. van Maaren, and T. Walsh (IOS Press, Amsterdam, 2009).
S. B. Akers, “Binary decision diagrams,” IEEE Trans. Comput. 27 (6) (1978).
R. E. Bryant, “Graph-based algorithms for Boolean functions manipulation,” IEEE Trans. Comput. 35 (8) (1986).
M. Chen, X. Qin, H.-M. Koo, and P. Mishra, System-Level Validation: High-Level Modeling and Directed Test Generation Techniques (Springer, Berlin, 2014).
P. N. Bibilo, The Use of Binary Decision Diagrams in the Synthesis of Logic Circuits (Belarus. Navuka, Minsk, 2014) [in Russian].
R. Rudell, “Dynamic variable ordering for ordered binary decision diagrams,” in Computer-Aided Design: Proceedings of the IEEE/ACM International Conference, Santa Clara (IEEE Comput. Soc. Press, Los Alamitos, 1993).
R. Ebendt, W. Gunther, and R. Drechsler, “An improved branch and bound algorithm for exact BDD minimization,” IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 22 (12) (2003).
R. Ebendt, G. Fey, and R. Drechsler, Advanced BDD Optimization (Springer, Dordrech, 2005).
R. Drechsler and B. Becker, Binary Decision Diagrams: Theory and Implementation (Springer, New York, 1998).
R. E. Bryant and C. Meinel, “Ordered binary decision diagrams,” in Logic Synthesis and Verification, Ed. by S. Hassoun, T. Sasao, and R. K. Brayton (Springer, Boston, MA, 2002).
C. Meinel and T. Theobald, Algorithms and Data Structures in VLSI Design: OBDD – Foundations and Applications (Springer, Berlin, 1998).
R. K. Breiton, G. D. Khechtel, and A. L. Sandzhovanni-Vinchentelli, “Synthesis of multilevel combinational logic circuits,” TIIER 78 (2) (1990).
S. Yang and M. Ciesielski, “BDS: A BDD-based logic optimization system,” IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 21 (7) (2002).
P. N. Bibilo and Yu. Yu. Lankevich, “The use of Zhegalkin polynomials for minimization of multilevel representations of Boolean functions based on Shannon expansion,” Program. Inzhen., No. 8, 369 (2017).
P. N. Bibilo and V. I. Romanov, “Minimization of binary decision diagrams for systems of completely defined Boolean functions using Shannon expansions and algebraic representations of cofactors,” Informatika 18 (3), 7 (2021).
P. N. Bibilo and V. I. Romanov, “Experimental study of algorithms for minimization of binary decision diagrams using algebraic representations of cofactors,” Program. Inzhen. 13, 51 (2022).
The Tests in the Monograph 'Logic Minimization Algorithms for VLSI Synthesis’. http://www1.cs.columbia.edu/~cs6861/sis/espresso-examples/ex. Accessed January 20, 2020.
P. N. Bibilo, “Minimization of binary decision diagrams for systems of incompletely defined Boolean functions using inverse cofactors,” Progr. Inzhen. 11 (3), 152 (2020).
A. D. Zakrevskii, Yu. V. Pottosin, and L. D. Cheremisinova, Logical Basis for Designing Discrete Devices (Fizmatlit, Moscow, 2007) [in Russian].
Yu. V. Pottosin and E. A. Shestakov, “Orthogonalization of a system of fully defined Boolean functions,” in Logic Design, Collection of Articles (Inst. Tekhn. Kibern. NAN Belarusi, Minsk, 2000), No. 5 [in Russian].
I. V. Romanovskii, Discrete Analysis, The School-Book, 4nd ed. (Nevskii Dialekt, BKhV-Peterburg, St. Petersburg, 2008) [in Russian].
P. N. Bibilo and S. V. Enin, Synthesis of Combinational Circuits by Methods of Functional Decomposition (Nauka Tekhnika, Minsk, 1987) [in Russian].
N. R. Toropov, “Minimization of systems of Boolean functions in the DNF class,” in Logic Design, Collection of Articles (Inst. Tekhn. Kibern. NAN Belarusi, Minsk, 1999), No. 4 [in Russian].