Тема: Анализ звуковых спектров

[Gall]

бабочка
data1[0]:=data[0];
data1[1]:=data[2];
data1[2]:=data[1];
data1[3]:=data[3];

Это не бабочка.

Бабочка - это вот (условно):

Код: [Выделить]

data1[0] := data[0] + w0 * data[2];
data1[2] := data[0] - w0 * data[2];
data1[1] := data[1] + w0 * data[3];
data1[3] := data[1] - w0 * data[3];
На схеме стрелочки показывают, что с чем складывать и что из чего вычитать. (рис. 6.7). То есть, если две стрелочки сходятся - значит, надо числа сложить. Если около стрелочки написано число, например +1, -1 или w0, значит, надо перед сложением на это число умножить. Способ записи формул в виде таких вот диаграмм со стрелочками для таких задач немножко удобнее, чем "обычный" алгебраический.

"Условно" - потому что у нас числа комплексные, а значит, нельзя просто написать "плюс" и "умножить". Придется как-то так:

Код: [Выделить]

function add(a, b : TComplex) : TComplex;
begin
    add.re := a.re + b.re;
    add.im := a.im + b.im;
end;

function mul(a, b: TComplex) : TComplex;
begin
    mul.re := a.re * b.re - a.im * b.im;
    mul.im := a.re * b.im + a.im * b.re;
end;

//...

data1[0] := add(data[0], mul(w0, data[2]));
// и так далее(не уверен, что я пишу на том же диалекте Паскаля, что и вы, но суть вроде ясна).

[barbucha]

w0 * data[2]
это пишется
mul.re := w0.re * data[2].re - w0.im * data[2].im;
mul.im := w0.re * data[2].im + w0.im * data[2].re;
так?

чему равно w0.re и w0.im ?

[Gall]

w0 * data[2]
это пишется
mul.re := w0.re * data[2].re - w0.im * data[2].im;
mul.im := w0.re * data[2].im + w0.im * data[2].re;
так?

Так. Напишите функцию, чтобы не писать это каждый раз (см. мой пример выше).

чему равно w0.re и w0.im ?

В этом примере w0=1, то есть w0.re=1, w0.im=0. (То есть, можно и не умножать было). Чему равно w0, в книжке тоже написано - смотрите внимательнее.

[barbucha]

w0.re=1, w0.im=0.

тоесть
w0.re=  cos  A
w0.im = sin  A
где А =0

правильно ли понял что круг нужно поделить на количество секторов равных количеству отсчетов.
В данном случае 360 / 4 = 90
поэтому
А0 = 0
А1 = 90
А2 = 180
А3 = 270

[Gall]

w0.re=1, w0.im=0.

тоесть
w0.re=  cos  A
w0.im = sin  A
где А =0

А где модуль числа? Синус и косинус на что умножаются?

правильно ли понял что круг нужно поделить на количество секторов равных количеству отсчетов.
В данном случае 360 / 4 = 90
поэтому
А0 = 0
А1 = 90
А2 = 180
А3 = 270

Нет. Забудьте вообще про круг, его там нету. Синусов и косинусов тоже нету. И никогда не считайте в градусах - в математике все углы всегда ТОЛЬКО в радианах. Тригонометрическая форма комплексного числа для расчетов вам вообще не потребуется.

Думайте в терминах комплексных функций. У вас на входе есть функция f(x). Вам на выходе надо получить функцию F(w). Обе функции комплексные. Ничего больше.

Вы просто хотите численно посчитать вот такой интегральчик:

для всех значений w. Ничего больше.

[barbucha]

могли бы вы в качестве примера привести текст программы на c++ или паскаль
БПФ из 4 отсчетов?

[barbucha]

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

[Gall]

Давайте сначала разберемся, как делать не быстрое, а ОБЫЧНОЕ преобразование Фурье.

Вы очень хотите сделать БПФ, но при этом явно совершенно не понимаете сути самого преобразования.

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

[barbucha]

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

[Gall]

Вот смотрите. Преобразование Фурье - это вычисление интеграла (не буду еще раз повторять, какого). Понятно, как примерно это считать:

Код: [Выделить]

for iw := 0 to N do
begin
    s := 0;
    for ix := 0 to N do
    begin
         s := s + чего-то там * data[ix];
    end;
    result[iw] := s;
end;
То есть, для каждого w считаем интеграл по x.

Можете посмотреть на формулы дискретного преобразования Фурье - там это написано не в виде интеграла, а в виде суммы.

Если сейчас вы внимательно проанализируете программу, вы увидите, что в ней внутренний цикл много раз повторяется для примерно одних и тех же чисел. Каждое data[ix] входит в каждое result[iw]. Не надо быть академиком, чтобы понять, что это очень нерационально - одна и та же работа делается много раз. К счастью, можно вынести общие слагаемые за скобку (причем несколько раз) и посчитать то же самое в другом порядке: сначала суммировать и умножать в маленьких группах, потом объединять маленькие группы в большие и так далее. Это и есть БПФ-"бабочка": сначала обрабатываем пары, потом пары пар... Результат получается тот же самый, но действий требуется гораздо меньше.

