Синтез конечного автомата для устройства управления ЭВМ

Обобщенная структурная схема конечного автомата КА (рис.1) содержит запоминающее устройство ЗУ (память на

триггерах Т1-Тn) и два комбинационных устройства КУ для формирования сигналов q1, q2,...,qn управления триггерами (КУ1) и для формирования требуемых выходных сигналов y1, y2,...,yk (КУ2).

Рис.1 Обобщенная структурная схема КА

КА работает циклами, заканчивая их всякий раз возвращением в исходное состояние.

По сигналу с ДШ команд схема запуска формирует входной сигнал x, который принимает только два значения: x1=0 (пауза в работе КА) и x2=1 (запуск и работа КА).

В ходе выполнения цикла КА в заданные моменты времени t1, t2, t3,... проходит через определенную последовательность внутренних состояний a(t) =al (l=0, 1,..., S), сменяющих друг друга при поступлении очередного тактового импульса Ф. При этом каждый цикл функционирования КА начинается в момент t поступления на его вход сигнала запуска x(t) =1.

Часть этих состояний (и тактов), пребывание в которых сопровождается выдачей импульса на какой-либо выход y1, y2,..., y16, можно назвать активными, а остальные, обеспечивающие заданные паузы между выдачами импульсов, - пассивными.

В качестве примера рассмотрим задачу синтеза КА с 1 входом и 16 выходами, который после запуска выдает импульс:

через (j+1) =(1+1) =2 тактовых интервалов - на выход с

номером (i+1) =(1+1) =2;

2) через (i+1) =(1+1) =2 тактов - на выход с номером

(j+1) =(1+1) =2;

3) через (i+j+9) =(1+1+9) =11 тактов - на выходы с номерами (j+4) =(1+4) =5 и (i+6) =(1+6) =7 и формирует сигнал “сброс” W=1, необходимый для возвращения КА в исходное состояние.

Здесь i=1, j=1 - предпоследняя и последняя цифры в номере зачетной книжки.

В состав КА входит генератор тактовой частоты. Он предназначен для синхронизации (т.е. согласования во времени) работы компонентов КА. Генератор формирует периодическую последовательность импульсов Ф с заданной частотой.

Тактовый интервал равен периоду периодической последовательности импульсов Ф.

В соответствии с заданием можно получить временную диаграмму работы КА (рис.2). Задание рекомендуется выполнить в следующем порядке:

1) по последним цифрам i и j номера зачетной книжки рассчитывают общее число состояний (S+1) КА, определяют необходимое количество триггеров n, активные состояния (такты) автомата, номера активных выходов;

2) строят граф, который задает алгоритм функционирования КА; составляют таблицы состояний и выходных сигналов КА, а по ним составляют таблицы истинности для сигналов на активных выходах и синтезируют функциональную схему КУ1, КУ2 в логическом базисе, заданном табл.1.

Таблица 1

Базис для синтезируемой схемы

3) В соответствии с ГОСТ 2.743-82 “Обозначения условные графические в схемах. Элементы цифровой техники” вычерчивают полную принципиальную электрическую схему КА, включая схему запуска, цепи возврата в исходное состояние (цепи “сброса”). ИМС выбирают из табл.2.

Таблица 2

Рекомендуемый перечень микросхем

Рис. 2. Временная диаграмма работы КА

Из временной диаграммы видно, что активными тактами в рабочем цикле КА будут такты с номерами 2 и 11; активными выходами - выходы с номерами 2, 5,

7. Каждый цикл функционирования КА начинается в момент поступления на его вход сигнала запуска x(t) =1. При поступлении очередного тактового импульса Ф, максимальное число которых в цикле КА равно максимальному числу рабочих тактов R=i+j+9=1+1+9=11.

КА проходит ряд сменяющих друг друга состояний a(t) =al (l=0, 1,..., S). Число рабочих состояний равно S, а общее число состояний КА, включая исходное a0, равно S+1 и связано с максимальным числом рабочих тактов R соотношением S?R.

