Материалы для студентов→ Курсовая работа /

Решение комплексной задачи синтеза дискретного устройства с памятью

Скачать файл
Добавил: fafnir
Размер: 407 KB
Добавлен: 30.04.2015
Просмотров: 998
Закачек: 14
Формат: doc

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

Кафедра ИТАС

Курсовая работа

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

Тема: Решение комплексной задачи синтеза дискретного устройства с памятью.

Вариант 3.

Выполнил: студент гр. ЭВТ-06

Бакунов Р. Р.

Зачетная книжка № 06-292

Проверил: профессор Коган Т. И.

Пермь 2007 г.

ОГЛАВЛЕНИЕ.

  • ОГЛАВЛЕНИЕ.
  • ВВЕДЕНИЕ.
  • ЗАДАНИЕ НА ПРОЕКТИРОВАНИЕ.
  • АБСТРАКТНЫЙ СИНТЕЗ АВТОМАТА.
  • Построение первичной таблицы переходов-выходов.
  • Построение минимизированной таблицы переходов.
  • Построение реализуемой таблицы переходов.
  • Построение таблицы переходов-выходов.
  • Построение таблицы возбуждений.
  • Получение условий работы синтезируемого ДУ.
  • СТРУКТУРНЫЙ СИНТЕЗ АВТОМАТА.
  • Минимизация функций, описывающих условия функционирования ДУ.
  • Приведение функций, описывающих условия работы автомата, к виду, удобному для реализации в базисе И-НЕ.
  • Построение функциональной схемы автомата по отдельным каналам.
  • Общая функциональная схема автомата.
  • ЭЛЕМЕНТЫ ФИЗИЧЕСКОГО СИНТЕЗА.
  • АНАЛИЗ АВТОМАТА НА ОТСУТСТВИЕ СОСТЯЗАНИЙ ТИПА «РИСК В 1» ПО ВЫХОДУ Z2 ИЛИ Z1.
  • АВТОМАТИЗИРОВАННЫЙ СИНТЕЗ АВТОМАТА НА ПЭВМ.
  • СРАВНЕНИЕ РУЧНОГО И МАШИННОГО РЕШЕНИЙ.
  • ЗАКЛЮЧЕНИЕ.

ВВЕДЕНИЕ.

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

В данной курсовой работе будет вручную решена задача абстрактного и структурного синтеза дискретного устройства с памятью- кодового замка, будут рассмотрены элементы физического синтеза. Кроме того, будет произведен анализ полученной функциональной схемы автомата на отсутствие состязаний типа «Риск в 1» по одному из выходов. В настоящее время, в «компьютерную эру», человеку уже необязательно «обременять» себя ручным выполнением решений многих задач. Это тоже найдет свое отражение в данной курсовой работе: наряду с ручным синтезом автомата будет выполнен машинный синтез с использованием пакета «PROEKT», а также будет произведено их сравнение.

ЗАДАНИЕ НА ПРОЕКТИРОВАНИЕ.

Спроектировать цифровой автомат (кодовый замок), имеющий три входа (a,b,c) и два выхода (z1,z2).

Выходz1 возбуждается при подаче входной последовательности сигналов 0-4-5-1-0, выходz2- при нарушении заданной последовательности.

В качестве элементной базы использовать интегральные микросхемы базиса И-НЕ. В качестве элементов памяти использоватьRS- триггеры с прямым управлением. После получения функциональной схемы автомата провести ее анализ на отсутствие состязаний типа «Риск в 1» в функции выходаz2 илиz1. Входные сигналы образуют совокупность соседних чисел.

АБСТРАКТНЫЙ СИНТЕЗ АВТОМАТА.

Построение первичной таблицы переходов-выходов.

Программа работы автомата, удовлетворяющая условию возбуждения выходаz1 при подаче заданной входной последовательности, имеет вид:

Первичная таблица переходов-выходов имеет вид:

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

