Загадочная функция БПФ (быстрое преобразование Фурье)

[dar3dev1l26]

Дело такое: Есть массив (назовем его M) длинной в 2^n типа short (2^16-битное целое) и функция БПФ. К массиву нужно применить БПФ, рассчитать фазы и амплитуды, заменить изначальный массив фаз на свой той же длинны, к старому массиву амплитуд и новому массиву фаз применить обратное БПФ - таким образом получаю модифицированный массив M*.
Если применить БПФ к М* и высчитать опять массив фаз, то должны получить мой закодированный массив фаз. Этот алгоритм работает, если массив М сгенерирован генератором случайных чисел с нормальным распределением. Если же массив не имеет нормального распределения (например я беру аудиоданные из wav файла), то восстановить информацию порой не получается, я не понимаю почему. Массив модифицированных фаз при этом один и тот же, разница лишь во входном массиве. Вот примеры попыток расшифровки массива модифицированных фаз (был закодирован символ " " - пробел, в двоичном формате 0010 0000):
==== из изначального массива, сгенерированного ГСЧ ====
-0.7854
-0.7854
0.7854
-0.7854
-0.7854
-0.7854
-0.7854
-0.7854
==== из массива, полученного при чтении wav-файла ====
-0.8709
-0.98058
1.07577
-0.69928
-0.73493
-0.74573
-0.76778
-0.83528
В данном случае пробел можно расшифровать, но бывает и такое:
-0.66045
0.62518 <-- ошибка
0.73987
-0.76039
-0.8683
-0.44188
-0.98273
-0.81388
или такое:
-0.5655
-0.68585
0.67254
-0.83685
-0.44762
2.36923 <-- ошибка
-0.68966
-1.58843
Кто разбирается помогите, почему тот же самый алгоритм с тем же маччивом модифицированных фаз работает хорошо со сгенерированным массивом и плохо( с ошибками) на произвольном массиве из аудиофайла?
Иногда везет и массив из аудио файла подходит, тогда ошибок нет. Но чаще он не подходит.

[dar3dev1l26]

Вот пример полного цикла:
=== Начальный массив (256 эл.) преобразованный в комплексные числа(взят из аудио файла, добавлена нулевая мнимая часть)===
0) Complex: (586, 0)
1) Complex: (301, 0)
2) Complex: (-351, 0)
3) Complex: (-387, 0)
...
252) Complex: (73, 0)
253) Complex: (41, 0)
254) Complex: (143, 0)
255) Complex: (334, 0)
=== Применение БПФ к нач. массиву ===
0) Complex: (-19365, 0)
1) Complex: (-13746.3973246366, 44795.1395624838)
2) Complex: (-25806.5526660665, 5665.97772386251)
3) Complex: (-892.533070457502, 7080.52455888832)
...
126) Complex: (20.8004709236866, -1.08753431714649)
127) Complex: (24.4207511861778, -0.474174015409517)
128) Complex: (25, 0)
129) Complex: (24.4207511861787, 0.474174015405879)
130) Complex: (20.8004709236848, 1.08753431714558)
...
252) Complex: (6517.55203141132, -6601.97414531479)
253) Complex: (-892.533070457501, -7080.52455888832)
254) Complex: (-25806.5526660665, -5665.97772386252)
255) Complex: (-13746.3973246365, -44795.1395624838)
=== находим массив амплитуд ===
0) 19365
1) 46856.88816
2) 26421.23131
3) 7136.55682
...
126) 20.82888
127) 24.42535
128) 25
129) 24.42535
130) 20.82888
...
252) 9277.09799
253) 7136.55682
254) 26421.23131
255) 46856.88816
=== находим массив фаз (в данном случае его искать не обязательно, всё равно замениять полностью, но мне это нужно для синхронизации фаз в wav файле, в прочем к делу отношения не имеет) ===
0) 3.14159
1) 1.86855
2) 2.92547
3) 1.69619
...
126) -0.05224
127) -0.01941
128) 0
129) 0.01941
130) 0.05224
...
252) -0.79183
253) -1.69619
254) -2.92547
255) -1.86855
=== заменяем вышестоящий массив фаз на этот массив фаз===
0) 0
1) 0
...
62) 0
63) 0
64) -1.5708
65) -1.5708
.. данные в виде +1.5708 или -1.5708..
126) -1.5708
127) -1.5708
128) 0
..
255) 0
=== Применяем обратное БПФ ===
0) Complex: (19365, 0)
1) Complex: (46856.8881577637, 0)
2) Complex: (26421.2313125973, 0)
3) Complex: (7136.55682460954, 0)
...
126) Complex: (1.27535905637866E-15, -20.8288819080166)
127) Complex: (1.4955721995132E-15, -24.425354234772)
128) Complex: (25, 0)
129) Complex: (24.4253542347728, 0)
130) Complex: (20.8288819080148, 0)
...
252) Complex: (9277.09798900275, 0)
253) Complex: (7136.55682460954, 0)
254) Complex: (26421.2313125973, 0)
255) Complex: (46856.8881577637, 0)
== Теперь сохраняем этот массив, отбрасывая мнимую часть как целый (short), потом опять БПФ применяем, опять находим массив фаз и получаем это (показываю сразу с позиции, куда я прятал информацию) ==
64) -0.78669
65) -0.78456
66) 0.78458
67) 0.77989
...
120) -0.46825
121) -0.70609
122) 0.89321 <--ошибка
123) 0.89081
124) 0.8436 <--ошибка
125) -0.90599
126) -0.71034
127) -0.67747
Кодировалось сообщение 12345678 - результат 1234567 (заместь 0001 000 - 0011 1000).
Сейчас напишу пример с использованием массива, сгенерированного ГСЧ.

