Основы проектирования на плис 2 страница

Метод основан на двух процедурах: неполного склеивания и поглощения. Аксиома неполного склеивания имеет вид:

Ах + А/х = Ах + А/х +А.

Здесь под А подразумевается любое алгебраическое выражение, в том числе и произведение нескольких аргументов. Правую часть можно упростить и довести ее просто до А, но это не делается сознательно. Несмотря на кажущуюся тавтологию, аксиома имеет смысл вследствие того, что в этом случае не теряются сокращаемые члены, как в обычной алгебре. Благодаря этому возможно исследование всех вариантов сокращения с последующим выбором оптимального. Для выбора используется вторая аксиома, поглощения:

АХ +А = А

Она очевидна и используется на втором этапе минимизации. Суть ее состоит в том, что после цепочки неполных склеиваний в конечной записи остаются только те произведения, которые не подвергались склеиваниям на предыдущих этапах.

Наконец, на завершающем этапе минимизации строится таблица Квайна, с помощью которой делается окончательный выбор минимальной ДНФ.

Проиллюстрируем алгоритм на примере функции четырех аргументов, задав ее таблично (см. рис. 1.11).

Х4	Х3	Х2	Х1	Y

Рисунок 1.11. - Функция четырех аргументов

Запишем ее СДНФ:

Y = |X1|X2|X3|X4₁ + X1|X2|X3|X4₂ + |X1X2X3|X4₃ + X1X2X3|X4₄ + |X1|X2|X3X4₅ + X1|X2|X3X4₆ + |X1|X2X3X4₇ + X1|X2X3X4₈ .

В выражении каждая конституента пронумерована для дальнейшего облегчения преобразований.

Первым шагом алгоритма является просмотр возможностей неполного склеивания. Для этого необходимо, чтобы претенденты на склеивание имели одинаковую длину, одинаковые аргументы и отличались друг от друга только в одном аргументе, причем этот аргумент в одном произведении был без инверсии, а во втором – с инверсией. Просмотр лучше проводить с начала списка.

Итак, первый член СДНФ можно склеить со вторым:

/Х1/Х2/Х3/Х4 + Х1/Х2/Х3/Х4 = А + /Х2/Х3/Х4.

Здесь А – выражение слева. Кроме того, первый член склеивается и с пятым:

/Х1/Х2/Х3/Х4 + /Х1/Х2/Х3Х4 = В + /Х1/Х2/Х3.

Продолжая ту же процедуру, проводим следующие склеивания: 2 и 6; 3 и 4; 5 и 6; 6 и 8; 7 и 8. В результате получаем:

Y = Q + |X2|X3|X4₉ + |X1|X2|X3₁₀ + X1|X2|X3₁₁ + Z2Z3|X4₁₂ + |X1|X2X4₁₃ + |X2|X3X4₁₄ + X1|X2X4₁₅ + |X2X3X4₁₆ .

Продолжаем склеивания в полученных сокращенных формах, помня упомянутое выше правило. При этом возможно склеивание следующих проиндексированных членов: 9 и 14, 13 и 15, 14 и 16. Получается выражение:

Y = W + |X2|X3 + |X2X4 + |X3X4.

Отметим, что на первом этапе склеиваний участвовали все члены СДНФ, а на втором не участвовали члены с номерами 10, 11 и 12. При составлении таблицы Квайна они должны учитываться.

Таблица Квайна строится следующим образом. Первый столбец содержит сокращенные формы, оставшиеся после поглощения. Первая строка перечисляет все конституенты СДНФ. Тело таблицы заполняется так: если рассматриваемая сокращенная форма входит в состав данной конституенты, на пересечении ставится значок (например, +) , если нет, делается пропуск. На рис. 10 приведена таблица для рассматриваемого примера.

|X2|X3	+	+			+	+
|X2X4					+	+	+	+
X1|X2|X3		+				+
X2X3|X4			+	+

Рисунок 1.12. – Таблица Квайна