Диаграмма объединений:

Минимизированная таблица переходов:

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

Определение всех переходов:

ab100

b→a110*c101

c→d001*a111

d→a011*a101

Диаграмма переходов:

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

Пусть переходca111будет идти черезb. Тогда минимизированная таблица переходов примет вид:

Переходы из строки с примут следующий вид:

cd001*(aab)111

Получается следующая диаграмма переходов:

Минимально количество элементов карты Карно = 2.

Все переходы удалось сделать соседними, лишних строк вводить не надо, количество ЭП – 2.

Кодирование строк (при базеy1y2):

a→00

b→01

c→11

d→10

Реализуемая таблица переходов:

Построение  таблицы переходов-выходов.

Таблица оцифрована в 8-ной системе счисления.

Построение таблицы возбуждений.

По заданию в качестве ЭП выбранRS-триггер с прямым управлением.

Таблица входовRS-триггера с прямым управлением:

Таблица возбуждений:

Получение условий работы синтезируемого ДУ.

Функции выходов:

z1(y1y2abc) = 20, [00, 01, 02, 03, 04, 05, 06, 07, 10, 14, 15, 16, 17, 21, 23, 25, 31, 34, 35, 37];

z2(y1y2abc) = 01, 02, 03, 05, 06, 07, 10, 16, 17, 23, 25, 34, 37, [00, 04, 14, 15, 20, 21, 31, 35];

Функции возбуждения ЭП:

S1(y1y2abc) = 15, [00, 01, 02, 03, 04, 05, 06, 07, 10, 14, 16, 17, 23, 25, 37];

R1(y1y2abc) = 23, 25, 37, [15, 20, 21, 31, 34, 35];

S2(y1y2abc) = 04, [00, 01, 02, 03, 05, 06, 07, 16, 17, 20, 21, 23, 25, 31];

R2(y1y2abc) = 16, 17, 31,  [04, 10, 14, 15, 34, 35, 37];

СТРУКТУРНЫЙ СИНТЕЗ АВТОМАТА.

Минимизация функций, описывающих условия функционирования ДУ.

z1(y1y2abc) = 20, [00, 01, 02, 03, 04, 05, 06, 07, 10, 14, 15, 16, 17, 21, 23, 25, 31, 34, 35, 37];

«20» покрыто.

z2(y1y2abc) = 01, 02, 03, 05, 06, 07, 10, 16, 17, 23, 25, 34, 37, [00, 04, 14, 15, 20, 21, 31, 35];

«01», «03», «05», «07» покрыто.

«02», «06», «16», «17», «23», «37» покрыто.

«10» покрыто.

«25» покрыто.

«34» покрыто.

S1(y1y2abc) = 15, [00, 01, 02, 03, 04, 05, 06, 07, 10, 14, 16, 17, 23, 25, 37];

«15» покрыто.

R1(y1y2abc) = 23, 25, 37, [15, 20, 21, 31, 34, 35];

«23», «37» покрыто.

«25» покрыто.

S2(y1y2abc) = 04, [00, 01, 02, 03, 05, 06, 07, 16, 17, 20, 21, 23, 25, 31];

«04» покрыто.

R2(y1y2abc) = 16, 17, 31,  [04, 10, 14, 15, 34, 35, 37];

«16», «17» покрыто.

«31» покрыто.

Приведение функций, описывающих условия работы автомата, к виду, удобному для реализации в базисе И-НЕ.

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

Выходz1:

Выходz2:

Триггер Т1:

Триггер Т2:

Общая функциональная схема автомата.

ЭЛЕМЕНТЫ ФИЗИЧЕСКОГО СИНТЕЗА.

Для построения рабочей схемы синтезируемого ДУ нужны следующие микросхемы:

К155ЛА10 – 3 шт. (3х3И-НЕ)

К155ЛА3 – 2 шт. (4х2И-НЕ)