Выполнение этого условия обеспечивает возможность выдачи выходного импульса на любом такте цикла.

Минимально необходимое количество триггеров определяется из соотношения n?log2(S+1).

Для разрабатываемого КА минимальное количество триггеров n=4, так как 24>11.

Для определения активных состояний следует задать определенный порядок их чередования в рабочем цикле КА, т.е. функцию переходов. Целесообразно принять алгоритм функционирования КА с функцией переходов, обеспечивающей естественный порядок смены состояний (рис.3). В этом случае КУ1 и память синтезируемого КА превращаются в суммирующий двоичный счетчик с параллельным переносом и коэффициентом пересчета Ксч=i+j+9=1+1+9=11, а КУ2 - в дешифратор состояний.

Рис.3. Алгоритм функционирования КА, заданный с помощью графа

Выходной сигнал КА может принимать значение произвольного 16-разрядного двоичного числа. Выходные сигналы КА могут быть описаны табл.3.

Таблица 3

Таблица выходных сигналов КА

Каждое состояние КА отождествляется с записанным в триггеры n-разрядным двоичным числом (табл.4).

Таблица 4

Таблица состояний КА

Для КА с естественной сменой состояний в порядке возрастания их номеров активными оказываются состояния а2, а11 (на втором и одиннадцатом тактах).

Для синтеза КУ1 и КУ2 следует задать таблично функцию переходов (табл.5) и функцию выходов (табл.6).

Таблица 5

Таблица функции переходов

Таблица 6

Таблица функции выходов

Для синтеза ЗУ целесообразно использовать ИМС К555ТВ6, которая содержит два JK-триггера с общим выводом питания (рис.4).

Рис.4. JK - триггер типа К555 ТВ6

Данные в каждом триггере переносятся от входов на выходы по отрицательному перепаду тактового импульса С. Когда импульс С переходит от высокого уровня к низкому, сигналы на входах J и K изменяться не должны. Данные от входов J и K следует загружать в триггер, когда на входе С присутствует напряжение высокого уровня. Режим работы триггера из микросхемы К555ТВ6 следует выбирать из табл.7.

Таблица 7

Состояния триггеров микросхемы К555ТВ6

Асинхронные входы сброса R имеют низкий активный уровень. Если на входе R будет напряжение низкого уровня, прохождение сигналов от входов C, J и K запрещается. На выходе Q появляется напряжение низкого уровня (первая строка табл.7). Остальные четыре режима работы возможны лишь при напряжении высокого уровня на входе R. Когда J=K=H, состояние выходов под действием отрицательного перепада на тактовом входе C не меняется (режим: хранения - нет изменений). Опираясь на таблицы состояний и выходных сигналов, а также таблицу состояний JK-триггеров ИМС

К555ТВ6 составляют полную таблицу функционирования КА (табл.8).

Таблица 8

Полная таблица функционирования КА, при построении ЗУ на JK-триггерах

Из анализа кодовых комбинаций для сигналов на управляющих входах триггеров для первого триггера видно, что он работает в режиме простого деления на два. Такой режим работы обеспечивается при J1=1, K1=1.

Для того, чтобы провести минимизацию для функций, определяющих каждый из управляющих сигналов триггеров Т2, Т3, Т4 данные из табл.8, касающиеся значений сигналов на их управляющих входах, переносят на карты Карно (рис.5).

Рис.5. Карты Карно для сигналов на управляющих входах JK-триггеров

В этих картах по четыре клетки не заполнены: эти клетки соответствуют неиспользованным кодовым комбинациям. Совокупность четырех триггеров может находиться в одном из шестнадцати состояний: 24=16, из которых в счетчике используется двенадцать.

Часть клеток в картах заполнена символом “X”, что означает, что минимизируемая функция может при данном наборе аргументов Q1... Q4 принимать любое значение: 0 или 1.

