2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

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

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



Начать новую тему Ответить на тему
 
 8-разрядный генератор псевдослучайных величин
Сообщение15.01.2007, 10:32 


01/02/06
16
Здравствуйте!

Есть задачка. Очень смутно представляю ее решение из-за недостатка знаний по данному предмету, поэтому прошу помощи у имеющих опыт в этой области.
Построить 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].

 Профиль  
                  
 
 
Сообщение15.01.2007, 19:11 


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

 Профиль  
                  
 
 
Сообщение15.01.2007, 22:38 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение15.01.2007, 22:40 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
Brukvalub писал(а):
а в каком именно томе - не помню


Во втором.

 Профиль  
                  
 
 
Сообщение16.01.2007, 00:31 


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

 Профиль  
                  
 
 
Сообщение16.01.2007, 19:02 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
Anton_DM писал(а):
Да и приводимые там схемы дают порядочную корелляцию.


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

 Профиль  
                  
 
 
Сообщение17.01.2007, 22:35 


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

 Профиль  
                  
 
 
Сообщение18.01.2007, 00:43 
Заслуженный участник
Аватара пользователя


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


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

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

Anton_DM писал(а):
Базовый регистр 15-и разрядный.


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

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

 Профиль  
                  
 
 
Сообщение18.01.2007, 09:43 


01/02/06
16
Someone писал(а):
Anton_DM писал(а):
Я вообще от него ничего не хочу. Мне просто нужно сдать эту работу. А вообще какой бы разрядности не был генератор в пределах разумного, есть разные алгоритмы и на разных схемах она бывает разная. А на приведенных Кнутом схеме она будет большой. Можно использовать др. схемы. Главное здесь корелляция дб максимально уменьшена. Она будет маленькой если период будет достаточно большим.


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

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

Anton_DM писал(а):
Базовый регистр 15-и разрядный.


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

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

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

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

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

 Профиль  
                  
 
 
Сообщение18.01.2007, 15:57 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
Anton_DM писал(а):
Сначала я думал взять 15 разр генератор и брать от него младшие 8 разр что привело бы к , я думаю, огромной корелляции, может быть даже это была бы линейная зависимость и никаких сл чисел я бы не получил.

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


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

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

 Профиль  
                  
 
 
Сообщение19.01.2007, 01:21 
Заслуженный участник
Аватара пользователя


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

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

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)$ также последовательность максимального периода, причем определяемая тем же характеристическим полиномом. Поэтому сплошная выборка и выборка "через один" ("через четыре", "через восемь",...) равноправны.

 Профиль  
                  
 
 
Сообщение22.01.2007, 15:23 


01/02/06
16
Уважаемый lafar!
Я был бы очень очень признателен если бы вы поделились списком литературы. Вижу что в этом вопросе вы разбираетесь. Нам в универе немного не в такой форме все это давалось. таких уравнений (уравний в общем виде) мы не писали. Нам больше в схемах все это давалось. Так же нас научили записывать характеристические уравнения для этих схем, пояснили некоторые тонкости и на этом мы закончили. Если есть возможность я бы даже просил прислать эту литературу мне в почтовый ящик на адрес antonfunticdol@yanex.ru .
А если бы я мог быть еще больше просить, то просил бы у вас помощи в решении именно этой задачи.
С уважением Антон.

 Профиль  
                  
 
 
Сообщение22.01.2007, 20:11 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
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)!

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 13 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group