Нужен генератор 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 для экономии вычислений.

Я вот этого не понял - 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

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

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

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

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

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

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

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

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

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

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

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

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

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

А куда быстрее ГПСП, а результат накпливающая сумма за несколько сдвигов?

Один из самых быстрых способов получить нормальное распределение - метод Бокса-Мюллера (нелинейное преобразование двух псевдослучайных последовательностей с равномерным распределением на интервале 0..1). Делал такую штуку на блекфине, вычисление одной выборки (включая генераторы ПСП) занимает 73 такта на выборку(выборка двухканальная). Для вычисления нелинейных преобразований использовал кусочно-линейную аппроксимацию. Подозреваю, что на ПЛИС скорость будет просто бешеная.

Молодой человек, скорости скоростями, но ко всему надо подходить с головой. На ГПСП на том же блэкфине результат получается за максимум 2-4 такта. Так куда быстрее то?

Макс_Мат Результат чего?!

нормально распределенные числа вообщето. О них же речь, насколько я понимаю

Сумма 12-15 равномернораспределенных отсчетов для моей задачи на сигнальном процессоре - долгонько. Вот и ищу "прямой" метод тактов на 3-4 на отсчет.....

Макс_Мат, а ну-ка просветите, что это вы там такое за 2-4 такта считаете??? сумму двух псп что-ли?

Мне интересно, кто сможет дать определение нормального распределения на конечном множестве?

Нет, нет, давайте все-таки двигаться вперед по-порядку. Раз люди в этой ветке что-то обсуждали, значит, возможно, они понимали, о чем беседуют. Вы нарисовались, такой весь из себя красивый и умный, сказали (почти) что все вокруг необразованные болваны, и что нормальное распределение можно генерировать за 4 такта некоего процессора. У меня лично возникло серьезное подозрение, что Вы под нормальным распределением понимали нечто, что другие люди совершенно нормальным распределением назвать не могут даже с очень большой натяжкой, и уж заведомо не подразумевали при обсуждении в этой ветке. Поэтому прежде, чем мы с Вами дойдем до обсуждения смысла использованных ранее в этой ветке уважаемыми собеседниками терминов, а также предельных переходов и аппроксимации непрерывных распределений дискретными, пожалуйста, разъясните все-таки подробно, что именно Вы подразумевали, когда утверждали, что некоторое "нормальное распределение" можно генерировать за 4 такта?

Такое ощущение, что я попал не в профессиональный форум, а в общеобразовательный. Идею дал - мало, "на пальцах" покажи. Надеюсь матлабная модели хватит? Для непосвященных - здесь randint-128 генерит равномер, т.е. описывает состояние регистра псп

R=[];
s=0;
delLine = zeros(32,1);
for i=1:10000,
v = randint(1,1,256)-128;
s = s + v - delLine(end);
delLine = [v; delLine(1:end-1)];
R=[R;s];
end;

Спасибо, теперь стало понятно, что имеется в виду именно скользящее среднее по 32 равномерно распределенным независимым отсчетам. Это, конечно, не так плохо, как я подумал с самого начала. Распределение у такого генератора, конечно, близко к нормальному - но есть одна засада, из-за которой для многих приложений, для которых нужно именно нормальное распределение, он неприменим. От генераторов случайных чисел обычно требуют еще одно свойство - генерируемая последовательность должна быть белой. У этого же генератора автокорреляционная функция представляет собой аккуратный треугольник, простирающийся на +-31 отсчет. Почему-то Вы об это важнейшее свойство упомянуть забыли. Кстати, ранее в этой ветке предлагалось суммирование нескольких равномерно распределенных отсчетов для получения приближения к нормальному распределению.

Нигде выше не сказано о корреляционных свойствах последовательности. Вот какое важное значение имеет строгость в высказываниях. Но уважаемый Олдринг, а для чего существуют литература, знания, опыт, мышление и т.д.? Что мешает нам сделать указанную последовательность "белой"? (Хотя, конечно, строго белым нельзя называть функции на конечных множествах). Что мешает нам рандомизировать знак? А, именно, либо использовать второй псп либо использовать для этого произвольно выбраный разряд генератора (кроме первого разумеется). Посмотрите что получится. И довольствуйтесь приобретенным опытом.

За четыре такта?

