Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

1. Основные понятия алгебры логики

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

Для формального описания цифровых автоматов применяется аппарат алгебры логики, созданной английским математиком Джорджем Булем (1815-1864). Поэтому алгебру логики называют алгеброй Буля или булевой алгеброй.

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

Логическая (булева) переменная - такая величина x, которая может принимать только два значения: x = {0,1} (ложное или истинное высказывание).

Логическая функция (функция алгебры логики - ФАЛ) - функция многих аргументов f(x_n-1, x_n-2,…, x₀), принимающая значения равные нулю или единице на наборах логических переменных x_n-1, x_n-2,…, x₀.

В дальнейшем в формальных описаниях наборов переменных и логических функций сами наборы переменных интерпретируются как двоичные коды (числа). В двоичных кодах расположение логических переменных упорядочено в порядке уменьшения индекса слева направо и каждая логическая переменная имеет вес в зависимости от позиции в коде, увеличивающийся справа налево. Вес каждой i - той логической переменной, являющейся значением разряда двоичного числа равен 2ⁱ (i = 0,…, n-1).

Для n - разрядного кода общее количество уникальных наборов переменных

N = 2ⁿ;

Максимальное числовое значение двоичного кода равно

A_макс = 2ⁿ-1;

Значения всех логических функций от одной переменной представлены в таблице 1.

Функция f₀(x) называется константой нуля, а функция f₃(x) - константой единицы. Функция f₁(x), повторяющая значения логической переменной, - тождественная функция (f₁(x) x), а функция f₂(x), принимающая значения, обратные значениям переменной x, - логическое отрицание или инверсия (НЕ) (f₂(x) = ).

Над элементами алгебры логики можно выполнять следующие операции:

Конъюнкция (И, логическое умножение) - произведение двух высказываний Р и Q, результатом которого является истина если оба высказывания истинны и ложное во всех других случаях;

Дизъюнкция (ИЛИ, логическая сумма) - сумма двух высказываний Р и Q, называется высказывание ложное если оба высказывания ложные и истинное во всех других случаях;

Инверсия (отрицание) - отрицание высказывания Р называется высказывание истинное, когда само высказывание Р ложное или наоборот.

1.2 Составление таблицы соответствия

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

При рассмотрении конечного автомата необходимо рассмотреть условие автоматности-то есть, должны выполняться два условия:

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

2. минимум три первых символа входных и выходных слов должны соответствовать друг другу. В нашем случае это условие частично не выполняется, поэтому для соблюдения условия автоматности кодопреобразователя, к входному и выходному словам добавляем пустые символы (0).

При этом таблица соответствия примет следующий вид:

После того как условие автоматности для проектируемого автомата выполнено, переходим к следующему этапу - построение граф-дерева для абстрактного автомата Мура.

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

- при описании функционирования автомата выражениями:

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

w(t) = [a(t), z(t)] - он называется автоматом Мили;

- при описании функционирования автомата выражениями:

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

w(t) = [a(t)] - он называется автоматом Мура.

В этих выражениях t - текущий момент дискретного автоматного времени, t+1 - следующий момент дискретного автоматного времени.

2. Основные понятия теории графов

Для определения основных понятий теории графов необходимо ввести определение множества. Множество - это совокупность некоторых объектов, объединенное общими свойствами. Множество может содержать n число компонентов. Множество может быть, конечно, или бесконечно.

Графами называют взаимосвязь двух множеств состоящих из множества вершин и множества ребер индуцируемых (связанных) между собой.

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

Неориентированный граф - граф не имеющий указания направлений ребер, при переходе из одной вершины в другую.

Ориентированный (полный) граф - граф с ребрами указывающими конкретное направление при переходе из одной вершины в другую.

Общий вид графов.

Неориентированный граф Ориентированный граф

Граф-дерево это слабосвязанный граф, у которого если удалить одно ребро, то он распадается на два графа.

Граф автомата - ориентированный связный граф, вершины которого соответствуют состояниям, а дуги - переходам между ними.

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

