Меню

Счетчики с управляемым сбросом

7. Счетчики с произвольным модулем счета и управляемым сбросом

Все рассмотренные ранее счетчики имеют «жесткую» структуру, при которой изменение модуля счета Кcч связано с коммутационными изменениями всей схемы. Однако можно построить счетчики, в которых изменение модуля счета осуществляется более простым способом, практически не вносящим изменений в основную схему счетчика. Этого можно достигнуть, если осуществить управляемый сброс счетчика в нулевое состояние. Например, если имеется четырехразрядный двоичный счетчик с Ксч=16, то для его преобразования в счетчик с модулем счета Ксч=13 необходимо, чтобы после состояния 12 следующий входной импульс сбрасывал его в 0, возвращая к началу цикла счета. Если счетчик выполнен на JK-триггерах, то для сброса в 0 должен вырабатываться сигнал R, под действием которого на входах всех триггеров устанавливалась бы комбинация сигналов J=0, К=1. Следовательно, схемы управления на входах триггеров двоичного счетчика с параллельным переносом, формирующие сигналы

где: i = 1,2. ,n-1; n — число разрядов счетчика, должны быть преобразованы в схемы управления, формирующие сигналы

.

Согласно этим выражениям схема i-го разряда счетчика будет иметь вид, показанный на рис. 12.11. Сигнал R сброса счетчика в 0 вырабатывается дополнительным конъюнктором при установке на его входах двоичного кода, равного значению Ксч -1. Это достигается подключением входов дополнительного конъюнктора к прямым выходам триггеров соответствующих разрядов.

Вкачестве примера, иллюстрирующего рассмотренный способ, на рис. 12.12 показана схема параллельного суммирующего счетчика с модулем счета Ксч=6.

При достижении счетчиком состояния 5 (Q2=1, Q1=0, Q=1) на выходе конъюнктора ИЗ образуется сигнал R=1, который устанавливает на входах каждого триггера комбинацию сигналов J=0, К=1. Под действием этих комбинаций очередной импульс, поступивший на вход С, осуществляет установку всех триггеров счетчика в нулевое состояние.

Схема счетчика с произвольным модулем счета может быть значительно упрощена, если в нем использовать триггеры с установочными входами. Примером может служить схема счетчика с модулем счета Кcч=11, выполненного на основе суммирующего 4-разрядного счетчика с параллельным переносом на двухступенчатых JK-триггерах с установочными входами (Рис. 12.13). На входыпостоянно заведены уровни логической 1, а на входыR поступает сигнал с выхода дополнительного конъюнктора. При счете от 0 до 10 конъюнктор закрыт и сигнал с его выхода R=1 не оказывает влияния на работу счетчика. При поступлении очередного импульса на входы С триггеров счетчик устанавливается в состояние 11 (Q3Q2Q1Q=1011). При этом на выходе конъюнктора образуется сигнал , который сбрасывает триггеры всех разрядов в нулевое состояние и одновременно служит сигналом переноса.

Достоинством счетчиков с управляемым сбросом является естественная двоичная последовательность кодов.

8. Генераторы чисел на основе счетчиков

Такие последовательностные устройства называют также кольцевыми распределителями сигналов. Последовательность двоичных чисел, образуемая на их выходах, часто используется в цифровых системах как последовательность сигналов. управляющих работой других узлов. Число состояний, которое может принимать генератор, называется длиной последовательности чисел L. С этой точки зрения любой счетчик можно рассматривать как генератор определенной последовательности чисел, у которого L = Ксч. Например, счетчик с модулем счета Ксч=8 (рис. 12.12) является генератором последовательности чисел 0-1 -2-3-4-5-6-7.

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

