Код LFSR дает неверный результат

Question

У меня есть код для LFSR и я получаю неправильные результаты, первые 8 бит должны быть 01110010, но я получаю 0101111001.

Я говорю о Галуа LSFR: en.wikipedia.org/wiki/Linear-feedback_shift_register

Кто-нибудь может увидеть, в чем проблема с этим кодом?

def lfsr(seed, taps):
  for i in range(10):
      nxt = sum([ seed[x] for x in taps]) % 2
      yield nxt
      seed = ([nxt] + seed)[:max(taps)+1]



for x in lfsr([0,0,1,1,1,0,0,1],[6,5,1]) :
  print x

Answer 1

Мой ответ на вопрос "Кто-нибудь может увидеть, в чем проблема с этим кодом?", - нет. Код работает, реализует LFSR (типа, часто используемого для аппаратного обеспечения псевдослучайных сигналов, и является основой для популярных функций CRC). Мне осталось догадаться, почему ты так думаешь.

LFSR этого типа может быть визуализирован как регистр сдвига с ответвлениями:

pos   0 1 2 3 4 5 6 7
reg   0 0 1 1 1 0 0 1
    ^-  +       + +

На каждой итерации одно значение вычисляется из отводов и вставляется на одном конце, сдвигая другие значения. В этом случае новый бит становится LSB. Итак, давайте запустим этот LFSR несколько циклов:

taps    +       + +
pos   0 1 2 3 4 5 6 7
reg   0 0 1 1 1 0 0 1
c1    0 0 0 1 1 1 0 0
c2    1 0 0 0 1 1 1 0
c3    0 1 0 0 0 1 1 1
c4    1 0 1 0 0 0 1 1
c5    1 1 0 1 0 0 0 1
c6    1 1 1 0 1 0 0 0
c7    1 1 1 1 0 1 0 0
c8    0 1 1 1 1 0 1 0

Обратите внимание, что мы читаем выходные биты в столбце 0, начиная с c1. Между прочим, позиция 7 не должна существовать, потому что нет никаких отводов так далеко назад; фрагмент кода удаляет такие столбцы.

Мне удалось воспроизвести значение, которое, как вы говорите, вы получаете, изменив входные и выходные данные восьми циклов. Можете ли вы объяснить, как вы достигнете значения, которое, как вы говорите, должно быть?

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

taps    +       + +  -v
pos   0 1 2 3 4 5 6 7
reg   0 0 1 1 1 0 0 1
c1    0 1 1 1 0 0 1 0
c2    1 1 1 0 0 1 0 0
c3    1 1 0 0 1 0 0 0
c4    1 0 0 1 0 0 0 1

Но даже в этом случае вывод будет 0001010111 (на этот раз читайте в столбце 7).