При описании автомата Мура в виде графа выходной сигнал у записывается внутри вершины a_m или рядом с ней, а входной сигнал х над дугой (ребром) демонстрирующей переход из одного состояния автомата в другое.

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

Граф-дерево автомата Мура

При построении граф-дерева автомата Мура используется таблица соответствий, дополненная до выполнения условия автоматности. После выполнения условия автоматности, граф-дерево автомата Мура примет вид:

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

Граф-дерево автомата Мили

В процессе этапа построения кодопреобразователя осуществляется преобразование граф-дерева автомата Мура в граф-дерево автомата Мили. Для этого все конечные состояния автомата Мура заменяются нулевым состоянием. В ходе выполнения перечисленных операций граф-дерево автомата Мили примет вид:

Таблица переходов по графу Мили.

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

Таблица выходов по графу Мили

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

3. Минимизация абстрактного автомата Мили

Два полностью определённых автомата называются эквивалентными, если они индуцируют (производят) одно и то же отображение множества входных слов во множество выходных слов.

Частичный цифровой автомат индуцирует лишь частичное отображение множества входных слов в выходные слова.

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

Полностью определённый автомат является частным случаем частичного автомата.

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

Таблица переходов с распределением неопределенностей

Исключение недостижимых состояний

Если в автомате имеется состояние отличное от нулевого (но только не начальное), в которое он не может попасть под воздействием любого допустимого слова-то такое состояние называется недостижимым. Недостижимые состояния могут быть исключены из рассмотрения - такая операция называется исключением недостижимых состояний. Недостижимые состояния исключаются из описания абстрактного автомата без изменения, индуцируемого автоматом отображения. Автомат, у которого все состояния достижимы - называется связанным.

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

Определение классов совместимости

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

Состояния называются i - совместимыми для i = 1, 2,…, если результат применения к этим состояниям любого слова длины i будет одинаковым. Классы совместимых состояний могут быть найдены непосредственно по таблице выходов. В один и тот же 1 - класс зачисляются состояния, обозначающие совпадающие (с точностью до неопределённых выходных сигналов) столбцы таблицы выходов. Классы (i+1) - совместимости получаются из классов i - совместимости путём их расщепления на классы (i+1) - совместимости. Для этого у каждого состояния, принадлежащего j - классу i - совместимости C_j(i), номера классов (индексы), в которые автомат переходит под воздействием каждой входной буквы. Если номер класса не определён, то ставится специальный символ, например, прочерк. Индексы классов, в которые переходит автомат под действием входного сигнала образуют отметку. Множество состояний с одинаковыми отметками в классе C_j (i) образуют классы (i+1) - совместимости. При выполнении операции расщепления классов специальный символ неопределённости может быть заменён номером (индексом) любого класса. Если операцию расщепления i - классов применить последовательно, начиная с 1 - класса, то через конечное число шагов процесс расщепления закончится. Нерасщепляемые далее классы образуют классы совместимых состояний. Иногда отметки состояний разных классов совпадают, но объединять такие состояния в один класс (i+1) - совместимости совершенно недопустимо.

Задачей минимизации методом расщепления классов совместимости является получение как можно меньшего количества, как можно большей ёмкости классов конечной совместимости.

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

цифровой граф теория автомат

Как видно из получившихся таблиц первичной совместимости, 1 класс необходимо разбить на 4 класса, а класс 2 - на 3 класса, поэтому:

Как видно из получившихся таблиц вторичной совместимости, необходимо продолжить операцию, поэтому:

Как видно из получившихся таблиц троичной совместимости, необходимо продолжить операцию, поэтому:

Как видно из получившихся 4-ной совместимости, необходимо продолжить операцию, поэтому:

Как видно из получившихся таблиц 5-ной совместимости, необходимо продолжить операцию, поэтому:

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

Составим таблицы состояний и выходов полученного автомата:

Размещено на Allbest.ru