Обнаружение узора в потоке битов

Пример со светофором продвигается полностью самостоятельно; детектор последовательности же реагирует на внешний поток битов, по одному биту за такт, и должен заметить ровно тот момент, когда только что появился целевой узор — скажем, 3-битная последовательность 1-0-1, — как бы она ни перемежалась с другими битами до и после.

Одно состояние на «сколько уже совпало»

Каждое состояние отражает, какая часть целевой последовательности уже совпала: S0 (ничего), S1 (совпал ведущий 1), S2 (совпало 1-0), после чего совпадение завершается и автомат возвращается в S0 или S1 в зависимости от того, что придёт следующим. Приход 0 в состоянии S1 ведёт в S2; приход 1 в состоянии S2 завершает совпадение. Важно, что совпадения могут перекрываться: завершение 1-0-1 из S2 приводит обратно в S1, а не в S0, поскольку та же самая финальная 1 может оказаться началом следующего совпадения.

Почему это должен быть автомат Мили, а не Мура

Весь смысл — пометить совпадение ровно в момент прихода решающего бита, в том же самом такте, — это именно та реактивность в том же такте, что определяет автомат Мили: выход = f(состояние, вход), а не только выход = f(состояние). Версия на автомате Мура смогла бы поднять выход лишь спустя полный такт после того, как узор уже завершился.

Попробуйте сами

Соберите 2-битный регистр состояния и логику следующего состояния/выхода для детектора 1-0-1 в редакторе схем — три состояния свободно помещаются в 2 бита, — подавайте поток битов через переключатель INPUT по одному такту CLOCK за раз и убедитесь, что выход поднимается ровно в момент прихода третьего бита узора 1-0-1, включая перекрывающиеся совпадения вроде 1-0-1-0-1.