О схемах, допускающих короткие единичные проверяющие тесты при произвольных неисправностях функциональных элементов | Прикладная дискретная математика. 2021. № 51. DOI: 10.17223/20710410/51/4

Доказано, что любую неконстантную булеву функцию от n переменных можно реализовать неизбыточной схемой из функциональных элементов в базисе {&, ⊕, ¬}, содержащей не более одной фиктивной входной переменной и допускающей единичный проверяющий тест длины не более 2n + 3 относительно произвольных неисправностей элементов.
  • Title О схемах, допускающих короткие единичные проверяющие тесты при произвольных неисправностях функциональных элементов
  • Headline О схемах, допускающих короткие единичные проверяющие тесты при произвольных неисправностях функциональных элементов
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 51
  • Date:
  • DOI 10.17223/20710410/51/4
Ключевые слова
схема из функциональных элементов, булева функция, неисправность, единичный проверяющий тест
Авторы
Ссылки
Чегис И.А., Яблонский С. В. Логические способы контроля работы электрических схем // Труды МИАН. 1958. Т. 51. С. 270-360.
Яблонский С. В. Надёжность и контроль управляющих систем // Материалы Всесоюзного семинара по дискретной математике и её приложениям (Москва, 31 января-2 февраля 1984г.). М.: Изд-во МГУ, 1986. С. 7-12.
Яблонский С. В. Некоторые вопросы надёжности и контроля управляющих систем // Математические вопросы кибернетики. Вып. 1. М.: Наука, 1988. С. 5-25.
Редькин Н. П. Надёжность и диагностика схем. М.: Изд-во МГУ, 1992. 192 с.
Бородина Ю. В. О схемах, допускающих единичные тесты длины 1 при константных неисправностях на выходах элементов // Вестник Московского университета. Сер. 1. Математика. Механика. 2008. №5. С. 49-52.
Попков К. А. Нижние оценки длин единичных тестов для схем из функциональных элементов // Дискретная математика. 2017. Т. 29. Вып. 2. С. 53-69.
Попков К. А. Единичные проверяющие тесты для схем из функциональных элементов в базисе «конъюнкция-отрицание» // Прикладная дискретная математика. 2017. №38. С. 66-88.
Reddy S. M. Easily testable realizations for logic functions // IEEE Trans. Comput. 1972. V.C-21. Iss. 11. P.1183-1188.
Коляда С. С. Единичные проверяющие тесты для схем из функциональных элементов // Вестник Московского университета. Сер. 1. Математика. Механика. 2013. №4. С. 32-34.
Коляда С. С. Верхние оценки длины проверяющих тестов для схем из функциональных элементов: дис.. канд. физ.-мат. наук. М., 2013. 77 с.
Романов Д. С. Метод синтеза легкотестируемых схем, допускающих единичные проверяющие тесты константной длины // Дискретная математика. 2014. Т. 26. Вып. 2. С.100-130.
Романов Д. С. О тестах для схем при неисправностях на выходах элементов // Материалы XVIII Междунар. конф. «Проблемы теоретической кибернетики» (Пенза, 19-23 июня 2017г.). М.: МАКС Пресс, 2017. С. 213-216.
Попков К. А. Короткие единичные тесты для схем при произвольных константных неисправностях на выходах элементов // Дискретная математика. 2018. Т. 30. Вып. 3. С. 99-116.
Коваценко С. В. Синтез легкотестируемых схем в базисе Жегалкина для инверсных неисправностей // Вестник Московского университета. Сер. 15. Вычислительная математика и кибернетика. 2000. №2. С. 45-47.
Редькин Н. П. О единичных проверяющих тестах схем при инверсных неисправностях элементов // XII Междунар. конф. по проблемам теоретической кибернетики (Н. Новгород, 1999). Тез. докл. М.: Изд-во механико-математического факультета МГУ, 1999. С.196.
Редькин Н. П. Единичные проверяющие тесты для схем при инверсных неисправностях элементов // Математические вопросы кибернетики. Вып. 12. М.: Физматлит, 2003. С. 217-230.
Попков К. А. Синтез легкотестируемых схем при однотипных константных неисправностях на входах и выходах элементов // Интеллектуальные системы. Теория и приложения. 2018. Т. 23. Вып. 3. С. 131-147.
Романов Д. С., Романова Е. Ю. Короткие тесты для схем в базисе Жегалкина // Интеллектуальные системы. Теория и приложения. 2016. Т. 20. Вып.3. С. 73-78.
Романов Д. С., Романова Е. Ю. Метод синтеза неизбыточных схем, допускающих единичные проверяющие тесты константной длины // Дискретная математика. 2017. Т. 29. Вып. 4. С. 87-105.
Попков К. А. Синтез легкотестируемых схем при произвольных константных неисправностях на входах и выходах элементов // Прикладная дискретная математика. 2019. №43. С. 78-100.
Попков К. А. Метод построения легко диагностируемых схем из функциональных элементов относительно единичных неисправностей // Прикладная дискретная математика. 2019. №46. С. 38-57.
Попков К. А. Короткие полные проверяющие тесты для схем из двухвходовых функциональных элементов // Дискретный анализ и исследование операций. 2019. Т. 26. №1. С. 89-113.
Яблонский С. В. Введение в дискретную математику. М.: Наука, 1986. 384 с.
 О схемах, допускающих короткие единичные проверяющие тесты при произвольных неисправностях функциональных элементов | Прикладная дискретная математика. 2021. № 51. DOI: 10.17223/20710410/51/4
О схемах, допускающих короткие единичные проверяющие тесты при произвольных неисправностях функциональных элементов | Прикладная дискретная математика. 2021. № 51. DOI: 10.17223/20710410/51/4