Современные информационные технологии/1.Компьютерная инженерия

К.т.н. Ткаченко В.Г., аспирант Кокорев А.В.

                            Одесская национальная академия связи

ПРЕДСТАВЛЕНИЯ МОНОТОННЫХ БУЛЕВЫХ

ФУНКЦИЙ ТЕЛЕКОММУНИКАЦИОННЫХ СИСТЕМ

В настоящее время значительно расширилась сфера применения цифровых  схем. В области телекоммуникаций эти схемы широко используются при сжатии и кодировании передаваемой информации, при цифровой коммутации, в маршрутизаторах и шлюзах. В связи с этим возникает проблема повышения надежности работы цифровых схем.

Традиционным подходом к повышению надежности является усложнение схем контроля, применение различных диагностических тестов [1]. Это приводит к удорожанию  электронных изделий и, как следствие, ограничению их применения. В работах [2]  предложен алгебраический подход, на основе которого разработан новый элементный базис для устройств обработки и преобразования информации повышенной надежности. При этом были исследованы и продвинуты на новый уровень такие области математики как комплементарная алгебра, предикатная алгебра выбора, аддитивно-мультипликативная алгебра. Для практического применения нового базиса требуются большие затраты, разработка новых стандартов и новых технологий. В [3] предложен комбинаторный подход для синтеза специальных классов булевых функций, в частности функций, удовлетворяющих критерию строгого лавинного эффекта. Комбинаторный подход позволяет производить синтез функций в традиционном элементном базисе.

Однако одного комбинаторного подхода недостаточно для класса монотонных булевых функций (МБФ) [4], так как  теория этих функций слабо представлена в литературе, а многие вопросы, касающиеся классификации этих функций, вычисления числа функций заданного класса, алгоритмов перехода к соседним функциям, связи этих функций с другими областями математики, вообще не рассматриваются.

Целью настоящей работы является показать, что повышения надежности цифровых электронных схем можно достигнуть в традиционно используемом элементном базисе за счет более широкого использования при их синтезе класса МБФ.

Каждой булевой функции от n переменных соответствует некоторое подмножество элементов булевой решетки ранга n, то есть множество входных наборов, на которых булева функция равна единице. Верно и обратное: каждому подмножеству элементов решетки отвечает некоторая булева функция. Такое представление является наиболее простым способом описания булевой функции. Если произвольный элемент булевой решетки входит в указанное подмножество для МБФ, то и все элементы большие него тоже входят в это подмножество.

Таким образом, вместо всех элементов, на которых МБФ равна 1, можно задать только минимальные элементы. Любая МБФ полностью определяется минимальными элементами булевой решетки из подмножества элементов этой решетки, на которой МБФ равна 1. Этим элементам соответствует некоторая антицепь в булевой решетке. Верно и обратное: любая антицепь определяет минимальные элементы некоторой МБФ. Если каждому минимальному элементу сопоставить конъюнкцию переменных, входящих во  входной набор, соответствующий минимальному элементу, а затем записать дизъюнкцию этих конъюнкций, то получим минимальную дизъюнктивную форму МБФ. С другой стороны каждому элементу булевой решетки ранга n соответствует некоторое подмножество множества из n элементов, а любой антицепи соответствует семейство подмножеств Шпернера, т.е. подмножеств, не входящих одно в другое.

Аналогично можно рассмотреть подмножество элементов булевой решетки, на которых МБФ равна 0 и выбрать из этого подмножества максимальные элементы. Максимальным элементам также соответствует некоторая антицепь в булевой решетке. Этой антицепи также соответствует семейство подмножеств Шпернера. Если каждому максимальному элементу сопоставить дизъюнкцию переменных, входящих во  входной набор, соответствующий максимальному элементу, а затем записать конъюнкцию этих дизъюнкций, то получим минимальную конъюнктивную форму МБФ. Если в минимальной конъюнктивной форме заменить операции дизъюнкции на операции конъюнкции, а операции конъюнкции на операции дизъюнкции, то после раскрытия скобок и приведения подобных членов получим минимальную дизъюнктивную форму двойственной МБФ. Например, двойственной к МБФ ABC является МБФ ABАC.

Еще один способ описания МБФ можно получить, если линейно упорядочить все входные наборы, а затем для каждого набора в строку записать значения (нули и единицы), которые МБФ принимает на этих наборах. Если рассматриваются МБФ от n переменных, то их можно описать наборами (строками) из 2n нулей и единиц. Если взять поэлементную дизъюнкцию или конъюнкцию таких наборов, то полученный набор также будет МБФ. Пост доказал [4] более общее утверждение о том, что монотонные булевы функции образуют замкнутый класс. Это значит, что если в МБФ f (x1, x2, … , xn) от n переменных вместо всех переменных подставить какие-либо МБФ от m переменных, то получается МБФ от m переменных. С помощью операций дизъюнкции и конъюнкции такие наборы можно представить в виде решетки. Такая решетка называется свободной дистрибутивной решеткой ранга n. Из построения следует, что она является подрешеткой булевой решетки ранга 2n.

Каждый минимальный набор МБФ можно представить в двоичном виде. Эти наборы можно записать в виде (0,1)-матрицы. Для обеспечения однозначности входные наборы в матрице упорядочены по возрастанию количества нулей, а наборы с одинаковым количеством нулей по возрастанию входных наборов как двоичных чисел. В результате получается способ описания МБФ в виде (0,1)-матрицы.

В [5]  показано, что отношение среднего количества отказов на произвольную булеву функцию от n переменных к отношению среднего количества отказов на произвольную МБФ от n переменных равно , где m — целая часть от деления   на 2. Для n равному 2 или 3 это отношение равно 2, а для n равному 10 это отношение равно 4,06.

В заключение отметим следующее. На основе проведенных исследований показано, что в случае использования при синтезе цифровых устройств монотонных булевых функций вместо произвольных булевых функций достигается уменьшение количества возможных отказов, т.е. повышение надежности работы синтезируемого устройства. Это уменьшение зависит от числа входов схемы, реализующей булеву функцию, и с ростом числа входов схемы повышается.

 

Литература

 

.  

1.      Иоффе М.И.  Диагностирование логических схем/ М.И.  Иоффе.– М.: Наука, 1989. – 158 с.

2.      Волгин Л.И. Логические основы математической теории надежности/ Л.И.Волгин.  –Ульяновск: УлГТУ,   1997. – 44 с.

3.      Самофалов А.Г. Комбинаторный подход к синтезу специальных классов

 булевых функций / А.Г. Самофалов, А.П. Марковский // Электронное моделирование. – 2004. – Т26. – №3. – С. 27– 40.

4.      Яблонский С.В. Функции алгебры логики и      классы Поста/ С.В. Яблонский, Г.П. Гаврилов, В.Б.  Кудрявцев. –  М.: Наука, 1966. – 120 с.

5. Ткаченко В.Г. Отказы цифровых схем.и представления монотонных булевых функций  / В.Г. Ткаченко //Наукові праці ОНАЗ ім. О.С. Попова. – Одеса, 2006. – №2. – С. 54 – 69.