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

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

Лекция 1. Основные понятия и определения

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

1.Класс логических или комбинационных схем (КС), в котором значение выходного сигнала в любой момент времени t однозначно определяется значениями входных сигналов в этот же момент времени.

2.Класс конечных автоматов (КА), в котором значение сигнала на выходе определяется не только значениями выходных сигналов, но и состоянием КА в предыдущий момент времени. Т.е. такие устройства обладают памятью, в отличие от КС.

Вопросы синтеза КС решаются с помощью аппарата математической логики.

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

ПФ называется функция f(x1, x2, …, xn), где x1, x2, …, xn — входные сигналы, способная принимать в качестве аргументов только 0 и 1.

Любая ПФ n аргументов определена на 2n наборов. Число различных y-ов ПФ n аргументов равно 22n (2^(2^n)).

Пример:

Зададим ПФ трёх аргументов f(x1, x2, x3) в виде ТИ ПФ. Данная функция определена на 23 = 8 наборах, которые обычно заполняются в соответственном порядке, последующий набор получается из предыдущего прибавлением единицы. Каждому набору ставится в соответствие ПФ (f).

ТИ ПФ:

1

Для синтеза КС зададим аргументы x1, x2, x3 как входные сигналы, а значение ПФ f

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

Возьмём некоторую КС, которая имеет n входов и m выходов и, следовательно, реализуют m ПФ от n аргументов.

Любая сколь угодно сложная ПФ может быть построена из более простых схем, называемых логическими элементами (ЛЭ).

ЛЭ реализует элементарную ПФ, число входов равно количеству аргументов ПФ, схема имеет только один выход.

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

1. Последовательное соединение логических элементов.

Рисунок 2

2. Перестановка ходов логических элементов. Рис. 3

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

Существует несколько базисов:

1.Булев базис: И, ИЛИ, НЕ.

2.Отрицание конъюнкции: И, НЕ (Рис.4). Штрих Шефера.

2

3. Отрицание дизъюнкции: ИЛИ, НЕ. Стрелка Пирса.

Рисунок 3

Характеристики логических элементов:

1.Коэффициент объединения J — ограничения на определённое число входных сигналов в одном элементе.

2.Коэффициент разветвления E — нагрузочная способность ЛЭ, т. е. наибольшее число входов других элементов, которые можно подсоединить к выходу данного элемента.

Синтез цифровых автоматов без памяти

Общие задачи структурного синтеза КС Рассмотрим синтез КС, реализующих одну ПФ. Процесс синтеза КС на элементах

заданного базиса состоит из следующих этапов:

1.Аналитическая запись ПФ в виде СДНФ, СКНФ.

2.Минимизация ПФ в Булевом базисе.

3.Представление полученного после минимизации выражения в заданном базисе.

4.Аналитическая запись ПФ в булевом базисе (СДНФ, СКНФ).

Аналитическая запись переключательной функции Для аналитического представления ПФ используют два правила её записи: по 1 и по 0. Запись по 1:

1.ТИ выбирает все наборы, на которых ПФ, равна 1.

2.Записывают произведение аргументов, соответствующих этим наборам. При этом аргумент записывается в прямом виде, если равен 1 и в инверсном, если равен 0.

3.Полученное произведение объединяется знаком дизъюнкции

Минимизация ПФ в булевом базисе

3

Полученные на первом этапе СДНФ и СКНФ неудобны для построения КС, т. к. в этом случае получается достаточно громоздкие схемы реализации ПФ. Для их упрощения используется минимизация ПФ:

1. Метод минимизации Блейка-Порецкого Суть метода заключается в реализации операции обобщённого склеивания. Если в

ДНФ входит две конъюнкции AC и B¬C, тогда справедливо равенство: A & C v B & ¬C = A & C v B & ¬C v A & B

Запишем функцию f(A,B,C) в следующем виде: A & C v B & ¬C =

A & C v A & B & C v B & ¬C v A & B & ¬C = A & C v B & ¬C v A & B

Если в ПФ есть конъюнкция с переменными C и ¬C, то, не изменяя исходную функцию, её можно дополнить новыми членами вида AB. Данный процесс выполняется, пока не будут возникать новая конъюнкция вида AB. В результате преобразования получим сокращённую ДНФ.

2.Метод минимизации Мак-Класки

Вэтом методе вместо буквенной записи используется запись 0 и 1, при этом аргумент

винверсном виде записывается 0, в прямом виде — 1. В дальнейшем переходит к записи номеров наборов.

f(A,B,C,D) =

¬A & ¬B & ¬C & ¬D v ¬A & ¬B & ¬C & D v ¬A & ¬B & C & ¬D v ¬A & B & C & D v

A & ¬B & ¬C & D v A & ¬B & C & ¬D v A & B & C & ¬D v A & B & C & D =

0000 v 0001 v 0010 v 0111 v 1001 v 1010 v 1110 v 1111 = 0 v 1 v 2 v 7 v 9 v 10 v 14 v 15 = (0, 1, 2, 7, 9, 10, 14, 15).

Идея дальнейшего склеивания заключается в том, что можно склеить только те составляющие ПФ, у которых число отрицаний отличается на 1.

Например:

¬A & ¬B & ¬C & ¬D v ¬A & ¬B & ¬C & D = 0000 v 0001 = 000 = ¬A & ¬B & ¬C.

