Что такое цифровой автомат

Цифровой автомат

Понятие

К цифровому автомату можно отнести как реальное физическое устройство, так и абстрактную систему. Физические устройства, представляющие собой ЦА, содержат память, которая состоит из запоминающих устройств (триггеров, элементов задержки и других), фиксирующих состояние, в котором он находится. Абстрактная система представляет собой математическую модель дискретного управляющего устройства.

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

Структурная схема содержит запоминающие элементы и комбинационные схемы.

На входы комбинационных схем поступают сигналы со входа автомата, а также состояния запоминающих элементов, определяющие состояние автомата, по цепям прямой и обратной связей.

Комбинационная схема, аргументами для которой служат буквы входного слова и состояния запоминающих элементов (состояние автомата), вырабатывает выходное слово. Выходные сигналы переводят автомат (его запоминающие элементы) в новое состояние. Аргументами для этой схемы служат буквы входного слова и состояния запоминающих элементов.

Способы описания

Наиболее распространёнными способами описания цифрового автомата являются табличный, графический и аналитический.

Графический способ

Самым наглядным способом является графическое представление автомата – ориентированный связный граф, вершины которого соответствуют состояниям, а дуги – переходами между ними (петля соответствует переходу в то же самое состояние). Стрелки на дугах ставятся в направлении от исходного состояния к конечному, над дугой приписывается значения сигналов входа и выхода (как вариант – над стрелкой пишут дробное значение, числитель в котором обозначает входной сигнал, под действием которого будет происходить переход, а знаменатель – текущее значение выходного сигнала).

Табличный способ

В табличном способе используются две таблицы для задания автомата: таблица переходов и таблица выходов. Часто эти таблицы совмещаются в отмеченную таблицу переходов автомата.

При построении таблицы переходов строки таблицы помечаются входным алфавитом, столбцы – состояниями. При пересечении строки и столбца в ячейку записывается состояние, к которому переходит автомат из начального состояния (столбец таблицы) под воздействием сигнала (строка таблицы).

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

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

Ещё одним табличным способом описания цифрового автомата является матрица соединений, строки и столбцы которой помечаются как состояния автомата, а клеткам соответствуют входной сигнал, под воздействием которого осуществляется переход (в скобках рядом с состоянием указывается выходной сигнал).

Аналитический способ

При аналитическом способе задания для каждого состояния автомата указываются отображения, представляющее собой множество всех троек, первый параметр которых – входной сигнал, второй – выходное состояние, третий – выходной сигнал, который выдаёт автомат при переходе из одного состояния в другое.

Источник

Оптимизация цифрового автомата (FSM)

Данный материал представляет краткое описание проблемы в теории цифровых автоматов и объясняет один из способов решения данной проблемы, который был найден при попытке автоматизации процесса построения цифрововых автоматов.

Введение

Автомат – система механизмов, устройств, в которой полностью автоматизированы процессы получения, преобразования, передачи энергии, материалов, информации.

Термин > в основном используется в двух аспектах:

При математическом подходе под автоматом понимается математическая модель, у которой должны быть входы, внутренние состояния и выходы. Детали структуры устройства не учитываюся и не рассматриваются.

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

С точки зрения сигналов цифровой автомат (ЦА) – система, которая может принимать входные сигналы, под их воздействием переходить из одного состояния в другое, сохранять его до прихода следующего входного сигнала, выдавать выходные сигналы.

В данной работе рассматриваются цифровые сигналы и двоичная логика на базе логических элементов.

Структурно-функциональная схема цифрового конечного автомата

Применение

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

Другое важнейшее применение теории автоматов — математически строгое нахождение разрешимости и сложности задач.

Автоматы Мура и Мили широко применяются при проектировании цифровых устройств на основе программируемых логических интегральных схем (ПЛИС). Наличие минимальной выходной задержки, связанной с переключением выходного регистра, отсутствие нестабильности переходного процесса на выходе автомата, отсутствие сквозного распространения сигнала через комбинационную схему от входа до выхода автомата, простота описания на языках описания аппаратуры делает автомат Мура практически незаменимым. Также автоматы Мура и взаимодействующие автоматы Мили используются в генетическом программировании.

Описание проблемы

1) Очень часто разработка ЦА начинается с реализации графа, который отражает закладываемую логику в простом и понятном для человека виде.

3) Определение разрядности памяти. Минимальное число триггеров можно вычислить по формуле:

4) Присвоение состояниям кодов. Алгоритма для правильного задания кодов для состояний нет. Именно от этого зависит сложность уравнений, которые мы получим для входов триггеров и количество элементов необходимых для сборки схемы.