[Gall]

Вообще вам идеально подойдет python с библиотекой scipy (http://scipy.org) - там есть весь набор готовых функций, включая линейную алгебру, преобразование Фурье, обработку многомерных изображений и т.д. Эта библиотека специально делалась для научных расчетов. С комплексными числами, векторами и матрицами она работает непосредственно, без дополнительного программирования.

[barbucha]

буду скачивать и разбиратся

[barbucha]

используются ли где либо методики перемешивания разрядов
например есть 6 битная шина и как в примере с БПФ идет зеркальное отображение или инвертирование сигнала.

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

вот пример только вместо единиц прямая линия
вместо нулей разорванная линия





при различных видах перетасовки разрядов получаются разные узоры

[barbucha]

еще один математический спецэффект
если взять таблицу любого размера и заполнить ее числами от 1 до X , а потом взять прямоугольник из чисел любой формы и посчитать сколько штук каких цифр. И после этого посчитать штуки штук то всегда выходят одинаковые числа
есть ли где либо объяснение этого явления

примеры




есть ли какой либо физический смысл у действий
например есть число 1367 оно = 1+3+6+7= 17 = 1 + 7 = 8
что в данном случае 8?

[Gall]

еще один математический спецэффект
если взять таблицу любого размера и заполнить ее числами от 1 до X , а потом взять прямоугольник из чисел любой формы и посчитать сколько штук каких цифр. И после этого посчитать штуки штук то всегда выходят одинаковые числа
есть ли где либо объяснение этого явления

Есть конечно. В теории чисел. Это довольно простые "игры" с цифрами.

В этом примере все просто до смешного: между клетками прямоугольника есть очень простая зависимость. По вертикали цифры всегда увеличиваются на единичку (с циклическим переполнением), а по горизонтали - на высоту всей таблицы (тоже с переполнением). Отсюда и следует напрямую вся "магия". Это напрямую связано с арифметикой ВЫЧЕТОВ, или, что то же самое,
модулярной арифметикой.

Вот более простой пример. Запишем чиста от 1 до N и под ними напишем еще раз то же самое, но в обратном порядке:
1 2 3 4 5 6 7 8 9 10 11 12 13
13 12 11 10 9 8 7 6 5 4 3 2 1
В каждой паре чисел, стоящих друг над другом, сумма будет равна N+1.
Доказательство фокуса: в верхнем ряду стоят числа вида i, а в нижнем ряду N+1-i. Очевидно, что i+N+1-i=N+1.

Основные принципы подобных фокусов такие: во-первых, нет никакой разницы, какими значками обозначать цифры. Если вместо арабских цифр использовать вавилонскую клинопись или китайские иероглифы, ничего не изменится. Точно так же ничего не изменится, если поменять ноль и единицу местами. Точно так же ничего не изменится, если писать цифры в обратном порядке, а при сложении и умножении делать перенос слева направо, а не справа налево. Отсюда берутся "кажущиеся" свойства.

Второй принцип - если мы выбрали систему счисления (десятичную, например), мы автоматически приписали особый смысл некоторым цифрам (например, девятке). Если мы используем позиционную запись, то особыми свойствами начинают обладать числа вида 10, 100, 1000 и т.д., а также числа 11, 111, 1111 и т.д. Причем особые свойства у них есть в ЛЮБОЙ системе счисления - важно не то, что они означают, а то, как они ПИШУТСЯ.

есть ли какой либо физический смысл у действий
например есть число 1367 оно = 1+3+6+7= 17 = 1 + 7 = 8
что в данном случае 8?

Есть, но не физический, а математический. Это называется "цифровой корень". Как и у любого другого математического объекта, у него есть свои свойства. В десятичной системе счисления эта процедура равноценна "выкидыванию девяток". То есть, просто ОСТАТКУ ОТ ДЕЛЕНИЯ НА 9. Это легко доказать.

Этот и другие фокусы есть в книгах, например, Мартина Гарднера.
Вот пример с цифровым корнем:
http://golovolomka.hobby.ru/books/gardner/gotcha/ch2/05.html
А вот книжка:
http://golovolomka.hobby.ru/books/gardner/gotcha/content.shtml

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

Я только что говорил про фокус с записью чисел в две строчки. Другой вариант этого фокуса - записать длинную строку чисел, сложенную "вдвое":
1 2 3 4 5 6 7
14 13 12 11 10 9 8
Анализ свойств такой записи сразу дает способ посчитать сумму всех чисел от 1 до N, а именно формулу N*(N+1)/2. Точно так же выводится формула суммы арифметической прогрессии.