Для реализации склеивания вводится понятие индекса. Индексом называется количество единиц в двоичном представлении этого числа.

0111 — 7

0000 — 0.

4

Минимизация ПФ

Метод Квайна Для минимизации используются операции поглощения и неполного склеивания.

xy v x y=x v xy v x y - операция неполного склеивания.

Теорема Квайна: если в СДНФ ПФ провести все операции неполного склеивания, а затем все операции поглощения, то в результате получится сокращённая ДНФ, т. е. дизъюнкция всех её простых импликант.

f (A ,B ,C)= A B C v A BC (1)v A B C(2)v A B C (1)v A B C(2)v

A BC (3)v A B C (4) v A B C(3)v A B C (4 )v A B C =

A B C(1)v A B C (2)v A BC (3)v A B C (4)v A BC (5)v A B C (6)

1*−2*= A C (по B)

1−6*=A B (по C)

2−3*=B C(по A)

3−4*= A B(по C)

4−5*=A C(по B)

5−6=B C (по A)

f (A ,B ,C)= A C v A B v BC v A B v A C v B C

Методы получения тупиковых и минимальных ДНФ

Дизъюнкция простых импликант, ни одну из которых исключить нельзя, называется тупиковой ДНФ, заданной ПФ.

Методы отыскания тупиковых форм

5

1. Метод испытания дизъюнктивных членов f (A ,B ,C)= A C v B C v A B v A B v A C v B C

1) A C=1, A=0, C=1 f ( A ,B , C)=B v B=1

A C−можно исключить (получилась единица)

f (A ,B ,C)=B C v A B v A C - тупиковая ДНФ.

2.Метод импликантных матриц

f1 ( A ,B ,C)= A C v A B v BC - минимальная

f2 ( A ,B ,C)= A B v B C v A C - минимальная

f 3 ( A ,B ,C)= A C v B C v B C v A C - тупиковая

Лабораторная работа №1 Синтез комбинационных схем на универсальных логических элементах

F(A, B, C, D) = v(1, 3, 6, 7, 9, 12, 13) = 1, v(0, 4, 8, 14) = 0

На остальных наборах ПФ не определена.

Минимизация по единицам

На карте Карно необходимо объединить единицы в контуры, состоящие из 2n клеток, причём одна и та же единица может входить в несколько контуров одновременно.

F(A, B, C, D) = A B !C v !A C v D A v B v C = !(!A !B !C)

И-НЕ: F(A, B, C, D) = !(!(A B !C) !(!A C) !D) X Y Z = !(!X v !Y v !Z)

ИЛИ-НЕ: F(A, B, C, D) = !(!A v !B v !C) v !(!!A v !C) v D = !!(!(!A v !B v !C) v !(A v !C)

v D)

Рис. 5

Рисунок 4: Схема И-НЕ

7

Правила считывания контуров с карты Карно Минимизация по единицам: переменная записывается в прямом виде, если равна

единице, и в инверсном, если равна нулю. Между переменными внутри контура ставится конъюнкция, между контурами — дизъюнкция.

Минимизация по нулям: переменная записывается в прямом виде, если равна нулю, и в инверсном — если равна единице. Внутри контура между переменными ставится знак дизъюнкции, между контурами — конъюнкции.

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

И−НЕ : F( A ,B ,C , D)=( A v C v D)( A v C)(B v D)=(( A C D)( A C)(B D)) ИЛИ−НЕ : F (A ,B ,C , D)=( A vC v D)( A v C)(B v D)=(( A vC v D)v ( A vC )v (B v D))

Рисунок 5: Схема И-НЕ

8

Рисунок 6: Схема ИЛИ-НЕ

Общая теория конечных цифровых автоматов с памятью

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

Кодирование информации

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

Математическая модель конечного автомата

X (x1, x2,... , xF)→ A (a0, a1, ... ,aM )→Y ( y1, ..., yG)

Для задания любого КА необходимо задать совокупность из пяти объектов.

S ( A , X ,Y ,δ, λ)

A = { a_0, a_1, ..., a_M } - множество сигналов

X = { x_1, x_2, ..., x_F } - множество входных воздействий Y = { y_1, ..., y_G } - множество выходных воздействий

Дельта - функция переходов, определяющая состояние автомата в момент времени ( t + 1 ), в зависимости от состояния автомата и входного сигнала в момент времени t

Лямбда - функция выходов, определяющая значение выходного сигнала, в зависимости от состояния автомата и входного сигнала в момент времени t.

9

Способы задания автоматов

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

Автомат Мили: автомат находится в некотором состоянии a(t) → подаётся входной сигнал x(t) → меняется сигнал на выходе автомата y(t) → автомат переходит в состояние a(t+1).

Автомат Мура: подаётся входной сигнал x(t) → автомат в состоянии a(t) → автомат переходит в состояние a(t+1) → формируется сигнал на выходе y(t).

1)Таблица переходов

2)Таблица выходов

В таблице переходов на пересечении столбца и строки ставится состояние КА, в которое он перейдёт из предыдущего состояния под воздействием входного сигнала X.

Эти таблицы необходимы для автомата Мили.

Очень часто в автомате Мили таблицу переходов и выходов совмещают.

Для автомата Мура требуется только одна таблица, т. к. Y однозначно определяется состоянием автомата. Такая таблица называется отмеченной.

10