Построение счетчика методом управления сбросом

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

Рассмотрим этот метод применительно к реализации синхронного счетчика с параллельным переносом на JK-триггерах. Функции возбуждения двоичного счетчика указанного типа, как известно, имеют вид J_i=K_i=Q₀Q₁…Q_i_-1 (в младшем триггере J₀=K₀=1). Введем в эти функции сигнал сброса R, изменив их следующим образом: J_i=(Q₀Q₁…Q_i_-1), K_i= J_i+R. Схема формирования функций возбуждения триггеров счетчика представлена на рис. 4.37.

Рис. 4.37. Схема формирования функций возбуждения и ее подключение к

триггерам счетчика

Пока сигнал сброса отсутствует (R=0), функции J_i и K_i не отличаются от соответствующих функций двоичного счетчика. Когда сигнал R=1, все функции J_i становятся нулевыми, а K_i – единичными, что заставляет все триггеры сброситься по приходе следующего такта. Если сигнал R появится как следствие достижения в счетчике числа М-1, то будет реализована последовательность счета 0, 1, 2, …, М-1, 0, …, т.е. счетчик с модулем М.

Конъюнктор, входящий в состав схемы, тоже вырабатывает сигнал сброса, но при достижении содержимым счетчика значения М-1. В случае построения четырехразрядного двоично-десятичного счетчика на входы конъюнктора Q₀Q₁Q₂Q₃ необходимо, соответственно подключить выходы счетчика , что приведет к сбросу всех разрядов счетчика по пришествию сигнала счета, последующего после достижения счетчиком числа 1001₂=9₁₀, т.е. счетчик действительно работает как двоично-десятичный.

4.8 Распределители тактов

Распределители тактов тоже относятся к разряду счетчиков, но в отличие от счетчиков, рассмотренных ранее, особенностью этих счетчиков является то, что код, записанный в его разряды, не является двоичным, т.е. это счетчики с недвоичным кодированием. Наибольшее практическое значение среди таких счетчиков имеют счетчики с кодом «1 из N» или распределители тактов и счетчики Джонсона.

4.8.1 Распределители импульсов и распределители уровней

Основной областью применения распределителей тактов являются системы синхронизации и управления. На их основе получают импульсные последовательности с заданными временными диаграммами. Для этого можно вначале разбить период временной диаграммы на части («кванты»), соответствующие минимальному интервалу временной диаграммы, применив задающий генератор с частотой m/T, где m – число квантов в периоде T диаграммы. Выходные импульсы задающего генератора затем распределяются во времени и пространстве так, что каждый квант появляется в свое время и в своем пространственном канале.

На рисунке 4.38.а представлена структура распределителя тактов (РТ), согласно которой РТ имеет 1 вход, на который подаются импульсы с задающего генератора (ЗГ), и N выходов, причем первый импульс генератора передается на первый выход (канал) РТ, второй – на второй и т.д.

Рис. 4.38 Структура распределителя тактов (а) и временные диаграммы распределения уровней (б) и импульсов (в)

Распределители тактов бывают двух типов: распределители уровней (РУ) и распределители импульсов (РИ).

Временная диаграмма работы распределителя уровней представлена на рис. 4.38.б. Как видно из этой диаграммы паузы между активными состояниями каналов РУ отсутствуют.

Временные диаграммы, представленные на рис. 4.38.в, соответствуют работе распределителя импульсов. В данном распределителе тактов на выходе каждого канала появляется импульс, длительность которого соответствует длительности входных импульсов от ЗГ. Распределители импульсов не имеют самостоятельной схемотехники, они реализуются на основе распределителей уровней путем включения в их выходные цепи конъюнкторов, на вторые входы которых подаются импульсы задающего генератора.

Имея распределенные во времени и пространстве «кванты», можно по схемам ИЛИ собирать из них импульсные последовательности с необходимыми временными диаграммами. Часто нужны именно те последовательности, которые вырабатываются непосредственно распределителями тактов.

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

4.8.2 Кольцевой регистр сдвига

Одним из вариантов схемотехнического решения распределителя тактов, а точнее – распределителя уровней, является сдвигающий регистр, замкнутый в кольцо (кольцевой регистр сдвига), если записанное в этот регистр слово содержит всего одну единицу. При сдвигах единица перемещается с одного выхода на другой, циркулируя в кольце. Число выходов РТ равно разрядности регистра. На рис. 4.39 представлена структурная схема РТ на 3 выхода, в виде кольцевого регистра сдвига, созданного на синхронных D-триггерах.

Рис. 4.39. Структурная схема РТ на базе кольцевого регистра сдвига

Недостаток данной схемы состоит в потере правильного ее функционирования при сбое. Т.е. если в силу каких-либо причин слово (только одна единица) в регистре исказится, то возникшая ошибка будет постоянной, а это значит, что данная схема не обладает свойством самозапуска.

На рис. 4.40 представлена схема РТ на кольцевом регистре сдвига с самовосстановлением за несколько тактов. Работа этой схемы основана на том, что на вход регистра подаются нули, пока в нем имеется хотя бы одна единица. Таким образом, лишние возникшие единицы на его входе будут устранены и, когда регистр очистится, сформируется сигнал записи единицы на его входе. Следовательно, потеря единственной единицы также будет исключена. Выход ЛЭ, выполняющего самовосстановление схемы, дает еще один дополнительный канал. На схеме, приведенной на рис. 4.40, показаны также цепи пуска/останова РТ и два варианта выхода – для распределителя уровней (непосредственно с триггеров и ЛЭ ИЛИ-НЕ) и распределителя импульсов (после стробирования сигналов распределителя уровней импульсами сдвига на цепочке конъюнкторов).

Рис. 4.40. Схема распределителя тактов с автоматическим вхождением в рабочий цикл

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

Рис. 4.41. Диаграмма состояний РТ с автоматическим вхождением в рабочий цикл за один такт

Таблица 4.7

Q₁	Q₂	Q₃	Q_1H	Q_2H	Q_3H	Q₁	Q₂	Q₃	Q_1H	Q_2H	Q_3H

Выбрав для построения схемы D-триггеры, учтем, что функция возбуждения этого триггера D=Q_H. Исходя из таблицы истинности, для функций D_i=Q_iH имеем следующие соотношения:

, и .

Схема распределителя тактов с автоматическим вхождением в рабочий цикл за один такт представлена на рис. 4.42.

Рис. 4.42. Функциональная схема распределителя тактов с автоматическим вхождением в рабочий цикл за один такт

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

4.8.3 Счётчик Джонсона

