8-разрядный генератор псевдослучайных величин

[Anton_DM]

Здравствуйте!

Есть задачка. Очень смутно представляю ее решение из-за недостатка знаний по данному предмету, поэтому прошу помощи у имеющих опыт в этой области.
Построить 8-и разрядный генератор равновероятных С.В. . Базовый регистр 15-и разрядный. Интервалы повторения

\[X_i \]

генератора не менее 500. Определить

\[R(\tau )\]

чисел X для

\[\tau \in [1,5]\]

.

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

Нас так учили.
D - оператор задержки на один такт
тогда некоторый 8-и разрядный генератор можно представить например так

\[ X = D^8 X + 1 + D^2 X + DX \]

это некий 8-и разрядный генератор с инверсией
и период его самого 8-и разрядного будет

\[ L = 2^n - 1 \]

то есть 256, а не 500.
Наверно можно удлинить n и сделать его например n=9 тогда наверно было бы все нормально
и даже не важно что будет он 9 разрядным и тогда период будет даже больше L = 512. Или я ошибаюсь.
А что на счет базового? Это что такое? А как его использовать или он так чтобы пыль в глаза пустить?
Если у вас есть опыт в подобных вопросах пожалуйста просветите.

Добавлено спустя 2 минуты 18 секунд:

Буду так же рад ссылкам на аналогичные темы и литературу.

Добавлено спустя 52 минуты 2 секунды:

Еще вариант
можно взять 15 регистров и генерировать на них случайные величины по какой -либо схеме. А потом взять и собирать значения регистров черз один. Если этот вариант правильный то помогите сосчитать период такого генератора и его корелляцию R на отрезке [1,5].

[Anton_DM]

Ну хоть кто - нибудь!!!!!!
Можете хоть оставить сообщение . Напишите что-нибудь. Что никто ничего не знает по этой теме?

[Brukvalub]

Не могу пройти мимо отчаянного крика о помощи, хотя генераторами случайных чисел я не занимаюсь.
1.Вот статья из Википедии со списком литературы: http://ru.wikipedia.org/wiki/%D0%93%D0%A1%D0%A7
2.Мне встречалось описание генераторов случайных чисел в знаменитом трёхтомнике:
Кнут Д.Э. — Искусство программирования (Том 1. Основные алгоритмы)
Кнут Д.Э. — Искусство программирования (Том 2. Получисленные алгоритмы)
Кнут Д.Э. — Искуcство программирования (Том 3. Сортировка и поиск)
а в каком именно томе - не помню, но, кажется, в первом. Ну, не стоит брезговать и информационным мусором из поисковиков, в нём тоже стоит порыться. Большим помочь не в состоянии.

[Someone]

Brukvalub писал(а):

а в каком именно томе - не помню

Во втором.

[Anton_DM]

К сожалению того что нужно у Кнута нет. Да и приводимые там схемы дают порядочную корелляцию. В инете искал, но увы. Тем не менее спасибо. Очень неприятно, когда топик просто тонет и его проходят мимо.

[Someone]

Anton_DM писал(а):

Да и приводимые там схемы дают порядочную корелляцию.

А чего Вы хотите от восьмиразрядного генератора?

[Anton_DM]

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

[Someone]

Anton_DM писал(а):

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

Восьмиразрядный генератор имеет не более 256 состояний. А период не превосходит числа состояний.

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

Anton_DM писал(а):

Базовый регистр 15-и разрядный.

Но 15-разрядный регистр даёт период не более 32768, что тоже очень мало.

Вы можете на основе этого регистра сделать свой генератор, а на выход выдавать только требуемые 8 разрядов.

[Anton_DM]

Someone писал(а):

Anton_DM писал(а):

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

Восьмиразрядный генератор имеет не более 256 состояний. А период не превосходит числа состояний.

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

Anton_DM писал(а):

Базовый регистр 15-и разрядный.

Но 15-разрядный регистр даёт период не более 32768, что тоже очень мало.

Вы можете на основе этого регистра сделать свой генератор, а на выход выдавать только требуемые 8 разрядов.

Об этом я писал выше.

Цитата:

Еще вариант
можно взять 15 регистров и генерировать на них случайные величины по какой -либо схеме. А потом взять и собирать значения регистров черз один. Если этот вариант правильный то помогите сосчитать период такого генератора и его корелляцию R на отрезке [1,5].

Больше эта проблема передо мной не стоит.
Это ясно я себе уяснил. Этот вариант предложила подруга. Сначала я думал взять 15 разр генератор и брать от него младшие 8 разр что привело бы к , я думаю, огромной корелляции, может быть даже это была бы линейная зависимость и никаких сл чисел я бы не получил.

Теперь у меня вопрост такой. Если я буду по предложенной схеме брать через один разряд, начиная с первого, то какой у меня период будет? По идее каждый разряд будет повторяться через период L=32768. Значит и в 8 разрядного числа будет этот период или я ошибаюсь?
И как посчитать R($\tau$) на отрезке [1,5]?

[Someone]

Anton_DM писал(а):

Сначала я думал взять 15 разр генератор и брать от него младшие 8 разр что привело бы к , я думаю, огромной корелляции, может быть даже это была бы линейная зависимость и никаких сл чисел я бы не получил.

