10.5. Эффекты квантования в алгоритмах БПФ
При
составлении программ (или при аппаратурной реализации БПФ) необходимо учитывать
эффекты, связанные с представлением обрабатываемых чисел и коэффициентов с
ограниченной точностью. К таким эффектам относятся шумы округления при усечении
результатов умножений, погрешности масштабирования промежуточных результатов с
целью устранения возможных переполнений, а также погрешности преобразования,
связанные с конечной точностью представления коэффициентов 
. Уэлч и ряд других авторов подробно проанализировали влияние
шума округления и масштабирования для алгоритмов БПФ по основанию 2 с
прореживанием по времени и по частоте при условии, что все арифметические
операции выполняются с фиксированной или плавающей запятой. Вопрос, связанный с
точностью представления коэффициентов, не рассматривался столь подробно,
поэтому ниже будут приведены лишь качественные результаты. Сначала будут
рассмотрены вопросы реализации алгоритмов БПФ с основанием 2 при выполнении
арифметических операций с фиксированной запятой.
Если
последовательность 
из 
отсчетов имеет коэффициенты ДПФ 
, то, согласно
теореме Парсеваля,
(10.3)
т.
е. средняя мощность выходных гармоник в раз превышает среднюю мощность
исходной последовательности. Следовательно, значения ДПФ последовательности
будут, вообще говоря, существенно превышать значения самой последовательности.
Поэтому при использовании арифметики с фиксированной запятой необходимо во
избежание переполнений ввести масштабирование. Чтобы показать, как могут
возникать переполнения, рассмотрим базовую операцию на 
-м этапе БПФ с
прореживанием по времени. Пусть 
и
-
входные числа базовой операции, a, 
и 
- выходные числа, причем 
-
поворачивающий
множитель. Тогда
(10.4)
Из
формулы (10.4) видно, что при переходе от этапа к этапу модули чисел, вообще
говоря, увеличиваются, поэтому их нужно масштабировать сдвигом вправо. Нетрудно
показать, что от этапа к этапу максимальное значение модуля комплексных чисел
не убывает 
,
как видно из соотношения (10.4), удовлетворяет неравенству.
(10.5)
Следовательно,
уровень сигнала на каждом этапе увеличивается не быстрее, чем на один двоичный
разряд.
Учитывая
вышеизложенное, можно предложить три метода масштабирования:
1.
Сдвиг вправо на один разряд на каждом этапе. Если 
для любых 
и числа сдвигаются
на разряд вправо после каждого этапа итерации (кроме последнего), то
переполнения не произойдет.
2.
Контроль последовательности, гарантирующий выполнение условия 
для всех . На
каждом этапе БПФ вычисляется массив и если хотя бы один отсчет массива
превысит по модулю 1/2, весь массив масштабируется сдвигом вправо на разряд.
3.
Проверка на переполнение. При этом исходная последовательность масштабируется
так, чтобы 
и
были
меньше единицы (а не 
, как в двух предыдущих методах). Если
в ходе базовой операции фиксируется переполнение, то все числа последовательности,
включая результаты уже выполненных на данном этапе (без переполнения) базовых
операций, сдвигаются на разряд вправо, после чего итерация продолжается с той
базовой операции, где произошло переполнение. На каждом этапе может произойти
более чем одно переполнение, но не больше двух.
Первый
метод связан с наименьшими затратами времени и наиболее прост для
программирования. Однако он дает наименьшую точность, так как масштабирование
на каждом этапе приводит к ненужному ухудшению точности в случаях, когда его
можно было не производить. Второй метод требует больших затрат времени
(поскольку на каждом этапе приходится вычислять модули всех чисел массива), и в
то же время он не слишком точный, так как весь массив всегда масштабируется
таким образом, чтобы модули всех его элементов не превышали 1/2, поэтому один
разряд памяти данных
не используется. Третий метод является самым точным, но здесь приходится
повторно обрабатывать всю последовательность всякий раз, когда обнаруживается
переполнение.
Уэлч
разработал довольно простую методику расчета граничных значений уровня шума
округления, возникающего при БПФ. Наличие шума округления обусловлено двумя
факторами:
1.
Появлением погрешности при округлении произведения 
в формулах (10.4). Если и представлены 
-разрядными числами
(т. е. действительная и мнимая части и содержат по разрядов),
то после округления каждого из четырех действительных произведений, входящих в , до -разрядного числа
получается ошибка, равномерно распределенная на интервале 
и имеющая нулевое среднее и
дисперсию, равную 
.
2.
Сдвигом Суммы на один разряд вправо, если при сложении происходит переполнение.
Если младший разряд, при сдвиге выходящий за пределы регистра, равен нулю, то
ошибки не будет. Если же он равен единице, то в зависимости от знака числа
возникает ошибка величиной 
. Дисперсия этой ошибки равна 
.
Верхнюю
границу отношения среднеквадратического значения шума округления к среднеквадратическому
значению выходных гармоник можно получить, предположив, что переполнение происходит
на каждом этапе, так что числа каждый раз приходится масштабировать. Если 
- отсчеты,
получаемые на 
-м
этапе, то 
- их дисперсия,
определяемая как
, (10.6)
причем
.
(10.7)
где
, так что
.
Равенство (10.7) получается в предположении, что на первом же этапе может произойти
переполнение, поэтому в числах нулевого этапа (т. е. в исходных отсчетах)
один младший разряд отбрасывается. На первом этапе базовая операция содержит
умножения только на 
, поэтому шум округления произведений
отсутствует.
На
втором этапе, согласно предположению, также может произойти переполнение,
поэтому массив 
нужно предварительно промасштабировать.
Следовательно, дисперсия 
будет равна
, (10.8)
причем
множитель 4 отражает тот факт, что ошибка при усечении выходных чисел на первом
этапе будет вдвое больше ошибки, обусловленной усечением выходных чисел на
нулевом этапе, поэтому дисперсия возрастает в четыре раза.
На втором этапе
алгоритма БПФ с прореживанием по времени выполняются умножения только на и 
поэтому ошибка,
связанная с округлением произведений, опять будет равна нулю. Итак, в
предположении, что числа 
также масштабируются, получим
следующую формулу для дисперсии ошибки на втором этапе БПФ:
(10.9)
причем
множитель 42 указывает на удвоение ошибки усечения при переходе от
первого этапа ко второму.
На
всех последующих этапах в большинстве базовых операций выполняются нетривиальные
умножения. Так, на третьем этапе половина базовых операций содержит такие
умножения, на четвертом этапе — три четверти и т. д. Согласно формулам (10.4),
общее выражение для действительной части результата базовой операции,
выполняемой на - м этапе, имеет
вид
(10.10)
Аналогичное
выражение можно записать и для мнимой части. Для тех базовых операций, где
умножение на не
является тривиальным, дисперсия результата 
(включая шум округления всех
произведений и шум усечения при масштабировании) имеет вид
(10.11)
где
слагаемое 
учитывает
дисперсию шума округления на -м
этапе, а член
-
дисперсию шума, связанную с масштабированием на этом же этапе. Как уже
отмечалось, оба эти члены равны
(10.12)
Третье
слагаемое суммы (10.11) содержит произведение квадрата модуля и 
. Поскольку 
, это слагаемое
совпадает с первым членом суммы. Второе слагаемое равно произведению 
на среднее
значение квадрата модуля переменных, преобразуемых на -м этапе. Дисперсия равна 
(поскольку
представляется
-разрядным
числом с погрешностью). Чтобы определить средний квадрат модуля переменных,
обрабатываемых на -м
этапе, нужно знать величину 
,
представляющую собой средний квадрат модуля исходного массива чисел, равный
(10.13)
Учитывая,
что среднее значение квадрата модуля увеличивается от этапа к этапу вдвое,
получим, что на выходе -го этапа оно будет равно 
. Тогда дисперсия становится равной
(10.14)
если
во всех базовых операциях -го этапа
выполняются нетривиальные умножения. Бели же ввести 
— долю базовых операций с
нетривиальными умножениями 
, — то второе и третье слагаемые суммы
(10.14) следует умножить на . Так, если 
(как это имеет
место на первом и втором этапах), то равенство (10.14) переходит в (10.8) (при 
) или в (10.9) (при 
). Бели принять,
что 
на
третьем этапе и 
на
всех последующих этапах, причем номер последнего этапа равен 
, то, согласно
формулам (10.7)-(10.14), получим
(10.15)
Поскольку
среднее значение квадратов модулей элементов выходного массива 
равно 
, то средний квадрат их
действительных (или мнимых) частей равен 
.
Таким образом, оценкой отношения среднеквадратических значений (СКЗ) шума и
сигнала на выходе (в пределе при больших )
является величина
(10.16)
Итак,
верхняя граница отношения ошибки к выходному сигналу возрастает как
, т. е. по 
разряда
на этап.
Формулу,
аналогичную (10.16), можно получить и для нижней границы отношения ошибки к
сигналу, если предположить, что переполнений вообще не происходит, так что
ошибки усечения, связанные с масштабированием, отсутствуют. Следовательно,
вплоть до третьего этапа ошибка вообще не возникает. Проведя аналогичный анализу
получим следующую формулу для дисперсии выходных отсчетов 
:
(10.17)
Таким
образом, при большом числе этапов нижняя граница отношения среднеквадратических
значений ошибки и сигнала на выходе имеет вид
(10.18)
Рассмотренная
модель возникновения ошибок была экспериментально подтверждена Уэлчем на
многочисленных примерах. На фиг. 10.16 показано, как изменяется отношение
среднеквадратических значений ошибки и сигнала на выходе, когда на вход поступают
случайные числа с нулевым средним, равномерно распределенные на интервале (-1,
1), причем разрядность чисел равна 17. В этом случае 
.
Как видно из графика, теоретическая верхняя граница хорошо согласуется с
экспериментальными данными, хотя ее наклон несколько больше, чем в эксперименте.
Нижняя граница [см. формулу (10.18)] не приведена, так как она является слишком
оптимистичной и малопригодна для практики.
Фиг. 10.16. Сравнение расчетной верхней границы
уровня шума при БПФ и экспериментальных результатов (по Уэлчу).
Хотя
выше был рассмотрен вариант алгоритма БПФ с прореживанием по времени, переход
к другим вариантам несложен, и оценки верхней и нижней границ отношения
среднеквадратических значений ошибки и сигнала, описываемые формулами (10.16)
и (10.18), справедливы и для них. Таким образом, при разработке систем БПФ с
фиксированной запятой можно руководствоваться формулой (10.16). Зная Максимальный
размер преобразуемого массива и
требуемое отношение среднеквадратических значений ошибки и выходного сигнала,
можно выбрать длину слова так, чтобы обеспечить требуемую
точность.
В
анализе, проведенном выше, рассматривались ошибки, связанные с округлением
произведений и масштабированием, которое используется, чтобы избежать
переполнений. При вычислении БПФ существует еще один источник погрешностей,
обусловленный неточным представлением значений поворачивающих множителей . Хотя полный
анализ этого эффекта еще не проводился, Вайнштейн, используя предположение о
случайном характере погрешностей представления коэффициентов, получил простое
выражение для отношения среднеквадратических значений ошибки и сигнала на выходе
(10.19)
Здесь
— число
разрядов, используемых для представления коэффициентов. Из формулы
(10.19) видно, что дисперсия ошибки с ростом увеличивается
весьма медленно. И хотя эта формула весьма приближенная, экспериментальные
измерения подтверждают основной вывод о том, что дисперсия ошибки
действительно с ростом увеличивается очень медленно. На фиг.
10.17 приведены результаты, полученные Вайнштейном для случаев выполнения
арифметических операций с фиксированной и плавающей запятой. Основное следствие
из приведенных результатов заключается в том, что фиксированная длина слова
(достаточно большая, чтобы обеспечить заданную точность представления
коэффициентов) может использоваться для широкого диапазона значений . Поэтому аппаратуру или
программы БПФ можно применять при решении широкого круга задач, для которых
значения могут отличаться на несколько
порядков.
Фиг. 10.17. Сравнение предельного значения расчетной
ошибки, связанной с квантованием коэффициентов БПФ, и экспериментальных
результатов (по Вайнштейну). - теория (фиксированная запятая); 
- эксперимент
(фиксированная запятая); • - эксперимент (плавающая запятая).
