12) Асимптотические методы синтеза

нижняя оценка — это число элементов, необходимое для реализации произвольной функции n переменных, а верхняя—достаточное

Шеннон предложил метод синтеза схемы S для реализации произвольной переключательной функции  и получил верхнюю оценку сложности (2ⁿ⁺³/n) (1 + _n), где _n -> 0 при n   для схем из контактных элементов. В приложении к схемам из функциональных элементов этот метод дает оценку (2ⁿ⁺²/n)•(1 + _n). Метод основан на использовании разложения произвольной функции

(₁,₂,…,_n)=₁·(1,₁,…,_n)₁·(0,₁,…,_n)

Все произведе­ния вида ₁₂…_n-m можно реализовать с помощью дешифратора (n — m) переменных, а все функции вида (, ,..., ,_n-m+1,…,_n) – с помощью схемы, называемой универсальным многополюсни­ком.

Универсальный многополюсник n переменных —схема, реализую­щая все булевы функции n переменных. Иными словами, это схема с 2­ выходами, на каждом из которых реализуется своя булева функ­ция.

Минимальная сложность L (n) == (2ⁿ⁺²/n) (1 + _n) получается при m= ]log₂ (n - 2log₂ n)[.

Более сильный метод был предложен О. Б. Лу Пановым. Функция задается в виде прямоугольной матрицы с 2^n-k строками и 2^k столбца­ми. Затем матрица разбивается на полосы по s строк. Каждая полоса рассматривается как таблица истинности какой-то функции, и для нее строится своя подсхема на основе дешифраторов k и n — k пере­менных. После этого все подсхемы объединяются с помощью элементов ИЛИ. Выбирая параметры k и s таким образом, чтобы получить мини­мум сложности, О. Б. Лупанов показал, что этот метод приводит к схеме, оценка сложности которой совпадает с нижней (2ⁿ/n) (1 - _n).

13) Дештфратор и основы с-за на основе дешифратора

Дешифратором называется комбинационная схема, реализующая все конституенты единицы. Иными словами, дешифратор — это схема, имеющая п входов и 2ⁿ выходов, включающая один из выходных кана­лов (на одном из выходов появляется единичное значение) при подаче соответствующего входного набора. Дешифратор является типовой комбинационной схемой, находящей широкое применение в вычисли­тельной технике. Поэтому дешифраторы небольшого числа переменных (обычно п≤ 4) (рис. 11.32) изготавливаются в виде стандартных мик­росхем. В ряде случаев на практике приходится строить дешифраторы, имеющие десятки тысяч выходов, например, в запоминающих устройствах и электронных коммутаторах.

Рассмотрим два наиболее распространенных способа синтеза де­шифраторов: матричный и прямоугольный. Отметим, что из определения конституенты единицы становится понятным, что при синтезе де­шифраторов используются только элементы типа И либо ИЛИ—НЕ. При матричном способе предполагается, что каждая конституспта едини­цы реализуется отдельно.

Прямоугольный способ практически всегда используется для случая больших значений п.

Суть способа (рис. 11.35) сводится к построению матрицы на 2ⁿ узлов, входами которой являются выходы дешифраторов k и п—k переменных. Оптимальным по крите­риям сложности и быстродействия является выбор k, наиболее близким n/2. В узлах матрицы располагаются двухвходовые элементы И. Очевидно, что при больших значениях п сложность дешифратора можно считать равной 2ⁿ двухвходовых элементов И, так как сложностью про­межуточных дешифраторов можно пренебречь. Кстати, последние то­же могут быть построены прямоугольным способом.