Необходимо, чтобы минимальным набором сокращенных произведений накрывались все столбцы. Формальное правило требует, что в минимальную форму обязательно входили такие сокращенные произведения, которые содержат хотя бы один плюсик, единственный в одном из столбцов. В нашем примере это первое, второе и четвертое произведение. Третье можно исключить как избыточное. Таким образом, минимальная ДНФ имеет вид:

Y = |X2|X3 + |X2X4 + X2X3|X4

Элементы теории конечных автоматов

Теория конечных автоматов была разработана в средине ХХ века группой ученых, в состав которой входили Н.Винер, А.Тюринг, Дж. Фон Нейман и др. Созданная ими теория послужила основанием для создания всего семейства цифровой техники. ПЛИС также входят в это семейство.

Конечный автомат (КА) является частным случаем конечной динамической системы (КДС). Последняя имеет следующие отличительные признаки:

1. Она работает в дискретные моменты времени, называемые тактами. Такты могут определяться с одинаковыми временными интервалами или с различным шагом во времени. Соответственно различают системы с равномерной и неравномерной тактностью. В общем случае тактом можно объявлять любой момент времени, в который происходит какое – то изменение или на входе или выходе системы или внутри самой системы.

2. КДС имеет конечное число входов и выходов. Количество состояний по каждому входу (т.е. количество различных входных воздействий), а также количество различных выходных состояний КДС также конечно.

3. Реакция КДС на входные воздействия также конечна, т.е. длится конечное число тактов.

Под понятие КДС можно подвести практически любое цифровое устройство. Исключением могут являться, например, генераторы или таймеры (да и то в случае, если они не имеют входов управления).

КА можно считать простейшим вариантом КДС по крайней мере по одному показателю: его динамические свойства распространяются только на два соседних такта. Один из них называется настоящее (Н), второй – прошлое (П).

Различают два типа КА. Первый тип обладает следующим свойством: его текущее состояние (т.е. в такт Н) зависит от предыдущего состояния и воздействия на него в настоящее время. Такой КА называется автоматом типа П – Н, или автоматом Мура. Второй тип зависит также от предыдущего состояния, но от воздействия в предыдущий такт. Это – автоматы типа П – П, или автоматы Мили.

Способы задания конечных автоматов

Существует три основных способа описания (задания) КА. Первый, табличный, является основным. Таблица КА – это прямоугольная таблица размером N*M, где N – количество выходных состояний, а М – количество входных состояний. Пример таблицы приведен на рис. 1.13. Здесь через Y_I обозначены выходные состояния КА, через X_J - входные воздействия.

	X1	X2	X3	X4	X5
Y1	Y2	Y4	Y1	Y4	Y1
Y2	Y1	Y1	Y2	Y3	Y3
Y3	Y2	Y3	Y4	Y1	Y2
Y4	Y1	Y1	Y4	Y2	Y4

Рисунок 1.13. – Пример таблицы конечного автомата

Принято считать, что между конечным автоматом и его таблицей существует взаимно однозначное соответствие, т.е. таблице соответствует единственный КА и наоборот. Недостатком табличного описания является отсутствие указания типа КА (П – П или П – Н), но это можно указать дополнительно.

Второй тип описания – диаграммы состояния, или диаграммы переходов. Это направленные графы, в которых число вершин равно числу выходных состояний, а направленные дуги соответствуют переходам КА при соответствующем входном воздействии. Воздействия надписываются над дугами, причем для КА типа П –П надписи делаются в началах дуг, а П – Н в концах, Так как граф получается громоздким, допускается кратные дуги заменять одной с записью входного воздействия в виде суммы. Пример диаграммы состояний приведем из таблицы по рис 1.14. Диаграмма приведена в предположении, что автомат – типа П – Н.

Рисунок 1.13 – Диаграмма состояний конечного автомата

Третий вариант задания КА – перечислением триад – совокупностей троек значений Y^P-1 X^P Y^P , т.е. предыдущего состояния, воздействия и конечного состояния. Это – для автомата типа П – Н; для автомата П – П в триаду включается Х^Р-1.

Этот метод используется редко из – за громоздкости, но применяется в задачах синтеза.