В качестве примера рассмотрим генератор чисел 5-3-11-7. Так как L=4, то в качестве основы генератора используется 2-разрядный суммирующий счетчик с модулем счета Ксч=4. К выходам Q1 и Q подключим комбинационную схему, преобразующую состояния счетчика 0-1-2-3 в последовательность чисел 5-3-11-7. Поскольку наибольшее число последовательности 11 представляется четырехразрядным двоичным кодом, то комбинационная схема должна содержать четыре выхода А,В,С,D. Считая выход А младшим разрядом, а выход D старшим, составим таблицу истинности комбинационной схемы (табл. 12.4), на основании которой, используя известные методы минимизации булевых функций, получим уравнения выходов:

.

Источник

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

Дата добавления: 2013-12-24 ; просмотров: 8392 ; Нарушение авторских прав

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

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

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

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

Конъюнктор, входящий в состав схемы, тоже вырабатывает сигнал сброса, но при достижении содержимым счетчика значения М-1. В случае построения четырехразрядного двоично-десятичного счетчика на входы конъюнктора QQ1Q2Q3 необходимо, соответственно подключить выходы счетчика , что приведет к сбросу всех разрядов счетчика по пришествию сигнала счета, последующего после достижения счетчиком числа 10012=910, т.е. счетчик действительно работает как двоично-десятичный.

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. Диаграмма состояний РТ с автоматическим вхождением в рабочий цикл за один такт

Q1 Q2 Q3 Q1H Q2H Q3H Q1 Q2 Q3 Q1H Q2H Q3H

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

, и .

Схема распределителя тактов с автоматическим вхождением в рабочий цикл за один такт представлена на рис. 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).

Номер состояния Q1 Q2 Q3 Q4 Номер состояния Q1 Q2 Q3 Q4

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

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

, , , ,

, , и ,

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

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

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

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

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

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

Читайте также:  Электросчетчик сэб 2а 07 212 микрон

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

.

Распределители тактов на основе счетчика Джонсона характеризуются небольшими аппаратурными затратами (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): память (ЭП) и комбинационную цепь (КЦ). На входы КЦ подаются входные сигналы Zt и сигналы состояния At цифрового автомата. На ее выходе вырабатываются выходные сигналы Wt и сигналы перевода ЦА в новое состояние At+1.

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

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

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

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

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

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

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

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

1. A=1, a2, . ,am> — множество состояний (внутренний алфавит),

2. Z=1, z2, . ,zf> — множество входных сигналов (входной алфавит),

3. W=1, w2, . wg> — множество выходных сигналов (выходной алфавит),

4. d : A·Z®A — функция переходов, реализующая отображение Dd ÍА·Z в А. Иными словами функция d некоторым парам “состояние — входной сигнал” (аm, zf) ставит в соответствие состояния автомата аs= d (am, zf), asÎA,

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

6. ai Î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.

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

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

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

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

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

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

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

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

Выходной сигнал Uh=l2(am) выдается все время, пока автомат находится в состоянии am. Выходной сигнал Wg=l1(am, zf) выдается во время действия входного сигнала Zf при нахождении автомата в состоянии am.

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

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

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

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

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

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

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

Абстрактный автомат называется конечным, если конечны множества А = 1, a2, . am>, Z = 1, z2, . zf>, W = 1, w2, . wg>. Автомат носит название инициального, если в нем выделено начальное состояние a1.

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

В отличие от абстрактного автомата, имеющего один вход и один выход (рис. 5.3.а), на которые поступают сигналы во входном и выходят в выходном W=1. WG> алфавитах, структурный автомат (рис. 5.3.б) имеет L входных каналов х12. хL и N выходных y1,y2,…,yN на каждом из которых присутствует сигнал структурного алфавита.

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

Обычно в качестве структурного используется двоичный алфавит. В этом случае каждому входному сигналу ZF абстрактного автомата соответствует некоторый двоичный вектор (lf1,lf2. lfL), где lfLÎ<0,1>.