К155ЛА2- 1 шт. (8И-НЕ)

К555ТР2- 1 шт. (ЧетыреRS-триггера)

Краткая техническая характеристика интегральных микросхем 155-й серии:

Основой микросхем являются транзисторы (транзисторно- транзисторная логика – ТТЛ).

Uпит = +5 В

U1 >= +2,4 В (высокий уровень)

U0 <= + 0,3 В (низкий уровень)

Pпотр = 10 мВт

Для 555-й серии параметры аналогичны, за исключением того чтоPпотр = 2 мВт, т.е. микросхемы этой серии «экономичнее» в 5 раз.

АНАЛИЗ АВТОМАТА НА ОТСУТСТВИЕ СОСТЯЗАНИЙ ТИПА «РИСК В 1» ПО ВЫХОДУZ2 ИЛИZ1.

Анализ по выходуz2:

Анализ по выходуz1:

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

Т.к. состязаний в функцияхz1 иz2 нет, то по заданию нужно выполнить пример из учебного пособия (часть 1, с. 130, пример 5.5).

Пример 5.5 Функциональная схема ДУ показана на рисунке 5.23.

Логическое выражение, описывающее условия его работы, имеет вид:

Очевидно, что в рассматриваемом ДУ могут иметь место состязания типа риск в нуле (форма КНФ) по переменнымx2 иx3, т.е. при таких изменениях состояний входов, при которыхx2 илиx3 меняются с 0 на 1, на выходе ДУ может кратковременно появиться ошибочный единичный сигнал.

Из КНФ  получаем:

Вычисляем функции риска в нуле поx2 иx3:

Вычисляем функцию риска в нуле для всего ДУ:

Приведем функцию  к символической форме при базеx1x2x3x4:

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

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

Полученный результат говорит о том, что на входных наборах 1, 3, 9, 10, 11, 14, 15 (при базеx1x2x3x4) на выходе ДУ сигнала быть не должно (нулевой сигнал). Однако вследствие наличия состязаний типа риск в нуле по переменнойx2 иx3 при переходах входных сигналов 10 → 14, 11 → 15, 1 → 3, 9 → 11, когда переменныеx2 иx3 изменяют свои значения с 0 на 1, возможны появления на выходе кратковременных ложных единичных сигналов.

АВТОМАТИЗИРОВАННЫЙ СИНТЕЗ АВТОМАТА НА ПЭВМ.

Распечатка результатов машинного синтеза:

SINTEZ - PROEKT24

PAMJAT = 'RS' c пpямым упpавлением'

STR = 13, STO = 8, XRAZV = 1, XRAZB = 3, ZRAZB = 2

Схема построена на 'И-НЕ' элементах

База входного слова: a,b,c;

База выходного слова: z1,z2;

Пеpвичная таблица пеpеходов-выходов:

╔═════╦════════════════════════════════════════╦═════╗

║N.вн.║ Вх.слова                               ║вых. ║

║сост.║ 0    1    3    7    6    4    5    2   ║¤1¤0 ║

╠═════╬════════════════════════════════════════╬═════╣

║ 1   ║ 1    6    -    -    -    2    -    7   ║ 0 0 ║

║ 2   ║ 8    -    -    -    9    2    3    -   ║ 0 0 ║

║ 3   ║ -    4    -    10   -    11   3    -   ║ 0 0 ║

║ 4   ║ 5    4    12   -    -    -    13   -   ║ 0 0 ║

║ 5   ║ 5    -    -    -    -    -    -    -   ║ 1 0 ║

║ 6   ║ -    6    -    -    -    -    -    -   ║ 0 1 ║

║ 7   ║ -    -    -    -    -    -    -    7   ║ 0 1 ║

║ 8   ║ 8    -    -    -    -    -    -    -   ║ 0 1 ║

║ 9   ║ -    -    -    -    9    -    -    -   ║ 0 1 ║