Синтез конечных автоматов

Используется разработчиками для разработки и реализации КА по формальному описанию его работы. Такое описание называется лента работы. Это полубесконечная таблица из двух строк: в первой записываются значения Х_I , во второй – Y_J . По имеющейся записи на ленте осуществляется заполнение таблицы КА, причем способ просмотра ленты зависит от типа КА. Для автоматов типа П – П и П – Н считывание проводится по форме, показанной на рис. 1.14, что соответствует принципам их работы.

Синтез осуществляется следующим образом. Составляется шаблон таблицы, исходя из списка на ленте и производится заполнение таблицы, начиная с левой ее части. Выбираем автомат типа П – П. Пара X4Y2 имеет результат Y3. Заполняем соответствующий элемент в таблице и смещаем шаблон вправо на шаг. Результат, Y1 также заносим в таблицу. Продолжая заполнение таблицы аналогичным образом, доходим до противоречия: пара X2Y1 по ленте должна давать Y1, но это место в таблице занято элементом Y2. Здесь возможны два решения: или считать КА нереализуемым, или переопределить состояние на ленте. Выберем второй вариант: заменим элемент на ленте табличным вариантом и продолжим просмотр. В результате после просмотра выделенного фрагмента ленты таблица принимает вид, показанный на рис. 1.15. Она заполнена не до конца, поэтому нужно или продолжать просмотр, или считать незаполненные ячейки недопустимыми состояниями.

При реализации КА возможны тупиковые ситуации, когда автомат попадает в состояние, из которого нет выхода: при любом входном воздействии его состояние не изменяется. В таких случаях вводится специальное входное состояние Х0 (сброс), которое переводит КА в исходное состояние. Кстати, такое входное воздействие предусмотрено на любом техническом устройстве и называется кнопкой аварийной остановки.

Триггеры как конечные автоматы

С изобретением триггеров произошла техническая революция во всех областях. Для человеческой цивилизации это изобретение можно сопоставить с такими достижениями, как способ добычи и поддержания огня, изобретение рычага и колеса. Совершенство и изящество электронной схемы триггера послужили толчком в развитии средств микроэлектроники, в том числе ПЛИС.

В основном триггеры (Т) являются элементами памяти, элементарной ее ячейкой. Т может иметь два устойчивых состояния, 0 или 1, причем сохраняет это состояние сколько угодно долго. В них используется эффект положительной обратной связи (ПОС), что и обеспечивает их свойства. Они могут быть реализованы на релейно – контактных устройствах, на транзисторах, электронных лампах, полупроводниковых структурах и т.д. Благодаря своей изящной структуре они легко переносятся на любую основу из нанотехнологий.

Рассмотрим простейший тип Т – асинхронные RS – триггеры. Асинхронными они называются вследствие того, что срабатывают сразу при поступлении управляющего сигнала. Они имеют два управляющих входа: S (от слова set – включить) и R (от слова reset – выключить). Любой триггер имеет два устойчивых состояния: 0 или 1. Обычно Т имеет два взаимно инверсных выхода, Q (от слова quit – выход) и |Q.

В дальнейшем будем рассматривать Т, реализованные на элементах И – НЕ и ИЛИ – НЕ. Схема RS – триггера на элементах ИЛИ – НЕ приведена на рис. 1.16. Использованы два элемента 2ИЛИ – НЕ, D1 и D2. Они, как видно из рисунка, охвачены перекрестной ПОС: выход D1 присоединен ко второму входу D2, а выход D2 – ко второму входу D1.

Рисунок 1.16. – Схема RS – триггера

Рисунок 1.17. - Временные диаграммы

На рис. 1.17 приведены временные диаграммы работы триггера. Предположим, вначале триггер находится в состоянии 0: на выходе D2 ноль, на выходе D1- единица. Благодаря тому, что единица с выхода D1 поступает на вход D2, состояние D2 подтверждается, и триггер сохраняет свое состояние.

