Пример реализации булевых функций приведен на рис.2.
Реализация комбинационных схем на ПЛМ
Неформально задача синтеза комбинационной схемы (КС) на ПЛМ может быть сформулирована следующим образом. Задано описание функционирования КС и допустимое множество вариантов микросхем ПЛМ. Требуется реализовать данную КС на возможно меньшем числе корпусов. В данной лабораторной работе сузим задачу до случая, когда фиксирован тип ПЛМ и требуется реализовать КС на одном корпусе (или показать, что такая реализация невозможна). Дадим формальную постановку задачи.
Пусть работа КС описывается системой из N булевых функций от L переменных. Будем полагать, что система функций представлена в дизъюнктивной нормальной форме (ДНФ), в которой число попарно неравных элементарных конъюнкций равно В. Такую систему функций будем обозначать СФ [L,N,B].
Если выполняется система неравенств
L £ S, N £ T, B £ Q, (1)
то возможна так называемая тривиальная реализация на ПЛМ [S, T, Q].
При данной реализации на промежуточных шинах в матрице И формируются все конъюнкции СФ, а в поле матрицы ИЛИ устанавливаются связи промежуточных шин с соответствующими выходами. Рис.2 является примером тривиальной реализации СФ [4, 3, 12] на ПЛМ [4, 3, 12].
При невыполнении системы неравенств (1) может быть применен следующий полуэвристический алгоритм для реализации СФ [L, N, B] на ПЛМ [S, T, Q].
1. Если L > S (не хватает входов в ПЛМ), то реализация на одной ПЛМ невозможна. Конец.
2. Если N > T (не хватает выходов ПЛМ), то реализация на одной ПЛМ невозможна. Конец.
3. Если B £ Q, то тривиальная реализация СФ [L, N, B]. Конец.
4. Поиск "инверсной" СФ [ L, N, B' ] с минимальным значением B'.
5. Если B' £ Q, то тривиальная реализация "инверсной" СФ[L, N, B] с соответствующей инверсией выходов. Конец.
6. Если L = S или N = T (нет "резерва" по входам или выходам ПЛМ), то переход на к.10.
7. Декомпозиция исходной СФ и переход к набору СФ', описывающему каскадное включение комбинационных схем.
8. Если невозможна тривиальная реализация набора СФ на ПЛМ, то переход к п.10.
9. Тривиальная реализация набора СФ и установление соответствующих связей между выходами и входами ПЛМ. Конец.
10. Переход от СФ [L, N, B] к СФ [ L, N, B' ] путем совместной минимизации исходной системы булевых функций.
11. Если B'' £ Q, то тривиальная реализация СФ[L, N, B''], иначе реализация на одной ПЛМ [S, T, Q], невозможна.
12. Конец.
Рассмотрим подробнее отдельные пункты алгоритма.
|
|
|
Рис.2. Пример реализации комбинационной схемы на ПЛМ [4, 3, 12] |
Переход к "инверсной" системе булевых функций
Пусть заданы некоторые СФ [L, N, B] вида
Y1 = F1 ( X1 , ... , XL );
Y2 = F2 ( X1 , ... , XL );
. . . . . . . . . . .
YN = FN ( X1 , ... , XL ).
Из данной СФ получим путем инвертирования некоторых разрядов функции так называемую "инверсную" СФ вида
Z1 = (Y1) j1 , Z2 = (Y2) j2 , ... , ZN = (YN) jn,
ì Y, если j = 0, где Z í
î `Y, если j = 1.
Каждая "инверсная" СФ задается двоичным вектором ( j1, j2, ... , jN). Следовательно, различные "инверсные" СФ могут быть получены перебором по (2N - 1) двоичным векторам. Если существует "инверсная" СФ [ L, N, B' ] с B' £ Q, то исходная СФ может быть реализована на ПЛМ[S,T,Q] следующим образом.
1. Выполняется тривиальная реализация "инверсной" СФ.
2. Осуществляется необходимая инверсия выходных сигналов.
А именно, если jК = 0, то в поле "Уровень выхода" для К-го выхода устанавливается символ "L", иначе символ "H".
Пример 1. Пусть требуется реализовать на ПЛМ [3, 2, 5] двоичный одноразрядный сумматор. Исходная СФ [3, 2, 8], описывающая работу сумматора, показана на рис.3 в табличной форме.
|
|
|
Рис.3. Реализация сумматора на ПЛМ: А, В - слагаемые; р - перенос из младшего разряда; S - сумма, с - перенос в старший разряд |
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.
