Research indexJournal article
О сложности и структуре минимальной каскадной контактной схемы, реализующей стандартную мультиплексорную функцию
Kudimov, Lozhkin
Дискретная математика1 Jan 2026
Journal article
О сложности и структуре минимальной каскадной контактной схемы, реализующей стандартную мультиплексорную функцию
Kudimov, Lozhkin · Дискретная математика · 2026 · Subscription
PaywalledRead at the publisher
The full text is at the publisher
You can read the abstract here, or open it at the publisher.
Abstract
Рассматривается задача индивидуального синтеза каскадных контактных схем для стандартной мультиплексорной функции порядка $n$. Доказано, что минимальная сложность указанной реализации равна $3 \cdot 2^n - 2$ и достигается только на канонической мультиплексорной каскадной контактной схеме порядка $n$, рассматриваемой с точностью до изоморфизма, переименования булевых переменных и применения операции свертывания.