Если в момент времени t₁ на входе S (вход D1) появится единица, элемент D1 переключается в 0, а за счет ПОС с выхода D1 на вход D2 это переключение происходит очень быстро. Повторная подача 1 на вход S (момент времени t¹ на временной диаграмме) состояние триггера не меняет. Он будет в единице до поступления управляющего воздействия на S – вход (момент t₂ на временной диаграмме). В это время он устанавливается в 0. Дальнейшая часть диаграммы просто повторяет процесс работы триггера.

Обязательным условием устойчивой работы RS – триггера является недопустимость одновременной подачи единиц на оба входа. Такая ситуация называется коллизия и приводит к неопределенному состоянию триггера. Для устранения коллизий иногда используют триггеры с преобладанием или по R, или по S – входу, но такой вариант используется редко.

Второй тип RS – триггеров – использование элементов И – НЕ. Схема такого триггера приведена на рис.1.18. В отличие от предыдущего варианта, триггер имеет инверсные входы, т.е. управляется нулями. Здесь запрещенной является одновременная подача нулей на оба входа.

Опишем RS – триггер как конечный автомат. Таблица состояний такого КА будет иметь вид, показанный на рис.1.19. При нулях на входах триггер сохраняет предыдущее состояние, при подаче управляющих воздействий на один из входов он безусловно переключается, а одновременная подача единиц запрещена.

Рисунок 1.19. – Таблица состояний

Диаграмма состояний RS – триггера приведена на рис. 1.20. Из нее видно, во – первых, что триггер относится к КА типа П – Н (надписи - у концов дуг), а во – вторых, что повторная подача управляющего воздействия не изменяет состояния триггера (петли на графе).

Рисунок 1.20. – Диаграмма состояний

На практике Т часто используются для формирования коротких фронтов импульсов: используется эффект ПОС. Еще одно важное применение Т – устранение «дребезга» контактов. При механическом замыкании или размыкании контактов при наличии напряжения возникают микроэлектрические дуги. Они и называются дребезгом. При маломощной коммутации особого вреда может не наблюдаться, но для работы подключенного к ним оборудования это недопустимо. Для устранения этого эффекта используют свойство триггера не реагировать на повторное управление. Схема такого подключения приведена на рис.1.21.

Рисунок 1.20. - Устранение дребезга

Еще один вариант RS – триггеров – введение в них синхронизации. Схема синхронизируемого RS – триггера приведена на рис. 1.22. Схема выполнена на трехвходовых элементах 3И - НЕ. При этом добавляется вход синхронизации С, дающий тот эффект, что переключение триггера возможно только при подаче 0 на вход С импульса синхронизации. Описание Т как конечного автомата не изменяется, только вместо входов R и S появляются входы CR и CS.

Рисунок 1.22. - Синхронизация триггера

Другая разновидность Т – JK – триггеры. В отличие от триггеров RS, они не имеют запрета на одновременную подачу управляющих воздействий на оба входа. При таком воздействии JK – триггеры переходят в противоположное состояние, что позволяет использовать их в новом качестве.

Таблица состояний JK – триггера показана на рис. 1.23. В отличие от RS, изменился последний элемент нижней строки. На диаграмме состояний (см. рис. 1.24) при неизменном внешнем виде изменились надписи над двумя дугами.

Рисунок 1.23. – Таблица состояний

Рисунок 1.24. – Диаграмма состояний

Несмотря на кажущуюся легкость в описании, реализация JK – триггера значительно сложнее, чем RS. На рис. 1.25 приведена схема синхронизируемого JK – триггера с дополнительными установочными входами.

Рисунок 1.25. – Схема синхронизируемого JK – триггера

По структуре триггер двухтактный. Он фактически состоит из двух триггеров: первого на элементах D1и D2 и второго, на элементах D4 и D5. Вход синхронизации С подается через инвертор D3 на вторую часть схемы, что и обеспечивает двухтактность (второй триггер срабатывает по противоположному фронту управляющего импульса). Наличие обратных связей с выхода D5 на вход D1 и с выхода D4 на вход D2 обеспечивает главное отличие триггера, а именно его переход в противоположное состояние при одновременной подаче единиц на входы J и K. Управляющие воздействия S и R на дополнительные входы второго триггера обеспечивают его безусловную установку.

