43140

Синтез автомата по заданому алгоритму роботи

Курсовая

Информатика, кибернетика и программирование

Система з чотирьох перемикальніх функцій задана таблицею 2.1 таблиця істиності заданих функцій Необхідно виконати сумісну мінімізацію функцій f1 f2 f3. Отримати операторні представлення для реалізації системи функцій на програмувальних логічних матрицях. 4 Етапи проектування і терміни їх виконання 1 Розмітка станів автомата 2 Формування вхідного та вихідного алфавітів 3 Побудова графа автомата 4 Побудова таблиці переходів 5 Побудова структурної таблиці автомата 6 Синтез комбинаційних схем для функцій збудження тригерів і вихідних...

Украинкский

2013-11-03

1.49 MB

6 чел.

Національний технічний університет України

 «Київський політехнічний інститут»

Факультет інформатики та обчислювальної техніки

Кафедра обчислювальної техніки

 

                        КУРСОВА РОБОТА

з дисципліни "Прикладна теорія цифрових автоматів"

Виконав:      Кравчук Ігор Веніамінович

                      Факультет     ІОТ

                      Група       ІО-81,  
                      
Залікова книжка  №  8108

Допущена до захисту__________________

Номер технічного завдання1 111 110 101 100

                                                                         _______________________

(підпис керівника)

 

Київ  - 2008р.


Опис альбому


№ рядка

Формат

Позначення

Найменування

Кількість

Примітка

1

2

Документація загальна

3

4

розроблена заново

5

6

А4

ІАЛЦ.463626.002 ТЗ

Технічне завдання

5

7

А3

ІАЛЦ.463626.003 Е2

Керуючий автомат

1  

8

Схема електрична

9

функціональна

10

А4

ІАЛЦ.463626.004 ПЗ

Пояснювальна записка

17

 


                                 

                                                                                                        

Технічне завдання


Зміст

1. Призначення розроблюваного обєкта                  2

2. Вхідні дані для розробки                                       2

3. Склад пристроїв                                           5

4. Етапи і терміни проектування ___________________5

5. Перелік текстової і графічної документації                 5


1 Призначення розроблюваного об’єкта

В курсовій роботі нам необхідно виконати синтез автомата Мілі. Керуючий автомат — це електрична схема, що виконує відображення вхідного сигналу у вихідний по заданому алгоритму. Практичнее застосування данного автомата можливе в області обчислювальної техніки.

2 Вхідні дані

Варіант завдання визначається дев’ятьма молодшими розрядами залікової книжки представлений у двійковій системі числення.

h9=1,  h8=1,   h7=0,   h6=1,   h5=0,   h4=1,   h3=1,   h2=0,   h1=0

Логічні умови(h8 h7 h3 = 000):

X2, NOT X2, NOT X1.

Послідовність керуючих сигналів(h9 h4 h1 = 001):   

Y1, (Y1, Y2), Y3, (Y4, Y5), Y2, (Y1, Y3).

Сигнал тривалістю 2t(h6 h2 = 11):

Y4

Тригер(h6 h5 = 10):

JK – тригер.

Логічні елементи(h3 h2 h1 = 011):

3І, 2АБО, НЕ.

Тип автомату(h4 = 0):

Мілі.

Система з чотирьох перемикальніх функцій задана таблицею 2.1:

x4

x3

x2

x1

f1

f2

f3

F4

0

0

0

0

1

1

1

0

0

0

0

1

1

1

0

1

0

0

1

0

1

1

1

0

0

0

1

1

0

0

0

0

0

1

0

0

0

1

0

0

1

0

1

0

0

0

0

0

1

1

0

1

0

0

1

1

1

1

1

1

0

0

0

1

0

0

0

1

0

0

1

0

0

0

1

1

0

1

0

0

0

0

0

1

0

1

1

1

0

0

1

1

1

0

0

1

1

1

1

1

0

1

1

0

0

0

1

1

1

0

0

1

0

1

1

1

1

1

1

1

1

1

Таблиця 2.1 – таблиця істиності заданих функцій

 

Необхідно виконати сумісну мінімізацію функцій f1, f2, f3. Отримати операторні представлення для реалізації системи функцій на програмувальних логічних матрицях.

Функцію f4 необхідно представити в канонічних формах алгебр Буля, Жегалкіна, Пірса та Шеффера. Визначити належність даної функції до п’яти передповних класів. Виконати мінімізацію функції методами:

