Содержание к диссертации
Введение
1. Вероятностные оценки ржений таблиц покрытии 9
1.1. Постановка задачи .,, 9
1.2. Вероятностные оценки решении таблиц покрытии 17
1.3. Экспериментальная проверка достоверности вероятностных: оценок 21
1.4. Выводы 32
2. Алгоритмы решения таблиц покрытий . 33
2.1. Задача покрытия - задача комбинаторного поиска . 33
2.2. Выбор числа переменных в решение 44
2.3. Алгоритмы решения таблиц покрытий на основе вероятностных оценок * 48
2.4. Экспериментальное сравнение эффективности алгоритмов решения таблиц покрытий 55
2.5. Выводы . 66
3. Синтез комбинационных схем логических матриц
3.1. Программируемые логические матрицы и их применение для синтеза комбинационныхсхем 67
3.2. Применение разложения Шеннона для минимизации булевых функции 82
3.3. Определение совокупностей существенных переменных неполностью определённых булевых функции. . 92
3.4. Реализация системы неполностью определённых булевых функций на программируемых
логических матрицах 100
3.5. Языки описания булевых функций и систем булевых функции 114
3.6. Программное обеспечение определения существенных переменных неполностью определённых булевых функции 127
3.7. Выводы 129
Основные результаты работы 130
Литература
- Вероятностные оценки решении таблиц покрытии
- Экспериментальная проверка достоверности вероятностных: оценок
- Алгоритмы решения таблиц покрытий на основе вероятностных оценок
- Определение совокупностей существенных переменных неполностью определённых булевых функции.
Введение к работе
Решение задач повышения уровня научных исследований, улучшения качества выпускаемой продукции и повышения эффективности производства требует значительного расширения сферы применения вычислительной техники. Б "Основных направлениях экономического и социального развития СССР на I98I-I985 годы и на период до 1990 г.", принятых на ХХУІ съезде КПСС, указывается на необходимость "расширять автоматизацию проектно-конструкторских и научно-исследовательских работ с применением электронно-вычислительной техники".
В настоящее время основной элементной базой современных цифровых устройств обработки данных являются большие интегральные схемы, в частности, программируемые логические матрицы (ШМ). Они предъявляют повышенные требования к надежности проектирования, что приводит к необходимости его автоматизации /34/. Кроме того, применение ЭВМ при проектировании дискретных устройств автоматики и вычислительной техники позволяет снизить трудоемкость и сроки разработки.
На этапе логического проектирования дискретных устройств часто возникает необходимость в решении комбинаторно-логических задач. Среди них важное место занимает задача о покрытии множеств. Исследование задачи покрытия является актуальным как в теоретическом, так и в прикладном отношении, что связано с её многочисленными практическими приложениями.
Для большинства комбинаторно-логических задач существуют простые в вычислительном отношении алгоритмы определения оптимальных решений. Однако, для задач большой размерности такая возможность нахождения решения является только потенциальной, так как эти алгоритмы связаны с перебором большого числа различных вариантов.
В /28/ показано, что не существует эффективных методов решения задачи покрытия. Это не означает, что такие методы не созданы к настоящему времени. Просто для задачи покрытия, как и для многих других логических задач на дискретных математических структурах, они вообще отсутствуют. Это обстоятельство позволяет отказаться от попыток построения методов для нахождения строго оптимальных рещений и направить все усилия по решению практических задач о покрытии множеств на создание эвристических алгоритмов.
Известны различные приближенные методы, в основу каждого из которых положена некоторая эвристика, направленная на усечение максимального дерева перебора вариантов и позволяющая получить решение, приближенное к оптимальному Приближенные методы не гарантируют получение минимального покрытия. Кроме того, решения, полученные этими методами, могут быть избыточными (например, минимаксный метод). В связи с этим возникает необходимость в оценке качества приближенных решений.
В диссертационной работе рассматриваются таблицы покритий (таблицы Квайна), представляющие собой булеву матрицу. Решение таблицы покрытий (Тії) заключается в нахождении совокупности её строк, покрывающих (единицами) все столбцы таблицы. Из всех решений ТП наибольший интерес представляет покрытие минимальной мощности.
К решению таблиц покрытий сводятся многие задачи, возникающие на этапе логического проектирования дискретных устройств автоматики и вычислительной техники. Наиболее известной из них является выделение из множества простых импликант булевой функции совокупности, образующей минимальную дизъюнктивную нормальную форму функции. В этом случае ТП обычно называют импли-кантной таблицей.
Определение минимального покрытия импликантной таблицы -один из основных этапов минимизации булевых функций по методу КваЙна-МакКласки, целью которой является получение минимальной ДНФ (т.е. ДТ®, содержащей минимальное число букв). Возможны другие цели минимизации булевых функций. При синтезе комбинационных схем из UM с фиксированным числом входных, выходных и конъюнктивных шин требуется найти такую ДНФ, в выражение для которой входит наименьшее число различных переменных. В этом случае становится актуальной задача определения для булевых функций совокупности существенных переменных минимальной мощности.
Необходимость в определении существенных переменных возникает также при реализации управлявших алгоритмов на программируемых средствах вычислительной техники (ПЗУ, микропроцессоры, микро-ЭШ), в некоторых декомпозиционных методах /102/. В диссертационной работе задача определения совокупностей существенных переменных сведена к задаче решения таблиц покрытий.
Целью работы является исследование задачи решения таблиц покрытий и разработка приближенных методов для синтеза комбинационных схем из ШМ.
В соответствии с поставленной целью был сформулирован и решен ряд задач: - введены вероятностные оценки, которые но виду конкретной таблицы покрытий позволяют априорно получить представление о качестве решения;
- проведена экспериментальная проверка достоверности вероятностных оценок;
- рассмотрена возможность применения вероятностных оценок для создания новых и модицикации существующих приближенных методов решения таблиц покрытий;
- на потоке задач проведено экспериментальное сравнение эффективности алгоритмов решения ТП на основе вероятностных оценок;
- разработан ориентированный на применение ЭШ практический алгоритм определения совокупностей существенных переменных неполностью определенных булевых функций;
- разработан метод реализации системы булевых функций на ПДМ, учитывающий связность функций системы.
Метод исследования основывается на использовании аппарата и понятий теории переключательных схем, теории конечных автоматов, теории вероятностей, математической статистики, теории комбинаторных вычислений.
Основными научными результатами проведенных исследований являются вероятностные оценки решений таблиц покрытий и их применение для модификации существующих и разработки новых приближенных методов решения ТП.
Практические результаты - процедура определения вероятностных оценок, алгоритмы решения Ш, разработка алгоритма реализации системы булевых функций на ПЛИ, разработка прикладных программ для ЭШ решения таблиц покрытий, определения существенных переменных неполностью определенных булевых функций.
Основные положения диссертационной работы опубликованы в восши печатных работах /БІ-Б8/ и представлялись для обсуждения на:
- УП Всесоюзном совещании-семинаре "Автоматизации проектирования современных ВЩ ", Симферополь, май, 1979 г.;
- Всесоюзной школе-семинаре "Автоматизации логического проектирования", Севастополь, сентябрь, 1982 г.;
- научно-технических конференциях профессорско-преподавательского состава ЛЭТИ им.В.И-Ульянова (Ленина), 1980-1984 г.г.
Вероятностные оценки решении таблиц покрытии
Пусть заданы два множества п \Оч С1г.,.. 0-л} и С--А & задано отношение/? . Множеству С поставим в соответствие булеву матрицу размерности fix /Ті » в которой на пересечении і -й строки и j -го столбца стоит I, если справедливо &i Rj , и 0, в противном случае. Покрытием множества О » или решением построенной таким образом таблицы, называемой таблицей покрытий (ІЇЇ)» будем называть такую совокупность её строк, при пересечении которых с каждым столбцом имеется хотя бы одна отметка (I).
Определение I. Решение TEI называется безызбыточным, если из него нельзя удалить ни одной строки, не нарушив условие покрытия.
Определение 2. Минимальным решением ТП называется решение, содержащее наименьшее число строк. Обычно возникает необходимость определения минимального безызбыточного решения. Ниже приводятся вероятностные оценки решений таблиц по крытий, которые могут быть использованы для оценки качества приближенно-минимального решения, а также дан построения новых приближенных методов.
Обозначим N - число строк, L - число столбцов таблицы покрытий. Пусть Рк - вероятность того, что произвольный набор из к строк, к N t является решением, /тс можно определить следующим образом: к рк= р/С С (I.D где OJC - математическое ожидание числа всех решений, содержащих к строк. Значение S/c определяется последовательно за конечное число шагов: И OK = 2J & .
Здесь М= тіл { M ,Ms.t..., МІ.} , где Mj - число отметок в \ -м столбце. Пусть М= fijf (в случае нескольких столбцов с минимальным числом отметок выбирается любой). Выбор столбца с минимальным числом отметок позволяет уменьшить объём вычислений.
На первом шаге рассматриваются все сочетания из к строк, содержащие первую отметку столбца j . Затем рассматриваются все сочетания, содержащие вторую отметку и не содержащие первой, и так далее.
Значение Ок на 6-м промежуточном шаге соответствует -й отметке столбца J. . После каждого шага таблица преоб 19 разуется путем удаления строки, содержащей с. -ю отметку столб ца \ . Перед первым шагом берется исходная таблица. Од. вычисляется по формуле: где / - поправочный коэффициент , ( #,. - число сочетаний из К строк, содержащие строку t (имеющую отметку в минимальном столбце), cLl ; =(? если строка Lg имеет отметку в J -м столбце, в противном случае CLl J - / . Выражение 1 - 4 І s-i#./ W ПК 1 представляет собой вероятность покрытия j -го столбца рассматриваемыми сочетаниями строк.
Введение поправочного коэффициента обусловлено тем, что формула вычисления вероятности покрытия столбца таблицы получена при условии равной вероятности вхождения строк в решение. В действительности, значения этих вероятностей не равны между ообой. Так как каждый столбец должен покрываться хотя бы одной строкой из входящих в решение, то наибольшую вероятность попасть в покрытие ТП имеют строки, помеченные в столбцах с наименьшим количеством отметок. В качестве основного влияющешо фактора здесь следует отметить характер разброса отметок по строкам столбцов, т.е. взаимное расположение всех отметок в пределах таблицы.
Данное обстоятельство необходимо каким-то образом учитывать, и использование поправочного коэффициента является одним из возможных в данной ситуации выходов. Значение вероятности гк можно использовать для оценки качества приближенно-минимального решения ТП. Можно определить вероятность того, что минимальное решение будет содержать /с строк: . Р1=Р.Л U-Pi). 4 1 Вероятность того, что решение, содержащее К строк, является минимальным, можно определить по формуле: На основании вероятности гк можно определить значение вероятности гк того, что к произвольных строк таблицы покрытий образуют безызбыточное решение: Я - Рк U-P . )" . Очевидно, что / р = р где К0 - мощность минимального решения. Представляет также интерес оценка числа всех решений ТЕС, содержащих JC строк, как избыточных /Vpsy , так и безызбыточных
Экспериментальная проверка достоверности вероятностных: оценок
Для оценки эффективности приближенных методов решения таблиц покрытий и сравнения их по качеству получаемого решения необходимо проводить статистические испытания на потоке задач. В связи с этим возникает необходимость генерации потока задач.
Генерацию потока задач можно осуществлять разными способами. Возможно получение TU с использованием булевых функций, описывающих функционирование реальных комбинационных устройств, либо с помощью псевдослучайного датчика ТП. Второй способ более предпочтителен, так как он характеризуется меньшими временными затратами на генерацию ТП (что немаловажно при большом количестве задач), и , кроме того, позволяет генерировать ТП с заданными характеристиками.
Опишем псевдослучайный датчик ТП для проверки эффективности приближенных методов решения таблиц покрытий. Информативными параметрами для него являются: число строк ТП, число столбцов, параметр Д , определяющий отношение максимального количества отметок в столбцах к числу строк ТП. Среднее число от 22 меток в строке в этом случае будет равно Я А/ Количество отметок в столбце лежит в интервале /.2—/у 4J
Генерируемые ТП не содержат столбцов с единственной отметкой. Это ограничение не снижает общности, так как выделение ядра и исключение из ТП таких столбцов происходит на первоначальном этапе, предшествующем процессу решения таблицы покрытий.
Распределение числа столбцов по количеству отметок из интервала U-Мл] можно задать линейной, параболической, либо произвольной функцией.
В процессе генерации возможно удаление столбцов, поглощаемых другими столбцами ТП. Вероятности появления отметок в строках могут быть как равными, так и неравными. Для этих целей используются датчики случайных чисел, распределенных по равномерному и произвольному законам»
При генерации обеспечивается отсутствие строк, не имеющих ни одной отметки.Предусмотрена возможность применения к полученным в результате генерации ТП правила поглощения строк.
Б таблице 1.3 приведены значения числа безызбыточных решений таблиц покрытий, полученных при генерации 322 ТЇЇ с параметрами N = 17,/, = 50, Д = 0,3. Как виднс)йз этой таблицы, число решений для выбранных информативных параметров является случайной величиной. Это объясняется тем, что разброс отметок по строкам носит случайный характер.
Псевдослучайный датчик ТП применялся для проверки достоверности гипотез о вероятностных оценках. Достоверность определения Гк вероятности того, что к произвольных строк
В основу эвристики были положены следующие соображения. Энтропия является некоторой мерой, которая характеризует всю совокупность распределения веротяностей. В данном случае производилась замена $вктнческого неравновероятного вхождения строк в решение равновероятным о такой же энтропией.
Значение Н1\ определяется выражением
Так как А/у тип К в общем случае являются не целыми ве личинами, то значение ( следует рассматривать как C-OHKI-HVC1 + (НК 1НК\)С\
Ео втором варианте значение поправочного коэффициента вычислялось по формуле T4-dt( -dit\U-diti -0= -)) && Б этом случае коррекция числа сочетаний строк при учете их неравной вероятности вховдения в ршение производилась варьированием параметров d4 и cL& Экспериментально было установлено, 4T0Ctf- 1»5 и d= 1,1.
Для каждого значения К из интервала / /, Л// генерировались все возможные сочетания строк, которые затем проверялись на условие покрытия рассматриваемой таблицы. Полученные таким образом относительные частоты
Алгоритмы решения таблиц покрытий на основе вероятностных оценок
Вероятностные оценки таблиц покрытий являются конструктивными в том смысле, что они могут быть использованы для построения алгоритмов решения ТН.
Пусть /V - число строк таблицы. Будем называть решением (покрытием) ТП такую совокупность её строк, для которых при пересечении со столбцами таблицы в каждом найдется хотя бы одна отметка. Под ценой решения будем понимать число строк, входящих в него.
Рассмотрим возможные алгоритмы решения ТО" на основе вероятностных оценок. Будем обозначать: Р - вероятность того, что к произвольных строк покроют Тії; PKii //1/ -вероятность того, что і -я строка входит в решение с ценой, равной К При нахождении приближенно-минимального решения можно использовать правила удаления строк, удаления столбцов и приращения покрытия (добавления в решение ядра таблицы). При этом дополнительный объем вычислений компенсируется уменьшением размерности ТП, что в конечном итоге приводит к сокращению времени нахождения решения.
Возможные алгоритмы решения Та приведены на рис.2.2. Приведем их содержательное описание. Алгоритм АІ.
Для исходной ТП определяются значения вероятностей Pt / - / А/ В решение выбирается квазисущественная строка. ИЗ таблицы вычеркивается эта строка, а также столбцы, имещие отметку на пересечении с ней.
Значение параметра к (априорного числа строк в решении) уменьшается на единицу. При преобразовании ТП могут появиться строки, не содержащие ни одной отметки. В этом случае они вычеркиваются из таблицы. Для преобразованной ТП процедура повторяется. Преобразо 5Г Алгоритмы решения ТП на основе вероятностных оценок АЛГОРИТМЫ ОПРЕДЕЛЕНИЕ ЧИСЛА СТРОК В РЕШЕНИИ Выбор в решение строки сШХ значением Удаление строки с Шп значением Рк , 1 4 Выбор в "оеиіение строки С MM / удаление - с Точный глет од с заданной верхней границей Генерирование "решения с исп, датчика пссвдослуч. чисел Без учёта вероятностей вхождения строк в решение С учётом вероятностей вхождения строк в решение
На каздом этапе из таблицы вычеркивается строка с минимальным значением г# . Решение получается добавлением ядра преобразованной таблицы.
Значение параметра к уменьшается на число строк, содер і
жащихся в ядре преобразованной ТП. Из таблицы вычеркиваются сталбцы, содержащие строки из ядра, а также столбцы, поглощаемые ядром. Алгоритм A3. Этот алгоритм является объединением двух предыдущих. На каддом этапе происходит одновременно выбор в решение квазисущественной строки и удаление строки с минимальным значением РІ Алгоритм А4.
Находятся все решения с числом строк, не превосходящим заданного. В качестве верхней границы мощности решений выбирается значение параметра к .
При последовательном раскрытии скобок в формуле Петрика для описанш ТП (представление ТП в виде конъюнкции дизъюнкций отмеченных строк столбцов) анализируются промежуточные результаты. При этом отбрасываются те из них, цена которых в дальнейшем превысит верхнюю границу.
Таким образом, полный перебор всех возможных вариантов заменяется усеченным перебором. Минимальное решение затем выбирается из множества всех полученных решений мощности не более Л" , Алгоритм А5.
Производится генерирование набора из л строк с помощью датчика псевдослучайных чисел. При этом предполагается, что вероятности вхождения всех строк в решение одинаковы.
Сгенерированная таким образом совокупность из л строк далее проверяется на решение. Если эти строки покрывают ТП, то они выбираются в решение. В противном случае процесс генерации повторяется. Алгоритм А6.
Отличие его от алгоритма А5 заключается в том, что генерация набора из к строк производится с учетом вероятностей вхождения каждой строки в решение с ценой, равной К .
Следует отметить, что алгоритмы решения ТП на основе вероятностных оценок ориентированы на применение ЭЕМ (в частности, на использование в системе автоматизированного проектирования дискретных устройств управления).
Алгоритмы AI - А4 гарантируют получение решения. При этом результатом работы алгоритма А4 является точное минимальное покрытие ТИ.
Для практической реализации алгоритмов А5, А6 необходимо определить количество генераций в процессе построения решения. Это можно обеспечить двумя способами: 1. Заданием максимального времени, в течение которого производится генерация наборов строк. 2. Заданием максимального числа генераций.
В случае, если решение все же не будет получено, следует увеличить число генераций, либо применить какуккяибо другую стратегию (например, увеличить значение К ).
Определение совокупностей существенных переменных неполностью определённых булевых функции.
Необходимость в нахождении совокупностей существенных переменных булевых функций нередко возникает на этапе логического проектирования в процессе синтеза дискретных устройств управления. В ч:астности, решение этой задачи становится важным при проектировании устройств управления дискретной автоматики и цифровой обработки данных на программируемых логических матрицах. Очевидно, что имеет смысл говорить о совокупностях сущест венных переменных неполностью определенных булевых функций. Для полностью определенных булевых функций существует только одна такая совокупность, в которую входят все переменные из области задания функции.
Пусть неполностью определенная булева функция j( Х/,...УХЛ) от п переменных задана двумя множествами кубов МІ И MQ /35/, где ПІ - множество кубо в, на которых функция принимает значение, равное единице; Мо - множество кубо в, на юторых функция принимает значение, равное нулю.
Определение I. Совокупность О , составленная из аргументов X ,fiXlt .„,ZiK 5 {# ,...,#л} называется существенной для неполностью определенной функции f (&17...j/і) если существует неполностью определенная функция от к переменных т (3 ,..., Л) , такая, что
Определение 2. Совокупность «5 , $ {Xj1}.. M V C? » называется тупиковой для т(Хіг.. -, Хл) , если она явля ется существенной для / (Xt). . . i Хл) , и никакая совокуп ность 5 С не является существенной для функции Пусть б (п) означает мощность множества А.
Определение 3. Совокупность S называется кратчайшей существенной совокупностью аргументов функции у (Xf . Xn.) если не существует существенной совокупности 5 , такой, что
Основные теоретические положения для нахождения всех тупиковых совокупностей аргументов неполностью определенных булевых функций представлены в работах Ю.Й.Іуравлева /37,38/. Там же приведены некоторые асимптотические оценки, которые дают представление о зависимости числа и сложности тупиковых совокупностей функций от числа её аргументов. Показано, что максимальное количество различных тупиковых совокупностей неполностью определенной булевой функции / (Х1з. .., Хл.) определяется выражением
а отношение максимальной мощности из всех тупиковых совокупностей к минимальной равно /i-/ . Однако предлагаемый практический алгоритм для нахождения всех тупиковых совокупностей аргументов, даже по мнению автора, весьма громоздок и при больших размерностях трудно выполним и на ЭВМ. Кроме того, данный алгоритм может применяться только к функциям, представленным в совершенной нормальной форме.
Другие опубликованные алгоритмы /39,40/ обладают хотя бы одним из указанных недостатков. В /41/ предлагается итерационная процедура последовательного исключения потенциально несущественных аргументов из неполностью определенной булевой функции. Для выбора переменной, исключаемой на каждом шаге, предлагается численный эвристический критерий. Этот метод не дает гарантии получения оптимального решения. Кроме того, в работе не исследованы вопросы сходимости итерационной процедуры.
Ниже приводится описание практического алгоритма, в котором определение совокупностей существенных переменных неполностью определенной булевой функции сводится к решению таблицы покрытий. Он может быть применен к функциям , представленным в произвольной нормальной форме, и удобен для программирования на ЭВМ.
