The Algorithm of Matrix Mapping of a Graph on a Boolean Cube.pdf Важной проблемой современной теории и практики автоматизированного про-ектирования дискретных устройств является задача энергосберегающего кодиро-вания состояний автомата, реализуемого логической схемой. Она формулируетсяследующим образом. Автомат задается неориентированным графом переходов Gс m вершинами. Информация об ориентации переходов при этом не учитывается,поскольку она оказывается несущественной. Требуется оптимальным образомразместить вершины графа в булевом пространстве M = {0, 1}n, размерность ко-торого n равна целому, ближнему сверху к log2 m, и которое можно рассматриватькак n-мерный булев куб. За критерий оптимальности примем число ребер графа,отображенных на ребра булева куба. В результате этого отображения инцидент-ные ребру графа вершины окажутся на соседних элементах пространства M, т.е.на булевых n-векторах, различающихся ровно в одной компоненте.В работе [1] был предложен эвристический визуальный метод решения этойзадачи, названный методом квадратов. Он основан на использовании графиче-ского изображения графа и карты Карно и заключается в построении последова-тельности конфигураций из ребер и квадратов, образующих фрагменты гиперку-ба. Квадратом называется четырехреберный цикл в графе.Ниже описывается оригинальный комбинаторный алгоритм решения этой жезадачи на базе матричных представлений, ориентированный на компьютернуюреализацию.1. Представление данныхРассматриваемый в предлагаемом алгоритме граф переходов представляетсясимметричной булевой матрицей смежности G размером m  m. Элемент этойматрицы gij = 1, если и только если вершины i и j связаны некоторым ребром −обозначим это ребро через (i-j). Другими словами, соответствующие этим верши-нам состояния автомата связаны некоторым переходом. Очевидно, что gij =gji.Положим, что gii = 0, поскольку переходы состояний в себя при решении рас-сматриваемой задачи не учитываются.Например, показанный на рис. 1 граф переходов автомата с 11 состояниямипредставляется следующей матрицей смежности:1 2 3 4 5 6 7 8 9 10 110 0 1 0 0 1 0 1 0 0 0 10 0 0 1 0 1 0 0 1 0 1 21 0 0 0 0 1 1 0 1 0 0 30 1 0 0 l 0 0 1 0 0 0 4G = 0 0 0 1 0 0 0 0 0 1 1 51 1 1 0 0 0 1 0 0 1 0 60 0 1 0 0 1 0 0 1 0 0 71 0 0 1 0 0 0 0 1 0 0 80 1 1 0 0 0 1 1 0 0 0 90 0 0 0 1 1 0 0 0 0 1 100 1 0 0 1 0 0 0 0 1 0 11Два ребра графа назовем параллельными, если они не содержат общих вершини принадлежат оба некоторому квадрату. Это условие легко проверяется в визу-альном методе - достаточно посмотреть на граф. В методе, предлагаемом в на-стоящей статье, оно представляется более формально, в терминах матрицы смеж-ности.Два ребра графа (i-j) и (k-l), задаваемые матричными элементами gij и gkl, па-раллельны, если матрица смежности G принимает значение 1 также на элементахgil и gkj. Другими словами, эти ребра параллельны, если все четыре элемента мат-рицы, расположенные на пересечении строк gi и gk со столбцами gj и gl, принима-ют значение 1.В этом случае они принадлежат квадрату, которыйудобно задать выражением (i, j, k, l), в котором смежныевершины представлены соседними или крайними члена-ми. Кроме ребер (i-j) и (k-l) в квадрат входит также парапараллельных ребер (j, k) и (l, i) (рис. 2).В данном примере (рис. 1) параллельными оказыва-ются ребра (4-5) и (11-2), принадлежащие отмеченномуна рисунке квадрату, равно как и ребра (5-11) и (2-4). Они представляются че-тырьмя матричными элементами, на пересечении строк 4 и 11 со столбцами 2 и 5.Это элементы g42, g45, g112 и g115. Они отмечены в матрице курсивом. А квадрат вцелом представляется выражением (4-5-11-2).Заметим, что перечисление вершин квадрата можно начинать с любой верши-ны и в любом направлении. Из этого следует эквивалентность следующих обо-значений данного квадрата:(4-5-11-2), (5-11-2-4), (11-2-4-5), (2-4-5-11), (2-11-5-4),(11-5-4-2), (5-4-2-11), (4-2-11-5).Структуру булева куба, на который требуется спроектировать граф переходов,представим переменной булевой матрицей B размером n на 2n, строки которой со-ответствуют булевым переменным x1, x2, …, xn, а столбцы - элементам булеваi jl kРис. 2. Квадрат (i, j, k, l)54 10 111 6 23 78 9Рис. 1. Граф переходовпространства этих переменных, т.е. вершинам булева куба. Назовем ее матрицейкуба.Перед выполнением алгоритма отображения все элементы матрицы куба име-ют значение 1. Например, при n = 4 эта матрица имеет следующий начальныйвид:1 1 1 1 1 10 1 2 3 4 5 6 7 8 9 0 1 2 3 4 50 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 x10 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 x20 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 x30 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 x41 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 x1B = 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 x2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 x3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 x4Элементы булева пространства (вершины булева куба), соответствующиестолбцам матрицы b j, пронумерованы и показаны сверху, а булевы переменные,соответствующие ее строкам bi - справа. Ребра куба представлены соответствую-щими парами элементов матрицы B; значение jbi говорит о том, что j-й вершинекуба инцидентно ребро, ориентированное по переиенной xi. Например, в матрицеотмечены полужирным четыре ребра, инцидентные вершине 0 - это ребра (0-1),(0-2), (0-4) и (0-8). При выполнении алгоритма некоторые элементы матрицы Bменяют свое значение с 1 на 0, что свидетельствует об использовании ребер буле-ва куба в ходе реализации алгоритма отображении ребер графа в булево про-странство.2. Алгоритм отображенияПредлагаемый алгоритм заключается в последовательном выборе ребер графа(единичных элементов матрицы G) и отображении их в булево пространствоM = {0, 1}n (n-мерный булев гиперкуб) путем кодирования соответствующих парвершин булевыми векторами с n компонентами.На первом шаге выбирается некоторое ребро, для которого находится парал-лельное ему. В рассматриваемом ниже примере из нескольких подходящих ребервсегда выбирается ребро с минимальным номером. Например, в рассматриваемомграфе первыми выбираются ребро (1-3) и параллельное ему ребро (7-6). Вершиныпервого из них кодируются соседними кодами − различающимися значением водной компоненте. Операцией смены значений другой компоненты из этих кодовполучаются коды вершин другого ребра.Так, вершины 1 и 3 кодируются векторами 0000 и 0001, а вершины 7 и 6 - век-торами 0010 и 0011. Эти ребра образуют квадрат (1-3-7-6), куда входят также реб-ра (3-7) и (6-1). Таким образом, в результате этой четыре ребра графа (1-3), (3-7).(7-6) и (6-1), образующие найденный квадрат, отображаются на соответствующиеребра булева куба: (0-1), (1-3), (3-2) и (2-0). Соответственно корректируется мат-рица B. Отображенные ребра отмечаются в матрице G.Проиллюстрируем эту операцию новым значением матрицы B. Сверху матри-цы B показаны вершины графа, проектируемые на вершины булева куба, пред-ставленные столбцами матрицы. Справа показано, как из кодов вершин ребра(1-3) получаются коды вершин параллельного ему ребра (7-6) Звездочкой отмече-на компонента с изменяемым значением.1 3 6 7 (1-3)  (7-6)1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0000B = 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 00010 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 *0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 7 00116 0010На каждом из последующих шагов алгоритма выбирается одно из отображен-ных ребер и находится параллельное ему свободное ребро графа (с пока не зако-дированными вершинами). Коды его вершин получаются из кодов соответствую-щих вершин отображенного ребра, сменой значений одной компоненты, так, что-бы они были новыми (ранее не встречались). В результате кодируются две новыевершины и отображаются три ребра.Опишем эти операции более подробно.Выбор отображенного ребра. Рассматривается некоторое отображенное ребро(i, j) графа, отмеченное в матрице G . Обозначим через b*i и b*j столбцы матрицыB, соответствующие кодам вершин i и j (например, b*7 = [1100]T). Если конъ-юнкция этих столбцов не содержит единиц (b*i  b*j = 0), не существует свободно-го ребра, параллельного ребру (i, j), следовательно, надо выбрать другое из ото-браженных ребер. Их можно перебирать в порядке нумерации.Нахождение параллельного ему среди свободных ребер. Обозначим через Nfмножество незакодированных вершин, а через Rf и Cf соответствующие этим вер-шинам подмножества строк и столбцов матрицы G. Допустим, что выбрано ото-браженное ребро (p-q). Рассмотрим в множестве Rf некоторую строку gk, содер-жащую единицу в j-й компоненте (gkj = 1). Если конъюнкция векторов gi и gkпринимает значение 1 в некотором столбце l из множества Cf, находится свобод-ное ребро (k-l), параллельное ребру (p-q). В противном случае рассматриваетсядругая строка из Rf.Кодирование вершин и отображение ребер. Коды вершин k и l получаютсясоответственно из кодов вершин j и i сменой значения младшей из компонент,удовлетворяющих следующему условию: одноименная компонента в вектореb*i  b*j должна быть равна единице. Из этого условия, в частности. следует, чтоданная компонента имеет одинаковое значение в кодах вершин j и i .В соответствии с этими правилами выполняются последующие шаги алгорит-ма. На каждом из них выбирается свободное ребро, параллельное одному из ото-браженных, и кодируются его вершины. Результат представляется новым значе-нием матрицы куба B. Процесс кодирования вершин показан справа от этой мат-рицы.Шаг 2.1 3 6 7 8 9 (1-3)  (9-8)1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0000B = 0 0 1 1 0 0 1 1 1 1 1 1 1 1 1 1 3 00010 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 *0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 9 01018 0100Шаг 3.1 3 6 7 8 9 4 2 (8-9)  (2-4)1 1 1 1 0 0 1 1 1 1 1 1 0 0 1 1 8 0100B = 0 0 1 1 0 0 1 1 1 1 1 1 1 1 1 1 9 01010 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 *0 0 0 0 0 0 1 1 1 1 1 1 0 0 1 1 2 11014 1100Шаг 4.1 3 6 7 8 9 4 2 5 11 (2-4)  (5-11)1 1 1 1 0 0 1 1 1 1 1 1 0 0 1 1 2 1101B = 0 0 1 1 0 0 1 1 1 1 1 1 1 1 1 1 4 11000 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 *0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 5 111011 1111В результате выполнения данной цепочки на гиперкуб отобразились 13 реберграфа и все его вершины, кроме одной, с номером 10. Ее можно закодировать,рассматривая коды соседних с ней вершин 5, 6 и 11 и выбирая среди свободных(еще не использованных) кодов ближайший к ним. Таким оказывается булев век-тор 0110, соседний с кодами вершин 5 и 6 - векторами 1110 и 0010. Этот выборприводит к отображению на гиперкуб еще двух ребер - (5-10) и (6-10). Оказыва-ются соседними коды вершин 8 и 10, хотя они не смежные, что находит отраже-ние в конечном значении матрицы куба:1 3 6 7 8 9 10 4 2 5 111 1 1 1 0 0 0 1 1 1 1 1 0 0 0 1B = 0 0 0 1 0 0 0 1 1 1 1 1 1 1 1 10 0 0 0 0 1 0 1 1 1 1 1 0 0 0 00 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0Присвоенные вершинам графа переходов кодыпоказаны в следующей таблице:0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 10 0 0 0 1 1 1 1 0 0 0 0 1 1 1 10 0 1 1 0 0 1 1 0 0 1 1 0 0 1 10 1 0 1 0 1 0 1 0 1 0 1 0 1 0 11 3 6 7 8 9 10 4 2 5 11а отображенные ребра отмечены на рис. 3Окончательный результат выполнения алгоритма иллюстрируется такжерис. 4, где выделены ребра булева четырехмерного куба, на которые отобразилисьребра рассматриваемого графа.Остались не отображенными на булев гиперкуб четыре ребра графа: 2-6, 3-6,7-9 и 10-11. Их веса (хэмминговы расстояния между кодами вершин) равны соот-ветственно 4, 2, 2 и 2.54 10 111 6 23 78 9Рис. 3. Граф переходовс отображенными ребрамиРис. 3. Результат отображения графа на булев кубНазовем дефектом отображения разность между суммой хэмминговых рас-стояний на ребрах и числом ребер. В данном примере он равен 6.Дефект отображения можно снизить полным или рандомизированным перебо-ром вариантов выбора пар параллельных ребер (одно уже отображенное, другое -свободное). Возможен также перебор на этапе кодирования вершин свободногоребра - при выборе переменной, по которой коды этих вершин будут соседними скодами вершин отображенного ребра.

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