Для увеличения количества выходных каналов РТ при том же количестве триггеров кольцевого регистра сдвига применяется кольцевой регистр сдвига с перекрестной обратной связью, который получил название счетчик ДжонсонаилиМёбиусаилиЛибау-Крейга. Такой счетчик имеет обратную связь на первый триггер от инверсии последнего триггера кольцевого регистра (рис. 4.43.а). Он имеет 2n состояний, т.е. при той же разрядности вдвое больше, чем обычный кольцевой регистр, а это значит, что с его помощью можно реализовать РТ с количеством выходных каналов в 2 раза больше по сравнению с РТ, реализованным на основе обычного кольцевого регистра сдвига. В то же время выход счетчика Джонсона представлен не в коде «1 из N», что требует преобразования кодов для получения выходов распределителя тактов. Такие преобразователи очень просты, что обуславливает применение счетчиков Джонсона в составе распределителей тактов.

Рис. 4.43 Функциональная схема счетчика Джонсона (а) и временные диаграммы его работы (б)

Показанный на рисунке четырехразрядный счетчик Джонсона при начальном нулевом состоянии работает следующим образом. Первый импульс сдвига установит первый триггер в единичное состояние (), в остальных разрядах будут нули как результат сдвига нулей от соседних слева разрядов. Второй импульс сдвига сохраняет единичное состояние первого триггера, т.к. по прежнему . Второй разряд окажется в единичном состоянии, поскольку примет единицу от первого триггера. Остальные разряды будут нулевыми. Последующие сдвиги приведут к заполнению единицами всех разрядов счетчика, т.е. «волна единиц», распространяясь слева направо приведет счетчик в состояние 1111. Следующий импульс сдвига установит первый разряд в ноль, т.к. теперь . Этим начинается процесс распространения «волны нулей». После восьми импульсов повторится состояние 0000, с которого начато рассмотрение работы счетчика. Временные диаграммы описанных процессов показаны на рис. 4.43.б.

Особенность рассмотренной схемы – четное число состояний при любом количестве разрядов n счетчика, т.к. 2n – всегда число четное. Обычный кольцевой счетчик такого ограничения не имеет.

Преобразование выходного кода счетчика Джонсона в код «1 из N» требует добавления всего одного двухвходового элемента И либо И-НЕ для каждого выхода распределителя тактов. Принцип дешифрации состоит в выявлении положения характерной координаты временной диаграммы – границы между зонами единиц и нулей (табл. 4.8).

Таблица 4.8

Номер состояния	Q₁	Q₂	Q₃	Q₄	Номер состояния	Q₁	Q₂	Q₃	Q₄

В двух случаях (для слов, состоящих только из нулей или только из единиц) состояние выявляется анализом крайних разрядов. В остальных случаях анализируются разряды на границе зоны единиц и нулей.

Как видно из таблицы, преобразование выходного кода счетчика Джонсона в код «1 из N» осуществляется согласно следующим выражениям:

, , , ,

, , и ,

где F_i (i=0…7) – выходы распределителя тактов.

По полученным выражениям строится дешифратор. Рассмотрим дешифратор на ЛЭ И-НЕ (с инверсными выходами). В таком дешифраторе можно дополнительно принять меры по предотвращению перекрытий импульсов в соседних каналах, возможных из-за различных задержек элементов. Используя элементы с тремя входами и «косыми связями» (рис. 4.44.а) можно запретить начало импульса в последующем канале до его завершения в предыдущем.

Рис. 4.44. Функциональная схема дешифратора кода Джонсона в код «1 из N» (а), структурная схема распределителя тактов на основе счетчика Джонсона и временные диаграммы его работы (б)

Распределитель тактов в целом (рис. 4.44.б) имеет выходные сигналы в коде «1 из N».

Для схем со счетчиком Джонсона могут возникнуть вопросы преодоления ограничения обязательной четности числа состояний счетчика и обеспечения автоматического вхождения его в рабочий цикл (свойства самозапуска).
Первую задачу можно решить в рамках подхода, применявшегося при построении счетчиков с произвольным модулем, т.е. исключением одного «лишнего» состояния. Получить схему с исключенным состоянием можно уже не раз показанным способом, переходя от таблицы функционирования (истинности) к функции возбуждения триггеров и далее к схеме. Однако в данном случае нетрудно сократить этот путь, воспользовавшись простыми рассуждениями. Пусть исключению подлежит состояние 11..11. Чтобы его исключить необходимо перейти к следующему состоянию не из состояния «все единицы», а от предыдущего состояния 11…10, которое создает единицу в предпоследнем разряде счетчика, т.е. ноль на инверсном выходе этого разряда. Подавая нулевой сигнал на вход счетчика вместе с основным сигналом обратной связи через конъюнктор (показан на рис. 4.44.б штриховой линией) исключим состояние 11…11 и получим счетчик с нечетным числом состояний 2n-1.

Задача обеспечения вхождения распределителя на основе счетчика Джонсона в рабочий цикл связана с тем, что базовая схема, рассмотренная выше, свойством самозапуска не обладает. Например, распределитель с трехразрядным счетчиком Джонсона имеет общее число возможных состояний 2³=8, а число состояний в рабочем цикле 2×3=6. Неиспользуемыми являются два состояния: 010 и 101. Нетрудно заметить, что из состояния 010 счетчик перейдет в состояние 101, а из состояния 101 в состояние 010. Таким образом, наряду с замкнутым рабочим циклом существует цикл из двух неиспользуемых состояний, попав в который, схема без постороннего воздействия не сможет перейти в рабочий цикл.

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

Распределители тактов на основе счетчика Джонсона характеризуются небольшими аппаратурными затратами (1/2 триггера и один двухвходовой вентиль на 1 канал) и достаточно высоким быстродействием (время установления = сумма задержек переключения триггера и вентиля). Счетчики Джонсона реализованы, в частности, в сериях ИС типа КМОП (микросхемы ИЕ9 и ИЕ19 серии К531 и др.), причем одной из причин их применения является отсутствие импульсных помех в цепи питания, создаваемых микросхемами. Распределитель тактов в целом реализован в ИС К561ИЕ8.

4.9 Контрольные вопросы

1. Нарисуйте схемы бистабильных ячеек на ЛЭ ИЛИ-НЕ и И-НЕ и почсните их работу.

2. Нарисуйте схему классификации триггеров.

3. Нарисуйте временные диаграммы работы асинхронного RS триггера с прямыми входами.

4. Опишите отличия R-триггера, S-триггера и E-триггера от RS-триггера.

5. Нарисуйте таблицу истинности JK-триггера.

6. Нарисуйте функциональные схемы синхронного RS-триггера в базисе ИЛИ-НЕ и И-НЕ

7. Нарисуйте временные диаграммы работы синхронного RS-триггера с синхронизацией по переднему и по заднему фронту.

8. Нарисуйте функциональную схему R-триггера на базе RS-триггера.

