Абстрактные симплициальные комплексы

Посчитал, теперь у меня есть полный список из 16143 монотонных функций шести аргументов. Прямо комбинаторный взрыв какой-то. Для семи аргументов должно быть 489996795, но я проверять не буду: нет уверенности, что пентиуму для вычислений хватит времени жизни вселенной. :)

Математика - царица наук. Как оказалось, последовательность 1,2,5,20,180,16143 давно известна и сводится к подсчёту количества абстрактных симплициальных комплексов из N неразмеченных элементов. Спасибо spamsink и a_shen за подсказку.

Желающие приобщиться к суровой науке могут попытаться прорубить статью, которая всё объясняет.

Почему интересны именно функции с шестью входами? У них есть определённое практическое применение. Дело в том, что в последних семействах микросхем Xilinx FPGA используются именно шестивходовые программируемые матрицы (LUT6).

Асинхронный канал: протокол 1-из-N

Главная фишка асинхронного дизайна - отсутствие тактирующего сигнала. Вместо глобального генератора синхроимпульсов используется локальный сигнал подтверждения и четырехфазовый протокол взаимодействия. Есть разные варианты протоколов, подробно описанные в умной книжке. Я здесь коротенько набросаю один их них.



Сигналы данных направлены от передатчика к приёмнику. Обычно один бит данных кодируется двумя сигналами (1-из-2). Иногда два бита кодируются четырьмя сигналами (1-из-4), это имеет свои преимущества.



Фаза 1: исходно сигналы данных равны нуль (состояние NULL). Подтверждение также равно нулю. Инициатива на стороне передатчика. Когда готов, передатчик выставляет один из сигналов данных в единицу (cостояние DATA).

Фаза 2: данные поступили на вход приёмника (cостояние DATA). Приёмник выставляет сигнал подтверждения.

Фаза 3: передатчик получил сигнал подтверждения и переводит сигналы данных обратно в состояние NULL.

Фаза 4: приёмник обнаружил состояние NULL на входе данных и сбрасывает сигнал подтверждения.

Здесь действуют два важных правила. В фазе 1 (когда ack=0) передатчик имеет право формировать на шине данных только положительные фронты. В фазе 3 (когда ack=1) допускаются только отрицательные фронты. При этих условиях синхронизация всегда устойчива, независимо от времени распространения сигнала и задержек на логических элементах.

Я обещал объяснить, почему так важны монотонные булевы функции. Всякие вычисления и прочие преобразования данных выполняются на фазе 1. Сигналы данных проходят через блок комбинационной логики. На вход поступают положительные фронты. Важно, чтобы на выходе тоже появлялись только положительные фронты, иначе собьётся синхронизация. Если комбинационную логику составлять только из монотонных функций, можно гарантировать, что отрицательных фронтов на выходе не будет.