Метод Шеннона синтезирует схему после разбиения переменных на две группы \(x'=(x_{1},\ldots,x_q)\) и \(x''=(x_{q+1},\ldots,x_n)\). Функция раскладывается по наборам второй группы, а для каждого такого набора используется соответствующий кофактор \(f_{\sigma''}(x')\). Затем схема для всех нужных кофакторов соединяется с селекторной частью, выбирающей кофактор по значениям
Оптимальный выбор q в этой конструкции даёт асимптотические верхние оценки \(L^K(n)\le (4+o(1))\cdot 2^n/n\) для контактных схем и \(L^C(n)\le (8+o(1))\cdot 2^n/n\) для СФЭ. Метод устанавливает правильный порядок \(2^n/n\), но не оптимальную ведущую
Что важно запомнить
- Переменные делятся на информационную группу x′ и адресную группу x″.
- Для каждого \(\sigma''\in B^{n-q}\) рассматривается кофактор \(f_{\sigma''}(x')=f(x',\sigma'')\).
- Функция собирается из кофакторов по разложению Шеннона, а значения x″ выбирают нужный
- Один общий блок может реализовывать множество функций от q переменных, после чего селекторная часть формирует итоговый выход.
- Получаются верхние оценки \(L^K(n)\le (4+o(1))\cdot 2^n/n\) и
- Асимптотически оптимальную константу 1 для СФЭ и КС дают более тонкие методы Лупанова.
Разложение по двум группам переменных
Выбирают q, 1≤q≤n, и записывают \(x'=(x_{1},\ldots,x_q)\), \(x''=(x_{q+1},\ldots,x_n)\). Для каждого набора σ″ значений адресных переменных возникает функция \(f_{\sigma''}(x')=f(x',\sigma'')\). Тогда исходная ФАЛ представляется в форме \(f(x',x'')=\bigvee_{\sigma''\in B^{n-q}} K_{\sigma''}(x'')\cdot f_{\sigma''}(x')\), где \(K_{\sigma''}\) — элементарная конъюнкция, равная 1 ровно на наборе σ″. Это обычное разложение по последним n−q переменным, но в методе Шеннона оно используется как схема
Схемная реализация
Кофакторы от q переменных реализуются общей универсальной частью, а вторая часть схемы по значениям x″ выбирает требуемый выход. Идея состоит в том, чтобы не строить заново одну и ту же q-местную функцию для каждого σ″. Размер универсального блока растёт с q, а размер селекторной части зависит от n−q. Поэтому параметр q выбирают так, чтобы сбалансировать эти две
Получаемые оценки
После такого баланса теорема 4.1 даёт \(L^K(n)\le (4+o(1))\cdot 2^n/n\) и \(L^C(n)\le (8+o(1))\cdot 2^n/n\). Эти оценки принципиально лучше прямого синтеза по СДНФ и показывают правильный экспоненциальный порядок сложности. Однако коэффициенты 4 и 8 ещё не являются асимптотически наилучшими. В последующих методах Лупанова ведущая константа для соответствующих функций Шеннона уменьшается до
Пример простыми словами
Для n=4 можно взять q=2. Тогда последние две переменные образуют четыре адреса 00, 01, 10 и 11. Каждому адресу соответствует своя функция двух первых переменных f₀₀(x₁,x₂), f₀₁(x₁,x₂), f₁₀(x₁,x₂), f₁₁(x₁,x₂). Схема сначала реализует нужные двухместные функции, а затем по x₃,x₄ выбирает правильную.
Частые ошибки
- Считать метод Шеннона простым последовательным разложением без совместного использования кофакторов. Экономия возникает именно из общей реализации повторяющихся функций.
- Фиксировать q заранее. В оценке q является параметром, который выбирают для баланса частей схемы.
- Называть оценки с коэффициентами 4 и 8 асимптотически точными. Они дают правильный порядок, но не лучшую константу.
- Путать верхние оценки метода Шеннона с мощностными нижними оценками.