9. Нарисуйте функциональную схему JK-триггера на базе RS-триггера.

10. Нарисуйте функциональную схему D-триггера на базе JK-триггера.

11. Нарисуйте функциональную схему n-разрядного регистра на D – триггерах.

12. Дайте определения счётчика и опишите классификацию счётчиков.

13. Дайте определения модуля счёта счётчика, разрешающей способности, время регистрации и ёмкости.

14. Опишите различные способы реализации произвольных модулей счёта в счётчиках.

15. Нарисуйте временные диаграммы работы распределителей уровней и импульсов.

16. Нарисуйте схему распределителя уровней на базе счётчика и дешифратора.

17. Нарисуйте схему распределителя импульсов на базе кольцевого регистра сдвига.

18. Нарисуйте функциональную схему счетчика Джонсона и временные диаграммы его работы.

Тема 5. Схемотехника цифровых узлов

Лекция 5

Как было указано в предыдущем разделе, большинство современных цифровых устройств являются последовательностными или цифровыми автоматами с памятью, состоящими из комбинационной схемы и элементов памяти – запоминающих элементов (ЗЭ) (рис.4.1). Там были рассмотрены

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

5.1 Цифровые автоматы и их разновидности

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

В состав цифровых автоматов обязательно входят запоминающие элементы (элементы памяти). Выходные сигналы в таких автоматах формируются в зависимости от входных сигналов и состояний, в которых находятся элементы памяти. Наличие элементов памяти придает ЦА свойство иметь некоторое внутреннее состояние А, определяемое совокупностью состояний всех элементов памяти. В зависимости от внутреннего состояния ЦА различно реагируют на один и тот же набор входных сигналов. Воспринимая входные сигналы Z при определенном состоянии, ЦА в соответствии с заложенной в него программой переходит в новое состояние и вырабатывает выходные сигналы W. Переходы ЦА из одного состояния в другое начинаются с некоторого исходного состояния, задание которого также является частью задания автомата. В конечном счете, текущее состояние и выходы автомата зависят от начального состояния и всех наборов входных сигналов, поступивших на автомат в предшествующие моменты времени. Таким образом, вся последовательность входных сигналов определяет последовательность состояний автомата и его выходных сигналов. Это объясняет название «последовательностные схемы».

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

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

Цифровые автоматы в каноническом представлении разделяют на две части (рис. 5.1): память (ЭП) и комбинационную цепь (КЦ). На входы КЦ подаются входные сигналы Z_t и сигналы состояния A_t цифрового автомата. На ее выходе вырабатываются выходные сигналы W_t и сигналы перевода ЦА в новое состояние A_t₊₁.

Рис. 5.1. Структурная схема асинхронного (а) и синхронного (б) цифровых автоматов

В асинхронных автоматах (рис. 5.1.а) очень часто роль элементов памяти играют элементы задержки, через которые сигналы состояния A_tпередаются на входы КЦ, чтобы совместно с новым набором входных переменных Z_t определить следующую пару значений выходов W_t и состояния A_t₊₁ на выходе. Элементы асинхронного ЦА переключаются под непосредственным воздействием изменений входных сигналов. Скорость распространения процесса переключений в цепях асинхронного автомата определяется собственными задержками элементов, поэтому моменты переходов из одного состояния в другое заранее не определены и могут совершаться через неравные между собой промежутки времени.

В синхронных автоматах имеются специальные входы С для подачи синхросигналов, которые разрешают элементам памяти прием данных только в определенные моменты времени. Элементами памяти (ЭП) в таких автоматах служат синхронные триггеры. Моменты времени, в которые оказывается возможным изменение состояния автомата, определяются специальным устройством – генератором синхронизирующих импульсов, выход которого подключается на вход С синхронного автомата. Соседние моменты времени оказываются при этом обычно разделенными равными временными промежутками. Процесс обработки информации в синхронных ЦА упорядочивается во времени, и в течение одного такта возможно распространение процесса переключения только в строго определенных пределах тракта обработки информации.

5.2 Абстрактный и структурный автоматы

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

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

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

Математической моделью ЦА (а в общем случае любого дискретного устройства) является так называемый абстрактный автомат, определенный как 6-компонентный кортеж: S=(A, Z, W, d, l, а₁) у которого:

1. A={a₁, a₂, ... ,a_m} - множество состояний (внутренний алфавит),

2. Z={z₁, z₂, ... ,z_f} - множество входных сигналов (входной алфавит),

3. W={w₁, w₂, ..., w_g} - множество выходных сигналов (выходной алфавит),

4. d : A·Z®A - функция переходов, реализующая отображение D_d ÍА·Z в А. Иными словами функция d некоторым парам “состояние - входной сигнал” (а_m, z_f) ставит в соответствие состояния автомата а_s= d (a_m, z_f), a_sÎA,

5. l : A·Z®W - функция выходов, реализующая отображение D_l ÍА·Z на W. Функция l некоторым парам “состояние - входной сигнал” (а_m, z_f) ставит в соответствие выходные сигналы автомата W_g=l(а_m, z_f), W_gÎW,

6. a_i ÎA - начальное состояние автомата.

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

Рис. 5.2. Абстрактный автомат

Абстрактный автомат (рис. 5.2) имеет один вход и один выход. Автомат работает в дискретном времени, принимающем целые неотрицательные значения t = 0,1,2,... В каждый момент t дискретного времени автомат находится в некотором состоянии a(t) из множества состояний автомата, причем в начальный момент t = 0 он всегда находится в начальном состоянии a(0)=a1. В момент t, будучи в состоянии a(t), автомат способен воспринять на входе букву входного алфавита z(t)ÎZ. В соответствии с функцией выходов он выдаст в тот же момент времени t букву выходного алфавита W(t)=l(a(t), z(t)) и в соответствии с функцией переходов перейдет в следующее состояние a(t+1)=d[a(t), z(t)], a(t) ÎA, w(t) ÎW.

Смысл понятия абстрактного автомата состоит в том, что он реализует некоторое отображение множества слов входного алфавита Z во множество слов выходного алфавита W. Т.е. если на вход автомата, установленного в начальное состояние a1, подавать буква за буквой некоторую последовательность букв входного алфавита z(0), z(1),... - входное слово, то на выходе автомата будут последовательно появляться буквы выходного алфавита w(0), w(1),... - выходное слово. Таким образом, выходное слово = =j(входное слово), где j - отображение, осуществляемое абстрактным автоматом.

На уровне абстрактной теории понятие "работа автомата" понимается как преобразование входных слов в выходные. Можно сказать, что в абстрактном автомате отвлекаемся от его структуры - содержимого прямоугольника (рис. 5.1), рассматривая его как "черный ящик", т.е. основное внимание уделяем поведению автомата относительно внешней среды.

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

