Структурный синтез конечных автоматов

Под цифровым конечным автоматом понимают дискретный преобразо­ватель информации, состоящий из комбинационной схемы и элементов памяти. Комбинационная схема строится из логических элементов, па­мять - из элементарных автоматов, а именно синхронных триггеров различных типов.

Работа подобных цифровых устройств описывается набором входных сигналов Z = {Z₁, Z_{2, …,} Z_p}, набором выходных сигналов W= { W_1, Z_2, …, Z_s }, множеством внутренних состояний (выходных сигна­лов элементов памяти) А = {a₁, a_2, …, a_k}, двумя характеристи­ческими функциями: функцией переходов δ и функцией выходов, λ, а также начальным состоянием автомата a₁ ∈ A.

Различают два типа автоматов: автоматы Мили и Мура. Для каж­дого из них внутреннее состояние в последующем такте полностью оп­ределяется входным сигналом и внутренним состоянием в данном так­те, что отражается в записи функций переходов

а(t+1) = δ [z(t), a(t)],

где t - автоматное время.

Отличаются автоматы Мили и Мура лишь записью функции выходов. Если в автомате Мили выходной сигнал зависит как от внутреннего состояния автомата, так и от входного сигнала в том же такте

W(t) = λ [z(t), a(t)],

Забиваем Сайты В ТОП КУВАЛДОЙ - Уникальные возможности от SeoHammer

Каждая ссылка анализируется по трем пакетам оценки: SEO, Трафик и SMM. SeoHammer делает продвижение сайта прозрачным и простым занятием. Ссылки, вечные ссылки, статьи, упоминания, пресс-релизы - используйте по максимуму потенциал SeoHammer для продвижения вашего сайта.

Что умеет делать SeoHammer

— Продвижение в один клик, интеллектуальный подбор запросов, покупка самых лучших ссылок с высокой степенью качества у лучших бирж ссылок.
— Регулярная проверка качества ссылок по более чем 100 показателям и ежедневный пересчет показателей качества проекта.
— Все известные форматы ссылок: арендные ссылки, вечные ссылки, публикации (упоминания, мнения, отзывы, статьи, пресс-релизы).
— SeoHammer покажет, где рост или падение, а также запросы, на которые нужно обратить внимание.

SeoHammer еще предоставляет технологию Буст, она ускоряет продвижение в десятки раз, а первые результаты появляются уже в течение первых 7 дней.

Зарегистрироваться и Начать продвижение

то в автомате Мура выходной сигнал определяется только внутренним состоянием в данном такте

W(t) = λ [a(t)],

В частном случае возможно и W(t) = а(t), т.е. выходной сигнал авто­мата одновременно является выходным сигналом памяти.

Практически указанное отличие проявляется в том, что при смене входного сигнала в пределах такта в автомате Мили изменяется сос­тояние выхода, а в автомате Мура - сохраняется неизменным, так как изменение состояния элементов памяти происходит только в момент действия импульсов синхронизации.

Каждое состояние входа и выхода любого автомата однозначно за­дается комбинацией двоичных сигналов на соответствующих n-разряд­ных шинах, поэтому условимся каждое отдельное состояние кодировать набором двоичных символов (битов):

Z_i ~ х(t) ={ x₁, x₂. x_n} - входной сигнал;

W_i ~ y(t) ={ y₁, y₂. y_m} - выходной сигнал;

a_i ~ Q(t) ={ Q₁, Q₂. Q_r} - сигнал внутреннего состояния (состояния триггеров памяти);

U(t) ={ u₁, u₂... u_k} - входной сигнал памяти.

В такой записи символическим обозначениям Z_i, W_i и a_i соот­ветствуют двоичные кодовые комбинации х(t), у(t) и Q(t), где х_j, y_j, Q_j, и u_j - отдельные биты кода, каждый из которых передается по своей информационной шине. Структурные схемы автоматов Мили и Мура показаны на рис. 4 и 5. Исходными данными для их синтеза являются таблицы переходов и выходов.

Рисунок 4. Структурная схема КА Мили

Рисунок 5. Структурная схема КА Мура

Структурный синтез КА Мили предполагает выполнение ряда эта­пов.

1. Выбирают систему логических элементов и элементов памяти, на которых будет строиться КА.

Сервис онлайн-записи на собственном Telegram-боте

Попробуйте сервис онлайн-записи VisitTime на основе вашего собственного Telegram-бота:
— Разгрузит мастера, специалиста или компанию;
— Позволит гибко управлять расписанием и загрузкой;
— Разошлет оповещения о новых услугах или акциях;
— Позволит принять оплату на карту/кошелек/счет;
— Позволит записываться на групповые и персональные посещения;
— Поможет получить от клиента отзывы о визите к вам;
— Включает в себя сервис чаевых.

Для новых пользователей первый месяц бесплатно.

Зарегистрироваться в сервисе

2. Определяют недостающие входные данные:

- число элементов памяти r ≥ log ₂ k

- число разрядов входной шины n ≥ log ₂ p

- число разрядов выходной шины m≥ log ₂ s,

где k, p, s - количество внутренних состояний, входных Z_i и выход­ных W_i сигналов соответственно. Числа r, п, т - целые.

3. Кодируют автомат. Это означает, что каждому входному и вы­ходному сигналу и внутреннему состоянию ставят в соответст­вие определенный двоичный код.

4. Переводят исходные таблицы выходов и переходов из символи­ческого алфавита в двоичный.

5. По таблице выходов составляют систему логических уравнений, связывающих выходные, сигналы КА у_j с внутренними состояниями и входными сигналами х_j. Общий вид такого уравнения

У_j = f_j (x₁, x₂, …, x_n, Q₁, Q₂, …, Q_r).

6. По таблице переходов составляют таблицу возбуждения памяти, т.е. двоичных сигналов, которые следует подавать на входы тригге­ров памяти для перевода их в требуемые состояния. Словари перехо­дов наиболее часто применяемых триггеров приведены в таблице 3.

Таблица 3 - Словари переходов триггеров

Для синтезируемого КА с помощью словаря следует преобразо­вать его таблицу переходов в таблицу возбуждения памяти (процесс преобразования поясняется ниже на конкретном примере).

7. По таблице возбуждения памяти составляют систему логичес­ких уравнений, связывающих входные сигналы памяти U_j с внутренними состояниями Q_j и входными сигналами х_j:

U_j = φ _j (x₁, x₂, …, x_n, Q₁, Q₂… Q_r).

8. Все уравнения, полученные в пп.5 и 7, минимизируют при помощи карт Карно.

9. По минимальным формам составляют полную логическую схему КА на микросхемах заданной серии.