Том 25, номер 2, 2018 г., Стр. 62-81

УДК 519.718.7
Попков К. А.
Полные проверяющие тесты длины два для схем при произвольных константных неисправностях элементов

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

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

DOI: 10.17377/daio.2018.25.592

Попков Кирилл Андреевич ¹
1. Институт прикладной математики им. М. В. Келдыша РАН,
Миусская пл., 4, 125047 Москва, Россия
е-mail: kirill-formulist@mail.ru

Статья поступила 6 октября 2017 г.

Литература

[1] Бородина Ю. В. О синтезе легкотестируемых схем в случае однотипных константных неисправностей на выходах элементов // Вестн. Моск. ун-та. Сер. 15. Вычисл. математика и кибернетика. 2008. № 1. С. 40–44.

[2] Бородина Ю. В. О схемах, допускающих единичные тесты длины 1 при константных неисправностях на выходах элементов // Вестн. Моск. ун-та. Сер. 1. Математика. Механика. 2008. № 5. С. 49–52.

[3] Бородина Ю. В. Нижняя оценка длины полного проверяющего теста в базисе {$x | y$} // Вестн. Моск. ун-та. Сер. 1. Математика. Механика. 2015. № 4. С. 49–51.

[4] Бородина Ю. В., Бородин П. А. Синтез легкотестируемых схем в базисе Жегалкина при константных неисправностях типа 0 на выходах элементов // Дискрет. математика. 2010. Т. 22, вып. 3. С. 127–133.

[5] Коляда С. С. Верхние оценки длины проверяющих тестов для схем из функциональных элементов: Дис. ... канд. физ.-мат. наук: 01.01.09. М., 2013. 77 с.

[6] Попков К. А. Нижние оценки длин полных диагностических тестов для схем и входов схем // Прикл. дискрет. математика. 2016. № 4. С. 65–73.

[7] Попков К. А. О единичных диагностических тестах для схем из функциональных элементов в базисе Жегалкина // Изв. вузов. Поволж. рег. Физ.-мат. науки. 2016. № 3. С. 3–18.

[8] Попков К. А. Единичные проверяющие тесты для схем из функциональных элементов в базисе «конъюнкция-отрицание». М., 2017. 31 с. (Препринт ИПМ им. М. В. Келдыша; № 30).

[9] Попков К. А. О точном значении длины минимального единичного диагностического теста для одного класса схем // Дискрет. анализ и исслед. операций. 2017. Т. 24, № 3. С. 80–103.

[10] Редькин Н. П. О полных проверяющих тестах для схем из функциональных элементов // Вестн. Моск. ун-та. Сер. 1. Математика. Механика. 1986. № 1. С. 72–74.

[11] Редькин Н. П. О схемах, допускающих короткие тесты // Вестн. Моск. ун-та. Сер. 1. Математика. Механика. 1988. № 2. С. 17–21.

[12] Редькин Н. П. О полных проверяющих тестах для схем из функциональных элементов // Мат. вопросы кибернетики. Вып. 2. М.: Наука, 1989. С. 198–222.

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

[14] Редькин Н. П. О единичных диагностических тестах для однотипных константных неисправностей на выходах функциональных элементов // Вестн. Моск. ун-та. Сер. 1. Математика. Механика. 1992. № 5. С. 43–46.

[15] Романов Д. С. О синтезе схем, допускающих полные проверяющие тесты константной длины относительно произвольных константных неисправностей на выходах элементов // Дискрет. математика. 2013. Т. 25, вып. 2. С. 104–120.

[16] Романов Д. С. Метод синтеза легкотестируемых схем, допускающих единичные проверяющие тесты константной длины // Дискрет. математика. 2014. Т. 26, вып. 2. С. 100–130.

[17] Романов Д. С., Романова Е. Ю. Метод синтеза неизбыточных схем, допускающих короткие единичные диагностические тесты при константных неисправностях на выходах элементов // Изв. вузов. Поволж. рег. Физ.-мат. науки. 2016. № 2. С. 87–102.

[18] Угольников А. Б. Классы Поста. Уч. пос. М.: Изд-во ЦПИ при мех.-мат. фак-те МГУ, 2008. 64 с.

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

[20] Яблонский С. В. Надежность и контроль управляющих систем // Мат. Всесоюз. семинара по дискрет. математике и ее прил. (Москва, 31 января – 2 февраля 1984 г.). М.: Изд-во МГУ, 1986. С. 7–12.

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

[22] DasGupta S., Hartmann C. R. P., Rudolph L. D. Dual-mode logic for function-independent fault testing // IEEE Trans. Comput. 1980. Vol. 29, No. 11. P. 1025–1029.

[23] Geetha V., Devarajan N., Neelakantan P. N. Network structure for testability improvement in exclusive-OR sum of products Reed–Muller canonical circuits // Int. J. Eng. Res. Gen. Sci. 2015. Vol. 3, No. 3. P. 368–378.

[24] Hayes J. P. On modifying logic networks to improve their diagnosability // IEEE Trans. Comput. 1974. Vol. 23, No. 1. P. 56–62.

[25] Hirayama T., Koda G., Nishitani Y., Shimizu K. Easily testable realization based on OR-AND-EXOR expansion with single-rail inputs // IEICE Trans. Inf. Syst. 1999. Vol. E-82D, No. 9. P. 1278–1286.

[26] Jameil A. K. A new single stuck fault detection algorithm for digital circiuts // Int. J. Eng. Res. Gen. Sci. 2015. Vol. 3, No. 1. P. 1050–1056.

[27] Neelakantan P. N., Ebenezer Jeyakumar A. Single stuck-at fault diagnosing circuit of Reed–Muller canonical exclusive-or sum of product Boolean expressions // J. Comput. Sci. 2006. Vol. 2, No. 7. P. 595–599.

[28] Rahagude N. P. Integrated enhancement of testability and diagnosability for digitac circuits: Mast. Sci. Dissertation. Virginia Polytech. Inst. State Univ., Blacksburg, VA, 2010. 75 pp.

[29] Rahaman H., Das D. K., Bhattacharya B. B. Testable design of AND-EXOR logic networks with universal test sets // Comput. Electr. Eng. 2009. Vol. 35, No. 5. P. 644–658.

[30] Reddy S. M. Easily testable realizations for logic functions // IEEE Trans. Comput. 1972. Vol. 21, No. 11. P. 1183–1188.

[31] Saluja K. K., Reddy S. M. On minimally testable logic networks // IEEE Trans. Comput. 1974. Vol. 23, No. 5. P. 552–554.

[32] Saluja K. K., Reddy S. M. Fault detecting test sets for Reed–Muller canonic networks // IEEE Trans. Comput. 1975. Vol. 24, No. 10. P. 995–998.

[33] Singh S. P., Sagar B. B. Stuck-at fault detection in combinational network coefficients of the RMC with fixed polarity (Reed–Muller coefficients) // Int. J. Emerg. Trends Electr. Electron. 2013. Vol. 1, No. 3. P. 93–96.