Каскадные контактные схемы и СФЭ: метод каскадов и его применение

Метод каскадов строит контактные схемы и СФЭ последовательным разложением реализуемых ФАЛ по переменным. На уровне переменной x_i функция g представляется через подфункции g₀ и g₁, полученные фиксацией x_i, и реализуется присоединением одного или двух противоположных контактов либо соответствующей комбинацией функциональных элементов.1

При синтезе системы F=(f₁,…,f_m) одинаковые остаточные функции и промежуточные фрагменты не строятся заново для каждого выхода. Их можно реализовать один раз и использовать совместно. Поэтому каскадный подход особенно естественен для многовыходных систем. Он конструктивен, но сам по себе не гарантирует минимальность схемы.1

Что важно запомнить
  • Каскадная КС строится рекурсивным присоединением одного или двух противоположных контактов.
  • Основной шаг основан на разложении \(g=\neg x_i\cdot g_{0}\lor x_i\cdot g_{1}\), где g₀ и g₁ получаются фиксацией x_i.1
  • Если одна из подфункций равна нулю, достаточно одноконтактного шага.
  • Для СФЭ одинаковые промежуточные функции, возникающие при разных разложениях, реализуются только один раз.1
  • Метод применим к системам ФАЛ и позволяет совместно использовать общие подвычисления.
  • Каскадный синтез не означает автоматической минимальности построенной схемы.

Каскадная структура

Каскадная контактная схема (ККС) — приведённая КС без изолированных полюсов, которую можно получить из системы тождественных вершин последовательностью операций присоединения одного или двух противоположных контактов и переименования выходов. Полной ККС называется ККС, построенная без операций присоединения одного контакта. Контактное дерево является частным примером ККС.1

На очередном шаге к уже построенным вершинам присоединяют один контакт либо пару противоположных контактов x_i и ¬x_i. Если использовать пару, новая вершина реализует функцию \(g=\neg x_i\cdot g_{0}\lor x_i\cdot g_{1}\), где g₀=g(0,x_{i+1},…,x_n), а g₁=g(1,x_{i+1},…,x_n). Если один кофактор равен нулю, разложение сокращается до одного литерала и одного ненулевого кофактора.1

Метод каскадов для системы функций

Для F=(f₁,…,f_m) рассматривают все различные функции, которые возникают после последовательной фиксации x₁,x₂,… . Построение выполняют в обратном порядке, начиная с последних переменных. Каждая отличная от уже реализованных остаточная функция получает собственную вершину, связанную с вершинами её кофакторов. После завершения построения выходами оставляют только вершины, реализующие исходные f₁,…,f_m.1

Для СФЭ используется та же логика разложения. Если один и тот же фрагмент вида g_σ·x_i^σ нужен при реализации разных функций, его реализуют единственный раз и затем подают на несколько последующих элементов. Именно совместное использование промежуточных результатов даёт преимущество общей СФЭ перед независимым синтезом каждого выхода.1

Применение и границы метода

Метод каскадов удобен для многовыходных систем, дешифраторов, мультиплексорных конструкций и функций с повторяющимися кофакторами. Он даёт явный алгоритм синтеза и позволяет получать верхние оценки сложности. Однако это не алгоритм минимизации. В лекциях приводятся примеры, где каскадная схема минимальна, и примеры, где построенная каскадная СФЭ уступает другой реализации.1

Пример простыми словами

Представьте две выходные функции, у которых после фиксации x₁ возникает одна и та же остаточная функция h(x₂,…,x_n). При независимом построении h пришлось бы реализовать дважды. В каскадной СФЭ h вычисляется один раз, а её результат разветвляется к двум последующим фрагментам схемы.

Частые ошибки
  • Считать каскадную КС обычным контактным деревом. Каскадная схема допускает более общее повторное использование уже построенных вершин.
  • Забывать, что при нулевом кофакторе используется одноконтактный шаг.
  • Строить одинаковую промежуточную функцию отдельно для каждого выхода СФЭ и тем самым терять главное преимущество метода.
  • Называть любую схему, полученную методом каскадов, минимальной. Метод гарантирует конструкцию, а не оптимальность.

Другие вопросы

Источники

  1. 1 Ложкин С. А. Лекции по основам кибернетики Вариант 2017 г. (гр. 311–319), глава 3, §4, каскадные КС и СФЭ, метод каскадов, МГУ, факультет ВМК