[DS 0]

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

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

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

С каких разрядов нужно брать обратную связь для получения правильного цикла ?

[bve 1]

Нужен генератор 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 0]

IF ( Xn+1<0 )

 

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

[vladv 0]

 

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 0]

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

[vladv 0]

Мне собственно полином был нужен под 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 :).

Изменено 9 сентября, 2006 пользователем vladv

[vladv 0]

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

 

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

максимальной длины.

 

 

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

Изменено 9 сентября, 2006 пользователем vladv

[DS 0]

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

 

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

[gab 0]

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

[Oldring 0]

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

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

 

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

 

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

[DS 0]

Кнута я как бы читал. Про линейно-конгруэнтные генераторы помню до сих пор и пользуюсь иногда.

У меня сейчас другая задача - размазать в спектре сигнала вредный артефактный пик, который потенциально может пустить вразнос систему управления.

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

[Oldring 0]

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

 

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

 

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

[DS 0]

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

[ya_maks 0]

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

[bve 1]

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