И эта тема, наверняка, не связана с "Hamiltonian decomposition of the hypercube". А жаль. Известно, что для n-куба существует floor(n/2) раздельных гамильтоновских циклов.
Это ограничение возникло тогда, когда Вы решили, что из-за деревьев не видно леса. Может быть всё-таки наоборот, из-за леса не видно деревьев? Например, чтобы сократить перебор для последовательных схем можно рассмотреть только связные графы на гиперкубе.
Если взглянуть что изменилось с 1960, а именно, кто ссылается на Фразера-Маллера, мы увидим, что это кооператив "Трасса". А если почитать статью этого кооператива на английском языке, то окажется, что анализ на полумодулярность можно делать гораздо быстрее, чем Вы. А именно, рассматривать только параллельные переключения. Впрочем, на малых размерностях преимущество может быть и не заметно.
Первый алгоритм анализа схем на предмет независимости от скорости
W. D. Frazer and D. E. Muller, “ A method for factoring the action of asynchronous circuits,” AIEE Fall General Meeting, 1960
основан на следующей идее:
Диаграмма переходов является дистрибутивной относительно состояния U, если каждое состояние V, достижимое из U, не является конфликтным и не является детонантным относительно какого-либо из своих элементов.
Состояние V схемы S называется конфликтным, если в V возбуждаются два элемента zj и zi, и zi стабилен в состоянии W, которое отличается от V только одной цифрой, соответствующей элементу zj. Другими словами, для элемента zi происходит переход сигнала типа 1*->1 или 0*->0, в то время как zj изменяет выходной сигнал.
Состояние W называется детонантным относительно элемента zi, если существует пара различных состояний U и V, непосредственно следующих за W (т.е., W->U, W->V), так что zi стабилен в состоянии W и возбуждается в обоих состояниях V и U.
Схема называется живой, если её граф состояний является сильно связным.
Детонантное (или детонационное?) состояние определено Вашими соавторами (а может быть и Вами) в Книге 1986. Отличие состоит в том, что оно определено (насколько я помню) для диаграммы переходов, которая даёт одну схему. У Вас из одной диаграммы может родиться много независимых схем...
В статье "On Hazard-Free Implementation of Speed-Independent Circuits" Кондратьев, Кишиневский и Яковлев по поводу дистрибутивных схем пишут следующее. В терминах диаграммы переходов, причинно-следственная связь ИЛИ соответствует понятию детонационного состояния. Т.е. Ваш алгоритм каким-то образом отсекает (или должен отсекать) детонационные состояния.
Рассмотрим случай n=3 и схемы, представляющие собой набор 2+1. А именно, такие, что после минимизации таблицы истинности первое уравнение подставляется во второе, а третье - само по себе. Могут ли эти уравнения быть такими же, как и в случаях n=2 и n=1, несмотря на дополнительные устойчивые состояния? Наверное, да, но не все. Эти схемы можно назвать изоморфными наследниками. Более того, поскольку устойчивые состояния ни на что не влияют, этих наследников можно задать с помощью don't care.
Кстати, электрически, 0(1)-схема - это вовсе не схема, а набор независимых схем. Что справедливо и в общем случае, булевы уравнения в системе могут и не подставляться одно в другое. Таким образом, интересно было бы отделить множественное число от единственного. Когда схема под номером таким-то это действительно одна схема, а не набор схем? К этому же вопросу примыкает вопрос буферов. Очевидно, что схему размерности n-1 можно доопределить до n введя набор буферов, замкнутых на себя. Это один способ. Второй - рассмотреть множество проводов и вставить буферы туда.
У Вас в той же статье ПМС используется тот же термин из теории сложности, что и для метода Квайна-МакКласки. Причём тут это? Притом, что сложность минимизации системы не полностью определённых булевых фуннкций (сильно разреженной таблицы истинности) - это, наверняка, не степенная функция. Можно спросить про такую минимизацию у искусственного интеллекта (и быть готовым к тому, что ответ будет поверхностным).
Это частный (и демонстративный случай) того, о чём говорилось в моём комментарии к предыдущей Вашей статье с медицинским названием "ПМС". А именно - если пометить тупиковые состояния иксами (don't care), то схема станет (гораздо) проще. Такие тупиковые состояния Вы раньше называли устойчивыми. В данном случае под словом тупик я имею ввиду последнее состояние в котором схема останавливается навсегда. Ключевое слово - навсегда, до сброса.
Хорошо бы дать строгие определения что такое рассматриваемое множество схем, что такое подмножество тупиковых схем и т.д. Например, счётчик, который досчитав до четырёх, выдаёт какую-то заданную последовательность и останавливается (сначала цикл, потом хвост) это тупиковая схема?
Насколько я понимаю, поиск изоморфных схем здесь происходит не среди полумодулярных (живых), а среди автономных (которые могут быть и не живыми). Последние для практики малоинтересны, поскольку представляют собой генератор конечной последовательности импульсов (выбег и стоп). Очевидно, что перебор комбинаций только для живых схем будет существенно короче. Кроме того, можно определить такое расширение живых схем размерности n-1 до таковых размерности n, которое отличается только добалением буфера. Смысл в том, что функционально эти схемы одинаковы, поскольку буфер - это модель провода. Т.е. новая n-схема просто не чувствительна к задержке в этом проводе.
Во-первых, основные понятия были введены не в 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 возникает вопрос правильных начальных условий. Таких, при которых схема является полумодулярной.
Я не знаю что такое гигачат. А узнать я хотел всего лишь как устроен логический блок в китайских FPGA, которые пока не вышли за пределы Китая и требуют регистрацию. Таких фирм по крайней мере две - Hercules и Ehiway.
Feedback, в смысле отзывы, предполагают замыкание, не так ли? :) Будем считать это рекламой. Неплохо бы там же разместить набор страниц, выдернутых из документации каждого производителя. На странице нарисован логический блок. Нужно знать куда попадёт код. В то, что производитель покажет как устроен коммутатор я не верю. Надёргать страницы - это работа для волонтёров. С ними я и поделился ссылкой.
Интересно какой отчёт даст Yosys после компиляции того же самого кода. Скорей всего для оптимизации Gowin использует ABC, как и Yosys. Тем временем появился другой (русскоязычный :) оптимизатор
А может взять и посмотреть кто из производителей даёт самый быстрый сумматор в железе? Не по типовой измеренной задержке, а по схемотехнике. Да, эти сумматоры почти одинаковые, а вдруг? Тем более, что некоторые китайские фирмы вдруг ожили и обновили ассортимент. Правда, чтобы скачать документацию (на китайском) нужно зарегистрироваться, а для этого может потребоваться китайский email и/или китайский номер телефона. Вот исчерпывающий список производителей FPGA.
Философский оффтоп. Когда-то М.Л. Цетлин придумал термин "целесообразное поведение". На предыдущем витке искусственного интеллекта целесообразное поведение описали математически. Представим теперь, что кто-то взял нейросеть и решил её обучить на наследии Черномырдина. Потом, в качестве не гумманитарного (и не гуманного) эксперимента эту нейросеть заставили написать про "сумматор". Как Черномырдин должен реагировать на просьбы? А на конструктивную критику? Какое поведение для Черномырдина является целесообразным?
Запретить - это цензура. Так нельзя, а то пострадает свобода. А как можно? Можно поставить реостат, который ограничивает доступ нейросети к энергии. Человек пишет параграф текста. Если в этом параграфе есть смысл - это увеличивает сопротивление реостата на 10%. Думаю, что я уже подвинул ползунок реостата на середину. Или у кого-то сомнения, в том, что про "сумматор" пишет не нейросеть?
И эта тема, наверняка, не связана с "Hamiltonian decomposition of the hypercube". А жаль. Известно, что для n-куба существует floor(n/2) раздельных гамильтоновских циклов.
Это ограничение возникло тогда, когда Вы решили, что из-за деревьев не видно леса. Может быть всё-таки наоборот, из-за леса не видно деревьев? Например, чтобы сократить перебор для последовательных схем можно рассмотреть только связные графы на гиперкубе.
Если взглянуть что изменилось с 1960, а именно, кто ссылается на Фразера-Маллера, мы увидим, что это кооператив "Трасса". А если почитать статью этого кооператива на английском языке, то окажется, что анализ на полумодулярность можно делать гораздо быстрее, чем Вы. А именно, рассматривать только параллельные переключения. Впрочем, на малых размерностях преимущество может быть и не заметно.
Первый алгоритм анализа схем на предмет независимости от скорости
W. D. Frazer and D. E. Muller, “ A method for factoring the action of asynchronous circuits,” AIEE Fall General Meeting, 1960
основан на следующей идее:
Диаграмма переходов является дистрибутивной относительно состояния U, если каждое состояние V, достижимое из U, не является конфликтным и не является детонантным относительно какого-либо из своих элементов.
Состояние V схемы S называется конфликтным, если в V возбуждаются два элемента zj и zi, и zi стабилен в состоянии W, которое отличается от V только одной цифрой, соответствующей элементу zj. Другими словами, для элемента zi происходит переход сигнала типа 1*->1 или 0*->0, в то время как zj изменяет выходной сигнал.
Состояние W называется детонантным относительно элемента zi, если существует пара различных состояний U и V, непосредственно следующих за W (т.е., W->U, W->V), так что zi стабилен в состоянии W и возбуждается в обоих состояниях V и U.
Схема называется живой, если её граф состояний является сильно связным.
Детонантное (или детонационное?) состояние определено Вашими соавторами (а может быть и Вами) в Книге 1986. Отличие состоит в том, что оно определено (насколько я помню) для диаграммы переходов, которая даёт одну схему. У Вас из одной диаграммы может родиться много независимых схем...
В статье "On Hazard-Free Implementation of Speed-Independent Circuits" Кондратьев, Кишиневский и Яковлев по поводу дистрибутивных схем пишут следующее. В терминах диаграммы переходов, причинно-следственная связь ИЛИ соответствует понятию детонационного состояния. Т.е. Ваш алгоритм каким-то образом отсекает (или должен отсекать) детонационные состояния.
Рассмотрим случай n=3 и схемы, представляющие собой набор 2+1. А именно, такие, что после минимизации таблицы истинности первое уравнение подставляется во второе, а третье - само по себе. Могут ли эти уравнения быть такими же, как и в случаях n=2 и n=1, несмотря на дополнительные устойчивые состояния? Наверное, да, но не все. Эти схемы можно назвать изоморфными наследниками. Более того, поскольку устойчивые состояния ни на что не влияют, этих наследников можно задать с помощью don't care.
Кстати, электрически, 0(1)-схема - это вовсе не схема, а набор независимых схем. Что справедливо и в общем случае, булевы уравнения в системе могут и не подставляться одно в другое. Таким образом, интересно было бы отделить множественное число от единственного. Когда схема под номером таким-то это действительно одна схема, а не набор схем? К этому же вопросу примыкает вопрос буферов. Очевидно, что схему размерности n-1 можно доопределить до n введя набор буферов, замкнутых на себя. Это один способ. Второй - рассмотреть множество проводов и вставить буферы туда.
У Вас в той же статье ПМС используется тот же термин из теории сложности, что и для метода Квайна-МакКласки. Причём тут это? Притом, что сложность минимизации системы не полностью определённых булевых фуннкций (сильно разреженной таблицы истинности) - это, наверняка, не степенная функция. Можно спросить про такую минимизацию у искусственного интеллекта (и быть готовым к тому, что ответ будет поверхностным).
Это частный (и демонстративный случай) того, о чём говорилось в моём комментарии к предыдущей Вашей статье с медицинским названием "ПМС". А именно - если пометить тупиковые состояния иксами (don't care), то схема станет (гораздо) проще. Такие тупиковые состояния Вы раньше называли устойчивыми. В данном случае под словом тупик я имею ввиду последнее состояние в котором схема останавливается навсегда. Ключевое слово - навсегда, до сброса.
Хорошо бы дать строгие определения что такое рассматриваемое множество схем, что такое подмножество тупиковых схем и т.д. Например, счётчик, который досчитав до четырёх, выдаёт какую-то заданную последовательность и останавливается (сначала цикл, потом хвост) это тупиковая схема?
Насколько я понимаю, поиск изоморфных схем здесь происходит не среди полумодулярных (живых), а среди автономных (которые могут быть и не живыми). Последние для практики малоинтересны, поскольку представляют собой генератор конечной последовательности импульсов (выбег и стоп). Очевидно, что перебор комбинаций только для живых схем будет существенно короче. Кроме того, можно определить такое расширение живых схем размерности n-1 до таковых размерности n, которое отличается только добалением буфера. Смысл в том, что функционально эти схемы одинаковы, поскольку буфер - это модель провода. Т.е. новая n-схема просто не чувствительна к задержке в этом проводе.
Во-первых, основные понятия были введены не в 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 возникает вопрос правильных начальных условий. Таких, при которых схема является полумодулярной.
Я не знаю что такое гигачат. А узнать я хотел всего лишь как устроен логический блок в китайских FPGA, которые пока не вышли за пределы Китая и требуют регистрацию. Таких фирм по крайней мере две - Hercules и Ehiway.
Проблема описана выше, а потом ещё и намёкнуто на то, что она описана выше. У меня нет ни китайского мейла ни китайского номера телефона.
Feedback, в смысле отзывы, предполагают замыкание, не так ли? :) Будем считать это рекламой. Неплохо бы там же разместить набор страниц, выдернутых из документации каждого производителя. На странице нарисован логический блок. Нужно знать куда попадёт код. В то, что производитель покажет как устроен коммутатор я не верю. Надёргать страницы - это работа для волонтёров. С ними я и поделился ссылкой.
Интересно какой отчёт даст Yosys после компиляции того же самого кода. Скорей всего для оптимизации Gowin использует ABC, как и Yosys. Тем временем появился другой (русскоязычный :) оптимизатор
https://arxiv.org/abs/2412.14933
А может взять и посмотреть кто из производителей даёт самый быстрый сумматор в железе? Не по типовой измеренной задержке, а по схемотехнике. Да, эти сумматоры почти одинаковые, а вдруг? Тем более, что некоторые китайские фирмы вдруг ожили и обновили ассортимент. Правда, чтобы скачать документацию (на китайском) нужно зарегистрироваться, а для этого может потребоваться китайский email и/или китайский номер телефона. Вот исчерпывающий список производителей FPGA.
https://github.com/FPGA-Systems/fpga-awesome-list
Философский оффтоп. Когда-то М.Л. Цетлин придумал термин "целесообразное поведение". На предыдущем витке искусственного интеллекта целесообразное поведение описали математически. Представим теперь, что кто-то взял нейросеть и решил её обучить на наследии Черномырдина. Потом, в качестве не гумманитарного (и не гуманного) эксперимента эту нейросеть заставили написать про "сумматор". Как Черномырдин должен реагировать на просьбы? А на конструктивную критику? Какое поведение для Черномырдина является целесообразным?
Запретить - это цензура. Так нельзя, а то пострадает свобода. А как можно? Можно поставить реостат, который ограничивает доступ нейросети к энергии. Человек пишет параграф текста. Если в этом параграфе есть смысл - это увеличивает сопротивление реостата на 10%. Думаю, что я уже подвинул ползунок реостата на середину. Или у кого-то сомнения, в том, что про "сумматор" пишет не нейросеть?