2.1 Определение абстрактного цифрового автомата
Обобщённая структура системы обработки цифровой информации, приведённая на рис.1, соответствует описанию абстрактного цифрового автомата. Для целей технического проектирования в каноническую структурную систему цифрового автомата необходимо включить систему синхронизации или систему задания автоматного времени. Введение системы автоматного времени обеспечивает устойчивость работы технического устройства - цифрового автомата и дискретный характер временных процессов в нём.
С помощью импульсов синхронизации исключается возможность некорректной работы цифрового автомата во время протекания переходных процессов в элементах блока памяти и в комбинационных схемах. Цифровые автоматы, работающие под управлением системы задания дискретного автоматного времени, называются синхронизированными цифровыми автоматами. Наличие системы задания дискретного автоматного времени накладывает ограничения и на порядок изменения входных управляющих сигналов множества X. Поскольку сигналы множества X формируются в других блоках сложной информационной системы, то учёт ограничений системы задания дискретного времени приводит к практической необходимости включения в информационную систему любой сложности единой системы синхронизации.
Для абстрактного математического описания цифрового автомата как кодопреобразователя (рис.1) используется его представление как шестиэлементного множества:
S ={A, X ,Y, , , a1}, (32)
где: A = {a1, .., am, ..., aM} - множество состояний автомата (алфавит состояний); X = {z1, ..., zf, ..., zF} - множество входных сигналов автомата (входной алфавит); Y = {w1, ..., wg, ..., wG} - множество выходных сигналов (выходной алфавит);
- функция переходов абстрактного цифрового автомата, реализующая отображение множества D в A (D является подмножеством прямого произведения множеств AX, то есть D AX). Таким образом, любое состояние цифрового автомата as = (am, zf), поскольку множество AX является множеством всевозможных пар (a, z) и as A.
- функция выходов абстрактного цифрового автомата, реализующая отображение множества D в Y (D является подмножеством прямого произведения множеств AX, то есть D AX). Таким образом, любой выходной сигнал множества Y wg = (am, zf);
a1 - начальное состояние автомата (a1 A). Поведение цифрового автомата существенно зависит от начального состояния. Для однозначного управления цифровым автоматом необходимо, чтобы он начинал работу из определённого начального состояния. Цифровой автомат с установленным (выделенным) начальным состоянием a1 называется инициальным.
Автомат является конечным, если A, X и Y - не являются бесконечными множествами.
Автомат является полностью определённым, если D = D = AX. Иными словами, у полностью определённого автомата области определения функций и совпадают с множеством AX - множеством всевозможных пар (am, zf). У частичного автомата функции и определены не для всех пар (am, zf) AX.
Теоретически все элементы множеств A, X ,Y могут быть закодированы числами в системах счисления с любым основанием, но практически всегда используется двоичная система счисления (двоичный структурный алфавит).
Для двоичной системы счисления обозначим:
A = {a1, .., am, ..., aM}, X = {x1, ...,xf, ...,xF}, Y = {y1, ..., yg, ...,yG} и определим разрядность двоичных кодов состояний, входного сигнала и выходного сигнала. Количество разрядов двоичного кода всегда целое число.
Количество разрядов двоичного кода состояний
p = ]log2M[. (33)
Количество разрядов двоичного кода входных сигналов
r = ]log2F[. (34)
Количество разрядов двоичного кода выходных сигналов
d = ]log2G[. (35)
В этих формулах ]...[ - означает ближайшее большее к значению внутреннего выражения целое число.
Согласно структурной схеме рис.21 коды наборов переменных комбинационных схем определяются в результате конкатенации кодов входных сигналов и кодов состояний блока памяти. Как наборы входных переменных, так и коды состояний блока памяти содержат запрещённые комбинации и поэтому системы функций алгебры логики, описывающих комбинационные схемы, будут не полностью определёнными.
Максимально возможное количество запрещённых кодов наборов переменных комбинационных схем определится как:
В зависимости от схемы кодирования входных сигналов и состояний, среди этих запрещённых наборов могут оказаться одинаковые, и поэтому реально количество запрещённых наборов на число совпадающих кодов меньше, чем определённое по ф.(36).
Часто на практике используется две разновидности цифровых автоматов, отличающихся способом формирования выходных сигналов:
- при описании функционирования автомата выражениями:
a(t+1) = [a(t), z(t)],
w(t) = [a(t), z(t)] - он называется автоматом Мили;
- при описании функционирования автомата выражениями:
a(t+1) = [a(t), z(t)],
w(t) = [a(t)] - он называется автоматом Мура.
В этих выражениях t - текущий момент дискретного автоматного времени, t+1 - следующий момент дискретного автоматного времени.
- Глава 1 5
- Глава 2 40
- Глава 3 88
- Введение
- Глава 1 логические основы цифровых автоматов
- 1.1 Основные понятия алгебры логики
- 1.2 Базис и, или, не. Свойства элементарных функций алгебры логики
- 1.3 Способы описания булевых функций
- 1.3.1 Табличное описание булевых функций
- 1.3.2 Аналитическое описание булевых функций
- 1.3.3 Числовая форма представления булевых функций
- 1.3.4 Графическая форма представления булевых функций
- 1.3.5 Геометрическое представление булевых функций
- 1.4 Минимизация функций алгебры логики
- 1.4.1 Минимизация с помощью минимизирующих карт
- 1.4.2 Минимизация функций алгебры логики по методу Квайна
- 1.4.3 Минимизация функций алгебры логики
- 1.5 Элементная база для построения комбинационных схем
- 1.5.1 Логические элементы и, или, не
- 1.5.1.1 Логические элементы и и и-не (Позитивная логика)
- 1.5.1.2 Логические элементы или, или-не (Позитивная логика)
- 1.5.2 Примеры технической реализации булевых функций
- 1.5.2.1 Функция исключающее-или (Сложение по модулю 2)
- 1.5.2.2 Минимизированная функция алгебры логики ф.(27) (Дешифратор второго рода)
- 1.5.3 Программируемые логические матрицы (плм)
- 1.5.3.1 Примеры плм
- 1.5.3.2 Процедуры программирования плм
- Глава 2 синтез цифровых автоматов
- 2.1 Определение абстрактного цифрового автомата
- 2.2 Методы описания цифровых автоматов
- 2.3 Синхронные и асинхронные цифровые автоматы
- 2.4 Связь между математическими моделями цифровых автоматов Мили и Мура
- 2.5 Минимизация абстрактных цифровых автоматов
- 2.5.1 Минимизация абстрактного автомата Мили
- 2.5.2 Минимизация абстрактного автомата Мура
- 2.6 Структурный синтез автоматов
- 2.6.1 Элементарные автоматы памяти
- 2.6.2 Синхронизация в цифровых автоматах
- 2.7 Структурный синтез цифровых автоматов по таблицам
- 2.8 Структурный синтез цифрового автомата по графу
- Глава 3 микропрограммные автоматы
- 3.1 Декомпозиция устройств обработки цифровой информации
- 3.2 Управляющие автоматы
- 3.3 Принцип действия управляющего автомата с хранимой в памяти логикой и микропрограммное управление
- 3.3.1 Горизонтальное микропрограммирование
- 3.3.2 Вертикальное микропрограммирование
- 3.3.3 Смешанное микропрограммирование
- 3.3.3.1 Вертикально - горизонтальное микропрограммирование
- 3.3.3.2 Горизонтально - вертикальное микропрограммирование
- 3.4 Управляющие автоматы с «жёсткой логикой»
- 3.5 Граф - схемы микропрограммных автоматов
- 3.6 Синтез микропрограммных автоматов по граф - схеме алгоритма
- 3.6.1 Синтез микропрограммного автомата Мили
- 3.6.2 Синтез микропрограммного автомата Мура
- 3.6.3 Минимизация микропрограммных автоматов
- Заключение