Подскажите алгоритм реализации КИХ фильтра на x86 совместимом процессоре. Требуется корректировать частотную характеристику 8 каналов аудио (16 бит 48КГц) в реальном времени. Реализация FFT->умножение->IFFT не проходит по времени (процессор 755 МГц). Для коррекции характеристики достаточно 64 коэффициентов. Может быть есть уже готовые примеры реализации, или на этом процессоре такое в принципе не возможно?

Используйте MMX-инструкции, с ними пожалуй возможно...

Неужели еще не придумали быстрых алгоритмов КИХ кроме как через FFT? Ведь для действительного сигнала работа с комплексными числами кажется лишней.

В основе фильтрации КИХ - фильтром лежит свёртка.
вы скорее всего используете секционную.

попробуйте использовать тот факт, что после фильтрации выходной сигнал имеет длину L = M + N - 1

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

L - длна полученной секции
M - длина секции, подающейся на вход.
N - длина фильтра.

Используйте DCT. Он быстрее..
Практически "готовый" эквалайзер можно "скопировать"
из стандартов по сжатию звука:
iso11172-3: polyphase filter bank - 32 полосы,
iso13818-3: polyphase filter bank - 32 полосы,
iso13818-7: TDAC filter bank - 128/1024 полосы,
iso14496-3: TDAC filter bank - 128/1024/120/960 полосы.
См.-> http://www.mp3-tech.org/programmer/docs/paper-1-english.pdf

# Используйте DCT. Он быстрее.. #

Может и быстрее, но при этом должны выполняться условия для N - точечной входной последовательности:

1. последовательность вещественная
2. x(n) = x(N - n)

1. Звук - это обычно "вещественная последовательность".
2. Банки фильтров, используемые в стандартах сжатия звука,
это именно ФИЛЬТРЫ, реализованные с помощью алгоритма DCT
и еще много чего. И как всякий фильтр они не требуют периодического
по времени сигнала на входе.

Что касается, "может и быстрее", то FFT (radix2) требует:
4*N*log2(N)+4*N умножений реальных чисел и
6*N*log2(N)+2*N сложений реальных чисел, т.е.
1792 умножений и 2432 сложений для N=64.

Тогда как DCT (radix-2) требует:
(N/2)*log2(N) умножений реальных чисел и
(3*N/2)*log2(N)-N+1 сложений реальных чисел, т.е.
192 умножений и 513 сложений для N=64.

См: IEEE Trans. on Comm., v.com-25, no.9, sept.1977, p.1004,
W.Chen. "A fast computational algorithm for the discrete cosine transform".

Сообщение отредактировал blackfin - Jan 27 2007, 13:56

Пардон, в статье Chen'а опечатка.

Для FFT (radix2):
2*N*log2(N)-2*N умножений реальных чисел и
3*N*log2(N)-N сложений реальных чисел, т.е.
640 умножений и 704 сложений для N=64.

Для DCT (radix-2):
(N/2)*log2(N) умножений реальных чисел и
(3*N/2)*log2(N)-N+1 сложений реальных чисел, т.е.
192 умножений и 513 сложений для N=64.

Сообщение отредактировал blackfin - Jan 27 2007, 14:32

К сожалению, у меня нет доступа к этому источнику, не мог бы ты мне перекинуть эту статью.
например, на мыло: tananykin@mail.ru

Сообщение отредактировал GinGreen - Jan 27 2007, 19:39

С удовольствием перекинул бы, но, к сожалению, у меня hard copy,
полученная когда-то в ГПНТБ.

В статье, ссылку на которую я привел в самом начале, есть подробный
вывод FDCT и его использование в полифазных фильтрах.
К сожалению, там нет числа сложений/умножений в общем виде,
а есть таблица для 2<= N<=64, поэтому понадобился Chen,
но у него выходят "несколько другие" значения,
хотя сама статья является "классической" и ссылки на нее
есть почти в каждой статье по FDCT. (Из тех, что видел я )

Нашел реализацию http://www.gnu.org.ua/software/gnuradio/doc/annotated.html
Если не влезет в реал тайм придется заморачиваться с FDCT, хотя не совсем понятно как синтезировать его по попроизвольной АЧХ.

Создатели вот этой свободной библиотеки http://www.fftw.org/ http://www.fftw.org/download.html потратили много времени, дабы на Вашей x86-машине Фурье выполнялся максимально быстро, и не только благодаря наличию MMX. Может чем-то поможет??? Я с ней еще не заморачивался, поэтому сам с удовольствием послушаю отзывы...

Попробуйте использовать готовые библиотеки наример от Intel - The Intel® Integrated Performance Primitives(IPP)