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

[DS]

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

[bve]

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

Долго пользуюсь 32-разрядным генератором с полиномом 0x4004000f.
Алгоритм таков: Xn+1=Xn<<1
IF ( Xn+1<0 ) Xn+1=Xn+1 XOR 0x4004000F

Особенно приятно, что в этом генераторе цепочка бит любой длины - случайна.
Я брал и 2 раза по 16, и 3 раза по 10 для экономии вычислений.

[DS]

IF ( Xn+1<0 )

Я вот этого не понял - XOR делается, только если старший бит ==1 ? Это зачем ?

[vladv]

IF ( Xn+1<0 )

Я вот этого не понял - XOR делается, только если старший бит ==1 ? Это зачем ?

По определению сдвигового регистра с линейными обратными связями (в форме Галуа).
Для указанного полинома (X**32+X**30+X**26+X**3+X**2+X**1+1) старший бит
регистра "XOR-ится в разряды" 0,1,2,3,26 и 30:
X[0] <= X[31]
X[1] <= X[31]^X[0]
X[2] <= X[31]^X[1]
X[3] <= X[31]^X[2]
X[4] <= X[3]
X[5] <= X[4]
...
X[25] <= X[24]
X[26] <= X[31]^X[25]
X[27] <= X[26]
...
X[29] <= X[28]
X[30] <= X[31]^X[29]
X[31] <= X[30]


Если просто брать 9 бит с разных разрядов, то будут встречаться "не совсем случайные"
подпоследовательности. Например, для 9-ти старших бит 24-х разрядного регистра в
какой-то момент будет такая последовательность:
01: 000000000
02: 000000000
...
14: 000000000
15: 000000000
16: 000000001
17: 000000010
...
23: 010000000
24: 100000000

[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

[vladv]

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

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

Был неправ. Можно и не переворачивать. В этом случае последовательность также будет максимальной длины, но иметь обратный порядок (на отдельном бите).

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

[DS]

Спасибо за ссылку ! Таблица полиномов - то, что нужно. Про поля Галуа я, видимо, все-таки почитаю, надо только выбрать пару дней спокойных, чтобы подумать. Заинтересовала связь неприводимых полиномов и регистров сдвига

Да, что-то приведенного полинома нет в таблице - ошибка в полиноме или он из секретных ?

[gab]

Ещё можете поискать по слову "tauswothe". При достаточно маленьких требуемых ресурсах он даёт достаточно длинную последовательность...

[Oldring]

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

Это зависит от требования к качеству непредсказуемости последовательности. Например, для криптографических задач LFSR как генератор случайных чисел абсолютно неприменим. Кроме того, LFSR как генератор именно чисел а не битовых последовательностей считается довольно посредственным - могут вылезти неожиданные эффекты если использовать эти числа в неподходящем месте. А в остальном все тривиально - выбор полиномов и длин безграничен. Если конечно период последовательности допустипо делать _больше_ требуемого минимума и заметные корреляции на длинах меньше периода допустимы.

Проиллюстрирую почему LFSR как генератор чисел плох. Например, такая примитивная реализация. Чтобы получить очередное число мы прокручиваем LFSR на один бит и берем 9 соседних разрядов. С вероятностью 1/2 очередное число будет в ровно два раза больше/меньше предыдущего, в зависимости от направления сдвига. Для многих задач это неприемлемо. Разные ухищрения позволяют улучшить последовательность получаемых чисел - но все равно она может оказаться неожиданно плохой. Как получать "хорошие" последовательности чисел - это отдельная наука, начните с Кнута.

[DS]

Кнута я как бы читал. Про линейно-конгруэнтные генераторы помню до сих пор и пользуюсь иногда.
У меня сейчас другая задача - размазать в спектре сигнала вредный артефактный пик, который потенциально может пустить вразнос систему управления.
Для железа сдвиговый регистр - самое то, а что надо делать не 1 а 9 сдвигов, уже написано было.

[Oldring]

Для железа сдвиговый регистр - самое то, а что надо делать не 1 а 9 сдвигов, уже написано было.

Что может произойти с системой управления - это вопрос отдельный. У меня нет данных чтобы его обсуждать. Наверняка для огрубления системы управления особо хорошие случайные числа вообще не нужны - может быть даже просто нелинейное подмешивание куда-нибудь бинарной псевдослучайной последовательности поможет.

Исходя из этого, возможно, что 1 сдвиг, что 9 - разницу не заметите. 9 сдвигов устраняют упомянутую мною неприятность - но все равно такая псевдослучайная последовательность может не проходить по довольно простым критериям случайности. См. например упражнение 3.2.2.18 из Кнута на русском 2000 года издания.

[DS]

Энергия в пике не превышает 10-20% энергии шума в полосе пропускания, поэтому мне важно просто чтобы длина цикла была большой, чтобы не перегнать этот пик в низкие частоты, где у меня шум маленький, а усиление большое. А то, что будет слегка неравномерный спектр, мне не важно - я пик размажу на ширину, вдесятеро большую полосы пропускания, он в белом шуме утонет.

[Макс_Мат]

ты был почти прав. Только тебе нужен 24+9=33 разрядный генератор. Полиномы посмотри поиском, либо Питерсон, Уэлдон "Коды, исправляющиие ошибки"

[bve]

А кто-нибудь знает БЫСТРЫй генератор с нормальным распределением?