Линейный регистр сдвига обратной связи?

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

def lfsr(seed, taps): sr, xor = seed, 0 while 1: for t in taps: xor += int(sr[t-1]) if xor%2 == 0.0: xor = 0 else: xor = 1 print xor sr, xor = str(xor) + sr[:-1], 0 print sr if sr == seed: break lfsr('11001001', (8,7,6,1)) #example 

Я назвал «xor» вывод функции XOR, не очень корректным. Тем не менее, это просто предназначено, чтобы показать, как он проходит через его возможные состояния, на самом деле вы заметили, что регистр представлен строкой. Не так много логической согласованности.

Это можно легко превратить в хорошую игрушку, которую вы можете смотреть часами (по крайней мере, я мог 🙂

 def lfsr(seed, taps): import time sr, xor = seed, 0 while 1: for t in taps: xor += int(sr[t-1]) if xor%2 == 0.0: xor = 0 else: xor = 1 print xor print time.sleep(0.75) sr, xor = str(xor) + sr[:-1], 0 print sr print time.sleep(0.75) 

Тогда мне это показалось, что это такое при написании программного обеспечения? Я слышал, что он может генерировать случайные числа; это правда? как? Итак, было бы неплохо, если бы кто-то мог:

  • объяснить, как использовать такое устройство в разработке программного обеспечения
  • придумайте какой-нибудь код, чтобы поддержать вышеизложенное или просто как мой, чтобы показать разные способы сделать это, на любом языке

Кроме того, поскольку это не так много дидактического материала вокруг этой части логики и цифровой схемы, было бы неплохо, если бы это могло быть местом для noobies (как я), чтобы лучше понять эту вещь или, лучше, понять, что это и как это может быть полезно при написании программного обеспечения. Должна ли это сделать wiki сообщества?

Тем не менее, если кто-то хочет играть в гольф … пожалуйста.

    One Solution collect form web for “Линейный регистр сдвига обратной связи?”

    На самом деле алгоритмы, основанные на LFSR, очень распространены. CRC фактически основан на LFSR. Конечно, в классах информатики люди говорят о полиномах, когда они говорят о том, как входное значение должно быть XORed с накопленным значением, в электротехнике мы говорим о кранах вместо этого. Это та же самая другая терминология.

    CRC32 является очень распространенным. Он используется для обнаружения ошибок в кадрах Ethernet. Это означает, что когда я отправил этот ответ, мой компьютер использовал алгоритм, основанный на LFSR, для генерации хэша IP-пакета, чтобы мой маршрутизатор мог убедиться, что его передача не повреждена.

    Другими примерами являются файлы Zip и Gzip. Оба используют CRC для обнаружения ошибок. Zip использует CRC32, а Gzip использует как CRC16, так и CRC32.

    CRC являются в основном хэш-функциями. И это достаточно хорошо, чтобы Интернет работал. Это означает, что LFSR – довольно хорошие хэш-функции. Я не уверен, что вы знаете это, но в целом хорошие хэш-функции считаются хорошими генераторами случайных чисел. Но дело с LFSR заключается в том, что выбор правильных кранов (полиномов) очень важен для качества хэш-функции / случайного числа.

    Ваш код, как правило, представляет собой игрушечный код, поскольку он работает с цепочкой из них и нулями. В реальном мире LFSR работает над битами в байте. Каждый байт, который вы нажимаете на LFSR, изменяет накопленное значение регистра. Это значение является фактически контрольной суммой всех байтов, которые вы проталкиваете через регистр. Два общих способа использования этого значения в качестве случайного числа – либо использовать счетчик, либо нажимать последовательность чисел через регистр, тем самым преобразуя линейную последовательность 1,2,3,4 в некоторую хешированную последовательность, такую ​​как 15306, 225, 557, 994, или для возврата текущего значения в регистр для генерации нового номера в кажущейся случайной последовательности.

    Следует отметить, что делать это наивно с помощью бит-fiddling LFSR довольно медленно, так как вам приходится обрабатывать биты за раз. Таким образом, люди придумали способы использования предварительно рассчитанных таблиц, чтобы сделать это по восемь бит за раз или даже по 32 бита за раз. Вот почему вы почти никогда не видите код LFSR в дикой природе. В большинстве производственных кодов он маскируется как нечто другое.

    Но иногда может пригодиться простой бит-крутой LFSR. Однажды я написал драйвер Modbus для микроконтроллера PIC, и этот протокол использовал CRC16. Предварительно рассчитанная таблица требует 256 байт памяти, а мой процессор имеет только 68 байтов ( я не шучу ). Поэтому мне пришлось использовать LFSR.

    Python - лучший язык программирования в мире.