Генератор псевдослучайных чисел Опции

[DS]

Нужен генератор 9 битных псевдослучайных чисел, с периодом повторения 2 в 24 или около того.
Я так понимаю, что нужен 24 битный сдвиговый регистр с обратными связями и можно просто брать 9 бит с его разрядов. Или все сложнее ?
Книжки у меня есть, но, честно говоря некогда разбираться, поскольку вопрос одноразовый.
С каких разрядов нужно брать обратную связь для получения правильного цикла ?

[DS]

Мне собственно полином был нужен под 32 разряда. Если делать в железке, то достаточно с указанных разрядов все просуммировать (XOR) и завести на 0 разряд, а код формировать 9 -ти кратным выполением сдвига , так ? Что нельзя брать кусок этого же регистра я уже понял - пример с нулями сам просится.

[vladv]

Мне собственно полином был нужен под 32 разряда. Если делать в железке, то достаточно с указанных разрядов все просуммировать (XOR) и завести на 0 разряд, а код формировать 9 -ти кратным выполением сдвига , так ?

Почти достаточно. Еще надо перевернуть их порядок, иначе рискуите не получить последовательность
максимальной длины.

Вообще говоря, есть две формы построения LFSR:
- в форме Фибоначи, это когда с указанных разрядов все просуммировать (XOR) и
заводится на 0 разряд
- в форме Галуа, это когда старший разряд суммируется в указанные разряды (как в примере bve).
Для полинома 0x4004000f имеем:
- "в указанные разряды" для Галуа: (32), 30, 26,3,2,1,0
- "с указанных разрядов" для Фибоначи: 32,31,30,29,6,2, (0)
Для обоих форм длина последовательности будет одинаковой и даже это общий случай) последовательность бит со старшего (а может быть и для любого) разряда с точностью до фазы
у обоих форм будет одинаковая. Однако последовательность состояний регистров в целом
для разных форм будут разные.

Если интересно, могу предложить небольшую статью:
http://www.newwaveinstruments.com/resource...ter_lfsr.htm
Там есть примеры других коэффициентов для различных длин регистров.

Кстати, если для 32-разрядного регистра формировать 9-ти разрядный код 9-ти кратным сдвигом,
то длина последовательности будет 1431655765, что намного больше, чем 2**24 .

Сообщение отредактировал vladv - Sep 9 2006, 13:06