А для чего Вы вообще что-то пишете? Какой в этом смысл?
Лично мне от Вас был интересен только способ быстрого построения генератора с нормальным распределением. Больше ничего. Я подумал, что может быть Вы знаете нечто, что другие в это ветке не знают? Оказалось, что Ваш способ с заковыкой и по сути мало отличается от описанного коллегами ранее. Нет, конечно, для некоторых узкоспециализированных задач он подойдет - но, скорее всего, в этих задачах было бы достаточно просто выходы LFSR.

P.S. Надеюсь, написав про невозможность получения белой случайной последовательности на конечных множествах, Вы имели в виду не то, что написали? Формализуйте, пожалйста, Ваше высказывание.

P.P.S. Что получится в результате экспериментов - разъясните, пожалуйста. Мне очень интересно. Кроме увеличения времени вычисления, конечно.

P.P.P.S. Здесь редко формулируют теоремы с математической точностью. Хороший тон - думать о том, что люди еще и подразумевают. Независимость отсчетов - это обычное требование для хороших генераторов.

R=[];
s=0;
delLine = zeros(32,1);
for i=1:10000,
v = randint(1,1,256)-128;
s = s + v - delLine(end);
delLine = [v; delLine(1:end-1)];
g = s;
if randint(1,1,2)==0,
g = -g;
end;
R=[R;g];
end;

Что то я перестал вас понимать...
"Лично мне от Вас был интересен только способ быстрого построения генератора с нормальным распределением".
Я показал вам генератор, в котором можно не то что разрядность чисел регулировать, а также(!) корреляционные свойства. Если вам нужны зависимые отчеты, пожалуйста, если нужны не зависимые, то тоже пожалуйста! Количество операций при этом константа и выгодно отличается от приведенных выше!

ps Уважаемый Олдриг, мне кажется, Вы либо перемудрствуете, либо Вам необходимо заново пройти курс обучения статистической теории. Не обижайтесь конечно, но создается такое впечатление.

psps только сейчас пришло в голову, может вам еще и код для сигнальника выложить? Говорите для какого? А может тогда вообще возьмете меня к себе на подработку? Сдается мне, что пока у нас в стране такие "спецы", долго еще будем после китая и кореи находиться

Нет, спасибо, код для сигнальника не нужен. Матлабовского скрипта достаточно.
Какие могут быть обиды? У меня, например, складывается впечатление, что Вы, пытаясь советовать коллегам алгоритмы генерации случайных чисел, не читали Кнута. Потому что пытаетесь порождать на лету методы генерации откровенно плохих случайных чисел. Может быть, Вам стоит с ознакомиться с этой классической книгой? Без обид?

Знаете, был когда-то такой популярный в СССР компьютер - ZX Spectrum. Если для него написать программу, в которой последовательно генерируемые числа рисовать в виде точек на экране - попарно X и Y координаты, то точки начинали вастраиваться в сетку линий. Такой тест - один из простейших критериев качества генератора случайных чисел, описанный в Кнуте. Называется критерием серий.

Для вашего генератора получается крест.

Нажмите для просмотра прикрепленного файла

Будет ли это крест на Вашем генераторе, или этот генератор можно будет использовать в конкретном алгоритме - зависит от алгоритма. Но обнаружить побочные эффекты будет, конечно, несколько сложнее. За счет некоторого замедления времени работы первоначального генератора.

Удивительно как вы неуклонно не хотите думать. Ведь все же уже разжевано до безобразия! Поймите, что именно мышление ведет к прогрессу и нельзя этой функции, данной нам свыше, допускать атрофироваться. Решение задачи можно сравнить с написанием картины - один, два штрижка и она превращается в шедевр. Но художник, опирается на внутренее чувство окружающего мира, а мы - на мышление(!).

Посмотрите этот алгоритм, и посчитайте количество операций, и если оно превысит, то смело бросьте в меня камень.

R=[];
s=0;
delLine = zeros(12,1);
mas=zeros(1,256);
for i=1:10000,
a = randint(1,1,256)+1;
v = a - 128;
s = s + v - delLine(end);
delLine = [v; delLine(1:end-1)];
g = mas(a);
mas(a) = s;
R=[R;g];
end;

ps меня удивило, что Вы, Олдрин, непонаслышке знакомы с синклером, думаю с радио-86рк тоже. Чувствуется старая закалка, не то, что нынешние студенты, которые живут с ожиданием, что все за них сделают...С Вами приятно общаться, но все же, настоятельно рекомендую вникать глубже в суть задач...есть у Вас такой небольшой порочек...

