Как бы я пошел о реализации этого алгоритма?

Question

Некоторое время назад я пытался заставить пульт дистанционного управления отправлять 12-битный двоичный «ключ».

Устройство, которое я сделал, работало, но было очень медленным, поскольку оно пробовало каждую комбинацию со скоростью около 50 бит в секунду (4096 кодов = 49152 бит = ~ 16 минут)

Я открыл приемник и обнаружил, что он использует сдвиговый регистр для проверки кодов, и между попытками не требовалось никакой задержки. Это означало, что получатель просто просматривал последние 12 битов, которые должны быть получены, чтобы определить, соответствуют ли они ключу.

Это означало, что, если поток 111111111111000000000000 был отправлен, он фактически перепробовал все эти коды.

111111111111    111111111110    111111111100    111111111000
111111110000    111111100000    111111000000    111110000000
111100000000    111000000000    110000000000    100000000000
000000000000

В этом случае я использовал 24 бита, чтобы попробовать 13 12-битных комбинаций (> 90% сжатия).

Кто-нибудь знает алгоритм, который мог бы уменьшить мои 49152 бита, отправленные, воспользовавшись этим?

Answer 1

То, о чем вы говорите, это последовательность де Брейна . Если вас не волнует, как это работает, вам нужен результат, здесь это .

Answer 2

Вне головы, я полагаю, что переключение одного бита в каждой 12-битной последовательности позаботится о других 13 комбинациях, например, 111111111101000000000010, затем 111111111011000000000100 и т. Д. Но вам все равно придется делать много перестановок даже при один бит, я думаю, вам все еще нужно сделать 111111111101000000000100 и т. д. Затем переверните два бита с одной стороны и 1 с другой и т. д.