Синтез цифрових автоматів

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Синтез цифрових автоматів

Вступ

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

Мета дослідження забезпечує вирішення наступних завдань:

1. Розробка перемикальної функції;

2. Розробка функції і синтез комбінаційної схеми для:

* Базису Буля;

* Полінома Жегалкіна;

* Стрілки Пірса;

* Штриху Шеффера;

* мінімізації функцій;

3. Синтез цифрового автомата.

Для вирішення поставлених завдань використано такі методи дослідження:

1. Теоретичний аналіз наукових літературних джерел;

2. Узагальнення;

3. Аналітичний метод;

4. Моделювання.

Курсова робота складається з вступу, двох розділів, висновків, списку використаних джерел, додатків.

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

Система з чотирьох перемикальних функцій задана у таблиці (для парного номеру залікової книжки обрати f₁ та f₃, а для непарного - f₂ та f₄:

Номер залікової книги: 121536

Уява у бінарному коді: 1 1101 1010 1100 0000

f1 = 1110 -01- 1000 1001

f3 = 1010 10-1 1100 1001

1. Основні властивості та алгоритм отримання ДДНФ, ДКНФ

На основі приведенних властивостей можно скласти наступний алгоритм отримання ДДНФ напряму з таблиці істинності, яка задає цифровой автомат.

Алгоритм запису ЛФ в ДДНФ має наступну послідовність:

-вибрати з таблиці істинності перший рядок, в якій f (x) = l;

-сформувати з змінних цього рядка кон'юнктивний терм (минтерм) відповідно до правила

-поставити оператор поділу + і перейти до пошуку наступного рядка, де f (x) = 1;

-якщо рядків з f (x) = l більше немає, то перейти до закінчення запису ДДНФ;

-кінець.

Для таблиці 5.2, відповідно з цим алгоритмом, маємо наступну ДДНФ:

f_ДДНФ(x₁, x₂, x₃) = x₂ x₃ + x₁ + x₁ x₂.

Для запису ЛФ використовувалися операції І, АБО, НЕ.

CДНФ (f1) =

CДНФ (f3)=

Властивості ДКНФ

Властивості функцій представлених в досконалої нормальної кон'юктивний формі (ДКНФ) аналогічні властивостям ДДНФ:

-всі диз'юнктивні терми ДКНФ є констітуенти 0, тобто макстермамі;

-в ДКНФ немає двох однакових макстермов;

-в ДКНФ макстерми не містять двох однакових змінних;

-в ДКНФ макстерм не містить разом з змінної і її заперечення;

-кожен макстерм містить всі змінні або їх заперечення.

Алгоритм запису ДКНФ

Враховуючи вище перераховані властивості, сформулюємо наступний алгоритм побудови ДКНФ для логічних функцій, заданих таблицею істинності:

-вибрати з таблиці перший рядок, де f (x) = 0;

-сформувати диз'юнктивний терм (макстерм) відповідно до правила

-поставити розділяють макстерми круглі дужки і оператор логічного множення і перейти до наступного рядка де f (x) = 0;

-якщо рядків з f (x) = 0 немає, то перейти до закінчення запису ДКНФ;

-кінець.

Рішення для таблиці 5.2. Відповідно до алгоритму маємо ДКНФ:f_ДКНФ(x₁,x₂,x₃)=(x₁+x₂+x₃)(x₁+x₂+)(x₁++x₃)?

?(+x₂+)(++).

Для представлення ДКНФ використовувалися операції І, АБО, НЕT

CКНФ(f1)=

CКНФ(f3)=

перемикальний буль алгебра цифровий

2. Методи мінімізації функцій алгебри логіки

Аналітичний метод мінімізації ЛФ

Визначення. Мінімальна форма (МКФ та МДФ) подання ФО це форма, яка містить мінімальну кількість термів і змінних в термах, і не повинна допускати подальших спрощень.

Наприклад, функція x1 + x2 може бути спрощена, якщо застосувати розподільний закон: x1x2 + x3 = (x1 + x3) (x2 + х3), тоді

x₁+x₂=(+x₁)(x₁+х₂)=x₁+x₁x₁+х₂+x₁x₂=0+x₁+х₂(+x₁)=x₁+х_2.

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

Приклад. Нехай задана ДДНФ

x₁x₂x₃+x₁x₂+x₁x₃+x₁+x₂x₃=

(додамо ще один кон'юнктивний терм x1x2x3 згідно аксіоми х + х = х,) тоді,

=x₁x₂x₃+x₁ x₂+x₁x₃+x₁+x₁x₂x₃+x₂x₃=

(використовуємо об'єднуючу і розподільну властивість кон'юнкції і диз'юнкції)

=x₁x₂(x₃+)+x₁(x₃+)+x₂x₃(x₁+)=

=x₁x₂+x₁+x₂x₃=x₁(x₂+)+x₂x₃=x₁+x₂x₃.

В даний час суттєві результати у вирішенні завдань мінімізації отримані лише для базису НЕ, І, АБО, тому що цей базис найбільш поширений в техніці проектування ЦА. Саме цим базисом ми будемо приділяти більше уваги надалі. З метою автоматизації процесу мінімізації функцій, на практиці часто застосовують числове і геометричне представлення функцій алгебри логіки.

Метод Куайна-Мак-Класкі (метод простих імлікант) - табличний метод мінімізації булевих функцій розроблений Уілардом Куайном і Едвардом Мак-Класкі. Функціонально ідентичний карті Карно, але таблична форма робить його ефективнішим для використання в комп'ютерних алгоритмах.

Незважаючи на більшу можливість практичного застосування ніж у карт Карно, коли мова йде про більше ніж чотири змінних, метод Куайна -- Мак-Класкі теж має обмеження області застосування через експоненціальне зростання часу зі збільшенням кількості змінних. Можна показати, що для функції від n змінних верхня границя кількості основних імплікант 3ⁿ/n. Якщо n = 32 їх може бути більше ніж 6.5 * 10¹⁵. Функції з великою кількістю змінних мають бути мінімізовані з допомогою потенційно не оптимального евристичного алгоритму, на сьогодні евристичний алгоритм мінімізації Еспресо є фактичним світовим стандартом.

1-й етап. Знаходження первинних импликант

Всі минтери даної функції порівнюються попарно. Якщо минтерми відрізняються однією координатою типу Fхi + F = F, то виписується кон'юнкція F, що є минтермов (r + l)-гo рангу. Минтерми r-го рангу, для яких відбулося склеювання, відзначаються.

Іншими словами, знаходження простих імплікант зводиться до побудови комплексу кубів

K (f) = К0 К1 К2... Кr.

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

Етап закінчується, коли жоден (r +1)-куб не може бути побудований. При цьому, всі невідмічені куби комплексу K (f) теж є простими импликантами і входять у покриття C (f) функції f.

Приклад. Нехай задана функція

F(х₁,х₂,х₃,х₄,х₅)=(0,1,2,3,4,5,14,15,16,17,18,19,21,23,31)

Прості і невідмічені імпліканти утворюють покриття С (f), яке може бути надмірною і вимагає подальших етапів мінімізації, а саме - складання таблиць покриття функції.

2-й етап. Складання таблиць покриття

Зрозуміло, що для знаходження мінімальної форми покриття необхідно видалити з покриття деякі прості або невідмічені імпліканти. Для цього використовують таблицю, рядки якої складають імпліканти покриття, а стовпці - 0-куби (минтермів) вихідної функції. Якщо імпліканта відрізняється від 0-куба (крім незалежних координат), то на їх перетині не ставиться мітка (див. таблицю 2.1).

Таблиця 2.1-Таблиця покриття комплексу кубів

3-й етап. Визначення істотних імплікант

Якщо у стовпці таблиці покриттів є тільки одна мітка, то первинна імпліканта, що стоїть у відповідному рядку, є суттєвою імплікантою, і її виписують у нове мінімальне покриття C (f). З таблиці покриттів виключаються рядки, відповідні істотним імплікантам і стовпці мінтермів, вкриває цими істотними імплікантами. Покриття буде мати вигляд:

C(f) = .

В результаті спрощення, отримаємо нову таблицю 2.2

Таблиця 2.2-Покриття

4-й етап. Викреслення зайвих стовпців.

Якщо в таблиці істотних імплікант є два стовпці які мають мітки в однакових рядках, то один із стовпців викреслюється.

5-й етап. Викреслення простих зайвих імплікант.

Якщо після викреслювання стовпців в таблиці з'являються рядки без міток, то імпліканти цих рядків викреслюються.

6-й етап. Вибір мінімального покриття.

У таблиці, отриманої після виділення істотних імплікант, вибирається сукупність простих імплікант, що забезпечує покриття всіх стовпців з мінімальною ціною СA.

У нашому прикладі вибирається імпліканта Х0Х01 (або 10ХХ1, тому що ціни СA однакові).

Таким чином, покриття функції має вигляд:

С(f) =

і визначає мінімальну ДНФ

f =++x₂x₃x₄+x₅+x₁x₃x₄x₅.

При використанні методу Куайна для ДКНФ необхідно розглядати значення функцій f = 0 і макстерми, відповідні цим значенням. В результаті отримаємо

Размещено на Allbest.ru