Синтез логической схемы цифрового автомата

Построение таблицы переходов по логической схеме цифрового автомата

Цифровой автомат – любое последовательное устройство. Цифровой автомат в общем случае содержит N триггеров. Состояние цифрового автомата характеризуется N-разрядным двоичным словом, каждый разряд которого ассоциируется с состоянием соответствующего триггера т.к. для N разрядного слова существует 2^N кодовых наборов , 2^N состояний будет характеризовать и поведение цифрового автомата.
Любой цифровой автомат в общем случае может быть представлен структурно как совокупность  двух подсистем:

   Поведение структуры описывается 4-мя группами сигналов:
Х – кодовое слово входного воздействия
Z – кодовое слово, обеспечивающее требуемый порядок смены состояний цифрового автомата
Q- кодовое слово, характеризующее состояние цифрового автомата

Сигнал С- синхронизации, инициирующий переключение триггера в триггерной подсистеме. Формирование С, как правило, непосредственно связано с алгоритмом работы устройства, в любом конкретном случае оговаривается отдельно.
   При проектировании цифрового аппарата необходимо определить объем памяти или число триггеров, обеспечивающих заданный алгоритм работы цифрового аппарата:
n≥log2^M , где
n- ближайшее большое число,
М- число необх. из условий работы состояний цифрового аппарата
Необходимое число состояний цифрового аппарата М может быть определено как максимальное число значений выходного сигнала, которое может существовать при одном значении входного сигнала.
   Работа цифрового аппарата может быть описана любой формой записи. Однако на практике чаще для первичной постановки задачи использовать словесное описание  и таблицы состояний (переходов) или графы переходов (схемы состояния) т.к. все эти формы описывают один и тот же алгоритм работы, они  легко преобразуется одна в другую.
Пример: Автомат для формирования сигнала перегрузки пассажирского лифта.
   Допустим, что одновременно в кабине лифта, вмещающей 6 человек, могут транспортироваться не более 3-х человек. Если число пассажиров превышает 3-х, то  должен выдаваться сигнал на блокировку работы лифта (сигнал перегрузки).
   Входным сигналом является двоичный код, 1 в нулевом разряде который обозначает больше числа пассажиров на 1, что фиксируется датчиком, а 1 в первом разряде – уменьшение пассажиров на 1.
   Решение: По словесному описанию алгоритма на входе цифрового автомата возможно действие трех различных входных сигналов:

1. число пассажиров в лифте остается неизменно
2. число пассажиров в лифте больше на одного
3. число пассажиров в лифте меньше на одного

Таблица состояний включает: G+1 столбец, где G – число различных входных сигналов, которые могут быть на входе цифрового автомата: т.е. 3+1=4 столбца.
2ⁿ строк
   Число необходимых состояний М определяется из анализа работы устройства:
- лифт пуст
- в лифте 1 чел
- в лифте 2 чел
- в лифте 3 чел
- в лифте 4 чел
- в лифте 5 чел
- в лифте 6 чел

М=7 n≥log2⁷ n=3 т.е. исп.3 триггера состояние цифрового автомата характеризуется 3-х разр. двоичным числом строк 2³=8

Таблица состояний цифрового автомата

При заполнении таблицы состояния на пересечении j-го и i-ой строки
Записывается дробь:
- в числителе записывается состояние, в которое попадает цифровой автомат после прихода очередного импульса С, если он находился в  i-ом состоянии и на его вход действовал j-ый входной сигнал
- в знаменателе указывается текущее значение выходного  сигнала существующего в цифровой автомат до прихода очередного импульса С при нахождении его в i-ом состоянии при действии j-го входного сигнала.
   Граф переходов – представляет собой графическую интерпретацию работы цифрового автомата. Им удобно пользоваться, если при первичном описании до конца не рассмотрен весь алгоритм работы и нельзя определить число М возможных состояний.
   При числе состояний 2ⁿ >16 граф нагляднее таблицы.
Каждое состояние цифрового автомата изображено в виде окружности с указанием N или кода соответствующего состояния.
   Переход от одного состояния к другому изображено в виде стрелки.
   Над стрелкой записывается дробь:
- в числителе которой, дано значение входного сигнала, под действием которого, при очередном импульсе С, произойдет указанный переход.
- в знаменателе записывается текущее значение выходного сигнала, соответствующее указанным состоянию и значению выходного сигнала.
   Состояние 111 является лишним, т.к. с точки зрения устройства оно не используется. В графе переходов лишние состояние образуют изолированную вершину

Так, если лифт пустой (что соответствует  S=000) и в него входит один человек (входной сигнал 01), то следующим будет новое состояние (S=001).При этом сигнал перегрузки Z не формирует 0.
Правила синтеза логической схемы цифрового автомата.

1. По условию работы цифрового автомата определяют число необходимых состояний и требуемый объем памяти его триггерной подсистемы
2. Выполняют формальное описание алгоритма работы цифрового автомата, т.е. составляют таблицу состояний или граф переходов.
3. Выбирают тип триггера для реализации триггерной подсистемы.
4. Используя формализованный алгоритм работы цифрового автомата и таблицы истинности для выбранного типа триггера, составляют расширенную таблицу переходов.

