3. 5. Проектування комбінаційних схем на плм

Під ПЛМ розуміється програмована логічна матриця – конструктивний елемент, який виготовляється у вигляді великої інтегральної схеми. Налаштування (програмування) ПЛМ здійснюється користувачем за допомогою спеціального обладнання і полягає в усуненні деяких зв’язків (серед позначених хрестиком на рис. 3. ) випалюванням чи посередково фотошаблонів. Така ПМЛ називається ( )-ПЛМ, де - число входів ПЛМ; - число виходів ПЛМ, а - число кон’юнкцій, що реалізуються ПЛМ. Входи і виходи ПЛМ називаються стовпцями, а кон’юнкції – рядками. Розглядувана ПЛМ містить ( ) стовпців і рядків. Число називається площею ПЛМ.

Рис. 3. . Функціональна схема ПЛМ.

ПЛМ можна представити у вигляді двох матриць та вхідного і вихідного буферів (рис. 3. ). Вхідні буфери БВХ перетворюють однофазні вхідні сигнали в парафазні і формують сигнали необхідної потужності для живлення матриці М1 логічних елементів І. Вихідні буфери БВИХ забезпечують необхідну навантажувальну здатність виходів. Дозволяють чи забороняють вихід ПЛМ на зовнішні шини за допомогою сигналу ОЕ, а інколи виконують і складніші дії.

Змінні подаються через вхідні буфери БВХ на входи елементів І (кон’юнкторів ) і в матриці М1 (матриця І) утворюються термів. Під термом тут розуміється кон’юнкція , що зв’язує вхідні змінні , представлені в прямій чи інверсній формі. Число термів, що формуються дорівнює числу кон’юнкторів або, що теж саме, числу виходів матриці кон’юнкцій М1.

Терми подаються далі на входи матриці АБО М2, тобто на входи диз’юнкторів, які формують вихідні функції. Число диз’юнкторів дорівнює числу відтворюваних функцій.

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

На рис. 3. показана для прикладу реалізація системи функцій , на (3, 2, 3)-ПЛМ.

Рис. 3. . Схема реалізації системи булевих функцій на ПЛМ.

Розрізняють дві задачі синтезу комбінаційних схем на ПЛМ.

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

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

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

Для реалізації системи ДНФ на ПЛМ з мінімальною площею необхідно перетворити початкову систему ДНФ до вигляду, що містиь мінімальне число вхідних змінних і мінімальне число кон’юнкцій в повній множині кон’юнкцій.

Можливість зменшення числа вхідних змінних системи ДНФ появляться в разі, коли значення функцій системи не змінюються при довільних змінах значень деяких змінних. Такі змінні називаються фіктивними. Для неповністю визначених булевих функцій одні й ті ж змінні можуть бути фіктивними і не фіктивними. Наприклад. Для функцій. Заданих табл. 3. , це всі змінні, крім . Дійсно, якщо закреслити будь-який стовпець таблиці, крім третього, то між наборами значень змінних, що залишилися, не знайдеться таких двох однакових наборів, на яких функції приймають різні значення. Після викреслювання деяких стовпців окремі змінні можуть стати фіктивними.

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

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

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

Мінімально можливе число вхідних змінних можна знайти так. За початковою табл. 3. утворюємо всі пари вхідних наборів, на яких хоча б одна із функцій системи приймає протилежне значення. Такими парами наборів являються (1, 2); (1, 3); (1, 4); (1, 5); (1, 6); (1, 7); (2, 3); (2, 4); (2, 5); (2, 6); (2, 8); (3, 4); (3, 5); (3, 7); (3, 8); (4, 6); (4, 7); (4, 8); (5, 6); (5, 7); (5, 8); (6, 7); (6, 8); (7, 8). Для кожної одержаної пари наборів вкажемо множину тих змінних, значеннями яких відрізняються набори розглядуваної пари. Так, набори, що входять в пару (1, 2), відрізняються значеннями змінних , . Зведемо одержані результати в матрицю, стовпці якої позначаються парами наборів описаного вище вигляду, а рядки - вхідними змінними, від яких залежить система булевих функцій. На перетині - о стовпця і - о рядка матриці поставимо одиницю, якщо змінна, що позначає - й рядок, має різні значення в парі наборів - о стовпця матриці. Одержана таким способом матриця називається матрицею розрізнень, а кожний її рядок – вектором розрізнень. Для розглядуваного прикладу матриця розрізнень наведена в табл. 3. .

Таблиця 3.

	1,2	1,3	1,4	1,5	1,6	1,7	2,3	2,4	2,5	2,6	2,8	3,4	3,5	3,7	3,8	4,6
				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				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	1

Таблиця 3. (продовження)

	4,7	4,8	5,6	5,7	5,8	6,7	6,8	7,8
	1	1
	1		1		1	1		1
	1	1		1	1	1	1
			1			1	1
	1		1		1	1		1

