9.5.2. АНАЛИЗ ЭФФЕКТОВ КВАНТОВАНИЯ В АЛГОРИТМАХ БПФ С ФИКСИРОВАННОЙ ЗАПЯТОЙ

Существует много различных алгоритмов БПФ, и, естественно, эффекты квантования будут зависеть от конкретного вида применяемого алгоритма. Наиболее часто используются алгоритмы с основанием 2, для которых величина вычисляемого преобразования является целым числом степени 2. Приводимое ниже рассуждение в своей большей части базируется на алгоритме с основанием 2 и прореживании во времени. Однако результаты с небольшой модификацией применимы для алгоритма с прореживанием по частоте. Кроме того, большинство идей, используемых при анализе ошибок алгоритмов с основанием 2, можно применить в других алгоритмах.

Рис. 9.16. (см. скан) Направленный граф для алгоритма БПФ с прореживанием по времени

Алгоритмы БПФ предназначены для вычисления бесконечной последовательности определяемой (9.78). Направленный граф, представляющий алгоритм с прореживанием во времени для показан на рис. 9.16. (Построение этой частной формы алгоритма было использовано в опубликованной экспериментальной работе.) Эта диаграмма имеет ряд ключевых аспектов, которые, как упоминалось в гл. 6, являются общими для всех стандартных алгоритмов с основанием 2. Дискретное преобразование Фурье вычисляется в течение этапов. На каждом этапе формируется новый массив чисел из предыдущего массива с помощью линейной комбинации элементов, отбираемых по два в данный момент времени. Требуемое ДПФ получается в массиве. Базовая числовая операция выполняется над парой чисел в массиве с тем, чтобы образовать пару чисел в массиве. Эта операция, называемая «бабочкой», выражается

Здесь индексы относятся к массивам соответственно, а и обозначают положение чисел в каждом массиве. (Отметим, что относится к входному массиву и — к выходному массиву.) Направленный граф, представляющий базовую операцию алгоритма БПФ («бабочку»), показан на рис. 9.17.

Рис. 9.17. Основная операция вычисления БПФ с прореживанием по времени

Рис. 9.18. Статистическая модель для шума округления при выполнении основной операции вычисления БПФ с прореживанием по времени при фиксированной запятой

Форма базовой операции в алгоритме с основанием 2 и прореживанием по частоте несколько отличается от формы базовой операции в алгоритме с прореживанием по времени; здесь базовая операция представляет

На каждом этапе выполняется базовых операций для образования следующего массива. Целое число меняется при изменении в соответствии с конкретной формой

используемого алгоритма БПФ. К счастью, наш анализ не связан с конкретным способом изменения . К тому же специфическое соотношение между определяющее способ индексации в массиве, для анализа не существенно. Детали анализа для алгоритмов с прореживанием по времени и по частоте несколько отличаются из-за различных форм базовой операции, однако основные результаты изменяются незначительно. При анализе будем предполагать, что базовая операция имеет форму (9.83), соответствующую прореживанию во времени.

Шум округления будем моделировать с помощью генератора аддитивного шума, связанного с каждой операцией умножения с фиксированной запятой. При этой модели для анализа эффектов шума округления базовая операция алгоритма рис. 9.17 заменяется базовой операцией алгоритма рис. 9.18. С помощью записи ясно показано, что эта величина представляет собой комплексную ошибку, возникающую при вычислении массива из массива, а именно при умножении элемента массива на комплексный коэффициент.

Поскольку будем предполагать, что входной величиной для БПФ является комплексная последовательность, то каждое из умножений оказывается комплексным и, таким образом, в действительности состоит из четырех действительных умножений, выполняемых точно так же, как было рассмотрено в предыдущем параграфе. Снова предполагается, что

1) шум округления, возникающий при каждом действительном умножении, равномерно распределен по амплитуде между , таким образом, имеет дисперсию

2) все источники шума, возникающие при каждом действительном умножении, некоррелированны друг с другом. Таким образом, для любого заданного комплексного умножения четыре составляющие шума некоррелированны друг с другом. Кроме того, они некоррелированны с составляющими шума от других комплексных умножений;

3) все источники шума некоррелированны с входным сигналом и, следовательно, с результатами вычисления в каждом массиве.

Поскольку каждая из этих четырех последовательностей является некоррелированным белым шумом с нулевым средним значением и все они имеют одинаковую дисперсию, то, как и в (9.80), имеем

Эта дисперсия будет обозначена через При расчете среднеквадратического значения выходного шума в любом выходном узле должна быть учтена роль каждого источника шума, который влияет на данный узел. Из рассмотрения направленного графа рис. 9.16 можно сделать следующие выводы:

1) в направленном графе функция передачи от одного узла к любому другому, соединенному с ним, сводится к умножению на

комплексную константу единичной величины (так как передача каждой ветви равна либо единице, либо целому числу степени );

