Основы Кибернетики, Алгоритмы решения задач/Задачи на синтез схем

Материал из eSyr's wiki.

Содержание 1 По заданной ФАЛ с помощью простейших методов, метода каскадов или метода Шеннона построить реализующую ее СФЭ или КС. 1.1 Простейшие методы 1.1.1 Промежуточные действия 1.1.2 Получение СФЭ 1.1.3 Получение КС 1.2 Метод каскадов 1.2.1 Промежуточные действия 1.2.1.1 Пример 1.2.2 Получение СФЭ 1.2.3 Получение КС 1.3 Метод Шеннона 1.3.1 Промежуточные действия 1.3.2 Получение СФЭ 1.3.3 Получение КС 2 Оценить сверху или снизу сложность конкретной ФАЛ или сложность самой сложной ФАЛ из заданного множества в заданном классе схем. 2.1 Оценка сложности самой сложной ФАЛ из класса 2.1.1 Пример 2.1.2 Пример 2.1.3 Оценка снизу 2.2 Оценка сложности ФАЛ 2.2.1 Оценка сверху 2.3 Оценка сложности самой сложной ФАЛ из класса 2.3.1 Оценка снизу 3 По заданной КС построить эквивалентную ей самокорректирующуюся КС. 3.1 Определение самокорректирующейся КС 3.2 Простейший способ построения 3.2.1 Пример 3.3 Способы с оптимизацией числа дуг самокорректирующейся КС 3.3.1 Для исправления одного замыкания 3.3.2 Для исправления одного обрыва цепи

По заданной ФАЛ с помощью простейших методов, метода каскадов или метода Шеннона построить реализующую ее СФЭ или КС.

Простейшие методы

Промежуточные действия

• Если ФАЛ представлена в виде таблицы, то построим по ней сокращённую(может совершенную????) ДНФ (как объединение всех возможных случаев, когда она равна 1).
• Если ФАЛ представлена в виде формулы, преобразуем ее, чтобы остались только функции базиса Б₀. Кроме того, поднимаем все отрицания (они должны стоять только над переменными, но не над бо́льшими кусками выражения).

Получение СФЭ

Строим как-нибудь подвыражения в соответствии с приоритетом операций. Поскольку оставлены только функции базиса Б₀, то это не вызывает особых затруднений. Что вижу, то и рисую.

Получение КС

Разбираем формулу

• A ∨ B преобразуем в ветвление, где один вариант реализует A, а другой — B
• A & B преобразуем в последовательное соединение, где первая часть реализует A, другая — B.
• x_i преобразуем в контакт с меткой x_i
• x_i преобразуем в контакт с меткой x_i

Метод каскадов

Промежуточные действия

Пусть у нас имеются булевы функции F₁(x₁,x₂,...x_n),...,F_k(x₁,x₂,...x_n), зависящие от n переменных. Обозначим следующее множество:

M0 = {F1(x1,x2,...xn),...,Fk(x1,x2,...xn)}.

В простейшем случае, в нем одна функция. Воспользуемся следующим приемом:

F(x1,x2,...xn)=x1*F(1,x2,...xn)V x1*F(0,x2,...xn)

Тогда определим правило построения следующих множеств (M₁,M₂,...,M_n):

Mi+1 = {g(0,xi+1,...xn)|g∈Mi} U {g(1,xi+1,...xn)|g∈Mi}.

Если функция представлена строкой значений, то формируем новое множество из левых и правых половин. Если функция представлена формулой, то подставляем в нее x_i=0 и x_i=1 и упрощаем. При этом после построения из M_i удаляются все фунции, несущественно зависящие от x₁ (для строк значений это хорошо видно, т.к. левая и правая половина совпадает)

Пример

f1(x1,x2,x3,x4)=(1000 0010 1111 1000)
f2(x1,x2,x3,x4)=(1000 1111 0010 1000)

• M₀={(1000 0010 1111 1000),(1000 1111 0010 1000)}
• M₁={(1000 0010),(1111 1000),(1000 1111),(0010 1000)}
• M₂={(1000),(0010),(1111)}
• M₃={(10),(00),(11)}
• M₄={0,1}

Получение СФЭ

Реализуем на базе любого входа

• 0 = x_i & x_i
• 1 = x_i V x_i

Для реализации элемента M_i используем элементы M_i+1: пусть f(0,x_i+1,...x_n)=g(x_i+1,...x_n) и f(1,x_i+1,...x_n)=h(x_i+1,...x_n).

Тогда для реализации f соединеним дизъюнкцией конъюнкцию g и x_i с конъюнкцией h и x_i.

Реализацию элементов M₀ метим как выходы СФЭ.

Получение КС

Обозначаем все элементы всех множеств узлами КС.

• если g(x_i+1,...x_n)=h(0,x_i+1,...x_n), то соединим g и h контактом с меткой x_i
• если g(x_i+1,...x_n)=h(1,x_i+1,...x_n), то соединим g и h контактом с меткой x_i

