43140

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

Курсовая

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

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

Украинкский

2013-11-03

1.49 MB

4 чел.

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

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

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

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

 

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

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

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

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

                      Група       ІО-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 – блок-схема алгоритму


 

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

29645. Метод наблюдения в социологическом исследовании. Виды наблюдения. Опыт использования в социологии 36.5 KB
  Виды наблюдения. Метод наблюдения в соцом исследовании используется в 2х смыслах широком и узком . В узком смысле – наблюдения – конкретезированный метод соц.
29646. Основные цели и задачи деятельности ИПБ 26 KB
  Активное участие в создании и деятельности ИПБ принимает Минфин РФ. ИПБ РФ объединяет аттестованных профессиональных бухгалтеров и аудиторов. ИПБ России имеет на территории страны свои филиалы и представительства которые являются его обособленными подразделениями.
29647. Особенности бухгалтерского дела на начальной стадии функционирования предприятия 29 KB
  Деятельность организации начинается с ее государственной регистрации. В небольших организациях процедуру регистрации часто проходит именно бухгалтер. Государственная регистрация осуществляется в срок не более чем 5 рабочих дней со дня представления документов в регистрирующий орган. Момент внесения записи регистрирующим органом в государственный реестр признается моментом государственной регистрации.
29648. Особенности бухгалтерского дела на стадии ликвидации 35.5 KB
  Согласно закону несостоятельность признанная арбитражным судом неспособность должника в полном объеме удовлетворять требования кредиторов по денежным обязательствам и или исполнить обязанность по уплате обязательных платежей. Лицами участвующими в деле о банкротстве являются: должник; арбитражный управляющий; конкурсные кредиторы; уполномоченные органы; федеральные органы исполнительной власти а также органы исполнительной власти субъектов Российской Федерации и органы местного самоуправления по месту нахождения должника в случаях...
29649. Особенности бухгалтерского дела на стадии реорганизации организации 42 KB
  № 283 Министерство финансов РФ утвердило Методические указания по формированию бухгалтерской отчетности при осуществлении реорганизации организаций Приказ от 20 мая 2003 г. Решение о реорганизации принимает высший орган управления юридического лица. При добровольной реорганизации собственники юридических лиц акционеры участники пайщики и т.
29650. Международные бухгалтерские профессиональные организации 27 KB
  Был создан для разработки стандартов которые можно было бы распространить на все страны мира. в настоящее время в него входят представители более 100 бухгалтерских организации из 75 стран. Членами Федерации являются представители профессиональных организаций более 70 стран.Объединяет правительства 24 стран включая большинство индустриально развитых государств: Австралию Австрию Канаду Францию германию Японию и др.
29651. Национальная Федерация консультантов и аудиторов 33.5 KB
  Предметом деятельности Федерации являются: проведение конгрессов конференций семинаров и других мероприятий для обмена мнениями по актуальным вопросам развития аудиторскоконсультационной деятельности; участие в подготовке нормативноправовых актов регулирующих аудиторскую и консультационную деятельность; организация взаимодействия с органами законодательной и исполнительной власти Российской Федерации по вопросам касающимся профессиональной деятельности Федерации; содействие внедрению в организацияхчленах Федерации...
29652. Организация автоматизированного рабочего места бухгалтера 26 KB
  При проектировании и создании АРМ бухгалтера можно выделить два основных вида обеспечения: техническое и программное. С вводом в эксплуатацию АРМ бухгалтера на базе ПК происходит распределение функций и операций между бухгалтером и персональным компьютером. Кроме того использование в качестве технического средства АРМ бухгалтера современных персональных ЭВМ дает возможность одновременно с децентрализованной обработкой учетных данных обеспечить интеграцию информационной базы сократить время обработки; ликвидировать разрыв во времени между...
29653. Организация бухгалтерского учета на предприятии 29 KB
  Основные правила организации и ведения бухгалтерского учета для всех предприятий едины. Ведение бухгалтерского учета регламентируется законами нормативными актами и положениями по бухгалтерскому учету. Такие вопросы как организация форма и техника ведения бухгалтерского учета предприятие решает самостоятельно.