Очевидно, что для представления (кодирования) входных сигналов Z1. ZF абстрактного автомата различными двоичными векторами должно быть выполнено условие L ] log2F [, аналогично N ] log2G [. Например, Z=1,Z2,Z3,Z4> и W=1,W2,W3>, тогда L log24=2 и N log23=2

Следовательно, структурный автомат с двумя входами x1 и x2 и двумя выходами y1 и y2 может быть представлен в виде, представленном на рис.5.4:

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

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

Для того, чтобы задать автомат, необходимо описать все компоненты кортежа S=(A, Z, W, d, l, а1 ). Множества А, 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. На пересечении столбца am и строки zf в табл. 5.1 записывается состояние as, в которое должен перейти автомат из состояния am под действием входного сигнала Zf, т.е. as=d(am, zf). На пересечении столбца am и строки zf в табл. 5.2 записывается выходной сигнал Wg, выдаваемый автоматом в состоянии am при поступ­лении на вход сигнала zf, т.е. Wg = l(am, zf).

Читайте также:  Тэк ввод показания счетчиков

Для приведенных таблиц множества, образующие автомат A=1, a2, a3,a4>, Z=1, z2>, W=1, w2, w3, w4, w5>. Автомат Мили может быть задан одной совмещенной таблицей переходов и выходов (табл. 5.3), в которой каждый элемент as / wg записанный на пересечении столбца am и строки zf, определяется следующим образом: as=d(am, zf); wf=l(am, zf).

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

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

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

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

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

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

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

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

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

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

Как следует из рис. 5.6, для автомата Sa при попадании в состояние а1 вырабатываются выходные сигналы W2, W4, W5, при попадании в а2 – W1, W2, a3 – W2, a4 – W3. Каждой паре „состояние ai — выходной сигнал Wj”, который вырабатывается при попадании в это состояние, поставим в соответствие состояние bk эквивалентного автомата Мура Sb с тем же выходным сигналом Wj : b1 =(a1, W2), b2 =(a1, W4), b3 =(a1, W5), b4 =(a2, W1), b5 =(a2, W2), b6 =(a3, W2), b7 =(a4, W3), т.е. каждое состояние ai автомата Мили порождает некоторое множество Ai состояний эквивалентного автомата Мура: A1=1, b­2, b3>, A2=4, b5>, A3=6>, A4=7>. Как видно, в эквивалентном автомате Мура количество состояний 7. Для построения графа Sb поступаем следующим образом. Т.к. в автомате Sa есть переход из состояния а1 в состояние а2 под действием сигнала z1 с выдачей W1, то из множества состояний A1 = 1, b2, b3>, порождаемых состоянием а1 автомата Sa в автомате Sb должен быть переход в состояние (a3, W2) = b6 под действием сигнала Z2 и т.д. Граф эквивалентного автомата Мура представлен на рис. 5.8.

Если от автомата Мура Sb, эквивалентного автомату Мили Sa (рис. 5.8) вновь перейти к автомату Мили, то получим автомат Мили S1 (рис. 5.9).

Вследствие транзитивности отношения эквивалентности два автомата Мили S1 и Sa также будут эквивалентными, но у последнего будут на 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-классы эквивалентности p1, объединяя в эквивалентные классы Bi состояния с одинаковыми столбцами: p1 = 1, B2>; B2 = 1, a2, a5, a6>; B2 = 3, a4>. Для получения 2-эквивалентных состояний строим таблицу 1-разбиения (табл.5.8), заменяя в таблице переходов состояния a1 соответствующими классами эквивалентности B1 или B2.

Из полученной таблицы 1-разбиения получаем 2-классы эквивалентности Ci и разбиение p2 = 1, C2, C3>, где С1 = 1, a2>, C2 = 5, a6>, C3 = 3, a4>. Сравнивая p2 и p1, отмечаем, что эти разбиения отличаются друг от друга. Поэтому аналогично строим таблицу 2-разбиения (табл. 5.9), опять заменяя в таблице переходов состояния ai соответствующими классами эквивалентности Ci.

Сравнивая p3 и p2, замечаем, что D1 = C1, D2 = C2, D3 = C3, p3 = p3. Следовательно получили разбиение на ¥- эквивалентные классы. Т.к. всего три таких класса, то минимальный автомат будет содержать всего три состояния. Выбираем из каждого класса Di по одному состоянию и получаем множество состояний A’ минимального автомата. Пусть, например, A’=<à1, à4, à5>. Для получения минимального автомата из первоначальных таблиц переходов и выходов (табл. 5.7) вычеркиваем столбцы, соответствующие «лишним состояниям» a2, a3, a6. В результате получается минимальный автомат Мили, эквивалентный исходному автомату (табл. 5.10).

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

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

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

ЭВМ перерабатывает информацию, выполняя над ней какие-то операции. Для выполнения операций над информацией используются операционные устройства – процессоры, каналы ввода-вывода, устройства управления внешними устройствами и т.д. Функцией операционного устройства является выполнение заданного множества операций F=<f1. fG> над входными словами D=<d1. dH> c целью вычисления слов R=<r1. rQ>, которые представляют результаты операций R=fg(D), где g=1,2. G.

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

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

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

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

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

Таким образом, из принципа микропрограммного управления следует, что структура и порядок функционирования операционных устройств предопределяется алгоритмом выполнения операции F=<f1. fG>.

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

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

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

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

Значения логических условий, вычисляемые в операционном автомате, отображаются множеством осведомительных сигналов X=<x1. xL>, каждый из которых отождествляется с определенным логическим условием.

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

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

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

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

1)множеством входных слов D=<d1. dH>, вводимых в автомат в качестве операндов;

