- •И. В. Потапов элементы прикладной теории цифровых автоматов
- •Оглавление
- •Введение
- •1. Представление чисел в эвм
- •1.1. Позиционные системы счисления
- •1.2. Обоснование применения в эвм двоичной системы счисления
- •1.3. Представление двоичных чисел с фиксированной и плавающей запятой
- •1.4. Прямой и инверсные коды чисел
- •1.5. Двоично-десятичные коды чисел
- •Вопросы для самоконтроля
- •2. Арифметические операции в двоичных кодах
- •2.1. Сложение двоичных кодов
- •2.2. Вычитание двоичных кодов
- •2.3. Выполнение операции округления чисел
- •2.3.1. Округление прямых кодов
- •2.3.2. Округление инверсных кодов
- •2.4. Умножение двоичных кодов
- •2.4.1. Умножение прямых кодов чисел
- •2.4.2. Ускоренное выполнение операции умножения
- •2.4.3. Умножение инверсных кодов чисел
- •2.5. Деление двоичных кодов
- •2.5.1. Деление прямых кодов чисел
- •2.5.2. Ускоренное выполнение операции деления
- •2.5.3. Деление дополнительных кодов чисел
- •2.6. Извлечение квадратного корня
- •2.7. Выполнение арифметических операций в d-кодах
- •2.7.1. Сложение в d-кодах
- •2.7.2. Умножение в d-кодах
- •2.7.3. Деление в d-кодах
- •Вопросы для самоконтроля
- •3. Переключательные функции
- •3.1. Основные определения и способы задания пф
- •3.2. Элементарные логические функции
- •3.3. Основные законы алгебры логики
- •3.4. Полные системы переключательных функций
- •3.5. Канонические формы аналитического представления пф
- •3.6. Кубическое представление пф
- •3.7. Синтез комбинационных схем
- •3.7.1. Синтез кс на логических элементах
- •3.7.2. Синтез кс на дешифраторах
- •3.7.3. Синтез кс на мультиплексорах
- •3.7.4. Синтез многовыходных схем
- •3.8. Риски сбоя в комбинационных схемах
- •Вопросы для самоконтроля
- •4. Минимизация переключательных функций
- •4.1. Минимизация пф с помощью карт Карно
- •4.2. Минимизация пф методом Квайна
- •4.3. Минимизация методом Квайна – Мак-Класки
- •4.4. Минимизация пф методом Блейка – Порецкого
- •4.5. Минимизация пф, заданных в конъюнктивной форме
- •4.6. Минимизация не полностью определенных пф
- •4.7. Минимизация систем пф
- •4.8. Минимизация пф в универсальных базисах и-не, или-не
- •Вопросы для самоконтроля
- •5. Моделирование работы и синтез автоматов с памятью
- •5.1. Основные модели, понятия и определения
- •5.1.1. Общее понятие цифрового автомата с памятью
- •5.1.2. Основные модели цифровых автоматов
- •5.1.3. Описание функционирования цифровых автоматов
- •5.1.4. Задание цифровых автоматов
- •5.1.5. Правила перехода между моделями Мили и Мура
- •5.2. Минимизация числа состояний цифровых автоматов
- •5.2.1. Минимизация числа состояний синхронного автомата методом Полла-Ангера
- •5.2.2. Минимизация числа состояний автомата Мура методом l-эквивалентных разбиений
- •5.2.3. Минимизация числа состояний автомата Мили методом l-эквивалентных разбиений
- •5.3. Структурный синтез цифровых автоматов
- •5.3.1. Типы элементарных автоматов, обладающие полной системой переходов-выходов
- •5.3.2. Основные этапы структурного синтеза
- •5.4. Рациональный выбор варианта кодирования состояний синхронных автоматов
- •Вопросы для самоконтроля
- •Библиографический список
- •Задания для выполнения самостоятельных работ
- •Илья Викторович потапов, канд. Техн. Наук, доцент элементы прикладной теории цифровых автоматов
5.2. Минимизация числа состояний цифровых автоматов
В общем случае таблица переходов ЦА, полученная тем или иным способом, может содержать избыточное число состояний. Поскольку от количества состояний абстрактного автомата зависит число элементов памяти, используемых при структурном синтезе ЦА, ставится задача сокращения избыточных состояний ЦА. При этом процесс минимизации числа состояний заключается в исключении некоторых состояний абстрактного автомата, а также в замене ряда состояний одним таким образом, чтобы получившийся в результате автомат был эквивалентен исходному, т.е. на одинаковую последовательность входных сигналов оба автомата (исходный и минимизированный, находящиеся в начальном состоянии) должны отвечать одинаковыми последовательностями выходных сигналов.
Рассмотрим приемы, позволяющие проводить предварительное сокращение числа состояний.
Во-первых, из таблицы переходов можно удалить все недостижимые состояния, т.е. такие, в которые автомат не сможет попасть из начального состояния под воздействием любой последовательности входных сигналов.
Во-вторых, из таблицы переходов автомата Мили можно исключить все состояния, которым соответствуют столбцы таблицы переходов, содержащие в своих ячейках только прочерки, т.е. неопределенные состояния перехода. При этом все вхождения исключенных по данному правилу состояний в упрощенной таблице переходов заменяются прочерками.
В-третьих, из таблицы переходов автомата Мура могут быть исключены все столбцы, соответствующие состояниям, отмеченным неопределенными выходными сигналами. Вхождения исключенных состояний в упрощенную таблицу переходов заменяются прочерками.
Кроме того, каждая группа состояний, которой соответствуют одинаковые столбцы таблицы переходов, может быть заменена одним из состояний группы, при этом все вхождения исключенных состояний в таблице переходов заменяются на состояние, номер которого представляет группу одинаковых столбцов.
Рассмотрим пример. Сформируем упрощенную таблицу переходов автомата, заданного табл. 5.8.
Таблица 5.8
x\а |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
х1 |
1,0 |
5,1 |
1,0 |
–,1 |
4,1 |
7,0 |
5,1 |
x2 |
2,1 |
3,0 |
2,1 |
6,1 |
5,0 |
–,1 |
3,0 |
В этой таблице одинаковые столбцы соответствуют состояниям (1, 3) и (2, 7). Введем обозначения: группа состояний (1, 3) – 1, группа (2, 7) – 2.
Тогда столбцы табл. 5.8, соответствующие состояниям 3 и 7, можно исключить, а все вхождения этих состояний заменить состояниями 1 и 2 соответственно. В результате получим упрощенную таблицу переходов (табл. 5.9).
Таблица 5.9
x\а |
1 |
2 |
4 |
5 |
6 |
х1 |
1,0 |
5,1 |
–,1 |
4,1 |
2,0 |
x2 |
2,1 |
1,0 |
6,1 |
5,0 |
–,1 |