|
Эта публикация цитируется в 4 научных статьях (всего в 4 статьях)
Короткие полные проверяющие тесты для схем из двухвходовых функциональных элементов
К. А. Попков Институт прикладной математики им. М.В. Келдыша РАН, Миусская пл., 4, 125047 Москва, Россия
Аннотация:
Установлено, что почти любую булеву функцию от $n$ переменных можно реализовать схемой из функциональных элементов в базисе $\{x\,\&\,y,x\vee y,x\oplus y,1\}$, допускающей полный проверяющий тест длины не более $4$ относительно произвольных константных неисправностей на выходах элементов. Доказаны также следующие утверждения: любую булеву функцию от $n$ переменных можно реализовать схемой из функциональных элементов в базисе $\{x\,\&\,y,x\vee y,x\oplus y,1\}$ (в базисе $\{x\,\&\,y,x\vee y,x\vee\overline y,x\oplus y\}$), содержащей не более одной фиктивной входной переменной и допускающей полный проверяющий тест длины не более $5$ (соответственно не более $4$) относительно неисправностей такого же типа. Ил. 2, библиогр. 24.
Ключевые слова:
схема из функциональных элементов, произвольная константная неисправность, полный проверяющий тест.
Статья поступила: 16.07.2018 Переработанный вариант: 02.08.2018 Принята к публикации: 28.11.2018
Образец цитирования:
К. А. Попков, “Короткие полные проверяющие тесты для схем из двухвходовых функциональных элементов”, Дискретн. анализ и исслед. опер., 26:1 (2019), 89–113; J. Appl. Industr. Math., 13:1 (2019), 118–131
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/da919 https://www.mathnet.ru/rus/da/v26/i1/p89
|
Статистика просмотров: |
Страница аннотации: | 251 | PDF полного текста: | 81 | Список литературы: | 36 | Первая страница: | 8 |
|