║ 10  ║ -    -    -    10   -    -    -    -   ║ 0 1 ║

║ 11  ║ -    -    -    -    -    11   -    -   ║ 0 1 ║

║ 12  ║ -    -    12   -    -    -    -    -   ║ 0 1 ║

║ 13  ║ -    -    -    -    -    -    13   -   ║ 0 1 ║

╚═════╩════════════════════════════════════════╩═════╝

Матpица объединеных стpок:

╔═════╦═════════════════════════════════════════════════════╗

║Nстp.║N стp.                                               ║

║мин. ║пеpв.табл.                                           ║

║табл.║ 1   2   3   4   5   6   7   8   9   10  11  12  13  ║

╠═════╬═════════════════════════════════════════════════════╣

║ 1   ║ 1   0   0   0   0   1   1   0   1   1   0   1   1   ║

║ 2   ║ 0   1   0   0   0   0   0   1   0   0   0   0   0   ║

║ 3   ║ 0   0   1   0   1   0   0   0   0   0   1   0   0   ║

║ 4   ║ 0   0   0   1   0   0   0   0   0   0   0   0   0   ║

╚═════╩═════════════════════════════════════════════════════╝

Минимизиpованная таблица пеpеходов:

╔═════╦═════════════════════════════════╗

║N.вн.║ Вх.слова                        ║

║сост.║ 0   1   3   7   6   4   5   2   ║

╠═════╬═════════════════════════════════╣

║ 1   ║ 1   1   1   1   1   2   1   1   ║

║ 2   ║ 2   -   -   -   1   2   3   -   ║

║ 3   ║ 3   4   -   1   -   3   3   -   ║

║ 4   ║ 3   4   1   -   -   -   1   -   ║

╚═════╩═════════════════════════════════╝

Матpица выходов:

╔═════╦═════════════════════════════════╗

║N.вн.║ Вх.слова                        ║

║сост.║ 0   1   3   7   6   4   5   2   ║

╠═════╬═════════════════════════════════╣

║ 1   ║ 00  01  01  01  01  00  01  01  ║

║ 2   ║ 01  --  --  --  01  00  00  --  ║

║ 3   ║ 10  00  --  01  --  01  00  --  ║

║ 4   ║ 10  00  01  --  --  --  01  --  ║

╚═════╩═════════════════════════════════╝

Pеализуемая таблица пеpеходов:

╔═════╦═════════════════════════════════╦═════╗

║N.вн.║ Вх.слова                        ║Вн.  ║

║сост.║ 0   1   3   7   6   4   5   2   ║сост.║

╠═════╬═════════════════════════════════╬═════╣

║ 1   ║ 1   1   1   1   1   2   1   1   ║ 00  ║

║ 2   ║ 2   -   -   1   1   2   3   -   ║ 01  ║

║ 3   ║ 3   4   -   2   -   3   3   -   ║ 11  ║

║ 4   ║ 3   4   1   -   -   -   1   -   ║ 10  ║

╚═════╩═════════════════════════════════╩═════╝

Конечная матpица выходов:

╔═════╦═════════════════════════════════╗

║N.вн.║ Вх.слова                        ║

║сост.║ 0   1   3   7   6   4   5   2   ║

╠═════╬═════════════════════════════════╣

║ 1   ║ 00  01  01  01  01  00  01  01  ║

║ 2   ║ 01  --  --  01  01  00  00  --  ║

║ 3   ║ 10  00  --  01  --  01  00  --  ║

║ 4   ║ 10  00  01  --  --  --  01  --  ║

╚═════╩═════════════════════════════════╝

Базис:  y1,y2,a,b,c

'RS' c пpямым упpавлением'

Уpавнения возбуждения элементов памяти:

S1 = y2*~b*c;

R1 = b + ~y2*a;

S2 = a*~b*~c + y1*~c;

R2 = ~y1*b + b*~c + ~a*c;

Уpавнения выходов:

