Преобразование Фурье бинарной последовательности

[misha89]

Добрый день.

Есть строка. Представим ее в виде двоичной последовательности длиной 1021 бит. Произведем преобразование Фурье, возьмем абсолютные значения и получим следующую гистограмму.

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

Вопрос: в чем физический смысл преобразования Фурье? Была двоичная последовательность, я ее разложил по частотам спектра по всей длине последовательности и что это дает? Например, что на позиции 30 в последовательности стоит "0", а у преобразования Фурье на позиции 30 - значение "65". Это значит, что чаще всего на этой позиции будет 0? С вероятностью 65%?

[Joe Black]

Симметрия видна, но вообще похоже на белый шум

[Евгений Машеров]

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

[misha89]

Евгений Машеров в сообщении #1132310 писал(а):

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

Но что дает эта частота относительно каждой позиции в последовательности?

например, можно посчитать частоту каждого байта в строке и тогда эта частота говорит нам о том, как часто встречается тот или иной символ. А тут что частота дает?

или о каких частотах идет речь?

Если со значения в каждой точке связи нет, тогда относительно всей последовательности что дает частота?

[svv]

misha89 в сообщении #1132304 писал(а):

Видна симметрия.

Эта симметрия — не следствие каких-то особых свойств данного сигнала, это общее свойство дискретного преобразования Фурье.

Допустим, Ваш сигнал — набор вещественных значений $u_m$, где $m=0..n-1$. Коэффициенты ДПФ можно вычислить по формулам:
$a_k=\frac 2 n \sum\limits_{m=0}^{n-1} u_m \cos \frac{2\pi m k}{n}\quad\quad b_k=\frac 2 n \sum\limits_{m=0}^{n-1} u_m \sin \frac{2\pi m k}{n}$
Тогда
$\begin{array}{l}a_{k+n}=a_k\\b_{k+n}=b_k\\a_{-k}=a_k\\b_{-k}=-b_k\end{array}$
Оно и понятно: если каждая гармоника представляется двумя числами, независимых гармоник будет вдвое меньше, чем отсчётов.

[misha89]

svv
Я с этим и не спорю. Это было просто описание гистограммы: симметрия, пики, пунктир.

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

[svv]

misha89 в сообщении #1132346 писал(а):

Как можно из этой частоты судить в дальнейшем о случайности, если не понимать смысла?

Амплитуды гармоник, полученные Вами — они для другого.

Не претендуя на строгость. Представьте, что у Вас на столе стоит набор камертонов: камертон единичной частоты (с периодом, равным длительности Вашего сигнала); двойной частоты (два колебания за то же время); тройной, и так далее.

Теперь Вы производите шум, описываемый Вашим сигналом — ну просто подаёте сигнал на колонки. Тогда Ваши коэффициенты покажут, насколько каждый из камертонов зарезонирует в ответ на этот сигнал. Иными словами, каков вклад именно такой частоты в Вашем сигнале (камертон откликается только на свою частоту).

[Евгений Машеров]

misha89 в сообщении #1132319 писал(а):

Но что дает эта частота относительно каждой позиции в последовательности?

например, можно посчитать частоту каждого байта в строке и тогда эта частота говорит нам о том, как часто встречается тот или иной символ. А тут что частота дает?

или о каких частотах идет речь?

Если со значения в каждой точке связи нет, тогда относительно всей последовательности что дает частота?

Ничего не даёт. Это не "частота встречаемости". Это частота синусоиды. Привязать её к конкретной точке нельзя. Низкая амплитуда на данной частоте говорит, что у нас нет закономерного изменения вероятности получения единицы, по крайней мере с периодом $T=\frac {2\pi} \omega=\frac 1 \nu$

[misha89]

svv
Евгений Машеров
Спасибо большое за ответы. Я осознал.

[Евгений Машеров]

Тут существенная деталь. Тест посредством Фурье на периодичность это обязательный этап тестирования равномерного ГСЧ, но проверяется не равномерность. А отсутствие закономерности. Можно получить идеально равномерно распределённую последовательность, просто беря последовательно 0 и 1. Но она не случайна, а повторяется с периодом 2. И Фурье проверяет не равномерность, а отсутствие легко выявляемой закономерности, колебаний постоянного периода. Хотя бы и невидимых простым глазом.