На практике наибольшее распространение получили два класса автоматов - автоматы Мили (Mealy) и Мура (Moore).

Закон функционирования автомата Мили задается уравнениями:

a(t+1) = d(a(t), z(t)); w(t) = l(a(t), z(t)), где t = 0,1,2,...

Закон функционирования автомата Мура задается уравнениями:

a(t+1)=d(a(t), z(t)); w(t) = l(a(t)), где t = 0,1,2,...

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

Кроме автоматов Мили и Мура иногда оказывается удобным пользоваться совмещенной моделью автомата, так называемым С- автоматом.

Под абстрактным С- автоматом будем понимать математическую модель дискретного устройства, определяемую восьмикомпонентным вектором

S=( A, Z, W, U, d, l₁, l₂, а₁), у которого:

1. A={a₁, a₂, ... ,a_m} - множество состояний;

2. Z={z₁, z₂, ... ,z_f} - входной алфавит;

3. W={w₁, w₂, ..., w_g} - выходной алфавит типа 1;

4. U={u₁, u₂,...,u_h} - выходной алфавит типа 2;

5. d : A · Z ® A - функция переходов, реализующая отображение D_d ÍА·Z в А;

6. l₁ : A · Z ® W - функция выходов, реализующая отображение D_l₁ ÍА·Z в W;

7. l₂ : A ® U - функция выходов, реализующая отображение D_l₂ ÍА в U;

8. а₁Î А - начальное состояние автомата.

Абстрактный С-автомат можно представить в виде устройства с одним входом, на который поступают сигналы из входного алфавита Z, и двумя выходами, на которых появляются сигналы из алфавитов W и U. Отличие С-автомата от моделей Мили и Мура состоит в том, что он одновременно реализует две функции выходов l₁ и l₂, каждая из которых характерна для этих моделей в отдельности. Закон функционирования С- автомата можно описать следующими уравнениями: а( t + 1)=d(a( t), z( t)); w( t)=l₁(a( t), z( t)); u( t)=l₂(a( t)), где t = 0, 1, 2, ...

Выходной сигнал U_h=l₂(a_m) выдается все время, пока автомат находится в состоянии a_m. Выходной сигнал Wg=l₁(a_m, z_f) выдается во время действия входного сигнала Z_f при нахождении автомата в состоянии a_m.

Рассмотренные выше абстрактные автоматы можно разделить на:

1) полностью определенные и частичные;

2) детерминированные и вероятностные.

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

Частичным называется абстрактный автомат, у которого функция переходов или функция выходов, или обе эти функции определены не для всех пар (a_i, z_j).

К детерминированным относятся автоматы, у которых выполнено условие однозначности переходов: автомат, находящийся в некотором состоянии a_i, под действием любого входного сигнала z_j не может перейти более, чем в одно состояние.

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

Абстрактный автомат называется конечным, если конечны множества А = {a₁, a₂, ..., a_m}, Z = {z₁, z₂, ..., z_f}, W = {w₁, w₂, ..., w_g}. Автомат носит название инициального, если в нем выделено начальное состояние a₁.

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

В отличие от абстрактного автомата, имеющего один вход и один выход (рис. 5.3.а), на которые поступают сигналы во входном и выходят в выходном W={W₁,..,W_G} алфавитах, структурный автомат (рис. 5.3.б) имеет L входных каналов х₁,х₂,..,х_L и N выходных y₁,y₂,…,y_N на каждом из которых присутствует сигнал структурного алфавита.

Рис.5.3. Абстрактный (а) и структурный (б) автоматы

Обычно в качестве структурного используется двоичный алфавит. В этом случае каждому входному сигналу Z_F абстрактного автомата соответствует некоторый двоичный вектор (l_f1,l_f2,..,l_fL), где l_fLÎ{0,1}.

