Міністерство освіти Російської Федерації
Томський політехнічний університет
Факультет автоматики та обчислювальної техніки
Кафедра обчислювальної
техніки
Курсова робота
з дисципліни "Теорія автоматів"
на тему: В«Синтез та аналіз логічної схеми при кубічному завданні булевої функціїВ»
Томськ 2009
ЗМІСТ
Введення
1. Знаходження мінімального покриття
2. Побудова факторізованного покриття
3. Складання логічної схеми на основі даного базису логічних елементів
4. Знаходження по пі-алгоритмом Рота одиничного покриття
5. Синтез контролюючого тесту. Контроль схеми тестом
Висновок
Література
ВСТУП
Апарат алгебри логіки широко застосовується в теорії ЦВМ, зокрема для розв'язання задач аналізу та синтезу схем. При вирішенні задачі синтезу вихідне логічне вираз, що описує деяку логічну функцію, перетвориться і спрощується так, щоб кожен член отриманого еквівалентного логічного виразу міг бути представлений простою схемою. Таким чином, при синтезі обчислювальних і керуючих схем складається математичний опис задачі у вигляді формул алгебри логіки. Потім проводиться мінімізація вихідної формули і з числа еквівалентних логічних схем вибирається та, яка допускає найбільш просту реалізацію.
У цій роботі стоїть завдання синтезу схеми, реалізує функцію, задану кубічним комплексом до (f). У табл. 1 наведено початкове покриття з 8 кубів. Логічну схему слід побудувати в універсальному базисі елементів АБО-НЕ, який характеризується коефіцієнтом об'єднання входу до (вх) = 4 і коефіцієнтом розгалуження по виходу до (р) = 2. Вартість покриття дорівнює 48.
Таблиця 1 </p>
Позначення куба
Покриття
Розмірність куба
a
1011X10
6
b
1X1XX11
4
c
1011X11
6
d
XX1X1X0
3
e
0X11111
6
f
00X0XX0
4
g
0X00101
6
h
10X00X0
5
Порядок виконання роботи можна визначити наступним чином:
1). Знаходження мінімального покриття;
2). Побудова факторізованного покриття;
3). Складання логічної схеми на основі даного базису логічних елементів;
4). Знаходження по пі-алгоритмом Рота одиничного покриття;
5). Побудова контролюючого тесту;
6). Перевірка логічної схеми контролюючим тестом.
1. ЗНАХОДЖЕННЯ МІНІМАЛЬНОГО ПОКРИТТЯ
В першу чергу необхідно знайти мінімальне в сенсі Кванта покриття. Мінімальне покриття булевої функції шукається в два етапи:
1). отримання мінімального безлічі Z простих импликант;
2). виділення L-екстремалів на безлічі Z.
Для виконання цих етапів використовуються операції *-Твори, #-віднімання кубів.
При виконанні операції *-твори одного куба на інший виходить новий куб, протилежні грані якого лежать у вихідних кубах. Цей новий куб може стати простий импликантой вихідного покриття. Треба мати на увазі, що куб є простою импликантой вихідного покриття, якщо він не становить грань ніякого іншого комплексу К або того куба, який вийшов при творі в процесі знаходження простих импликант. Це означає, що прості імпліканти при *-творі не дають нових кубів, не входять у попередні куби.
При знаходженні простих импликант виконуються всі попарні твори з урахуванням того, що твір куба самого на себе призводить до куба, який бере участь у творі; що твір першого куба на другий одно творів другої куба на перший.
Операція *-твори двох кубів а = а 1 а 2 ... а i ... a n і b = b 1 b 2 ... b i ... b n визначається на основі табл. 2.
Таблиця 2
a i * b i
a i
0
1
X
b i
0
0
Y
0
1
Y
1
1
X
0
1
X
Якщо значення Y виходить тільки в одній координаті, то твір кубів a і b дає так званий знову утворений куб, в якому величина Y замінюється на X. Якщо ж мається більш однієї координати Y, то зірчасті твір дає 0.
Процес знаходження множини простих импликант є циклічним. У кожному циклі спочатку видаляються ті куби вихідного покриття, які є гранями інших кубів цього покриття. Далі видаляються куби вихідного покриття, що є гранями кубів покриття. Повинні бути видалені отримані при *-творі куби, які є гранями кубів покриття. І нарешті, видаляються отримані куби з розмірністю, на одиницю меншою номера циклу. Що залишилися в таблиці куби передаються на наступний цикл *-твори. Цикли виконуються до тих пір, поки перестануть з'являтися знову утворені куби. Процес знаходження множини простих импликант для 35-го варіанта наведено в табл. 3,4,5,6. Куб В«зВ» не використовується при знаходженні даної множини, тому він входить до куб В«bВ».
1 цикл знаходження множини простих импликант Таблиця 3
1011X10
1X1XX11
XX1X1X0
0X11111
00X0XX0
0X00101
1011X10
-
1X1XX11
1011X1X
-
XX1X1X0
1011110
1X1X11X
-
0X11111
Г†
XX11111
0X1111X
|
