2. 1. Основні поняття

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

Загальна теорія автоматів поділяється на абстрактну і структурну.

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

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

Абстрактний цифровий автомат визначається сукупністю п’яти об’єктів , де , - множина вхідних сигналів автомата (вхідний алфавіт автомата); , - множина станів автомата (алфавіт станів автомата); , - множина вихідних сигналів автомата (вихідний алфавіт автомата); - функція переходів автомата , яка задає відображення множин ( , тобто яка ставить у відповідність будь-якій парі елементів декартового добутку множин ( ) елемент ; - функція виходів автомата , яка задає відображення , або .

За способом формування функції виходів розрізняють три типи абстрактних автоматів: автомат Мілі, автомат Мура і С-автомати. В автоматі Мілі функція виходів задає відображення . В автоматі Мура функція виходів задає відображення . В абстрактному С-автоматі вводяться дві функції виходів і , які задають відображення і відповідно. При цьому алфавіт виходів С-автомата або .

Довільний абстрактний автомат Мілі чи Мура має один вхідний і один вихідний канали (рис. 2. 1,а). Довільний абстрактний С-автомат має один вхідний і два вихідних канали (рис. 2. 1,б).

Рис. 2. 1. Структура абстрактних автоматів: а – Мілі та Мура;

б – С-автомата.

Розрізняють повністю визначені і часткові автомати.

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

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

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

Автомат працює в дискретному автоматному часі 0, 1, 2, ... і переходи із стану в стан здійснюються миттєво. В кожний момент дискретного часу автомат знаходиться в деякому стані із множини станів . Якщо автоматі ініціальний , то в початковий момент часу = 0 він завжди знаходиться в початковому стані . В момент , знаходячись в стані , автомат здатен сприйняти на вході букву вхідного алфавіту . У відповідності із функцією виходів він видасть у той же момент часу букву вихідного алфавіту і у відповідності із функцією переходів перейде в наступний стан . Згідно із визначенням абстрактного автомата, автомат Мілі в цьому разі характеризується системою рівнянь:

,

;

автомат Мура – системою рівнянь:

,

,

а С-автомат – системою рівнянь:

,

,

.

Іншими словами, якщо на вхід ініціального автомата Мілі чи Мура, який установлений у початковий стан , подавати буква за буквою деяку послідовність букв вхідного алфавіту , , , ...- вхідне слово, то на виході автомата будуть появлятися букви вихідного алфавіту , , , ... - вихідне слово. Для випадку С-автомата на його виходах будуть появлятися дві послідовності: , , , ... і , , ,...

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

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

Ряд процесів, якими керують реальні автомати , не вимагають для своєї роботи знання попередньої історії. В них вихідний сигнал визначається тільки вхідними сигналами. Такі автомати мають тільки один стан. Їх задають трійкою , де функція виходів - це відображення ( ), тобто . Автомати з одним внутрішнім станом називаються абстрактними автоматами з тривіальною пам’яттю (без пам’яті) або комбінаційними автоматами.

Алфавіти входів, станів і виходів автоматів задаються, як звичайні множини, наприклад, переліком своїх елементів. Функції переходів і виходів можуть бути задані матрично, графічно і аналітично. Тому будь-який абстрактний автомат може бути заданий трьома способами: матрично, графічно і аналітично.

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

Таблиця переходів довільного повністю визначеного абстрактного автомата будується так. Стовпці таблиці позначаються буквами вхідного алфавіту автомата, а рядки таблиці – буквами алфавіту станів автомата. В клітинці таблиці переходів, яка знаходиться на перетині стовпця, позначеного вхідним сигналом , і рядка, позначеного станом , ставиться стан , що є результатом переходу автомата із стану під дією вхідного сигналу , що визначається виразом . Приклад таблиці переходів деякого абстрактного повного автомата із вхідним алфавітом і алфавітом станів представлений у табл. 2. 1. Якщо абстрактний автомат частковий, то в клітині таблиці його переходів, яка знаходиться на перетині стовпця, позначеного вхідним сигналом , і рядка, позначеного станом (при умові, що перехід із стану під дією вхідного сигналу невизначений), ставиться прочерк, і будь-яке вхідне слово, яке приводить до вказаного переходу, є забороненим. Інші клітинки заповнюються так само, як і для повного автомата. Приклад таблиці переходів деякого абстрактного часткового автомата з вхідним алфавітом

Таблиця 2. 1 Таблиця 2. 2

Стани	Вхідні сигнали				Стани	Вхідні сигнали
						- -	-

і алфавітом станів представлений в табл. 2. 2. Вигляд таблиці переходів не залежить від типу автомата, що задається (автомат Мура, Мілі чи С-автомат). Таблиці виходів автомата Мура, Мілі, С-автомата мають відмінності.

Таблиця виходів повного автомата Мілі будується так. В клітинці таблиці виходів, яка знаходиться на перетині стовпця, позначеного вхідним сигналом , і рядка, позначеного станом , ставиться вихідний сигнал , котрий автомат Мілі видає, перебуваючи в стані під дією вхідного сигналу , що визначається виразом . Приклад таблиці виходів деякого абстрактного повного автомата Мілі із вхідним алфавітом , алфавітом станів і вихідним алфавітом представлений в табл. 2. 3.

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

представлений у табл. 2. 4.

Таблиця 2. 3 Таблиця 2. 4

Стани	Вхідні сигнали				Стани	Вихідні сигнали

Абстрактний повний С-автомат задається двома таблицями виходів, перша з яких є таблиця виходів Мілі, а друга – таблиця виходів автомата Мура.

Якщо автомат Мілі частковий, то в деяких клітинках його таблиці виходів може стояти прочерк, який означає відсутність вихідного сигналу. При цьому прочерк обов’язково ставиться в тих клітинках таблиці виходів, котрі відповідають таким же клітинкам з прочерком в таблиці переходів автомата Мілі. Приклад таблиці виходів часткового автомата Мілі, заданого таблицею переходів (табл. 2. 2) із вхідним алфавітом , представлений в табл. 2. 5.

Прочерки в деяких клітинках таблиці виходів часткового автомата Мура не зв’язані з прочерками у клітинках його таблиці переходів. Це визначається тим, що вихідний сигнал автомата Мура залежить тільки від стану, в якому знаходиться автомат. Наприклад, таблиця виходів часткового автомата Мура, заданого таблицею переходів (табл. 2. 2), може бути представлена і як табл. 2. 4, якщо в кожному своєму стані автомат видає який-небудь вихідний сигнал, і як табл. 2. 6, якщо значення вихідного сигналу автомата для деяких станів невизначене.

Таблиця 2. 5 Таблиця 2. 6

Стани	Вхідні сигнали			Стани	Вихідні сигнали
	- -	- -			-

На практиці таблиці переходів і виходів автомата часто суміщають у одну таблицю, що називається позначеною таблицею переходів автомата. Така таблиця переходів повного автомата Мілі, який представлений таблицею переходів (табл. 2. 1) і таблицею виходів (табл. 2. 3), зведена в табл. 2. 7. Позначена таблиця переходів часткового автомата Мура (табл. 2. 2) і таблиця виходів (табл. 2. 4) зведена в табл. 2. 8.

Крім таблиць переходів і виходів довільний абстрактний автомат може бути описаний матрицею з’єднань. Такий опис є одним із способів матричного завдання абстрактних автоматів. Матриця з’єднань довільного абстрактного автомата являється квадратною і містить стільки стовпців (рядків), скільки різних станів має даний автомат. Кожний стовпець (рядок0 матриці з’єднань позначається буквою станів автомата. Якщо автомат ініціальний, то перший зліва стовпець і перший зверху рядок матриці його з’єднань позначаються буквою початкового стану автомата. В клітинці матриці з’єднань, яка знаходиться на перетині стовпця, позначеного буквою стану і рядка. Позначеного буквою стану автомата, ставиться вхідний сигнал (або диз’юнкція вхідних сигналів), під дією котрих виконується перехід автомата із стану в стан . Якщо матрицею з’єднань задається

Таблиця 2. 7 Таблиця 2. 8

Стан	Вхідні сигнали				Стани	Вхідні сигнали		Вихідні сигнали
							-
						-
						-

абстрактний автомат Мілі, то поряд із буквою вхідного сигналу в дужках вказується буква вихідного сигналу , який видає автомат Мілі, здійснюючи перехід . Матриця з’єднань деякого автомата Мілі, представленого позначеною таблицею переходів (табл. 2. 7), показана на рис. 2. 2.

		-	-
-
	-
			-

Рис.2. 2. Матриця з’єднань автомата Мілі.

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

При графічному способі задавання абстрактні автомати представляються орієнтованими графами. Стани автомата зображаються вершинами графа, а переходи між станами – дугами між відповідними вершинами. При цьому кожній дузі графа приписується деяка буква вхідного алфавіту автомата, яка вказує, що даний перехід автомата виконується тільки при появі вхідного сигналу , а кожній вершині графа – буква відповідного стану автомата. Якщо графом зображається автомат Мілі, то вихідні сигнали автомата проставляються на дугах графа (у відповідності з таблицею виходів автомата) поряд із буквою вхідного сигналу. Приклад графа автомата Мілі, заданого таблицею переходів (табл. 2. 1) і таблицею виходів (табл. 2. 3), показаний на рис. 2. 3, а. Якщо графом зображається автомат Мура, то вихідні сигнали автомата проставляються біля вершин графа (у відповідності із таблицею виходів автомата). Приклад графа автомата Мура, заданого таблицею переходів (табл. 2. 2) і таблицею виходів (табл. 2. 4), показаний на рис.2. 3,б.

Рис. 2. 3. Граф: а – автомата Мілі; б – автомата Мура.

При аналітичному способі задавання абстрактні автомати представляються четвіркою об’єктів , де задає для кожного стану автомата відображення ( . Іншими словами, при аналітичному способі задавання для кожного стану автомата вказується відображення , яке становить собою множину всіх трійок , . , і таких, що під дією вхідного сигналу автомат виконує перехід із стану в стан , видаючи при цьому вихідний сигнал . Відображення записується так: .

Аналітичне задавання автомата Мілі, представленого позначеною таблицею переходів (табл. 2. 7, має такий вигляд

Автомат , , , ,

;

;

;

.

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

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

Розробка реальних автоматів (представлених хоча б на рівні принципових електричних схем) вимагає їх завдання спочатку на абстрактному рівні з наступним переходом на структурний рівень, який враховує використовувані в схемі автомата логічні елементи і зв’язки між ними. В зв’язку з цим виникає задача синтезу абстрактного автомата, виходячи із деякого початкового, наприклад, словесного описання його роботи.

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

Розділ 3. СИНТЕЗ КОМБІНАЦІЙНИХ СХЕМ

Синтез комбінаційних схем на логічних елементах

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

Система функцій, яка реалізується вибраною для синтезу схем сукупністю логічних елементів, завжди має бути функціонально повною, тобто такою, що допускає реалізацію будь-якої функції на основі принципу суперпозиції. Мінімізацію функцій можна виконувати у різних алгебрах. У зв’язку з цим відомі різні методи побудови комбінаційних схем. Розглянемо один із можливих підходів до побудови комбінаційних схем у елементному базисі трьох алгебр: Буля, Шефера і Пірса.

Синтез комбінаційних схем у заданому елементному базисі можна розділити на три етапи.

На першому етапі виконують мінімізацію перемикальних функцій обраним методом.

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

На третьому етапі з урахуванням цільової функції проектування обирають операторну форму перемикальної функції і будують комбінаційну схему.

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

Розглянемо етапи синтезу комбінаційної схеми на прикладі перемикальної функції, заданої у ДДНФ:

.

На першому етапі виконаємо мінімізацію заданої функції та її заперечення за допомогою діаграм Вейча (рис.1).

Рис. 1. Діаграми Вейча

Знаходимо МДНФ функції та її заперечення:

; .

Другий етап починається з одержання восьми нормальних форм у базисі логічних елементів {І, АБО, НЕ, І-НЕ, АБО-НЕ} (див. ).

Виходячи із МДНФ функції за допомогою правила де Моргана послідовно одержимо чотири нормальні форми:

(форма І / АБО)

(форма І-НЕ / І-НЕ)

(форма АБО / І-НЕ

(форма АБО-НЕ / АБО

На основі МДНФ заперечення заданої функції, отримаємо ще чотири нормальні форми:

(форма І / АБО-НЕ)

(форма І-НЕ / І)

(форма АБО / І)

(форма АБО-НЕ / АБО-НЕ)

Для побудови схеми можуть використовуватися різні форми, які залежать від елементного базису. Так, наприклад, якщо задані елементи І, І-НЕ, то підходять форми І-НЕ / І-НЕ та І-НЕ / І.

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

;

;

;

,

де ; .

Число груп змінних також не повинно перевищувати . В іншому випадку зазначені перетворення виконують також і стосовно груп змінних. Наведені перетворення дозволяють подати функції в операторній формі з урахуванням числа входів логічних елементів.

На третьому етапі потрібно вибрати одну схему з кількох можливих, яка найбільше задовольняє заданим параметрам (зазвичай – за складністю та швидкодією).

Для порівняння складності схем варто визначити їх складність за Квайном або за числом умовних корпусів інтегральних схем (див. )

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

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

Наприклад, за наявності двовходових елементів 2І-НЕ та 2І (цифри показують кількість входів елемента) задану функцію можна подати в нормальних формах І-НЕ / І-НЕ та І-НЕ / І таким чином:

; (І-НЕ / І-НЕ)

. (І-НЕ / І)

Операторні форми в даному випадку збігаються з нормальними формами. За отриманими операторними формами можна побудувати комбінаційні схеми на елементах 2І-НЕ та 2І (рис. 2).

Рис. 2. Комбінаційні схеми: а – на логічних елементах 2І-НЕ;

б – на логічних елементах 2І-НЕ та 2І

У кожній схемі максимальна затримка сигналів визначається ланцюжком із двох елементів, тобто , де − затримка сигналу одним відповідним елементом. Якщо елементи І-НЕ мають однакові часові параметри, що й елементи І, то обидві схеми за швидкодією рівнозначні. За складністю комбінаційні схеми також рівнозначні.

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

Число логічних елементів, об’єднаних в один корпус ІМС, характеризує степінь інтеграції логічних елементів. Степінь інтеграції впливає на надійність, габаритні розміри, енергоспоживання проектованих КС. Розрізняють ІМС малого, середнього, великого і надвеликого степеня інтеграції. Зазвичай при оцінці степеня інтеграції ІМС враховується число логічних двовходових елементів І, реалізованих на одному кристалі ІМС: малі інтегральні схеми – до 10 елементів, середні інтегральні схеми – до 100 елементів, великі інтегральні схеми (ВІС) – до 100 000 вентилів, більше 100 000 вентилів – надвеликі інтегральні схеми НВІС.

З погляду на коефіцієнт використання логічних елементів в корпусах ІМС, перша комбінаційна схема (рис. 2, а) краща.

Кожний логічний елемент ІМС характеризується низкою електричних параметрів, зокрема, коефіцієнтами об’єднання І по входу і по виходу та затримкою .

Коефіцієнт об’єднання І по входу логічного елемента ІМС задає максимальне число логічних елементів , виходи яких можуть бути з’єднані на вході даного елемента.

Коефіцієнт об’єднання по виходу (коефіцієнт розгалуження) логічного елемента ІМС задає максимальне число входів логічних елементів, котрі можуть бути з’єднані з виходом даного логічного елемента без порушення режиму його роботи.

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

Проходження сигналів різними шляхами в КС викликає появу різних затримок, що може стати причиною нестійкого функціонування КС. Комбінаційні схеми під час перехідних процесів можуть формувати короткочасні вихідні сигнали, не передбачені таблицею істинності. Якщо на сусідніх наборах та в таблиці істинності задані однакові значення функції, то за зміни вказаних наборів на короткий час може виникати протилежний за значенням сигнал. Це обумовлено наявності в схемі шляхів з різною тривалістю проходження сигналів від входів схеми до виходів. Ця проблема відома як проблема «гонок». Яка обумовлює так званий «ризик збою» в комбінаційних схемах.

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

Другий спосіб полягає у встановленні фільтрів для вихідних сигналів на тих виходах комбінаційної схеми. Де можуть виникати помилкові сигнали (рис. 3 і 4).

Короткочасні сигнали затримуються на елементі затримки перед поданням на один з входів вихідного елемента фільтра, наприклад, на повторювачі. За рахунок такого рознесення в часі короткочасних сигналів помилкові сигнали на виході фільтра відсутні.

Проектування комбінаційних схем на дешифраторах і

мультиплексорах

Дешифратор – це типова комбінаційна схема, призначена для реалізації конституент одиниці.

Розрізняють повні і неповні дешифратори. Повні дешифратори реалізують конституент (мають виходів), де - це число інформаційних входів. Неповні дешифратори реалізують менш ніж конституент.

Приклади умовного графічного позначення трьохвходових дешифраторів показані на рис. 3. Сигнали на виходах дешифратора

Рис. 3. Умовне графічне позначення дешифраторів:

а – повного дешифратора; б – неповного дешифратора

формуються відповідно до таблиці істинності (табл. ) функцій дешифратора.

Таблиця

№ н
0 1 2 3 4 5 6 7	0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1	1 0 0 0 0 0 0 0	0 1 0 0 0 0 0 0	0 0 1 0 0 0 0 0	0 0 0 1 0 0 0 0	0 0 0 0 1 0 0 0	0 0 0 0 0 1 0 0	0 0 0 0 0 0 1 0	0 0 0 0 0 0 0 1

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

;

;

;

…………..

.

Дешифратори сумісно зі схемами АБО можна використовувати для відтворення довільних логічних функцій. Дійсно, на виходах дешифратора виробляються всі кон’юнктивні терми (конституенти одиниці), які тільки можна скласти із даного числа аргументів. Логічна функція в ДДНФ є диз’юнкція деякого числа таких термів. Об’єднуючи потрібні терми за схемою АБО, можна одержати будь-яку функцію даного числа аргументів.

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

Приклад. Реалізувати за допомогою дешифратора і логічних елементів АБО систему функцій:

;

;

.

Схема реалізації заданої системи функцій показана на рис. 4

Рис. 4. Схема реалізації системи перемикальних функцій на

дешифраторі і логічних елементах АБО

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

Під мультиплексором (MUX) розуміється конструктивний елемент з одним виходом і двома групами входів: адресні входи (входи керування, селекторні входи) і входи даних (інформаційні входи). Мультиплексор дозволяє подаванням певних двійкових векторів на адресні входи підключати до виходу потрібний вхід даних. Фактично мультиплексор є комутатором відповідного входу даних на спільний вихід. Потрібний вхід даних вибирається за допомогою відповідної адреси. В наш час при проектуванні засобів обчислювальної техніки мультиплексори широко застосовуються також і як універсальні логічні модулі (УЛМ). Універсальність їх полягає в тому, що для заданого числа аргументів можна налаштувати УЛМ на будь-яку функцію. При цьому немає потреби (що важливо) ні складати ДДНФ, ні мінімізувати функцію. Відомо, що загальне число функцій аргументів виражається як . Із збільшенням число функцій стрімко зростає. Хоча практичний інтерес представляють не всі існуючі функції, можливість одержати будь-яку із величезного числа функцій свідчить про великі перспективи застосування УЛМ.

Адресні входи мультиплексора позначимо буквами , а інформаційні входи – буквами . Якщо мультиплексор має адресних входів, то число його інформаційних входів буде дорівнювати

. Однорозрядний мультиплексор з інформаційними входами характеризується парою чисел та 1 і позначається як МХ( ). Наприклад, МХ(2 – 1) – однорозрядний мультиплексор з двома інформаційними входами, МХ(4 – 1) – однорозрядний мультиплексор з чотирма інформаційними входами.

Умовні графічні позначення мультиплексорів МХ(2 – 1) і МХ(4 – 1) зображені на рис. 5, а їх таблиці істинності – відповідно у табл. і табл. .

Рис. 5. Умовні графічні позначення мультиплексорів:

а – МХ(2 – 1); б – МХ(4 – 1)

Таблиця Таблиця

0 1			0 0 0 1 1 0 1 1

Розглянемо способи налаштування УЛМ для відтворення перемикальних функцій.

Перший спосіб. Налаштування УЛМ виконується шляхом фіксації деяких входів. При цьому на адресні входи мультиплексора слід подавати аргументи функції, а на інформаційні – сигнали налаштування. Таким чином, для використання мультиплексора як УЛМ, потрібно змінити призначення його входів. Якщо на інформаційні входи (наприклад, рис. 5, б) подати двійковий вектор, що відповідає стовпцю значень заданої функції в таблиці істинності (табл. ), а на адресні входи – значення змінних, то мультиплексор реалізує функцію . Зауважимо, що в описаному способі відтворення функції на інформаційні входи мультиплексора подаються константи (0 та 1) у відповідності із значеннями функції в її таблиці істинності. Іншими словами, алфавіт налаштування має вигляд {0, 1}. Приклад реалізації функції (табл. 3. ) наведений на рис. 3.

.

Таблиця 3.

0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1	1 1 0 0 0 1 1 0

Рис. 3. . Реалізація функції на

мультиплексорі.

Іноді мультиплексор має додатковий вхід , який називається стробом. Функції стробу наступні: якщо = 1, то вихід мультиплексора дорівнює нулю (незалежно від двійкового набору, поданого на адресні входи); якщо = 0, то мультиплексор функціонує як звичайно.

Другий спосіб. Велике число входів налаштування спонукає на пошук можливостей його зменшення. Такі можливості існують і полягають у розширенні алфавіту сигналів налаштування. Якщо перейти від алфавіту {0, 1} до алфавіту {0, 1, }, де - літерал одного із аргументів, то число входів аргументів зменшиться на одиницю, а число входів налаштування – вдвічі. Під літералом змінної розуміється або сама змінна, або її інверсія.

Для нового алфавіту код налаштування знаходиться так. Аргументи, за винятком , подаються на адресні входи, що відповідає їх фіксації у виразі для шуканої функції, яка стає функцією єдиного аргументу . Цю функцію, яку назвемо залишковою, і потрібно подавати на входи налаштування.

Приклад. Реалізувати на мультиплексорі функцію .

Виникає питання, який саме аргумент функції перенести в сигнали налаштування? Рекомендується : в сигнали налаштування варто переводити той аргумент, який має мінімальне число входжень в терми функції. Тільки в цьому випадку будуть максимально використані внутрішні логічні ресурси мультиплексора, а серед сигналів налаштування збільшиться число констант, що і вважається сприятливим для схемної реалізації УЛМ.

Мінімальне число входжень у виразі даної функції має змінна , яку і перенесемо в число сигналів налаштування. Залишкова функція визначиться табл. 3. Реалізація заданої функції показана на рис. 3. .

Таблиця 3.

0 0 1 0 0 1 1 1	1 0 0

Рис. 3. . Реалізація булевої функції на мультиплексорі.

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

Таблиця 3.

0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1	0 0 0 1 1 1 1 1 0 0 0 1 0 0 0 1

При електронному налаштуванні УЛМ

константами 0 та 1 потрібен мультиплексор

„16 – 1”, на входи налаштування якого

подаються значення самої функції із таблиці.

При перенесенні в сигнали

налаштування (алфавіт налаштування

{0, 1, }) потрібно знайти залишкову функцію,

аргументами якої є вектор змінних .

Кожна комбінація цих змінних зустрічається у

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

суміжних парах рядків, можна помітити, що

залишкова функція відповідає іншій таблиці (табл. 3. ).

Для реалізації цього варіанта УЛМ досить

мультиплексора „8 – 1”(рис. 3. ).

Таблиця 3.

0 0 0 0 0 1	0
0 1 0 0 1 1	1 1
1 0 0 1 0 1	0
1 1 0 1 1 1	0

Рис. 3. . Реалізація функції . При перенесенні в сигнали налаштування двох змінних ( і ) для пошуку залишкової функції потрібно переглянути четвірки суміжних рядків табл. 3. з незмінними наборами - аргументами, що подаються на адресні входи УЛМ. Цей перегляд приводить до таблиці залишкової функції (табл. 3. ). З цієї таблиці видно, що для відтворення даної функції достатньо використати мультиплексор „4 – 1” і логічний елемент 2І для одержання добутку . Схема реалізації даної функції показана на рис. 3.

Логічні блоки на мультиплексорах використовуються в сучасних надвеликих інтегральних схемах (НВІС) програмованої логіки, що виготовляються ведучими світовими фірмами.

Таблиця 3.

0 0 0 1 1 0 1 1	1

Рис. 3. .Схема реалізації функції .