Очевидно, что для представления (кодирования) входных сигналов Z₁,..,Z_F абстрактного автомата различными двоичными векторами должно быть выполнено условие L ] log₂F [, аналогично N ] log₂G [. Например, Z={Z₁,Z₂,Z₃,Z₄} и W={W₁,W₂,W₃}, тогда L log₂4=2 и N log₂3=2

Закодировать входные и выходные сигналы можно, например, так: Z₁ = 00, Z₂ = 01, Z₃ = 10, Z₄ = 11, W₁ = 00, W₂ = 01 и W₃ = 11.

Следовательно, структурный автомат с двумя входами x₁ и x₂ и двумя выходами y₁ и y₂ может быть представлен в виде, представленном на рис.5.4:

Рис.5.4 Структурный автомат с двумя входами x₁ и x₂ и двумя

выходами y₁ и y₂

5.3. Способы описания и задания автоматов

Для того, чтобы задать автомат, необходимо описать все компоненты кортежа S=(A, Z, W, d, l, а₁). Множества А, Z, W описываются и задаются простым перечислением своих элементов. Среди многообразия различных способов заданий функций d и l (следовательно и всего автомата в целом) наибольшее распространение получили табличный и графический.

При табличном способе задания автомат Мили описывается с помощью двух таблиц. Одна из них (таблица переходов) задает функцию d, т.е. a(t +1)=d(a(t), z(t)) (табл. 5.1), вторая (таблица выходов) - функцию l, т.е. W(t)=l(a(t), z(t)) ( табл. 5.2).

Каждому столбцу из приведенных таблиц поставлено в соответствие одно состояние из множества А, каждой строке – один входной сигнал из множества Z. На пересечении столбца a_m и строки z_f в табл. 5.1 записывается состояние a_s, в которое должен перейти автомат из состояния a_m под действием входного сигнала Z_f, т.е. a_s=d(a_m, z_f). На пересечении столбца a_m и строки z_f в табл. 5.2 записывается выходной сигнал W_g, выдаваемый автоматом в состоянии a_m при поступлении на вход сигнала z_f, т.е. W_g = l(a_m, z_f).

Для приведенных таблиц множества, образующие автомат A={a₁, a₂, a₃,a₄}, Z={z₁, z₂}, W={w₁, w₂, w₃, w₄, w₅}. Автомат Мили может быть задан одной совмещенной таблицей переходов и выходов (табл. 5.3), в которой каждый элемент a_s / w_g записанный на пересечении столбца a_m и строки z_f, определяется следующим образом: a_s=d(a_m, z_f); w_f=l(a_m, z_f).

Автомат Мура задается одной отмеченной таблицей переходов (табл. 5.4), в которой каждому столбцу приписаны не только состояние a_m, но еще и выходной сигнал W_g, соответствующий этому состоянию, где W_g=l(a_m).

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

Для задания С - автоматов также используется табличный метод. В этом случае таблица переходов (табл.5.5) аналогична таблице переходов автомата Мили, а в таблице выходов каждое состояние отмечено соответствующим выходным сигналом u_i выходного алфавита типа 2 (табл.5.6).

При графическом способе автомат задается в виде ориентированного графа, вершины которого соответствуют состояниям, а дуги - переходам между ними. Дуга, направленная из вершины a_m, задает переход в автомате из состояния a_m в состояние a_s. В начале этой дуги записывается входной сигнал Z_fÎZ, вызывающий данный переход a_s=d(a_m,z_f). Для графа автомата Мили выходной сигнал w_gÎW, формируемый на переходе, записывается в конце дуги, а для автомата Мура – рядом с вершиной a_m, отмеченной состоянием a_m, в котором он формируется. Если переход в автомате из состояния a_m в состояние a_s производится под действием нескольких входных сигналов, то дуге графа, направленной из a_m в a_s, приписываются все эти входные и соответствующие выходные сигналы. Граф С-автомата содержит выходные сигналы двух типов и они обозначаются на графе как на графах соответствующих автоматов. Графы автоматов, заданных своими таблицами переходов и выходов (табл. 5.1¸5.6) представлены на рисунках 5.5¸5.7.

5.4. Связь между моделями Мура и Мили

Автоматы Мура, Миля и С-автоматы определяют лишь структуру построения автомата. Автоматы, имеющие разную внутреннюю структуру, могут быть эквивалентны. Два автомата с одинаковыми входными и выходными алфавитами называются эквивалентными, если после установки их в начальное состояние их реакции на любое входное слово совпадают.

Для каждого автомата Мили может быть построен эквивалентный ему автомат Мура и наоборот.( аналогично это относится и к С-автоматам)

Переход от автомата Мура к эквивалентному ему автомату Мили тривиален и легко осуществляется при графическом способе задания автомата. Для получения графа автомата Мили необходимо выходной сигнал W_g, записанный рядом с вершиной a_s исходного автомата Мура, перенести на все дуги, входящие в эту вершину.

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

Переход от автомата Мили к эквивалентному ему автомату Мура более сложен. Это связано с тем, что в автомате Мура в каждом состоянии вырабатывается только один выходной сигнал. Переход наиболее наглядно делать при графическом способе задания автомата. В этом случае каждое состояние a_i исходного автомата Мили порождает столько состояний автомата Мура, сколько различных выходных сигналов вырабатывается в исходном автомате при попадании в состояние a_i. Рассмотрим переход от автомата Мили S_a к автомату Мура S_b на примере автомата (рис. 5.6).

Как следует из рис. 5.6, для автомата S_a при попадании в состояние а₁ вырабатываются выходные сигналы W₂, W₄, W₅, при попадании в а₂ – W₁, W₂, a₃ – W₂, a₄ – W₃. Каждой паре „состояние a_i - выходной сигнал W_j”, который вырабатывается при попадании в это состояние, поставим в соответствие состояние b_k эквивалентного автомата Мура S_b с тем же выходным сигналом W_j : b₁=(a₁, W₂), b₂=(a₁, W₄), b₃=(a₁, W₅), b₄=(a₂, W₁), b₅=(a₂, W₂), b₆=(a₃, W₂), b₇=(a₄, W₃), т.е. каждое состояние a_i автомата Мили порождает некоторое множество A_i состояний эквивалентного автомата Мура: A₁={b₁, b₂, b₃}, A₂={b₄, b₅}, A₃={b₆}, A₄={b₇}. Как видно, в эквивалентном автомате Мура количество состояний 7. Для построения графа S_b поступаем следующим образом. Т.к. в автомате S_a есть переход из состояния а₁ в состояние а₂ под действием сигнала z₁ с выдачей W₁, то из множества состояний A₁= {b₁, b₂, b₃}, порождаемых состоянием а₁ автомата S_a в автомате S_b должен быть переход в состояние (a₃, W₂) = b₆ под действием сигнала Z₂ и т.д. Граф эквивалентного автомата Мура представлен на рис. 5.8.

Если от автомата Мура S_b, эквивалентного автомату Мили S_a (рис. 5.8) вновь перейти к автомату Мили, то получим автомат Мили S₁ (рис. 5.9).

Вследствие транзитивности отношения эквивалентности два автомата Мили S₁ и S_a также будут эквивалентными, но у последнего будут на 3 состояния больше. Таким образом, эквивалентные между собой автоматы могут иметь различное число состояний, в связи с чем возникает задача нахождения минимального (т.е. с минимальным числом состояний) автомата в классе эквивалентных между собой автоматов.

5.5. Минимизация числа внутренних состояний полностью определенных автоматов

Рассмотрим метод минимизации полностью определенных автоматов, предложенный Ауфенкампом и Хоном.

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

Для пользования методом введем несколько определений.

Два состояния абстрактного автомата называются 1-эквивалентными в том случае, если реакции автомата в этих состояниях на всевозможные входные слова совпадают.

Объединение всех 1-эквивалентных состояний абстрактного автомата образует 1-класс эквивалентности.

1-эквивалентные состояния автомата называются 2-эквивалентными, если они переводятся любым входным сигналом также в 1-эквивалентные состояния.

Объединение всех 2-эквивалентных состояний образует 2-класс эквивалентности.

По индукции можно распространить определение до i-эквивалентных состояний и i-классов эквивалентности.

Если для некоторого i разбиения состояний автомата на ( i +1) - классы совпадает с разбиением на i-классы, то оно является разбиением и на ¥ - классы эквивалентности.

Разбиение множества внутренних состояний автомата на ¥ - классы и является требуемым разбиением на классы эквивалентности, при этом такое разбиение может быть получено за конечное число шагов.

Все вышеизложенное непосредственно применимо к минимизации автомата Мили. При минимизации полностью определенных автоматов Мура вводится понятие 0-эквивалентности состояний и разбиение множества состояний на 0-эквивалентные классы: к такому классу относятся одинаково отмеченные состояния автомата Мура.

Если два 0-эквивалентных состояния любым входным сигналом переводится в два 0-эквивалентных состояния, то они называются 1-эквивалентными. Все дальнейшие классы эквивалентности состояний для автомата Мура определяются аналогично приведенному для автоматов Мили.

Рассмотрим пример минимизации автомата Мили, заданного таблицами переходов и выходов – таблицы 5.7.

Из таблицы выходов получаем разбиение на 1-классы эквивалентности p₁, объединяя в эквивалентные классы Bi состояния с одинаковыми столбцами: p₁ = {B₁, B₂}; B₂= {a₁, a₂, a₅, a₆}; B₂= {a₃, a₄}. Для получения 2-эквивалентных состояний строим таблицу 1-разбиения (табл.5.8), заменяя в таблице переходов состояния a₁ соответствующими классами эквивалентности B1 или B2.

Из полученной таблицы 1-разбиения получаем 2-классы эквивалентности C_i и разбиение p₂= {C₁, C₂, C₃}, где С₁= {a₁, a₂}, C₂= {a₅, a₆}, C₃= {a₃, a₄}. Сравнивая p₂ и p₁, отмечаем, что эти разбиения отличаются друг от друга. Поэтому аналогично строим таблицу 2-разбиения (табл. 5.9), опять заменяя в таблице переходов состояния a_i соответствующими классами эквивалентности C_i.

Из полученной таблицы 2-разбиения получаем 3-классы эквивалентности D_i и разбиение p₃={ D₁, D₂, D₃}, где D₁= {a₁, a₂}, D₂= {a₅, a₆}, D₃= {a₃, a₄}.

Сравнивая p₃ и p₂, замечаем, что D₁= C₁, D₂= C₂, D₃= C₃, p₃= p₃. Следовательно получили разбиение на ¥- эквивалентные классы. Т.к. всего три таких класса, то минимальный автомат будет содержать всего три состояния. Выбираем из каждого класса D_i по одному состоянию и получаем множество состояний A' минимального автомата. Пусть, например, A'={à₁, à₄, à₅}. Для получения минимального автомата из первоначальных таблиц переходов и выходов (табл. 5.7) вычеркиваем столбцы, соответствующие "лишним состояниям" a₂, a₃, a₆. В результате получается минимальный автомат Мили, эквивалентный исходному автомату (табл. 5.10).

Табл.5.10. Таблицы переходов и выходов минимального автомата

Минимизацией числа внутренних состояний автомата заканчивается этап абстрактного синтеза.

5.6. Принцип микропрограммного управления. Понятия об операционном и управляющем автоматах

ЭВМ перерабатывает информацию, выполняя над ней какие-то операции. Для выполнения операций над информацией используются операционные устройства – процессоры, каналы ввода-вывода, устройства управления внешними устройствами и т.д. Функцией операционного устройства является выполнение заданного множества операций F={f₁,...,f_G} над входными словами D={d₁,...,d_H} c целью вычисления слов R={r₁,...,r_Q}, которые представляют результаты операций R=f_g(D), где g=1,2,...,G.

Функциональная и структурная организация операционных устройств базируется на принципе микропрограммного управления, который состоит в следующем:

1. Любая операция f_g(g=1,...,G), реализуемая устройством, рассматривается как сложное действие, которое разделяется на последовательность элементарных действий над словами информации. Эти элементарные действия называются микрооперациями.

2. Для управления порядком следования микроопераций используются логические условия, которые в зависимости от значений слов, преобразуемых микрооперациями, принимают значения "ложь" или "истина" (1 или 0).

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

4. Микропрограмма используется как форма представления функции устройства, на основе которой определяется структура и порядок функционирования устройства во времени.

Таким образом, из принципа микропрограммного управления следует, что структура и порядок функционирования операционных устройств предопределяется алгоритмом выполнения операции F={f₁,...,f_G}.

К элементарным действиям над словами информации - микрооперациям относятся: передача информации из одного регистра в другой, взятие обратного кода, сдвиг и т.д.

В любом устройстве обработки цифровой информации можно выделить два основных блока – операционный автомат (ОА) и управляющий автомат (УА).

Операционный автомат (ОА) служит для хранения слов информации, выполнения набора микроопераций и вычисления значений логических условий X (рис. 5.10), т.е. операционный автомат является структурой, организованной для выполнения действий над информацией. Микрооперации, выполняемые ОА, задаются множеством управляющих сигналов Y={y₁,...., y_M}, с каждым из которых отождествляется определенная микрооперация.

Рис. 5.10. Структурная операционного устройства с микропрограммным управлением

Значения логических условий, вычисляемые в операционном автомате, отображаются множеством осведомительных сигналов X={x₁,...,x_L}, каждый из которых отождествляется с определенным логическим условием.

Управляющий автомат (УА) генерирует последовательность управляющих сигналов, предписанную микропрограммой и соответствующую значениям логическим условий. Иначе говоря, управляющий автомат задает порядок выполнения действий в ОА, вытекающий из алгоритма выполнения операций. Наименование операции, которую необходимо выполнить в устройстве, определяется кодом g операции, поступающим в УА извне. По отношению к УА сигналы g₁,...,g_h, посредством которых кодируется наименование операции и осведомительные сигналы x₁,...,x_L, формируемые в операционном автомате, играют одинаковую роль: они влияют на порядок выработки управляющих сигналов Y. Поэтому сигналы g₁,...,g_h и x₁,...,x_L относятся к одному классу – к классу осведомительных сигналов, поступающих на вход УА.

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

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

Функция ОА определяется следующей совокупностью сведений:

1)множеством входных слов D={d₁,...,d_H}, вводимых в автомат в качестве операндов;

