Рассматривается задача синтеза неизбыточных схем из функциональных элементов, реализующих булевы функции от n переменных и допускающих короткие единичные проверяющие тесты относительно однотипных константных неисправностей на выходах элементов, в базисе {&, -} и схожих базисах. Для каждой булевой функции, допускающей реализацию неизбыточной схемой, найдено минимально возможное значение длины такого теста. В частности, доказано, что оно не превосходит трёх.
Скачать электронную версию публикации
Загружен, раз: 167
- Title Единичные проверяющие тесты для схем из функциональных элементов в базисе «конъюнкция-отрицание»
- Headline Единичные проверяющие тесты для схем из функциональных элементов в базисе «конъюнкция-отрицание»
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 38
- Date:
- DOI 10.17223/20710410/38/5
Ключевые слова
схема из функциональных элементов, константная неисправность, единичный проверяющий тест, logic network, stuck-at fault, single fault detection testАвторы
Ссылки
ЧегисИ.А., Яблонский С. В. Логические способы контроля работы электрических схем // Труды МИАН. 1958. Т. 51. С. 270-360
Яблонский С. В. Надежность и контроль управляющих систем // Материалы Всесоюзного семинара по дискретной математике и ее приложениям (Москва, 31 января-2 февраля 1984 г.). М.: Изд-во МГУ, 1986. С. 7-12.
Яблонский С. В. Некоторые вопросы надежности и контроля управляющих систем // Математические вопросы кибернетики. Вып. 1. М.: Наука, 1988. С. 5-25.
Редькин Н. П. Надежность и диагностика схем. М.: Изд-во МГУ, 1992. 192 с.
Reddy S. M. Easily testable realization for logic functions // IEEE Trans. Comput. 1972. V. C-21. No. 11. P. 1183-1188.
Коляда С. С. Верхние оценки длины проверяющих тестов для схем из функциональных элементов: дис.. канд. физ.-мат. наук. М., 2013. 77с.
Романов Д. С. Метод синтеза легкотестируемых схем, допускающих единичные проверяющие тесты константной длины // Дискретная математика. 2014. Т. 26. №2. С. 100-130.
Редькин Н. П. О полных проверяющих тестах для схем из функциональных элементов // Вестник Московского университета. Серия 1. Математика. Механика. 1986. №1. С. 72-74.
Редькин Н. П. О полных проверяющих тестах для схем из функциональных элементов // Математические вопросы кибернетики. Вып. 2. М.: Наука, 1989. С. 198-222.
Романов Д. С. О синтезе схем, допускающих полные проверяющие тесты константной длины относительно произвольных константных неисправностей на выходах элементов // Дискретная математика. 2013. Т. 25. №2. С. 104-120.
Редькин Н. П. О схемах, допускающих короткие тесты // Вестник Московского университета. Серия 1. Математика. Механика. 1988. №2. С. 17-21.
Редькин Н. П. О единичных диагностических тестах для однотипных константных неисправностей на выходах функциональных элементов // Вестник Московского университета. Серия 1. Математика. Механика. 1992. №5. С. 43-46.
Бородина Ю. В. О синтезе легкотестируемых схем в случае однотипных константных неисправностей на выходах элементов // Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика. 2008. №1. С. 40-44.
Попков К. А. О точном значении длины минимального единичного диагностического теста для одного класса схем // Препринты ИПМ им. М.В.Келдыша. 2015. №74. 21с.
Бородина Ю. В. Нижняя оценка длины полного проверяющего теста в базисе {х | у} // Вестник Московского университета. Серия 1. Математика. Механика. 2015. №4. С. 49-51.
Бородина Ю. В. О схемах, допускающих единичные тесты длины 1 при константных неисправностях на выходах элементов // Вестник Московского университета. Серия 1. Математика. Механика. 2008. №5. С. 49-52.
Бородина Ю. В., Бородин П. А. Синтез легкотестируемых схем в базисе Жегалкина при константных неисправностях типа 0 на выходах элементов // Дискретная математика. 2010. Т. 22. №3. С. 127-133.
Попков К. А. О единичных диагностических тестах для схем из функциональных элементов в базисе Жегалкина // Известия высших учебных заведений. Поволжский регион. Физико-математические науки. 2016. №3. С. 3-18.
Яблонский С. В. Введение в дискретную математику. М.: Наука, 1986. 384 с.
Единичные проверяющие тесты для схем из функциональных элементов в базисе «конъюнкция-отрицание» | Прикладная дискретная математика. 2017. № 38. DOI: 10.17223/20710410/38/5
Скачать полнотекстовую версию
Загружен, раз: 455