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

Федеральное агентство по образованию

Тихоокеанский государственный университет

 

Кафедра «Вычислительная техника»

 

 

 

 

 

 

Пояснительная записка к курсовой работе

по дисциплине «теория автоматов»

«Синтез цифрового автомата на заданных элементах памяти и заданных на определенном логическом базисе»

 

Вариант № 15

 

 

 

 

 

 

 

 

 

 

 

 

 

 

                                                                            Выполнил:

студент гр. МТС-11

                                                                             Селина А.К

 

                                                                          проверил:

                                                                          Агеев В.В.

 

 

 

 

 

 

 

г. Хабаровск, 2012г.

 

РЕФЕРАТ

 

 

 Курсовая работа по дисциплине  «Теория автоматов» содержит 1 лист  чертежа формата А3 и пояснительную записку на 26 листов формата А4, включающую 15 таблиц, 4 схемы, 2 временных диаграммы и 1 литературный источник.

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Содержание:

 

 

1.Задание  на курсовую работу_______________________________________ 4

2.Номер  варианта с индивидуальным заданием_________________________5

3.Основные единицы, сокращения, термины___________________________6

4.Задание  I_______________________________________________________9

5.Задание  II_______________________________________________________9

6.Задание  III_____________________________________________________ 10

7.Задание  IV_____________________________________________________11

8.Задание  V______________________________________________________12

9.Задание  VI_____________________________________________________ 13

10.Задание  VII___________________________________________________ 15

11.Задание VIII___________________________________________________17

12.Выводы_______________________________________________________22

13. Список  литературы_____________________________________________23

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ЗАДАНИЕ  ДЛЯ  ВЫПОЛЕНИЯ  КУРСОВОЙ РАБОТЫ

 

1. Анализ автомата

 

1. Проверить определение состояние автомата (все вершины должны быть пронумерованы однозначно).
2. Во всех дугах исходящих из каждой вершины должны быть различные значения.
3. Мощность множества Х должна быть минимальна.
4. Отметить тупиковые состояния (все выходы, ни одного выхода)
5. Отметить приходящие состояния (вершины из которых имеются только выходы, ни одного входа).
6. Определить мощность множеств Х, У, Z.
7. Определить тупиковые и приходящие подавтоматы.

 

2. Составить автоматную матрицу.
3. Составить таблицу переходов/ выходов.
4. Произвести эффективное кодирование состояний автомата, с учетом типа триггера, входящих в память автомата.
5. Представить закодированную таблицу .
6. Синтез КС автомата

 

1. Заполнить карты Карно.
2. Найти оптимальные покрытия.
3. Представить КС в заданном логическом базисе или на логических блоках.

7. С помощью графического редактора представить принципиальную схему автомата.
8. Структурное моделирование автомата с помощью графического редактора и редактора временных диаграмм.

 

1. Определение тестовой последовательности входных сигналов .
2. Описание автомата с помощью оператора Machine.
3. Структурное и поведенческое ((GE и WF) и (Machine)).

 

9. Выводы.

 

 

 

 

 

 

Вариант 15

 

Задан цифровой автомат.

 

Произвести синтез данного автомата на D триггере и Multiplexor (MUX).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

 

 

Altera( AHDL) – графический редактор языка .

ДНФ- дизъюнктивная нормальная форма.

КНФ- конъюнктивная нормальная форма.

КС- комбинационная схема.

Multiplexor (MUX) - устройство, собирающее несколько узкополосных (низкоскоростных) коммуникационных каналов в широкополосный (broadband), или высокоскоростной, канал.

Machine – автоматный порт.

 

Термины:

 

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

 

Цифровой автомат – устройство, предназначенное для преобразования цифровой информации.

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

Автомат функционирует в дискретном времени 

Каждый i-ый момент времени автомат находится в состоянии , воспринимает входной сигнал , осуществляет переход в состояние , выдает выходной сигнал . В момент времени , автомат переходит в состояние и не воспринимает входной сигнал.

 