2)множеством выходных слов R={r₁,...,r_Q}, представляющих результаты операций;

3)множеством внутренних слов S={s₁,...,s_N}, используемых для представления информации в процессе выполнения операций. Можно считать, что входные и выходные слова совпадают с определенными внутренними DÍS, RÍS.

4)множеством микроопераций Y={y_m}, реализующих преобразование S=j_m(s) над словами информации, где j_m – вычисляемая функция;

5)множеством логических условий X={x_i}, где x_i=y_i(s_i) и y_i – булева функция;

T.o. функция ОА задана, если заданы (определены) множества D, R, S, Y, X. Время не является аргументом функции ОА. Функция устанавливает список действий-микроопераций и логических условий, которые может выполнять автомат, но никак не определяет порядок следования этих действий во времени. Т.е. функция ОА характеризует средства, которые могут быть использованы для вычислений, но не сам вычислительный процесс.

Порядок выполнения действий во времени определяется в форме функций управляющего автомата.

Функция управляющего автомата – это операторная схема алгоритма (микропрограммы), функциональными операторами которой являются символы у₁,...,у_m, отождествляемые с микрооперациями, и в качестве логических условий используются булевы переменные х₁,..., х_L. Т.е. совокупность микроопераций, объединенных алгоритмом операции, составляет микропрограмму операции, которая, в свою очередь, является связующим звеном между командой (кодом операции) и операционным устройством (аппаратными средствами), предназначенным для преобразования информации.

Управляющий автомат состоит из отдельных логических схем, вырабатывающих управляющие сигналы в заданной последовательности. Такой автомат можно рассматривать как управляющий автомат Мура или Мили.

Чтобы построить схему управляющего автомата, нужно задать микропрограмму работы операционного устройства. Микропрограмма наиболее часто представляется в виде граф - схемы алгоритма (ГСА). ГСА определяет вычислительный процесс последовательно во времени, устанавливая порядок проверки логических условий х₁÷х_L и порядок следования микроопераций у₁÷у_m.

