Применение методов минимизации булевых функций для оптимизации цифровых устройств
Автор: Смагин А.А., Шиготаров А.В.
Журнал: Известия Самарского научного центра Российской академии наук @izvestiya-ssc
Рубрика: Физика и электроника
Статья в выпуске: 3-2 т.11, 2009 года.
Бесплатный доступ
В статье рассмотрены вопросы применения алгоритмов минимизации булевых функций для оптимизации цифровых устройств. Предлагаются точный и приближенный методы минимизации, основанные на использовании двоичных диаграмм решения и хешировании общих префиксов термов, соответственно. Результаты компьютерных экспериментов показывают преимущество предложенных алгоритмов (в смысле скорости работы), по сравнению с методами, приводимыми в литературе.
Алгоритмы минимизации, булевы функции, цифровые устройства
Короткий адрес: https://sciup.org/148198637
IDR: 148198637 | УДК: 621.382.82+
Logic minimization based approach for optimization of digital devices
This article deals with the using of logic minimization algorithms for optimization of digital devices. We propose exact and approximate minimization algorithms, based on the using of binary decision diagrams and hashing of common prefixes of the terms, respectively. Experimental results show that our methods outperform well-known methods appeared in literature in terms of runtime.
Список литературы Применение методов минимизации булевых функций для оптимизации цифровых устройств
- Chandra A.K., Markowsky G. On the number of prime implicants.-Discrete Mathematics 24(1978), pp 7-11.
- Coudert O., Madre J.C. Implicit and incre-mental computation of primes and essential primes of Boolean functions//Proc. of the Design Automation Conf. (Anaheim, CA, 1992), pp 36-39.
- Coudert O., Madre J.C. New ideas for solving covering problems//Proc. of the Design Automation Conference, 1995, pp 641-645.
- Liu H. Routing Table Compaction in Ternary-CAM//IEEE Micro, Jan/Feb 2002, pp. 58-64.
- Meinel C., Theobald T. Algorithms and data structures in VLSI design, Springer-Verlag NY, 1998. -267 p.
- McAuley A., Francis P. Fast Routing Table Lookup Using CAMs//Proc. IEEE Infocom, vol. 3, IEEE CS Press, Los Alamitos, Calif., 1993, pp. 1382-1391.
- Ravikumar V.C., Bhuyan L.N., Mahapatra R.N., EaseCAM: An Energy and Storage Efficient TCAM-Based Router Architecture for IP Lookup//IEEE Transactions on Computers, vol. 54, 2005, 521-533.
- Rudell R. Multiple-valued minimization for PLA synthesis. UCB technical report M86/65, 1986.
- Stergiou S., Jain J. Optimizing Routing Tables on Systems-on-Chip with Content-Addressable Memories//Proc. IEEE International System-on-Chip Symposium, 2008, pp 1-6.
- Umans C., Villa T. Sangiovanni-Vincentelli A. Complexity of two-level logic minimization. IEEE Transactions on Computer-Aided design, 2006, pp 1230-1246.
- http://www.ee.pdx.edu/~alanmi/research/ex-tra.htm.
- lpsolve.sourceforge.net
- http://www.routeviews.org/
- vlsi.colorado.edu/~fabio/
- http://web.cecs.pdx.edu/~alanmi/research/min/rondo.exe.
