|
ИСТИНА |
Войти в систему Регистрация |
ФНКЦ РР |
||
Короткие тесты для схем в базисе Жегалкинастатья
- Авторы: Романов Д.С., Романова Е.Ю.
- Журнал: Интеллектуальные системы. Теория и приложения (ранее: Интеллектуальные системы по 2014, № 2, ISSN 2075-9460)
- Том: 20
- Номер: 3
- Год издания: 2016
- Издательство: [б.и.]
- Местоположение издательства: М.
- Первая страница: 73
- Последняя страница: 78
- Аннотация: В работе доказывается, что при любом целом неотрицательном n любую булеву функцию f от n переменных можно реализовать в базисе Жегалкина неизбыточной схемой из функциональных элементов (СФЭ) с n входами и одним выходом, допускающей единичный проверяющий тест длины не более 16 относительно одиночных произвольных константных неисправностей на входах и выходах элементов. Доказывается также существование конечного полного базиса, в котором при любом целом неотрицательном n любую булеву функцию f от n переменных можно реализовать неизбыточной СФЭ с n входами и одним выходом, допускающей единичный проверяющий тест длины не более 6 относительно одиночных произвольных константных неисправностей на входах и выходах элементов. Установлена асимптотика вида 2n - 2 log n + O(1) функции Шеннона длины единичного проверяющего теста для СФЭ в базисе Жегалкина относительно одиночных произвольных константных неисправностей на входах и выходах элементов, а также на входах схемы. Доказано, что при добавлении двух дополнительных выходов при любом целом неотрицательном n любую булеву функцию f от n переменных можно реализовать в базисе Жегалкина неизбыточной СФЭ с n входами, допускающей единичный проверяющий тест длины не более 18 относительно одиночных произвольных константных неисправностей на входах и выходах элементов, а также на входах схемы.
- Добавил в систему: Романов Дмитрий Сергеевич