Кубічне числення

Кубічне числення - є математичним апаратом, який використовується при синтезі і аналізі в більшості сучасних систем автоматизованого проектування (САПР) цифрових схем.

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

Історія

Малюнок куба для функції 3-х змінних

Будь-який набір змінних (pattern) в кубічному представленні логічних функцій прийнято називати кубом або вектором в n-вимірному просторі. Змінні куба прийнято називати координатами, а компоненти вектора - розрядами. Визначення "куб" і "вектор" зазвичай використовують як синоніми. Кількість змінних в кубі визначає його мірність (розрядність вектора). Зазвичай мірність куба визначається числом змінних булевої функції або загальною кількістю ліній аналізованої комутаційної схеми (вхідних, вихідних і внутрішніх).

Для представлення логічних функцій в кубічної форми використовується чотирьох символьний теоретико-множинний алфавіт, заснований на двох логічних примітивах 0 і 1, тобто кубічний алфавіт можна уявити, як А = {0, 1, U, X}. Зазвичай в теоретико-множинному представленні символ U асоціюється з поняттям "порожньо" (Ø). Символ Х в цьому алфавіті може розглядатися як універсум, тобто Х = 0 ∪ 1 ∪ U. Надалі викладі Ø("порожньо") і U ("unnown state") розглядаються як синоніми.

Графическая интерпретация кубического алфавита А = {0,1,U,X} с использованием диаграмы Венна

Кодовою відстанню d між двома кубами називається кількість координат які відрізняються (розрядів). Наприклад, якщо A = 0XX0 і B = 01X1, то кодова відстань між ними дорівнює 2 (d = 2).

Кількість символів Х в кубі визначає його ранг. Наприклад, куб 0011 має нульовий ранг, 0X11 - перший ранг, XX11 - другий ранг і т.д. При цьому куб першого рангу "покриває" 2 набору, другого рангу - 4 набори і т.д. Таким чином можна визначити, що куб рангу k "покриває" 2k довічних наборів.

Сукупність кубів, що покривають всі вхідні набори функції, називається покриттям або кубічним покриттям (КП). Безліч кубів, на яких функція дорівнює 0, називають нульовим покриттям (C⁰), а на яких дорівнює 1 - одиничним покриттям (C¹). Позначення КП у вигляді C⁰ і C¹ походить від англійського терміна "Cover" - покривати.

Кубічні покриття основних логічних елементів

3І (3AND)

1	2	3	4
0	x	x	0
X	0	X	0
x	x	0	0
1	1	1	1

3І-НІ (3NAND)

1	2	3	4
0	x	x	1
X	0	X	1
x	x	0	1
1	1	1	0

3АБО (3OR)

1	2	3	4
1	x	x	1
X	1	X	1
x	x	1	1
0	0	0	0

3АБО-НІ (3NOR)

1	2	3	4
1	x	x	0
X	1	X	0
x	x	1	0
0	0	0	1

3XOR

1	2	3	4
0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	0
1	1	1	1

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

Нехай задана функція f (3,7,11,12,13,14,15) = 1. Представимо її у вигляді карти Карно і виконаємо мінімізацію в кубічному і аналітичному вигляді. Аналітичне представлення цієї функції має вигляд f = x₁x₂ v x₃x₄.

Покрытие четырехмерного куба

В еквівалентній схемі для C¹ кожен куб покриття являє собою кон'юнкцію (елемент І) по суттєвим координатам куба (не рівним Х), причому координата, що дорівнює 1, відповідає змінної без інверсії, а координата, що дорівнює 0, відповідає змінної з інверсією. Одиничне покриття цілком відповідає об'єднанню всіх кубів покриття (елементів І) по АБО. Нульове покриття C⁰ з цієї точки зору відповідає зворотного ДНФ.

Кубічне представлення логічної функції 4-х змінних для функції f (3,7,11,12,13,14,15) = 1

Операції кубічного числення

Теоретико-множинні операції

Операції кубічного числення визначають перетворення над виразами в кубічної (векторній формі) в алфавіті {0, 1, X}. Основні операції кубічного числення є перетин, об'єднання і доповнення, які є відображенням відповідних логічних операцій кон'юнкції, диз'юнкції і заперечення в теоретико-множинному алфавіті. Існує ще ряд спеціальних теоретико-множинних кубічних операцій, використовуваних в кубічних методах мінімізації булевих функцій, для моделювання та побудови тестів при описі примітивних елементів схем в кубічному вигляді, але вони використовуються досить рідко і не розглядаються у даній статті.

Операція перетину (∩) двох n-мірних векторів (кубів) А = (а1, а2, ... аn) і B = (b1, b2, ... bn), де n - кількість розрядів вектора (координат куба), позначається C = A ∩ B, де C = (c1, c2, ... cn), і визначається в такий спосіб:

Операція перетину

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

Окремим випадком операції перетину є операція поглинання (Є). Часто у літературі цю операцію називають операцією приналежності за аналогією з відповідною теоретико-множинної операцією. Куб А поглинається кубом В (А належить В) (А Є В), якщо А ∩ В = А. Якщо у поглинанні беруть участь однакові куби, то результатом буде один з цих кубів.

Нижче наведені приклади виконання операції перетину C = A ∩ B для різних операндів.

0 X 0 X ∩ X 1 0 X = 0 1 0 X;

0 X 0 X ∩ 1 1 0 X = Ø ;

0 X 0 0 ∩ 0 X 0 X = 0 X 0 0 (поглинання, A Є B);