На рис 24,б показано изображение JK – триггера на принципиальных схемах.

Триггеры такого типа используются редко ввиду своей громоздкости. Обычно идут на пути уменьшения количества входов (оставляют один установочный вход, чаще R) или переходят на более практичные D – триггеры.

D – триггер, или триггер задержки, обычно имеет четыре входа: D, C, S и R. Последние являются установочными и необязательными. Сущность работы D – триггера состоит в том, что он переключается по входу С (точнее, по переднему или заднему фронту управляющего импульса на этом входе) и переходит в состояние, которое в этот момент присутствует на входе D. В этом и состоит сущность задержки.

Существует множество практических схем на D – триггерах, часть из которых мы рассмотрим позднее. Пока ограничимся изображением D – триггера на схемах (рис. 25) и включением его в счетном режиме (рис. 26). В последнем случае установочные входы не показаны

Практические приложения ПЛИС

В теории конечных автоматов и цифровых систем принято различать устройства с быстрой и медленной тактностью. В первом варианте используются естественные задержки на срабатывание отдельных вентилей, Этот вариант обеспечивает высокое быстродействие, но имеет и недостатки. Главный из них - необходимость учета пути следования сигналов, и принятия дополнительных мер для синхронизации. При усложнении устройства эта проблема значительно усложняется.

Второй недостаток – усиление зависимости от внешних факторов, особенно от температуры. Время задержки на срабатывание очень сильно зависит от температуры и носит к тому же случайный характер.

Эти недостатки серьезно снижают возможности систем с быстрой тактностью или требуют дополнительных мероприятий по компенсации нежелательных явлений.

Системы с медленной тактностью основаны прежде всего на внешней синхронизации. Это намного снижает риск коллизий и зависимость от внешних условий.

В ПЛИС имеется возможность использовать оба метода за счет их структурной избыточности. Тем не менее, в дальнейшем будет отдаваться предпочтение системам с синхронизацией. Исключение будет делаться только для комбинационных схем.

Комбинационные схемы

Из множества различных комбинационных схем рассмотрим только двоичные шифраторы и дешифраторы. Они нужны для иллюстрации возможностей комбинаторики и послужат в дальнейшем для их программирования.

Двоичные шифраторы предназначены для преобразования позиционного кода в двоичный. Позиционный код – это множество из N входов, на каждом из которых может быть 0 или 1. Количество разрядов двоичного кода К определяется по формуле: К ≥ log₂ N.

Предположим, N = 12. Тогда К = 4. Составляем таблицу номеров позиционного кода и эквивалентных им двоичных кодов (рис. 27).

№	23	22	21	20

Рисунок 1.27. – Таблица кодов

Чтобы получить двоичный шифратор, в данном случае необходимо иметь К схем ИЛИ (в данном случае 4) с числом входов у каждой, равным количеству 1 в соответствующем столбце. В данном случае в первом и втором столбцах по 5 единиц, а в третьем и четвертом – по 6,следовательно, необходимы две 5 – входовых и две 6 – входовых схемы ИЛИ. Схема шифратора примет вид, приведенный на рис. 1.28.

Рисунок 1.28. – Шифратор на 12 входов

При этом может возникнуть сложность, связанная с тем, что таких схем может не быть; тогда они могут синтезироваться из схем с меньшим числом входов. Например, схема ИЛИ на 6 входов при наличии только двухвходовок примет .

Рисунок 1.29.- Схема 6 ИЛИ

вид, изображенный на рис. 1.29.

Дешифраторы выполняют функцию, противоположную шифраторам. Они имеют К входов двоичного кода и N выходов позиционного и реализуются на К – входовых схемах И. Количество схем И равно количеству выходов. Дополнительно в них вводятся К инверторов Схема дешифратора кода из предыдущего примера, т.е. (4,12) приведена на рис. 1.30. Для упрощения изображения на входе рисуется жгут. Поясним принцип работы дешифратора по схеме. Он содержит 12 четырехвходовых схем И D1,…D12 и 4 инвертора D12….D16. Логика работы следующая. Допустим, D1 настроен на единицу. Двоичный код единицы 0001. Для того, чтобы сработала схема D1, нужно , чтобы на всех ее входах были единицы. Поэтому младший разряд на вход D1 подключается непосредственно, а старшие – через инверторы. Соответственно и маркировка выходов из жгута: 1.2.3.8. Код цифры 9 – 1001, поэтому маркировка выходов 5,2,3,8.