Число строк таблицы равно максимальному числу значений входного сигнала комбинационной подсистемы.
Число столбцов таблицы 5:
Х – входной сигнал;
Qn – текущее состояние;
Qn+1 – следующее состояние;
Y – входные сигналы на информационных входах триггеров;
Z – выходные сигналы.

1. Используя расширенную таблицу переходов, минимизируют ФАЛ, описывающие комбинационную подсистему цифрового автомата.
2. По полученным ФАЛ строят логическую схему цифрового автомата.

Пример: Вернемся к нашему примеру.
  1 и 2 пункты уже сделаны, выберем тип триггера.
Нет однозначных рекомендаций по выбору типа триггера, чтобы в дальнейшем получить наиболее простую техническую реализацию. Однако при выборе триггера, информационные сигналы которые содержат большое число неопределенных значений входного сигнала, структура цифрового аппарата получается более проста.
   Рекомендуется предпочтение отдавать JK,RS и триггер
3 пункт: выбираем JK-Триггер
4 пункт: получение расширенной таблицы истинности
   По таблице состояний – на вход комбинационной подсистемы действующих 5 переменных: х1,х0 – входные управляющие сигналы,
Q2 Q1 Q0 – вых. сост. триггерной подсистемы
Расширенная таблица истинности должна содержать 2⁵=32 строки, что усложняет процедуру проектирования.
Для упрощения проектирования необходимо понизить число входных переменных комбинационной подсистемы.
Обратимся к таблице состояний.
Объем памяти  понижать не можем, т.к. он определяется числом состояний М.

Пути упрощения данного алгоритма:

2 способ:
2-х разрядный код воздействия отражает всего 2 ситуации человек вошел в лифт (01) и человек вышел (10)
Код 11 невозможен по условиям работы устройства
Код 00 при нем по каждому сигналу С происходит подтверждение текущего состояния и выходных сигналов устройства.
Того же эффекта можно добиться если нет изменения состояния,  сигнал С будет отсутствовать и триггер будет в режиме хранения информации.
Тогда используя асинхронный триггер, внешнее воздействие на устройство можно представить одноразрядным двоичным кодом.
Число строк ниже в 2 раза:
2⁴=16

1 способ:
Присвоение входным воздействиям различного приоритета, так чтоб устройство при поступлении одновременно нескольких входных сигналов выбирало бы наиболее важный.
   Так по условию надо формировать сигнал перегрузки. Увеличение числа пассажиров (х0=1) – имеет повышенный приоритет.
   Таблица истинности должна рассматривать все возможные ситуации в работе, для однозначного определения поведения устройства в любых аварийных ситуациях.
Хотя по условию работы входной сигнал 11 не возможен, по таблице истинности должны рассмотреть все варианты.
   При появлении кода 11 устройство должно реагировать как на сигнал 01.
Тогда в данном случае можно сократить число строк на 8.
2 способ: Воспользуемся вторым способом, но этот способ не снял вопрос об изолированных вершинах графа переходов, т.е. надо предусмотреть возможность выхода устройства из запрещенных аварийных ситуаций. Место алгоритма, куда должно вернуться устройство при этом, определяется из условий его работы.
   Пусть у нас формируется сигнал аварии и триггерная подсистема возвращается в исходное состояние (000). Пусть такие же действия сопровождаются и  нереальные ситуации (лифт пуст, а человек из него выходит).

   Скорректированный с учетом сказанного алгоритм приведен в таблицу переходов:

Z1=1 – сигнал перегрузки
Z0=1 сигнал аварии

По скорректированной таблице переходов построить расширенную таблицу истинности с учетом выбранного типа триггера.

По таблице истинности записываем ФАЛ:

По ФАЛ можно построить принципиальную схему:
Берем 3 триггера и заводим на каждый вход соответствующие функции.
Схема большая приводить не будем.

Построение таблицы переходов по логической схеме цифрового автомата

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

1. По логической схеме цифрового автомата записывают ФАЛ, связывающее его выходные сигналы и сигналы на информационных входах Т с входными сигналами и кодами состояний триггерной подсистемы.
2. Строят расширенную таблицу истинности.
3. Записываются все возможные комбинации входных сигналов и кодов состояния триггерной подсистемы
4. По ФАЛ для записанных входных воздействий комбинационной подсистемы отыскивают соответствующие значения выходных сигналов и сигналов на информационных входах триггеров;
5. По известным информационным сигналам триггеров и таблице истинности переходов находят коды следующих состояний триггерной подсистемы
6. По расширенной таблице истинности составляют таблицу состояний или граф переходов цифрового автомата.

Пример:
Для заданной схемы определяют на входное воздействие вида 1,1,0,0,1,1,0 при условии, что в исходном положении код состояния триггерной подсистемы =11.

Решение:
1. Записываем ФАЛ для выходных сигналов Z1 и Z0 и сигналов на информационных входах триггеров Т1 и Т0.




2.Заполняем расширенную таблицу истинности.
Для этого сигнала записываем не возможные комбинации сигналов х и Q1nQ0n, находим Z1, Z0 и Т1, Т0 и по таблице переходов Т-триггера следующее состояния триггеров (n+1).

3.Строим граф переходов.

Для временных диаграмм предположим, что в момент n T прихода синхроимпульса на входе управления есть предыдущий сигнал Х и его смена происходящая после переключения триггеров.

Вернутся к содержанию...