| Текущая версия |
Ваш текст |
| Строка 1: |
Строка 1: |
| - | == По заданной ФАЛ с помощью простейших методов, метода каскадов или метода Шеннона построить реализующую ее СФЭ или КС. == | + | == From Ebaums Inc to MurkLoar. == |
| - | | + | We at EbaumsWorld consider you as disgrace of human race. |
| - | === Простейшие методы ===
| + | Your faggotry level exceeded any imaginable levels, and therefore we have to inform you that your pitiful resourse should be annihilated. |
| - | ==== Промежуточные действия ====
| + | Dig yourself a grave - you will need it. |
| - | * Если ФАЛ представлена в виде таблицы, то построим по ней совершенную ДНФ (как объединение всех возможных случаев, когда она равна 1).
| + | |
| - | * Если ФАЛ представлена в виде формулы, преобразуем ее, чтобы остались только функции базиса Б<sub>0</sub>. Кроме того, поднимаем все отрицания (они должны стоять только над переменными, но не над бо́льшими кусками выражения).
| + | |
| - | | + | |
| - | ==== Получение СФЭ ====
| + | |
| - | Строим как-нибудь подвыражения в соответствии с приоритетом операций. Поскольку оставлены только функции базиса Б<sub>0</sub>, то это не вызывает особых затруднений. Что вижу, то и рисую.
| + | |
| - | | + | |
| - | ==== Получение КС ====
| + | |
| - | Разбираем формулу
| + | |
| - | * ''A'' ∨ ''B'' преобразуем в ветвление, где один вариант реализует ''A'', а другой — ''B''
| + | |
| - | * ''A'' & ''B'' преобразуем в последовательное соединение, где первая часть реализует ''A'', другая — ''B''.
| + | |
| - | * <span style="border-top:solid 1px">''x''<sub>i</sub></span> преобразуем в контакт с меткой <span style="border-top:solid 1px">''x''<sub>i</sub></span>
| + | |
| - | * ''x''<sub>i</sub> преобразуем в контакт с меткой ''x''<sub>i</sub>
| + | |
| - | | + | |
| - | === Метод каскадов ===
| + | |
| - | ==== Промежуточные действия ====
| + | |
| - | Пусть у нас имеются булевы функции F<sub>1</sub>(x<sub>1</sub>, x<sub>2</sub>, … , x<sub>n</sub>), … , F<sub>k</sub>(x<sub>1</sub>, x<sub>2</sub>, … , x<sub>n</sub>), зависящие от n переменных. Обозначим следующее множество:
| + | |
| - | M<sub>0</sub> = {F<sub>1</sub>(x<sub>1</sub>, x<sub>2</sub>, … , x<sub>n</sub>), … , F<sub>k</sub>(x<sub>1</sub>, x<sub>2</sub>, … , x<sub>n</sub>)}.
| + | |
| - | В простейшем случае, в нем одна функция. Воспользуемся следующим приемом:
| + | |
| - | F(x<sub>1</sub>, x<sub>2</sub>, … , x<sub>n</sub>) = x<sub>1</sub>*F(1,x<sub>2</sub>, … , x<sub>n</sub>)V <span style="border-top:solid 1px">x<sub>1</sub></span>*F(0, x<sub>2</sub>, …, x<sub>n</sub>)
| + | |
| - | Тогда определим правило построения следующих множеств (M<sub>1</sub>, M<sub>2</sub>, … , M<sub>n</sub>):
| + | |
| - | M<sub>i+1</sub> = {g(0,x<sub>i+1</sub>, … , x<sub>n</sub>)|g∈M<sub>i</sub>} U {g(1,x<sub>i+1</sub>, … , x<sub>n</sub>)|g∈M<sub>i</sub>}.
| + | |
| - | Если функция представлена строкой значений, то формируем новое множество из левых и правых половин.
| + | |
| - | Если функция представлена формулой, то подставляем в нее x<sub>i</sub>=0 и x<sub>i</sub>=1 и упрощаем.
| + | |
| - | При этом после построения из M<sub>i</sub> удаляются все фунции, несущественно зависящие от x<sub>1</sub> (для строк значений это хорошо видно, т.к. левая и правая половина совпадает)
| + | |
| - | ===== Пример =====
| + | |
| - | f<sub>1</sub>(x<sub>1</sub>,x<sub>2</sub>,x<sub>3</sub>,x<sub>4</sub>)=(1000 0010 1111 1000)
| + | |
| - | f<sub>2</sub>(x<sub>1</sub>,x<sub>2</sub>,x<sub>3</sub>,x<sub>4</sub>)=(1000 1111 0010 1000)
| + | |
| - | *M<sub>0</sub> = {(1000 0010 1111 1000),(1000 1111 0010 1000)}
| + | |
| - | *M<sub>1</sub> = {(1000 0010),(1111 1000),(1000 1111),(0010 1000)}
| + | |
| - | *M<sub>2</sub> = {(1000),(0010),(1111)}
| + | |
| - | *M<sub>3</sub> = {(10),<strike>(00)</strike>,<strike>(11)</strike>}
| + | |
| - | *M<sub>4</sub> = {0,1}
| + | |
| - | | + | |
| - | ==== Получение СФЭ ====
| + | |
| - | Реализуем на базе любого входа
| + | |
| - | *0 = x<sub>i</sub> & <span style="border-top:solid 1px">x<sub>i</sub></span>
| + | |
| - | *1 = x<sub>i</sub> V <span style="border-top:solid 1px">x<sub>i</sub></span>
| + | |
| - | | + | |
| - | Для реализации элемента M<sub>i</sub> используем элементы M<sub>i+1</sub>: пусть f(0,x<sub>i+1</sub>,...x<sub>n</sub>)=g(x<sub>i+1</sub>,...x<sub>n</sub>) и f(1,x<sub>i+1</sub>,...x<sub>n</sub>)=h(x<sub>i+1</sub>,...x<sub>n</sub>).
| + | |
| - | | + | |
| - | Тогда для реализации f соединеним дизъюнкцией конъюнкцию g и <span style="border-top:solid 1px">x<sub>i</sub></span> с конъюнкцией h и x<sub>i</sub>.
| + | |
| - | | + | |
| - | Реализацию элементов M<sub>0</sub> метим как выходы СФЭ.
| + | |
| - | | + | |
| - | ==== Получение КС ====
| + | |
| - | Обозначаем все элементы всех множеств узлами КС.
| + | |
| - | *если g(x<sub>i+1</sub>,...x<sub>n</sub>)=h(0,x<sub>i+1</sub>,...x<sub>n</sub>), то соединим g и h контактом с меткой <span style="border-top:solid 1px">x<sub>i</sub></span>
| + | |
| - | *если g(x<sub>i+1</sub>,...x<sub>n</sub>)=h(1,x<sub>i+1</sub>,...x<sub>n</sub>), то соединим g и h контактом с меткой x<sub>i</sub>
| + | |
| - | После этого удаляем вершину с меткой 0 и все ведущие в нее контакты. Вершину с меткой 1, а также F<sub>1</sub>,...,F<sub>k</sub> помечаем как входы КС.
| + | |
| - | | + | |
| - | === Метод Шеннона ===
| + | |
| - | ==== Промежуточные действия ====
| + | |
| - | Выбираем некоторое 1≤q≤n. Расклыдаваем исходное f(x',x") = V x<sub>i+1</sub><sup>σ<sub>i+1</sub></sup> & x<sub>i+2</sub><sup>σ<sub>i+2</sub></sup> & ... & x<sub>n</sub><sup>σ<sub>n</sub></sup> & f<sub>σ"</sub>(x').
| + | |
| - | Обычно выбирают q = округленноый вниз(log<sub>2</sub>(n-2*log<sub>2</sub>(n))). После чего составляется универсальный многополюсник порядка q(имеющий q входов и 2<sup>n</sup> выходов) и мультиплексор порядка n-q (зависщий от адресных переменных x<sub>i+1</sub>, ... ,x<sub>n</sub> и от выходов универсального многополюсника, выдающий на выход f<sub>σ"</sub>(x') в соответствии с приведенной формулой в свой единственный выход).
| + | |
| - | | + | |
| - | Данный метод не применяется на практике для построения КС или СФЭ, это скорее мысленный эксперимент вроде падающего из окна Дэвида Дойча или квантового самоубийцы, используемый затем Шенноном и его последователями для оценки функции Шеннона...
| + | |
| - | | + | |
| - | ==== Получение СФЭ ====
| + | |
| - | Универсальный многополюсник в СФЭ выглядит так:
| + | |
| - | Мультиплексор порядка q для f(x) в СФЭ выгладит так:
| + | |
| - | | + | |
| - | ==== Получение КС ====
| + | |
| - | Универсальный многополюсник в КС выглядит так: точно так же как в методе каскадов к каждой вершине приписываем <span style="border-top:solid 1px">x<sub>1</sub></span> или x<sub>1</sub>, дабы соединить с новой волной вершин. В каждой следующем множестве будет в 2 раза больше вершин.
| + | |
| - | Мультиплексор порядка q для f(x) в КС выгладит так:
| + | |
| - | | + | |
| - | == Оценить сверху или снизу сложность конкретной ФАЛ или сложность самой сложной ФАЛ из заданного множества в заданном классе схем. ==
| + | |
| - | === Оценка сложности самой сложной ФАЛ из класса ===
| + | |
| - | Для того, что посчитать сложность самой сложной ФАЛ из некоторого класса ''Q''(''n'') ∈ ''P''<sub>2</sub>(''n''), то есть, иначе говоря, вычислить функцию Шеннона, связанную с классом ''Q''(''n'') (и для некоторого класса cхем U — например, СФЭ или КС), необходимо выполнить следующие шаги:
| + | |
| - | # Посчитать число функций в заданном классе ''Q''(''n'').
| + | |
| - | # Сразу же из этого получить асимптотически нижнюю оценку функции Шеннона, связанной с классом ''Q''(''n''):
| + | |
| - | #* ''L''<sup>''K''</sup>(''Q''(''n'')) ≳ log(|''Q''(''n'')|) / log(log(|''Q''(''n'')|))
| + | |
| - | #* L<sup>C</sup>(''Q''(''n'')) ≳ log(|''Q''(''n'')|) / log(log(|''Q''(''n'')|))
| + | |
| - | # Показать, как для любой функции из данного класса построить схему из класса U, реализующую данную функцию и имеющую сложность, асимптотически равную вычисленной нижней оценке. Из этого будет следовать, что полученная асимптотически нижняя оценка является и асимптотически верхней оценкой, а из этого, в свою очередь, будет следовать, что функция Шеннона для заданного класса ''U''(''n'') будет просто асимптотически равна полученной нижней оценке.
| + | |
| - | #* В пункте 3 всегда пригождается следующее: для любой функции от ''n'' переменных можно построить, реализующую её СФЭ и КС со сложностью, асимптотически не превосходящей 2<sup>n</sup> / ''n''
| + | |
| - | | + | |
| - | ==== Пример ====
| + | |
| - | * Посчитать функцию Шеннона, связанную с классом самодвойственных функций, для класса СФЭ.
| + | |
| - | ** Самодвойственная функция ''f'': ''f''(''x''<sub>1</sub>, …, ''x''<sub>n</sub>) = <span style="border-top:solid 1px">''f''(<span style="border-top:double 3px">''x''</span><sub>1</sub>, …, <span style="border-top:double 3px">''x''</span><sub>n</sub>)</span>
| + | |
| - | | + | |
| - | '''Решение'''
| + | |
| - | # Первый пункт является самым главным. В нём нужно получить некоторую формулу, в которой любая функция из заданного класса выражается через функцию от меньшего числа переменных. Полученная формула пригодится и впоследствии. Например, для класса самодвойственных функций, разложим функцию ''f'' по первой переменной ''f''(''x''<sub>1</sub>, ''x''<sub>2</sub>, …, ''x''<sub>n</sub>) = <span style="border-top:solid 1px">''x''</span><sub>1</sub> & ''f''(0, ''x''<sub>2</sub>, …, ''x''<sub>n</sub>) ∨ ''x''<sub>1</sub> & ''f''(1, ''x''<sub>2</sub>, …, ''x''<sub>n</sub>) = <span style="border-top:solid 1px">''x''</span><sub>1</sub> & ''f''(0, ''x''<sub>2</sub>, …, ''x''<sub>n</sub>) ∨ ''x''<sub>1</sub> & ''f''(0, <span style="border-top:solid 1px">''x''</span><sub>2</sub>, …, <span style="border-top:solid 1px">''x''</span><sub>n</sub>) = <span style="border-top:solid 1px">''x''</span><sub>1</sub> & ''f''<sub>0</sub>(''x''<sub>2</sub>, …, ''x''<sub>n</sub>) ∨ ''x''<sub>1</sub> & <span style="border-top:solid 1px">''f''<sub>0</sub>(''x''<sub>2</sub>, …, ''x''<sub>n</sub>)</span>, где ''f''<sub>0</sub> = ''f''(0, ''x''<sub>2</sub>, …, ''x''<sub>n</sub>). Перепишем это в виде ''f''(''x''<sub>1</sub>, …, ''x''<sub>n</sub>) = ''x''<sub>1</sub> ⊕ ''f''<sub>0</sub>(''x''<sub>2</sub> ⊕ ''x''<sub>1</sub>, …, ''x''<sub>n</sub> ⊕ ''x''<sub>1</sub>) (*). Теперь видно, самодвойственная функция от ''n'' переменных однозначно определяется функцией ''f''<sub>0</sub> от ''n'' − 1 переменной, и, следовательно, число самодвойственных функций от ''n'' переменных равно 2<sup>2<sup>''n'' − 1</sup></sup>. В принципе, это и ежу очевидно, но полученная нами (*) потребуется нам в дальнейшем.
| + | |
| - | # Из пункта 1 следует что ''L''<sup>C</sup>(''Q''(''n'')) ≳ 2<sup>''n'' − 1</sup> / ''n''
| + | |
| - | # Из (*), а также из утверждения строим схему для произвольной самодвойственной функции. Строим ''f''<sub>0</sub> (сложность 2<sup>''n'' − 1</sup> / (''n'' − 1)). Для ''n'' «⊕» потребуется ещё не более, чем ''C'' × ''n'' функциональных элементов. В итоге как раз и получится, что сложность результирующей схемы асимптотически не превосходит 2<sup>''n'' − 1</sup> / ''n''
| + | |
| - | | + | |
| - | ==== Пример ====
| + | |
| - | * Посчитать функцию Шеннона, также для класса СФЭ, связанную с классом функций, таких, что:
| + | |
| - | ''f''(''x''<sub>1</sub>, ''x''<sub>2</sub>, ''x''<sub>3</sub>, …, ''x''<sub>n</sub>) = ''f''(<span style="border-top:solid 1px">''x''</span><sub>3</sub>, ''x''<sub>1</sub>, ''x''<sub>2</sub>, …, ''x''<sub>n</sub>)
| + | |
| - | | + | |
| - | '''Решение'''
| + | |
| - | # Разлагаем ''f'' по первым трём переменным:
| + | |
| - | #* ''f''(''x''<sub>1</sub>, ''x''<sub>2</sub>, ''x''<sub>3</sub>, ''x''<sub>4</sub>, …, ''x''<sub>n</sub>) = <span style="border-top:solid 1px">''x''</span><sub>1</sub> & <span style="border-top:solid 1px">''x''</span><sub>2</sub> & <span style="border-top:solid 1px">''x''</span><sub>3</sub> & ''f''(0, 0, 0, ''x''<sub>4</sub>, …, ''x''<sub>n</sub>) ∨ <span style="border-top:solid 1px">''x''</span><sub>1</sub> & <span style="border-top:solid 1px">''x''</span><sub>2</sub> & ''x''<sub>3</sub> & ''f''(0, 0, 1, ''x''<sub>4</sub>, …, ''x''<sub>n</sub>) ∨ <span style="border-top:solid 1px">''x''</span><sub>1</sub> & ''x''<sub>2</sub> & <span style="border-top:solid 1px">''x''</span><sub>3</sub> & ''f''(0, 1, 0, ''x''<sub>4</sub>, …, ''x''<sub>n</sub>) ∨ <span style="border-top:solid 1px">''x''</span><sub>1</sub> & ''x''<sub>2</sub> & ''x''<sub>3</sub> & ''f''(0, 1, 1, ''x''<sub>4</sub>, …, ''x''<sub>n</sub>) ∨ ''x''<sub>1</sub> & <span style="border-top:solid 1px">''x''</span><sub>2</sub> & <span style="border-top:solid 1px">''x''</span><sub>3</sub> & ''f''(1, 0, 0, ''x''<sub>4</sub>, …, ''x''<sub>n</sub>) ∨ ''x''<sub>1</sub> & <span style="border-top:solid 1px">''x''</span><sub>2</sub> & ''x''<sub>3</sub> & ''f''(1, 0, 1, ''x''<sub>4</sub>, …, ''x''<sub>n</sub>) ∨ ''x''<sub>1</sub> & ''x''<sub>2</sub> & <span style="border-top:solid 1px">''x''</span><sub>3</sub> & ''f''(1, 1, 0, ''x''<sub>4</sub>, …, ''x''<sub>n</sub>) ∨ ''x''<sub>1</sub> & ''x''<sub>2</sub> & ''x''<sub>3</sub> & ''f''(1, 1, 1, ''x''<sub>4</sub>, …, ''x''<sub>n</sub>) = (<span style="border-top:solid 1px">''x''</span><sub>1</sub>''x''<sub>2</sub><span style="border-top:solid 1px">''x''</span><sub>3</sub> ∨ ''x''<sub>1</sub><span style="border-top:solid 1px">''x''</span><sub>2</sub>''x''<sub>3</sub>) & ''f''<sub>a</sub> ∨ (<span style="border-top:solid 1px">(<span style="border-top:double 3px">''x''</span><sub>1</sub>''x''<sub>2</sub><span style="border-top:double 3px">''x''</span><sub>3</sub> ∨ ''x''<sub>1</sub><span style="border-top:double 3px">''x''</span><sub>2</sub>''x''<sub>3</sub>)</span>) & ''f''<sub>b</sub> (*), <br />где ''f''<sub>a</sub> = ''f''(0, 0, 0, ''x''<sub>4</sub>, …, ''x''<sub>n</sub>) = ''f''(1, 0, 0, ''x''<sub>4</sub>, …, ''x''<sub>n</sub>) = ''f''(1, 1, 0, ''x''<sub>4</sub>, …, ''x''<sub>n</sub>) = f(1, 1,1,x4,...,xn) = ''f''(0, 1, 1, ''x''<sub>4</sub>, …, ''x''<sub>n</sub>) = ''f''(0, 0, 1, ''x''<sub>4</sub>, …, ''x''<sub>n</sub>); <br /> ''f''<sub>b</sub> = ''f''(0, 1, 0, ''x''<sub>4</sub>, …, ''x''<sub>n</sub>) = ''f''(1, 0, 1, ''x''<sub>4</sub>, …, ''x''<sub>n</sub>). Теперь видно, что функция из данного класса однозначно определяется парой (''f''<sub>a</sub>, ''f''<sub>b</sub>), где ''f''<sub>a</sub>, ''f''<sub>b</sub> — функции от ''n'' − 3 переменных. Таким образом, число функций из заданного класса равно числу таких пар, т. е. 2<sup>2<sup>''n'' − 3</sup></sup> × 2<sup>2<sup>''n'' − 3</sup></sup> = 2<sup>2<sup>''n'' − 2</sup></sup>
| + | |
| - | # Из (1) следует, что ''L''<sup>C</sup>(''Q''(''n'')) ≳ 2<sup>''n'' − 2</sup> / ''n''
| + | |
| - | # Опять же, из (*) ясно, как строить схему для произвольной функции из заданного класса. Строим СФЭ для функций ''f''<sub>a</sub>, ''f''<sub>b</sub> (сложность каждой ≤ (2<sup>''n'' − 3</sup> / (''n'' − 3)). И, кроме того, нам потребуется дополнительная константа С «∨», «&» и «¬» для реализации (*). Складывая (2<sup>''n'' − 3</sup> / (''n'' − 3)) + (2<sup>''n'' − 3</sup> / (''n'' − 3)) + С, получим как раз, что это ≲ 2<sup>''n'' − 2</sup> / ''n''.
| + | |
| - | | + | |
| - | <!-- Объяснил довольно криво, но, надеюсь, идея понятна.
| + | |
| - | И ещё я не умею пользоваться викой. Как встраивать латеховские формулы?
| + | |
| - | Почему у меня не получается? Вначаое пытался, а потом забил...
| + | |
| - | | + | |
| - | Есир, помоги, пожалуйста! Надеюсь, что ты всё приведёшь к нормальному виду, если тебе не будт влом.
| + | |
| - | Броник. -->
| + | |
| - | | + | |
| - | ==== Оценка снизу ====
| + | |
| - | | + | |
| - | === Оценка сложности ФАЛ ===
| + | |
| - | ==== Оценка сверху ====
| + | |
| - | === Оценка сложности самой сложной ФАЛ из класса ===
| + | |
| - | ==== Оценка снизу ====
| + | |
| - | | + | |
| - | == По заданной КС построить эквивалентную ей самокорректирующуюся КС. ==
| + | |
| - | === Определение самокорректирующейся КС ===
| + | |
| - | (p, q)-самокорректирующейся КС называют КС, из которой всегда получается эквивалентная ей КС (реализующая те же формулы через все контакты) после p операций обрыва контакта (смена проводимости одного контакта с x<sup>σ</sup> на 0) и q операций замыкания контакта (смена проводимости одного контакта с x<sup>σ</sup> на 1).
| + | |
| - | | + | |
| - | === Простейший способ построения ===
| + | |
| - | * Для защиты от одного разрыва каждый контакт заменяем на пару параллельных.
| + | |
| - | * Для защиты от n разрывов — на (n+1) дублирующих друг друга контактов.
| + | |
| - | * Для защиты от одного замыкания каждый контакт заменяем на пару последовательных.
| + | |
| - | * Для защиты от n замыканий — на (n+1) подряд идущих одинаковых контактов.
| + | |
| - | Итого, для (p, q)-самокорректирующей схемы мы каждый из контактов заменяем на последовательность из (q + 1) блоков, каждый из которых — параллельный пучок из (p + 1) контакта.
| + | |
| - | | + | |
| - | ==== Пример ====
| + | |
| - | {|
| + | |
| - | !Исходная контактная схема
| + | |
| - | !Контактная схема, исправляющая один разрыв
| + | |
| - | |-
| + | |
| - | |style="text-align:center"|[[Изображение:Contact_scheme.png|320px|Исходная контактная схема]]
| + | |
| - | |style="text-align:center"|[[Изображение:Contact_scheme_parallel.png|320px|Контактная схема, исправляющая один разрыв]]
| + | |
| - | |-
| + | |
| - | !Контактная схема, исправляющая одно замыкание
| + | |
| - | !Контактная схема, исправляющая один разрыв и одно замыкание
| + | |
| - | |-
| + | |
| - | |style="text-align:center"|[[Изображение:Contact_scheme_sequential.png|320px|Контактная схема, исправляющая одно замыкание]]
| + | |
| - | |style="text-align:center"|[[Изображение:Contact_scheme_pq.png|320px|Контактная схема, исправляющая один разрыв и одно замыкание]]
| + | |
| - | |}
| + | |
| - | | + | |
| - | === Способы с оптимизацией числа дуг самокорректирующейся КС ===
| + | |
| - | Существуют способы предварительной модификации схемы, после чего к контактам нетронутой части применяется описанный выше алгоритм.
| + | |
| - | | + | |
| - | ==== Для исправления одного замыкания ====
| + | |
| - | *Выделяем цикл из одинаковых контактов, вводим новую вершину и делаем ее центром звезды, на которую заменяем найденный цикл.
| + | |
| - | *Все контакты, не вошедшие ни в 1 цикл удваиваем последовательно.
| + | |
| - | *Данная конфигурация устойчива к одному замыканию, т.к. между любыми исходными узлами появляется не 1, а 2 контакта.
| + | |
| - | | + | |
| - | ==== Для исправления одного обрыва цепи ====
| + | |
| - | *Выделяем звезду из одинаковых контактов, удаляем все контакты звезды и соединяем все контакты циклом.
| + | |
| - | *Все контакты, не вошедшие ни в 1 звезду удваиваем параллельно.
| + | |
| - | *Данная конфигурация устойчива к одному обрыву, т.к. между любыми 2 узлами появляется не 1, а 2 пути.
| + | |
| - | | + | |
| - | {{Курс Основы Кибернетики}}
| + | |