Операционные элементы

Согласно принципа микропрограммного управления, любая сложная операция распадается на ряд микроопераций, которые выполняются ОА. Различные микрооперации выполняются элементарными ОА - так называемыми операционными элементами (ОЭ), которые являются составными частями основного ОА.

Под операционным элементом понимают устройство, реализующее одну из следующих функций или их произвольную комбинацию:

- хранение слова информации;

- выполнение некоторых микроопераций, в результате которых вычисляется новое значение слова;

- вычисления логического условия, зависящего от слова.

Принято считать, чтофункция ОЭ определена, если заданы:

- описание хранимого или вычисляемого слова;

- описание множества микроопераций, выполняемых этим элементом;

- описание вычисляемых этим элементом логических условий.

Для построения ОА ОЭ соединяются между собой с помощью цепей передачи слов информации от выходов одних элементов к входам других.

В зависимости от выполняемых микроопераций ОЭ делятся на разновидности: шина, регистр, счетчик, сумматор, схема сравнения, дешифратор, шифратор и т.д.

5.7. Граф - схемы алгоритмов (ГСА) и их разновидности. Способы задания ГСА, требования к ним

Алгоритм. Существует несколько определений этого понятия. Мы будет придерживаться следующего: алгоритм – определенная последовательность действий, позволяющая за конечное число шагов получить желаемый результат.

Граф-схема алгоритма (ГСА). ГСА позволяет описать последовательность выполнения шагов алгоритма в общем виде в виде графической нотации, не вдаваясь в детали реализации этого алгоритма. Т.о. граф-схема алгоритма есть форма представления микропрограммы, которую должно выполнить операционное устройство (ОУ). При построении операционного устройства, как состоящего из операционного (ОА) и управляющего (УА) автоматов, необходимо уметь выделить функции ОА и УА из ГСА. Обычно микропрограмма представляется в виде содержательной ГСА. В этом случае для задания функций ОА необходимо перечислить все выполняемые микрооперации и все проверяемые логические условия данной микропрограммы, а также описать разрядность слов, обрабатываемых операционным устройством. Для инициализации выполнения той или иной микрооперации на ОА должны поступать в нужный согласно ГСА момент времени управляющие сигналы Yi. Обычно при проектировании ОУ принимают определенный способ кодирования микроопераций (чаще всего кодом, содержащим столько разрядов, сколько всего различных микроопераций) и для разработки ОА считают, что УА выдает код микроопераций, которые должны выполниться в данный момент времени.

Для УА важна последовательность выдачи соответствующих кодов микроопераций в зависимости от логических условий, вырабатываемых ОА и

анализируемых УА в нужные моменты времени. Если принят способ кодирования микроопераций, то функции УА задаются кодированной ГСА. Поэтому для различных содержательных ГСА, имеющих одинаковую кодированную ГСА, ОА будут различны, но УА будет одним и тем же.

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

– вершина «начало» имеет один выход, входов не имеет. Обозначает начало микропрограммы.

– вершина «конец» имеет любое число входов, выходов не имеет. Обозначает конец микропрограммы.

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

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

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

Граф микропрограммы состоит из совокупности перечисленных вершин и дуг, соединяющих выходы одних вершин с входами других. Соединение вершин и направление дуг графа определяют исходя из алгоритма операции, описываемого графом, и структуры операционного автомата.

Сама микропрограмма и ее граф должны быть корректны, т.е. отвечать следующим условиям:

1. в графе должна быть только одна начальная и одна конечная вершина;

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

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

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

Пример ГСА представлен на рисунках 5.11 и 5.12.

ГСА, представленная на рис. 5.11, называется содержательной, т.к. внутри вершин записаны в явном виде микрооперации и логические условия. Если же каждую микрооперацию обозначить символами Yi, a логические условия через Xi, то получится так называемая кодированная ГСА (рис. 5.12). Для правильного восприятия микропрограммы, заданной в виде кодированной ГСА, необходимо знать соответствия между Yi, Xi и содержанием соответствующих микроопераций и логических условий.

Между граф - схемой операционного устройства и графом переходов, управляющим функционированием этого операционного устройства, существует строгая взаимосвязь. На рис. 5.13.а представлена ГСА некоторого операционного устройства, микропрограмма которого выполняется при начальном условии Н=1. Условия, указанные в данной ГСА, определяют последовательность выполнения микроопераций. Посмотрим, как связать граф-схему микропрограммы с автоматом Мура или Мили.

Для автомата Мура выходной сигнал зависит только от его внутреннего состояния, т.е. в нашем случае V = F(Q). Поэтому каждая операторная вершина ГСА должна быть отмечена символом исходного состояния автомата q_i. На рис. 5.13.а слева от операторов дана отметка ГСА, интерпретируемая как автомат Мура. По этим отметкам выполняется построение графа переходов автомата Мура (рис. 5.13.б), где вершинами являются состояния автомата, а дугами – условия переходов из одного состояния в другое. Таким образом, функции выходов автомата Мура , где q_i – состояние автомата, обеспечивающее выработку сигнала v_i.

Рис. 5.13. ГСА операционного устройства (а) и графы переходов автомата Мура (б) и Мили (в)

Переход автомата из одного состояния в другое при отсутствии логических условий (безусловный переход) происходит под действием синхросигнала. Условный переход происходит в том направлении, которое соответствует вычисленному значению условия z_i.

Для построения автомата Мили следует помнить, что выходной сигнал зависит как от внутреннего состояния, так и от входного сигнала.

Разметка ГСА автомата Мили делается иначе, чем для автомата Мура. Символом q₀ отмечают вход первой вершины графа, следующей за начальной, и вход конечной вершины ГСА. Выходы других операторных вершин обозначаются символом q_i. На рис. 5.13.а состояния автомата Мили отмечены символами q₀÷ q₄, взятыми в скобки. Граф переходов автомата Мили показан на рис. 5.13.в. В автоматах Мили функции выходов, по которым вырабатываются сигналы микроопераций, определяются по формуле , где q_i - состояние автомата, сопровождающееся выработкой сигнала v_j, z_k - логическое условие, определяющее выработку сигнала при переходе автомата из состояния q_i.

В случае безусловного перехода автомата из состояния q_i сигнал v_j определяется только значением q_i.

5.8. Абстрактный синтез микропрограммных управляющих автоматов Мили и Мура

В дальнейшем будем рассматривать синтез только УА и только кодированной ГСА.

Конечный автомат, интерпретирующий микропрограмму работы дискретного устройства, называется микропрограммным автоматом. Одну и ту же ГСА можно интерпретировать как автоматом Мили, так и автоматом Мура.

Абстрактный синтез микропрограммного автомата по ГСА осуществляется в два этапа:

