Фрактальный "белый" шум

[MeV]

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

Итак, последовательность создается следующим образом (способ не единственный, но самый наглядный):
1. Начинаем со строки 00 или 01.
2. Далее справа приписываем повтор имеющейся строки, певую половину которой инвертируем.
3. Повторям пункт 2 столько, сколько нам надо.

Демонстрация для начальной строки 00:
00
0010
00101110
0010111011011110
и т.д.

Демонстрация для начальной строки 01:
01
0111
01111011
0111101110001011
и т.д.

Получающаяся последовательность не потеряла фрактальных свойств, присущих Морсу-Туэ. Но не этим последовательность замечастельна.
А замечательна своим спектром.
Вот FFT спектр для последовательности 00:

А вот FFT для 01:


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

К сожалению, поиски в интернете описания данной последовательности не дали результата.
Что это за последовательность?

[MeV]

MeV в сообщении #1136854 писал(а):

Что это за последовательность?

Нашел. Есть такая последовательность A268411, соотвествующая случаю 01, описанному выше. Выложили ее совсем недавно.
Дает четность количества переходов из 0 в 1 в двоичном представлении числа. Это еще один вариант получения последовательности, который я знал.
Автор этой последовательности Владимир Шевелев. Но он получил эту последовательность для решения совсем других проблем и о спектральных свойствах вероятно даже и не подозревает.

[arseniiv]

Решил проверить в Mathematica 8 и получил какие-то совсем не такие спектры (от последовательности, конечно, сначала отнимал $1/2$). По крайней мере, если брать модули амплитуд. Если брать квадраты модулей, вещественные или мнимые части, точки уже более-менее равномерно заполняют график.

А, точно, насколько помню, обычно реализации FFT как раз выдают массив вещественных и мнимых частей амплитуд — у вас, видимо, тоже?

Более по теме: вы можете, в принципе, дополнить найденную статью в OEIS. Там зарегистрироваться нетрудно, и редакторы после просмотра изменения или допустят, или скажут, что уточнить/перефразировать. Видимо, в этом случае можно сформулировать какое-то утверждение о спектральной плотности, но я тут не специалист.

(Вообще, интересная последовательность, просто мне нечего добавить.)

[MeV]

arseniiv в сообщении #1137225 писал(а):

получил какие-то совсем не такие спектры

Возможно ошибка где-то у Вас.
На картинке у меня показаны спектральные амплитуды (не квадраты). Вот демонстрационный пример на MATLab (последовательность нормализована, 0 заменены на -1):
*************************************************
clear;
Size_power2 = 8; %Sequence length: 2^Size_power2

S=2;
FWN_seq(1)=-1; % The first element
FWN_seq(2)=1; % The second element

for i = 2 : Size_power2
FWN_seq(S+1:S+S/2)=-FWN_seq(1:S/2);
FWN_seq(S+S/2+1:2*S)=FWN_seq(S/2+1:S);
S=2*S;
end

plot(abs(fft(FWN_seq)));
*****************************************************

Вместо abs можно использовать: angle, real, imag для вывода аргумента, действительной или минимой частей. Равномерность заполнения графика от этого не зависит.

Спасибо за совет по OEIS. Попробую написать.
Ну и для поднятия интереса покажу как эта последовательность расширяется на 2D случай.

[arseniiv]

MeV в сообщении #1137249 писал(а):

Возможно ошибка где-то у Вас.

Первые куски последовательности совпадают с вашими.

MeV в сообщении #1137249 писал(а):

Вместо abs можно использовать: angle, real, imag для вывода аргумента, действительной или минимой частей. Равномерность заполнения графика от этого не зависит.

Да, для аргумента у меня тоже равномерно получается. Но вот графики начальной половины массива, выдаваемого Fourier в Mathematica, для 14-й итерации последовательности ($2\cdot 2^{14}$ чисел):
Модуль
Квадрат модуля
Аргумент
Re
Im
Модуль Re
Модуль Im

По виду последних двух можно судить, что даже действительные и мнимые части амплитуд спектра не очень-то равномерно распределяются по сравнению с аргументом или квадратом модуля (плотность больших по модулю значений не очень). Проблема с модулем без квадрата видна явно. Код для желающих проверить на ошибки — ниже:

(Код)