Упрощенная структурная схема  автомата имеет вид:

 

 

 

 

 

 

 

 

 

Multiplexor (MUX)

Мультиплексор — устройство, имеющее несколько сигнальных входов, один или более управляющих входов и один выход.   Мультиплексор позволяет  передавать сигнал с одного из входов на выход; при этом выбор желаемого  входа осуществляется подачей соответствующей  комбинации управляющих сигналов.   Аналоговые и цифровые мультиплексоры значительно различаются  по принципу работы. Первые электрически соединяют выбранный вход с выходом (при этом сопротивление между  ними невелико — порядка единиц/десятков ом). Вторые же не образуют прямого электрического соединения между выбранным входом и выходом, а лишь «копируют» на выход  логический уровень ('0' или '1') с выбранного входа. Аналоговые мультиплексоры иногда называют ключами или коммутаторами.   Мультиплексоры могут  использоваться в делителях частоты, триггерных устройствах, сдвигающих устройствах  и др. Мультиплексоры часто используют для преобразования параллельного  двоичного кода в последовательный. Для такого преобразования достаточно подать на информационные входы мультиплексора параллельный двоичный код, а сигналы  на адресные входы подавать в такой  последовательности, чтобы к выходу поочередно подключались входы, начиная  с первого и заканчивая последним.

Дизъюнктивная нормальная форма(ДНФ) 

 

 

     Переменная   или   называется литералом (или  буквой).     

Конъюкция литералов, встречающихся  не более чем по одному разу, называется элементарной конъюнкцией. Число букв входящих в неё называется её рангом. Элементарная конъюнкция называется полной относительно рассматриваемой булевой функции, если её ранг равен числу переменных данной функции.     

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

 

 

Конъюнктивная нормальная форма (КНФ)

 

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

 

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

 

 

Карты Карно

 

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

C(куб)- оценка стоимости комбинационной схемы.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Задание I

 

Произведем анализ автомата, заданного графом:

 

1. Все вершины пронумерованы.
2. Во всех дугах исходящих из каждой вершины различные значения.
3. Мощность множества Х минимальна.

Z1 <X1, X3>,  N=2;

Z2 <X3, X2, X1>, N=3;

Z3 <X1, X2, X3>, N=3;

Z4 <X1, X2>,  N=2;

Z5 <X1, X2, X3>, N=3;

Z6 <X1, X2, X3>, N=3;

Z7 <X1>, N=1.

4. Тупиковых состояний (все входы, ни одного выхода) нет.
5. Приходящих состояний (вершины, из которых имеются только выходы, ни одного входа) нет.
6. Мощность множеств Х, У, Z.

X=3, Y=2, Z=7.

7. Тупиковых и приходящих подавтоматов нет.

 

 

 

Задание II

 

Составим  автоматную матрицу.

 

	Z1	Z2	Z3	Z4	Z5	Z6	Z7
Z1	-	1/2	-	3/2	-	-	-
Z2	-	-	-	3/2	1/1	-	2/1
Z3	1/1	-	3/2	2/2	-	-	-
Z4	-	-	-	-	2/1	-	1/2
Z5	-	3/1	-	-	2/1	-	1/2
Z6	2/1	-	½	3/2	-	-	-
Z7	-	-	-	-	-	1/1	-

 

 

 

 

 

 

 

Задание III

 

Составим таблицу переходов/выходов

 

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

 

Табл.

 

	Z1	Z2	Z3	Z4	Z5	Z6	Z7
X1	Z2	Z5	Z1	Z7	Z7	Z3	Z6
X2	-	Z7	Z4	Z5	Z5	Z1	-
X3	Z4	Z4	Z3	-	Z2	Z4	-

 

Табл.

 

 

	Z1	Z2	Z3	Z4	Z5	Z6	Z7
X1	Y2	Y1	Y1	Y2	Y2	Y2	Y1
X2	-	Y1	Y2	Y1	Y1	Y1	-
X3	Y2	Y2	Y2	-	Y1	Y2	-