Алгоритм фильтрации, пример на основе БПФ (стр. 6 из 6)
.В рассматриваемом алгоритме каждый элемент
представляет собой произведение v квантованных коэффициентов. Действительно, можно показать, что каждый отсчет входной последовательности, продвигаясь к k-мувыходу (см. рис.5), на каждой ступени алгоритма претерпевает умножение только на один поворачивающий множитель, т. е. 
(8.14)где
(8.15)Дисперсия элементарных ошибок округления
комплексных коэффициентов равна 
Индивидуальная ошибка БПФ, обусловленная округлением коэффициентов, равна
(8.16)Вычитая (8.15) из (8.14), получаем
члены высшего порядка.Пренебрегая членами высшего порядка и подставляя последнее выражение в (8.16), получаем следующее СК3 ошибки, вызванной квантованием коэффициентов:
(8.17)По теореме Парсеваля СК3 выходного сигнала равно
(8.18)Отсюда «СК3 ошибки / СК3 выходного сигнала» = (v/б) 2-2b2. В случае 16-точечного БПФ «СК3 ошибки/СК3 выходного сигнала» = (2/3) 2-2b2.
В реферате рассмотрены вычислительные ошибки только одного из многочисленных алгоритмов БПФ для определенного вида представления чисел. С таким же успехом использованный подход может быть применен для анализа ошибок других алгоритмов. При этом, очевидно, СК3 ошибок будет существенно зависеть от конфигурации направленного графа алгоритма, способа представления чисел и метода масштабирования.
ЗАКЛЮЧЕНИЕ
До середины 1960-х для представления спектрального разложения использовались точные формулы для нахождения параметров синусов и косинусов. Соответствующие вычисления требовали как минимум N**2 (комплексных) умножений. Таким образом, даже сегодня высокоскоростному компьютеру потребовалось бы очень много времени для анализа даже небольшого временного ряда (для 8,000 наблюдений потребовалось бы, по меньшей мере 64 миллиона умножений).
Ситуация кардинально изменилась с открытием так называемого алгоритма быстрого преобразования Фурье, или БПФ для краткости. Достаточно сказать, что при применении алгоритма БПФ время выполнения спектрального анализа ряда длины N стало пропорционально N*log2(N) что конечно является огромным прогрессом.
Однако недостаток стандартного алгоритма БПФ состоит в том, что число данных ряда должно быть равным степени 2 (т.е. 16, 64, 128, 256,...). Обычно это приводит к необходимости добавлять нули во временной ряд, который, как описано выше, в большинстве случаев не меняет характерные пики периодограммы или оценки спектральной плотности. Тем не менее, в некоторых случаях, когда единица времени значительна, добавление констант во временной ряд может сделать результаты более громоздкими.
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ
1. Цифровая обработка сигналов: Учебн. Пособие для вузов/Л. М. Гольденберг, Б.Д. Матюшкин, М. Н. Поляк. – 2изд., перераб. и доп. – М.: Радио и связь, 1990. – 256 с.: ил.
2. Рабинер Л., Гоулд Б. Теория и применения цифровой обработки сигналов. – М.:Мир, 1978.-848с.
3. Макклеплан Д.Х., Рейдер Ч. М. Применение теории чисел в цифровой обработке сигналов: Пер. с англ. – М.: Радио и связь, 1983.-264с.
4. Гольденберг Л.М., Матюшкин Б.Д., Поляк М. Н. Цифровая обработка сигналов: Справочник.- М.: Радио и связь, 1985. – 312с., ил.