|
Дискретный анализ и исследование операций, сер. 1, 1998, том 5, выпуск 3, страницы 44–63
(Mi da361)
|
|
|
|
Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)
Минимальные самокорректирующиеся схемы для одной последовательности булевых функций
Н. П. Редькин Московский государственный университет им. М. В. Ломоносова, механико-математический факультет
Аннотация:
Рассматриваются схемы из надежных и ненадежных функциональных элементов, в которых выход каждого элемента можно соединять только с одним входом какого-нибудь одного элемента схемы. Каждый надежный элемент имеет вес $P\geqslant 3$ и всегда реализует приписанную ему функцию из базиса $\textrm Б$. Каждый ненадежный элемент имеет вес 1 и в исправном состоянии реализует приписанную ему функцию из базиса $\textrm Б$, а в неисправном состоянии – булеву константу $\delta$. Схема считается 1-самокорректирующейся, если при переходе в неисправное состояние любого одного ненадежного элемента она реализует ту же самую функцию, что и при исправном состоянии всех ее элементов. Под сложностью схемы понимается сумма весов всех ее элементов, а через $L_1(f)$ обозначается наименьшая из сложностей самокорректирующихся схем, реализующих булеву $f$. Пусть $p_1=x_1y_1$, а $p_n=x_ny_n\vee(x_n\vee y_n)p_{n-1}$, где $n=2,3,\dots$. Для последовательности булевых функций $p_n$ и базиса $\textrm Б=\{\&,\vee\}$ (а также и для $\textrm Б=\{\&,\vee,\overline{\phantom a}\}$) при любом фиксированном $\delta$ и $n>1$ установлено, что $L_1(p_n)=8n-6+P$. Библиогр. 5.
Статья поступила: 05.02.1998
Образец цитирования:
Н. П. Редькин, “Минимальные самокорректирующиеся схемы для одной последовательности булевых функций”, Дискретн. анализ и исслед. опер., сер. 1, 5:3 (1998), 44–63
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/da361 https://www.mathnet.ru/rus/da/v5/s1/i3/p44
|
Статистика просмотров: |
Страница аннотации: | 189 | PDF полного текста: | 85 |
|