9.5. ЭФФЕКТЫ КОНЕЧНОЙ РАЗРЯДНОСТИ РЕГИСТРОВ ПРИ ВЫЧИСЛЕНИИ ДИСКРЕТНОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ
Поскольку дискретное преобразование Фурье (ДПФ) находит широкое практическое применение в цифровой фильтрации и спектральном анализе, важно проанализировать эффекты, возникающие при вычислении ДПФ за счет конечной разрядности чисел в регистрах. Точный анализ этого вопроса сложен, и часто для выбора необходимого числа разрядов регистра достаточно воспользоваться упрощенным методом анализа, который приводится ниже. Этот метод аналогичен рассмотренному в предыдущих параграфах. В частности, ошибки округления, возникающие в различных точках системы в соответствии с алгоритмом вычисления, будут представлены соответствующими источниками аддитивного шума. Кроме того, вводится ряд предположений для упрощения метода анализа. На основе полученных результатов даются некоторые простые и полезные правила, справедливые для большинства эффектов шумов округления. Анализ дается на примере операции округления. Однако (как и при анализе ошибок за счет шумов округления для цифровых фильтров) полученные результаты в общем случае могут быть модифицированы для операции усечения в арифметических устройствах с фиксированной запятой при дополнительном коде и плавающей запятой при обратном и прямом кодах.
В гл. 6 показано, что существует ряд методов вычисления ДПФ. В этом параграфе сначала рассматриваются ошибки, возникающие при прямом вычислении ДПФ, а затем анализируются
эффекты шумов округления на примере одного частного класса алгоритмов быстрого преобразования Фурье (БПФ).
9.5.1. АНАЛИЗ КВАНТОВАНИЯ ПРИ ВЫЧИСЛЕНИИ ДПФ
Дискретное преобразование Фурье определяется равенством
где
Несмотря на то что в общем случае (9.78) вычисляется на основе одного из алгоритмов (в совокупности известных, как алгоритмы БПФ), в ряде случаев (когда требуемое
мало) наиболее рациональным подходом является прямое накопление произведений в выражении (9.78). Анализ процедуры вычисления ДПФ в этом случае довольно прост и используется в качестве основы для рассмотрения эффектов квантования.
Нетрудно видеть, что при заданном значении
полностью аналогично выражению сверточной суммы
, которая была подробно рассмотрена ранее. В данном случае величины
выполняют роль импульсной характеристики,
и
-выходной и входной последовательностей соответственно. Следует учитывать, что все эти величины в общем случае комплексные. Таким образом, для прямого вычисления ДПФ можно использовать метод анализа § 9.4 с учетом того, что ошибки представляют собой комплексные последовательности.
Рис. 9.15. Статистическая модель для шума округления при вычислении ДПФ с фиксированной запятой
На рис. 9.15 показан один из вариантов прямого вычисления
Здесь через
обозначен результат вычисления
с ограниченной точностью и через
— ошибка в определении
величины. Комплексные величины
представляют ошибки, обусловленные округлением произведений
Может быть показано, что эти комплексные ошибки суммируются на выходе. При этом
Тогда произведение
можно представить в виде
В случае ограниченной точности арифметического устройства с фиксированной запятой результат округления рассмотренного комплексного произведения можно представить в виде
Это значит, что каждое действительное умножение создает ошибку округления. Чтобы вычислить дисперсию ошибки
необходимо сделать ряд предположений относительно ее отдельных составляющих. В частности, предполагается, что ошибки, обусловленные каждым действительным умножением: 1) представляют собой случайные величины, равномерно распределенные на интервале от
до
Поэтому дисперсия ошибки каждого источника равна
некоррелированы между собой; 3) некоррелированны с входным сигналом и, следовательно, с выходным.
Среднее значение ошибки за счет операции округления при комплексном умножении равно нулю. Так как квадрат комплексной ошибки
равен
то среднее значение величины
есть
Среднее значение квадрата выходной ошибки равно
Как и при прямой форме построения КИХ-фильтра, здесь уровень выходного шума пропорционален
Как и при прямой форме построения КИХ-фильтра с фиксированной запятой, при прямом вычислении ДПФ важной проблемой является ограничение динамического диапазона. Из (9.78) следует, что
Чтобы не происходило
передополнения, необходимо выполнить условие
Оно выполняется, если
Таким образом, в наихудшем случае для предотвращения переполнения можно разделить входной сигнал на
Например, последовательность
имеет ДПФ
. С другой стороны,
может быть меньше единицы, даже если условие (9.82) не выполняется. Рассмотрим, например, последовательность
которая имеет
для
Если
и только немного меньше единицы, то (9.82) не выполняется, однако
Существует ряд методов решения проблемы ограничения динамического диапазона. Можно делить входной сигнал на
однако при этом растет выходное отношение шум/сигнал. Можно использовать схемы с поблочно плавающей запятой, в которых в случае переполнения производится деление на два. Можно использовать также арифметическое устройство с плавающей запятой, в котором принципиально исключена возможность переполнения. Все эти способы будут в деталях проанализированы на базе одного из классов алгоритмов БПФ. Будут также сделаны выводы относительно ошибок, обусловленных квантованием значений коэффициентов.