Программируемые логические матрицы
⇐ ПредыдущаяСтр 3 из 3
Цель работы: ознакомление с методами программирования на ПЛМ.
1. МЕТОДИЧЕСКИЕ УКАЗАНИЯ
Понятие о программируемых логических матрицах
Программируемая логическая матрица (ПЛМ) - это микросхема, состоящая в общем случае из двух матриц: матрицы И и матрицы ИЛИ. Каждая из этих матриц представляет собой сетку из ортогональных проводников. Эти проводники называют шинами. В местах пересечения шин при изготовлении ПЛМ устанавливают элементы с односторонней проводимостью (ЭОП) - диоды или транзисторы. Пользователь по своему усмотрению может удалить отдельные ЭОП. Процесс удаления ЭОП называют программированием ПЛМ. Программирование реальной микросхемы сводится к подаче импульсов тока на определенные выводы микросхемы. Эти импульсы тока приводят к разрушению связи соответствующего ЭОП с шиной. Обобщенная структурная схема ПЛМ представлена на рис.1. Матрица И связана со входами ПЛМ через программируемые инверторы. Между собой матрицы соединены так называемыми промежуточными шинами. Для ПЛМ с S входами, Т выходами и Q промежуточными шинами будем использовать обозначение ПЛМ [S,T,Q].
Двоичные сигналы, подаваемые на входы ПЛМ, будем называть входными переменными. Двоичные сигналы, формируемые на выходах ПЛМ, будем называть выходными переменными. В матрице И на промежуточных шинах формируются конъюнкции входных переменных. Для разных промежуточных шин конъюнкции формируются независимо друг от друга. В конъюнкцию входная переменная может входить либо в прямом, либо в инверсном виде. Кроме того, переменная может не участвовать при формировании конъюнкции.
В матрице ИЛИ каждая выходная переменная формируется как дизъюнкция переменных на соответствующих промежуточных шинах. Дизъюнкции для разных выходных переменных формируются независимо друг от друга. В каждую дизъюнкцию может входить любое число переменных, сформированных на промежуточных шинах. Выходы матрицы ИЛИ связаны с выходами ПЛМ через программируемые инверторы, что позволяет формировать выходную переменную как инверсию соответствующего выхода матрицы ИЛИ.
Таблицы программирования ПЛМ
Как было отмечено выше, при программировании ПЛМ устанавливаются соответствующие связи в матрицах И, ИЛИ и слое инверторов. Описание этих соединений представляют в виде специальной таблицы, которую называют таблицей программирования. Данная таблица содержит три поля (рис.2): поле матрицы И, поле матрицы ИЛИ, поле УРОВЕНЬ ВЫХОДА. Перед заполнением таблицы реализуемая на ПЛМ система булевых функций должна быть представлена в дизъюнктивной форме. Описание конъюнкций формируется в поле матрицы И. Конъюнкции с номером J формируются по следующему правилу. Если I-я переменная входит в конъюнкцию без инверсии, то на пересечении J-й строки и I-го столбца ставится 1, если с инверсией - то 0. Если в данную конъюнкцию элемент не входит, то ставится символ "-". Описание дизъюнкции формируется в поле матрицы ИЛИ. Дизъюнкция для I-й выходной переменной формируется по следующему правилу. Если J-я конъюнкция входит в дизъюнкцию, то на пересечении J-й строки и I-го столбца ставится символ " * ", иначе символ "·". Каждый из выходов ПЛМ можно получить с инверсией или без нее в зависимости от того, какой из двух символов L (LOW - низкий) или Н (HIGH - высокий) проставлен в поле уровня выхода. Пример реализации булевых функций приведен на рис.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. Конец. Рассмотрим подробнее отдельные пункты алгоритма.
Переход к "инверсной" системе булевых функций
Пусть заданы некоторые СФ [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 в табличной форме.
Перебором по 22- 1 = 3 различным "инверсным" СФ получаем, что минимальное число конъюнкций имеет СФ [S, C]. Тривиальная реализация данной СФ показана на рис.4.
Декомпозиция системы булевых функций
Если для реализации исходной СФ [L, N, B] не хватает промежуточных шин, т.е. B > Q, но имеется резерв по входам и выходам ПЛМ, то может быть использован следующий подход. Рассмотрим комбинационную схему как каскадное соединение комбинационных схем. Пусть первая комбинационная схема описывается СФ [L1, N1, B1] и выполняются следующие условия М £ S: N1+ N2+... + NK£ Т; В1+ В2+... + ВК£ Q, (2)
где М - общее число различных переменных во всех К СФ (max (LI) £ М £ L1+ L2+... + LN). При выполнении условий (2) на одной ПЛМ [S, T, Q] может быть одновременно выполнена тривиальная реализация всех К СФ. Переход от исходной СФ к набору СФ, отвечающих условиям (2), может быть осуществлен аналитическими методами, базирующимися на декомпозиции булевых функций [1]. Например, сумма по модулю два от четырех переменных А, В, С, D может быть представлена следующим образом: A Å B Å C Å D = Y0 Å Y1, где Y0 = A Å B, Y1 = C Å D. Реализация данного варианта вычисления суммы по модулю 2 на ПЛМ приведена на рис.4. В большинстве практических случаев синтеза узлов ЦВМ можно избежать применения достаточно громоздких аналитических методов следующим образом. 1. Задача, решаемая синтезируемой комбинационной схемой, разбивается на ряд подзадач, реализуемых с помощью комбинационных схем. 2. Работа каждой комбинационной схемы описывается соответствующей СФ. 3. Если для полученного набора СФ не выполняются условия (2), то следует попытаться повторить п.п. 1, 2 с другим разбиением на подзадачи. 4. Выполняется тривиальная реализация набора СФ и устанавливаются соответствующие связи между входами и выходами ПЛМ. В некоторых микросхемах ПЛМ часть выходов внутри корпуса микросхемы соединяются со строго определенными входами данной ПЛМ. Эту особенность необходимо учитывать при составлении таблицы программирования. Во всех последующих примерах будем полагать, что используется ПЛМ [16, 8, 17], в которой выход F0может соединяться только со входом А8, выход F1- со входом А9,..., выход Fi- со входом А(8 + i),..., выход F7- со входом А15.
Пример 2. Требуется реализовать на ПЛМ [16, 8, 17] комбинационную схему с шестью входами (Х1, Х2,..., Х6), и тремя выходами (Y1, Y2, Y3). КС должна формировать на выходах Y1, Y2, Y3двоичное число, значение которого равно суммарному количеству единиц на входах. 1. Разбиваем КС на КС1, КС2, КС3, КС4. КС1 и КС2 решают задачу определения числа единиц на входах Х1, Х2, Х3и Х4, Х5, Х6 соответственно. КС3, КС4 суммируют результат работы КС3, КС4. Представление синтезируемой КС в виде каскадного включения КС1 - КС4 приведено на рис.5. 2. Так как КС1, КС2, КС4 можно рассматривать как одноразрядные сумматоры, а КС3 - как сумматор, не использующий перенос из младшего разряда, то работу данных комбинационных схем можно описать следующими СФ. Каждая из КС1, КС2, КС описывается своей СФ [3, 2, 5] (см. пример 1), а КС3 описывается СФ [2, 2, 2]. 3. Условия (2) для полученного набора СФ выполняются. 4. Реализация СФ показана на рис.6. КС1 реализована на ПШ00 - ПШ04, КС2 - на ПШ05 - ПШ09, КС3 - на ПШ10 - ПШ11, КС4 - на ПШ12 - ПШ16.
Синтез конечных автоматов на ПЛМ
Пусть требуется реализовать на ПЛМ конечный автомат (КА), который имеет L входов, N выходов и D элементов памяти. В общем случае в КА должны содержаться две комбинационные схемы - КС для формирования функций возбуждений и КС для формирования выходных сигналов автомата. Эти комбинационные схемы будем обозначать как КС1 и КС2 соответственно. Ограничимся случаем, когда в качестве элементов памяти выступают только D - триггеры. Пусть КС1 описывается СФ1[L1,N1,B1], а КС2 - СФ2 [L2, N2, B2], где L1=L+D, N1=D, N2=N, L2 £ L+D (L2=L+D для автомата Мили, L2= = D для автомата Мура). Тогда реализация КА на ПЛМ в общем случае сводится к совместной реализации СФ1, СФ2 на ПЛМ и установлению соответствующих соединений выходов и входов ПЛМ с триггерами. Синхронизация работы автомата осуществляется путем подачи синхронизирующих импульсов на соответствующие входы триггеров. Пример 3. Требуется реализовать на ПЛМ [16, 8, 19] реверсивный синхронный счетчик с коэффициентом перерасчета 8. Входной сигнал Х (при Х= = 1 - прямой счет, при Х = 0 - обратный). Выходные сигналы Y1, Y2. Если содержимое счетчика равно 111, то Y1= 1, иначе Y1= 0. Если в счетчике записано четное число, то Y2= 1, иначе Y2= 0. Соединение входов и выходов ПЛМ с триггерами и соответствие между входами/выходами счетчика и ПЛМ приведено на рис.7. КС1 реализована на промежуточных шинах ПШ00 - ПШ13. На ПШ00 - ПШ06 выполнен фрагмент КС1, реализующий прямой счет, а на ПШ07 - ПШ13 - реализующий обратный счет. КС2 реализована на ПШ15 - ПШ18. Для простоты в данном примере выполнена тривиальная реализация КС1 и КС2 (путем минимизации число необходимых промежуточных шин может быть уменьшено).
Специфика реализации автомата Мура
В автомате Мура выходной сигнал зависит только от состояния автомата. Эта особенность позволяет в ряде случаев уменьшить число промежуточных шин, используемых при реализации КС2. Пусть на ПЛМ [S, T, Q] выполнена тривиальная реализация СФ1[L1,N1,B1], описывающая работу КС1. Обозначим через V1, V2,..., VDнекоторое состояние автомата (V1=1, если 1-й триггер находится в состоянии 1), а через - [V1, V2,., VD] - множество промежуточных шин, на которых формируется единичный сигнал, если автомат находится в состоянии V1, V2,..., VD. Предположим, что из состояния V1, V2,..., VDотсутствует переход в состояние 0, 0,..., 0, тогда справедливо утверждение. Если автомат находится в состоянии V1, V2,..., VD, то при любых входных сигналах хотя бы на одной из шин множества [V1, V2,..., VD] присутствует единичный сигнал. Пусть требуется формировать некоторый выходной сигнал автомата Y = 1, если автомат находится в состоянии V1, V2,..., VD. В этом случае для получения выходного сигнала Y нет необходимости использовать отдельную промежуточную шину, сигнал Y можно формировать как дизъюнкцию всех промежуточных шин из множества [V1, V2,..., VD]. С учетом вышеизложенного после тривиального синтеза КС1 синтез КС2 может быть выполнен по следующему алгоритму. 1. I:= 1, В:= <число промежуточных шин, задействованных при реализации КС1>. 2. Для всех состояний V1, V2,..., VD, в которых должен формироваться сигнал Y1, выполняются следующие действия 2.1 Если из состояния V1, V2,..., VDне существуют переходы в состояние 0, 0,..., 0, то п.2.5. 2.2 В:= В + 1. 2.3 Если В > Q, то реализация на ПЛМ [S, T, Q] невозможна. Конец. 2.4 На промежуточной шине с номером В в поле матрицы И формируется конъюнкция вида V1, V2,... VD. Данная промежуточная шина соединяется в поле матрицы ИЛИ с выходом Y1. 3. I:= I + 1. 4. Если I < N, то п.2, иначе реализация КС2 выполнена. Конец.
Пример 4. Счетчик из примера 3 требуется реализовать на ПЛМ [16, 8, 15], т.е. для реализации КС2 после реализации КС1 имеется только одна промежуточная шина. Таблица программирования ПЛМ приведена на рис.8. Так как из любого четного состояния счетчика отсутствуют переходы в состояние 0,0,0, то для выполнения фрагмента КС2, формирующего выходной сигнал Y2, не требуется дополнительных промежуточных шин. Из состояния 1, 1, 1, в котором формируется Y1= 1, существует переход в состояние 0, 0, 0. Таким образом, для получения сигнала Y1используется ПШ15.
2. ОПИСАНИЕ ПРОГРАММЫ МОДЕЛИРОВАНИЯ ПЛМ
Общая характеристика программы
Для проверки правильности составления таблицы программирования ПЛМ в лабораторной работе используется специальная программа, которая может рассматриваться как составная часть системы автоматизированного проектирования цифровых устройств на ПЛМ. Данная программа позволяет моделировать ПЛМ с 16 входами (А0 - А15), 8 выходами (F0 - F7) и 30 промежуточными шинами (это близко к ПЛМ 556РТ1, которая отличается от ПЛМ, моделируемой в программе только большим числом (48) промежуточных шин). При моделировании можно имитировать соединение выходов ПЛМ со входами и включение D-триггеров между выходами и входами. При установлении соединений между выходами и входами ПЛМ допустимы только соединения вида F0с А8, F1- с А9,..., Fi- с А(8 + i),..., F7- с А15. Наличие и вид соединения задаются пользователем программы. Программа отображает на экране таблицу описания ПЛМ, текущее состояние входов и выходов ПЛМ и связи между выходами и входами ПЛМ (рис.10). Студент с помощью клавишей терминала по своему усмотрению может изменить содержимое любого из полей таблицы описания ПЛМ. Программа работает в двух режимах - ручном и автоматическом. В ручном режиме студент формирует значение сигналов на входе ПЛМ, а программа определяет соответствующие значения на выходе ПЛМ. В автоматическом режиме значения на входе ПЛМ формируются программой в соответствии с номером варианта. При этом программа контролирует правильность таблицы программирования путем проверки на совпадение ожидаемых и полученных значений на выходе ПЛМ.
Инструкция по работе с программой
1. Программа запускается лаборантом без участия студента. Все сообщения программа формирует в верхнем правом углу экрана. 2. После появления на экране изображения полей ПЛМ (рис. 9) студент, используя клавиши управления курсором или мышь, последовательно описывает поле матрицы И, поле матрицы ИЛИ и поле УРОВЕНЬ ВЫХОДОВ в соответствии с правилами, описанными в подразделе 1.2. Далее в виде строки из восьми символов описывается поле СВЯЗЬ ВЫХОДА СО ВХОДОМ. Каждый первый символ строки описывает связь i-го выхода с 8+i входом. Значения символов следующие: символ "ПРОБЕЛ" - связь отсутствует; символ "D" - связь через D-триггер; символ "." - непосредственная связь. 3. При работе в ручном режиме студент в поле входных переменных формирует соответствующие значения и нажимает клавишу <Enter>. Программа считывает входные переменные и в поле выходных переменных отображает их значения. При формировании выходных значений программа учитывает связи между выходами и входами ПЛМ. Если программа обнаруживает недопустимые символы в полях ПЛМ, то данные символы помечаются знаком "#", выдается соответствующее сообщение с указанием числа ошибочных символов. Таким образом, изменяя значение входных переменных и нажимая клавишу < Enter >, можно просмотреть работу схемы на различных наборах входных переменных. При обнаружении ошибок в работе схемы студент, используя клавиши управления, может подвести курсор к любому символу из описания ПЛМ и исправить этот символ. 4. Переход из ручного режима в автоматический осуществляется путем одновременного нажатия клавиш <Ctrl-Tab>. В автоматическом режиме путем нажатия клавиши < Enter > выполняется пошаговая проверка для всех указанных в заданном варианте исходных данных. По окончании всех проверок выдается сообщение о числе обнаруженных ошибок. 5. Переход из автоматического режима в ручной осуществляется путем одновременного нажатия клавиш < Ctrl-Tab >.
3. ПРАКТИЧЕСКАЯ ЧАСТЬ ЛАБОРАТОРНОЙ РАБОТЫ
Практическая часть лабораторной работы включает синтез на ПЛМ следующих цифровых устройств: а) преобразователя кодов (см. лаб. раб. № 2); б) некоторый узел ЦВМ, являющийся конечным автоматом. Студенту требуется разработать таблицы программирования ПЛМ и проверить правильность составления таблиц программирования с помощью моделирующей программы. При составлении таблиц для ПЛМ следует учитывать ограничения, которые обусловлены спецификой моделирующей программы.
4. ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ
Подготовка к лабораторной работе
1. Выбрать из табл.5 к лабораторной работе № 2 исходные данные для преобразователя кодов. 2. Установить соответствие между входами/выходами ПЛМ и входами/выходами преобразователя кодов. 3. Составить таблицу программирования ПЛМ для преобразователя кодов. 4. Выбрать из табл.1 исходные данные для синтеза конечного автомата. 5. Установить соответствие между входами/выходами ПЛМ и входами/выходами автомата. 6. Выбрать входы и выходы ПЛМ для подключения элементов памяти. 7. Составить таблицу программирования для синтезируемого автомата. 8. Подготовить тестовый пример (для проверки работы синтезируемого автомата).
Работа в учебной лаборатории
После запуска лаборантом моделирующей программы студент выполняет следующие действия. 1. Вводится описание таблицы программирования ПЛМ для преобразователя кодов. 2. В ручном режиме проверяется и в случае ошибки редактируется описание таблицы программирования. 3. Окончательная проверка выполняется в автоматическом режиме. Результат проверки демонстрируется преподавателю. 4. Вводится описание таблицы программирования ПЛМ для конечного автомата. 5. В ручном режиме проверяется и в случае ошибки редактируется описание таблицы программирования. 6. Работа автомата демонстрируется преподавателю.
5. СОДЕРЖАНИЕ ОТЧЕТА
1. Исходные данные для синтеза преобразователя кодов. 2. Описание основных этапов синтеза преобразователя кодов. 3. Таблица программирования ПЛМ для преобразователя кодов. 4. Исходные данные для синтеза заданного конечного автомата. 5. Описание основных этапов синтеза конечного автомата. 6. Таблица программирования ПЛМ для конечного автомата. Функциональное назначение входов и выходов ПЛМ. 7. Тестовый пример. Таблицы программирования составляются в виде, приведенном на рис.10.
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
1. Баранов С.И., Скляров В.А. Цифровые устройства на программируемых БИС с матричной структурой. М.: Радио и связь, 1986. 2. Щелкунов Н.Н., Дианов А.П. Процедуры программирования логических матриц // Микропроцессорные средства и системы. 1986 № 2. С.71-76. 3. Угрюмов Е.П. Проектирование элементов и узлов ЦВМ. М Высшая школа, 2004.
СОДЕРЖАНИЕ
Читайте также: I. Психологические и поведенческие техники, подготавливающие к увеличению продолжительности жизни. Воспользуйтесь поиском по сайту: ©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...
|