1. Получение отмеченной ГСА;

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

5.8.1. Синтез автомата Мили

На этапе получения отмеченной ГСА входы вершин, следующих за операторными, отмечают символами a₁, a₂,.. по следующим правилам:

- символом а₁ отмечают вход вершины, следующей за начальной, а также вход конечной вершины;

- входы всех вершин следующих за операторными, должны быть отмечены;

- входы различных вершин, за исключением конечной, отмечаются различными символами;

- если вход вершины отмечается, то только одним символом.

Ясно, что для проведения отметок потребуется конечное число символов а₁,...,a_m. Результатом первого этапа является отмеченная ГСА, которая служит основой для второго этапа - перехода к графу или таблицам переходов-выходов. Пример ГСА, отмеченной для автомата Мили, представлен на рис. 5.14.

На втором этапе, из отмеченной ГСА, строят граф автомата или таблицы переходов-выходов. Для этого полагают, что в автомате будет столько состояний сколько символов a_i понадобилось при отметке ГСА.

На плоскости рисунка отмечаем все состояния автомата a_i. Для каждого из состояний a_i определяем по отмеченной ГСА все пути, ведущие в другие состояния и проходящие обязательно только через одну операторную вершину. Например, из состояния а₁ (рис.5.14.) есть переход в состояние a₂ (путь проходит через операторную вершину y₁ y₂) и в состояние a₄ (путь проходит через вершину y₃ y₄). Перехода из a₁ в a₃ нет, так как на этом пути нет ни одной операторной вершины. Будем считать, что автомат осуществляет переход, например, из a₁ в a₂ при условии x₁=0 и вырабатывает на этом переходе выходные сигналы у₁ у₂ (то, что записано в проходимой операторной вершине ГСА, рис. 5.14). Значение условий х₂, х₃, х₄ на этом переходе не оказывает влияния на автомат.

Исключение составляет только путь, ведущий в конечную вершину, он может не содержать ни одной операторной вершины (например, переход из а₆в а₁), т.е. не сопровождается выработкой выходных сигналов.

Отмечаем на графе все указанные пути для всех состояний в виде дуг, которым приписываем условия перехода и выходной сигнал, вырабатываемый на этом переходе. Получим граф автомата Мили (рис. 5.15).

На этом графе переходам типа а₃®a₄, a₅®a₁ приписывается условие перехода 1, т.к. эти переходы являются безусловными и выполняются всегда, когда автомат попадает в состояние а₃ или а₅. На основании отмеченной ГСА или графа автомата можно построить таблицу переходов-выходов. Для микропрограммных автоматов таблица переходов-выходов строится в виде списка и различаются прямая и обратная таблицы. Для данного автомата прямая таблица представлена в табл. 5.11, обратная – в табл. 5.12.

В приведенных таблицах a_m - исходное состояние, a_s - состояние перехода, Х - условие (входной сигнал), обеспечивающий переход из состояния a_m в состояние a_s, Y - выходной сигнал, вырабатываемый автоматом при переходе из a_m в a_s.

Отличие прямой таблицы переходов-выходов от обратной состоит в том, что в прямой таблице записи сгруппированы по состояниям a_m, а в обратной – по состояниям a_s.

5.8.2. Синтез автомата Мура

Для автомата Мура на этапе получения отмеченной ГСА разметка производится согласно следующим правилам:

Ø символом а₁ отмечается начальная и конечная вершины;

Ø различные операторные вершины отмечаются различными символами;

Ø все операторные вершины должны быть отмечены.

Пример ГСА, отмеченной для автомата Мура, представлен на рис. 5.16.

Граф автомата Мура, соответствующий отмеченной ГСА (рис. 5.16), представлен на рис. 5.17. Построение его аналогично построению графа для автомата Мили.

Таблицы переходов-выходов автомата Мура представлены в табл. 5.13 (прямая) и табл. 5.14 (обратная). Обычно для автомата Мура в таблице переходов-выходов дополнительный столбец для выходных сигналов не используется, и выходной сигнал записывается в столбце, где указывается исходное состояние a_m или состояния перехода a_s.

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

5.9. Структурный синтез микропрограммных управляющих автоматов Мили и Мура

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

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

Рассмотрим этапы структурного синтеза на конкретных примерах.

5.9.1. Структурный синтез автомата Мили

Выполним структурный синтез микропрограммного автомата Мили, заданного своей таблицей переходов-выходов (табл. 5.11 или табл. 5.12). В качестве примера синтез будем выполнять по прямой таблице (табл. 5.11).

1. В исходном автомате количество состояний М=6, следовательно, число элементов памяти m = ] log ₂ M [ = ] log ₂ 6 [ = 3. Пусть для синтеза используются JK триггеры.

2. Кодируем внутренние состояния автомата, используя для этого карту Карно (рис. 5.18) и, по возможности, метод соседнего кодирования.

3. Строим прямую структурную таблицу переходов-выходов автомата Мили (табл. 5.15). В данной таблице в столбцах K(a_m) и K(a_s) указывается код исходного состояния и состояния перехода соответственно. В столбце ФВ (функций возбуждения) указывается те значения функций возбуждения, которые на данном переходе обязательно равны 1. Остальные (т.е. равные 0 или принимающие неопределенные значения) не указываются. Это эквивалентно тому, что всем неопределенным значениям функций возбуждения приписывается значение 0, что в общем случае не дает минимальной функции, однако в реальных автоматах минимизация обычно не делается в виду ее неэффективности.

Табл. 5.15. Структурная таблица переходов-выходов автомата Мили

a_m	K(a_m)	a_s	K(a_s)	X	Y	ФВ
						J₂
						J₃
						-
						J₁
						J₃
				1		K₁
						K₃
						J₁
				1		K₁K₂
					-	K₂K₃
						K₃

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

5. Для получения функций выходов поступаем аналогично:

6. Для построения функциональной схемы автомата по полученным выражениям необходимо либо заменить a_i его значениями через Q₁Q₂Q₃ либо получить сигнал, соответствующий a_i. Обычно используют второй способ и для получения сигнала a_i применяют так называемый дешифратор состояний, на вход которого поступают сигналы с выходов элементов памяти Q₁Q₂Q₃. Кроме того, при построении схемы стараются выделить общие части, встречающиеся в функциях возбуждения или выходных сигналах. В этом случае окончательная система уравнений, по которым строится схема, будет иметь вид:

Функциональная схема автомата, построенная на основании полученных уравнений, представлена на рис. 5.19.

5.9.2. Структурный синтез автомата Мура

Выполним структурный синтез микропрограммного автомата Мура, заданного своей таблицей переходов-выходов (табл. 5.13 или табл. 5.14). В качестве примера синтез будем выполнять по обратной таблице (табл. 5.14).