5) Составление таблицы состояний-переходов.

6) Составление булевых арифметических уравнений для входов триггеров. Карты Карно составляются по таблице состояний-переходов, уравнения минимизируются.

7) Преобразование уравнений для согласования с элементной базой.

8) Разработка электрической схемы.

Решение

Была разработана программа для построения цифровых автоматов. На вход программа принимает граф. В программе граф представляется в наборе вершин и рёбер(вершина, входной сигнал, вершина для перехода). Итерируясь по рёбрам составляются таблицы истинности для каждого разряда в СКНФ и СДНФ. Методом Куайна-Мак-Класки минимизируются обе формы уравнений. Для каждого разряда выбирается выражение с минимальным количеством логических операций >, >. Общее количество этих операций является критерием качества данной кодировки.

Количество возможных вариантов задания состояний можно рассчитать зная разрядность памяти(M) и количество состояний(S).

Количество вариантов выборки(V) нужного количества состояний(S) из всего количества кодов(C), формула из комбинаторики:

Количество возможных вариантов задания состояний(A) равно:

Если перебирать все варианты и потом отобрать лучший, то в зависимости от графа программа может исполняться слишком долго. Такой вариант подойдёт для автоматов с небольшим числом вариантов задания кодов состояний.

Для автоматов с большим числом возможных вариантов задания состояний был разработан генетический алгоритм перебора вариантов состояний.

Схема генетического алгоритма

Результаты

Для исследования был спроектирован автомат с числом возможных вариантов задания состояний равным 6720. Для каждого варианта было рассчитано количество необходимых элементов для реализации.

Данный ЦА описывает поведение пчелы (для простоты восприятия), входной сигнал представляет 0(всё спокойно) или 1(пчела видит шершня).

Граф цифрового автомата, описывающий поведение пчелы

Количество состояний: 5

Разрядность памяти: ceil(log2(5)) = 3

Разрядность входного сигнала: 1

Пример расчёта числа всех возможных вариантов построения автомата:

Источник

ОСНОВНЫЕ ПОЛОЖЕНИЯ

Цифровой автомат (ЦА) – это условная, формальная модель любого информационного устройства дискретного действия. Модель предназначена для представления устройства на логическом уровне, т.е. в ней не допускается использование каких-либо физических характеристик процессов, происходящих при работе реального устройства.

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

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

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

Итак, подытоживая сказанное, мы определили ЦА как условную, упрощенную модель технического устройства, имеющую ограниченное дискретное множество состояний.

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

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

Работа ЦА протекает во времени, но это особенное, автоматное время, представляющее смену последовательных дискретных моментов t = 0, 1, 2, 3. ЦА всегда начинает свою работу с момента t = 0, а время окончания может быть не определенным или бесконечным.

Теорию автоматов принято делить на две основные части: абстрактную и структурную.

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

Рис. 1.1. Схема абстрактного автомата

Буква х изображает совокупность всех одновременно подаваемых на входы устройства сигналов. Фактически это должно означать некоторую комбинацию значений двоичных переменных, поступающих по разным линиям связи, но для абстрактной теории это не имеет значения. Теория ограничивается определением множества

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

Выход У автомата определяется аналогично. Все выходные буквы принадлежат выходному алфавиту

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

Каждая буква а означает одно определенное состояние ЦА. Все эти буквы в совокупности образуют внутренний алфавит или алфавит состояний.

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

Структурная теория ЦА представляет автомат в виде логической сети с явно выраженными функциональными элементами, элементами памяти и линиями связи (микроподход). Представление об этом дает рис. 1.2.

Рис. 1.2. Структурная схема цифрового автомата

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

Аналогично определяются выходной вектор и вектор внутренних состояний, число компонент которого равно числу элементов памяти в схеме ЦА.

Ясно, что между буквами абстрактных алфавитов X, Y и А с одной стороны и буквами структурных алфавитов U, Z и Q – с другой должно существовать взаимно-однозначное отображение. И все же это – разные алфавиты. Переход от абстрактного алфавита к структурному называется кодированием автоматных алфавитов и представляет одну из важных задач структурной теории.

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

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

Рассмотрим некоторые вопросы классификации автоматов. Все ЦА можно разделить на два основные класса: автоматы без памяти, или примитивные автоматы, и автоматы с памятью.

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

В структурном алфавите для автомата, имеющего несколько выходов, можно написать

,

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