- невизначених коефіцієнтів;

- Квайна (Квайна-Мак-Класкі);

- діаграм Вейча.

3 Склад пристроїв

Керуючий автомат.

Керуючий автомат складається з комбінаційної схеми і пам’яті на тригерах. Тип тригерів і елементний базис задані в технічному завданні.

Програмувальна логічна матриця.

ПЛМ складається із двох (кон’юктивної і диз’юнктивної ) матриць, де виходи першої приєднуються на входи другої і дозволяють реалізувати комбінаційні схеми в базисі  {І/АБО, І/АБО-НЕ}.

4 Етапи проектування і терміни їх виконання

1) Розмітка станів автомата

2) Формування вхідного та вихідного алфавітів

3) Побудова графа автомата

4) Побудова таблиці переходів

5) Побудова структурної таблиці автомата

6) Синтез комбинаційних схем для функцій збудження тригерів і вихідних сигналів

7) Побудова схеми автомата в заданому базисі.

5 Перелік текстової и графічної документації

  1.  Титульний лист
  2.  Аркуш з написом «Опис альбому»
  3.  Опис альбому
  4.  Аркуш з написом «Технічне завдання»
  5.  Технічне завдання
  6.  Аркуш з написом «Керуючий автомат. Схема електрична функціональна»
  7.  Керуючий автомат. Схема електрична функціональна
  8.  Аркуш з написом «Пояснювальна записка»
  9.  Пояснювальна записка


Керуючий автомат

Схема електрична функціональна


Пояснювальна записка


Зміст

1 Вступ                                                                                                        2

2 Синтез автомата                                                                            2

2.1 Структурний синтез автомата_________________________________________2

3 Синтез комбінаційних схем                                                                7

3.1 Вступ_____________________________________________________________7  

3.2 Представлення функцій f4 в канонічній формі алгебри Буля_______________7

3.3 Представлення функцій f4 в канонічній формі алгебри Жегалкіна__________7

3.4 Представлення функцій f4 в канонічній формі алгебри Пірса______________7

3.5 Представлення функцій f4 в канонічній формі алгебри Шеффера__________8

3.6 Визначення належності функції f4 до п’яти чудових класів_______________8                         

  3.7 Мінімізація функції f4 методом невизначених коефіцієнтів_______________8                          

  3.8 Мінімізація функції f4 методом Квайна-Мак-Класкі_____________________9

  3.9 Мінімізація функції f4 методом діаграм Вейча__________________________10

  3.10 Спільна мінімізація функцій f1, f2, f3                                                      11

3.11 Спільна мінімізація заперечень функцій f1,f2,f3                                         13

3.12 Одержання операторних форм для реалізації на ПЛМ                                     15

4 Висновок                                                                                16

5 Список літератури                                                                     17


1 Вступ

У даній курсовій роботі необхідно виконати синтез автомата і синтез комбінаційних схем. Розробка виконується на підставі

«Технічного завдання ІАЛЦ.463626.002 ТЗ».

2 Синтез автомата

2.1 Структурний синтез

За графічною схемою алгоритму (рисунок 2.1 «Технічного завдання ІАЛЦ.463626.002 ТЗ») виконаєму розмітку станів автомата (рисунок 2.1):  

Рисунок 2.1 - розмітка станів автомата


Згідно з блок-схемою алгоритму(рисунок 2.1) побудуємо граф автомата Мілі

(рис. 2.2), виконаємо кодування станів автомата.

Рисунок 2.2 – Граф автомата

