Representation of an arbitrary number with weight sum of essential subtrees.pdf Увеличивающиеся сложность и значимость дискретных управляющих систем требуютих высокой надежности. Сложность систем повышает вероятность возникновениянеисправностей в них. Обнаружение неисправности в первый же момент ее проявленияна выходах устройства позволяет защитить систему, в которую устройствовстроено. Такое обнаружение неисправности может достигаться, например, за счетиспользования самопроверяемых схем, дающих возможность обнаруживать неисправностив режиме нормального функционирования схемы. Обнаружение осуществляетсяс помощью самотестируемого детектора кодовых слов некоторого кода, в частности(m, п)-кода, состоящего из всех булевых векторов длины n и веса m. На выходах само-проверяемого устройства, к которому подключен детектор слов (m, п)-кода, не всегдадостигаются всевозможные кодовые слова. Число l достигаемых кодовых слов можетбыть меньше числа всевозможных кодовых слов (числа сочетаний из n по m).В [1] предложена формула разложения множества кодовых слов (m, ^-кода длязаданных n и m:Dm (x ) = d 0 (x 1)Dm-k ( x *) v d 1 (x 1)Dm_-fc1( x *) v ... v Dm(x - fc ( x *). (1 )Здесь X - множество булевых переменных, |X| = n; {X 1,X *} - разбиение X ,|X 1| = k, |X*| = n - k; Dp(X;) есть дизъюнкция конъюнкций, представляющих всевозможныекодовые слова (q, р)-кода. Если n - k > k, то формула (1) используетсядля разложения каждого коэффициента D m ^ X ;), где i = 0,m, и т. д. Полученная вконечном итоге формула F , задающая все кодовые слова (m, ^-кода, представляетсянекоторым деревом D. Некоторые поддеревья в нём определяются как существенные.Каждому существенному поддереву сопоставляется выражение, которое являетсялогическим произведением ДНФ, отмечающих листья этого поддерева. Важнойхарактеристикой поддерева является его вес, то есть число кодовых слов (m, ^-кода,представляемых поддеревом. Вес поддерева равен произведению длин ДНФ, сопоставляемыхего листьям.Построение самотестируемого детектора для / кодовых слов (m, ^-кода основанона решении следующих двух задач:1) представление числа / суммой весов некоторых существенных поддеревьев дереваD, являющегося некоторым разложением (m, ^-кода с помощью формулы (1);2) построение самотестируемого детектора на базе полученного представления.Данная работа посвящена первой из этих задач. Возможность и сложность её решениязависят от числа существенных поддеревьев в дереве D и их весов. Вид дерева D,существенных поддеревьев в нём и значения весов последних определяются видомформулы F, представленной деревом D, который, в свою очередь, зависит от значенияпараметра k, выбираемого на каждом шаге разложения. В [1] значение k от шагак шагу не изменяется.В [2] был предложен эвристический подход к представлению произвольного числа/ суммой весов подмножества существенных поддеревьев в дереве D , построенном спостоянным k. При этом иногда приходилось менять ДНФ, сопоставляемые листьям,путем вычеркивания из них конъюнкций. Процедура коррекции ДНФ не была алгоритмизирована.В данной работе предлагается метод построения требуемого дерева D, позволяющийпредставить произвольное число / суммой весов подмножства его существенныхподдеревьев без изменения ДНФ, сопоставляемых их листьям. С этой целью на каждомшаге разложения (m, ^-кода с использовании формулы (1) выбирается k = [r /2 ].Здесь r на первом шаге равно n, а далее совпадает с числом переменных очередногокоэффициента разложения. Разложение выполняется до тех пор, пока r не окажетсяравным некоторому заданному значению r0. Такой метод позволяет увеличить числосущественных поддеревьев дерева D, уменьшая их веса и облегчая тем самым возможностьпредставления числа / суммой весов подмножества существенных поддеревьев.Предложен последовательный алгоритм, в котором на каждом шаге в построенном Dвыбирается существенное поддерево, вес которого наиболее близок к разности между /и суммой весов уже выбранных существенных поддеревьев. Экспериментально показано,что этим алгоритмом (при r0 = 2) можно получить необходимое представлениелюбого числа / в диапазоне от 2 до C^6. Выявлены некоторые свойства существенныхподдеревьев, связывающие величину r0 с весами последних.

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