ЛБ4

МИНОБРНАУКИ РОССИИ

Федеральное государственное образовательное учреждение высшего образования

“Юго–Западный государственный университет”

Кафедра информационной безопасности

Лабораторная работа №4

По дисциплине “Дискретная математика”

По теме “ ЦИФРОВЫЕ АВТОМАТЫ.

СТРУКТУРНЫЙ СИНТЕЗ ЦИФРОВЫХ АВТОМАТОВ”

Выполнил: студент группы ИБ-11б

Гребенникова А.И.

Проверил Шевелев С.С.

Курск 2022г.

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

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

Теоретическая часть.

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

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

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

Если за 1 такт в устройство передается 1 из разрядов 2ого числа (кода), устройство работает в посл. коде, если за 1 такт его работы передается все двоичное число одновременно, то устройство работает в парал. коде:

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

Математической моделью ЦА (а в общем случае любого дискретного устройства) является так называемый абстракт­ный автомат, определенный как 6-компонентный кортеж: A=(S, X, Y, , , S0) у которого:

1. S={s₁, s₂, ... ,s_m} – алфавит состояний – множество состояний, в которых может находиться проектируемый цифровой автомат. Количество состояний играет важную роль при реализации ЦА. Чем больше состояний, тем больше требуется запоминающих элементов(триггеров) для построения ЦА.

2. X={x₁, x₂, ... ,x_f} – алфавит входных значений – множество значений, которые могут поступать на вход ЦА. Например, если у автомата двухразрядный двоичный вход, то элементами алфавита могут быть 00, 01, 10 и 11.

3. Y={y₁, y₂, ..., y_g} – алфавит выходных значений – множество значений, которые могут быть установлены на выходе ЦА.

4. :SXS – функция переходовs(t+1)=(x(t),s(t)). Функция переходов определяет, в какое состояние s(t+1) перейдет автомат под воздействием входного сигнала x(t), если в текущий момент времени автомат находится в состоянии s(t).

5. : AZW – функция выходов y(t)= (s(t),x(t)). Функция выходов определяет какое выходное значение y(t) будет установлено на выходе автомата в зависимости от входного значения x(t) и текущего состояния s(t).

6. s_iS - начальное состояние автомата –состояние в которое устанавливается ЦА после подачи питания или после сброса

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

Рис.1. Абстрактный автомат

Абстрактный автомат (рис. 1) имеет один вход и один выход. Автомат работает в дискретном времени, принимающем целые неотрицательные значения t = 0,1,2,... В каждый момент t дискретного времени автомат находится в некотором состоянии s(t) из множества состояний автомата, причем в начальный момент t = 0 он всегда находится в начальном со­стоянии s(0)=s1. В момент t, будучи в состоянии s(t), автомат способен воспринять на входе букву входного алфавита X(t)Z. В соответствии с функцией выходов он выдаст в тот же момент времени t букву выходного алфавита y(t)=(s(t), z(t)) и в соответствии с функцией переходов перейдет в следующее состояние s(t+1)=[s(t), x(t)], s(t) A, y(t) Y.

Смысл понятия абстрактного автомата состоит в том, что он реализует некоторое отображение множества слов вход­ного алфавита X во множество слов выходного алфавита Y. Т.е. если на вход автомата, установленного в начальное состояние s1, подавать буква за буквой некоторую последовательность букв входного алфавита x(0), x(1),... - входное слово, то на выходе автомата будут последовательно появляться буквы выходного алфавита y(0), y(1),... - выходное слово. Т.о. выходное слово = (входное слово), где  - отображение, осуществляемое абстрактным автоматом.

Разновидности цифровых автоматов

На практике наибольшее распространение получили два класса автоматов - автоматы Мили (Mealy) и Мура (Moore).

Закон функционирования автомата Мили задается уравнениями:

s(t+1) = (s(t), z(t)); w(t) = (s(t), z(t)), t = 0,1,2,...

Закон функционирования автомата Мура задается уравнениями:

s(t+1)=(s(t), z(t)); w(t) = (s(t)), t = 0,1,2,...

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

Кроме автоматов Мили и Мура иногда оказывается удобным пользоваться совмещенной моделью автомата, так на­зываемым С- автоматом.

Абстрактный С- автомат можно представить в виде устройства с одним входом, на который поступают сигналы из входного алфавита X, и двумя выходами, на которых появляются сигналы из алфавитов Y и U. Отличие С - автомата от моделей Мили и Мура состоит в том, что он одновременно реализует две функции выходов ₁ и ₂, каждая из которых характерна для этих моделей в отдельности. Закон функционирования С- автомата можно описать следующими уравнениями:

s(t+1) =(s(t), z( t )); w(t) =₁(s(t), z(t)); u(t) = ₂(s( t )); t = 0, 1, 2, ...

Выходной сигнал U_h=₂(s_m) выдается все время, пока автомат находится в состоянии s_m. Выходной сигнал Wg=₁( s_m, z_f) выдается во время действия входного сигнала Z_f при нахождении автомата в состоянии s_m.

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

Для того, чтобы задать автомат, необходимо описать все компоненты кортежа A=(S, X, Y, , , а₁ ). Множества S, X, Y описываются и задаются простым перечислением своих элементов. Среди многообразия различных способов заданий функций  и  (следовательно, и всего автомата в целом) наибольшее распространение получили табличный и графиче­ский.

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

