[Dot 0]

Я тут микроконтроллером генерирую случайные последовательности.

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

 

На текущий момент мне представляется один критерий -- гладкость фурье-спектра.

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

 

Спектр полученного сигнала -- в приложении. F -- частота сэмплироания (битов).

Есть пики, с этим не поспоришь. Но они пропадают, если последовательность дополнительно пропустить через тот же регистр с обр. связями.

[_artem_ 0]

http://csrc.nist.gov/rng/rng9.html

[acex2 0]

Я тут микроконтроллером генерирую случайные последовательности.

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

 

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

[Dot 0]

Спасибо.

Нашел безответный топик одной девушки

http://forums.software-testing.ru/index.php?showtopic=3896

В нем много интересных ссылок.

 

Как я понял случайность не доказуема. Проверяется только отсутствие той или иной случайности.

[Krys 2]

Именно так. Ничего случайного не бывает. Любой генератор случайных чисел даёт приблизительно случайные числа. Есть даже в умных книжках (не готов, правда, привести библиографическую ссылку - далеко книжка, но когда-то читал) понятие "интервал корреляции", если не ошибаюсь. Он означает количество "достаточно случайных" чисел, которые выдаёт генератор. Если это количество превысить, то числа уже точно будут повторяться и перестанут даже приблизительно быть случайными.

Так что весь вопрос лишь в требуемом интервале корреляции.

[Alex2172 0]

Ваш генератор - хаотическая система.

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

Корреляционную размерность K=2 дает простейший класический генератор (формулу не помню).

Субъективно считаю что при K>6..8 уже сложно проверить чем сформирована "случайная последовательность" - хаотической системой, созданной человеком, или богом - ибо для проверки понадобиться "очень много оперативки и производительности вычислителя"

[bve 1]

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

[Pathfinder 0]

Микроконтроллер, и др. микропроцессорная система - конечный автомат, он может генерировать не случайную, а псевдослучайную последовательность (ПСП) с очень большим периодом, поскольку сам по себе является системой детерминированной. В зависимости от задачи, требования к последовательности (к статистическим и частотно-временным параметрам) могут быть разные. По поводу генераторов ПСП и критериев их "качества" много и доступно написано в книжке Аверилл М. Лоу и Дэвида Кельтона "Имитационное моделирование".

Изменено 1 марта, 2006 пользователем Pathfinder

[Silent Observer 0]

Чтобы доказать, что данный процесс является случайным, надо расчитать и построить автокорреляционную функцию. Случайная величина не коррелируется сама с собой и коэффициент корреляции равен нулю. В идеале автокорреляционная функция должна быть похожа на дельта-функцию.

Изменено 2 марта, 2006 пользователем Silent Observer

[Pathfinder 0]

Автокорреляционная функция (АКФ) характеризует лишь частотно-временные свойства и не более того. АКФ является дельта-функцией только для БЕЛОГО шума. Если пропустить белый шум через фильтр, он не станет от этого менее "случайным", хотя корреляционная функция при этом изменится. Вообще "случайность" это противоположность детерминированности, и вопрос постановки задачи. Даже синус для нас является случайным если мы не знаем заранее что будет получен именно он.

[Tanya 4]

Микроконтроллер, и др. микропроцессорная система - конечный автомат, он может генерировать не случайную, а псевдослучайную последовательность (ПСП) с очень большим периодом, поскольку сам по себе является системой детерминированной. В зависимости от задачи, требования к последовательности (к статистическим и частотно-временным параметрам) могут быть разные. По поводу генераторов ПСП и критериев их "качества" много и доступно написано в книжке Аверилл М. Лоу и Дэвида Кельтона "Имитационное моделирование".

А вот если этому конечному автомату дать вычислять Пи (3.14....) или корень из двух, то что (по Вашему) получится периодическая дробь? Да, последовательность цифр будет детерминирована, но вполне подойдет в качестве псевдослучайной.

[Tanya 4]

Микроконтроллер, и др. микропроцессорная система - конечный автомат, он может генерировать не случайную, а псевдослучайную последовательность (ПСП) с очень большим периодом, поскольку сам по себе является системой детерминированной. В зависимости от задачи, требования к последовательности (к статистическим и частотно-временным параметрам) могут быть разные. По поводу генераторов ПСП и критериев их "качества" много и доступно написано в книжке Аверилл М. Лоу и Дэвида Кельтона "Имитационное моделирование".

А вот если этому конечному автомату дать вычислять Пи (3.14....) или корень из двух, то что (по Вашему) получится периодическая дробь? Да, последовательность цифр будет детерминирована, но вполне подойдет в качестве псевдослучайной.

Это была провокационная шутка. Извините. Странно, что никто не прореагировал.

[Silent Observer 0]

Если пропустить белый шум через фильтр, он не станет от этого менее "случайным", хотя корреляционная функция при этом изменится.

 

Пропустив случайный процесс через фильтр, вы ограничите спектр этого процесса, а это уже элемент детерминированности. Спектр случайного процесса также должен быть случайным.

[Pathfinder 0]

Пропустив случайный процесс через фильтр, вы ограничите спектр этого процесса, а это уже элемент детерминированности. Спектр случайного процесса также должен быть случайным.

Так. Уважаемый Silent Observer, срочно открываем любой учебник по стат. радиофизике, или просто по статистике, и читаем что такое случайный процесс и какие у него есть характеристики, а также связь между ними. Если надо, могу в электронном виде прислать.

Случайность и детерминизм меряются относительно задачи - если мы не знаем какой сигнал будет принят - то он случайный. Любое невырожденное преобразование этого случайного процесса (линейное/нелинейное, с памятью/без памяти) не делает его детерминированным, даже если мы знаем как при этом изменятся его характеристики.

Что касается спектра - тут Вы сами себе противоречите - АКФ в виде дельта-функции соответствует спектр белого шума - абсолютно детерминированный спектр.

[sK0T 0]

А чем не подходит шум зенера или иного теплового процесса? Что значит «абсолютно случайный»? Изначально некорректный вопрос, на мой вкус.