Том 26, номер 1, 2019 г., Стр. 89-113

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

Аннотация:
Установлено, что почти любую булеву функцию от $n$ переменных можно реализовать схемой из функциональных элементов в базисе {$x \And y, x \lor y, x \oplus y, 1$}, допускающей полный проверяющий тест длины не более 4 относительно произвольных константных неисправностей на выходах элементов. Доказаны также следующие утверждения: любую булеву функцию от $n$ переменных можно реализовать схемой из функциональных элементов в базисе {$x \And y, x \lor y, x \oplus y, 1$} (в базисе {$x \And y, x \lor y, x \lor \bar{y}, x \oplus y$}), содержащей не более одной фиктивной входной переменной и допускающей полный проверяющий тест длины не более 5 (соответственно не более 4) относительно неисправностей такого же типа.
Ил. 2, библиогр. 24.

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

DOI: 10.33048/daio.2019.26.623

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

Статья поступила 16 июля 2018 г.
После доработки — 2 августа 2018 г.
Принята к публикации 28 ноября 2018 г.

Литература

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

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

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

[4] Попков К. А. О тестах замыкания для контактных схем // Дискрет. математика. 2016. Т. 28, вып. 1. С. 87–100.

[5] Попков К. А. Полные проверяющие тесты длины два для схем при произвольных константных неисправностях элементов // Дискрет. анализ и исслед. операций. 2018. Т. 25, № 2. С. 62–81.

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

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

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

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

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

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

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

[13] 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.

[14] 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.

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

[16] 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.

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

[18] 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.

[19] Rahagude N. P. Integrated enhancement of testability and diagnosability for digital circuits: Diss. . . . Mast. Sci. Blacksburg, Virginia, 2010. 75 pp.

[20] 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.

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

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

[23] 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.

[24] 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. (IJETEE). 2013. Vol. 1, No. 3. P. 93–96.