Для синтезу логічної схеми автомату необхідно виконати синтез функцій збудження тригерів та вихідних функцій автомата. Кількість станів автомата дорівнює 6, кількість тригерів знайдемо за формулою K>= ]log2N[ = ]log26[ = 3, звідки К = 3. Так як для побудови данного автомата необхідно використовувати    JK-тригери, запишемо таблицю переходів цього типу тригерів (рисунок 2.3).

Рисунок 2.3 – Таблиця переходів JK-тригера

На основі графа автомата (рисунок 2.2) складемо структурну таблицю автомата (таблицю 2.1).

Таблиця 2.1 – Структурна таблиця

                                              

На основі структурної таблиці автомата (таблиці 2.1) виконаємо синтез комбінаційних схем для вихідних сигналів і функцій збудження тригерів. Аргументами функцій збудження тригерів є коди станів та вхідні сигнали, для вихідних сигналів – тільки коди станів. Виконаємо Мінімізацію вищевказаних функцій методом діаграм Вейча (рисунок 2.4, 2.5). Зауважимо, що операторні представлення функцій сформовані враховуючи елементний базис {3І, 2АБО, НЕ}.

Рисунок 2.4 – діаграми Вейча

                                                                

Рисунок 2.5 – діаграми Вейча

                                                                                 

Виконаємо мінімізацію вихідних функцій теж методом діаграм                   Вейча (рисунок 2.6).

Рисунок 2.6 – мінімізація вихідних функцій

Можна побачити, що мінімізовані функції вже входять в елементний базис.

Даних достатньо для побудови комбінаційних схем функцій збудження тригерів та функцій сигналу виходу, таким чином, і всієї комбінаційної схеми. Автомат будуємо на JK-тригерах. Автомат є синхронним, так як його роботу синхронизує генератор, а JK-тригер є керований перепадом сигналу.

Схема даного автомату виконана згідно з єдиною системою конструкторської документації  (ЄСКД) і наведена у документі «Керуючий автомат. Схема електрична функціональна ІАЛЦ.463626.003 Е2».


3
Синтез комбінаційних схем

3.1 Вступ

На основі «Технічного завдання ІАЛЦ.463626.002 ТЗ» виконуємо синтез комбінаційних схем.

Умова курсової роботи вимагає представлення функції f4 в канонічних формах алгебр Буля, Жегалкіна, Пірса і Шеффера.

3.2 Представлення функцій f4 в канонічній формі алгебри Буля.

В даній алгебрі визначені функції {І, АБО, НЕ}.

3.3 Представлення функцій f4 в канонічній формі алгебри Жегалкіна.

В даній алгебрі визначені функції {І, виключне АБО, const 1}.

3.4 Представлення функцій f4 в канонічній формі алгебри Пірса.

В даній алгебрі визначені функції {АБО-НЕ}.

        

3.5 Представлення функцій f4 в канонічній формі алгебри Шеффера

В даній алгебрі визначені функції {І-НЕ}.

3.6 Визначення належності функції f4 до п’яти чудових класів

1. Дана функція зберігає нуль, так як F(0000)=0.

2. Дана функція зберігає одиницю, так як F(1111)=1.

3. Дана функція не самодвоїсна, так як F(0001)=1, F(1110)=1.

4. Дана функція не монотонна, так як F(0001)=1 < F(0010)=0.

5. Дана форма нелінійна, так як канонічна форма алгебри Жегалкіна, що отримана у підрозділі 3.3 є не лінійним поліномом.

На основі вищесказаного робимо висновок, що функція f4 належить першим двом і не належить останнім трьом передповним класам.

3.7 Мінімізація функції f4 методом невизначених коефіцієнтів

Ідея цього методу полягає у відшуканні ненульових коефіцієнтів при кожній імпліканті. Рівняння для знаходження коефіцієнтів представимо таблицею     (таблиця 3.7.1). Виконаємо ви креслення тих рядків на яких функція приймає нульові значення. Викреслимо вже знайдені нульові коефіцієнти в тих рядках таблиці, що залишилися імпліканти, що залишилися після виконання попередніх дій поглинають ті імпліканти, що розташовані зправа від них.

Таблиця 3.7.1 – таблиця невизначених коефіцієнтів

Отримаємо СДНФ функції:

Построим таблицю покриття(таблиця 3.7.2).

Таблиця 3.7.2 – таблиця покриття

Отримаємо МДНФ функції:

3.8 Мінімізація функції f4 методом Квайна-Мак-Класкі

Виходячи з таблиці істинності функції, запишемо стовпчик ДДНФ, розподіливши терми за кількістю одиниць. Проводимо попарне склеювання між сусідніми групами. Подальше склеювання неможливе.

Виконаємо поглинання термів(рисунок 3.8.1).

 

Рисунок 3.8.1 – поглинання термів

Як можна побачити, ми одержали тіж самі імпліканти, що і при мінімізації методом невизначених коефіцієнтів. Тому результат буде той самий:

3.9 Мінімізація функції f4 методом діаграм Вейча

Виконаємо мінімізацію функції методом Вейча (рисунок 3.9.1). Цей метод дуже зручний при мінімізації функції з кількістю аргументів до чотирьох включно. Кожна клітинка відповідає констітуєнті, а прямокутник з кількох клітинок – імпліканті.

Рисунок 3.9.1 - мінімізацію функції методом Вейча

3.10 Спільна мінімізація функцій f1, f2, f3

Щоб одержати схеми з мінімальними параметрами необхідно виконати сумісну мінімізацію системи функцій та їх заперечень.

Виконаємо мінімізацію системи функцій f1, f2, f3, заданих таблицею істинності (технічного завдання ІАЛЦ.463626.002 ТЗ) методом діаграм Вейча (рисунок 3.10.1).

Рисунок 3.10.1 - мінімізацію системи функцій f1, f2, f3


Виведемо перші чотирі нормальні формі:

           І/АБО

         І-НЕ/І-НЕ

 АБО/І-НЕ

АБО-НЕ/АБО

Реалізуємо системи функцій f1, f2, f3 на елементах І-НЕ/І-НЕ. Реалізація функцій в заданому елементному базисі представлена на рисунку 3.10.2.

Рисунок 3.10.2 – схема систем функцій f1, f2, f3


3.11 Спільна мінімізація заперечень функцій f1, f2, f3

Виконаємо мінімізацію заперечень невизначених систем функцій f1, f2, f3, заданих таблицею істинності (технічного завдання ІАЛЦ.463626.002 ТЗ) методом діаграм Вейча (рисунок 3.11.1).

Рисунок 3.11.1 – мінімізація заперечень функцій


Виведемо перші чотирі нормальні формі:

        І/АБО-НЕ

           І-НЕ/І

   АБО-І

АБО-НЕ/АБО-НЕ

Реалізуємо системи функцій f1, f2, f3 на елементах АБО-НЕ/АБО-НЕ. Реалізація функцій в заданому елементному базисі представлена на рисунку 3.11.2.

Рисунок 3.11.2 - схема систем функцій f1, f2, f3


3
.12 Одержання операторних форм для реалізації на ПЛМ

Одержимо операторне представлення функцій на ПЛМ.

       На ПЛМ можна реалізувати форми {І/АБО, І/АБО-НЕ}.

І/АБО : Всього 4 змінні, 9мплікант, 3 функції.

І/АБО-НЕ : Всього 4 змінні, 9мплікант, 3 функції.

Тому не має різниці яку ПЛМ обрати. Для зразку оберемо ПЛМ(4,9,3).

Побудуємо карту програмування ПЛМ (рисунок 3.12.1).

X4

X3

X2

X1

F1

F2

F3

Рисунок 3.12.1 - мнемонічна схема ПЛМ

Покажемо умовне графічне позначення даної ПЛМ (рисунок 3.12.2)

Рисунок 3.12.2 -  умовне графічне позначення ПЛМ

4 Висновок

Метою даної курсової роботи було закріпити навички абстрактного та структурного синтезу автомата по заданому алгоритму роботи. При синтезі автомата було використане сусіднє кодування, яке бажано робити для більш правильної та стабільної праці пристрою. Також постало питання мінімізації систем функцій для зменшення кількості логічних елементів та збільшення швидкодії схеми.

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

Усі схеми та керуючий автомат були перевірені в программі AFDK 2.0. Перевірка дала позитивні результати.

Також я покращив навички оформлення текстову конструкторську документацію відповідно до діючих стандартів.

5 Список літератури

1) Жабін В.І.,Ткаченко В.В. Логические основы и схемотехника цифровых ЭВМ.–Київ ТОО "Век+",1999.

