Comments 10
К сожалению при публикации этой статьи я допустил в тексте и в программе на листинге 1 ошибку - в главном цикле область изменения переменной I указана до 255, тогда как следует до 256. Соответственно полученное число ПМС из двух элементов должно быть равным 98.
Приношу извинения немногочисленным читателям, если таковые будут.
Статья исправлена.
Таки, а что мешало опубликовать код как блок кода, а не как картинку? Аналогичный вопрос с формулами.
Ну, и финальный код кажется можно упростить до проверки наборов
if (Q[j]==0) or (Q[j]==1) or (Q[j]==4) or (Q[j]==5):превращается в
if Q[j] in (0,1,4,5):а там и вовсе блоки превращаются во что-то такое
f = (Q[i^1] not in (0,1,4,5)) and (Q[i^2] not in (0,2,4,6))
# ну или как два выражения
f = (Q[i^1] not in (0,1,4,5))
f = f and (Q[i^2] not in (0,2,4,6))Спасибо. Наверное вы правы, но я не специалист по программированию вообще и по Питону в частности. Поэтому пишу программы только для утилитарных целей - не до красоты и лаконичности. Для меня интерес представляют схемы из логических элементов и их статистические свойства.
Кажется после питона немного почитать мануал по использованию разметки хабра не должно быть каким-то рокет сайенс.
Поэтому пишу программы только для утилитарных целей
ну, так через пол года откроете свой же код и ахнете над понаписанным. чуть-чуть идиоматичней переписать и самому станет удобнее использовать и расширять свои же утилиты. Ну, или ИИ попросите переписать, с питоном должны справиться.
А вообще в статье не хватает вводных о предмете. Ни что за полумодулярные системы, ни с чего вообще возникла задача чего-то там посчитать, про какую скорость вообще речь от которой никто не зависит.
Про программирование вы совершенно правы, что касается предмета исследований, то термины типа схемы не зависящие от скорости, полумодулярные или последовательные хорошо известны специалистам в области асинхронной схемотехники именно на которых и рассчитана эта статья, причем первая, попавшая на Хабр, так-то дальше песочницы меня и не пропускали. Для них, этих специалистов, это букварь и толковать эти термины лишний раз я посчитал излишним. А вот подсчетом таких схем никто не занимался, вот я и заинтересовался этой темой.
Математика довольно универсальна в этом плане и есть некоторый шанс, что ваши расчёты вполне могут всплыть не только в схемотехнике, но где-нибудь ещё, а то и вовсе кто-нибудь уже пробовал посчитать что-то похожее. Но когда обрезаются вводные и делается жёсткая привязка к некой узкой области, то рассмотреть подобные связи несколько проблемно.
К сожалению автор является (точнее являлся) специалистом именно в узкой области, где занимались созданием полумодулярных схем, обладающих некоторыми преимуществами перед синхронными и вопрос об их подсчете никогда не стоял. Оценка же их количества показала, что эта задача имеет слишком высокую вычислительную сложность, а результаты для малых количеств элементов можно оценивать просто как подарок.
Во-первых, основные понятия были введены не в 1961, а на шесть лет раньше:
D. E. Muller, Theory of asynchronous circuits. Report no. 66, Digital Computer Laboratory, University of Illinois at Urbana-Champaign, 1955.
Во-вторых, замкнутые схемы, вернее схемы, которые можно замкнуть, - это довольно ограниченное подмножество всех полумодулярных схем. Почему? Потому что внешняя среда зачастую не может быть реализована схемой из-за неразрешимых конфликтов полной кодировки (CSC conflicts).
В-третьих, приведённый алгоритм подсчитывает заведомо избыточные схемы. Почему? Потому что на практике схемы, как правило, определены на маленьком подмножестве всех 2^n состояний. Пусть, в качестве примера, это будет ровно половина от 2^n. В оставшуюся половину состояний схема просто не заходит. Эта, "пустая" половина в Вашем алгоритме "обрабатывается" с помощью устойчивых состояний. Другими словами, если следующее состояние равно предыдущему, то мы имеем соответствующее значение функций в таблице истинности. Т.е. булевы функции, подлежащие минимизации доопределяются строго определённым образом. Можно и нужно доопределять их произвольным образом с помощью don't care. Минимизация таблицы истинности с большим количеством don't care зачастую даёт гораздо более компактный результат. Другое дело, что в случае don't care возникает вопрос правильных начальных условий. Таких, при которых схема является полумодулярной.
На счет истории предмета комментатор очевидно прав. На счет ограниченности модели - замечание, скорее всего, неактуально в силу вычислительной сложности даже при введенных ограничениях. Десять элементов в схемотехнике ерунда, а различных даже замкнутых схем 2**10240. Вопрос оптимальности схем здесь, как впрочем и у Мюллера, вообще не рассматривается, т.к. он определяется выбранным элементным базисом.
Полумодулярные схемы