Применение методов минимизации булевых функций для оптимизации цифровых устройств
Автор: Смагин А.А., Шиготаров А.В.
Журнал: Известия Самарского научного центра Российской академии наук @izvestiya-ssc
Рубрика: Физика и электроника
Статья в выпуске: 3-2 т.11, 2009 года.
Бесплатный доступ
В статье рассмотрены вопросы применения алгоритмов минимизации булевых функций для оптимизации цифровых устройств. Предлагаются точный и приближенный методы минимизации, основанные на использовании двоичных диаграмм решения и хешировании общих префиксов термов, соответственно. Результаты компьютерных экспериментов показывают преимущество предложенных алгоритмов (в смысле скорости работы), по сравнению с методами, приводимыми в литературе.
Алгоритмы минимизации, булевы функции, цифровые устройства
Короткий адрес: https://sciup.org/148198637
IDR: 148198637
Список литературы Применение методов минимизации булевых функций для оптимизации цифровых устройств
- 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.