2) Самофалов К.Г., Корнійчук В.І., Тарасенко В.П. Электронные цифровые вычислительные машины. – К. Вища школа, 1983.

3) Савельєв А.Я. Арифметические и логические основы цифровых автоматов.– Москва: Энергия,1974 г.

4) Поспелов Д.А. Логические методы анализа и синтеза схем.– Москва: Энергия,1974г.

5) Хоуп Г. «Проектирование цифровых вычислительных машин и интегральных схем. » Москва: Мир, 1984 г.

За алгоритмом вказаним на рисунку 2.1 виконати синтез і побудувати функціональну схему управляючого автомату.

Рисунок 2.1 – блок-схема алгоритму


 

А также другие работы, которые могут Вас заинтересовать

82487. Мировое хозяйство, понятие и эволюция. Интеграция в мировой экономике 32.42 KB
  Интеграция в мировой экономике Мировое хозяйство совокупность национальногосударственных и негосударственных структур а также их взаимодействий на основе международного разделения труда и политических контактов. В данной трактовке мировое хозяйство представляет собой единое экономическое пространство мегаэкономику в котором субъектами хозяйственных отношений выступают: национальные экономики стран мира; субъекты мирового бизнеса транснациональные корпорации и их альянсы; институты мирового хозяйства международные экономические...