Для кодирования состояний цифрового автомата выбираем RS-триггеры. Необходимое количество триггеров выбирается из условия минимального n, удовлетворяющего соотношению 2ⁿ ≥ N, где n – необходимое количество триггеров; N – количество состояний цифрового автомата.

Для N равного 8 , n равно 3. Каждому состоянию цифрового автомата поставим в соответствие комбинацию состояний триггеров. Кодирование состояний цифрового автомата представлено в таблице 4.

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

С целью минимизации дизъюнктивной нормальной формы используется карта Карно, которая представляет собой один из табличных способов. Карта Карно состоит из клеток, поэтому для этой переменной требуется клеток. Каждая клетка номеруется с помощью чисел «0» и «1». Номера клеток присваиваются таким образом, что бы номера соседних клеток в двоичном коде отличались не более чем на 1 разряд. Для того что бы с помощью карт Карно задать функцию, в каждую клетку необходимо занести значения , которое она принимает на наборе .

Нумерация клеток карты Карно состоит, так что их двоичные номера у соседних клеток отличаются только в одном разряде.

Для минимизации переключательной функции с помощью карт Карно и их синтеза в форме минимальной дизъюнктивной нормальной форме (МДНФ). Взаимно соседние клетки в карте Карно заполненные единицами должны быть объединены площадями минимизации. Площади минимизации состоит из взаимно соседних клеток и имеет форму квадрата или прямоугольника.

Проверка работоспособности цифрового автомата

На вход генератора случайных чисел подаем произвольную последовательность представленную на рис.4, частью которой является наша последовательность (0100111).Делая пошаговую проверку, видим, что цифровой автомат определяет заданную последовательность. Работоспособность автомата представлена на рис. 5.

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

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

Ход работы:

1. Разработка таблиц и графа автомата Мили.

Возьмём свой номер в списке группы.

5₁₀ = 000101₂

Составим граф схему ЦА по нашей последовательности.

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

входной сигнал внутр. состояния	X
	0	1
S0	S1	S0
S1	S2	S0
S2	S3	S0
S3	S3	S4
S4	S5	S0
S5	S1	S6
S6	S1	S0

Таблица 2 - Выходных сигналов

входной сигнал внутр. состояния	X
	0	1
S0	Y0	Y0
S1	Y0	Y0
S2	Y0	Y0
S3	Y0	Y0
S4	Y0	Y0
S5	Y0	Y1
S6	Y0	Y0

Таблица 3 - Совмещённая

входной сигнал внутр. состояния	X
	0	1
S0	S1/ Y0	S0/ Y0
S1	S2/ Y0	S0/ Y0
S2	S3/ Y0	S0/ Y0
S3	S3/ Y0	S4/ Y0
S4	S5/ Y0	S0/ Y0
S5	S1/ Y0	S6/ Y1
S6	S1/ Y0	S0/ Y0

Таблица 4 - Кодирование состояний

состояния внутр.триггеровсостояния	Q1	Q2	Q3
S0	0	0	0
S1	0	0	1
S2	0	1	0
S3	0	1	1
S4	1	0	0
S5	1	0	1
S6	1	1	0

Правила переходов RS двоичных триггеров представлено в таблице 5.

Таблица 5 - Таблица переходов

Переходы триггера	R	S
0→0	*	0
0→1	0	1
1→1	0	*
1→0	1	0

Таблица 6 - Кодированная таблица цифрового автомата

	x	Q1	Q2	Q3				R1 S1	R2 S2	R3 S3	Y0	Y1
S0	0	0	0	0	0	0	1	* 0	* 0	0 1	1	0
S0	1	0	0	0	0	0	0	* 0	* 0	* 0	1	0
S1	0	0	0	1	0	1	0	* 0	0 1	1 0	1	0
S1	1	0	0	1	0	0	0	* 0	* 0	1 0	1	0
S2	0	0	1	0	0	1	1	* 0	0 *	0 1	1	0
S2	1	0	1	0	0	0	0	* 0	1 0	* 0	1	0
S3	0	0	1	1	0	1	1	* 0	0 *	0 *	1	0
S3	1	0	1	1	1	0	0	0 1	1 0	1 0	1	0
S4	0	1	0	0	1	0	1	0 *	* 0	0 1	1	0
S4	1	1	0	0	0	0	0	1 0	* 0	* 0	1	0
S5	0	1	0	1	0	0	1	1 0	* 0	0 *	1	0
S5	1	1	0	1	1	1	0	0 *	0 1	1 0	0	1
S6	0	1	1	0	0	0	1	1 0	1 0	0 1	1	0
S6	1	1	1	0	0	0	0	1 0	1 0	* 0	1	0

Рисунок 1 - Граф-схема функционирования RS-триггера

2. Минимизация функций с помощью карт Карно.

Таблица 7 - Минимизация функции R1

XQ1 Q2Q3	00	01	11	10
00	*	*	*	*
01	0	1	-	1
11	1		-	1
10	*	*	0	*

Таблица 8 - Минимизация функции S1

XQ1 Q2Q3	00	01	11	10
00	0	0	0	0
01	*	0	-	0
11	0	*	-	0
10	0	0	1	0

Таблица 9 - Минимизация функции R2

XQ1 Q2Q3	00	01	11	10
00	*	0	0	0
01	*	*	-	1
11	*	0	-	1
10	*	*	1	1