Алгоритм фильтрации, пример на основе БПФ
Информация - Математика и статистика
Другие материалы по предмету Математика и статистика
µ значение отсчета.
Анализ траекторий распространения элементарных ошибок, возникающих на различных ступенях алгоритма, позволяет сделать следующие выводы:
1. Элементарная ошибка с дисперсией , возникающая на т-й ступени алгоритма. вызывает ошибку с дисперсией в 2v-m выходных точках БПФ.
2. Дисперсия ошибки каждого выходного отсчета алгоритма, обусловленной округлением произведений, равна сумме ошибок, 2v-m из которых вызывается ошибками т-й ступени.
Перейдем к анализу арифметических ошибок. В силу того, что математическое ожидание всех элементарных ошибок равно нулю, математическое ожидание результирующей ошибки E(e(k))=0 для всех k. Тогда СКЗ ошибок ДПФ будет определяться только дисперсией элементарных ошибок.
Дисперсия ошибок округления произведения двух комплексных чисел на т-й ступени равна 4. Множитель появляется из-за масштабирования на т предыдущих ступенях путем деления пополам.
Вычислим СКЗ ошибок e(k), k=0,...,N-1. Из анализа алгоритма БПФ (8.3) и соответствующего направленного графа следует, что нетривиальные умножения, связанные с вычислением отсчета Х (k), появляются, начиная со ступени
(8.5)
где. Это объясняется тем, что первое появление
единицы в двоичном представлении , , соответствует умножению на коэффициент -1 на ступени т, тогда на следующей т+ l-й ступени наличие коэффициента = 1 приведет к умножению на j, а уже на т+2 и далее ступенях все умножения будут нетривиальными. Это хорошо проследить, анализируя выражение (8.3), описывающее т-ю ступень алгоритма. Можно показать путем вычислений s (k), что для определения отсчетов с номерами k=0, N/4; N/2; 3N/4 не требуется выполнение нетривиальных умножений, все умножения здесь на ; . Ошибка округления этих отсчетов равна нулю. А для вычисления СКЗ ошибок округления отсчетов с другими k воспользуемся вторым выводом. В результате получим
(8.6)
Пример 7. Рассмотрим вычисление ошибок округления отсчетов 16-точечного БПФ. Для этого выпишем для каждого номера отсчета его двоичное представление . Затем пользуясь выражением (8.6), вычисляем ошибки округления. Результаты расчетов приводятся в табл.1. Заметим, что отсчеты с номерами k=4, 8, 12 вычисляются точно так, как s(k)>4, где 4-максимальное число возможных ступеней алгоритма, т. е. в формировании отсчетов с номерами 0, 4, 8, 12 участвуют умножения только на тривиальные множители (см. также граф на рис.5).
Вычислим СКЗ ошибки, усредненное по всем k. На первых двух ступенях алгоритма (т=1,2) все умножения являются точными, так как множители тривиальны ; на выходах т-й ступени (т = 3,…, у) появляется N произведений в блоках, причем четыре произведения в каждом блоке являются точными в результате умножения также на тривиальные множители.
Таблица 1
Тогда, пользуясь выводом 1, получаем
(8.7)
В случае 16-точечного БПФ
Определим СКЗ выходной ошибки алгоритма, обусловленной масштабированием промежуточных результатов. Ошибка масштабирования комплексного числа на m-й ступени алгоритма имеет нулевое среднее и дисперсию . Множитель появляется из-за масштабирования на m предыдущих ступенях.
В соответствии с выводом 2 СКЗ индивидуальной ошибки равно
(8.8)
в случае 16-точечного БПФ
Усредненное по всем выходам k СК3 также равно
(8.9)
Среднеквадратическое значение суммарной ошибки, обусловленной округлением и масштабированием, вычисляется как сумма отдельных СК3:
(8.10)
СК3 суммарной ошибки, усредненное по всем выходам алгоритма, равно
(8.11)
В случае 1б-точечного БПФ
Результаты вычисления СК3 суммарных ошибок также приведены в табл.1. Точность алгоритма принято оценивать по отношению СК3 ошибки / СК3 выходного сигнала. В данном случае оно составляет
____СКЗ ошибки______ = (8.12)
СКЗ выходного сигнала
В случае 1б-точечного БПФ
___СК3 ошибки_______ =
СК3 выходного сигнала
Как видно из полученных выражений, точность алгоритма зависит от двух параметров: длины преобразования N и разрядности представления чисел b1. Если известны требования по точности вычисления и размер преобразования, разрядность процессора БПФ можно определить из следующего выражения, полученного логарифмированием выражения (8.12):
(8.13)
Теперь перейдем к анализу ошибок БПФ, вызванных неточным представлением значений поворачивающих множителей Пусть
- точные значения коэффициентов Фурье, а (k) - неточные, полученные при условии представления коэффициентов конечным числом разрядов
.
В рассматриваемом алгоритме каждый элемент представляет собой произведение v квантованных коэффициентов. Действительно, можно показать, что каждый отсчет входной последовательности, продвигаясь к k-му выходу (см. рис.5), на каждой ступени алгоритма претерпевает умножение только на один поворачивающий множитель, т. е.
(8.14)
где
(8.15)
Дисперсия элементарных ошибок округления комплексных коэффициентов равна
Индивидуальная ошибка БПФ, обусловленная округлением коэффициентов, равна
(8.16)
Вычитая (8.15) из (8.14), получаем
ч?/p>