Единичные проверяющие тесты для схем из функциональных элементов

Краткие сообщения

УДК 519.95

ЕДИНИЧНЫЕ ПРОВЕРЯЮЩИЕ ТЕСТЫ ДЛЯ СХЕМ ИЗ ФУНКЦИОНАЛЬНЫХ ЭЛЕМЕНТОВ

С. С. Коляда1

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

n

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

Circuits of functional elements in arbitrary complete finite bases are considered. Possibility

n

n

Key words: circuits of functional elements, identity checking tests, constant faults.

В работе рассматривается задача построения легкотестируемых схем из функциональных элементов в функционально полных конечных базисах. Допускаются единичные произвольные константные неисправности на выходах элементов, когда в неисправное состояние может перейти ровно один элемент схемы, который вне зависимости от того, что подается на его входы, выдает некоторую булеву константу 5, где 5 € {0,1}. Отсутствующие здесь определения некоторых общепринятых понятий и разъяснения по затрагиваемой проблематике можно найти, например, в работах [1-5].

Пусть S — схема, реализующая в исправном состоянии булеву функцию f (ж), х = (x\,..., xn). Схему S будем считать неизбыточной, если при переходе в любое неисправное состояние любого элемента эта схема реализует нетривиальную, т.е. отличную от f (X), функцию неисправности g(X).