Знайдемо мінімальне покриття стовпців матриці рядками. Для цього можна, наприклад, скористатися методом Петрика. Кон’юнктивне представлення таблиці має вигляд:

Після проведення перетворень одержимо .

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

Таким чином, розглядувана система булевих функцій суттєво залежить від змінних . Таблиця істинності функцій із врахуванням сказаного представлена в табл. 3. . Другим параметром ПЛМ, що впливає на її площу, являється число рядків (число реалізуємих елементів кон’юнкції). При реалізації системи ДНФ булевих функцій число рядків одержаної ПЛМ дорівнює числу різноманітних кон’юнкцій системи функцій. Природно ставиться задача знаходження мінімального їх числа. Останнє можна зробити з використанням методу мінімізації систем булевих функцій. В результаті мінімізації даної системи булевих функцій одержимо

; .

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

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

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

2. Знаходиться мінімальна ДНФ системи булевих функцій.

3. Кон’юнкції одержаної ДНФ реалізуються в першій матриці ПЛМ, а самі функції – в другій матриці – диз’юнкцією відповідних кон’юнкцій.

Через велику трудомісткість відповідних алгоритмів знаходження мінімального числа вхідних змінних і мінімальної ДНФ системи булевих функцій практично можливе лише для функцій від невеликого числа змінних. Тому для розв’язку таких задач великої розмірності застосовуються евристичні алгоритми. Більше того, знаходження мінімального числа змінних і мінімальної ДНФ в загальному випадку може й не дати мінімальної площі ПЛМ. Дійсно, для системи функцій (табл. 3. ) мінімальне число змінних дорівнює трьом. А мінімальна ДНФ складається із 6 простих імплікант. Відповідно, ПЛМ, що реалізує функції і , показана на рис. 3. Вона

Рис. 3. . Схема ПЛМ, що реалізує систему функцій і .

містить 5 стовпців і 6 рядків. Сумарна площа ПЛМ дорівнює 30. Якщо в табл. 3. закреслити стовпці і , вийде система функцій, що представлена в табл. 3. .

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

; ,

тобто містить чотири різні прості імпліканти. Реалізація одержаної системи

на ПЛМ представлена на рис. 3. . Сумарна

Таблиця 3. площа ПЛМ дорівнює .

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

Додаткову можливість скорочення площі

ПЛМ дає використання дужкових форм.

Розглянемо, наприклад, функції, ДДНФ

яких мають вигляд:

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

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

,

де . Тоді .

Одержані ДНФ реалізуються ПЛМ, представленою на рис. 3. , з сумарною площею .

Розглянемо деякі підходи до розв’язку другої задачі – задачі синтезу комбінаційних схем на ПЛМ, що випускаються серійно.

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

Приклад. Реалізувати систему булевих функцій: ;

; ; на ( ) =

= (3. 2. 4) – ПЛМ.

В нашому випадку ; = 4; = 5; = 3; = 2; = 4. Реалізація функції може бути здійснена у відповідності з блок-схемою (рис. 3. ,а). Принципова електрична схема показана на рис. 3. , б.

Рис. 3. . Блок-схема (а) та електрична схема (б) реалізації системи

перемикальних функцій на ПЛМ.

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

Приклад. Реалізувати на ( ) = 3, 2, 3)-ПЛМ систему перемикальних

функцій: ;

.

Очевидно, ; ; . Одна із можливих реалізацій функцій показана на рис. 3. , де ;

; ; , а ;

.

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

Розглянемо випадок, коли , . . Реалізація таких систем перемикальних функцій схемами з мінімальним числом ПЛМ основана на методах декомпозиції перемикальних функцій. Мінімальній за числом ПЛМ схемі відповідає декомпозиція вихідної системи функцій на мінімальне число підсистем, кожна із яких містить не більше ніж функцій і не більше ніж кон’юнкцій. Якщо не перейматися про мінімальне число ПЛМ, то можна будувати схему із ПЛМ так. Виберемо із вихідної системи підсистему із функцій. Якщо число різних імплікант, що входять у вибрані функції, , то підсистема реалізується на одній ПЛМ. Якщо ж , то підсистема реалізується схемою із - ПЛМ. Із решти функцій виберемо наступні функції і поступимо аналогічним чином. Загальне число ПЛМ в одержаній за описаним способом схемі може досягати величини .

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

Аналіз комбінаційних схем

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

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

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

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

; .

Виконуємо перетворення, користуючись законами і аксіомами булевої алгебри:

.

У результаті одержали МДНФ перемикальної функції:

.

Розділ 4. ПРОЕКТУВАННЯ ЦИФРОВИХ АВТОМАТІВ

З ПАМ’ЯТТЮ