(* инверсия последовательности 0 и 1 *)
inverted[xs_] := Map[1 - # &, xs]

(* инверсия первой половины последовательности *)
withInvertedStart[xs_ /; EvenQ[Length[xs]]] :=
  With[{n = Length[xs]/2}, Join[inverted@Take[xs, n], Drop[xs, n]]]

a268411step[xs_] := Join[xs, withInvertedStart@xs]

(* Убедимся, что получается что-то нужное: *)
stringify[xs_] := StringJoin[ToString /@ xs]
stringify /@ NestList[a268411step, {0, 1}, 5] // Column
(* Должны вывестись последовательные первые куски последовательности *)
(* Конец убеждения *)

(* Графики: *)
(* Итерация *)
n = 14;

(* Последовательность *)
seq = Nest[a268411step, {0, 0}, n] - 1/2;

(* Фурье *)
fseq = Fourier[seq];
(* а теперь его почти первая половина (без амплитуды нулевой частоты, с амплитудой частоты Найквиста) *)
fseq = fseq[[2 ;; Length[fseq]/2 + 1]];

(* Для удобства рисования одинаковых графиков *)
L[e___] := ListPlot[e, Axes -> False, Frame -> True, PlotRange -> All, PlotStyle -> {PointSize[Tiny]}]
L2[f_] := L[f /@ fseq, PlotLabel -> f[z]]

(* Рисуем *)
L2[Abs]
L2[Abs[#]^2 &]
L2[Arg]
L2[Re]
L2[Abs[Re[#]] &]
L2[Im]
L2[Abs[Im[#]] &]

В упоминаемых там функциях я уверен.

-- Пн июл 11, 2016 20:58:19 --

Давайте лучше статистические показатели сравним. Сейчас дам среднее для модулей амплитуд.

-- Пн июл 11, 2016 21:07:54 --

Для модулей среднее $0{,}665759$, тогда как для квадратов модулей — $0{,}500027$, это всё если нормировать модули/квадраты модулей на $[0;1]$.

P. S. Ой, я тут сделал путаницу с порядком последовательности. Сейчас везде сделаю одинаковый. [Сделал. 14-я итерация последовательности, как выше.]

[MeV]

arseniiv в сообщении #1137271 писал(а):

По виду последних двух можно судить, что даже действительные и мнимые части амплитуд спектра не очень-то равномерно распределяются

Вы показали графики, и все стало ясно. Под равномерностью я имел в виду только равномерное распределение спектральной плотности по частотному диапазону (по области определения), но не по значению (по области значения). Это уже Вы обнаружили, что квадрат модуля распределен равномерно еще и по области значения. Я на это не обратил внимания (два глаза хорошо, а четыре лучше).
Ну вот такие свойства. Это же не настоящий белый шум.

arseniiv в сообщении #1137271 писал(а):

Давайте лучше статистические показатели сравним.

Среднее для модулей уменя получается 0.6666, для квадратов модулей - 0.5, что близко вашим данным. Отличия, я думаю, можно списать на ошибки округления.

[arseniiv]

MeV в сообщении #1137280 писал(а):

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

А. Тогда прекрасно.

[MeV]

Тут вот ведь какое дело получается.
Как я уже приводил выше картинку, последовательность расширяется на случай 2D. А вот как выглядит его 2D Фурье преобразование:


Аналогично 1D случаю, спектр относительно равномерно распределен по всему частотному диапазону.

Можно пойти дальше и расширить последовательность до 3D. Получим теоретическую основу для гипотетического метаматериала или квазикристалла. Обычно квазикристаллы демонстрируют оси симметрии (например 5-го порядка), запрещенные трансляционной симметрией. Однако эта детерминистическая структура с дальним порядком в рентгеновских лучах не даст вообще никакой ярко выраженной дифракционной картины. Она будет похожа на аморфное тело.

[Vince Diesel]

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

[MeV]

Vince Diesel в сообщении #1137406 писал(а):

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

Задачи смоделировать белый шум не стояло. Белый шум, например, хорошо производят MLS последовательности.
Задача стояла найти неслучайную, но непериодическую последовательность. Одна такая найденная последовательность привлекла внимание своими необычными спектральными свойствами. И как оказалось, эта последовательность имеет номер A268411.

Последовательность A268411 имеет инфрмационную энтропию 2 бита (практически нулевую) и крайне небольшую алгоритмическую сложность. Для криптографии не имеет никакого интереса.
Зато может использоваться для создания метаматериалов. Например, можно методом оттиска формировать матовые поверхности.