После этого удаляем вершину с меткой 0 и все ведущие в нее контакты. Вершину с меткой 1, а также F₁,...,F_k помечаем как входы КС.

Метод Шеннона

Промежуточные действия

Выбираем некоторое 1≤q≤n. Расклыдаваем исходное f(x',x") = V x_i+1^σ_i+1 & x_i+2^σ_i+2 & ... & x_n^σ_n & f_σ"(x'). Обычно выбирают q = округленноый вниз(log₂(n-2*log₂(n))). После чего составляется универсальный многополюсник порядка q(имеющий q входов и 2ⁿ выходов) и мультиплексор порядка n-q (зависщий от адресных переменных x_i+1, ... ,x_n и от выходов универсального многополюсника, выдающий на выход f_σ"(x') в соответствии с приведенной формулой в свой единственный выход).

Данный метод не применяется на практике для построения КС или СФЭ, это скорее мысленный эксперимент вроде падающего из окна Дэвида Дойча или квантового самоубийцы, используемый затем Шенноном и его последователями для оценки функции Шеннона...

Получение СФЭ

Универсальный многополюсник в СФЭ выглядит так: Мультиплексор порядка q для f(x) в СФЭ выгладит так:

Получение КС

Универсальный многополюсник в КС выглядит так: точно так же как в методе каскадов к каждой вершине приписываем x₁ или x₁, дабы соединить с новой волной вершин. В каждой следующем множестве будет в 2 раза больше вершин. Мультиплексор порядка q для f(x) в КС выгладит так:

Оценить сверху или снизу сложность конкретной ФАЛ или сложность самой сложной ФАЛ из заданного множества в заданном классе схем.

Оценка сложности самой сложной ФАЛ из класса

Для того, что посчитать сложность самой сложной ФАЛ из некоторого класса Q(n) ∈ P₂(n), то есть, иначе говоря, вычислить функцию Шеннона, связанную с классом Q(n) (и для некоторого класса cхем U — например, СФЭ или КС), необходимо выполнить следующие шаги:

1. Посчитать число функций в заданном классе Q(n).
2. Сразу же из этого получить асимптотически нижнюю оценку функции Шеннона, связанной с классом Q(n):
   • L^K(Q(n)) ≳ log(|Q(n)|) / log(log(|Q(n)|))
   • L^C(Q(n)) ≳ log(|Q(n)|) / log(log(|Q(n)|))
3. Показать, как для любой функции из данного класса построить схему из класса U, реализующую данную функцию и имеющую сложность, асимптотически равную вычисленной нижней оценке. Из этого будет следовать, что полученная асимптотически нижняя оценка является и асимптотически верхней оценкой, а из этого, в свою очередь, будет следовать, что функция Шеннона для заданного класса U(n) будет просто асимптотически равна полученной нижней оценке.
   • В пункте 3 всегда пригождается следующее: для любой функции от n переменных можно построить, реализующую её СФЭ и КС со сложностью, асимптотически не превосходящей 2ⁿ / n

Пример

• Посчитать функцию Шеннона, связанную с классом самодвойственных функций, для класса СФЭ.
  • Самодвойственная функция f: f(x₁, …, x_n) = f(x₁, …, x_n)

Решение

1. Первый пункт является самым главным. В нём нужно получить некоторую формулу, в которой любая функция из заданного класса выражается через функцию от меньшего числа переменных. Полученная формула пригодится и впоследствии. Например, для класса самодвойственных функций, разложим функцию f по первой переменной f(x₁, x₂, …, x_n) = x₁ & f(0, x₂, …, x_n) ∨ x₁ & f(1, x₂, …, x_n) = x₁ & f(0, x₂, …, x_n) ∨ x₁ & f(0, x₂, …, x_n) = x₁ & f₀(x₂, …, x_n) ∨ x₁ & f₀(x₂, …, x_n), где f₀ = f(0, x₂, …, x_n). Перепишем это в виде f(x₁, …, x_n) = x₁ ⊕ f₀(x₂ ⊕ x₁, …, x_n ⊕ x₁) (*). Теперь видно, самодвойственная функция от n переменных однозначно определяется функцией f₀ от n − 1 переменной, и, следовательно, число самодвойственных функций от n переменных равно 2^{2n − 1}. В принципе, это и ежу очевидно, но полученная нами (*) потребуется нам в дальнейшем.
2. Из пункта 1 следует что L^C(Q(n)) ≳ 2^{n − 1} / n
3. Из (*), а также из утверждения строим схему для произвольной самодвойственной функции. Строим f₀ (сложность 2^{n − 1} / (n − 1)). Для n «⊕» потребуется ещё не более, чем C × n функциональных элементов. В итоге как раз и получится, что сложность результирующей схемы асимптотически не превосходит 2^{n − 1} / n

Пример

• Посчитать функцию Шеннона, также для класса СФЭ, связанную с классом функций, таких, что:

f(x₁, x₂, x₃, …, x_n) = f(x₃, x₁, x₂, …, x_n)

Решение

1. Разлагаем f по первым трём переменным:
   • f(x₁, x₂, x₃, x₄, …, x_n) = x₁ & x₂ & x₃ & f(0, 0, 0, x₄, …, x_n) ∨ x₁ & x₂ & x₃ & f(0, 0, 1, x₄, …, x_n) ∨ x₁ & x₂ & x₃ & f(0, 1, 0, x₄, …, x_n) ∨ x₁ & x₂ & x₃ & f(0, 1, 1, x₄, …, x_n) ∨ x₁ & x₂ & x₃ & f(1, 0, 0, x₄, …, x_n) ∨ x₁ & x₂ & x₃ & f(1, 0, 1, x₄, …, x_n) ∨ x₁ & x₂ & x₃ & f(1, 1, 0, x₄, …, x_n) ∨ x₁ & x₂ & x₃ & f(1, 1, 1, x₄, …, x_n) = (x₁x₂x₃ ∨ x₁x₂x₃) & f_a ∨ ((x₁x₂x₃ ∨ x₁x₂x₃)) & f_b (*),
     где f_a = f(0, 0, 0, x₄, …, x_n) = f(1, 0, 0, x₄, …, x_n) = f(1, 1, 0, x₄, …, x_n) = f(1, 1,1,x4,...,xn) = f(0, 1, 1, x₄, …, x_n) = f(0, 0, 1, x₄, …, x_n);
     f_b = f(0, 1, 0, x₄, …, x_n) = f(1, 0, 1, x₄, …, x_n). Теперь видно, что функция из данного класса однозначно определяется парой (f_a, f_b), где f_a, f_b — функции от n − 3 переменных. Таким образом, число функций из заданного класса равно числу таких пар, т. е. 2^{2n − 3} × 2^{2n − 3} = 2^{2n − 2}
2. Из (1) следует, что L^C(Q(n)) ≳ 2^{n − 2} / n
3. Опять же, из (*) ясно, как строить схему для произвольной функции из заданного класса. Строим СФЭ для функций f_a, f_b (сложность каждой ≤ (2^{n − 3} / (n − 3)). И, кроме того, нам потребуется дополнительная константа С «∨», «&» и «¬» для реализации (*). Складывая (2^{n − 3} / (n − 3)) + (2^{n − 3} / (n − 3)) + С, получим как раз, что это ≲ 2^{n − 2} / n.

Оценка снизу

Оценка сложности ФАЛ

Оценка сверху

Оценка сложности самой сложной ФАЛ из класса

Оценка снизу

По заданной КС построить эквивалентную ей самокорректирующуюся КС.

Определение самокорректирующейся КС

(p, q)-самокорректирующейся КС называют КС, из которой всегда получается эквивалентная ей КС (реализующая те же формулы через все контакты) после p операций обрыва контакта (смена проводимости одного контакта с x^σ на 0) и q операций замыкания контакта (смена проводимости одного контакта с x^σ на 1).

Простейший способ построения

• Для защиты от одного разрыва каждый контакт заменяем на пару параллельных.
• Для защиты от n разрывов — на (n+1) дублирующих друг друга контактов.
• Для защиты от одного замыкания каждый контакт заменяем на пару последовательных.
• Для защиты от n замыканий — на (n+1) подряд идущих одинаковых контактов.

Итого, для (p, q)-самокорректирующей схемы мы каждый из контактов заменяем на последовательность из (q + 1) блоков, каждый из которых — параллельный пучок из (p + 1) контакта.

Пример

Исходная контактная схема	Контактная схема, исправляющая один разрыв
Контактная схема, исправляющая одно замыкание	Контактная схема, исправляющая один разрыв и одно замыкание

Способы с оптимизацией числа дуг самокорректирующейся КС

Существуют способы предварительной модификации схемы, после чего к контактам нетронутой части применяется описанный выше алгоритм.

Для исправления одного замыкания

• Выделяем цикл из одинаковых контактов, вводим новую вершину и делаем ее центром звезды, на которую заменяем найденный цикл.
• Все контакты, не вошедшие ни в 1 цикл удваиваем последовательно.
• Данная конфигурация устойчива к одному замыканию, т.к. между любыми исходными узлами появляется не 1, а 2 контакта.

Для исправления одного обрыва цепи

• Выделяем звезду из одинаковых контактов, удаляем все контакты звезды и соединяем все контакты циклом.
• Все контакты, не вошедшие ни в 1 звезду удваиваем параллельно.
• Данная конфигурация устойчива к одному обрыву, т.к. между любыми 2 узлами появляется не 1, а 2 пути.