2) в направленном графе каждый выходной узел соединяется с базовыми операциями. Например, на рис. 9.19а показан направленный граф с исключением всех базовых операций, которые не соединяются с (0), а на рис. 9.196 — направленный граф с исключением всех базовых операций, которые не соединяются с

Рис. 9.19. Базовые операции, влияющие на формирование: а)

Указанные выше замечания можно обобщить на случай , имеющего произвольную степень 2.

Как следствие первого замечания, среднеквадратическое значение уровня составляющей выходного шума, обусловленной каждым из элементарных источников шума, является одинаковым и равным Общий шум в каждом выходном узле равен сумме шумов, поступающих к такому узлу. Поскольку предполагалось, что все источники шума некоррелированные, среднеквадратическое значение уровня выходного шума равно умноженной на число, равное количеству источников шума, воздействующих на этот узел. При каждой базовой операции вводится не больше одного комплексного источника шума; следовательно, на основании приведенного выше вывода 2 к каждому выходному узлу поступают шумы не более чем от источников. В действительности все базовые операции не создают шумов округления, поскольку некоторые (например, все те, которые используются на первом и втором этапах) включают только умножение на единицу. Однако если предположить, что шум округления возникает при каждой базовой операции, то общий результат можно рассматривать как верхнюю границу уровня выходного шума. С учетом этих предположений среднеквадратическое значение выходного шума для величины определяется по формуле

которую для больших можно аппроксимировать как

В соответствии с этим результатом среднеквадратическое значение выходного шума пропорционально — количеству точек преобразования. Эффект удвоения или добавления другого этапа в БПФ выражается в удвоении среднеквадратического значения выходного шума.

При выполнении алгоритма БПФ арифметическим устройством с фиксированной запятой должна быть полная уверенность в отсутствии переполнения. Из (9.83) следует, что

а также то, что

В (9.88) подразумевается, что максимальные значения модулей являются неубывающими от этапа к этапу; когда величина выходного сигнала БПФ становится меньше единицы, то величина точек в каждом массиве должна быть меньше единицы т. е. ни в одном из массивов не будет переполнения.

Чтобы выразить это ограничение в качестве граничного условия для входной последовательности, из предыдущего параграфа напомним, что условие

является как необходимым, так и достаточным для гарантии Таким образом, условие (9.90) является достаточным для гарантии отсутствия переполнения для всех этапов алгоритма.

Чтобы получить точное выражение для отношения шум/спгпал на выходе алгоритма БПФ с учетом необходимого масштабирования, рассмотрим входной сигнал, в котором последовательные величины последовательности некоррелированны, т. е. входной сигнал в виде белого шума. Предполагается также, что действительная и мнимая части входной последовательности некоррелированны и что каждая из них имеет равномерную плотность амплитуд на интервале между . [Заметим, что этот сигнал удовлетворяет (9.90).] Тогда средний квадрат модуля комплексной входной последовательности равен

Дискретное преобразование Фурье входной последовательности равно из которого ясно, что с учетом сделанных выше предположений относительно входного сигнала

Объединив (9.87) и (9.92), получим

Таким образом, в соответствии с результатом (9.93) выходное отношение шум/сигнал пропорционально Поскольку пропорциональна то (9.93) указывает, что отношение шум/сигнал возрастает пропорционально или одному разряду на каждый этап. Это значит, что если удваивается соответственно прибавлению одного дополнительного этапа к БПФ, то для сохранения того же отношения шум/сигнал к длине регистра должен быть добавлен один разряд. Предположение о том, что входной сигнал является белым шумом, здесь, на самом деле, не критично. Для ряда других входных сигналов отношение шум/сигнал также пропорционально только с другим коэффициентом пропорциональности.

Выражение (9.89) допускает другую процедуру масштабирования. Поскольку максимальные значения модулей увеличиваются от этапа к этапу не более чем в 2 раза, то переполнения можно избежать, потребовав, чтобы и вводя ослабление входного сигнала на 1/2 на каждом этапе. В этом случае выход будет состоять не из ДПФ, определяемого (9.78), а из этого ДПФ, умноженного на Хотя среднеквадратическое значение выходного сигнала будет в раз меньше, чем при отсутствии масштабирования, амплитуда входного сигнала может быть в раз больше без переполнения. Таким образом, максимально достижимая амплитуда выходного сигнала (при входном воздействии в виде белого шума) остается той же, что и ранее. Однако уровень выходного шума будет много меньше, чем в (9.87), поскольку шум, возникающий на более ранних этапах вычисления БПФ, будет ослаблен за счет масштабирования, используемого для последующих массивов. А именно, при введении масштабирующего множителя 1/2 на входе каждой базовой операции можно модифицировать базовую операцию рис. 9.18, как показано на рис. 9.20,

Рис. 9.20. Базовая операция с использованием масштабирующих умножителей и сопутствующим шумом округления при фиксированной запятой

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