Рисунок 30. – Дешифратор

Для реализации многовходовых схем И используется или параллельное, или каскадное включение. Здесь также возможны варианты. Например, для создания 6 – входовой схемы И из двухвходовок можно применить параллельное включение, как это показано на рис. 31, в можно и каскадное, по типу рис. 32. Последний вариант удобнее для программирования.

Рисунок 1.31. – Схема 6И

Рисунок 1.32 – Схема 6И, каскадная

Возможности конструирования логических устройств еще больше увеличиваются при использовании схем типа И – НЕ и ИЛИ – НЕ. При этом широко используются аксиомы Де Моргана: |(X1 + X2) = |X1&|X2 и |(X1&X2) = |X1 +|X2. На практике это называется инверсная логика: функция И преобразуется в ИЛИ и наоборот. Например, функцию 7И можно реализовать по типу рис.1.33, а функцию 6ИЛИ – по варианту рис. 1.34. Отметим, что это – не лучшие варианты реализации. Вентили D4 и D8 на рис.1.33 и D7 на рис. 1.34 выполняют функции инверторов и показаны здесь для иллюстрации возможностей схем.

Рисунок 1.33. - Схема 7И, вариант 1

Рисунок 1.34. - Схема 7И, вариант 2

В заключение этого раздела приведем пример реализации ДНФ из ранее приведенного примера раздела «минимизация методом Квайна». Имеем функцию вида:

Y = |X2|X3 + |X2X4 + X2X3|X4 .

Так как осталось для реализации 3 аргумента, устройство имеет три входа и один выход. Схема для его реализации приведена на рис. 1.35. Она содержит 3 инвертора D1, D2 и D3, схемы D4 – D6, реализующие умножения. и D7 для сложения.

Рисунок 1.35. - Пример реализации ДНФ

Повышенные возможности для инженерного синтеза представляют схемы с использованием триггеров, так как у них имеются и прямые, и инверсные выходы, что предоставляет дополнительные возможности для инженерного синтеза.

При достаточно сложных системах управления возникают проблемы с правильностью реализации. Особенно остро ставятся проблемы с возможными коллизиями из – за различных задержек по времени срабатывания. Недоучет этого может привести к возникновению импульсов помехи или ложным срабатываниям. Простой пример: устройство должно отрабатывать заданное число циклов, которое задается на специальном счетчике. Если на его входе возникают помехи, возникающие из – за недоучета времен задержки по разным каналам, счетчик завершит работу раньше положенного. Найти такие помехи при отладке оборудования очень непросто, так как импульсы очень короткие, и их тем же осциллографом не обнаружить.

Для отладки цифровой техники желательно использовать компьютерное моделирование. В настоящее время существует достаточно большое количество моделирующих пакетов, которые должны быть на вооружении профессиональных инженеров.

Устройства с использованием триггеров

В принципе эта тема достаточно обширна и может рассматриваться в специальных дисциплинах по схемотехнике. Здесь приводится остаточно компактный набор типичных схем, которые впоследствии могут реализовываться на ПЛИС.

Элементы задержки

Задержка нужна для выравнивания фронтов, синхронизации элементов или ля задания технологических пауз в системах управления.

Возможны быстрые и тактируемые (медленные) задержки. Быстрые реализуются последовательным включением нескольких элементов. Время задержки пропорционально количеству элементов в цепочке. Обычно время срабатывания задается в паспорте на ПЛИС и измеряется микросекундами, поэтому диапазон задержек ограничен. Кроме того, время задержки имеет большую случайную составляющую, зависящую к тому же от внешних факторов, особенно от температуры.