[ Синтез цифрових схем арифметичних пристроїв ] | Рез. У пр. коді | |
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.
*
Безліч С3 - пусте (склеювання не дало нових кубів більш високої розмірності). Багато простих імплекант Z: 0101x; 01x11; x1011; 011x1; 1x011; xx101; x110x; 1x10x; 10xx1; 10x1x; 101xx. Відкинемо ті куби з безлічі Z, які покриваються іншими.
За допомогою операції перетину знаходимо L-екстремал утворені на безлічі N.
N = {Æ} Куби на безлічі L: 01010; 00101; 01100; 10001; 10010. L-екстремал: 0101x; xx101; x110x; 10xx1; 10x1x. Знайдемо куби з L не покриті L-екстремали.
З останків Z (за винятком-екстремалів L) виберемо куби які покриють залишок безлічі L.
Тупикові форми: 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
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
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
Безліч C2: 0x0x1; 0x1x0; 1x0x0; 1x1x1.
Безліч С3 - пусте. Багато простих імплекант Z: 0x0x1; 0x1x0 1x0x0; 1x1x1.
За допомогою операції перетину знаходимо L-екстремал утворені на безлічі N.
Оскільки N = {Æ} то всі Z утворено на безлічі L. Куби на безлічі L: 0x0x1; 0x1x0; 1x0x0; 1x1x1. L-екстремал: 0x0x1; 0x1x0; 1x0x0; 1x1x1. Перевіримо, чи не залишилося кубів з L не покритих L-екстремали.
Всі 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.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
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 |
За побудованої таблиці сформуємо таблицю істинності для налаштування ПЛМ:
X1
За отриманою таблиці побудуємо автомат, як пам'ять використовуючи T-тригери. |