Типичными автоматами без памяти являются цифровые комбинационные элементы (КЭ): сумматоры, дешифраторы, схемы сравнения, мультиплексоры и т.п. При описании таких КЭ используется структурный по своему смыслу алфавит, но обозначения (например, входная переменная х) могут совпадать с принятыми в литературе буквами абстрактных алфавитов. Применительно к автоматам без памяти это допустимо, ввиду простоты их функций, и не приводит к неправильному пониманию. При описании автоматов с памятью придется более строго различать обозначения переменных на абстрактном и структурном уровнях.

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

Цифровой автомат считается конечным, если конечны множества входных сигналов X, состояний S и выходных сигналов Y, то есть это автомат с ограниченной памятью состояний. Конечный автомат, в каждом состоянии которого существует функция перехода для всех возможных входных символов, называется полностью определенным конечным автоматом.

Работа ЦА осуществляется в автоматном времени, определяемом числом периодов поступления входных сигналов.

Любой цифровой автомат состоит из двух частей: комбинационной логической схемы (КС) и памяти (П). С учетом этого ЦА может быть изображен так, как показано на рис. 1.4. В данном случае в некоторой степени раскрыта структура автомата. КС автомата формирует выходные сигналы, сигналы перевода триггеров блока памяти в новые состояния. Наличие блока памяти позволяет помнить предысторию работы автомата под воздействием входных сигналов.

Рис. 1.3. Общее изображение Рис. 1.4. Структурное изображение

Источник

Понятие о цифровом автомате

МАТЕМАТИЧЕСКИЕ ОСНОВЫ ТЕОРИИ ЦИФРОВЫХ АВТОМАТОВ

Общие сведения о цифровых автоматах

Понятие о цифровом автомате

Зависимость между выходными и входными сигналами в цифровом автомате реализуется с помощью соединения элементов, которые принято называть логическими.

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

Вторично изменить свое состояние или вернуться в исходное эти элементы могут после воздействия других входных сигналов или повторного воздействия тех же входных сигналов или сигналов ими порождаемых. Такие элементы принято называть элементами памяти (ЭП) цифрового автомата. Типичными представителями элементов памяти являются широко применяемые на практике тригерные устройства различных типов.

Наличие в цифровом автомате элементов памяти значительно расширяет возможности преобразования информации, при этом могут запоминаться значения входных сигналов, поступающих в предыдущие моменты времени, и использоваться при формировании выходных сигналов.

При решении задач анализа и синтеза цифровых автоматов элементы памяти принято выделять в отдельный блок, который называется блоком памяти или просто памятью цифрового автомата (рис.1.1,б). Часть схемы автомата, не содержащая элементов памяти, называется логическим преобразователем или комбинационным блоком автомата. ЦА, представленный на рис. 1.1,б, получил название канонического автомата или автомата с канонической структурой.

Выходы логического преобразователя непосредственно соединяются с соответствующими входами блока памяти автомата. Поэтому множество u нередко называют множеством входов управления памятью автомата. В общем случае l k, так как каждый элемент памяти автомата может иметь один или несколько управляющих входов. Так, при построении памяти автомата на RS-триггерах мощность множества u в два раза превышает мощность множества Y, т.е. l=2k. Ввиду простоты технической реализации в настоящее время наибольшее распространение получили цифровые автоматы, сигналы в которых принимают только два возможных значения. При математическом описании таких сигналов, независимо от физической природы, их значения отождествляют с цифрами 0 и 1. В дальнейшем изложении будем рассматривать автоматы, работающие только с двоичными сигналами.

Если каждому входному сигналу автомата присвоить конкретное значение на множестве <0,1>, то полученная совокупность значений входных сигналов будет представлять собой комбинацию значений входных сигналов или входной набор цифрового автомата. В общем виде входной набор цифрового автомата запишется следующим выражением:

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

,

где .

Выходной набор цифрового автомата будем записывать в виде

Совокупность выходных наборов образует множество выходных наборов автомата:

,

где — мощность множества выходных наборов цифрового автомата.

и множество состояний памяти цифрового автомата:

,

где

Цифровые автоматы в зависимости от количества состояний памяти делятся на автоматы с одним внутренним состоянием, у которых элементы памяти отсутствуют, и автоматы с двумя и более внутренними состояниями, содержащие один и более элементов памяти.

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

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

,

которая обозначает, что состояние цифрового автомата a_p характеризуется входным набором и состоянием памяти s_j.

Совокупность состояний a_p образует множество состояний автомата

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

N_сост =

Полученное число определяет максимальную мощность множества А и, следовательно, для реальных автоматов . Число состояний µ быстро возрастает с увеличением сложности автомата, числа входов и элементов памяти.

Источник