Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 12
Насколько я понимаю, поиск изоморфных схем здесь происходит не среди полумодулярных (живых), а среди автономных (которые могут быть и не живыми). Последние для практики малоинтересны, поскольку представляют собой генератор конечной последовательности импульсов (выбег и стоп). Очевидно, что перебор комбинаций только для живых схем будет существенно короче. Кроме того, можно определить такое расширение живых схем размерности n-1 до таковых размерности n, которое отличается только добалением буфера. Смысл в том, что функционально эти схемы одинаковы, поскольку буфер - это модель провода. Т.е. новая n-схема просто не чувствительна к задержке в этом проводе.
Во-первых не правильно противопоставляться полумодулярные и живые схемы. Схема имеющая устойчивые (тупиковые состояния) может быть вполне полумодулярной, например x=x; y=y.
Во-вторых поиск изоморфных был осуществлен, как среди всех схем, так и среди таких классов, как полумодулярные и последовательные, что видно из результирующих таблиц (1 и 2).
В-третьих понятие нечувствительности к задержке в проводе относится только к полумодулярным схемам и означает, что такая задержка не выводит схему из этого класса.
Более того, еще Маллер показал, что все полумодулярные схемы не чувствительны к задержке в проводе исходящем из выхода элемента до первого разветвления - именно этот фокус и проделал комментатор. Скажем, в синхронной схеме он бы не прошел.
И, строго говоря, схема с добавленной задержкой не эквивалентна исходной, т.к. имеет в двое больше состояний и может быть для получения этих дополнительных состояний задержку-то и добавили.
Хорошо бы дать строгие определения что такое рассматриваемое множество схем, что такое подмножество тупиковых схем и т.д. Например, счётчик, который досчитав до четырёх, выдаёт какую-то заданную последовательность и останавливается (сначала цикл, потом хвост) это тупиковая схема?
Кстати, электрически, 0(1)-схема - это вовсе не схема, а набор независимых схем. Что справедливо и в общем случае, булевы уравнения в системе могут и не подставляться одно в другое. Таким образом, интересно было бы отделить множественное число от единственного. Когда схема под номером таким-то это действительно одна схема, а не набор схем? К этому же вопросу примыкает вопрос буферов. Очевидно, что схему размерности n-1 можно доопределить до n введя набор буферов, замкнутых на себя. Это один способ. Второй - рассмотреть множество проводов и вставить буферы туда.
Это справедливое замечание, но я ограничился подсчетом схем (различных систем уравнений) не исследуя их структуру. Такая попытка исследования была предпринята в серии статей "Последовательные схемы" опубликованных в Песочнице Хабра. Меня больше интересовали статистические характеристики схем, а именно размеры множеств изоморфных к которым они принадлежат. То, что среди перечисляемых схем много "мусора" очевидно, но, как пошутил один математик, - это на Земле это мусор, а может на Альфе Центавра Ab лучшие умы пытаются создать что-то подобное, но не смогут пока не прочитают обсуждаемый материал.
Рассматриваются все возможные схемы поведение которых можно задать системой логических уравнений, как в известной комментатору Алгебре асинхронных логических схем.
Тупиковые схемы не определяются, определяются тупиковые состояния, т.е. такие, в которых выходы всех элементов устойчивы. Например, генератор из трех, соединенных в кольцо, инверторов можно доопределить так, что состояния 000 и 111 будут устойчивы и схема станет последовательной для всех состояний, хотя, конечно, и усложнится.
Это частный (и демонстративный случай) того, о чём говорилось в моём комментарии к предыдущей Вашей статье с медицинским названием "ПМС". А именно - если пометить тупиковые состояния иксами (don't care), то схема станет (гораздо) проще. Такие тупиковые состояния Вы раньше называли устойчивыми. В данном случае под словом тупик я имею ввиду последнее состояние в котором схема останавливается навсегда. Ключевое слово - навсегда, до сброса.
Естественно из тупикового (сиречь устойчивого) состояния схема сама не выйдет. Можно ли устойчивые состояния переопределять произвольно с целью минимизации схемы,- вопрос ее(схемы) применения и в данной статье не рассматривается, но как бы эти состояния не определить, полученная схема все равно будет описана системой логических уравнений, а значит и посчитана, если число n элементов не слишком велико.
У Вас в той же статье ПМС используется тот же термин из теории сложности, что и для метода Квайна-МакКласки. Причём тут это? Притом, что сложность минимизации системы не полностью определённых булевых фуннкций (сильно разреженной таблицы истинности) - это, наверняка, не степенная функция. Можно спросить про такую минимизацию у искусственного интеллекта (и быть готовым к тому, что ответ будет поверхностным).
Теория сложности применяется к оценке разных алгоритмов и то, что комментатор знает о ее оценке метода Квайна-МакКласки, свидетельствует о его высокой образованности. Но так совпало, что и алгоритм пересчета схем о котором толкуют мои статьи обладает высокой сложностью. Такова природа вещей и не надо обвинять в этом автора.
Рассмотрим случай n=3 и схемы, представляющие собой набор 2+1. А именно, такие, что после минимизации таблицы истинности первое уравнение подставляется во второе, а третье - само по себе. Могут ли эти уравнения быть такими же, как и в случаях n=2 и n=1, несмотря на дополнительные устойчивые состояния? Наверное, да, но не все. Эти схемы можно назвать изоморфными наследниками. Более того, поскольку устойчивые состояния ни на что не влияют, этих наследников можно задать с помощью don't care.
В статье рассматриваются только алгоритмы подсчета схем разных подклассов без учета структурных особенностей самих схем. Поднятым вами проблемам уделено некоторое внимание в цикле статей "Последовательные схемы", опубликованном в песочнице.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Изоморфные схемы