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

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

Перейти к: навигация, поиск

Содержание

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

[править] Простейшие методы

[править] Промежуточные действия

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

[править] Получение СФЭ

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

[править] Получение КС

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

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

[править] Метод каскадов

[править] Промежуточные действия

Пусть у нас имеются булевы функции F1(x1, x2, … , xn), … , Fk(x1, x2, … , xn), зависящие от 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)

Тогда определим правило построения следующих множеств (M1, M2, … , Mn):

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

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

[править] Пример
f1(x1,x2,x3,x4)=(1000 0010 1111 1000)
f2(x1,x2,x3,x4)=(1000 1111 0010 1000)
  • M0 = {(1000 0010 1111 1000),(1000 1111 0010 1000)}
  • M1 = {(1000 0010),(1111 1000),(1000 1111),(0010 1000)}
  • M2 = {(1000),(0010),(1111)}
  • M3 = {(10),(00),(11)}
  • M4 = {0,1}

[править] Получение СФЭ

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

  • 0 = xi & xi
  • 1 = xi V xi

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

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

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

[править] Получение КС

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

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

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

[править] Метод Шеннона

[править] Промежуточные действия

Выбираем некоторое 1≤q≤n. Расклыдаваем исходное f(x',x") = V xi+1σi+1 & xi+2σi+2 & ... & xnσn & fσ"(x'). Обычно выбирают q = округленноый вниз(log2(n-2*log2(n))). После чего составляется универсальный многополюсник порядка q(имеющий q входов и 2n выходов) и мультиплексор порядка n-q (зависщий от адресных переменных xi+1, ... ,xn и от выходов универсального многополюсника, выдающий на выход fσ"(x') в соответствии с приведенной формулой в свой единственный выход).

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

[править] Получение СФЭ

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

[править] Получение КС

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

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

[править] Оценка сложности самой сложной ФАЛ из класса

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

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

[править] Пример

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

Решение

  1. Первый пункт является самым главным. В нём нужно получить некоторую формулу, в которой любая функция из заданного класса выражается через функцию от меньшего числа переменных. Полученная формула пригодится и впоследствии. Например, для класса самодвойственных функций, разложим функцию f по первой переменной f(x1, x2, …, xn) = x1 & f(0, x2, …, xn) ∨ x1 & f(1, x2, …, xn) = x1 & f(0, x2, …, xn) ∨ x1 & f(0, x2, …, xn) = x1 & f0(x2, …, xn) ∨ x1 & f0(x2, …, xn), где f0 = f(0, x2, …, xn). Перепишем это в виде f(x1, …, xn) = x1f0(x2x1, …, xnx1) (*). Теперь видно, самодвойственная функция от n переменных однозначно определяется функцией f0 от n − 1 переменной, и, следовательно, число самодвойственных функций от n переменных равно 22n − 1. В принципе, это и ежу очевидно, но полученная нами (*) потребуется нам в дальнейшем.
  2. Из пункта 1 следует что LC(Q(n)) ≳ 2n − 1 / n
  3. Из (*), а также из утверждения строим схему для произвольной самодвойственной функции. Строим f0 (сложность 2n − 1 / (n − 1)). Для n «⊕» потребуется ещё не более, чем C × n функциональных элементов. В итоге как раз и получится, что сложность результирующей схемы асимптотически не превосходит 2n − 1 / n

[править] Пример

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

f(x1, x2, x3, …, xn) = f(x3, x1, x2, …, xn)

Решение

  1. Разлагаем f по первым трём переменным:
    • f(x1, x2, x3, x4, …, xn) = x1 & x2 & x3 & f(0, 0, 0, x4, …, xn) ∨ x1 & x2 & x3 & f(0, 0, 1, x4, …, xn) ∨ x1 & x2 & x3 & f(0, 1, 0, x4, …, xn) ∨ x1 & x2 & x3 & f(0, 1, 1, x4, …, xn) ∨ x1 & x2 & x3 & f(1, 0, 0, x4, …, xn) ∨ x1 & x2 & x3 & f(1, 0, 1, x4, …, xn) ∨ x1 & x2 & x3 & f(1, 1, 0, x4, …, xn) ∨ x1 & x2 & x3 & f(1, 1, 1, x4, …, xn) = (x1x2x3x1x2x3) & fa ∨ ((x1x2x3x1x2x3)) & fb (*),
      где fa = f(0, 0, 0, x4, …, xn) = f(1, 0, 0, x4, …, xn) = f(1, 1, 0, x4, …, xn) = f(1, 1,1,x4,...,xn) = f(0, 1, 1, x4, …, xn) = f(0, 0, 1, x4, …, xn);
      fb = f(0, 1, 0, x4, …, xn) = f(1, 0, 1, x4, …, xn). Теперь видно, что функция из данного класса однозначно определяется парой (fa, fb), где fa, fb — функции от n − 3 переменных. Таким образом, число функций из заданного класса равно числу таких пар, т. е. 22n − 3 × 22n − 3 = 22n − 2
  2. Из (1) следует, что LC(Q(n)) ≳ 2n − 2 / n
  3. Опять же, из (*) ясно, как строить схему для произвольной функции из заданного класса. Строим СФЭ для функций fa, fb (сложность каждой ≤ (2n − 3 / (n − 3)). И, кроме того, нам потребуется дополнительная константа С «∨», «&» и «¬» для реализации (*). Складывая (2n − 3 / (n − 3)) + (2n − 3 / (n − 3)) + С, получим как раз, что это ≲ 2n − 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 пути.


Основы Кибернетики


01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16


Календарь

пт пт пт пт пт
Февраль
09 16 26
Март
02 09 16 23 30
Апрель
06 13 20 27
Май
04 11 18 25

Материалы к экзамену

Экзаменационные вопросы 3 потока 2007 (new!) | Алгоритмы решения задач | Теормин | Определения

Личные инструменты
Разделы