Синтез цифрових схем арифметичних пристроїв

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати

Зміст

Постановка завдання

Вихідні дані до курсового проекту

Розробка алгоритму множення

Розробка структурної схеми пристрою

Синтез перетворювача множника

Логічний синтез однорозрядного четверичная помножувача-суматора

Логічний синтез однорозрядного четверичная суматора

Синтез МПА дільника

Постановка завдання

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

За вихідними даними необхідно розробити:

  1. Алгоритм виконання операції множення, для чого потрібно:

  • перевести вихідні числа з десяткової системи числення в двійково-десяткову;

  • представити числа у формі з плаваючою комою;

  • провести перемножування чисел за алгоритмом "Г" в додаткових розрядах на два розряди одночасно;

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

  1. Алгоритм виконання операцій додавання і віднімання.

  1. Структурну схему комбінованого пристрою (додавання і множення), що містить вузли для дії над мантиси і порядку, і визначити час множення з урахуванням тимчасових затримок у комбінаційних схемах.

  2. Функціональні схеми основних вузлів проектованого суматора-помножувача в заданому логічному базисі. Для цього провести:

  • логічний синтез комбінаційного однорозрядного четверичная суматора (ОЧС) на основі складеної таблиці істинності для суми доданків з урахуванням перенесення з молодшого розряду, використовуючи при цьому алгоритм вилучення (Рота), та оцінити ефективність мінімізації;

  • логічний синтез однорозрядного комбінаційного четверичная помножувача-суматора (ОЧУС), шляхом мінімізації перемикальних функцій по кожному виходу схеми. Мінімізація виконується з застосуванням карт Карно-Вейча з наступною оцінкою ефективності мінімізації;

  • логічний синтез комбінаційної схеми перетворювача множника (ПМ);

  • побудувати функціональну схему ОЧС на мультиплексорах;

  • побудувати функціональну схему ПМ і ОЧУС в заданому базисі;

  1. Визначити час множення на один розряд і на n розрядів множника.

  2. Розробити алгоритм виконання операції ділення.

  3. Функціональну схему дільника, представивши його як керуючий автомат, для чого необхідно:

  • побудувати граф зв'язності автомата;

  • розмітити його для синтезу автомата Мура;

  • побудувати таблицю переходів автомата;

  • визначити переключательние функції вихідних сигналів і сигналів зворотного зв'язку;

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

Вихідні дані до курсового проекту

В якості вихідних даних до курсового проекту задається наступне:

  1. Вихідні операнди - десяткові числа з цілою і дробовою частиною, над якими проводиться операція множення (36,39 & 53,25).

  2. Алгоритм виконання операції множення Г.

  3. Метод прискореного множення на базі якого будується помножувач:

  • множення закодованого двійково-четверичная множимо на 2 розряди двійкового множника одночасно в додаткових кодах;

Перетворення множника в обох випадках проводиться для виключення з процесу множення діади множника 11.

  1. Двійкові коди четверичная цифр множимо для роботи в двійково-четверичной системі числення (подається кодом: 0 4 - 00, 1 4 - 11, 2 4 - 01, 3 4 - 10). Множник представляється звичайним весомозначним кодом: 0 4 - 00, 1 4 - 01, 2 4 - 10, 3 4 - 11.

  1. Тип синтезованого пристрою множення, визначається основними структурними вузлами, на базі яких будується помножувач:

  • помножувач 2-го типу будується на базі ОЧУС, ОЧС і регістра результату.

  1. Спосіб мінімізації та логічний базис для апаратної реалізації ОЧС і ОЧУС (функціонально повний базис представлений функцією 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

ОЧС реалізується на мультиплексорах).

  1. Алгоритм виконання операції ділення:

  • поділ з відновленням залишків;

  1. Клас синтезованого мікропрограмного автомата: Мура.

  1. Логічний базис для апаратної реалізації дільника, як керуючого автомата: ПЛМ і тригери для організації ланцюга зворотного зв'язку (Т-тригери).

Розробка алгоритму множення

  1. Переклад співмножників з десяткової системи числення в четверичная:

Множимо

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

  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

  1. Множення двох чисел з плаваючою комою на 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 с / с

    1. Після закінчення множення необхідно оцінити похибку обчислень. Для цього отримане твір (Мн * Мт 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

    За побудованої таблиці сформуємо таблицю істинності для налаштування ПЛМ:

    X1

    X2

    T1

    T2

    T3

    Y0

    Y1

    Y2

    Y3

    D1

    D2

    D3

    -

    -

    0

    0

    0

    0

    0

    0

    0

    0

    0

    1

    0

    -

    0

    0

    1

    1

    0

    0

    0

    0

    1

    0

    1

    -

    0

    0

    1

    1

    0

    0

    0

    0

    1

    1

    -

    -

    0

    1

    0

    0

    1

    0

    0

    0

    0

    0

    -

    -

    0

    1

    1

    0

    0

    1

    0

    0

    0

    1

    -

    0

    1

    0

    0

    0

    0

    0

    1

    1

    1

    1

    -

    1

    1

    0

    0

    0

    0

    0

    1

    1

    0

    0

    За отриманою таблиці побудуємо автомат, як пам'ять використовуючи T-тригери.

    44


    Додати в блог або на сайт

    Цей текст може містити помилки.

    Комунікації, зв'язок, цифрові прилади і радіоелектроніка | Курсова
    421.1кб. | скачати


    Схожі роботи:
    Вбудований контроль і діагностика цифрових пристроїв Методи підвищення контролепригодности цифрових
    Аналіз та моделювання цифрових і аналогових схем
    VHDL - технології дослідження цифрових пристроїв
    Вбудований контроль і діагностика цифрових пристроїв Методи вище
    Синтез цифрових комутаційних систем
    Складання логічних схем з метою проектування комбінаційних пристроїв
    Синтез логічних схем
    Дослідження методів та інструментальних засобів проектування цифрових пристроїв на основі програмованих
    Синтез логічної функції та аналіз комбінаційних схем
    © Усі права захищені
    написати до нас