Особенностью минимизации логических функций, значение

которых при определенных наборах аргументов не играет роли (незаполненные клетки и клетки с символом “X”) является то, что при проведении в картах контуров, охватывающих единицы, можно включать в эти контуры также и клетки, в которых функция не определена.

Синтез КУ1 осуществляют по логическим функциям для сигналов на управляющих входах триггеров:

J1=1,K1=1,

J2=Q1Q2,K2=Q1Q2,

J3=Q1Q2Q3Q4 K3=Q1Q2Q3,

J4=Q1Q2Q3,K4=Q1Q2Q4.

Так как сигналы V2, V5, V7, W только один раз за цикл принимают единичное значение, то при синтезе КУ2 аналитические выражения для их логических функций получают сразу, минуя этап минимизации:

V2=Q1Q2Q3Q4,

V5=V7=W=Q1Q2Q3Q4.

Используя полученные аналитические выражения для логических функций КУ1 и КУ2 синтезируют схему автомата на выбранных из табл.2 ИМС (Рис.6).

Рис.6. Принципиальная электрическая схема КА при построении ЗУ на JK-триггерах

В КА JK-триггер целесообразно использовать в качестве синхронного счетного триггера, в котором на тактовый вход подают тактовые импульсы Ф с генератора тактовой частоты, а счетные импульсы q подают на соединенные входы J и K (рис.7).

Рис.7. Преобразование JK-триггера в синхронный счетный триггер ФС (TV-триггер)

Текущее состояние счетного триггера определяется не информацией на входах, а состоянием его в предыдущем такте. При входной комбинации Jn=Kn=1 с каждым тактовым импульсом происходит опрокидывание триггера, и его выходные сигналы меняют свое значение, а при Jn=Kn=0 он переходит в режим хранения информации независимо от смены сигналов на входе C(Ф). Это расширяет функциональные возможности счетного триггера, позволяя в нужные моменты времени сохранять информацию на его выходах в течение требуемого числа тактов.

Уравнение такого триггера выглядит следующим образом:

Qn+1=(nQnVФnQn) qnVQnn,

а его переключательная функция характеризуется табл.9.

Таблица 9

Состояния синхронного счетного триггера

Опираясь на таблицы состояний и выходных сигналов, а также таблицу состояний синхронного счетного триггера составляют полную таблицу (табл.10) функционирования КА.

Так как в рассматриваемом случае задействованы не все состояния КА (не задействованы состояния a12, a13, a14, a15), то логические функции q1, q2, q3, q4 оказываются не полностью определенными, отчего в их таблицах истинности появляются “безразличные” переменные, обозначенные символами “x”, которые по мере необходимости могут принимать значения 1 или 0.

Кроме того в табл.6 составной частью входят таблицы истинности не только для q1, q2, q3, q4, а также - выходных сигналов y2, y5, y7 и сигнала сброса W, так как все эти функции зависят от переменных Q1(t), Q2(t), Q3(t), Q4(t).

Таблица 10

Полная таблица функционирования КА, при построении ЗУ на синхронных счетных триггерах (TV-триггерах)

Получим МДНФ для сигналов управления триггерами на картах Карно (рис8).

Рис.8. Карты Карно для сигналов на управляющих входах TV-триггеров

Синтез КУ1 осуществляют на логических функциях для сигналов управления триггерами:

q1=1; q2=Q1; q3=Q1Q2; q4=Q1Q2Q3, а синтез КУ2 - по ранее полученным уравнениям (рис.9).

Рис.9. Принципиальная электрическая схема КА при построении ЗУ на TV-триггерах

Сравнивая схемы Рис.6 и рис.9 можно установить, что применение TV-триггеров упрощает синтез КА: при синтезе схемы Рис.6 использовано 14 логических элементов, а схемы рис.9 - только10: на 4 меньше.

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

2. Индивидуальное задание