Так как все источники шума некоррелированные, среднеквадратическое значение уровня выходного шума в каждом узле по-прежнему равно сумме составляющих каждого источника шума в направленном графе. Однако в противоположность предыдущему случаю ослабление шума каждого источника при прохождении через направленный граф зависит от массива, в котором он возник. Шумы источника, возникающие в массиве, будут при распространении до выхода умножены на комплексный коэффициент с величиной Из рис. 9.16 видно, что при каждый выходной узел соединяется с: 1) базовой операцией, создаваемой массивом; 2) базовыми операциями, создаваемыми массивом; массивом и т. д.

В общем случае при каждый выходной узел соединяется с базовыми операциями и поэтому с источниками шума, возникающими в массиве. Таким образом, в каждом выходном узле среднеквадратическое значение уровня шума равно

При больших будем предполагать, что пренебрежимо мала по сравнению с единицей, поэтому

и, таким образом, много меньше результирующей дисперсии шума, когда для всех входных данных применяется масштабирование.

Теперь можно объединить (9.95) с (9.92) для получения отношения шум/сигнал в случае поэтапного масштабирования и белого шума на входе. Получим

где результат пропорционален а не Объяснение того факта, что в (9.96) выходное отношение шум/сигнал возрастает пропорционально или половине разряда на каждый этап вычисления, было впервые дано Уэлчем [23]. Важно снова

подчеркнуть несущественность предположения о том, что сигнал является белым шумом. Основной результат об увеличении на половину разряда длины регистра на каждый этап вычисления справедлив для широкого класса сигналов, при этом только множитель на константу в (9.96) будет зависеть от свойств сигнала.

Необходимо также отметить, что множитель числителя, обусловливающий увеличение отношения шум/сигнал с увеличением эквивалентен уменьшению уровня сигнала (требуемому для исключения переполнения) по мере выполнения этапов вычисления. В соответствии с (9.95) очень небольшой шум (только один или два разряда) присутствует в конечном массиве. Большая часть шума была устранена при масштабировании.

В проводимом ранее обсуждении предполагался прямой порядок вычисления с фиксированной запятой, т. е. были возможны только предварительно установленные ослабления и не допускалось изменение масштабирования путем проверки на переполнение. Очевидно, что если возможности аппаратурного или программного выполнения таковы, что должен использоваться прямой метод вычисления с фиксированной запятой, то следует, по возможности, вводить аттенюаторы с ослаблением на 1/2 в каждый массив, а не использовать большое ослабление во входном массиве.

Третий способ для устранения переполнения заключается в использовании поблочно плавающей запятой. В этой процедуре исходный массив нормируется до крайнего слева слова ЦВМ с учетом ограничения Вычисление выполняется по методу с фиксированной запятой, за исключением того, что после каждого сложения производится проверка на переполнение. Если обнаруживается переполнение, то весь массив делится на 2 и вычисление продолжается. Для определения масштабирующего множителя или порядка для всего выходного массива производится подсчет необходимого количества сдвигов. Выходное отношение шум/сигнал в сильной степени зависит от того, на каком этапе вычисления произошли переполнения и от их числа. Место и время возникновения переполнений определяются преобразуемым сигналом и, таким образом, для анализа отношения шум/сигнал при выполнении БПФ с поблочно плавающей запятой необходимо знать свойства входного сигнала.

Как мы видели, можно найти входной сигнал, для которого не требуется масштабирование, а также входной сигнал, для которого требуется деление на для предотвращения переполнения. Можно ожидать, что случай входного белого шума является примером входного сигнала, находящегося где-то посередине между этими двумя крайними вариантами, т. е. масштабирование на всех этапах вычисления может в общем случае не потребоваться. Этот случай был проанализирован теоретически [19], однако его анализ является довольно сложным и здесь не приведен. Вместо этого представлены некоторые экспериментальные результаты.

На рис. 9.21 представлена зависимость выходного отношения шум/сигнал от На этом рисунке показаны экспериментально измеренные величины выходного отношения шум/сигнал для преобразований с поблочно плавающей запятой входного белого шума при использовании в арифметическом устройстве операции округления [26].

Рис. 9.21. Экспериментальные и теоретические зависимости выходного отношения шум/сигнал от при вычислении БПФ с поблочно плавающей запятой

Для сравнения также показана теоретическая кривая, представляющая согласно (9.96) отношение шум/сигнал при фиксированной запятой. Видно, что для этого типа входного сигнала использование поблочно плавающей запятой дает некоторые преимущества по сравнению с фиксированной запятой, особенно при больших преобразованиях. Для отношение шум/сигнал при поблочно плавающей запятой составляет 1/8 от отношения шум/сигнал при фиксированной запятой, что характеризует улучшение на 3 разряда. Вайнштейном (Weinstein) [26] были проведены экспериментальные исследования для проверки того, как изменятся результаты для поблочно плавающей запятой, когда вместо округления используется усечение. Результаты этого эксперимента также показаны на рис. 9.21. При этом отношение шум/сигнал, как правило, немного хуже, чем для округления. Скорость возрастания отношения шум/сигнал с увеличением представляется примерно такой же, как и при округлении.