[dar3dev1l26]

=== Начальный массив (256 эл.) преобразованный в комплексные числа(сгенерированный ГСЧ в диапазоне типа short с нормальным распределением, добавлена нулевая мнимая часть)===
0) Complex: (7608, 0)
1) Complex: (6149, 0)
2) Complex: (4411, 0)
3) Complex: (9032, 0)
...
252) Complex: (-26361, 0)
253) Complex: (-11528, 0)
254) Complex: (-30730, 0)
255) Complex: (9459, 0)
=== Применение БПФ к нач. массиву ===
0) Complex: (-266723, 0)
1) Complex: (-205584.142144339, -59076.3053166473)
2) Complex: (-96004.9341597073, 74059.0382069111)
3) Complex: (-228230.07586437, 39987.130440044)
...
126) Complex: (-171475.093895942, -28013.9767662284)
127) Complex: (-194922.892572028, 39157.6390911049)
128) Complex: (301113, 0)
129) Complex: (-194922.892572028, -39157.639091105)
130) Complex: (-171475.093895942, 28013.9767662282)
...
252) Complex: (-3361.17948795692, -308323.032067308)
253) Complex: (-228230.07586437, -39987.1304400443)
254) Complex: (-96004.9341597074, -74059.0382069112)
255) Complex: (-205584.142144339, 59076.3053166472)
=== находим массив амплитуд ===
0) 266723
1) 213903.83202
2) 121250.51968
3) 231706.57766
...
126) 173748.35458
127) 198817.13897
128) 301113
129) 198817.13897
130) 173748.35458
...
252) 308341.35245
253) 231706.57766
254) 121250.51968
255) 213903.83202
=== находим массив фаз (тот что не обязательный) ===
0) 3.14159
1) -2.86177
2) 2.48453
3) 2.96815
...
126) -2.97965
127) 2.94334
128) 0
129) -2.94334
130) 2.97965
...
252) -1.5817
253) -2.96815
254) -2.48453
255) 2.86177
=== заменяем вышестоящий массив фаз на этот массив фаз (он тот же что и в примере 1)===
0) 0
1) 0
...
62) 0
63) 0
64) -1.5708
65) -1.5708
.. данные в виде +1.5708 или -1.5708..
126) -1.5708
127) -1.5708
128) 0
..
255) 0
=== Применяем обратное БПФ ===
0) Complex: (266723, 0)
1) Complex: (213903.832015907, 0)
2) Complex: (121250.519681948, 0)
3) Complex: (231706.57765779, 0)
...
126) Complex: (1.06386669495286E-11, -173748.354584672)
127) Complex: (1.21736365815138E-11, -198817.138969042)
128) Complex: (301113, 0)
129) Complex: (198817.138969042, 0)
130) Complex: (173748.354584672, 0)
...
252) Complex: (308341.352450054, 0)
253) Complex: (231706.57765779, 0)
254) Complex: (121250.519681948, 0)
255) Complex: (213903.832015907, 0)
== Теперь сохраняем этот массив, отбрасывая мнимую часть как целый (short), потом опять БПФ применяем, опять находим массив фаз и получаем это (показываю сразу с позиции, куда я прятал информацию) ==
64) -0.7854
65) 0.7854
66) -0.7854
67) -0.7854
...
124) 0.7854
125) 0.7854
126) -0.7854
127) -0.7854
Как часы работает.... Никакой погрешности +\- 0.7854.

[dar3dev1l26]

Почему так?

[raxp]

сгенерирован генератором случайных чисел с нормальным распределением. Если же массив не имеет нормального распределения (например я беру аудиоданные из wav файла

один вопрос - почему в аудиофайле не набор данных с нормальным распределением? Что показывает утилита ENT по статистике выборки?

[s-andriano]

Проверьте, не происходит ли в процессе прямого или обратного преобразования переполнения, сопровождающегося потерей разрядов.

[dar3dev1l26]

Сообщение от raxp

один вопрос - почему в аудиофайле не набор данных с нормальным распределением? Что показывает утилита ENT по статистике выборки?

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

Сообщение от s-andriano

Проверьте, не происходит ли в процессе прямого или обратного преобразования переполнения, сопровождающегося потерей разрядов.

Не происходит, я тестировал ГСЧ алгоритм с типом данных Int32 - в два раза больше short. Да и основные рассчеты ведутся с комплексными числами (double, double).


Вот алгоритм, в книге не пишет ни слова о случайном распределении:

[dar3dev1l26]

Разницы между данными из аудиофайла и данными сгенерированными ГСЧ кроме равномерного распределения я не вижу. Это странно как-то.

[dar3dev1l26]

Сегодня ходил к учителю, мы с ним не смогли разобраться с этой проблемой. Он знает что такое ДПФ, БПФ, но почему так происходит у меня он тоже не знает, на практике не работал в этой области. Мы только заметили, что ошибок будет меньше, если во входной последовательности не будет нулей, хотя эти же нули никак не влияют на качество, если они в последовательности сгенерированной ГСЧ. Но это не решает проблему полностью, всё равно ошибки бывают, хоть уже и меньше.

[s-andriano]

dar3dev1l26, это ведь Вы писали?

Соотношение скрываемая информация:аудио данные - 1:4. То есть на 16 бит скрываемой информации приходится 64 единицы аудио данных.

А в приведенном Вами скане фигурирует 8-32 бита в секунду, что примерно соответствует 1:48000.
Разница - ни много, ни мало - 4 порядка.
Может, здесь и ошибка?