0 X 0 1 ∩ 0 X 0 1 = 0 X 0 1 ( A = B ).

Операція об'єднання ( U ) двох n-мірних кубів А = (а1, а2, ... аn) і B = (b1, b2, ... bn), де n - кількість координат куба, позначається C = A B, де C = (c1, c2, ... cn), і визначається як C = ( (a1 b1), (a2 b2), ... (an bn) ). Кубічна операція об'єднання є покоординатною і правила її виконання у кожному розряді які вказані у таблиці нижче. Ранг результату об'єднання С завжди більше або дорівнює рангу більшого з кубів, що беруть участь у об'єднанні. Відзначимо, що для кубів з кодовою відстанню d більше або рівним 2 результати об'єднання можуть бути суперечливими.

U 0 1 X

0 0 X X

1 X 1 X

X X X X

Окремим випадком операції об'єднання є операція склеювання. Куби одного рангу А і В склеюються, якщо вони різняться лише у одному розряді i, причому a_i і b_i нерівні X. Відзначимо, що саме операція склеювання ніколи не дає суперечливих результатів.

Нижче наведені приклади виконання операції об'єднання C = A B для різних операндів.

0 X 0 X U 0 X X 0 = 0 X X X (d=2, результат суперечливий, тому що 0X11 не Є A,B , але 0X11 0XXX);

0 X 0 X U 0 X 0 1 = 0 X 0 X (поглинання, B Є A);

0 X 0 1 U 0 X 0 0 = 0 X 0 X (d=1, склеювання);

0 1 0 1 U 0 1 1 0 = 0 1 X X (d=2, результат суперечливий).

Операція доповнення для одного n-мірного куба А = (а1,а2, ... аn), де n - кількість координат куба, позначається C = Ā, де C = (c1,c2, ... cn). За аналогією з аналітичним описом логічних функцій операцію доповнення часто називають логічною інверсією і правила її виконання у кожному розряді вказані у таблиці справа. Відзначимо, що ранг доповнення С по відношенню до вихідного кубу А завжди залишається незмінним.

A 0 1 X

C = Ā 1 0 X

Приклади виконання: A = 0 X 0 X, C = 1 X 1 X; A = 0 1 1 0, C = 1 0 0 1 .

Логічні операції

Крім теоретико-множинних операцій для кубічного представлення функцій алгебри логіки можна визначити логічні операції, які за назвами аналогічні логічним функцій двох змінних. Правила виконання цих операцій відповідають побітовим логічним операціям у мовах програмування високого рівня. Нижче розглянуті основні з цих операцій, а саме, кон'юнкція (AND), диз'юнкція (OR), що виключає АБО (XOR).

Кубічна операція кон'юнкції (І, AND, &) двох n-мірних кубів А = (а1,а2, ... аn) і B = (b1,b2, ... bn), де n - кількість координат куба, позначається C = A & B, де C = (c1,c2, ... cn), і визначається як C = ( (a1 & b1), (a2 & b2), ... (an & bn) ) . Кубічна операція кон'юнкції є покоординатною і правила її виконання у кожному розряді вказані у таблиці нижче. Досить часто у літературі цю операцію називають логічним множенням і позначають "точкою", "*", або не позначав зовсім.

& 0 1 X

0 0 0 0

1 0 1 X

X 0 X X

Приклади виконання: 0 X 0 1 & 1 1 X 1 = 0 X 0 1; 0 1 1 0 & 0 1 X X = 0 1 X 0 .

Кубічна операція диз'юнкції (АБО, OR, v) двох n-мірних кубів А = (а1,а2,...аn) і B = (b1,b2, ... bn), де n - кількість координат куба, позначається C = A v B, где C = (c1,c2, ... cn), і визначається як C = ( (a1 v b1), (a2 v b2), ... (an v bn) ) . Кубічна операція диз'юнкції є покоординатною і правила її виконання у кожному розряді вказані у таблиці нижче. Досить часто у літературі цю операцію називають логічним складанням і позначають знаком "+".

V 0 1 X

0 0 1 X

1 1 1 1

X X 1 X

Приклади виконання: 0 X 0 1 v 1 1 X 1 = 1 X 0 1; 0 1 1 0 v 0 1 X X = 0 1 1 X .

Кубічна операція що виключає АБО (сума по модулю 2, XOR,) двох n-мірних кубів А = (а1,а2, ... аn) і B = (b1,b2, ... bn), де n - кількість координат куба , позначається C = A B, де C = (c1,c2, ... cn), і визначається як C = ( (a1 b1), (a2 b2), ... (an bn) ) . Кубічна операція "сума по модулю 2" є покоординатною і правила її виконання у кожному розряді вказані у таблиці нижче. Іноді у літературі цю операцію називають арифметичним складанням у одному розряді без переносу (або функцією напівсуматора).

$\oplus$ 0 1 X

0 0 1 X

1 1 0 X

X X X X

Приклади виконання: 0 X 0 1 $\oplus$ 1 1 X 1 = 1 X X 0; 0 1 1 0 $\oplus$ 0 1 0 1 = 0 0 1 1 .

Відзначимо, що всі перераховані вище операції відповідають умовам асоціативності і комутативність.

Література

• Миллер Р. Теория переключательных схем. В двух томах. – М.: Наука, 1970. – 416 с.
• Хаханов В.И. Техническая диагностика элементов и узлов персональных компьютеров. – К.: ІЗМН.– 1997.– 308 с.