2)множеством выходных слов R=<r1. rQ>, представляющих результаты операций;

3)множеством внутренних слов S=<s1. sN>, используемых для представления информации в процессе выполнения операций. Можно считать, что входные и выходные слова совпадают с определенными внутренними DÍS, RÍS.

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

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

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

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

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

Чтобы построить схему управляющего автомата, нужно задать микропрограмму работы операционного устройства. Микропрограмма наиболее часто представляется в виде граф — схемы алгоритма (ГСА). ГСА определяет вычислительный процесс последовательно во времени, устанавливая порядок проверки логических условий х1÷хL и порядок следования микроопераций у1÷у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). Поэтому каждая операторная вершина ГСА должна быть отмечена символом исходного состояния автомата qi. На рис. 5.13.а слева от операторов дана отметка ГСА, интерпретируемая как автомат Мура. По этим отметкам выполняется построение графа переходов автомата Мура (рис. 5.13.б), где вершинами являются состояния автомата, а дугами – условия переходов из одного состояния в другое. Таким образом, функции выходов автомата Мура , где qi – состояние автомата, обеспечивающее выработку сигнала vi.

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

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

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

Разметка ГСА автомата Мили делается иначе, чем для автомата Мура. Символом q отмечают вход первой вершины графа, следующей за начальной, и вход конечной вершины ГСА. Выходы других операторных вершин обозначаются символом qi. На рис. 5.13.а состояния автомата Мили отмечены символами q ÷ q4, взятыми в скобки. Граф переходов автомата Мили показан на рис. 5.13.в. В автоматах Мили функции выходов, по которым вырабатываются сигналы микроопераций, определяются по формуле , где qi — состояние автомата, сопровождающееся выработкой сигнала vj, zk — логическое условие, определяющее выработку сигнала при переходе автомата из состояния qi.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

На плоскости рисунка отмечаем все состояния автомата ai. Для каждого из состояний ai определяем по отмеченной ГСА все пути, ведущие в другие состояния и проходящие обязательно только через одну операторную вершину. Например, из состояния а1 (рис.5.14.) есть переход в состояние a2 (путь проходит через операторную вершину y1 y2) и в состояние a4 (путь проходит через вершину y3 y4). Перехода из a1 в a3 нет, так как на этом пути нет ни одной операторной вершины. Будем считать, что автомат осуществляет переход, например, из a1 в a2 при условии x1=0 и вырабатывает на этом переходе выходные сигналы у1 у2 (то, что записано в проходимой операторной вершине ГСА, рис. 5.14). Значение условий х2, х3, х4 на этом переходе не оказывает влияния на автомат.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

