7. Операции кубического исчисления конъюнкция (and), дизъюнкция (or), исключающее или (xor)

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

Кубическое представление логических функций наиболее пригодно для машинных методов их анализа, так как позволяет компактно представлять логические функции от большого количества переменных. Это свойство определило наибольшую распространенность кубического представления логических функций при создании САПР цифровой аппаратуры. Именно поэтому кубическое представление логических функций заслуживает более подробного рассмотрения.

Для представления логических функций в кубической форме используется четырехсимвольный теоретико-множественный алфавит, основанный на двух логических примитивах 0 и 1, т.е. кубический алфавит можно представить, как А = {0, 1, U, X}. Обычно в теоретико-множественном представлении символ U ассоциируется с понятием «пусто» (). Символ Х в этом алфавите может рассматриваться как унирверсум, т.е. Х = 0 1  U .   В дальнейшем  («пусто») и U («unrnown state») рассматриваются как синонимы.

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

Рисунок 2.43 – Графическая интерпретация кубического алфавита

Для логических функций, определенных для 0 и 1, символы {U, X} можно рассматривать как один символ X. Исходя из этого классический кубический алфавит имеет вид А = {0, 1, X}.

Любой набор переменных (pattern) в кубическом представлении логических функций принято называть кубом или вектором в n-мерном пространстве. Переменные куба принято называть координатами, а компоненты вектора - разрядами. Определения «куб» и «вектор» обычно используют в качестве синонимов.

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

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

Количество символов Х в кубе определяет его ранг. Например, куб 0011 имеет нулевой ранг, 0X11 - первый ранг, XX11 - второй ранг и т.д. При этом куб первого ранга «покрывает» 2 набора, второго ранга - 4 набора и т.д. Таким образом, можно определить, что куб ранга k «покрывает» 2^k двоичных наборов.

Совокупность кубов, покрывающих все входные наборы функции, называется покрытием или кубическим покрытием (КП). Множество кубов, на которых функция равна 0, называют нулевым покрытием (C⁰), а на которых равна 1 - единичным покрытием (C¹). Обозначение КП в виде C⁰ и C¹ происходит от английского слова «Сover» - покрывать.

Способ кубического представления булевых функций и операции над кубами в этом представлении образуют кубическое исчисление.

Можно определить логические операции, которые по названиям аналогичны логическим функциям двух переменых. Правила выполнения этих операций соответствуют побитовым логическим операциям в языках программирования высокого уровня. Ниже рассмотрены основные из этих операций, а именно, конъюнкция (AND), дизъюнкция (OR), исключающее ИЛИ (XOR) .

Кубическая операция конъюнкции (И, AND, &) двух n-мерных кубов А = (а₁,а₂, ... а_n) и B = (b₁,b₂, ... b_n), где n - количество координат куба, обозначается C = A & B, где C = (c₁,c₂, ... c_n), и определяется как C = ((a₁ & b₁), (a₂ & b₂), ... (a_n & b_n)). Кубическая операция конъюнкции является покоординатной и правила ее выполнения в каждом разряде указаны в табл. 2.4. Достаточно часто в литературе эту операцию называют логическим умножением и обозначают точкой, «*» или не обозначают вовсе.

Таблица 2.4 - Кубическая операция И

Примеры выполнения:

0X01 & 11X1 = 0X01;

0110 & 01XX = 01X0 .

Кубическая операция дизъюнкции (ИЛИ, OR, v) двух n-мерных кубов А = (а₁,а₂,...а_n) и B = (b₁,b₂, ... b_n), где n - количество координат куба, обозначается C = A v B, где C = (c₁,c₂, ... c_n), и определяется как C = ((a₁ v b₁), (a₂ v b₂), ... (a_n v b_n)). Кубическая операция дизъюнкции является покоординатной и правила ее выполнения в каждом разряде указаны в табл. 2.5. Достаточно часто в литературе эту операцию называют логическим сложением и обозначают знаком «+».

Таблица 2.5 - Кубическая операция ИЛИ

Примеры выполнения:

0X01 v 11X1 = 1X01;

0110 v 01XX = 011X.

Кубическая операция исключающее ИЛИ (сумма по модулю 2, XOR, ) двух n-мерных кубов А = (а₁,а₂, ... а_n) и B = (b₁,b₂, ... b_n), где n - количество координат куба, обозначается C = A  B, где C = (c₁,c₂, ... c_n), и определяется как C = ( (a₁  b₁), (a₂  b₂), ... (a_n  b_n) ) . Кубическая операция «сумма по модулю 2» является покоординатной и правила ее выполнения в каждом разряде указаны в табл. 2.6. Иногда в литературе эту операцию называют арифметическим сложением в одном разряде без переноса (или функцией полусумматора).

Таблица 2.6 - Кубическая операция исключающая ИЛИ

Примеры выполнения:

0X01  11X1 = 1XX0;

0110  0101 = 0011 .

Отметим, что все вышеперечисленные операции отвечают условиям ассоциативности и коммутативности.