z1 = y1*~a*~c;

z2 = ~y1*~a*c + b + ~y2*a*c + ~y1*y2*~a + y1*a*~c;

Теперь выводим на элементах И-НЕ

'RS' c пpямым упpавлением'

Уpавнения возбуждения элементов памяти:

S1 = ~( ~( y2*~b*c ) );

R1 = ~( ~(b) * ~(~y2*a) );

S2 = ~( ~(a*~b*~c) * ~(y1*~c) );

R2 = ~( ~(~y1*b) * ~(b*~c) * ~(~a*c) );

Уpавнениявыходов:

z1 = ~( ~( y1*~a*~c ) );

z2 = ~( ~(~y1*~a*c) * ~(b) * ~(~y2*a*c) * ~(~y1*y2*~a) * ~(y1*a*~c) );

Функциональная схема, полученная в результате машинного решения:

СРАВНЕНИЕ РУЧНОГО И МАШИННОГО РЕШЕНИЙ.

В ручном решении таблица переходов-выходов имеет вид:

Функции возбуждения элементов памяти и выходов имеют вид:

В машинном решении эти функции имеют вид:

S1 = y2*~b*c;

R1 = b + ~y2*a;

S2 = a*~b*~c + y1*~c;

R2 = ~y1*b + b*~c + ~a*c;

z1 = y1*~a*~c;

z2 = ~y1*~a*c + b + ~y2*a*c + ~y1*y2*~a + y1*a*~c;

Видно, что есть расхождения в функцияхz,S2 иR2.

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

Между таблицами, полученными вручную и с помощью машины, есть различия. В ручной таблице клетка с ВС = 30 является неиспользуемой. В связи с этим отсутствует переход от клетки с ВС=20 к клетке с ВС=30. Причиной этого является, как следует из матрицы объединенных строк, разное объединение строк:

ручное решение: 1 - 1,6,7,9,10,12,13; 2 - 2,8; 3 - 3,11; 4- 4,5.

машинное решение: 1 – 1,6,7,9,10,12,13; 2 – 2,8; 3 – 3,5,11; 4 – 4.

В данном случае это привело к тому, что в таблице переходов-выходов машинного решения содержится большее количество значащих (заполненных) клеток, а, значит, большее число переходов и, как следствие, большее число букв в функцияхS2 иR2. Таким образом, в данном случае машинное решение оказалось более сложным, чем ручное.

Работа машины имеет некоторые особенности. На этапе минимизации первичной таблицы переходов-выходов машина выбирает объединяемые строки путем последовательного сравнения каждой строки со всеми остальными. Группа непротиворечивых строк объединяется в одну строку минимизированной таблицы переходов, и строки, входящие в эту группу, исключаются из дальнейшего рассмотрения. Процедура продолжается, пока не будут исключены все строки из первичной таблицы переходов. Человек же при объединении строк первичной таблицы переходов выбирает варианты объединения строк, исходя из своих знаний и прогнозов на получение минимизированной таблицы с наименьшим количеством значащих клеток (тактов). Здесь кроется одна из причин возможных неоднозначностей конечных результатов. Но, как правило, это не единственная причина.

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

ЗАКЛЮЧЕНИЕ.

В данной курсовой работе произведен ручной абстрактный и структурный синтез дискретного устройства (кодового замка) по заданным условиям работы, рассмотрены элементы физического синтеза (были подобраны микросхемы, необходимые для осуществления физического синтеза проектируемого ДУ, определено нужное их количество), а также произведен анализ спроектированного автомата на отсутствие состязаний типа «Риск в 1» по одному из выходов. Кроме того, был выполнен машинный синтез рассматриваемого ДУ с помощью пакета «PROEKT», а также проведено сравнение результатов ручного и машинного синтезов (в данном случае машинное решение оказалось более сложным, чем ручное), плюс ко всему прочему было дано объяснение несовпадения этих результатов.