| Синтез цифрових схем арифметичних пристроїв[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.
скачати
Зміст Постановка завдання Вихідні дані до курсового проекту Розробка алгоритму множення Розробка структурної схеми пристрою Синтез перетворювача множника Логічний синтез однорозрядного четверичная помножувача-суматора Логічний синтез однорозрядного четверичная суматора Синтез МПА дільника Постановка завдання Курсовий проект передбачає синтез цифрових схем арифметичних пристроїв, що виконують операції додавання, віднімання, множення і ділення над числами, представленими у формі з плаваючою комою в двійковій і двійково-четверичной системах числення. За вихідними даними необхідно розробити: Алгоритм виконання операції множення, для чого потрібно:
перевести вихідні числа з десяткової системи числення в двійково-десяткову; представити числа у формі з плаваючою комою; провести перемножування чисел за алгоритмом "Г" в додаткових розрядах на два розряди одночасно; оцінити похибку обчислення після переведення результату у вихідну систему числення.
Алгоритм виконання операцій додавання і віднімання.
Структурну схему комбінованого пристрою (додавання і множення), що містить вузли для дії над мантиси і порядку, і визначити час множення з урахуванням тимчасових затримок у комбінаційних схемах. Функціональні схеми основних вузлів проектованого суматора-помножувача в заданому логічному базисі. Для цього провести:
логічний синтез комбінаційного однорозрядного четверичная суматора (ОЧС) на основі складеної таблиці істинності для суми доданків з урахуванням перенесення з молодшого розряду, використовуючи при цьому алгоритм вилучення (Рота), та оцінити ефективність мінімізації; логічний синтез однорозрядного комбінаційного четверичная помножувача-суматора (ОЧУС), шляхом мінімізації перемикальних функцій по кожному виходу схеми. Мінімізація виконується з застосуванням карт Карно-Вейча з наступною оцінкою ефективності мінімізації; логічний синтез комбінаційної схеми перетворювача множника (ПМ); побудувати функціональну схему ОЧС на мультиплексорах; побудувати функціональну схему ПМ і ОЧУС в заданому базисі;
Визначити час множення на один розряд і на n розрядів множника. Розробити алгоритм виконання операції ділення. Функціональну схему дільника, представивши його як керуючий автомат, для чого необхідно:
побудувати граф зв'язності автомата; розмітити його для синтезу автомата Мура; побудувати таблицю переходів автомата; визначити переключательние функції вихідних сигналів і сигналів зворотного зв'язку; побудувати функціональну схему подільника на базі програмованої логічної матриці і заданих тригерів.
Вихідні дані до курсового проекту В якості вихідних даних до курсового проекту задається наступне: Вихідні операнди - десяткові числа з цілою і дробовою частиною, над якими проводиться операція множення (36,39 & 53,25). Алгоритм виконання операції множення Г. Метод прискореного множення на базі якого будується помножувач:
Перетворення множника в обох випадках проводиться для виключення з процесу множення діади множника 11. Двійкові коди четверичная цифр множимо для роботи в двійково-четверичной системі числення (подається кодом: 0 4 - 00, 1 4 - 11, 2 4 - 01, 3 4 - 10). Множник представляється звичайним весомозначним кодом: 0 4 - 00, 1 4 - 01, 2 4 - 10, 3 4 - 11.
Тип синтезованого пристрою множення, визначається основними структурними вузлами, на базі яких будується помножувач:
Спосіб мінімізації та логічний базис для апаратної реалізації ОЧС і ОЧУС (функціонально повний базис представлений функцією x 1 + x 2:
Табл іца 1. Таблиця істинності: X1 | X2 | 1 | не 1 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 0 |
ОЧС реалізується на мультиплексорах). Алгоритм виконання операції ділення:
Клас синтезованого мікропрограмного автомата: Мура.
Логічний базис для апаратної реалізації дільника, як керуючого автомата: ПЛМ і тригери для організації ланцюга зворотного зв'язку (Т-тригери).
Розробка алгоритму множення Переклад співмножників з десяткової системи числення в четверичная:
Множимо 36 | 4 0,39 Мн 4 = 210,1203 36 9 | 4 квітня 0 2 серпня 1,56 Мн 2 / 4 = 011100,11010010 1 квітня 2,24 4 0,96 4 3,84 4 3,36 МНОЖИТЕЛЬ 53 | 4 0,25 Мт 4 = 311,1 52 13 | 4 4 Мт 2 / 4 = 110101,01 1 12 3 1,00 1 Запишемо співмножник у формі з плаваючою комою в прямому коді:
Мн = 0,01110011010010 Р мн = 0,0010 +03 закодований за завданням Мт = 0,11010101 Р мт = 0,0011 +03 незакодірованний за завданням [Мт] д = Мт = 0,3111 4 = 0,11010101 2 / 4 [Мт] дп = 0,101010101 2 / 4 Мн = 0,2101203 [- Мн] д = 3,1232131 Множення двох чисел з плаваючою комою на 2 розряди множника одночасно в додаткових кодах зводиться до складання порядків, формуванню знака твори, перетворенню розрядів множника з метою виключення діади 11, і перемножування мантис співмножників.
Порядок твору буде дорівнює: Р мн = 0.0010 + 03 Р мт = 0.0011 03 Р = 0.1101 12 результат закодований у відповідності із завданням на кодування множимо. Знак твору визначається сумою за модулем два знаків співмножників, тобто: зн Мн + зн Мт = 0 + 0 = 0. Для множення мантис необхідно попередньо перетворити множник, щоб виключити діаду 11 (3 4), замінивши її на тріаду 101. Перемноження мантис за алгоритмом «Г» наведено втабліце 2: [Мт] дп = 0,101010101 2 / 4 Мн = 0,2101203 [-Мн] д = 3,1232131 Таблиця 2. Множення за алгоритмом "Г". Четверичная с / р | ЗНАК | РЕГІСТР РЕЗУЛЬТАТУ | ДІЇ | 0. | 000000000000 |
| 0. | 000000000000 | +0 | 0. | 000000000000 |
| 0. | 021012030000 | + Мн>> 1 | 0. | 021012030000 |
| 3. | 331232131000 | -Мн>> 2 | 10. | 012310221000 |
| 0. | 000210120300 | + Мн>> 3 | 10. | 013121001300 |
| 0. | 000021012030 | + Мн>> 4 | 0. | 013202013330 |
| 0. | 000002101203 | + Мн>> 5 | 0. | 013210121133 | Рез. У доп коді | 0. | 013210121133 | Рез. У пр. коді |
| 132101,21133 |
|
| 1937,5927734375 | 10 с / с |
Після закінчення множення необхідно оцінити похибку обчислень. Для цього отримане твір (Мн * Мт 4 = 013 210 121 133 Р Мн * Мт = 6) приводиться до нульового порядку, а потім переводиться в десяткову систему числення:
Мн * Мт 4 = +132101,21133 Р Мн * Мт = 0; Мн * Мт 10 = +1937,5927734375. Результат прямого перемноження операндів дає таке значення: Мн 10 * Мт 10 = 36,39 * 53,25 = 1937,7675. Абсолютна похибка: D = 1937,7675 - +1937,5927734375 = 0,17473. Відносна похибка: D 0,17473 ( = 0,00901%) Мн * Мт 1937,7675 Ця похибка є сумарної, накопиченої за рахунок наближеного перекладу з 10 с / с в четверичная обох співмножників, а також за рахунок округлення отриманого результату твори. У разі негативного множимо: [Мт] дп = 0,101010101 2 / 4 Мн = - 0,2101203 [Мн] д = 3,1232131 [- Мн] д = 0,2101203 Четверичная с / р | ЗНАК | РЕГІСТР РЕЗУЛЬТАТУ | ДІЇ | 0. | 000000000000 |
| 0. | 000000000000 | +0 | 0. | 000000000000 |
| 3. | 312321310000 | + Мн>> 1 | 3. | 312321310000 |
| 0. | 002101203000 | -Мн>> 2 | 3. | 321023113000 |
| 3. | 333123213100 | + Мн>> 3 | 10. | 320212332100 |
| 3. | 3 33312321310 | + Мн>> 4 | 10. | 320131320010 |
| 3. | 33 3331232131 | + Мн>> 5 | 10. | 320123212201 | Рез. У доп коді | 1. 3 - 4 = 1 | 013210121133 |
| Рез. У пр. коді |
| 132101,21133 |
|
| 1937,5927734375 | 10 с / с |
Розробка структурної схеми пристрою
Структурна схема будується на основі наступних блоків
зрушення
Dn Q1
З Qn
S1
S2
"+1"
Призначений для зберігання і зсуву n-розрядного значення числа. Регістр має n інформаційних входів D 1 - Dn, керуючий вхід дозволу запису в регістр С, керуючі входи зсуву вмісту регістра вліво S 1 і вправо S 2, керуючий вхід доповнення 1 до вмісту регістра "+1", і n виходів Q 1 - Qn . Всі керуючі функції виконуються при вступі 1 на відповідний керуючий вхід.
Розрядність регістра результату повинна бути на одиницю більше, ніж розрядність вихідних доданків, щоб передбачити можливість виникнення при підсумовуванні переносу.
R
P 2 Р1
від молодшого
ОЧУС
ОЧУС
до старшого
ОЧУС
Мн Мт
ОЧУС призначений для отримання однієї четверичной цифри шляхом перемноження діади множимо (Мн) і діади множника (Мт), і додавання до отриманого результату переносу від молодшого ОЧУС (P 1).
Якщо пристрій працює як суматор, то обидва доданків послідовно (за 2 такти) заносяться в регістр множимо, а на керуючий вхід ФДК F 2 надходить «1». На виходах ФДК формується додатковий код першого доданка з урахуванням знака. Перший доданок без змін повинно бути записано в регістр результату, тому керуючі сигнали, що надходять на входи «h» всіх ОЧУС, дозволяють переписати на виходи ОЧУС розряди першого доданка без змін. Якщо на вхід «h» надходить «0», то ОЧУС перемножує розряди Мн і Мт і додає до отриманого результату перенесення з попереднього ОЧУС.
Якщо пристрій працює як помножувач, то множимое і множник розміщуються у відповідні регістри, а на керуючий вхід ФДК F 2 надходить «0». Діада множника надходить на входи ПМ.
Оскільки на входи ОЧУС з регістра Мт не можуть прийти коди «3», в таблиці істинності роботи ОЧУС будуть міститися 16 байдужих вхідних наборів.
Після ОЧУС часткові твори складаються між собою в ОЧС (на першому такті йде додавання з нулем).
Часткові суми зберігаються в регістрі результату.
S
P2 P 1
А В
Призначений для підсумовування двох четверичная цифр і додавання до отриманої суми одиниці переносу від попереднього ОЧС. Формує одиницю перенесення в наступний ОЧС.
У ОЧС перший доданок складається з нулем, записаним в регістрі результату, і переписується без змін в регістр результату. На другому такті другий доданок з регістра множимо через ланцюжок ОЧУС потрапляє на входи ОЧС і складається з перших складових, що зберігаються в регістрі результату. Сума зберігається в регістрі результату. Якщо пристрій працює як суматор, ніяких зрушень вмісту регістрів не проводиться.
Знак Yn Y 1
f 1
f 2
Знак Xn X 1
Призначений для отримання додаткового коду багаторозрядного четверичная числа. ФДК має n двійкових входів (Х1-Х n), n двійкових виходів (Y 1 - Yn), окремий вхід для знаку преутвореного числа, а також керуючі входи (f 1) та (f 2). При подачі керуючого сигналу ("1") на вхід f 1 ФДК формує додатковий код числа у сооответствії з його знайомий. При подачі керуючого сигналу ("1") на вхід f 2 ФДК формує подвійний додатковий код числа. Принцип роботи ФДК залежно від керуючих сигналів див. у таблиці 3.
Таблиця 3. Робота ФДК.
F1 F2 | Результат на виході ФДК |
0 0 | доп. код множимо |
0 1 | доп. код доданка |
1 0 | подвійний доп. код множимо (змінює знак Мн) |
1 січня | доп. код доданка |
Синтез перетворювача множника
Завданням ПМ є виключити з множника діади 11, замінивши їх на тріади. Регістр множника є зсувними, після кожного такту множення його вміст зсувається на 2 двійкових розряди, і в кінці множення регістр обнуляється. Вихід 3 ПМ переходить в одиничний стан, якщо поточна діада містить заперечення (01). У цьому випадку ініціалізується керуючий вхід F 1 формувача додаткового коду (ФДК), і на виходах ФДК формується подвійний додатковий код множимо (множення на -1).
На виходах 1,2 ПМ формуються діади перетвореного множника, які надходять на входи ОЧУС разом з діади множимо. На трьох виходах ОЧУС формується результат множення Діад Мн * Мт + перенесення з попереднього ОЧУС. Максимальної цифрою в діаді перетвореного множника є двійка, тому перенесення, формований ОЧУС, може бути тільки двійковим:
3 * 2 = 1 2
max ma х max
Мн Мт перенесення
Табл.4. Таблиця істинності перетворювача множника.
D1 | D2 | D3 | P1 | P2 | F |
0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 1 | 0 | 1 | 0 |
0 | 1 | 0 | 0 | 1 | 0 |
0 | 1 | 1 | 1 | 0 | 0 |
1 | 0 | 0 | 1 | 0 | 1 |
1 | 0 | 1 | 0 | 1 | 1 |
1 | 1 | 0 | 0 | 1 | 1 |
1 | 1 | 1 | 0 | 0 | 0 |
Виходячи з вище викладеної таблиці синтезується схема.
_ _ _ _ _ _ _ _ |
F = x1x2x3 + x1x2x3 + x1x2x3 = x1x2 + x1x3 = x1 (x2 + x3) |
_ _ _ |
P1 = x1x2x3 + x1x2x3 |
_ _ _ _ _ _ _ _ |
P2 = x1x2x3 + x1x2x3 + x1x2x3 + x1x2x3 = x2x3 + x2x3 = x2 Å x3 |
Перетворювач множника.
Структурна схема пристрою приведена на малюнку в додатку. Вона містить регістри: множимо (Рг Мн), множника (Рг Мт), результату (Рг Рез), формувачі додаткового коду (ФДК), 16 блоків ОЧС, 15 блоків ОЧУС і перетворювач множника (ПМ).
Пристрій множення працює наступним чином:
Вихідні співмножники записуються в регістри (Рг Мн, Рг Мт) Рг Рез обнуляється.
З виходів ФДК на входи ОЧУС надходять по 2 двійкові цифри. Результат операції надходить у ОЧС, де сумується з вмістом Рг Рез і записується знову в Рг Рез.
Після проведення цих операцій відбувається зсув Рг Мн, Рг Мт.
Якщо на вхід "h" подається "1" те ОЧУС стають "прозорими" і пристрій працює як суматор завдяки ОЧС. Слогани послідовно (за 2 такти) заносяться в регістр множимо.
Тимчасові витрати на множення співмножників визначаються в основному витратами на освіту часткових творів, одержуваних на виходах ОЧУС, і приблизно рівні:
Ту = 8 (t СДВ + t ПМ + t ФДК + 15 t ОЧУС + 16 t ОЧС), де:
t ОЧС-час формування одиниці переносу в ОЧС
t ОЧУС - час множення на одному ОЧУС
t СДВ-час зсуву множимо (множника)
t ПМ - час затримки в перетворювачі множника
t ФДК - час затримки на ФДК
Насправді, операції виконуються паралельно в декількох вузлах, і час затримки буде визначаться найбільшою складовою (або 15 t ОЧУС, або 15 t ОЧУС, в залежності від конкретної реалізації).
Логічний синтез однорозрядного четверичная помножувача-суматора
ОЧУС - це комбінаційне пристрій, що має 6 входів (2 розряду з регістра МН, 2 розряду з регістра Мт, вхід перенесення і керуючий вхід h) і 3 виходи. Принцип роботи ОЧУС описується за допомогою таблиці істинності (табл.5).
Розряди множника закодовані: 0 - 00; 1 - 01; 2 - 10; 3 - 11.
Розряди множимо закодовані: 0 - 00; 1 - 11; 2 - 01; 3 - 10.
Керуючий вхід h визначає тип операції: 0 - множення закодованих цифр, що надійшли на інформаційні входи, і додавання переносу; 1 - вивід на виходи без зміни значення розрядів, що надійшли з регістра множимо.
Табл. 5
пер. | Мн | Мт | упр. |
| Перенесення | Результат | Результат операції |
|
Р1 | Х1 | Х2 | У1 | У2 | h |
| Р | Q1 | Q2 | У четверичной с / р |
|
0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 * 0 +0 = 0 0 |
|
0 | 0 | 0 | 0 | 0 | 1 |
| 0 | 0 | 0 | Вихід - код «0 0» |
|
0 | 0 | 0 | 0 | 1 | 0 |
| 0 | 0 | 0 | 0 * 1 +0 = 0 0 |
|
0 | 0 | 0 | 0 | 1 | 1 |
| 0 | 0 | 0 | Вихід - код «0 0» |
|
0 | 0 | 0 | 1 | 0 | 0 |
| 0 |
0 | 0 | 0 * 2 +0 = 0 0 |
| 0 | 0 | 0 | 1 | 0 | 1 |
| 0 | 0 | 0 | Вихід - код «00» |
|
0 | 0 | 0 | 1 | 1 | 0 |
| Х | Х | Х | 0 * 3 +0 = 00 | * |
0 | 0 | 0 | 1 | 1 | 1 |
| Х | Х | Х | Вихід - код «00» | * |
0 | 0 | 1 | 0 | 0 | 0 |
| 0 | 0 | 0 | 2 * 0 +0 = 00 |
|
0 | 0 | 1 | 0 | 0 | 1 |
| 0 | 0 | 1 | Вихід - код «02» |
|
0 | 0 | 1 | 0 | 1 | 0 |
| 0 | 0 | 1 | 2 * 1 +0 = 02 |
|
0 | 0 | 1 | 0 | 1 | 1 |
| 0 | 0 | 1 | Вихід - код «02» |
|
0 | 0 | 1 | 1 | 0 | 0 |
| 1 | 0 | 0 | 2 * 2 +0 = 1 0 |
|
0 | 0 | 1 | 1 | 0 | 1 |
| 0 | 0 | 1 | Вихід - код «02» |
|
0 | 0 | 1 | 1 | 1 | 0 |
| Х | Х | Х | 2 * 3 +0 = 1 2 | * |
0 | 0 | 1 | 1 | 1 | 1 |
| Х | Х | Х | Вихід - код «02» | * |
0 | 1 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 3 * 0 +0 = 00 |
|
0 | 1 | 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | Вихід - код «03» |
|
0 | 1 | 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 3 * 1 +0 = 03 |
|
0 | 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | Вихід - код «03» |
|
0 | 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 3 * 2 +0 = 12 |
|
0 | 1 | 0 | 1 | 0 | 1 |
| 0 | 1 | 0 | Вихід - код «03» |
|
0 | 1 | 0 | 1 | 1 | 0 |
| Х | Х | Х | 3 * 3 +0 = 21 | * |
0 | 1 | 0 | 1 | 1 | 1 |
| Х | Х | Х | Вихід - код «03» | * |
0 | 1 | 1 | 0 | 0 | 0 |
| 0 | 0 | 0 | 1 * 0 +0 = 00 |
|
0 | 1 | 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | Вихід - код «01» |
|
0 | 1 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 1 * 1 +0 = 01 |
|
0 | 1 | 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | Вихід - код «01» |
|
0 | 1 | 1 | 1 | 0 | 0 |
| 0 | 0 | 1 | 1 * 2 +0 = 02 |
|
0 | 1 | 1 | 1 | 0 | 1 |
| 0 | 1 | 1 | Вихід - код «01» |
|
0 | 1 | 1 | 1 | 1 | 0 |
| Х | Х | Х | 1 * 3 +0 = 03 | * |
0 | 1 | 1 | 1 | 1 | 1 |
| Х | Х | Х | Вихід - код «01» | * |
1 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 * 0 +1 = 01 |
|
1 | 0 | 0 | 0 | 0 | 1 |
| 0 | 0 | 0 | Вихід - код «00» |
|
1 | 0 | 0 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 * 1 +1 = 01 |
|
1 | 0 | 0 | 0 | 1 | 1 |
| 0 | 0 | 0 | Вихід - код «00» |
|
1 | 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 * 2 +1 = 01 |
|
1 | 0 | 0 | 1 | 0 | 1 |
| 0 | 0 | 0 | Вихід - код «00» |
|
1 | 0 | 0 | 1 | 1 | 0 |
| Х | Х | Х | 0 * 3 +1 = 01 | * |
1 | 0 | 0 | 1 | 1 | 1 |
| Х | Х | Х | Вихід - код «00» | * |
1 | 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 1 | 2 * 0 +1 = 01 |
|
1 | 0 | 1 | 0 | 0 | 1 |
| 0 | 0 | 1 | Вихід - код «02» |
|
1 | 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 0 | 2 * 1 +1 = 03 |
|
1 | 0 | 1 | 0 | 1 | 1 |
| 0 | 0 | 1 | Вихід - код «02» |
|
1 | 0 | 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 2 * 2 +1 = 11 |
|
1 | 0 | 1 | 1 | 0 | 1 |
| 0 | 0 | 1 | Вихід - код «02» |
|
1 | 0 | 1 | 1 | 1 | 0 |
| Х | Х | Х | 2 * 3 +1 = 13 | * |
1 | 0 | 1 | 1 | 1 | 1 |
| Х | Х | Х | Вихід - код «02» | * |
1 | 1 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 3 * 0 +1 = 01 |
|
1 | 1 | 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | Вихід - код «03» |
|
1 | 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 0 | 3 * 1 +1 = 10 |
|
1 | 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | Вихід - код «03» |
|
1 | 1 | 0 | 1 | 0 | 0 |
| 1 | 1 | 0 | 3 * 2 +1 = 13 |
|
1 | 1 | 0 | 1 | 0 | 1 |
| 0 | 1 | 0 | Вихід - код «03» |
|
1 | 1 | 0 | 1 | 1 | 0 |
| Х | Х | Х | 3 * 3 +1 = 12 | * |
1 | 1 | 0 | 1 | 1 | 1 |
| Х | Х | Х | Вихід - код «03» | * |
1 | 1 | 1 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 * 0 +1 = 01 |
|
1 | 1 | 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | Вихід - код «01» |
|
1 | 1 | 1 | 0 | 1 | 0 |
| 0 | 0 | 1 | 1 * 1 +1 = 02 |
|
1 | 1 | 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | Вихід - код «01» |
|
1 | 1 | 1 | 1 | 0 | 0 |
| 0 | 1 | 0 | 1 * 2 +1 = 03 |
|
1 | 1 | 1 | 1 | 0 | 1 |
| 0 | 1 | 1 | Вихід - код «01» |
|
1 | 1 | 1 | 1 | 1 | 0 |
| Х | Х | Х | 1 * 3 +1 = 10 | * |
1 | 1 | 1 | 1 | 1 | 1 |
| Х | Х | Х | Вихід - код «01» | *
|
У таблиці виділено 16 байдужих наборів, тому що на входи ОЧУС з розрядів множника не може вступити код 11.
Таблиця 6. Шістнадцять байдужих наборів для ОЧУС.
P1 | X1 | X2 | Y1 | Y2 | H |
0 | 0 | 0 | 1 | 1 | 0 |
0 | 0 | 0 | 1 | 1 | 1 |
0 | 0 | 1 | 1 | 1 | 0 |
0 | 0 | 1 | 1 | 1 | 1 |
0 | 1 | 0 | 1 | 1 | 0 |
0 | 1 | 0 | 1 | 1 | 1 |
0 | 1 | 1 | 1 | 1 | 0 |
0 | 1 | 1 | 1 | 1 | 1 |
1 | 0 | 0 | 1 | 1 | 0 |
1 | 0 | 0 | 1 | 1 | 1 |
1 | 0 | 1 | 1 | 1 | 0 |
1 | 0 | 1 | 1 | 1 | 1 |
1 | 1 | 0 | 1 | 1 | 0 |
1 | 1 | 0 | 1 | 1 | 1 |
1 | 1 | 1 | 1 | 1 | 0 |
1 | 1 | 1 | 1 | 1 | 1 |
Таблиця 7. Одиничні набори для виходу Q 1 ОЧУС:
P1 | X1 | X2 | Y1 | Y2 | h |
0 | 1 | 0 | 0 | 0 | 1 |
0 | 1 | 0 | 0 | 1 | 0 |
0 | 1 | 0 | 0 | 1 | 1 |
0 | 1 | 0 | 1 | 0 | 1 |
0 | 1 | 1 | 0 | 0 | 1 |
0 | 1 | 1 | 0 | 1 | 0 |
0 | 1 | 1 | 0 | 1 | 1 |
0 | 1 | 1 | 1 | 0 | 1 |
1 | 0 | 0 | 0 | 0 | 0 |
1 | 0 | 0 | 0 | 1 | 0 |
1 | 0 | 0 | 1 | 0 | 0 |
1 | 0 | 1 | 0 | 0 | 0 |
1 | 0 | 1 | 0 | 1 | 0 |
1 | 0 | 1 | 1 | 0 | 0 |
1 | 1 | 0 | 0 | 0 | 0 |
1 | 1 | 0 | 0 | 0 | 1 |
1 | 1 | 0 | 0 | 1 | 1 |
1 | 1 | 0 | 1 | 0 | 0 |
1 | 1 | 0 | 1 | 0 | 1 |
1 | 1 | 1 | 0 | 0 | 0 |
1 | 1 | 1 | 0 | 0 | 1 |
1 | 1 | 1 | 0 | 1 | 1 |
1 | 1 | 1 | 1 | 0 | 0 |
1 | 1 | 1 | 1 | 0 | 1 |
Таблиця 8. Карта Карно-Вейча для одиничних наборів виходу Q 1 ОЧУС:
1 |
| * | 1 |
| * | 1 |
|
1 | 1 | * | 1 | 1 | * | 1 | 1 |
1 | 1 | * | 1 | 1 | * | 1 | 1 |
1 |
| * | 1 |
| * | 1 |
|
1 | 1 | * | 1 |
| * |
|
|
|
| * |
|
| * |
|
|
|
| * |
|
| * |
|
|
1 | 1 | * | 1 |
| * |
|
|
Q1 = X1 H + P1 X1 Y2 + P1 Y2 H + P1 X1 H =
= X1 (H + P1 Y2) + P1 H (Y2 X1)
Таблиця 9. Одиничні набори для виходу Q 2 ОЧУС:
P1 | X1 | X2 | Y1 | Y2 | h |
0 | 0 | 1 | 0 | 0 | 1 |
0 | 0 | 1 | 0 | 1 | 0 |
0 | 0 | 1 | 0 | 1 | 1 |
0 | 0 | 1 | 1 | 0 | 1 |
0 | 1 | 0 | 1 | 0 | 0 |
0 | 1 | 1 | 0 | 0 | 1 |
0 | 1 | 1 | 0 | 1 | 0 |
0 | 1 | 1 | 0 | 1 | 1 |
0 | 1 | 1 | 1 | 0 | 0 |
0 | 0 | 1 | 1 | 0 | 1 |
1 | 0 | 0 | 0 | 0 | 0 |
1 | 0 | 0 | 0 | 1 | 0 |
1 | 0 | 0 | 1 | 0 | 0 |
1 | 0 | 1 | 0 | 0 | 0 |
1 | 0 | 1 | 0 | 0 | 1 |
1 | 0 | 1 | 0 | 1 | 1 |
1 | 0 | 1 | 1 | 0 | 0 |
1 | 1 | 1 | 1 | 0 | 1 |
1 | 1 | 0 | 0 | 0 | 0 |
1 | 1 | 1 | 0 | 0 | 0 |
1 | 1 | 1 | 0 | 0 | 1 |
1 | 1 | 1 | 0 | 1 | 0 |
1 | 1 | 1 | 0 | 1 | 1 |
1 | 1 | 1 | 1 | 0 | 1 |
Таблиця 10. Карта Карно-Вейча для нульових наборів виходу Q 2 ОЧУС:
| 1 | * | 1 |
| * | 1 | 1 |
1 | 1 | * | 1 | 1 | * | 1 | 1 |
|
| * |
|
| * |
|
|
|
| * | 1 |
| * |
| 1 |
| 1 | * |
| 1 | * |
| 1 |
|
| * |
|
| * |
|
|
1 | 1 | * | 1 | 1 | * | 1 | 1 |
|
| * |
| 1 | * | 1 | 1 |
Q2 = (X2 + H) * (P1 + X2 + Y1) * (P1 + Y1 + Y2 + H) * (X1 + X2 + Y2) * (P1 + X1 + Y1 + Y2 + H) * * (P1 + X1 + X2 + Y2 + H) * (P1 + X1 + Y1 + H)
Таблиця 11. Одиничні набори для виходу перенесення ОЧУС P 2:
P1 | X1 | X2 | Y1 | Y2 | h |
0 | 0 | 1 | 1 | 0 | 0 |
0 | 1 | 0 | 1 | 0 | 0 |
1 | 0 | 1 | 1 | 0 | 0 |
1 | 1 | 0 | 0 | 1 | 0 |
1 | 1 | 0 | 1 | 0 | 0 |
Таблиця 12. Карта Карно-Вейча для одиничних наборів виходу перенесення ОЧУС P:
| 1 | * | 1 | 1 | * |
|
|
|
| * |
|
| * |
|
|
|
| * |
|
| * |
|
|
|
| * |
|
| * |
|
|
|
| * | 1 | 1 | * |
|
|
|
| * |
|
| * |
|
|
|
| * |
|
| * |
|
|
|
| * |
|
| * |
|
|
P = X1 X2 Y1 H + X1 X2 Y1 H + P1 X1 X2 Y2 H =
= H X2 X1 (Y1 + P1 Y2) + X1 X2 Y1 H = H (X1 X2 Y1 + X1 X2 (Y1 + P1 Y2))
Ефективність мінімізації визначається коефіцент мінімізації. Він розраховується за наступною формулою:
Ціна вихідного покриття
Коеф .=-----------------------------------------
Ціна мінімального покриття
Таблиця 13. Коефіцієнт мінімізації.
| Ціна вихідного покриття | Ціна мінімального покриття | Коефіцент мінімізації |
Q1 | 154 | 15 | 10,27 |
Q2 | 154 | 32 | 4,81 |
P2 | 35 | 14 | 2,5 |
Логічний синтез однорозрядного четверичная суматора
ОЧС - це комбінаційне пристрій, що має 5 входів (2 розряду одного доданка, 2 розряду другому доданку і вхід переносу) і 3 виходи. Принцип роботи ОЧС описується за допомогою таблиці істинності (табл. 3).
Розряди обох доданків закодовані: 0 - 00; 1 - 11; 2 - 01; 3 - 10.
Таблиця істинності функціонування ОЧС будується для п'яти змінних, чотири з яких (А1, А2, В1, В2) є виходами ОЧУС, а п'ята - міжрозрядних перенесення з ОЧС суміжного старшого розряду пристрою множення. Четверичная цифра суми як діада S 1 S 2 в таблиці істинності утворюється з урахуванням прийнятого кодування четверичная цифр.
Табл. 14
À1 | À2 | У 1 | У 2 | p | P | S1 | S2 | в четверичной с / р |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 + 0 +0 = 0 0 |
0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 0 + 0 +1 = 0 1 |
0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 + 2 +0 = 02 |
0 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 0 + 2 +1 = 03 |
0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 + 3 +0 = 03 |
0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 0 +3 +1 = 10 |
0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 +1 +0 = 0 1 |
0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 0 +1 +1 = 02 |
0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 2 +0 +0 = 02 |
0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 2 +0 +1 = 03 |
0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 2 +2 +0 = 10 |
0 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 2 +2 +1 = 11 |
0 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 2 +3 +0 = 11 |
0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 2 +3 +1 = 12 |
0 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 2 +1 +0 = 03 |
0 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 2 +1 +1 = 10 |
1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 3 +0 +0 = 03 |
1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 3 +0 +1 = 10 |
1 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 3 +2 +0 = 11 |
1 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | 3 +2 +1 = 12 |
1 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 3 +3 +0 = 12 |
1 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 3 +3 +1 = 13 |
1 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 3 +1 +0 = 10 |
1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 3 +1 +1 = 11 |
1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 +0 +0 = 01 |
1 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 1 +0 +1 = 02 |
1 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 1 +2 +0 = 03 |
1 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 1 +2 +1 = 10 |
1 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 1 +3 +0 = 10 |
1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 +3 +1 = 11 |
1 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 +1 +0 = 02 |
1 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 1 +1 +1 = 03 |
Байдужі набори в таблиці істинності відсутні тому зі старших виходів ОЧУС можуть прийти коди 0, 1, 2 і 3.
Таблиця 15. Одиничні набори для виходу перенесення P ОЧС.
A1 | A2 | У 1 | У 2 | p |
0 | 0 | 1 | 0 | 1 |
0 | 1 | 0 | 1 | 0 |
0 | 1 | 0 | 1 | 1 |
0 | 1 | 1 | 0 | 0 |
0 | 1 | 1 | 0 | 1 |
0 | 1 | 1 | 1 | 1 |
1 | 0 | 0 | 0 | 1 |
1 | 0 | 0 | 1 | 0 |
1 | 0 | 0 | 1 | 1 |
1 | 0 | 1 | 0 | 0 |
1 | 0 | 1 | 0 | 1 |
1 | 0 | 1 | 1 | 0 |
1 | 0 | 1 | 1 | 1 |
1 | 1 | 0 | 1 | 1 |
1 | 1 | 1 | 0 | 0 |
1 | 1 | 1 | 0 | 1 |
Таблиця 16. Одиничні набори для виходу S 1 ОЧС.
À1 | À2 | У 1 | У 2 | p |
0 | 0 | 0 | 0 | 1 |
0 | 0 | 0 | 1 | 1 |
0 | 0 | 1 | 0 | 0 |
0 | 0 | 1 | 1 | 0 |
0 | 1 | 0 | 0 | 1 |
0 | 1 | 0 | 1 | 1 |
0 | 1 | 1 | 0 | 0 |
0 | 1 | 1 | 1 | 0 |
1 | 0 | 0 | 0 | 0 |
1 | 0 | 0 | 1 | 0 |
1 | 0 | 1 | 0 | 1 |
1 | 0 | 1 | 1 | 1 |
1 | 1 | 0 | 0 | 0 |
1 | 1 | 0 | 1 | 0 |
1 | 1 | 1 | 0 | 1 |
1 | 1 | 1 | 1 | 1 |
Таблиця 17. Одиничні набори для виходу S 2 ОЧС.
À1 | À2 | У 1 | У 2 | p |
0 | 0 | 0 | 0 | 1 |
0 | 0 | 0 | 1 | 0 |
0 | 0 | 1 | 1 | 0 |
0 | 0 | 1 | 1 | 1 |
0 | 1 | 0 | 0 | 0 |
0 | 1 | 0 | 1 | 1 |
0 | 1 | 1 | 0 | 0 |
0 | 1 | 1 | 0 | 1 |
1 | 0 | 0 | 1 | 0 |
1 | 0 | 0 | 1 | 1 |
1 | 0 | 1 | 0 | 0 |
1 | 0 | 1 | 1 | 1 |
1 | 1 | 0 | 0 | 0 |
1 | 1 | 0 | 0 | 1 |
1 | 1 | 1 | 0 | 1 |
1 | 1 | 1 | 1 | 0 |
Алгоритм Рота для виходу перенесення ОЧС
Відшукування безлічі L-екстремалів
Z 0 = {Æ}; C 0 = L;
Безліч С0: 11101; 00101; 01010; 01011; 01100; 01101; 01111; 10001;
10010; 10011; 10100; 10101; 10110; 10111; 11011.
C0 * C0 | 11101 | 00101 | 01010 | 01011 | 01100 | 01101 | 01111 | 10001 | 10010 | 10011 | 10100 | 10101 | 10110 | 10111 | 11011 |
11101 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
00101 | yy101 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
01010 | y1yyy | 0yyyy |
|
|
|
|
|
|
|
|
|
|
|
|
|
01011 | y1yy1 | 0yyy1 | 0101x |
|
|
|
|
|
|
|
|
|
|
|
|
01100 | y110y | 0y10y | 01yy0 | 01yyy |
|
|
|
|
|
|
|
|
|
|
|
01101 | x1101 | 0x101 | 01yyy | 01yy1 | 0110x |
|
|
|
|
|
|
|
|
|
|
01111 | y11y1 | 0y1y1 | 01y1y | 01x11 | 011yy | 011x1 |
|
|
|
|
|
|
|
|
|
10001 | 1yy01 | y0y01 | yy0yy | yy0y1 | yyy0y | yyy01 | yyyy1 |
|
|
|
|
|
|
|
|
10010 | 1yyyy | y0yyy | yy010 | yy01y | yyyy0 | yyyyy | yyy1y | 100yy |
|
|
|
|
|
|
|
10011 | 1yyy1 | y0yy1 | yy01y | yy011 | yyyyy | yyyy1 | yyy11 | 100x1 | 1001x |
|
|
|
|
|
|
10100 | 1y10y | y010y | yyyy0 | yyyyy | yy100 | yy10y | yy1yy | 10y0y | 10yy0 | 10yyy |
|
|
|
|
|
10101 | 1x101 | x0101 | yyyyy | yyyy1 | yy10y | yy101 | yy1y1 | 10x01 | 10yyy | 10yy1 | 1010x |
|
|
|
|
10110 | 1y1yy | y01yy | yyy10 | yyy1y | yy1y0 | yy1yy | yy11y | 10yyy | 10x10 | 10y1y | 101x0 | 101yy |
|
|
|
10111 | 1y1y1 | y01y1 | yyy1y | yyy11 | yy1yy | yy1y1 | yy111 | 10yy1 | 10y1y | 10x11 | 101yy | 101x1 | 1011x |
|
|
11011 | 11yy1 | yyyy1 | y101y | x1011 | y1yyy | y1yy1 | y1y11 | 1y0y1 | 1y01y | 1x011 | 1yyyy | 1yyy1 | 1yy1y | 1yy11 |
|
11100 | 1110x | yy10y | y1yy0 | y1yyy | x1100 | y110y | y11yy | 1yy0y | 1yyy0 | 1yyyy | 1x100 | 1y10y | 1y1y0 | 1y1yy | 11yyy |
Куби, що утворилися в цій таблиці, утворюють безліч A 1. Безліч C 1 отримуємо за формулою: C 1 = A 1 È (C 0 - Z 0)
Безліч C1: x1101; 1x101; 1110x; 0x101; x0101; 0101x; 01x11; x1011; 0110x; x1100; 011x1; 100x1; 10x01; 1001x; 10x10; 10x11; 1x011; 1010x; 101x0; 1x100; 101x1; 1011x.
C1 * A1 | x1101 | 1x101 | 1110x | 0x101 | x0101 | 0101x | 01x11 | x1011 | 0110x | x1100 | 011x1 | 100x1 | 10x01 | 1001x | 10x10 | 10x11 | x011 | 1010x | 101x0 | 1x100 | 101x1 |
x1101 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1x101 | 11101 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1110x | 11101 | 11101 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0x101 | 01101 | xx101 | x1101 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x0101 | xx101 | 10101 | 1x101 | 00101 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0101x | 01yy1 | y1yy1 | y1yyx | 01yy1 | 0yyy1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
01x11 | 011x1 | y11y1 | y11y1 | 011x1 | 0y1y1 | 01011 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x1011 | x1yy1 | 11yy1 | 11yy1 | 01yy1 | xyyy1 | 01011 | 01011 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0110x | 01101 | x1101 | x110x | 01101 | 0x101 | 01yyx | 011x1 | 01yy1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
x1100 | x110x | 1110x | 11100 | 0110x | xy10y | 01yy0 | 011yy | x1yyy | 01100 |
|
|
|
|
|
|
|
|
|
|
|
|
011x1 | 01101 | x1101 | x1101 | 01101 | 0x101 | 01x11 | 01111 | 01x11 | 01101 | 0110x |
|
|
|
|
|
|
|
|
|
|
|
100x1 | 1yy01 | 10x01 | 1yy01 | y0y01 | 10x01 | yy011 | yy011 | 1x011 | yyy01 | 1yy0y | yyyx1 |
|
|
|
|
|
|
|
|
|
|
10x01 | 1x101 | 10101 | 1x101 | x0101 | 10101 | yy0y1 | yyxy1 | 1y0y1 | yy101 | 1y10y | yy101 | 10001 |
|
|
|
|
|
|
|
|
|
1001x | 1yyy1 | 10yy1 | 1yyyx | y0yy1 | 10yy1 | yy01x | yy011 | 1x011 | yyyyx | 1yyy0 | yyy11 | 10011 | 100x1 |
|
|
|
|
|
|
|
|
10x10 | 1y1yy | 101yy | 1y1y0 | y01yy | 101yy | yy010 | yyx1y | 1y01y | yy1y0 | 1y1y0 | yy11y | 1001x | 10xyy | 10010 |
|
|
|
|
|
|
|
10x11 | 1y1y1 | 101x1 | 1y1y1 | y01y1 | 101x1 | yy011 | yyx11 | 1x011 | yy1y1 | 1y1yy | yy111 | 10011 | 10xx1 | 10011 | 10x1x |
|
|
|
|
|
|
1x011 | 11yy1 | 1xyy1 | 11yy1 | yxyy1 | 10yy1 | x1011 | x1011 | 11011 | y1yy1 | 11yyy | y1y11 | 10011 | 100x1 | 10011 | 1001x | 10011 |
|
|
|
|
|
1010x | 1x101 | 10101 | 1x10x | x0101 | 10101 | yyyyx | yy1y1 | 1yyy1 | yy10x | 1x100 | yy101 | 10x01 | 10101 | 10yyx | 101x0 | 101x1 | 10yy1 |
|
|
|
|
101x0 | 1y10y | 1010x | 1x100 | y010y | 1010x | yyy10 | yy11y | 1yy1y | yy100 | 1x100 | yy1xy | 10yxy | 1010x | 10x10 | 10110 | 1011x | 10y1y | 10100 |
|
|
|
1x100 | 1110x | 1x10x | 11100 | yx10y | 1010x | y1yy0 | y11yy | 11yyy | x1100 | 11100 | y110y | 10y0y | 1010x | 10yy0 | 101x0 | 101yy | 1xyyy | 10100 | 10100 |
|
|
101x1 | 1x101 | 10101 | 1x101 | x0101 | 10101 | yyy11 | yy111 | 1yy11 | yy101 | 1y10y | yy1x1 | 10xx1 | 10101 | 10x11 | 1011x | 10111 | 10x11 | 10101 | 101xx | 1010x |
|
1011x | 1y1y1 | 101x1 | 1y1yx | y01y1 | 101x1 | yyy1x | yy111 | 1yy11 | yy1yx | 1y1y0 | yy111 | 10x11 | 101x1 | 10x1x | 10110 | 10111 | 10x11 | 101xx | 10110 | 101x0 | 10111 |
Безліч C2: xx101; x110x; 1x10x; 10xx1; 10x1x; 101xx.
* | xx101 | x110x | 1x10x | 10xx1 | 10x1x | xx101 |
|
|
|
|
| x110x | x1101 |
|
|
|
| 1x10x | 1x101 | 1110x |
|
|
| 10xx1 | 10101 | 1x101 | 10101 |
|
| 10x1x | 101x1 | 1y1yx | 101xx | 10x11 |
| 101xx | 10101 | 1x10x | 1010x | 101x1 | 1011x |
Безліч С3 - пусте (склеювання не дало нових кубів більш високої розмірності). Багато простих імплекант Z: 0101x; 01x11; x1011; 011x1; 1x011; xx101; x110x; 1x10x; 10xx1; 10x1x; 101xx. Відкинемо ті куби з безлічі Z, які покриваються іншими. # Z z 0101x 01x11 x1011 011x1 1x011 xx101 x110x 1x10x 10xx1 10x1x 101xx 0101x _ 01111 11011 011x1 1x011 xx101 x110x 1x10x 10xx1 10x1x 101xx 01x11 01010 _ 11011 01101 1x011 xx101 x110x 1x10x 10xx1 10x1x 101xx x1011 01010 01111 _ 01101 10011 xx101 x110x 1x10x 10xx1 10x1x 101xx 011x1 01010 11011 _ 10011 1x101 1110x 1x10x 10xx1 10x1x 101xx x0101 x1100 1x011 01010 01101 _ 1x101 1110x 1x10x 101x1 1011x 101xx x0101 x1100 10x01 10x10 xx101 01010 10011 _ 11100 1x100 10111 1011x 1011x x1100 10001 10x10 101x0 x110x 01010 10011 10101 _ 10100 10111 1011x 1011x x0101 10001 10x10 101x0 1x10x 01010 10011 _ 10111 1011x 1011x 00101 01100 10001 10x10 10110 10xx1 01010 00101 01100 10100 _ 10110 10110 10x10 10x1x 01010 00101 01100 10100 _ 10001 101xx 01010 00101 01100 10001 _ 10010 01010 00101 01100 10001 10010
|
За допомогою операції перетину знаходимо L-екстремал утворені на безлічі N. Z # (Z - z) Ç L 01010 00101 01100 10001 10010 11101 OOOOO 00101 O 00101 OOO 01010 01010 OOOO 01011 OOOOO 01100 OO 01100 OO 01101 OOOOO 01111 OOOOO 10001 OOO 10001 O 10010 OOOO 10010 10011 OOOOO 10100 OOOOO 10101 OOOOO 10110 OOOOO 10111 OOOOO 11011 OOOOO 11100 OOOOO
|
N = {Æ} Куби на безлічі L: 01010; 00101; 01100; 10001; 10010. L-екстремал: 0101x; xx101; x110x; 10xx1; 10x1x. Знайдемо куби з L не покриті L-екстремали.
L # E 11101 00101 01010 01011 01100 01101 01111 10001 10010 10011 10100 10101 10110 10111 11011 11100 0101x 11101 00101 01100 01101 01111 10001 10010 10011 10100 10101 10110 10111 11011 11100 xx101 01100 01111 10001 10010 10011 10100 10110 10111 11011 11100 x110x 01111 10001 10010 10011 10100 10110 10111 11011 10xx1 01111 10010 10100 10110 11011 10x1x 01111 10100 11011 01111 10100 11011
|
З останків Z (за винятком-екстремалів L) виберемо куби які покриють залишок безлічі L.
(Z \ E) Ç (L # E) 01111 10100 01x11 01111 O x1011 OO 011x1 01111 O 1x011 OO 1x10x O 10100 101xx O 10100
|
Тупикові форми: 01 x 11, 011 x 1 & 1 x 10 x, 101 xx Мінімізована Переключательная функція для виходу перенесення ОЧС C min: 0101x; xx101; x110x; 10xx1; 10x1x; 01 x 11; 101 xx. Алгоритм Рота для виходу S 1 ОЧС C 0 = L; Z 0 = 0; Безліч С0: 00001; 00011; 00100; 00110; 01001; 01011; 01100; 01110; 10000 10010; 10101; 10111; 11000; 11010; 11101 C0 * C0 | 00001 | 00011 | 00100 | 00110 | 01001 | 01011 | 01100 | 01110 | 10000 | 10010 | 10101 | 10111 | 11000 | 11010 | 11101 | 00001 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| 00011 | 000x1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
| 00100 | 00y0y | 00yyy |
|
|
|
|
|
|
|
|
|
|
|
|
| 00110 | 00yyy | 00y1y | 001x0 |
|
|
|
|
|
|
|
|
|
|
|
| 01001 | 0x001 | 0y0y1 | 0yy0y | 0yyyy |
|
|
|
|
|
|
|
|
|
|
| 01011 | 0y0y1 | 0x011 | 0yyyy | 0yy1y | 010x1 |
|
|
|
|
|
|
|
|
|
| 01100 | 0yy0y | 0yyyy | 0x100 | 0y1y0 | 01y0y | 01yyy |
|
|
|
|
|
|
|
|
| 01110 | 0yyyy | 0yy1y | 0y1y0 | 0x110 | 01yyy | 01y1y | 011x0 |
|
|
|
|
|
|
|
| 10000 | y000y | y00yy | y0y00 | y0yy0 | yy00y | yy0yy | yyy00 | yyyy0 |
|
|
|
|
|
|
|
|
10010 | y00yy | y001y | y0yy0 | y0y10 | yy0yy | yy01y | yyyy0 | yyy10 | 100x0 |
|
|
|
|
|
|
10101 | y0y01 | y0yy1 | y010y | y01yy | yyy01 | yyyy1 | yy10y | yy1yy | 10y0y | 10yyy |
|
|
|
|
|
10111 | y0yy1 | y0y11 | y01yy | y011y | yyyy1 | yyy11 | yy1yy | yy11y | 10yyy | 10y1y | 101x1 |
|
|
|
|
11000 | yy00y | yy0yy | yyy00 | yyyy0 | y100y | y10yy | y1y00 | y1yy0 | 1x000 | 1y0y0 | 1yy0y | 1yyyy |
|
|
|
11010 | yy0yy | yy01y | yyyy0 | yyy10 | y10yy | y101y | y1yy0 | y1y10 | 1y0y0 | 1x010 | 1yyyy | 1yy1y | 110x0 |
|
|
11101 | yyy01 | yyyy1 | yy10y | yy1yy | y1y01 | y1yy1 | y110y | y11yy | 1yy0y | 1yyyy | 1x101 | 1y1y1 | 11y0y | 11yyy |
|
11111 | yyyy1 | yyy11 | yy1yy | yy11y | y1yy1 | y1y11 | y11yy | y111y | 1yyyy | 1yy1y | 1y1y1 | 1x111 | 11yyy | 11y1y | 111x1 |
C1 = A1 È (C0-Z0)
Безліч C1: 000x1; 0x001; 0x011; 001x0; 0x100; 0x110; 010x1; 011x0; 100x0; 1x000; 1x010; 101x1; 1x101; 1x111; 110x0; 111x1.
C1 * A1 | 000x1 | 0x001 | 0x011 | 001x0 | 0x100 | 0x110 | 010x1 | 011x0 | 100x0 | 1x000 | 1x010 | 101x1 | 1x101 | 1x111 | 110x0 |
000x1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0x001 | 00001 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0x011 | 00011 | 0x0x1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
001x0 | 00yxy | 00y0y | 00y1y |
|
|
|
|
|
|
|
|
|
|
|
|
0x100 | 00y0y | 0xy0y | 0xyyy | 00100 |
|
|
|
|
|
|
|
|
|
|
|
0x110 | 00y1y | 0xyyy | 0xy1y | 00110 | 0x1x0 |
|
|
|
|
|
|
|
|
|
|
010x1 | 0x0x1 | 01001 | 01011 | 0yyxy | 01y0y | 01y1y |
|
|
|
|
|
|
|
|
|
011x0 | 0yyxy | 01y0y | 01y1y | 0x1x0 | 01100 | 01110 | 01yxy |
|
|
|
|
|
|
|
|
100x0 | y00xy | y000y | y001y | y0yx0 | y0y00 | y0y10 | yy0xy | yyyx0 |
|
|
|
|
|
|
|
1x000 | y000y | yx00y | yx0yy | y0y00 | yxy00 | yxyy0 | y100y | y1y00 | 10000 |
|
|
|
|
|
|
1x010 | y001y | yx0yy | yx01y | y0y10 | yxyy0 | yxy10 | y101y | y1y10 | 10010 | 1x0x0 |
|
|
|
|
|
101x1 | y0yx1 | y0y01 | y0y11 | y01xy | y010y | y011y | yyyx1 | yy1xy | 10yxy | 10y0y | 10y1y |
|
|
|
|
1x101 | y0y01 | yxy01 | yxyy1 | y010y | yx10y | yx1yy | y1y01 | y110y | 10y0y | 1xy0y | 1xyyy | 10101 |
|
|
| 1x111 | y0y11 | yxyy1 | yxy11 | y011y | yx1yy | yx11y | y1y11 | y111y | 10y1y | 1xyyy | 1xy1y | 10111 | 1x1x1 |
|
| 110x0 | yy0xy | y100y | y101y | yyyx0 | y1y00 | y1y10 | y10xy | y1yx0 | 1x0x0 | 11000 | 11010 | 1yyxy | 11y0y | 11y1y |
| 111x1 | yyyx1 | y1y01 | y1y11 | yy1xy | y110y | y111y | y1yx1 | y11xy | 1yyxy | 11y0y | 11y1y | 1x1x1 | 11101 | 11111 | 11yxy |
Безліч C2: 0x0x1; 0x1x0; 1x0x0; 1x1x1. C2 * A2 | 0x0x1 | 0x1x0 | 1x0x0 | 0x0x1 |
|
|
| 0x1x0 | 0xyxy |
|
| 1x0x0 | yx0xy | yxyx0 |
| 1x1x1 | yxyx1 | yx1xy | 1xyxy |
Безліч С3 - пусте. Багато простих імплекант Z: 0x0x1; 0x1x0 1x0x0; 1x1x1. Z # Z | 0x0x1 | 0x1x0 | 1x0x0 | 1x1x1 | 0x0x1 | - | 0x1x0 | 1x0x0 | 1x1x1 | 0x1x0 | 0x0x1 | - | 1x0x0 | 1x1x1 | 1x0x0 | 0x0x1 | 0x1x0 | - | 1x1x1 | 1x1x1 | 0x0x1 | 0x1x0 | 1x0x0 | - | - | 0x0x1 | 0x1x0 | 1x0x0 | 1x1x1 |
За допомогою операції перетину знаходимо L-екстремал утворені на безлічі N. Z # (Zz) Ç L 0x0x1 0x1x0 1x0x0 1x1x1 00001 00001 OOO 00011 00011 OOO 00100 O 00100 OO 00110 O 00110 OO 01001 01001 OOO 01011 01011 OOO 01100 O 01100 OO 01110 O 01110 OO 10000 OO 10000 O 10010 OO 10010 O 10101 OOO 10101 10111 OOO 10111 11000 OO 11000 O 11010 OO 11010 O 11101 OOO 11101 11111 OOO 11111
|
|
|
|
|
Оскільки N = {Æ} то всі Z утворено на безлічі L. Куби на безлічі L: 0x0x1; 0x1x0; 1x0x0; 1x1x1. L-екстремал: 0x0x1; 0x1x0; 1x0x0; 1x1x1. Перевіримо, чи не залишилося кубів з L не покритих L-екстремали.
L # E 00001 00011 00100 00110 01001 01011 01100 01110 10000 10010 10101 10111 11000 11010 11101 11111 0x0x1 00100 00110 01100 01110 10000 10010 10101 10111 11000 11010 11101 11111 0x1x0 10000 10010 10101 10111 11000 11010 11101 11111 1x0x0 10101 10111 11101 11111 1x1x1
|
Всі L-екстремал, і тільки вони входять в C min: 0x0x1; 0x1x0; 1x0x0; 1x1x1. Алгоритм Рота для виходу S 2 ОЧС: С0 = L; Z 0 = 0; Безліч С0: 00001; 00010; 00110; 00111; 01000; 01011; 01100; 01101; 10010; 10011; 10100; 10111; 11000; 11001; 11101. C0 * C0 | 00001 | 00010 | 00110 | 00111 | 01000 | 01011 | 01100 | 01101 | 10010 | 10011 | 10100 | 10111 | 11000 | 11001 | 11101 | 00001 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| 00010 | 000yy |
|
|
|
|
|
|
|
|
|
|
|
|
|
| 00110 | 00yyy | 00x10 |
|
|
|
|
|
|
|
|
|
|
|
|
| 00111 | 00yy1 | 00y1y | 0011x |
|
|
|
|
|
|
|
|
|
|
|
| 01000 | 0y00y | 0y0y0 | 0yyy0 | 0yyyy |
|
|
|
|
|
|
|
|
|
|
| 01011 | 0y0y1 | 0y01y | 0yy1y | 0yy11 | 010yy |
|
|
|
|
|
|
|
|
|
| 01100 | 0yy0y | 0yyy0 | 0y1y0 | 0y1yy | 01x00 | 01yyy |
|
|
|
|
|
|
|
|
| 01101 | 0yy01 | 0yyyy | 0y1yy | 0y1y1 | 01y0y | 01yy1 | 0110x |
|
|
|
|
|
|
|
| 10010 | y00yy | x0010 | y0y10 | y0y1y | yy0y0 | yy01y | yyyy0 | yyyyy |
|
|
|
|
|
|
|
|
10011 | y00y1 | y001y | y0y1y | y0y11 | yy0yy | yy011 | yyyyy | yyyy1 | 1001x |
|
|
|
|
|
|
10100 | y0y0y | y0yy0 | y01y0 | y01yy | yyy00 | yyyyy | yy100 | yy10y | 10yy0 | 10yyy |
|
|
|
|
|
10111 | y0yy1 | y0y1y | y011y | x0111 | yyyyy | yyy11 | yy1yy | yy1y1 | 10y1y | 10x11 | 101yy |
|
|
|
|
11000 | yy00y | yy0y0 | yyyy0 | yyyyy | x1000 | y10yy | y1y00 | y1y0y | 1y0y0 | 1y0yy | 1yy00 | 1yyyy |
|
|
|
11001 | yy001 | yy0yy | yyyyy | yyyy1 | y100y | y10y1 | y1y0y | y1y01 | 1y0yy | 1y0y1 | 1yy0y | 1yyy1 | 1100x |
|
|
11101 | yyy01 | yyyyy | yy1yy | yy1y1 | y1y0y | y1yy1 | y110y | x1101 | 1yyyy | 1yyy1 | 1y10y | 1y1y1 | 11y0y | 11x01 |
|
11110 | yyyyy | yyy10 | yy110 | yy11y | y1yy0 | y1y1y | y11y0 | y11yy | 1yy10 | 1yy1y | 1y1y0 | 1y11y | 11yy0 | 11yyy | 111yy |
Безліч C1:
00x10 x0010 0011x x0111 01x00 x1000 0110x x1101 1001x 10x11 1100x 11x01
C1 = A1 È (C0 \ Z0)
C1 * A1 | 00x10 | x0010 | 0011x | x0111 | 01x00 | x1000 | 0110x | x1101 | 1001x | 10x11 | 1100x |
00x10 |
|
|
|
|
|
|
|
|
|
|
|
x0010 | 00010 |
|
|
|
|
|
|
|
|
|
|
0011x | 00110 | 00x10 |
|
|
|
|
|
|
|
|
|
x0111 | 0011x | x0y1y | 00111 |
|
|
|
|
|
|
|
|
01x00 | 0yxy0 | 0y0y0 | 0y1y0 | 0y1yy |
|
|
|
|
|
|
|
x1000 | 0y0y0 | xy0y0 | 0yyy0 | xyyyy | 01000 |
|
|
|
|
|
|
0110x | 0y1y0 | 0yyy0 | 0y1yx | 0y1y1 | 01100 | 01x00 |
|
|
|
|
|
x1101 | 0y1yy | xyyyy | 0y1y1 | xy1y1 | 0110x | x1y0y | 01101 |
|
|
|
|
1001x | x0010 | 10010 | y0y1x | 10x11 | yy0y0 | 1y0y0 | yyyyx | 1yyy1 |
|
|
|
10x11 | y0x1y | 1001x | x0111 | 10111 | yyxyy | 1y0yy | yy1y1 | 1y1y1 | 10011 |
|
|
1100x | yy0y0 | 1y0y0 | yyyyx | 1yyy1 | x1000 | 11000 | y1y0x | 11x01 | 1y0yx | 1y0y1 |
|
11x01 | yyxyy | 1y0yy | yy1y1 | 1y1y1 | y1x0y | 1100x | x1101 | 11101 | 1y0y1 | 1yxy1 | 11001 |
Безліч С2 - пусте
Багато простих імплекант Z: 00001; 01011; 10100; 11110; 00x10; x0010;
0011x; x0111; 01x00; x1000; 0110x; x1101; 1001x; 10x11; 1100x; 11x01.
00001 01011 10100 11110 00001 00001 OOO 00010 OOOO 00110 OOOO 00111 OOOO 01000 OOOO 01011 O 01011 OO 01100 OOOO 01101 OOOO 10010 OOOO 10011 OOOO 10100 OO 10100 O 10111 OOOO 11000 OOOO 11001 OOOO 11101 OOOO 11110 OOO 11110
|
Куби на безлічі L: 00001; 01011; 10100; 11110.
L-екстремал: 00001; 01011 10100; 11110.
L # E 00001 00010 00110 00111 01000 01011 01100 01101 10010 10011 10100 10111 11000 11001 11101 11110 00001 00010 00110 00111 01000 01011 01100 01101 10010 10011 10100 10111 11000 11001 11101 11110 01011 00010 00110 00111 01000 01100 01101 10010 10011 10100 10111 11000 11001 11101 11110 10100 00010 00110 00111 01000 01100 01101 10010 10011 10111 11000 11001 11101 11110 11110 00010 00110 00111 01000 01100 01101 10010 10011 10111 11000 11001 11101 00010 00110 00111 01000 01100 01101 10010 10011 10111 11000 11001 11101
|
00010 00110 00111 01000 01100 01101 10010 10011 10111 11000 11001 11101 00x10 00010 00110 OOOOOOOOOO x0010 00010 OOOOO 10010 OOOOO 0011x O 00110 00111 OOOOOOOOO x0111 OO 00111 OOOOO 10111 OOO 01x00 OOO 01000 01100 OOOOOOO x1000 OOO 01000 OOOOO 11000 OO 0110x OOOO 01100 01101 OOOOOO x1101 OOOOO 01101 OOOOO 11101 1001x OOOOOO 10010 10011 OOOO 10x11 OOOOOOO 10011 10111 OOO 1100x OOOOOOOOO 11000 11001 O 11x01 OOOOOOOOOO 11001 11101
|
Тупикові форми: 00 x 10, x 0111, 2001 x 00, x 1101, 1001 x, 1100 x
C min = 00001; 01011 10100; 11110, 00x10, x0111, 01x00, x1101, 1001x, 1100x
Ефективність мінімізації визначається коефіцент мінімізації. Він розраховується за наступною формулою:
Ціна вихідного покриття
Коеф .=-----------------------------------------
Ціна мінімального покриття
Таблиця 13. Коефіцієнт мінімізації.
| Ціна вихідного покриття | Ціна мінімального покриття | Коефіцент мінімізації |
Q1 | 84 | 6 | 14 |
Q2 | 84 | 35 | 2,4 |
P2 | 84 | 21 | 4 |
Синтез МПА дільника
Автомат повинен управляти розподілом з відновлення залишку. Блок-схема цього алгоритму наведена нижче:
Y 0 - підсумовування діленого і подвійного додаткового коду дільника.;
Y 1 - занесення нуля в регістр приватного, відновлення залишку (підсумовування діленого і дільника);
Y 2 - занесення одиниці в регістр приватного;
Y 3 - зсув регістра суми і приватного влего, нарощування точності приватного;
X 1 - перевірка знакового розряду регістра суми (0 - позитивне, 1 - негативне);
X 2 - перевірка досягнення точності обчислення;
За умовами задачі дільник необхідно синтезувати у вигляді керуючого автомата Мура. Розмітка ДСА в цьому випадку відбувається за наступним алгоритмом:
1. Влучною a 1 відзначаються перша і остання вершини.
2. Мітками a 2 .. am зазначаються всі операторні вершини.
За зазначеної ДСА будується таблиця переходів:
am | K (am) | as | F (am, as) | K (as) | X (am, as) | Y (am, as) |
A1 | 000 | A2 | 001 | 001 | - | - |
A2 | 001 | A3 | 011 | 010 | X1 | Y0 |
A2 | 001 | A4 | 010 | 011 | X1 | Y0 |
A3 | 010 | A5 | 110 | 100 | - | Y1 |
A4 | 011 | A5 | 111 | 100 | - | Y2 |
A5 | 100 | A2 | 101 | 001 | X2 | Y3 |
A5 | 100 | A1 | 100 | 000 | X2 | Y3 |
За побудованої таблиці сформуємо таблицю істинності для налаштування ПЛМ:
-