Построение кодопреобразователя (стр. 5 из 8)
У полностью определённых автоматов класс конечной совместимости не пересекаются, поэтому нормализованный автомат является единственным и процесс минимизации этим заканчивается. В случае получения частичного автомата классы i-совместимости пересекаются. Это приводит к тому, что нормализованный автомат может описываться конечным количеством вариантов таблиц или графов. В случае частичных автоматов часто отказываются от достижения абсолютной минимизации и ограничиваются нахождением нормализованного автомата и его эвристическим доопределением.
Таблица состояний и выходов нормализованного автомата
| Вх/сост | G1 | G2 | G3 | G4 | G5 | G6 | G7 | G8 | G9 | G10 | G11 | G12 | G13 |
| 0 | G2/0 | G3/0 | G4/0 | G5/0 | G10/0 | G11/0 | G12/0 | G13/0 | G16/0 | G17/0 | G18/0 | G20/0 | G21/0 |
| 1 | G6/0 | G7/0 | G8/0 | G9/0 | -/- | G14/0 | -/- | G15/0 | -/- | -/- | -/- | G19/0 | -/- |
| Вх/сост | G14 | G15 | G16 | G17 | G18 | G19 | G20 | G21 | G23 | G24 | G25 | G26 | |
| 0 | G23/0 | G26/0 | G22/0 | G1/0 | G13/0 | G16/0 | G10/1 | G17/1 | G25/1 | G26/1 | G21/0 | G22/1 | |
| 1 | -/- | -/- | -/- | -/- | G15/1 | -/- | -/- | -/- | G24/1 | -/- | -/- | -/- |
В результате всех преобразований мы получили нормализованный минимизированный автомат, по которому построим граф автомата Мили:
Структурный синтез цифрового автомата
Структурный синтез цифрового автомата - это кодирование его входных и переменных и состояний автомата и получение функции возбуждения и функций выходов триггера.
Задачей этапа структурного синтеза является построение принципиальной схемы автомата из элементарных автоматов заданного типа. Элементарные автоматы подразделяются на два больших класса:
- элементарные автоматы памяти (запоминающие элементы);
- элементарные автоматы без памяти (элементарные комбинационные схемы или логические элементы).
Задача синтеза цифрового автомата имеет решение в том случае, если система элементарных автоматов является структурно полной.
Всякая система элементарных автоматов, содержащая элементарный автомат, Мура (триггер) и какую-нибудь функционально полную систему логических элементов является структурно полной системой.
Если автомат имеет М состояний, то для двоичного структурного алфавита количество триггеров в блоке памяти этого автомата
n=]log2M[ (1)
где ]...[- ближайшее большее целое число.
Если в каждую клетку таблицы переходов и выходов записать двоичный код, соответствующий размещённым там состояниям или выходным сигналам цифрового автомата, то таким образом получаются кодированные таблицы переходов и выходов.
Кодированная таблица выходов является табличным описанием системы булевых функций, реализуемых схемой КСВЫХ. Кодированная таблица переходов только после переработки с использованием матрицы переходов для заданного типа триггеров будет называться кодированной таблицей возбуждений и соответствовать описанию комбинационной схемы КСВХ.
Таким образом, задача синтеза состоит в определении по таблицам функций выхода и функций возбуждения триггеров заданного типа в блоке памяти, минимизации их для выбранной элементной базы и схемной реализации в функционально полном базисе элементов.
Выбор триггера
Комбинационная схема с обратными связями, имеющая два устойчивых состояния и предназначенная для хранения одного бита информации, называется элементарным автоматом или триггером.
Для синтеза цифровых автоматов триггеры рассматриваются как элементы систем, и важным является изучение его поведения в системе, а не внутренняя структура или принципиальная схема. В этом состоит системотехнический подход к изучению триггеров различных типов.
Триггер типа RS. Название триггера происходит от английских слов set и reset, он имеет два входа - S для установки триггера в единицу и R для установки его в ноль. Как правило, он имеет два выхода: прямой и инверсный. Если для перевода триггера из одного состояния в другое на установочные входы необходимо подавать не логические единица, а нули, то такой триггер называется триггером с инверсным управлением.
Рис. 2. Триггеры типа RS с прямым (а) и инверсным (б) управлением
Триггер типа JK. Триггер типа JK работает также как и триггер RS, с той лишь разницей, что допустима одновременная подача сигналов J=K=1, которая изменяет его состояние на обратное. Вход K эквивалентен входу R, а вход J - входу S.
Триггер типа D. Название триггера происходит от английского слова «задержка» (delay). Триггер имеет один вход. На выходе он должен повторять сигнал, существовавший на своем входе в предыдущий такт: D-триггеры всегда выпускаются синхронными, так как асинхронный триггер работает просто как повторитель входных сигналов.
Рис. 3. Условные обозначения JK и Dтриггера.
Триггер типа T. триггеры этого типа выпускаются промышленностью как самостоятельные устройства. Они могут быть собраны из триггеров других типов как на рис. 4. логическая единица, приложенная к T-входу триггера, меняет его состояние на обратное.
Рис. 4. Счетные триггеры
Триггер типа RST. Это счетный триггер с двумя установочными входами. Многовходовый триггер в цифровом автомате позволяет упростить его структуру.
Для решения нашей задачи выберем D-триггер, который имеет всего один вход (D) и на выходе он повторяет сигнал на входе D, существовавший в предыдущем такте автоматного времени.
Поскольку в пределах периода синхроимпульсов входной сигнал появляется в произвольный момент времени, то на выход входной сигнал проходит с произвольной задержкой, не превышающей длительность периода синхросигнала.
Представление функции возбуждения
По формуле (1) рассчитаем необходимое количество разрядов для кодирования: N = ]log223[ = 5 разрядов.
Если в каждую клетку таблицы переходов и выходов записать двоичный код, соответствующий размещённым там состояниям или выходным сигналам цифрового автомата, то таким образом получаются кодированные таблицы переходов и выходов.
Кодированная таблица выходов является табличным описанием системы булевых функций, реализуемых схемой КСвых. Кодированная таблица переходов только после переработки с использованием матрицы переходов для заданного типа триггеров будет называться кодированной таблицей возбуждений и соответствовать описанию комбинационной схемы КСВХ. Очевидно, что при кодировании переходов и выходов можно придерживаться двух принципов описания булевых функций. Если желательно получить табличное описание функций выходов с наименьшим количеством единичных значений, то для кодирования часто встречающихся в таблице выходов сигналов следует использовать коды с максимально возможным количеством нулей в коде, а для кодирования следующих по количеству ссылок в таблице выходов сигналов использовать коды с увеличивающимся количеством единиц в кодовых комбинациях. Для кодирования состояний блока памяти на D триггерах также можно использовать этот принцип кодирования, поскольку таблица возбуждений для них совпадает с таблицей переходов. Рекомендовать этот принцип для, всеобщего применения при синтезе автоматов нельзя, так как при минимизации булевых функций возможно получение более простых результирующих форм представления функций, имеющих более сложную запись в СДНФ (Нормальная дизьюктивная форма - это набор переменных без общих отрицаний и скобок. Совершенная НДФ - это когда все наборы переменных имею одинаковую длину. СДНФ - это набор конъюнкций переменных одинаковой длины). Этот принцип можно использовать только в том случае, если ФАЛ выходов и ФАЛ возбуждений для D триггеров не подлежат минимизации, поскольку реализуются на мультиплексорах, дешифраторах или постоянных запоминающих устройствах.