Том 20, номер 2, 2013 г., Стр. 58-74

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

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

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

Коляда Сергей Сергеевич ¹
1. Московский гос. университет им. М. В. Ломоносова,
Ленинские горы, 119991 Москва, Россия
е-mail: kolyadass@mail.ru

Статья поступила 15 января 2012 г.
Исправленный вариант — 9 октября 2012 г.

Литература

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

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

[3] Чегис И. А., Яблонский С. В. Логические способы контроля электрических схем // Тр. мат. ин-та им. В. А. Стеклова АН СССР. - 1958. - T. 51. - C. 270–360.

[4] Яблонский С. В. Введение в дискретную математику. 2-е изд. - М.: Наука, 1986. - 384 c.

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

[6] Reddy S. M. Easily testable realization for logic functions // IEEE Trans. Comput. - 1972. - N 1. - P. 124–141.