Множество входных наборов T = {(Г\,..., Ъ\} называется единичным, проверяющим тестом для схемы S, реализующей функцию f, если для любой нетривиальной функции неисправности g существует набор ( из T, такой, что f (() = g(() число l называется длиной теста.

В работе [6] для схем в базисах В\ = {хку, х}, В2 = {хку, х ф у, 1}, Bs = {хку, х ф у ф 1, 0}, В4 = {хку, ху, ху1}, В5 = {хку}, В6 = {хУу, х}, В7 = {хУу, ху, 1}, В8 = {хУу, ху1, 0}, В9 = {х V у, х у, ху1}, В ю = {хУу}, Вц = {хку, х}, Bi2 = {хку, 1}, Вц = {хУу, х}, В14 = {х\/у, 0}, ¿is = {хку, х у 1}, £>i6 = {х V у, х ф у}, Вп = {хку, х\/ у} (т.е. в базисах из элементов, имеющих не более двух входов) установлен следующий результат.

Теорема 1. Для любой булевой функции f (xi,..., xn), где n ^ Ъ, и любого i € {1,..., 17} существует неизбыточная схем,а, в базисе Bi, реализующая данную функцию и допускающая единичный, проверяющий тест, длина, которого не превосходит, n + 3.

Аналогичная оценка для схем в базисе Жегалкина ранее была получена в [7], однако указанный там метод построения легкотестируемых схем годится только для базисов, содержащих конъюнкцию и линейную функцию (x ф y ил и x ф y ф 1).

Совсем недавно в [8] установлено, что любую булеву функцию можно реализовать схемой в базисе {хку, х ф у, 1 ,х(у V z) V х(у ~ z)}, допускающей единичный проверяющий тест из четырех наборов.

Основным результатом данной заметки является следующая

Теорема 2. Для любой булевой функции f (xi,..., xn), где n ^ 3, и любого функционально полного конечного ба,зи,са, существует неизбыточная схема в этом базисе, реализующая данную функцию и

n+3

Из-за ограниченности объема статьи ниже перечисляются лишь основные идеи и этапы доказательства теоремы 2 и приводятся наиболее важные вспомогательные утверждения. При распространении утверждения теоремы 1 на произвольные базисы используется метод расширения базисов, предложенный в [9]. Приведем некоторые важные определения и факты, касающиеся этого метода.

Пусть B — произвольный полный конечный базис; расширением, базиса B будем считать базис B

B

1 Коляда Сергей Сергеевич — асп. каф. дискретной математики мех.-мат. ф-та МГУ, e-mail: kolyadassQmail.ru.

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

ВВ входов). Отсюда следует, что для доказательства теоремы 2 достаточно установить ее для расширения В

Булеву функцию (х, у, г) = ху ф хг ф ух ф 71 ж ф 72у Ф 7зг Ф 74, где 7Ь ..., 74 е {0,1}, будем называть особенной [9]. Будем обозначать через Е7 элемент с тремя занумерованными входами, который реализует ^7(х, у, г) при подаче ж, у, г соответственно на 1, 2, 3-й вход. Из всех возможных наборов 7 достаточно рассмотреть наборы (1,1,1,74), (0,1,1,74), (0, 0,1,74), (0, 0, 0,74), где 74 = 0,1 (остальные сводятся к указанным переименованием переменных функции ^7).

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

В1 В2

В1 В2

01

ции f (х1,..., хп) существует неизбыточная схем,а 51 в базисе В1; допускающая единичный проверяющий тест длины, I. Тогда, существует неизбыточная схем,а, 52 в базисе В2; которая реализует f (х1,... ,хп) и допускает, единичный, проверяющий тест длины, I.

Наличие же в расширении любого конечного функционально полного базиса если не функций типа конъюнкции (или дизъюнкции), то хотя бы особенной функции гарантирует

Лемма 2 [9]. Максимальное расширение произвольного полного конечного ба,зи,са, содержит либо нелинейную функцию от двух переменных, л,ибо особенную функцию.

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

Схему £7с тремя входами будем называть 7-схемой, если она состоит из элементов Е7 и реализует функцию хуга V (ж V у)га(а — константа 0 или 1) при подаче х,у,г соответственно на 1, 2, 3-й вход, а при подаче на третий вход любой константы (0 или 1) получается схема, различными функциями неисправности которой являются константы. Отметим, что для каждого из рассматриваемых наборов 7 в [9] установлена возможность построения 7-схемы из одного или двух элементов Е7.

Для доказательства теоремы 2 устанавливается возможность построения для произвольной булевой функции от п переменных требуемой схемы (неизбыточной и допускающей единичный проверяющий тест не более чем из п + 3 наборов, п ^ 3) для базиса В^ = {ж&у, ж} при следующих дополнительных условиях. В схеме наряду с одиночными константными неисправностями типа 0 и типа 1 на выходах элементов допускаются: а) "тождественные" неисправности инверторов, когда все инверторы схемы переходят в неисправное состояние и реализуют тождественные функции своих входов (т.е. каждый инвертор реализует вместо отрицания тождественную функцию); б) одновременные однотипные константные неисправности инверторов, когда все инверторы переходят в неисправное состояние и реализуют булеву константу 5 (одну и ту же для всех инверторов; 5 € {0,1}).

Аналогичные возможности устанавливаются для базисов В'2 = {х V у, ж} и В'3 = {§,(ру, ж}, где 5 € {0,1}, а ^7 — произвольная особенная функция. Наконец, такие же возможности построения легкоте-стируемых схем распространяются на схемы в базисе В4 = {х ф у, х ~ у, ^7}, но уже без дополнительных условий, т.е. снова допускаются только одиночные константные неисправности на выходах элементов схем.

В самом доказательстве теоремы 2 можно выделить четыре этапа. Три первых коротких охватывают случаи, когда базисы содержат обе булевы константы или только одну из них; здесь рассуждения сходны с теми, которые использовались при доказательстве теоремы 1. Четвертый этап наиболее сложный. Здесь рассматриваются случаи, когда расширение базиса содержит отрицание и когда в расширении базиса отрицание отсутствует. В последнем случае показано, что расширение содержит хотя бы одну из функций х ф у, х&7у и хотя бы одну из функций х ~ у, х V у.

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

17 ВМУ, математика, механика, №4

СПИСОК ЛИТЕРАТУРЫ

1. Лупанов О.Б. Асимптотические оценки сложности управляющих систем. М.: Изд-во МГУ, 1984.

2. Чегис И.А., Яблонский C.B. Логические способы контроля работы электрических схем // Тр. Матем. ин-та АН СССР. 1958. 51. 270-360.

3. Яблонский C.B. Некоторые вопросы надежности и контроля управляющих систем // Математические вопросы кибернетики. Вып. 1. М.: Наука: Физматлит, 1988. 5-25.

4. Редькин Н.П. Надежность и диагностика схем. М.: Изд-во МГУ, 1992.

5. Яблонский C.B. Введение в дискретную математику. 2-е изд. М.: Наука, 1986.

6. Коляда С. С. О единичных проверяющих тестах для константных неисправностей на выходах функциональных элементов // Вестн. Моск. ун-та. Матем. Механ. 2011. № 6. 47-49.

7. Reddy S.M. Easily testable realization for logic functions // IEEE Trans. Comput. 1972. N I. 124-141.

8. Романов Д. С. Метод синтеза легкотестируемых схем в одном базисе, допускающих единичные проверяющие тесты константной длины // Вестн. Моск. ун-та. Матем. Механ. 2012. № 2. 24-29.

9. Редькин Н.П. О полных проверяющих тестах для схем из функциональных элементов // Математические вопросы кибернетики. Вып. 2. М.: Наука: Физматлит, 1989. 192-222.

Поступила в редакцию 13.07.2012

УДК 511.218

О КОЛИЧЕСТВЕ ДЕЛИТЕЛЕЙ ЦЕНТРАЛЬНОГО БИНОМИАЛЬНОГО КОЭФФИЦИЕНТА

Г. В. Федоров1

В статье выведены асимптотические формулы для выражений log т (СП) и log т( [1,..., nj). Ключевые слова: функция делителей, биномиальные коэффициенты, наименьшее общее кратное.

Asymptotic formulas are derived for the following expressions: log т ( СП ) and log т ( [1,..., nj ). Key words: divisor function, binomial coefficients, least common multiple.

В 1980 г. П. Эрдеш и Р. Грам [1] предположили, что для всех n > 4 "центральные" биномиальные коэффициенты (П") = СП не являются бесквадратными. А. Саркози [2] в 1985 г. доказал это предполо-

n

n > 4

В данной статье мы рассмотрим количество делителей "центрального" биномиального коэффициента. Теорема 1. При n ^ то имеет, место асимптотическая формула

log г

где 0 ^ T — произвольное фиксированное целое число, коэффициенты Ck вычисляются по формулам,

~ Г(log t)k ;

m=1Jm+2

В частности, из асимптотической формулы (1) следует, что

logr(C£l) = 2(log2

1 Федоров Глеб Владимирович — асп. каф. математических и компьютерных методов анализа мех.-мат. ф-та МГУ, e-maïl: glebonyat@mail.ru.