50267 (Структурные автоматы), страница 3
Описание файла
Документ из архива "Структурные автоматы", который расположен в категории "". Всё это находится в предмете "информатика" из 1 семестр, которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "курсовые/домашние работы", в предмете "информатика, программирование" в общих файлах.
Онлайн просмотр документа "50267"
Текст 3 страницы из документа "50267"
Х = {x1, x2, x3}; Kвх >= int(log2|3|)= 2,
У = {y1, y2, y3, y4}; Kвых >= int(log2|3|)= 2,
А = {a1, a2, а3}; Kсост >= int(log2|3|)= 2.
Заполним таблицы кодирования (табл. 9 – 11):
Таблица 9.
| Х | z1 | z2 |
| x1 | 0 | 0 |
| x2 | 0 | 1 |
| x3 | 1 | 0 |
Таблица 10
| У | w1 | w2 |
| y1 | 1 | 0 |
| y2 | 0 | 0 |
| y3 | 1 | 1 |
| y4 | 0 | 1 |
Таблица 11
| А | 1 | 2 |
| a1 | 0 | 0 |
| a2 | 0 | 1 |
| a3 | 1 | 1 |
Каждый разряд вектора кода обозначим символом с соответствующим номером. Входные - z, выходные - w, состояния – а.
Таблица 12
| z1z2 | |||
| 12 | 00 | 01 | 10 |
| 00 | 01/11 | 11/01 | 01/00 |
| 01 | - | 00/11 | 11/10 |
| 11 | 00/00 | - | 11/11 |
В результате получим таблицу переходов и выходов структурного автомата (табл. 12.). Выполним кодирование элементарного автомата Мура (табл. 8.):
- выпишем алфавиты автомата и определим длины векторов кодов алфавитов,
R={r1,r2}; Kвх >= int(log2|2|)=1,
В = {b1, b2}; Kсост >= int(log2|2|)= 1;
-заполним таблицы кодирования:
Структурная таблица переходов элементарного автомата Мура имеет вид (табл. 15.):
Так как абстрактный автомат имеет три состояния, каждое из которых кодируется двумя разрядами, то структурный автомат будет содержать два запоминающих элемента.
Теперь задача сводится к синтезу комбинационной схемы, реализующей канонические уравнения:
w1=l(a1,a2.z1,z2), w2= l(a1, a2, z1, z2) - функции выходов автомата
1= f(a1,a2.z1,z2), 2= f(a1,a2.z1,z2) - функции возбуждения элементов памяти автомата.
Функции w1, w2 можно получить непосредственно из отмеченной таблицы переходов структурного автомата как дизъюнкцию конъюнкций, соответствующих тем наборам (1,2.z1,z2), на которых эти функции принимают значения 1. Но более удобно пользоваться так называемой таблицей формирования функций возбуждения и функций выходов автомата, в которой в табличной форме задана система булевых функций (табл. 16). Заполним эту таблицу, используя коды соответствующих алфавитов и таблицу переходов и выходов абстрактного автомата. Для заполнения колонок 1, 2 необходимо воспользоваться еще и таблицей элемента памяти (табл. 15).
Для заполнения функций возбуждения элементов памяти рассматривается переход из исходного состояния (12) в состояние перехода (12). За первый разряд 1 отвечает первый элемент памяти (его функция 1), за второй 2 - второй элемент памяти (его функция 2).
В таблице проставляется значение входного сигнала, который обеспечивает соответствующий переход. Количество функций возбуждения элементов памяти автомата зависит от количества разрядов вектора кода состояния и от количества информационных входов самого запоминающего элемента. Рассмотрим, например, что будет со структурным автоматом, если он находится в состоянии 01, и на его вход поступил сигнал 10.
Как видно из таблицы переходов структурный автомат перейдет в состояние 11. Этот переход складывается из двух переходов элементов памяти: 1-й из 0 в 1, 2-й из 1 в 1. По таблице 15 определим входные сигналы элемента памяти, обеспечивающие эти переходы: это 0 и 1., и т.д. В клетку соответствующего перехода запишем вектор функции возбуждения, вызывающий данный переход.
Таблица 16.
| Исходное состояние | Входной сигнал | Состояние перехода | Функции возбуждения эл-в памяти | Выходной сигнал | |||||
| a1 | a2 | z1 | z2 | a1 | a2 | 1 | 2 | w1 | w2 |
| 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | ||
| 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | ||
| 0 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | ||
| 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 |
| 1 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | ||
По таблице 16 запишем аналитические выражения канонических уравнений:
Z1 Z2
Рисунок 4- Структурная схема автомата
Не занимаясь минимизацией канонический уравнений, построим схему электрическую функциональную (рис. 5).
-
Элементы памяти
В качестве элементов памяти структурного автомата обычно используются триггеры. Как уже было сказано, с точки зрения прикладной теории цифровых автоматов, триггер - это элементарный автомат Мура, обладающий полной системой переходов и полной системой выходов.
Триггер характеризуется числом информационных входов, внутренних состояний, числом выходных сигналов и т.д. выходные сигналы триггера отождествляются с его внутренними состояниями, именно поэтому таблица переходов совпадает с таблицей выходов и триггер задается только одной из них (таблицей переходов). Как правило, триггер формирует как прямой сигнал, так и инверсный.
Рассмотрим некоторые из этапов канонического метода более подробно, с применением специальных методов.
Рисунок 5- Функциональная схема автомата
-
-
-
-
4.1 Элементы памяти с одним информационным входом
Существует только 4 типа запоминающих элементов с одним информационным входом, имеющих полную систему переходов и выходов: D-триггер, Т-триггер, 
-триггер, 
-триггер. Таблицы их переходов представлены табл. 17 - 20. соответственно, а условные графические изображения триггеров представлены на рис. 6. Входы D, T, называются информационными.
Таблицы переходов триггеров составляются только для информационных входов. Остальные входы являются вспомогательными. В частности, вход C - вход для подключения синхросерии (о чем будет сказано ниже). Каждый из триггеров имеет два выхода. Появление единичного сигнала на выходе, помеченном на рисунках символом q, означает, что триггер находится в единичном состоянии. Появление единичного сигнала на выходе 
говорит о нулевом состоянии.
а) б) в) г )
Рисунок 6- Условное графическое обозначение триггеров:
а)D-триггер; б) Т-триггер; в) D-триггер; г) T-триггер
В таблицах переходов две первые колонки одинаковые - в них перечислены все возможные комбинации входного сигнала и состояния элемента памяти. Для того, чтобы элементарный автомат имел полную систему переходов, колонку Q(t+1) следует заполнить таким образом, чтобы во второй и третьей колонках встречались все возможные типы переходов (00, 01, 10, 11). Для триггера типа D колонка Q(t+1) и D совпадают, т.к. выходной сигнал отождествляется с состоянием, то это означает, что данный элемент является элементом задержки на 1 такт. Его характеристическое уравнение имеет вид:
