Разработать
Деинтонирование звука
Содержание |
Введение
Требуется реализовать приложение которое будет понижать частотные свойства записи человеческой речи без потери её разборчивости.
Аналитический обзор
Для выполнения деинтонирования звукового файла необходимо выполнить FFT преобразование, после чего массив частот на заданный отрезок после чего выполняем обратное FFT.
На рисунке представлена блок-схема алгоритма выполнения деинтонирования звука.
Быстрое преобразование Фурье
Быстрое преобразование Фурье (БПФ, FFT) — это алгоритм быстрого вычисления дискретного преобразования Фурье (ДПФ). То есть, алгоритм вычисления за количество действий, меньшее чем O(N2), требуемых для прямого (по формуле) вычисления ДПФ. Иногда под БПФ понимается один из быстрых алгоритмов, называемый алгоритмом прореживания по частоте/времени или алгоритмом по основанию 2, имеющего сложность O(Nlog(N)). Покажем как выполнить дискретное преобразование Фурье за действий при . В частности, при N = 2n понадобится O(Nlog(N)) действий. Дискретное преобразование Фурье преобразует набор чисел в набор чисел , такой, что , где εn = 1 и при 0 < k < n. Алгоритм быстрого преобразования Фурье применим к любым коммутативным ассоциативным кольцам с единицей. Чаще всего этот алгоритм применяют к полю комплексных чисел (c ε = e2πi / n) и к кольцам вычетов. Основной шаг алгоритма состоит в сведении задачи для N чисел к задаче для p = N / q числам, где q — делитель N. Пусть мы уже умеем решать задачу для N / q чисел. Применим преобразование Фурье к наборам для . Покажем теперь, как за O(Np) действий решить исходную задачу. Заметим, что . Выражения в скобках нам уже известны — это i(mod p)-тое число после преобразования Фурье j-той группы. Таким образом, для вычисления каждого bi нужно O(q) действий, а для вычисления всех bi — O(Nq) действий, что и требовалось получить. Для обратного преобразования Фурье можно применять алгоритм прямого преобразования Фурье — нужно лишь использовать ε − 1 вместо ε (или применить операцию комплексного сопряжения в начале к входным данным, а затем к результату, полученному после прямого преобразования Фурье) и окончательный результат поделить на N.