Теперь у меня вопрост такой. Если я буду по предложенной схеме брать через один разряд, начиная с первого, то какой у меня период будет? По идее каждый разряд будет повторяться через период L=32768. Значит и в 8 разрядного числа будет этот период или я ошибаюсь?
И как посчитать R($\tau$) на отрезке [1,5]?

Вопросы, на которые нет ответа без информации о генераторе. Вы можете привести точный алгоритм Вашего генератора?

Например, для генератора $x_{k+1}=(ax_k+c)\pmod{m}$ с максимальным периодом $m$ следует брать не младшие, а старшие разряды. Если Вы сделали такой генератор на базе 15-разрядного регистра, то берите 8 старших бит, брать через один будет хуже. Для других генераторов ситуация может быть другой.

[lofar]

Не вполне понял условия задачи. Поясните, пожалуйста, используемую терминологию. Что можно использовать? Что нужно получить? Что нужно посчитать?

Насколько я понял, главным действующим лицом является линейный регистр сдвига (ЛРС). Приведу ряд предложений о ЛРС, возможно, они будут Вам полезны.

1) ЛРС определяется длиной $n$ и характеристическим полиномом $f(x)=x^n-a_{n-1}x^{n-1}-\ldots-a_0\in\mathbb Z_2[x]$. Если в момент времени $t$ регистр имеет заполнение $U(t)=(u_{n-1}(t),\ldots,u_0(t))$, то в следующий момент его заполнение определяется соотношением $U(t+1)= (a_{n-1}u_{n-1}(t)+\ldots+a_0u_0, u_{n-1}(t),\ldots, u_1(t))$. То есть, за 1 такт регистр смещается вправо на 1 элемент, позиция с номером $0$ выходит из регистра (вытесняется), позиция с номером $n-1$ освобождается и туда записывается комбинация элементов регистра с коэффициентами характеристического полинома.

2) Фиксировав ячейку ЛРС с номером $k$ получаем двоичную последовательность по времени: $u_k(t)$, $t=1,2,\ldots$ Эта последовательность периодическая с периодом $T_k$. Причем $T_k\le 2^n-1$.

3) Равенство $T_k = 2^n-1$ достигается если и только если характеристический полином $f(x)$ неприводим над $\mathbb Z_2$ и его корень $\alpha$ в поле разложения $GF(2^n)$ является примитивным (порождает мультипликативную группу поля $GF(2^n)$). Имеются таблицы таких полиномов (они называются полиномами максимального периода или примитивными полиномами).

4) Если $u_k(t)$ является последовательностью максимального периода ($T_k = 2^n-1$), то таковы и все остальные последовательности $u_0(t), u_1(t),\ldots,u_{n-1}(t)$. Значит, в частности, период любой вектор-последовательности вида $V(t)=(u_{k_0}(t),\ldots, u_{k_m}(t))$ (выборка из исходного ЛРС) равен $2^n-1$.

5) Если $u_k(t)$ --- последовательность максимального периода, то мультиграммы в ней распределены равномерно на периоде: всякий ненулевой двоичный набор длины $r\leqslant n$ встречается на периоде ровно $2^{n-r}$ раз (нулевой набор встречается $2^{n-r}-1$ раз).

6) Если $u_k(t)$ --- последовательность максимального периода, то $u_k(2^st)$ также последовательность максимального периода, причем определяемая тем же характеристическим полиномом. Поэтому сплошная выборка и выборка "через один" ("через четыре", "через восемь",...) равноправны.

[Anton_DM]

Уважаемый lafar!
Я был бы очень очень признателен если бы вы поделились списком литературы. Вижу что в этом вопросе вы разбираетесь. Нам в универе немного не в такой форме все это давалось. таких уравнений (уравний в общем виде) мы не писали. Нам больше в схемах все это давалось. Так же нас научили записывать характеристические уравнения для этих схем, пояснили некоторые тонкости и на этом мы закончили. Если есть возможность я бы даже просил прислать эту литературу мне в почтовый ящик на адрес [e-mail] .
А если бы я мог быть еще больше просить, то просил бы у вас помощи в решении именно этой задачи.
С уважением Антон.

[Someone]

lofar писал(а):

4) Если $u_k(t)$ является последовательностью максимального периода ($T_k = 2^n-1$), то таковы и все остальные последовательности $u_0(t), u_1(t),\ldots,u_{n-1}(t)$. Значит, в частности, период любой вектор-последовательности вида $V(t)=(u_{k_0}(t),\ldots, u_{k_m}(t))$ (выборка из исходного ЛРС) равен $2^n-1$.

Д.Кнут. Искусство программирования для ЭВМ. Том 2. Получисленные алгоритмы. "Мир", Москва, 1977.

3.2.2. Другие методы.

Цитата:

Предупреждение: Некоторые попадались в ловушку, пытаясь использовать метод выработки случайных последовательностей битов для получения случайных дробей, занимающих целое слово $(.Y_0Y_1\dots Y_{k-1})_2,(.Y_kY_{k+1}\dots Y_{2k-1})_2,\dots$. На самом деле это довольно плохой способ, хотя отдельные биты каждой дроби вполне случайны (см. упр. 18)!