82488. Международная торговля: свобода торговли и протекционизм 33.52 KB
  Сторонники свободной торговли считают что международная торговля должна развиваться на основе рыночных сил спроса и предложения т. Экономические аргументы в защиту протекционистских мер: с помощью импортных пошлин страна может достичь улучшения условий торговли и увеличения экономического выигрыша; поддержка национальной промышленности на этапе ее зарождения и становления; повышение уровня занятости национальных ресурсов; смягчение кризиса в отраслях испытывающих экономические трудности; ограждение национальной экономики от мировых...
82489. Международная валютная система 30.96 KB
  Основной задачей мировой валютной системы МВС является регулирование сферы международных расчетов для обеспечения устойчивого экономического роста и поддержания равновесия во внешнеторговом обмене. Мировая валютная система представляет собой: определенный набор международных платежных средств; режим обмена валют включая валютные курсы; условия конвертируемости механизм обеспечения валютноплатежными средствами международного оборота; регламентацию форм международных расчетов; режим международных рынков валюты и золота; статус...
82490. Объект и предмет экономической теории. Методология экономической науки 35.64 KB
  Методология экономической науки. Первый раздел имеет методологическое фундаментальное значение так как служит основным средством исследования двух следующих разделов микроэкономики и макроэкономики. Это привело к появлению множества методов исследования экономической теории: Метод научной абстракции Отвлечение в процессе познания от внешних явлений не экономических сторон выделение более глубокой сущности предмета или экономического явления Метод функционального анализа Используется зависимость функцияаргумент для проведения...
82491. Основные направления и школы в экономической теории. Экономические законы и категории 34.86 KB
  Экономические законы и категории. Экономические законы и категории. Различают специфические общие и особенные экономические законы. Специфические экономические законы действуют в пределах исторически определенных форм хозяйствования.
82492. Рынок и условия его возникновения: типы рынков, экономические и неэкономические блага, типы хозяйственных систем, виды и формы собственности 36.72 KB
  Рынок это такая экономическая система которая базируется на частной собственности на средства производства и на принципах самостоятельно независимого принятия решений отдельных хозяйствующих субъектов фирмами или частными лицами. экономическая обособленность производителей в форме частной собственности. виды и формы собственности Собственность можно классифицировать различным образом например: 1 По форме присвоения различных форм собственности индивидуальная коллективная и государственная собственность.
82493. Теория собственности: понятие, виды, формы. Права собственности. Приватизация, ее особенности в России 34.53 KB
  Права собственности. Теория собственности: понятие виды формы Собственность это система экономических отношений между людьми выражающаяся во владении пользовании и распоряжении средствами производства и соответствующей им формы присвоения средств и результатов производства. Собственность можно классифицировать различным образом например: 1 По форме присвоения различных форм собственности индивидуальная коллективная и государственная собственность.
82494. Ограниченность ресурсов и кривая производственных возможностей 43.7 KB
  В широком смысле ограничены прежде всего способности человека взять имеющиеся в природе в изобилии свободные материальные ресурсы при том что в перспективном плане строго дефицитными могут быть лишь невоспроизводимые условия время и лучшие естественные ресурсы. Виды экономических ресурсов природные ресурсы земля недра водные лесные и биологические климатические и рекреационные ресурсы сокращенно земля; трудовые ресурсы люди с их способностью производить товары и услуги сокращенно труд; капитал в форме денег и ценных...
82495. Цена, спрос и предложение. Равновесие по Маршаллу и по Вальрасу. Паутинообразная модель 71.61 KB
  Цена́ количество денег в обмен на которые продавец готов передать продать единицу товара. Цена является коэффициентом обмена конкретного товара на деньги. Спрос на какойлибо товар или услугу это желание и возможность потребителя купить определенное количество товара или услуги по определенной цене в определенный период времени. Объем спроса это то количество товара или услуги которое потребители согласны купить по определенной цене в течении определенного периода времени.