5. Цифровые автоматы, их виды и классификация.
Цифровыми (конечными) автоматами называются устройства, предназначенные для обработки информации, заданной цифровыми кодами. Информация, поступающая в цифр. устройство представляет собой набор дискретных сигналов, отображающих некоторую последовательность 0 и 1, т.е. двоичный код.
В общем случае, на вход цифр. устройства поступает некоторый набор 2ых переменных Х(х1, х2… хn), а с выхода устройства снимается набор или множество значений У(у1,у2… уn), причем цифр. устройства реализуют определенную связь (лог. функцию) между вх. и вых. переменными.
На передачу сигнала через устройство отводится конечн. промежуток времени – такт работы устройства.
Если за 1 такт в устройство передается 1 из разрядов 2ого числа (кода), устройство работает в посл. коде, если за 1 такт его работы передается все двоичное число одновременно, то устройство работает в парал. коде:
П
рименительно к ЭВМ в зависимости от способа обработки циф информации различают 2 класса дискретных автоматов: комбинационные и последовательные.
Комбинационные автоматы (комбинационные схемы) – устройства, в которых значения вых сигналов У(у1, у2… уm) в любой момент дискр. времени однозначно определяется совокупностью вх сигналов Х. Т.о. одним из достоинств комб. схем является их высокое быстродействие. Преобразование информации в комб. схемах однозначно определяется лог. функциями вида 
. Лог функции и соответствующие им комбинационные схемы разделяют на регулярные и нерегулярные структуры. Регулярные структуры предполагают построение схема таким образом, что кажд из ее выходов строится по аналогии с предыдущими. В нерегулируемых структурах такая аналогия отсутствует.
Многие регулярные структуры положены в основу построения ряда интегральных схем малой и средней степени интеграции, а также отдельных частей БИС и СБИС. Из регулярных комбинац. схем наиболее распространены шифраторы, дешифраторы, схемы сравнения, комбинационные сумматоры, коммутаторы (мультиплексоры и демультплексоры), выполненные на основе лог. элементов и несодержащих обратных связей.
В последовательном автомате выходные сигналы в данный момент времени зависят не только от значения входного сигнала в данный момент, но и от значения входного сигнала в прошлом, т.е. внутреннее состояние устройства. Понятеие состояния последов. автомата предполагает наличие у него внутренней памяти, где должна хранится информация о предыдущих воздействиях. Функциональное соотношение: 
Различают последовательные автоматы автоматы Мура(выходной сигнал определяется текущим состоянием автомата) и автоматы Мили (выход зависит как от состояния, так и от входного сигнала)
пример Автоматы Мура: триггеры, счетсчики, накапливающие сумматоры, регистры и др.
Шифраторы (кодеры, ш.) – преобразуют сигнал на одном из своих входов (унитарный код) в n-разрядный 2ный код на выходе, соответствующий 10чному номеру активного входа.
Число информационных входов ш. = числу символов преобразуемого кода и должно соответствовать условию 
, где n – число информационных выходов.
Кроме обычных шифраторов, существуют шифраторы с приоритетом, в таких ш. допускается подавать сигнал 1 одновременно на несколько входов, а ш. выдаст на выход код числа, соответствующего № старшего входа, т.е. если при работе ЭВМ решается задача определения приоритетного претендента на обслуживание и имеется одновременно несколько запросов, то обслужится запрос с наибольшим номером. Основное назначение ш. является преобразование № источника сигнала в 2чный код. 
Дешифраторы (д.)
Д. представляет собой комбинационное устройство, позволяющее распознавать числа, представленные позиционно n-разрядным кодом.
Если на вход д. подать n-размерный 2ый код, то на выходе устройства появляется код «1 из N» в кодовой комбинации которого только одна позиция будет представлена единицей, а остальные – нулем. Такой код называется унитарным.
Т.к. макс. возможное количество чисел, закодированные N-разрядным 2чным кодом = количеству наборов из N аргументов // 
— неполный д.
В ЭВМ д. используют для расшифровки адресных ячеек ЗУ, а также в устройствах цифровой индикации.
Мультиплексоры MUX (MS) (м.) – устройства, подключающие единственный выход к одному из информационных входов, № которого задается 2чн. кодом, поступившим на управляющий (адресный) вход. МS принимает сигнал, поступивший на входы, т.е. решает задачу, обратную распределителю.
Демультиплексоры (DMS, DMX)
DMX – устройства, в котором сигналы с 1ого информационного входа поступают в желательной последовательности на требуемые выходы в зависимости от значения 2ого кода на адр. шинах.
, где n – число выходов, m – число адр. входов.
Логические основы проектирования цифровых устройств
Задачи, решаемые при разработке цифровых логических устройств, можно разделить на две категории:
- Синтез — это процесс построения схемы цифрового устройства по заданию.
- Анализ — процесс обратный синтезу.
Модель дискретного устройства, отражающая только его свойства по переработке сигналов, называется дискретным (цифровым) автоматом.
Рис. 1 — Схема представления цифрового автомата в виде многополюсника
X=(X1, X2, . Xm) — входные сигналы
Y=(Y1, Y2, . Yn) — выходные сигналы
S=(S1, S2, . Sp) — состояние внутренних элементов памяти автомата
В общем случае, модель представляет собой многополюсный черный ящик с m входами и n выходами (рис. 1). Состояние автомата определяется состояниями сигналов на его входах и выходах. Совокупность входных и выходных переменных Х и Y образуют входное и выходное слово автомата, соответственно.
Различные значения входных переменных образуют алфавит (т.к. алфавит входных и выходных переменных един, в дальнейшем будет рассматриваться только один алфавит). В цифровой технике алфавит входного (выходного) слова содержит два значения (две буквы) «1» и «0».
Каждое слово — набор переменных на входе или на выходе автомата, отличается от другого слова хотя бы одной буквой. Каждая буква слова поставлена в соответствие с номером входа (выхода) автомата.
Основы алгебры логики
Алгебра логики (АЛ) является основным инструментом синтеза и анализа дискретных автоматов всех уровней. Алгебру логики называют также "Булевой алгеброй". Алгебра логики базируется на трёх функциях, определяющих три основные логические операции.
1. Функция отрицания ( НЕ ). f1 = X читается, как "f1 есть (эквивалентна) НЕ Х". Элемент, реализующий функцию НЕ, называется элементом НЕ или инвертором .
Рис. 2 — Условное графическое обозначение элемента НЕ
Элемент НЕ имеет два состояния.
| X | f1 |
|---|---|
| 1 | 0 |
| 0 | 1 |
2. Функция логического умножения ( конъюнкции ). Функция логического умножения записывается в виде f2=X 1 ·X 2 . Символы логического умножения: &,^, •.
Функция конъюнкции читается так: "f2 есть (эквивалентна) Х 1 и Х 2 , поскольку функция истинна тогда, когда истинны 1-й и 2-й аргументы (переменные)". Конъюнкцию называют функцией И , элемент, реализующий эту функцию, элементом И .
Рис. 3 — Условное графическое обозначение элемента И
| X1 | X2 | f2 |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 1 | 1 |
В общем случае функцию логического умножения от n переменных записывают так:
Количество переменных (аргументов), участвующих в одной конъюнкции, соответствует количеству входов элемента И .
3. Логическое сложение ( дизъюнкция ). Функция логического сложения записывается в виде f3=X1 + X2, и читается так: "f3 есть Х1 или Х2, поскольку функция истинна, когда истинна одна или другая переменная (хотя бы одна)". Поэтому функцию дизъюнкции часто называют функцией ИЛИ . Символы логического сложения: +,V.
Рис. 4 — Условное графическое обозначение элемента ИЛИ
| X1 | X2 | f2 |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 1 | 1 |
Используя операции (функции) И , ИЛИ , НЕ можно описать поведение любого комбинационного устройства, задав сколь угодно сложное булево выражение. Любое булево выражение состоит из булевых констант и переменных, связанных операциями И , ИЛИ, НЕ .
Пример булева выражения: f(X1,X2) = X1 +X1· X2 +( X1 + X2 )·X1.
Элементарные функции алгебры логики
Среди всех функций алгебры логики особое место занимают функции одной и двух переменных, называемые элементарными. В качестве логических операций над переменными, эти функции позволяют реализовать различные функции от любого числа переменных.
Общее количество функций алгебры логики от m переменных R=2 k , где k=2 m .
| Переменные и их состояния | Обозначение функции | Назначение функции | ||||
|---|---|---|---|---|---|---|
| X1 | 0 | 0 | 1 | 1 | ||
| X2 | 0 | 1 | 0 | 1 | ||
| f0 | 0 | 0 | 0 | 0 | f0=0 | Генератор 0 |
| f1 | 0 | 0 | 0 | 1 | f1=X1·X2 | «И» |
| f2 | 0 | 0 | 1 | 0 | f2=X1· X2 | |
| f3 | 0 | 0 | 1 | 1 | f3=X1 | |
| f4 | 0 | 1 | 0 | 0 | f4= X1 ·X2 | |
| f5 | 0 | 1 | 0 | 1 | f5=X2 | |
| f6 | 0 | 1 | 1 | 0 | f6=X1⊕X2 | Сумматор по модулю два |
| f7 | 0 | 1 | 1 | 1 | f7=X1+X2 | «ИЛИ» |
| f8 | 1 | 0 | 0 | 0 | f8= X1+X2 | «ИЛИ-НЕ» |
| f9 | 1 | 0 | 0 | 1 | f9=X1
X2 | Функция равнозначности |
| f10 | 1 | 0 | 1 | 0 | f10= X2 | «НЕ» Х2 |
| f11 | 1 | 0 | 1 | 1 | f11=X1+ X2 | |
| f12 | 1 | 1 | 0 | 0 | f12= X1 | «НЕ» Х1 |
| f13 | 1 | 1 | 0 | 1 | f13= X1 +X2 | |
| f14 | 1 | 1 | 1 | 0 | f14= X1·X2 | «И-НЕ» |
| f15 | 1 | 1 | 1 | 1 | f15=1 | Генератор 1 |
Основные законы алгебры логики.
Основные законы АЛ позволяют проводить эквивалентные преобразования функций, записанных с помощью операций И , ИЛИ , НЕ , приводить их к удобному для дальнейшего использования виду и упрощать запись.
| N | а | б | Примечание |
|---|---|---|---|
| 1 | 0 =1 | 1 =0 | Аксиомы (тождества) |
| 2 | X+0=X | X*1=X | |
| 3 | X+1=1 | X*0=0 | |
| 4 | X+X=X | X*X=X | |
| 5 | X+ X =1 | X* X =0 | |
| 6 | X =X | Закон двойного отрицания | |
| 7 | X+Y=Y+X | X*Y=Y*X | Закон коммутативности |
| 8 | X+X*Y=X | X[X+Y]X | Закон поглощения |
| 9 | [ X+Y ]= X * Y | [ X*Y ]= X + Y | Правило де-Моргана (закон дуальности) |
| 10 | [X+Y]+Z=X+Y+Z | [X*Y]Z=XZ+YZ | Закон ассоциативности |
| 11 | X+Y*Z=[X+Y][X+Z] | X[Y+Z]=XY+XZ | Закон дистрибутивности |
Булевой алгебре свойственен принцип двойственности, что наглядно иллюстрирован в табл. 5. Как следует из табл. 5, только закон двойного отрицания не подчиняется этому принципу.
Используя законы алгебры логики, можно упростить булевы выражения, в частности, правило склеивания позволяет упростить выражение типа
Действительно, используя законы 2, 5 и 11 можно записать исходное выражение в виде Х 2 (Х 1 + Х 1 ) =Х 2 . Так как логическая операция Х 1 + Х 1 = 1 (см. закон 5), а Х 2 ×1 = Х 2 (см. закон 2б), полученное выражение истинно.
Способы задания функций алгебры логики.
При сопоставлении функций АЛ с дискретными автоматами аргументы функций, сопоставляются с входами, а сами функции с выходами дискретного автомата.
Поскольку дискретный автомат имеет конечное число входов, то мы будем иметь дело с функцией конечного числа аргументов. Если автомат имеет m входов, то количество входных переменных тоже m и число возможных комбинаций наборов значений этих входных аргументов (переменных) К=2 m .
Поскольку автомат имеет конечное число входов, его состояние описывается конечным числом значений функций выходов. Существует несколько способов задания функций алгебры логики дискретного автомата.
Табличный способ
При этом способе функция задается в виде таблицы истинности, представляющей собой совокупность всех наборов переменных и соответствующих им значений функции.
| N | X3 | X2 | X1 | F(X1,X2,X3) |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 1 |
| 2 | 0 | 1 | 0 | 1 |
| 3 | 0 | 1 | 1 | 0 |
| 4 | 1 | 0 | 0 | 0 |
| 5 | 1 | 0 | 1 | 1 |
| 6 | 1 | 1 | 0 | 0 |
| 7 | 1 | 1 | 1 | 0 |
Таблица истинности содержит 2 m строк, m столбцов (по количеству входов) и один столбец для записи значения функции.
Например: пусть требуется задать функцию трех переменных F1(Х1,Х2,Х3) (рис. 5), т.е. автомат на три входа и на один выход, следовательно, M=3, К=8.
Рис. 5 — Функциональное обозначение цифрового автомата трех переменных
Числовой способ
В этом случае функция задается в виде десятичных эквивалентов номеров наборов аргументов, при которых функция принимает единичное значение. Например, для рассмотренного выше примера функция F принимает единичные значения на наборах переменных со следующими номерами: 1, 2, 5, тогда числовой способ задания будет иметь вид
Координатный способ
При этом способе дискретный автомат задается с помощью карты его состояния, которая известна как карта Карно .
Карта Карно содержит 2 m клеток по числу наборов значений переменных. Каждая клетка определяется координатами строк и столбцов, соответствующими определенному набору переменных. Все входные переменные разбиваются на 2 группы так, что одна группа определяет координаты строк, а другая — координаты столбцов. В каждой клетке карты Карно проставляется соответствующее значение функции на заданном наборе. Пример задания функции трех переменных приведен на рис. 6. Числовое выражение этой функции выглядит так:
Рис. 6 — Карта Карно функции трех переменных
Пример построения карты Карно для функции 4-х переменных. Пусть функция задана в числовой форме и имеет вид:
Следовательно, К=16, m=4.
Сначала проводим разметку координат карты Карно без указания значений функции. Для удобства воспользуемся указанием «шапки» в виде прямых линий, “под” которыми переменные входят в значение координат без отрицания (рис.7). Таким образом, по столбцам и по строкам переменные входят без отрицания в пределах линии-шапки.
Рис. 7 — Карта Карно функции четырех переменных
Для наглядности координаты клеток карты Карно указаны в трех формах:
- в виде наборов переменных;
- в виде двоичного числа, соответствующего порядковому номеру набора переменных;
- в десятичном эквиваленте номеров наборов переменных.
На практике координаты внутри клеток не записывают (рис. 8), в клетках указываются единичные значения функции, соответствующие “координатным” наборам переменных. Нулевые значения функции в клетки можно не записывать, т.е. клетки, координаты которых определяются наборами переменных с нулевыми значениями функции, можно оставить пустыми.
Рис. 8 — Карта Карно функции четырех переменных с указанием внешних разметок
Следует отметить, что перестановка местами переменных Х1 и Х2, а так же переменных Х3 и Х4 допускается, допускается также перестановка местами переменных Х1Х2 и Х4Х3. При построении карты Карно, т.е. при задании логической функции, указывают лишь внешние элементы разметки координат (рис. 8).
Аналитический способ задания функции алгебры логики
При этом способе функция задается в виде аналитического выражения, полученного путем применения каких-либо логических операций.
Совершенная нормальная дизъюнктивная форма (СНДФ)
По таблице истинности можно составить логическое выражение, содержащее наборы переменных, в которые входят все переменные с отрицанием или без. Одна из его форм называется СНДФ.
В качестве примера получения СНДФ рассмотрим случай задания логической функции в виде таблицы истинности. Пусть задана функция трех переменных. Таблица истинности этой функции показана в табл. 7.
| N | X3 | X2 | X1 | F(X) |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 0 |
| 2 | 0 | 1 | 0 | 1 |
| 3 | 0 | 1 | 1 | 0 |
| 4 | 1 | 0 | 0 | 1 |
| 5 | 1 | 0 | 1 | 1 |
| 6 | 1 | 1 | 0 | 0 |
| 7 | 1 | 1 | 1 | 0 |
Из таблицы истинности видно, что функция принимает значение логической единицы только на трех наборах переменных, т.е. на 2, 4 и 5-м наборах. Для второй строки (второго набора переменных) можно записать: Х1=0, Х2=1, Х3=0, следовательно, функция f(0,1,0)=1. Принято (по умолчанию) считать, что если переменная в «нормальном» состоянии имеет значение логической единицы, а в инверсном — логического нуля, тогда функцию для второй строки можно представить в виде X 1 Х 2 X 3 = 1. Для четвертой строки — X 1 X 2 Х 3 = 1 и для пятой строки — Х 1 X 2 Х 3 = 1. Аналитическое выражение функции выглядит как
Каждое произведение содержит все три переменные с отрицанием или без отрицания и соответствует только одной строке набора переменных, на котором функция принимает значение логической единицы. Произведения, в которых содержатся все переменные с отрицанием или без, называются конституентами единицы или минтермами . Функция будет представлять логическую сумму всех произведений, равных логической единице. В нашем примере вся сумма (дизъюнкция) соответствует совокупности произведений переменных для трех строк.
СНДФ любой функции записывается по таблице истинности согласно следующему правилу.
Для каждого набора переменных, на которых функция принимает значение логической 1, записываются конституенты, и все эти конституенты объединяются дизъюнктивно.
Переменные каждой строки, имеющие значение логического 0, в конституенты входят с отрицанием (записываются в произведение в инвертированном виде), а переменные, имеющие значения логической 1 — без отрицания.
Любую логическую (булеву) функцию можно представить дизъюнкцией конституент. Если одно из произведений не содержит хотя бы одной переменной, то такая форма называется нормальной дизъюнктивной формой (НДФ).
Совершенная нормальная конъюнктивная форма (СНКФ)
Совершенной конъюнктивной нормальной формой (СКНФ) называется такая конъюнктивная нормальная форма, у которой в каждую дизъюнкцию входят все переменные данного списка (либо сами, либо их отрицания), причем в одном и том же порядке.
Свойства совершенства для СКНФ:
- Каждый логический множитель формулы содержит все переменные, входящие в функцию.
- Все логические множители различны.
- Ни один множитель не содержит одновременно переменную и ее отрицание.
- Ни один множитель не содержит одну и ту же переменную дважды.
Алгоритм получения СКНФ по таблице истинности:
- Отметить те строки таблицы истинности, в последнем столбце которых стоят 0:
- Выписать для каждой отмеченной строки дизъюнкцию всех переменных следующим образом: если значение в данной строке равно 0, то в дизъюнкцию включать саму эту переменную, если равно 1, то ее отрицание.
- Все полученные дизъюнкции связать в конъюнкцию.
- Упрощаем формулу, применяем законы логики (если это необходимо).
Если (хотя бы одна) дизъюнкции, которые называются также макстермами (конституентами нуля), не содержат отдельные переменные, то такая форма записи функции называется нормальной конъюнктивной формой (НКФ).
Пример: Восстановить логическую функцию по ее таблице истинности (табл. 8).
| N | X1 | X2 | X3 | F(X) | F (X) |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 0 |
| 1 | 0 | 0 | 1 | 1 | 0 |
| 2 | 0 | 1 | 0 | 0 | 1 |
| 3 | 0 | 1 | 1 | 0 | 1 |
| 4 | 1 | 0 | 0 | 1 | 0 |
| 5 | 1 | 0 | 1 | 1 | 0 |
| 6 | 1 | 1 | 0 | 0 | 1 |
| 7 | 1 | 1 | 1 | 1 | 0 |
Решение
СКНФ составляется на основе таблицы истинности по правилу: для каждого набора переменных, при котором функция равна 0, записывается сумма, в которой с отрицанием берутся переменные, имеющие значение 1.
F(X1,X2,X3)=(X1+ X2 +X3)•(X1+ X2 + X3 )•( X1 + X2 +X3)
Полная система логических функций. Понятие о базисе
Система простых логических функций, на основе которой можно получить любую сложную логическую функцию, называется функционально полной. В этом случае говорят, что этот набор образует базис.
Что такое цифровой автомат
Цифровыми (конечными) автоматами называются устройства, предназначенные для обработки информации, заданной цифровыми кодами. Информация, поступающая в цифр. устройство представляет собой набор дискретных сигналов, отображающих некоторую последовательность 0 и 1, т.е. двоичный код.
В общем случае, на вход цифр. устройства поступает некоторый набор 2ых переменных Х(х1, х2… хn), а с выхода устройства снимается набор или множество значений У(у1,у2… уn), причем цифр. устройства реализуют определенную связь (лог. функцию) между вх. и вых. переменными.
На передачу сигнала через устройство отводится конечн. промежуток времени – такт работы устройства.
Если за 1 такт в устройство передается 1 из разрядов 2ого числа (кода), устройство работает в посл. коде, если за 1 такт его работы передается все двоичное число одновременно, то устройство работает в парал. коде:
Применительно к ЭВМ в зависимости от способа обработки циф информации различают 2 класса дискретных автоматов: комбинационные и последовательные.
Комбинационные автоматы (комбинационные схемы) – устройства, в которых значения вых сигналов У(у1, у2… уm) в любой момент дискр. времени однозначно определяется совокупностью вх сигналов Х. Т.о. одним из достоинств комб. схем является их высокое быстродействие. Преобразование информации в комб. схемах однозначно определяется лог. функциями вида . Лог функции и соответствующие им комбинационные схемы разделяют на регулярные и нерегулярные структуры. Регулярные структуры предполагают построение схема таким образом, что кажд из ее выходов строится по аналогии с предыдущими. В нерегулируемых структурах такая аналогия отсутствует.
Многие регулярные структуры положены в основу построения ряда интегральных схем малой и средней степени интеграции, а также отдельных частей БИС и СБИС. Из регулярных комбинац. схем наиболее распространены шифраторы, дешифраторы, схемы сравнения, комбинационные сумматоры, коммутаторы (мультиплексоры и демультплексоры), выполненные на основе лог. элементов и несодержащих обратных связей.
В последовательном автомате выходные сигналы в данный момент времени зависят не только от значения входного сигнала в данный момент, но и от значения входного сигнала в прошлом, т.е. внутреннее состояние устройства. Понятеие состояния последов. автомата предполагает наличие у него внутренней памяти, где должна хранится информация о предыдущих воздействиях. Функциональное соотношение:
Различают последовательные автоматы автоматы Мура(выходной сигнал определяется текущим состоянием автомата) и автоматы Мили (выход зависит как от состояния, так и от входного сигнала)
пример Автоматы Мура: триггеры, счетсчики, накапливающие сумматоры, регистры и др.
Шифраторы (кодеры, ш.) – преобразуют сигнал на одном из своих входов (унитарный код) в n-разрядный 2ный код на выходе, соответствующий 10чному номеру активного входа.
Число информационных входов ш. = числу символов преобразуемого кода и должно соответствовать условию , где n – число информационных выходов.
Кроме обычных шифраторов, существуют шифраторы с приоритетом, в таких ш. допускается подавать сигнал 1 одновременно на несколько входов, а ш. выдаст на выход код числа, соответствующего № старшего входа, т.е. если при работе ЭВМ решается задача определения приоритетного претендента на обслуживание и имеется одновременно несколько запросов, то обслужится запрос с наибольшим номером. Основное назначение ш. является преобразование № источника сигнала в 2чный код.
Дешифраторы (д.)
Д. представляет собой комбинационное устройство, позволяющее распознавать числа, представленные позиционно n-разрядным кодом.
Если на вход д. подать n-размерный 2ый код, то на выходе устройства появляется код «1 из N» в кодовой комбинации которого только одна позиция будет представлена единицей, а остальные – нулем. Такой код называется унитарным.
Т.к. макс. возможное количество чисел, закодированные N-разрядным 2чным кодом = количеству наборов из N аргументов // — неполный д.
В ЭВМ д. используют для расшифровки адресных ячеек ЗУ, а также в устройствах цифровой индикации.
Мультиплексоры MUX (MS) (м.) – устройства, подключающие единственный выход к одному из информационных входов, № которого задается 2чн. кодом, поступившим на управляющий (адресный) вход. МS принимает сигнал, поступивший на входы, т.е. решает задачу, обратную распределителю.
Демультиплексоры (DMS, DMX)
DMX – устройства, в котором сигналы с 1ого информационного входа поступают в желательной последовательности на требуемые выходы в зависимости от значения 2ого кода на адр. шинах.
, где n – число выходов, m – число адр. входов.
Описание цифровых автоматов на VHDL
Цифровой автомат (ЦА) — это устройство, которое осуществляет прием, хранение и преобразование дискретной информации по некоторому алгоритму и может находиться в одном из нескольких устойчивых состояний [7].
Рисунок 1 — Граф цифрового автомата
Если выходной сигнал цифрового автомата зависит лишь от текущего состояния, то такой автомат называется автоматом Мура, если же выходной сигнал зависит от текущего состояния и входных сигналов, то такой цифровой автомат носит название автомата Мили.
Цифровой автомат может быть описан с помощью таких представлений:
— в виде ориентированного графа,
— с помощью переходов и выходов.
Представление цифрового автомата в виде ориентированного графа показано на рис. 1. Здесь в кругах — вершинах графа — показаны состояния цифрового автомата, переходы между состояниями показаны дугами между вершинами, а переход в то же самое состояние — петлей.
Возле дуг и петель показаны значения входных сигналов, при которых происходит этот переход. Например, (a OR b) обозначает, что этот переход произойдет при a = 1 или b = 1.
Выходные сигналы для автомата Мура показаны около вершин графа, а для цифрового автомата Мили — на дугах возле входных сигналов. Т.о. на рис. 1 показан цифровой автомат Мура.
Представление цифрового автомата с помощью таблиц предполагает наличие двух таблиц: таблицы переходов и таблицы выходов. Таблица переходов связывает между собой текущее состояние, входные сигналы и будущее состояние цифрового автомата. Таблица переходов ЦА, описанного графом на рис. 1, показана в табл. 1.
Таблица 1 — Таблица переходов цифрового автомата
| Текущее состояние | Следующее состояние | Условие перехода |
| S0 | S0 | a=0 ИЛИ c=0 |
| S0 | S1 | a=1 |
| S1 | S1 | a=1 ИЛИ b=1 |
| S1 | S0 | a=0 И b=0 |
| S0 | S2 | c=1 |
| S2 | S2 | c=1 ИЛИ b=1 |
| S2 | S0 | c=0 И b=0 |
Таблица выходов — показывает соответствие текущего состояния цифрового автомата и его выходных сигналов (табл. 2).
Таблица 2 — Таблица выходов цифрового автомата>
| Текущее состояние | Выход |
| S0 | 00 |
| S1 | 01 |
| S2 | 10 |
При реализации цифрового автомата мы будем придерживаться принципа разделения на комбинационную и последовательностную части схемы. При такой интерпретации цифровой автомат будет представлен тремя блоками (рисунок 2):
— комбинационный блок логики переходов;
— регистр для хранения состояний ЦА;
— комбинационный блок формирования выходных сигналов — разные для ЦА Мили и Мура.
Рисунок 2 — Схематическое изображение цифрового автомата с асинхронными выходами
Схема логики переходов на свой вход получает код текущего состояния цифрового автомата (present_st) и внешние сигналы (input_signal). Выходом этого блока будет код следующего состояния (next_st).
В регистр состояний входит три сигнала: тактовый (clk), сброса (reset) и код следующего состояния (next_st). Тактовый сигнал и сигнал сброса предназначены для управления триггерами, которые хранят состояние цифрового автомата. По переднему фронту тактового сигнала производится запись следующего состояния (next_st) в триггеры. Результаты записи в триггеры появляется на выходе регистра состояния в виде сигнала текущего состояния ЦА (present_st).
Блок формирования выходных сигналов в зависимости от состояния ЦА (и входных сигналов для автомата Мили) формирует асинхронные выходные сигналы. Для получения синхронных выходных сигналов в этот блок дополнительно встраивают регистр.
Использование VHDL для описания цифровых автоматов
Для описания состояний цифрового автомата необходимо использовать перечислимый тип. Для этого описывается тип (state_type), значениями которого являются состояния цифрового автомата. Потом описывается сигнал (state) этого перечислимого типа, в котором и будет храниться текущее состояние автомата.
При реализации будет получена схема из нескольких триггеров. В зависимости от метода кодирования состояний количество триггеров может изменяться, что влияет на быстродействие и размер схемы. Более подробно о методах кодирования мы поговорим чуть позже.
Для описания работы цифрового автомата и создания комбинационных схем логики переходов и выходов необходимо использовать соответствующие таблицы и помощью оператора case проанализировать значения сигнала present_st.
Процесс, который описывает комбинационную часть для вычисления логики переходов цифрового автомата, может быть описан с помощью такого шаблона:
Для описания логики выходных сигналов возможно использование оператора процесса или оператора параллельного условного присваивания.
Процесс, который описывает комбинационную часть для вычисления выходных сигналов цифрового автомата Мура, может быть описан с помощью такого шаблона:
Здесь в списке инициализации процесса используется только текущее состояние цифрового автомата present_st, значения которого анализируются с помощью оператора case.
Для автомата Мили этот же процесс будет выглядеть таким образом:
Этот процесс для инициализации использует текущее состояние ЦА (present_st) и входной сигнал (input_signal) так как изменения любого из этих сигналов должно запускать выполнение процесса.
Для получения синхронных выходных сигналов необходимо использовать процесс, у которого в списке инициализации находится только тактовый сигнал clk. Анализ текущего состояния так же как и в предыдущем случае производится с помощью оператора case.
Формирование выходных сигналов с помощью параллельного условного присваивания не требует оператора процесса. В этом случае можно использовать такую конструкцию:
При описании последовательностной части цифрового автомата в списке инициализаторов процесса должны содержатся сигналы clk и reset. При поступлении сигнала сброса reset цифровой автомат переходит в начальное состояние init, из которого начинается работа всего автомата. Передний фронт сигнала clk приводит к записи в триггеры ЦА его нового текущего состояния, т.е. сигнал next_st переписывается в сигнал present_st.
Фактически последовательностная часть представляет собой регистр со сбросом:
Сигнал сброса может быть синхронным или асинхронным. Выше в листинге описан вариант асинхронного сброса.
При использовании асинхронного сигнала сброса мы всегда знаем в каком состоянии будет находиться цифровой автомат при включении питания, т.е. до поступления тактового сигнала и начала нормальной работы системы. В этом случае нет необходимости декодировать неиспользуемые состояния цифрового автомата, что позволяет уменьшить схему логики переходов.
Использование синхронного сигнала сброса не позволяет определить в каком состоянии окажется автомат при включении питания. Возможно, что он <<залипнет>> в одном из неописанных состояний. Т.о. при описании цифрового автомата необходимо описать все2^n комбинаций состояний триггеров вне зависимости от того являются они рабочими состояниями цифрового автомата или нет. Здесь n — количество триггеров, применяемых для кодирования цифрового автомата. Это, в свою очередь приведет, к увеличению схемы логики переходов.
Для того, чтобы избежать <<залипания>> ЦА в неописанных состояниях необходимо явно прописывать действия в таких ситуациях с помощью конструкции when… others. Например, возможно использование такого процесса для описания синхронного сброса и действий в неиспользуемых состояниях.
Три, два, один
Цифровой автомат можно описать с помощью одного, двух или трех операторов процесса. Эти варианты рассмотрим на примере цифрового автомата управления светофором.
Этот цифровой автомат имеет пять состояний: начальное (Init), красный ( R ), зеленый (G) и два желтых — один для перехода из красного к зеленому (RG), а второй — из зеленого к красному (GR). В том случае, когда вход cnt равняется нулю, никаких переходов не происходит, когда вход cnt равняется единице — происходит переход в следующее состояние. Граф цифрового автомата изображен на рис. 3.
Рисунок 3 — Граф цифрового автомата светофора
Этот же автомат может быть представлен с помощью таблицы переходов и таблицы выходов. Выходной сигнал представлен трехбитным вектором, в котором старший бит отвечает за красный, второй – за желтый и младший – за зеленый.
Таблица 3 — Таблица переходов
| present_ st | next_st | Условие перехода |
| Init | Init | cnt = 0 |
| Init | R | cnt = 1 |
| R | R | cnt = 0 |
| R | RG | cnt = 1 |
| RG | RG | cnt = 0 |
| RG | G | cnt = 1 |
| G | G | cnt = 0 |
| G | GR | cnt = 1 |
| GR | GR | cnt = 0 |
| GR | R | cnt = 1 |
Таблица 4 — Таблица выходов
| present_st | output |
| Init | 000 |
| R | 100 |
| RG | 010 |
| G | 001 |
| GR | 010 |
Для описания состояний ЦА необходимо описать перечислимый тип, в котором будут перечислены все состояния. В приведенном примере вводится тип state_type, который содержит пять значений: Init, R, RG, G, GR. Для работы конкретного экземпляра цифрового автомата нужно описать сигналы этого типа. В примере это сигналы next_st, present_st для хранения последующего и текущего состояний автомата соответственно. При выполнении процессов этот сигнал будет принимать значение текущего состояния цифрового автомата.
Теперь рассмотрим описание этого цифрового автомата с помощью трех процессов (рисунок 4), каждый из которых описывает отдельную часть цифрового автомата:
— комбинационная часть для логики переходов;
— комбинационная часть для выходных сигналов;
— последовательностная часть только для записи состояний цифрового автомата.
Рисунок 4 — Цифровой автомат с тремя процессами
Такой вариант описания цифрового автомата дает возможность разработчику отделять логику переходов от логики формирования выходящих сигналов и осуществлять синхронную запись состояния автомата в регистр хранения состояния. А это, в свою очередь, позволяет более просто описывать и отлаживать синхронный цифровой автомат.
Сама программа представляет собой комбинацию трех процессов, описанных выше.
Результирующий граф ЦА, полученный при компиляции в пакете Quartus II показан на рисунке 5 (меню Tools — Netlist Viewers — State Machine Viewer).
Рисунок 5 — Цифровой автомат с тремя процессами. Результат компиляции
Результат синтеза программы, приведенной в листинге выше, показан на рис. 6 (меню Tools — Netlist Viewers — Technology Map Viewer). Для облегчения понимания на рисунке элементы ввода-вывода обозначены как IO, триггеры как FF, а логические элементы — LE. Как видно в результате синтеза получится схема из 5 триггеров для хранения состояний цифрового автомата (в случае метода кодирования One Hot) и двух логических элементов для реализации схемы переходов и формирования выходных сигналов.
Рисунок 6 — Цифровой автомат с тремя процессами. Technology Map Viewer
Описание с помощью двух процессов (рис. 6) предполагает, что блок логики переходов и регистр состояний объединяются в один процесс, в котором с помощью оператора case производится выбор будущего значения состояния цифрового автомата. Поскольку нет необходимости разделять сигналы текущего и будущего состояний, то эти два сигнала заменены на один, state, в котором и хранится состояние цифрового автомата.
В листинге ниже показан пример описания ЦА с асинхронным сбросом. В результате компиляции будет получен такой же результат как и в предыдущем случае — рис.7.
Рисунок 7 — Цифровой автомат с двумя процессами
Рисунок 8 — Результат синтеза цифрового автомата с синхронным сбросом
Описание цифрового автомата с помощью одного процесса предполагает, что вся логика находится в одном процессе. Некоторые авторы [5] считают, что использование одного процесса для описания цифрового автомата является более простым и позволяет более просто описывать и отлаживать цифровой автомат. Данное утверждение справедливо для небольших цифровых автоматов. При увеличении количества состояний и использовании одного процесса ухудшается читабельность кода. Потому как еще древние римляне при описании цифровых автоматов пользовались правилом «Разделяй и властвуй».
Еще одним аргументом, который приводится в пользу использования одного процесса при описании цифрового автомата, является то, что этот вариант предполагает использование синхронных выходных сигналов. Это условие не является обязательным для всех ЦА и может быть легко достижимо, что было показано выше при обсуждении логики формирования выходных сигналов.
И все же, для завершения образа, приведем пример описания цифрового автомата с асинхронным сбросом с помощью одного процесса.
Результат компиляции программы показан на рисунке \ref . Очевидно, что результат оказался таким же как и при описании с помощью двух процессов с единственным отличием – добавились триггеры для выходного регистра.
Рисунок 9 — Цифровой автомат с одним процессом
Подведем небольшие итоги наших изысканий.
Первое, и самое важное. Цифровой автомат существует! Мы его видели на картинке 5.
Второе. Описания с помощью двух и трех процессов дают одинаковый результат и выбор метода описания зависит от предпочтений разработчика.
Третье. Нужно очень внимательно относиться к начальному сбросу автомата и описанию неиспользуемых состояний.
Четвертое. Описание с помощью одного процесса приводит к появлению регистров для выходных сигналов цифрового автомата.
1. Altera. Quartus II Handbook Version 10.0 Volume 1: Design and Synthesis Vol. 1, 2010 — 1820 p.
2. B. Cohen. VHDL Coding style and Metodologies. Kluwer Academic Publishers.2002 — 454 p.
3. D. L. Perry. VHDL programming by example. New York: McGraw-Hill, 2002.- 476 p.
4. D. J. Smith. HDL chip design: a practical guide for designing, synthesizing, and simulating ASICs and FPGAs using VHDL or Verilog. Madison, AL: Doone Publications, 1996. — 448 p.
5. A. Taylor. How to Implement State Machines in Your FPGA. Xcell, 81(4), p. 52–57.
6. Xilinx. VHDL Reference Guide. XST User Guide.
7. К. Г. Самофалов. Прикладная теория цифровых автоматов. М. 1987. 375 с.
Теория цифровых автоматов
Цифровые автоматы — это цифровые устройства, которые выполняют заданные функции без прямого участия людей.
Общие сведения о цифровых автоматах
Под цифровым автоматом следует понимать дискретный преобразователь информации, который способен принимать разные состояния, осуществлять переход под влиянием входного сигнала из одного состояния в другое и формировать выходные сигналы. Автомат именуется конечным, когда множество его внутренних состояний, а также множество значений входных и выходных сигналов являются конечными.
Цифровые автоматы могут обладать жесткой (схемной) логикой, а также логикой, которая хранится в памяти. Существуют следующие классы автоматов:
- Синхронные автоматы.
- Асинхронные автоматы.
Синхронным автоматом является автомат, который работает под управлением тактовых, то есть, синхронизирующих, сигналов, имеющих постоянную длительность и постоянную частоту, если квантование времени равномерное. Входные сигналы способны влиять на состояние автомата только при наличии тактового сигнала и не изменяются в течение времени тактового сигнала. Период следования тактовых сигналов обязан быть больше или равен времени, которое требуется конкретному автомату, для того чтобы перейти из одного состояния в другое. При рассмотрении абстрактного автомата, предполагается, что изменение внутренних состояний автомата осуществляется в интервалы времени между смежными тактовыми сигналами, а выходные сигналы должны формироваться по фронту очередного тактового сигнала.
Для асинхронных автоматов длительность интервала времени, в течение которого останется неизменным состояние входных сигналов, считается переменной величиной и может определяться временем, которое требуется автомату, для того чтобы установить соответствующие выходные сигналы и завершить переход в новое состояние. То есть, асинхронный автомат обязан сформировать каким-либо известным методом сигнал об окончании очередного такта, по которому текущие входные сигналы можно снимать, а далее приступить к началу следующего такта, то есть, разрешается поступление новых входных сигналов.
Теория цифровых автоматов
Управление — это такая организация технологического процесса, которая способна гарантировать достижение поставленной цели. Теория цифровых автоматов является разделом современной науки и техники, основой которого выступают как фундаментальные, общенаучные дисциплины, такие как, математика, физика, химия и так далее, так и прикладные дисциплины, такие как, электроника, микропроцессорная техника, программирование и так далее.
Каждый процесс, связанный с управлением, в том числе и автоматическим, должен содержать следующие базовые элементы:
- Получение информации, характеризующей задачу управления.
- Получение информации, характеризующей итоги управления.
- Осуществление анализа поступившей информации.
- Воздействие на управляемый объект, то есть, реализация решения.
Это означает, что для реализации процесса управления, система управления цифрового автомата должна иметь:
- Источники информации о задаче управления.
- Источники информации об итогах управления. То есть, это могут быть различные измерительные устройства, типа датчиков, детекторов и тому подобное.
- Оборудование, которое позволяет выполнить анализ поступающих данных и сформировать решение.
- Исполнительное оборудование, которое способно оказать воздействие на управляемый объект, то есть, обладает различными регуляторами, двигателями, усилителями, преобразователями и тому подобное.
В случае, когда цифровой автомат оснащен всеми указанными выше элементами, то такой автомат представляет собой замкнутую систему управления. Принципом обратной связи считается управление техническим объектом с использованием информации об итогах управления. Структурная организация такого цифрового автомата показана на рисунке ниже.
Рисунок 1. Структурная организация цифрового автомата. Автор24 — интернет-биржа студенческих работ
Если цифровой автомат имеет структурную организацию, изображенную на рисунке выше, и может функционировать без участия человека, то такой автомат может считаться системой автоматического управления (САУ). А когда цифровой автомат работает при участии человека в качестве оператора, то тогда он может считаться автоматизированной системой управления.
Если управление реализовано по определенному закону изменения объекта во времени и не зависит от результатов управления, то такое управление осуществляется по разомкнутому циклу, а сам процесс управления является программным управлением. К цифровым автоматам, использующим принцип разомкнутого цикла, могут быть отнесены, к примеру, промышленные конвейерные и роторные линии, станки с числовым программным управлением (ЧПУ) и тому подобное.
Цифровые автоматы, выполняющие функции автоматических систем управления, можно разделить на следующие типы:
- Цифровые автоматы, являющиеся системами автоматического управления (САУ).
- Цифровые автоматы, являющиеся системами автоматического регулирования (САР).
- Цифровые автоматы, являющиеся следящими системами (СС).
Необходимо подчеркнуть, что системы САР и СС по существу могут считаться подмножествами САУ.
Автоматическая система управления, способная обеспечить неизменным, то есть, постоянным, какое-либо значение (или группу значений) в управляемом объекте, называется системой автоматического регулирования (САР). Системы автоматического регулирования могут считаться наиболее применяемым типом автоматических систем управления.
В теории цифровых автоматов, управляющих техническими устройствами, принято разбивать систему на совокупность отдельных звеньев, соединенных в сетевые структуры. В простейшем случае система может состоять из одного звена, на вход которого поступает входной сигнал (вход), а на выходе формируется отклик системы (выход). Такая система представлена на рисунке ниже.
Тема 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) у которого:
2. Z= — множество входных сигналов (входной алфавит),
3. W= — множество выходных сигналов (выходной алфавит),
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 возможен переход с заданной вероятностью в различные состояния.
Вслед за этапом абстрактного синтеза автоматов следует этап структурного синтеза, целью которого является построение схемы, реализующей автомат из элементов заданного типа. Если абстрактный автомат был лишь математической моделью, проектируемого устройства, то в структурном автомате учитывается структура входных и выходных сигналов автомата, а также его внутренне устройство на уровне логических схем. Основной задачей структурной теории автоматов является разработка общих методов построения структурных схем автоматов.
В отличие от абстрактного автомата, имеющего один вход и один выход (рис. 5.3.а), на которые поступают сигналы во входном и выходят в выходном W= алфавитах, структурный автомат (рис. 5.3.б) имеет L входных каналов х1,х2. хL и N выходных y1,y2,…,yN на каждом из которых присутствует сигнал структурного алфавита.
Рис.5.3. Абстрактный (а) и структурный (б) автоматы
Обычно в качестве структурного используется двоичный алфавит. В этом случае каждому входному сигналу ZF абстрактного автомата соответствует некоторый двоичный вектор(lf1,lf2. lfL), где lfLÎ .
Очевидно, что для представления (кодирования) входных сигналов Z1. ZF абстрактного автомата различными двоичными векторами должно быть выполнено условие L 
] log2F [, аналогично N ] log2G [. Например, Z= и W= , тогда L log24=2 и N log23=2
Следовательно, структурный автомат с двумя входами x1 и x2 и двумя выходами y1 и y2 может быть представлен в виде, представленном на рис.5.4:
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).
Автомат Мура задается одной отмеченной таблицей переходов (табл. 5.4), в которой каждому столбцу приписаны не только состояние am, но еще и выходной сигнал Wg, соответствующий этому состоянию, где Wg=l(am).
Для частичных автоматов Мили и Мура в рассмотренных таблицах на месте неопределенных состояний и выходных сигналов ставится прочерк . Об этом говорит сайт https://intellect.icu . В таких автоматах выходной сигнал на каком-либо переходе всегда не определен, если неопределенным является состояние перехода. Кроме того, выходной сигнал может быть неопределенным и для некоторых существующих переходов.
Для задания С — автоматов также используется табличный метод. В этом случае таблица переходов (табл.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= , A2= , A3= , A4= . Как видно, в эквивалентном автомате Мура количество состояний 7. Для построения графа Sb поступаем следующим образом. Т.к. в автомате Sa есть переход из состояния а1 в состояние а2 под действием сигнала z1 с выдачей W1, то из множества состояний A1 = , порождаемых состоянием а1 автомата Sa в автомате Sb должен быть переход в состояние (a3, W2) = b6 под действием сигнала Z2 и т.д. Граф эквивалентного автомата Мура представлен на рис. 5.8.
Рис. 5.8. Автомат Мура Sb, эквивалентный автомату Мили Sa
Если от автомата Мура Sb, эквивалентного автомату Мили Sa (рис. 5.8) вновь перейти к автомату Мили, то получим автомат Мили S1 (рис. 5.9).
Рис. 5.9. Автомат Мили S1, эквивалентный автомату Мура Sb
Вследствие транзитивности отношения эквивалентности два автомата Мили 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.
Сравнивая p3 и p2, замечаем, что D1 = C1, D2 = C2, D3 = C3, p3 = p3. Следовательно получили разбиение на ¥- эквивалентные классы. Т.к. всего три таких класса, то минимальный автомат будет содержать всего три состояния. Выбираем из каждого класса Di по одному состоянию и получаем множество состояний A’ минимального автомата. Пусть, например, A’= . Для получения минимального автомата из первоначальных таблиц переходов и выходов (табл. 5.7) вычеркиваем столбцы, соответствующие «лишним состояниям» a2, a3, a6. В результате получается минимальный автомат Мили, эквивалентный исходному автомату (табл. 5.10).
Табл.5.10. Таблицы переходов и выходов минимального автомата
Минимизацией числа внутренних состояний автомата заканчивается этап абстрактного синтеза.
5.6. Принцип микропрограммного управления. Понятия об операционном и управляющем автоматах
ЭВМ перерабатывает информацию, выполняя над ней какие-то операции. Для выполнения операций над информацией используются операционные устройства – процессоры, каналы ввода-вывода, устройства управления внешними устройствами и т.д. Функцией операционного устройства является выполнение заданного множества операций F= над входными словами D= c целью вычисления слов R= , которые представляют результаты операцийR=fg(D), где g=1,2. G.
Функциональная и структурная организация операционных устройств базируется на принципе микропрограммного управления, который состоит в следующем:
1. Любая операция fg (g=1. G), реализуемая устройством, рассматривается как сложное действие, которое разделяется на последовательность элементарных действий над словами информации. Эти элементарные действия называются микрооперациями.
2. Для управления порядком следования микроопераций используются логические условия, которые в зависимости от значений слов, преобразуемых микрооперациями, принимают значения «ложь» или «истина» (1 или 0).
3. Процесс выполнения операций в устройстве описывается в форме алгоритма, который представляется в терминах микроопераций и логических условий и
Продолжение:
См.также
- эквивалентность конечных автоматов , теорема мура ,
- эквивалентные автоматы преобразование автоматов мура в мили , из мили в мура ,
- построение абстрактных автоматов по граф-схеме микропрограммы ,
- конечные автоматы , виды конечных автоматов ,
- абстрактный автомат , методы задания автоматов , классификация абстрактных автоматов ,
Я хотел бы услышать твое мнение про схемотехника цифровых узлов Надеюсь, что теперь ты понял что такое схемотехника цифровых узлов, цифровой автомат и для чего все это нужно, а если не понял, или есть замечания, то нестесняся пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Компьютерная схемотехника и архитектура компьютеров
Разработка цифрового автомата
Цифровой автомат – это дискретный преобразователь информации, который способен принимать различные состояния, переходить под воздействием сигналов или команд программы решения задачи из одного состояния в другое и выдавать выходные сигналы.
Цифровой автомат является конечным, если множество его внутренних состояний, а также множество значений выходных и входных сигналов конечны. Автоматы могут быть со схемной логикой и логикой, которая хранится в памяти. Различают два класса цифровых автоматов:
- Асинхронные.
- Синхронные.
Синхронные цифровые автоматы характеризуются следующими аспектами. Они функционируют под управлением тактовых сигналов (синхронизирующие сигналы), с постоянной длительностью и постоянной частотой. Период следования тактовых сигналов должен быть больше или равен времени, которое необходимо реальному автомату для перехода из одного состояния в другое. В асинхронном цифровом автомате длительность интервала времени, в течении которого остается неизменным состояние входных сигналов, является величиной переменной, которая определяется временем, необходимым устройству для установки соответствующих выходных сигналов и завершения перехода в новое состояние. Таким образом, асинхронный цифровой автомат должен формировать сигнал о завершении очередного такта, согласно которому могут быть сняты входные сигналы, после чего начинается следующий такт, то есть появляется возможность поступления новых входных сигналов. Чтобы создать конечный цифровой автомат необходимо зафиксировать три конечных множества: множество возможных входных сигналов, множество возможных выходных сигналов и множество возможных внутренних состояний автомата. На множестве состояний автомата фиксируется одно из них в качестве начального. Состояние автомата используется для описания систем, выходные сигналы которых зависят не только от входных сигналов в данный момент времени, но и от некоторой предыстории — сигналов, поступивших на вход системы ранее. Таким образом цифровые автоматы являются последовательными схемами, обладающие памятью.
Разработка цифрового автомата
Разработка цифрового автомата состоит из следующих этапов:
- Построение структурной схемы цифрового автомата. Основными элементами цифрового автомата являются преобразователь кода, счетчик, регистр сдвига, устройство управления. Счетчик предназначен для получения взвешенного кода. Регистр сдвига предназначен для преобразования параллельного кода, который поступает с выхода преобразователя. Устройство управления используется получения управляющих сигналов цифрового автомата. Такие составляющие, как счетчик, регистр и преобразователь подлежат подробной разработке, а устройство управления разрабатывается на стадии расчета быстродействия цифрового автомата.
- Разработка преобразователя кода. Данный этап проектирования состоит из построения таблицы состояний, записи алгебраической функции, выбора микросхемы для построения принципиальной схемы, разработки принципиальной схемы, расчета быстродействия и потребления энергии.
- Разработка счетчика. На данном этапе осуществляется разработка функциональной схемы счётчика пол заданным условиям.
- Разработка регистра сдвига.
Порядок и особенности разработки цифрового автомата зависят от имеющихся исходных данных, требований технического задания, условий эксплуатации устройства и т. п.
В настоящее время существуют два основных принципа разработки цифрового автомата: принцип программируемой логики и принцип схемной логики.
В случае использования принципа схемной логики, в процессе разработки цифрового автомата подбирается некоторый набор цифровых микросхем и определяется схема соединения их выводов, обеспечивающая требуемое функционирование устройства. Автоматы, построенные согласно данному принципу, обеспечивают самое высокое быстродействие при заданном типе технологии элементов. Недостаток принципа схемной логики заключается в трудности применения последних достижений микроэлектроники, а именно интегральных микросхем большой и сверхбольшой степени интеграции, что связано с тем, что для разных устройств требуются различные интегральные микросхемы, что является причиной экономической нецелесообразности производства таких автоматов в промышленных масштабах.
Принцип программируемой логики предполагает построение автомата с использованием одной или нескольких интегральных микросхем большой интеграции некоторого универсального устройства, необходимое функционирование которого обеспечивается посредством заключения в память устройства определенной программы или микропрограммы.