Объяснение кода Galois LFSR

Я пытаюсь понять, как работает код LFSR Галуа. На странице википедии есть рисунок с примером. Есть фрагмент кода C.

#include <stdint.h>
uint16_t lfsr = 0xACE1u;
unsigned period = 0;

do {
unsigned lsb = lfsr & 1;  /* Get lsb (i.e., the output bit). */
lfsr >>= 1;               /* Shift register */
if (lsb == 1)             /* Only apply toggle mask if output bit is 1. */
lfsr ^= 0xB400u;        /* Apply toggle mask, value has 1 at bits corresponding
                         * to taps, 0 elsewhere. */
++period;
} while(lfsr != 0xACE1u);

Я не могу понять рисунок, приведенный в Википедии, и соотнести его с кодом. что делает маска переключения? Может ли кто-нибудь объяснить, как операция работает с последовательностью битов примера и ее смещенными версиями. Я не знаю полей и не понимаю код. Я проверил в Интернете, но не смог найти хороших объяснений алгоритма, не вдаваясь в терминологию полей. Пожалуйста, помогите.

c math shift galois-field

Karan Talasila 03.06.2013 источник

comment

Я пытаюсь реализовать Galois LFSR для запутывания строки, я хочу понять, как работает LFSR. В приведенном выше примере вики 0xACE1u является начальным состоянием. Могу ли я узнать, что такое «0xB400u»? - Ravi Kiran 16.06.2017

Ответы (1)

arrow_upward
8
arrow_downward

Все может стать яснее, если вы на самом деле запустите код и добавите несколько строк, чтобы увидеть промежуточное содержимое переменной регистра сдвига lfsr:

#include <stdint.h>
#include <stdio.h>

int main(int argc, char* argv[])
{
    uint16_t lfsr = 0xACE1u;
    unsigned period = 0;
    char s[16+1];

    do {
          unsigned lsb = lfsr & 1;  /* Get lsb (i.e., the output bit). */
          lfsr >>= 1;               /* Shift register */
          if (lsb == 1)             /* Only apply toggle mask if output bit is 1. */
            lfsr ^= 0xB400u;        /* Apply toggle mask, value has 1 at bits corresponding
                                    /* to taps, 0 elsewhere. */
          ++period;

          for (int i = 0; i < 16; i++)
          {
             s[15 - i] = (lfsr & (1 << i)) ? '1' : '0';
          }
          s[16] = '\0';
          printf("\n%10d: %s", period, s);
    } while(lfsr != 0xACE1u);

    return 0;
}

Вывод выглядит следующим образом:

     1: 1110001001110000
     2: 0111000100111000
     3: 0011100010011100
     4: 0001110001001110
     5: 0000111000100111
     6: 1011001100010011
     7: 1110110110001001
     8: 1100001011000100
    ....

 65527: 1000000110011100
 65528: 0100000011001110
 65529: 0010000001100111
 65530: 1010010000110011
 65531: 1110011000011001
 65532: 1100011100001100
 65533: 0110001110000110
 65534: 0011000111000011
 65535: 1010110011100001   (= 0xACE1u)

Оператор сдвига ">>" перемещает все биты на единицу вправо. Для целых чисел без знака это то же самое, что деление на два. "lfsr & 1" возвращает младший значащий бит (= бит 0). "lfsr ^= 0xB400u" инвертирует четыре из 16 бит lfsr, потому что оператор "^" оценивает побитовое исключающее или. 0xB400 в двоичном формате равно 1011 0100 0000 0000. Поэтому старший бит (= бит 15), бит 13, бит 12 и бит 10 инвертируются.

Axel Kemper 03.06.2013

comment

Спасибо за объяснение. Могу ли я узнать, почему ›› используется для деления на 2. Фактическая операция, которую нужно выполнить, это lfsr*x mod p(x), где lfsr — текущее состояние, а p(x) — характеристический полином. Я не понимаю, почему краны переворачиваются, когда младший бит равен 1, и сохраняются, как обычно, когда младший бит равен 0. Как операция модуля относится к флиппину кранов, я не могу понять. - Karan Talasila; 03.06.2013

comment

Попробуйте понять первый 4-битный пример в статье Википедии (en.wikipedia.org/wiki/Linear_feedback_shift_register< /а>). Затем расширьте это до 16 бит. Возможно, стоит сначала взглянуть на вентили exor и сдвиговые регистры. - Axel Kemper; 03.06.2013

comment

Могу ли я узнать, что это за шестнадцатеричное значение «0xB400u» в приведенном выше примере? - Ravi Kiran; 16.06.2017

comment