Синтез цифрового автомата

Теория автоматов

Теория автоматов тесно связана с теорией формального языка. В данном контексте автоматы используются в качестве конечных представлений формальных языков, которые могут быть бесконечными. Во многих случаях автоматы классифицируются по классу формальных языков, которые они способны распознавать, в том числе, как в иерархии Хомского, описывающая отношения вложенности между основными классами автоматов. Автоматы используются в теории вычислений, искусственном интеллекте, конструировании компиляторов, формальной верификации и синтаксическом анализе.

Цифровые автоматы

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

1. Множество возможных входных сигналов.
2. Множество возможных выходных сигналов.
3. Множество возможных внутренних состояний автомата.

Синтез цифрового автомата

С точки зрения синтеза цифровой автомат удобно представлять в виде структурной схемы, пример которой изображен на рисунке ниже.

Рисунок 1. Структурная схема цифрового автомата. Автор24 — интернет-биржа студенческих работ

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

1. Кодирование входных сигналов в виде набора логических переменных.
2. Кодирование выходных сигналов в виде набора логических функций.
3. Кодирование состояний цифрового автомата.
4. Формирование кодированной таблицы переходов.
5. Выбор типа запоминающего устройства.
6. Составление логических выражений для логических функций, которые были использованы для кодирования выходных сигналов.
7. Составление логических выражений для сигналов управления памятью.
8. Синтез логических схем для сформированных логических выражений.
9. Формирование выходных сигналов цифрового автомата на основании их кодирующих функций.