Том 24, номер 3, 2017 г., Стр. 80-103

УДК 519.718.7
Попков К. А.
О точном значении длины минимального единичного диагностического теста для одного класса схем

Аннотация:
Рассматривается задача синтеза неизбыточных схем из функциональных элементов в базисе {&, ∨, ¬}, реализующих булевы функции от $n$ переменных и допускающих короткие единичные диагностические тесты относительно однотипных константных неисправностей на выходах элементов. Для каждой булевой функции, допускающей реализацию неизбыточной схемой, найдено минимально возможное значение длины такого теста. В частности, доказано, что оно не превосходит двух.
Ил. 3, библиогр. 27.

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

DOI: 10.17377/daio.2017.24.546

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

Статья поступила 8 июня 2016 г.
Исправленный вариант — 27 февраля 2017 г.

Литература

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[19] Hirayama T., Koda G., Nishitani Y., Shimizu K. Easily testable realization based on single-rail-input OR-AND-EXOR expressions // IEICE Trans. Inf. Syst. 1999. Vol. E82-D, No. 9. P. 1278–1286.

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

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

[22] Rahagude N. P. Integrated enhancement of testability and diagnosability for digital circuits // MA Sci. Diss., VA Polytech. Inst. State Univ., Blacksburg, VA, 2010. 75 pp.

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

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

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

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

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