Застосування алгебри висловлень до аналізу й синтезу схем з функціональних елементів

Величезні швидкості роботи сучасних ЕОМ досягнуті за рахунок застосування безконтактних схем, що працюють значно швидше, ніж контактні схеми. В ЕОМ застосовуються електронні прилади, що реалізують основні логічні операції (заперечення, кон’юнкцію, диз'юнкцію й ін.). Не стосуючись структури й фізичних основ цих пристроїв, називаних функціональними елементами, позначимо їх умовно в такий спосіб:

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

пристрій, що реалізує конъюнкцию; пристрій має два й більше входи й один вихід. Сигнал з'являється на виході тоді й тільки тоді, коли на всі входи подані сигнали.

пристрій, що реалізує диз'юнкцію; пристріймає два й більше входи й один вихід. Сигнал з'являється на виході тоді й тільки тоді, коли поданий сигнал хоча б на один вхід.

Обмежимося тільки цими пристроями, хоча на практиці існують функціональні елементи, що реалізують і інші операції. Але можна обійтися тільки перерахованими трьома пристроями, тому що будь-яку бульову функцію можна виразити, використовуючи тільки операції з замкненої системи {-, Λ, v}.

Цих властивостей елементів досить для рішення завдань синтезу й аналізу схем із цих елементів.

Розглянемо приклад побудови однорозрядного суматора двійкових чисел. Задано двійкові числа a₁a₂...a_k...a_n і b₁b₂...b_k...b_n. Потрібно побудувати суматор для k -го розряду. Завдання полягає в конструюванні схеми із трьома входами A, В, С и двома виходами S і Р, щоб при подачі на входи A і B сигналів, що зображують двійкові цифри - доданки даного розряду, а на вхід C - сигналу, що зображує значення переносу із сусіднього молодшого розряду, одержати на виході S значення суми в даному розряді, а на виході Р - значення переносу в сусідній старший розряд.

Нагадаємо, що додавання чисел у двійковій системі проводиться в такий спосіб: 0+0=0,. 0+1=1+0=1, 1+1=10, 1 + 1+1=11 і т.д.

Скориставшись цією таблицею додавання чисел у двійковій системі, одержимо таблицю:

Уважаючи, що 0 і 1 є значення булевой функції, і вибираючи рядка, що закінчуються на 1, одержимо:

S=ABC v C v В v А , P=ABC v BC v А C v АB (1).

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

Можна показати, що P=AB v АC v ВC, S=ABC v (A v B vС) після спрощення формул (1).

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

Поиск по сайту: