реклама на сайте
подробности

 
 
 
Reply to this topicStart new topic
> Синтез гауссовского шума, Эффективный алгоритм синтеза псевдослучайной последовательности с норм
Pathfinder
сообщение Apr 24 2006, 14:16
Сообщение #1


Местный
***

Группа: Свой
Сообщений: 275
Регистрация: 29-06-05
Пользователь №: 6 400



Кто-нибудь знает где взять эффективный алгоритм синтеза гауссовского шума в целочисленной арифметике? решение в лоб (2 рекуррентные последовательности максимальной длины+нелин. преобразования) требует вычисления функции sqrt(-ln(1-x)), а считается она очень медленно - для получения 16-битного корня требуется 16 операций деленья, и еще одна для вычисления логарифма. Может есть какие-то быстрые итеративные алгоритмы? Сразу уточню, период последовательности должен быть очень большим.


--------------------
ADC / DAC LC Filter Designer — Удобный инструмент проектирования LC-фильтров для ЦАП и АЦП
Go to the top of the page
 
+Quote Post
Pavel_I
сообщение Apr 24 2006, 14:24
Сообщение #2


Частый гость
**

Группа: Свой
Сообщений: 179
Регистрация: 27-06-05
Из: Москва
Пользователь №: 6 325



Получить процесс с распределением приближающимся к гауссовскому можно путем суммирования
отсчетов равномерно-распределенного процесса. Т.е. один отсчет формируемого процесса получаем
путем суммирования нескольких отсчетов равномерного процесса. Чем больше суммируем - тем лучше
приближение.
Go to the top of the page
 
+Quote Post
SavSerG
сообщение Apr 24 2006, 16:10
Сообщение #3





Группа: Новичок
Сообщений: 11
Регистрация: 25-07-05
Пользователь №: 7 070



Вот алгоритм на основе суммы 20 равномерно распределенных чисел,
нелинейное преобразование для того, чтобы "хвосты" распределения
моделировались точнее. Уже при 12 числах нормальная гауссовская последовательность получается.
При сумме 12 чисел не надо вычислять корень, т.к. он равен 1.
long double gen()
{
long double x=0.0;
for(int i=0;i<20;i++){
x+=(double(rand())/double(RAND_MAX)-0.5);
};
x*=sqrtl(0.6); //sqrtl(12.0/N=20)
x+=0.01*x*(x*x-3.0);
return x;
}
Можно почитать книгу Numirical receipes on C там были алгоритмы генерирования
гауссовского шума
Go to the top of the page
 
+Quote Post
Stanislav
сообщение Apr 24 2006, 17:58
Сообщение #4


Гуру
******

Группа: Свой
Сообщений: 4 363
Регистрация: 13-05-05
Из: Москва
Пользователь №: 4 987



Чисто практическое дополнение.
Для получения "хорошего" распределения Гаусса достаточно сложить 4-5 равномерно распределённых чисел. Ошибка распределения при этом составит ничтожно малую величину, которая, скорее всего, не будет иметь практического значения.
Иными словами, эффективность вычисления случайной величины, распределённой по Гауссу, определяется эффективностью алгоритма подсчёта равномерно распределённого числа. Дабы избавиться от сложного масштабирования, следует принять во внимание, что эффективная амплитуда равномерно распределённого в интервале [-1 ; 1] случайного процесса равна, если склероз не изменяет, sqrt(1/3).
PS. Блин, опять форум глючит...


--------------------
Самонадеянность слепа. Сомнения - спутник разума. (с)
Go to the top of the page
 
+Quote Post
gab
сообщение Apr 25 2006, 10:32
Сообщение #5


Местный
***

Группа: Свой
Сообщений: 376
Регистрация: 30-06-04
Из: Moskow
Пользователь №: 218



Цитата(Pathfinder @ Apr 24 2006, 18:16) *
Кто-нибудь знает где взять эффективный алгоритм синтеза гауссовского шума в целочисленной арифметике? решение в лоб (2 рекуррентные последовательности максимальной длины+нелин. преобразования) требует вычисления функции sqrt(-ln(1-x)), а считается она очень медленно - для получения 16-битного корня требуется 16 операций деленья, и еще одна для вычисления логарифма. Может есть какие-то быстрые итеративные алгоритмы? Сразу уточню, период последовательности должен быть очень большим.

Я делал на ПЛИС по методике изложенной в статье. Работало на 64МГц.Прикрепленный файл  tc05_dul98.pdf ( 486.46 килобайт ) Кол-во скачиваний: 565


--------------------
serpents on the way to paradise -
dying for love, fighting for ages.

Go to the top of the page
 
+Quote Post
SavSerG
сообщение Apr 25 2006, 19:21
Сообщение #6





Группа: Новичок
Сообщений: 11
Регистрация: 25-07-05
Пользователь №: 7 070



Цитата(Stanislav @ Apr 24 2006, 21:58) *
Чисто практическое дополнение.
Для получения "хорошего" распределения Гаусса достаточно сложить 4-5 равномерно распределённых чисел. Ошибка распределения при этом составит ничтожно малую величину, которая, скорее всего, не будет иметь практического значения.

У каждого понятие о "хорошем" распределении свое. Мне при моделировании суммы 20 равномернораспределенных чисел хватало с натяжкой. Потом от суммирования отказался и выбрал алгоритм посложнее. Когда надо
моделировать вероятность аномальных ошибок при оценивании рассеяния неизвестного параметра,
а она на уровне 10^-7 начинаешь искать датчик гауссовского шума с "очень хорошими" хвостами smile.gif

Сообщение отредактировал SavSerG - Apr 25 2006, 19:24
Go to the top of the page
 
+Quote Post
Stanislav
сообщение Apr 25 2006, 20:44
Сообщение #7


Гуру
******

Группа: Свой
Сообщений: 4 363
Регистрация: 13-05-05
Из: Москва
Пользователь №: 4 987



Цитата(SavSerG @ Apr 25 2006, 23:21) *
У каждого понятие о "хорошем" распределении свое. Мне при моделировании суммы 20 равномернораспределенных чисел хватало с натяжкой. Потом от суммирования отказался и выбрал алгоритм посложнее. Когда надо
моделировать вероятность аномальных ошибок при оценивании рассеяния неизвестного параметра,
а она на уровне 10^-7 начинаешь искать датчик гауссовского шума с "очень хорошими" хвостами smile.gif
Ни в коем случае не буду возражать против этого (хотя, Вы явно ошиблись в порядке). Для моделирования, конечно, может потребоваться ещё бОльшая точность. smile.gif Однако, с практической точки зрения, для большинства измерительных задач такая точность является излишней (существуют и другие факторы, не вписывающиеся в рамки формальной модели и имеющие влияние гораздо бОльшее, нежели "негауссовость" процесса).
ЗЫ. Не могли бы Вы привести более эффективный метод получения гауссова процесса?


--------------------
Самонадеянность слепа. Сомнения - спутник разума. (с)
Go to the top of the page
 
+Quote Post
Pathfinder
сообщение Apr 26 2006, 12:13
Сообщение #8


Местный
***

Группа: Свой
Сообщений: 275
Регистрация: 29-06-05
Пользователь №: 6 400



Спасибо за ответы, но хотел бы сделать несколько уточнений:
Цитата
У каждого понятие о "хорошем" распределении свое.

Есть объективные численные критерии - период последовательности, хи квадрат, критерий Андерсена-Дарлинга, Колмогорова-Смирнова и др.
С суммированием и центральной предельной теоремой все понятно, только тут куча недостатков есть:
1. Нужен многопоточный генератор равномерного распределения - следовательно еще придется алгоритм вычисления начальных условий для него реализовать
2. Период формируемой последовательности уменьшится пропорционально числу суммируемых потоков, чего очень не хочется - желательно уложиться в 32 бита и получить период порядка 10^9-10^10
3. Число суммируемых потоков - боюсь, 20 все же с трудом хватит...
4. Суммируемые числа надо сгенерить, потом их просуммировать и отнормировать (тут еще небольшая потеря точности). При числе потоков порядка 10 на сигнальном проце все удовольствие займет порядка 40 инструкций на одну выборку - многовато huh.gif

2 gab, спасибо за ссылку, еще нашел несколько статей этих же авторов. Похоже, предложенный ими метод наиболее эффективен.


--------------------
ADC / DAC LC Filter Designer — Удобный инструмент проектирования LC-фильтров для ЦАП и АЦП
Go to the top of the page
 
+Quote Post
gab
сообщение Apr 26 2006, 16:10
Сообщение #9


Местный
***

Группа: Свой
Сообщений: 376
Регистрация: 30-06-04
Из: Moskow
Пользователь №: 218



Цитата(Pathfinder @ Apr 26 2006, 16:13) *
2 gab, спасибо за ссылку, еще нашел несколько статей этих же авторов. Похоже, предложенный ими метод наиболее эффективен.

Я проверял его diehard'ом. Всё нормально. Мы его использовали для хардварного моделирования AWGN канала при передаче данных. Единственная моя модификация - увеличенный размер генераторов с равномерным распределением, т.к. мы считали BER и аппаратура работала около недели smile.gif.


--------------------
serpents on the way to paradise -
dying for love, fighting for ages.

Go to the top of the page
 
+Quote Post

Reply to this topicStart new topic
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 


RSS Текстовая версия Сейчас: 12th July 2025 - 07:43
Рейтинг@Mail.ru


Страница сгенерированна за 0.01447 секунд с 7
ELECTRONIX ©2004-2016