Операционные элементы - Тема 5. Схемотехника цифровых узлов, Цифровые автоматы

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

...

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

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.

Рис. 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.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) и, по возможности, метод соседнего кодирования.

Рис. 5.18. Карта Карно для кодирования состояний автомата (а) и результат кодирования состояний (б)

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

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

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).

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

2. Кодируем внутренние состояния автомата, используя алгоритм кодирования для D-триггеров ( чем больше переходов в это состояние, тем меньше единиц должно быть в коде этого состояния). Количество переходов в данное состояние легко определяется из обратной таблицы: a₁ ~ 2, a₂ ~ 3, a₃ ~ 2, a₄ ~ 1, a₅ ~ 1, a₆ ~ 1, a₇ ~ 2. Поэтому коды состояний следующие:

a₂ - 000, a₁ - 001, a₃ - 010, a₇ - 100, a₄ - 011, a₅ - 101, a₆ - 110.

3. Строим структурную таблицу переходов - выходов автомата Мура. Построение таблицы выполняется аналогично автомату Мили. Результат представлен в табл. 5.16.

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

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

или, если принять, что

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

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

5.10. Синтез автомата Мура на базе регистра сдвига

Кроме рассмотренного ранее канонического метода, существуют и другие методы синтеза управляющих автоматов, среди которых наиболее широко используется синтез на базе регистра сдвига. Этот метод позволяет при построении схемы отказаться от дешифратора, т.к. состояния кодируются унитарным кодом. В автомате количество элементов памяти выбирается равным количеству внутренних состояний. В каждый момент времени только один триггер находится в 1, остальные в 0. Обычно при синтезе на базе регистра сдвига используются D-триггеры. Очень эффективен данный метод для так называемых линейных микропрограмм, т.е. микропрограмм без ветвлений (отсутствует логические условия). Рассмотрим пример синтеза управляющего автомата Мура данным методом. Пусть закодированная ГСА микропрограммы имеет вид рис. 5.21.

продолжение следует...

Продолжение:

Часть 1 Тема 5. Схемотехника цифровых узлов, Цифровые автоматы и их разновидности
Часть 2 Операционные элементы - Тема 5. Схемотехника цифровых узлов, Цифровые автоматы
Часть 3 Вау!! 😲 Ты еще не читал? Это зря! - Тема 5. Схемотехника цифровых узлов, Цифровые автоматы

См.также

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