Как бы я приступил к реализации этого алгоритма?
-
20-08-2019 - |
Вопрос
Некоторое время назад я пытался принудительно использовать пульт дистанционного управления, который отправил 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 бита, воспользовавшись этим?
Решение
То, о чем вы говорите, - это последовательность де Брейна.Если вас не волнует, как это работает, вам просто нужен результат, вот оно.
Другие советы
Навскидку, я полагаю, что переключение одного бита в каждой 12-битной последовательности привело бы к появлению еще 13 комбинаций, например 111111111101000000000010, затем 111111111011000000000100 и т.д.Но вам все равно придется сделать много перестановок, даже с одним битом, я думаю, вам все равно придется сделать 111111111101000000000100 и т.д.Затем переверните два бита с одной стороны и 1 с другой и т.д.