Дискретное преобразование Фурье
08.01.2015 03:00
2
Покумеков, я понял, что можно такое дело запросто забацать на проце фирмы ATMEL - какой-нибудь ATMEG-е.
Для реализации наших «дергающихся палочек» нам всего-то потребуется оцифровать входящий аналоговый сигнал (зависимость громкости от времени) и разложить его в ряд Фурье (зависимость амплитуд гармоник сигнала от частоты).
Каждая наша «палочка» будет отвечать за определенный интервал частот (гармонику), а ее высота - за общую амплитуду этого интервала.
В принципе, все просто - бери учебник, сдувай с него пыль, вспоминай алгоритм бабочки и реализуй - но мне мешало одно и имя ему ЛЕНЬ :)
Что делают в таких ситуациях? Прально - лезут в гугль, наверняка кто-нибудь уже что-то подобное делал. Так оно и есть, библиотек море, есть даже популярные вроде такого или такого. Есть даже очень точные, есть 16-битные, 8-битные и т.д., есть даже очень хорошее объяснение всего мат. аппарата.
Но все это было не то - алгоритмы были сложные и тяжелые по вычислениям и затратам на память (требовалось аж три массива - входной и два выходных - действительная и мнимая части). Мало того, что столько памяти на более-менее простой однокристалке взять просто неоткуда (ну или будет ее впритык) так еще и она могла не успеть все это разложить в перерывах между оцифровкой сигнала.
Точность тут вообще никуда не уперлось - мы же не частотомер делаем. Хотелось простецкого алгоритма, пусть и выдающего лишь приближенные результаты. И на выходе нам требуется лишь амплитуда, мнимые и действительные части не нужны. Амплитуда считается как sqrt( мнимое2 + действительное2 ).
После достаточно длительных поисков я наконец нашел идеальный вариант для меня на pastebin-е.
Очень простой алгоритм, делающий все, что мне нужно было, привожу его псевдокод на JavaScript:
var FFT = ( function( size ) { var m = size + ( size % 2 ); //размер выходного буфера должен быть четным var out = new Array( m ); return function( data, len ) { var pid = ( 2.0 * Math.PI ) / len; var r, i, w, t; //высчитываем среднее значение по всему интервалу //для последующей нормализации var mv = 0; for ( t = 0; t < len; t++ ) mv += data[t]; mv = mv / len; for ( w = 0; w < m; w++ ) { var a = w * pid; r = 0; i = 0; for ( t = 0; t < len; t++ ) { //нормализация значения из интервала var v = data[t] - mv; var ta = a * t; r += v * Math.cos( ta ); i += v * Math.sin( ta ); } out[w] = Math.sqrt( r * r + i * i ) / len; } return out; }; } )( 64 );
При начальном создании:
| size | количество наших гармоник (должно быть кратно 2), полезных гармоник всегда на 1 меньше, т.к. первая гармоника (0 Hz) бесполезна для нашей цели |
Возвращает функцию с параметрами:
| data | массив данных |
| len | его длинна |
При вызове ее с данными звука, вернет массив длиной size с амплитудами гармоник.
Соответственно, пропускаем 0 значение из этого буфера (тот самый 0 Hz), а значения с 1 по size - 1 и есть высоты наших «палочек» от самой низкой гармоники (басы) до самой высокой (писк).
Ну и используя наш опыт WEB Audio API и его ScriptProcessor - демка на 64 гармоники (заодно можно увидеть, почему самая первая гармоника нам не нужна - после нормализации ее амплитуда всегда 0):
играть
Зная вот эти алгоритмы аппроксимации, переложить этот код в код однокристалки не составит труда (обычно ограничения там в том, что числа целочисленные и доступны только действия +-*/).
08.01.2015, Protocoder