Parallel decomposition of a system of partial boolean functions.pdf Под декомпозицией системы булевых функций понимается ее представление в виде суперпозиции двух или более систем функций, каждая из которых в некотором смысле проще исходной системы. Задача декомпозиции булевых функций является одной из важных и сложных задач из области логического проектирования, ее успешное решение непосредственно влияет на качество и стоимость проектируемых цифровых устройств. Декомпозиция системы булевых функций, описывающей поведение некоторого дискретного устройства, ведет к разбиению его на отдельные блоки, что облегчает дальнейшую процедуру логического синтеза. Как показано в работах [1, 2], данной задаче посвящено значительное количество статей, однако вопрос еще требует исследований [3]. В настоящей статье рассматривается задача декомпозиции системы булевых функций в следующей постановке. Задана система частичных (не полностью определенных) булевых функций в виде векторной функцииf(x) = fi(x),/2(x), ...,fn(x)), где компонентами вектора x = (x1, Х2, ..., x„) являются булевы переменные, составляющие множество Х. Требуется найти суперпозициюf(x) < 9(^1(^1), £2(^2), ..., gk(Zk)), где Z1, Z2, ..., Zk - векторные переменные, компонентами которых служат соответственно переменные из подмножеств Z1, Z2, ..., Zk (возможно, пересекающихся) множества Х = {Х1, Х2, ..., x„}, а символ < обозначает отношение реализации, т. е. значения компонент ф1, ф2, ..., фт векторной функции ф совпадают со значениями компонент функции f везде, где эти значения определены. При этом мощность |Z;| (i = 1, 2, ..., k) должна быть ограничена некоторой заданной величинойр, а число k должно быть минимальным и меньшим, чем п. Указанная декомпозиция определяет структуру логической схемы, показанную на рис. 1. Такой вид декомпозиции назван многоблочной параллельной декомпозицией [4]. Подобная задача при k = 2 решалась в статье [5]. Рис. 1. Структура логической схемы В подавляющем большинстве публикаций, рассматривающих задачу декомпозиции булевых функций, подмножества Z1, Z2, ..., Zk считаются заданными [2, 4, 6, 7]. Вопросу поиска таких подмножеств, при которых существует соответствующая декомпозиция, посвящено не так много публикаций. Среди работ, где рассматривается данный вопрос, можно назвать работы [8-13]. В данной статье предлагается подход, не требующий конкретного задания подмножеств Z1, Z2, ..., Zk. Его можно рассматривать как дальнейшее развитие подхода, представленного в работе [14]. 1. Описание подхода Предлагаемый подход к решению данной задачи требует интервального задания системы частичных булевых функций [3] - в виде пары троичных матриц X, F размерности l х n и l х m соответственно. Столбцы матрицы X соответствуют переменным x\, Х2, ..., xn, а столбцы матрицы F - функциям f\(x), fi(x), ..., fm(x). Строка матрицыXпредставляет интервал булева пространства, а соответствующая ей строка матрицы F - значения функций на этом интервале. Символ «-» в i-й строке и j-м столбце матрицы F означает, что i-й интервал не используется для задания функцииf(x). Строки матриц X и F имеют единую нумерацию. Рассмотрим графы Gx = (V, EX) и Gf = (V, Ef), где множество вершин V является множеством общих номеров строк матриц X и F, а множества ребер Ex и Ef являются множествами пар номеров ортогональных строк матриц X и F соответственно. Две строки троичной матрицы ортогональны, если имеется столбец, у которого в одной из этих строк расположен ноль, а в другой - единица [3]. Система функций задана корректно с помощью матриц X и F, если Ef с Ex, т.е. Gf является остовным подграфом графа Gx. Замечание. Любая пара матриц (X, F) указанного вида может рассматриваться как представление некоторой системы частичных булевых функций, если граф Gf является остовным подграфом графа Gx. Каждому ребру из множества Ex приписано множество переменных из множества Х = {x1, Х2, ..., Xn}, по которым соответствующие строки ортогональны. Полному двудольному подграфу, или биклике, графа Gx припишем множество переменных из Х, взятых по одной из каждого ребра, принадлежащего данной биклике. Биклику назовем допустимой, если число приписанных ей переменных не превышает р и если она содержит хотя бы одно ребро из множества Ef. Множество переменных, приписываемых биклике, определяется следующим образом. Пусть {xi, Xj, ..., Xk} - множество переменных, по которым ортогональны две строки, соответствующие ребру из множества Ex. Образуем элементарную дизъюнкцию xi v xj v ... v xk из этих переменных. Получим конъюнктивную нормальную форму (КНФ), членами которой будут указанные дизъюнкции, взятые по всем ребрам, входящим в данную биклику. После удаления возможных поглощаемых элементарных дизъюнкций преобразуем полученную КНФ, раскрыв скобки, в дизъюнктивную нормальную форму (ДНФ). Множество переменных, приписанных биклике, составят переменные, входящие в элементарную конъюнкцию минимального ранга полученной ДНФ. Утверждение. Для системы частичных булевых функций f(x), заданной троичными матрицами Xи F, существует реализующая ее суперпозиция 9^1(^1), g2(Z2), ..., gk(Zk)), если существует покрытие множества Ef допустимыми бикликами графа Gx, число которых k. Пусть получено указанное покрытие бикликами B\, B2, ..., Bk. Каждая биклика Bi может быть задана парой множеств вершин {V/, V"), поскольку каждая вершина из V' связана в биклике ребрами со всеми вершинами из V". Каждая функция gi(Zi) задается матрицами Xi и Ft. Матрица Xi является минором матрицы X, образованном столбцами, соответствующими переменным, приписанным биклике Bi. Матрица Fi состоит из одного столбца, где в строке с номером, соответствующим вершине из Vi , находится 0, в строке с номером, соответствующим вершине из V," находится 1 (или наоборот), а в строке, для которой нет соответствующих вершин ни в V]', ни в V", находится символ «-». Векторная функция ф задается матрицами U и Ф. Матрица U состоит из столбцов, представляющих матрицы Fi, F2, ..., Fk, а матрица Ф совпадает с матрицей F. Действительно, согласно приведенному выше замечанию пара матриц (U, Ф) может рассматриваться как представление системы частичных булевых функций. Нетрудно видеть, что для любого значения вектора х, произвольно взятого из области определения любой функции fi заданной системы, значения функций фг- и fi будут совпадать. Следовательно, пары матриц (Xi Fi), (X2 F2), ..., (Xk Fk) и (U, Ф) представляют искомую суперпозицию. Это представление обладает избыточностью в виде повторяемых и поглощаемых строк в матрицах, а также знаков «-» в одностолбцовых матрицах Fi. Такую избыточность легко устранить, удалив упомянутые строки из матриц. 2. Точный метод Точный метод, гарантирующий минимум числа функций в искомой суперпозиции, описан в статье [15] и заключается в выполнении процесса, состоящего из следующих этапов. 1. Нахождение всех максимальных допустимых биклик в графе Gx. Для этого можно использовать метод, представленный в работе [16]. 2. Получение кратчайшего покрытия множества Ef найденными бикликами. Если число биклик, составляющих покрытие, не меньше п, то для заданной системы функций не существует нетривиальной декомпозиции указанного вида. 3. Определение булевых функций gi(Zi), £2(^2), gk(Zk) и векторной функции ф. На этапе получения покрытия можно продолжить оптимизацию решения, уменьшая сумму чисел компонент векторов zi, Z2, ..., Zk. Тогда каждую биклику надо снабдить весом в виде числа приписанных ей переменных и решать задачу о взвешенном покрытии. При доопределении не полностью определенных булевых функций в процессе декомпозиции некоторые переменные могут оказаться несущественными аргументами. Тогда можно выбирать вариант с наименьшим числом существенных аргументов. Пример 1. Пусть система частичных булевых функцийf(x) задана следующими троичными матрицами: Ребра графа Gx = (V, Ex) с приписанными им переменными х1 х2 хз х4 х5 х6 / /2 /3 "1 0 1 0 1 0" 1 " 0 0 1 ■ 1 0 - - 0 1 - 2 - 1 1 2 1 - 1 1 0 1 3, F = 0 - 0 3 0 1 0 1 1 1 4 1 1 - 4 1 - 1 - 1 0 5 - 0 1 5 0 0 - 1 1 - 6 1 0 - 6 Требуется получить суперпозициюf(x) < ф^^О, g2(Z2), gk(Zk)) при минимальном k и числе р компонент каждого из векторов Zi, Z2, ..., Zk, не превышающем 3. Граф Gx = (V, EX) с множеством вершин V = (vi, V2, V3, V4, V5, ve] представим в виде перечня ребер. В табл. 1 представлены эти ребра и приписанные им переменные. Граф Gf = (V, Ef) имеет то же множество вершин, а его множество ребер Ef отличается от Ex только тем, что в нем отсутствуют ребра V2V4 и V5V6. Таблица 1 ViV2 ViV3 V1V4 V1V6 V2V3 V2V4 V2V5 V2V6 V3V4 V3V5 V3V6 V4V5 V4V6 V5V6 х1 Х4 х5 хб Х1 х2 хз х4 хб х1 х4 х1 х4 х5 х4 х1 х4 х1 хз х5 х5 хб х1 х5 х1 хз х6 х2 х1 Для графа Gx получено 18 максимальных допустимых биклик. Искомое покрытие составляют следующие биклики с соответствующими КНФ и ДНФ:

Скачать электронную версию публикации