am K(am) as K(as) X Y ФВ
J2
J3
J1
J3
1 K1
K3
J1
1 K1K2
K2K3
K3

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

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

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

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

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

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

Источник



Двоично-кодированные счетчики с произвольным модулем счета

Нередко на практике необходимо создавать счетчики с модулями, не равным целой степени числа 2 — счетчи­ки с произвольным модулем. Из них наиболее часто встре­чаются двоично-десятичные счетчики, поскольку десятич­ная система счисления является общепринятой.

Для построения счетчика с произвольным модулем М число log2M округляют до ближайшего большего целого числа

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

Наибольшее распространение при построении таких счетчиков получили:

· метод исключения лишних состояний;

· метод управляемого сброса.

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

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

Четырехразрядный двоичный счетчик имеет дополни­тельно четырехвходовый элемент 4И-НЕ, на входы кото­рого подаются сигналы с выходов триггера Q4 3Q2 1 При появлении на синхронизирующем входе С одиннадцатого по счету импульса триггера счетчика устанавливаются в состояние 1010

Q4 3Q2 1= 1111. (3.34)

Тогда элемент 4И-НЕ через время, равное задержке распространения сигнала формирует на своем выходе ну­левой сигнал сброса, который, поступая на асинхронные входы R всех триггеров, принудительно устанавливает их в нулевое состояние. Далее начинается новый цикл счета.

Временные диаграммы, иллюстрирующие работу де­сятичного счетчика, представлены на рис. 3.47.

В методе управляемого сброса на короткое время, обус­ловленное задержкой t3ad в элементах тракта 4И-НЕ и сраба­тыванием триггеров по входу обнуления R, в счетчике уста­навливается лишнее выходное состояние 1010 (рис. 3.47). Если такое явление даже кратковременное является недопу­стимым, то проектируют счетчик по методу исключения лишних состояний.

Решение задачи управляемого сброса можно упростить. Например, при формировании двоично-десятичного счет­чика обратим внимание, что единичные выходы берут с двух разрядов — второго и четвертого. Тогда можно использовать двухвходовый элемент 2И-НЕ, подавая на его входы сигналы Q4 Q2, а инверсные выходы с первого и третьего счетчиков 1 3 не использовать.

По такому принципу строится десятичный счетчик на микросхеме К555ИЕ5, имеющий два входа асинхронного сброса (рис. 3.48, а), объединенных операцией И-НЕ. Для выполнения десятичного счета достаточно входы RO (1), RO (2) соединить с выходами Q4 Q2.

Ввиду особой важности десятичных счетчиков в стан­дартных сериях микросхем имеются десятичные счетчи­ки. Например, микросхема К555ИЕ9 (рис. 3.48, б) — четырехразрядный двоично-десятичный счетчик с асинхронным сбросом, дешифрирующим счетным выходом, с возможностью синхронной установки с произвольное со­стояние от нуля до девяти. Счетчик имеет вход синхро­низации С, вход установки нуля R, четыре информаци­онных входа D1-D4, входы разрешения счета VI, разре­шения предварительной записи V2, разрешения перено­са Р1, четыре выхода Q1-Q4 и выход переноса информа­ции Р2.

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

Аналогичным образом могут быть построены счетчи­ки на любое другое значение модуля счета. Например, для построения счетчика по модулю 5 согласно (3.31) необхо­димо три триггера 3>log25. На рис. 3.49 показан пример счетчика по модулю 5.

На входы элемента 3И-НЕ подаются сигналы Q3Q2Q1 в соответствии с 510 = 1012. Далее по приходу пятого им­пульса на выходе элемента ЗИ-НЕ формируется нулевой уровень, который обнуляет счетчик, поступая на входы асинхронного сброса R всех триггеров. Отметим, что среди других счетчиков с недвоичным ко­дированием практическое значение имеют счетчики с кодом Грея, счетчики Джонсона, счетчики с кодом «1 из N».

Источник