Постепенно переходим к криптографии?

Мышление не заменяет образование. Кнута Вы ведь так и не прочитали?

Да, Вы избавились от сильной связи между соседними отсчетами. С третьей попытки. Все равно, без тщательного анализа нельзя утверждать, что Ваш доморощенный алгоритм генерирует достаточно хорошие случайные числа. Критериев их качества ведь до фига. К сожалению, незнание недостатков обычно не устраняет сами недостатки.

P.S. РКшки у меня не было. Журналы Радио читал. Но тогда оставалось только завидовать друзьям. С Синклерами, действительно, знаком не понаслышке. Хорошая была школа.

Это не доморощенный алгоритм. Он подробно исследован и запатентован. Я собственно оттуда и узнал о нем. Автора не помню. Кстати, кто-то из соотечественников, Чикин, кажется...

Если алгоритм опубликован и подробно исследован рядом компетентных в вопросе исследователей - это, конечно, совершенно другое дело. Тогда ему можно до некоторой степени доверять. Конечно, после обнаружения первоисточника и проверки корректности реализации. Мелочи могут быть критичными.

Ну так ведь первые две Ваши реализации ведь были имменно доморощенными?

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

Согласен. Я сам столкнулся с необходимостью реализации быстрых алгоритмов генерации и наткнулся на этот алгоритм. По мере тестов (именно практических на сигналыче) получали различные модификации.

ps Кстати, Вы не смотрели матлабовский генератор? Уж слишком подозрительно граммотно он сделан. А алгоритмиками матлабовцы не хотят делиться, или я плохо искал... Что думаете?

Нет, не смотрел. Вопрос в общем-то детально меня не особо интересовал. Работает - и ладно, особо важные исследования с ним я не проводил.

Это поможет?

спасибо, посмотрим на досуге...

Макс_Мат, вы так и не ответили, каким образом предлагаемые вами методы реализуются за 4 такта на блекфине

А нужно ли это лично Вам? Если Вы до сих пор не видите как и не хотите учиться, то может Вам вообще покинуть сферу деятельности, связанную с электроникой и, в частности, с сигнальными процессорами?

ps обучают программированию на специальных курсах или в соседних разделах на форуме...

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

я одно время работал с очень талантливым человеком. И вот, частенько, он любил повторять, когда мы принимали на работу очередного студента: "если человек к 18 годам не стал профессиональным инженером, то он им не станет никогда".

Уважаемые участники, для есть отдельный раздел. Не отходите от темы!

Для автора, думаю, через полгода запоздалый ответ вряд ли будет полезен, но "для копилки" хочу привести ещё один генератор ПСП, до безобразия простой, легко настраиваемый на любую длину чисел и на любую длину неповторяющегося куска.

X_next = 5*(1 + X_prev)
Вычисления производятся по модулю 2 в степени k (k - любое целое число от 3 до бесконечности).
Этот генератор обладает ПОЛНЫМ периодом (то есть, цикл проходит через все k-битные числа, прежде чем возникнет повтор).
А главное - простота реализации на любом МК. Это проще, чем вычислять регистр с линейной обратной связью, особенно если в МК есть умножение.

Примеры:
Чтобы получить посл-сть 9-битных чисел с периодом 512, применяем вышенаписанную формулу при k=9
Чтобы получить посл-сть 9-битных чисел с периодом 2^24, то применяем вышенаписанную формулу при k=24 и берём СТАРШИЕ 9 бит от получающихся чисел.

Если кто-то усмотрит в этом генераторе некую автокорреляцию, ухудшающую свойства случайности, то есть такой выход (при наличии в МК быстрого умножения)
X_next = A * X_prev + B
где коэффициенты A и B - любые целые числа, такие что A даёт остаток 1 при делении на 4, а B - любое нечётное. Эти требования на A и B гарантируют полноту периода, то есть, все k-битные числа будут собраны в один цикл (при любом k).
Автокорреляция, имхо, может быть улучшена, если взять большие числа A и B (вариант A=B=5 в этом плане хуже, но зато он предпочтительнее для тех, кому придётся умножать сдвигами и сложениями)

Конечно, для криптографических целей этот генератор не подходит.