Быстрое преобразование Фурье

(по алгоритму переиндексации  на выходе одномерного алгоритма).

Рис. 2.10 иллюстрирует реализацию гнездового алгоритма БПФ для

двумерных сигналов без применения процедур кронекеровского произве-

дения матриц. У прямоугольников  проставлены размерности двумерных

таблиц, над стрелками  – номера пунктов алгоритма.

– 61 –

Представленный алгоритм для конкретной реализации требует  сле-

дующих затрат оперативной  памяти:

- двумерная таблица данных  – My1(N1) ´ My1(N2) комплексных

слов; матрицы базовых  алгоритмов предсложений и постсложений – 1 байт

на элемент матрицы;

- двумерная таблица умножений,  сформированная из диагональных

матриц базовых алгоритмов – My1(N1) ´ My1(N2) вещественных слов.

Переиндекса-

ция на входе

столбцов

исходной

таблицы и

обработка их

матрицами

предсложений

базовых

алгоритмов My1(N1)

Переиндекса-

ция на входе

строк

исходной

таблицы и

обработка их

матрицами

предсложений

базовых

алгоритмов

My1(N2)

My1(N1)

N2

My1(N1)

8, 9 6, 7

Выходная

двумерная

таблица

N1

N2

My1(N1)

My1(N2)

поэлементное

умножение

Двумерная

таблица

умножений

Bb

5

Обработка

столбцов

двумерной

таблицы

матрицами

постсложений

базовых

алгоритмов и

переиндексация

их на выходе

Обработка строк

двумерной

таблицы

матрицами

постсложений

базовых

алгоритмов и

переиндексация

их на выходе

My1(N1)

N 2 N2 My1(N2)

Исходная

двумерная

таблица

данных

N1

1, 2 3, 4

Рис. 2.10. Гнездовой алгоритм вычисления двумерного БПФ

– 62 –

По трудоемкости приведенный  алгоритм не отличается от алгоритма

с процедурами кронекеровского  произведения матриц. Предложенный ал-

горитм удобно использовать для проектирования программного обеспече-

ния спектрального анализа  и цифровой фильтрации изображений. Про-

граммное обеспечение  реализации алгоритма рассмотрено  ниже.

2.10. Оценка верхней границы ошибки реализации алгоритмов

быстрого преобразования Фурье с фиксированной арифметикой

В настоящее время архитектуры  большого класса микропроцессоров

и процессорных элементов, реализующих  операции как с плавающей, так  и

с фиксированной арифметикой, значительно дольше (как правило, в не-

сколько раз) позволяют выполнять  операции с плавающей арифметикой  по

сравнению с фиксированной. Поэтому в ряде случаев при  решении задач

цифровой обработки сигналов в реальном времени эффективно в  смысле

быстродействия реализовывать  алгоритмы БПФ с фиксированной  арифме-

тикой. Расплачиваться за уменьшение времени реализации БПФ приходит-

ся точностью представления  чисел с фиксированной точкой и большими

ошибками округления. Согласно теореме Парсеваля, средняя мощность

выходных гармоник в N раз (N длина блока данных БПФ) превышает

среднюю мощность исходной последовательности. Следовательно, значе-

ния БПФ последовательности будут, вообще говоря, существенно превы-

шать значения самой последовательности. Поэтому при использовании

арифметики с фиксированной  запятой необходимо во избежание  перепол-

нений разрядной сетки  представления чисел ввести масштабирование.

С точки зрения точности при реализации алгоритмов БПФ с  фикси-

рованной арифметикой  все комплексные числа целесообразно  представ-

лять меньшими единицы  по модулю (½x½ < 1). В работе [13] подробно

представлены проблемы оценки точности реализации алгоритмов БПФ

Кули – Тьюки с прореживанием  по времени по основанию 2 и способы

масштабирования, позволяющие  избежать переполнений. Ниже рассмот-

рены оценки точности реализации обобщенного алгоритма Кули –  Тьюки с

прореживанием по частоте  и обобщенного гнездового алгоритма  БПФ, а

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

полнения разрядной сетки  представления чисел при допустимой точности

реализации БПФ.

Авторами источнока [9] приведена  довольно простая методика рас-

чета верхних граничных  значений уровня шума округления, возникающего

при реализации БПФ с фиксированной  арифметикой. Предполагается, что

наличие шума округления обусловлено  двумя факторами:

1) появление погрешности  при округлении произведений  отсчетов

БПФ на фазовые множители. Если отсчеты БПФ и фазовые  множители

представлены s-разрядными числами (т. е. действительные и мнимые части

сомножителей содержат по s двоичных разрядов и представлены в диапа-

– 63 –

зоне [-1, 1-2-s]), то после округления каждого из четырех действительных

произведений до s-разрядного числа получается ошибка, равномерно рас-

пределенная на интервале (-2-2s, 2-2s) и имеющая нулевое среднее и диспер-

сию равную D2=2-2s/12;

2) сдвигом суммы на  один разряд вправо (деление на  два) при мас-

штабировании, если при сложении происходит переполнение разрядной

сетки представления чисел. Если отбрасываемый разряд при сдвиге равен

нулю, то ошибки не будет, если он равен единице, то в зависимости  от

знака числа возникает  ошибка величиной -2-s или 2-s. Дисперсия этой

ошибки равна 2-2s / 2 = 6 D2.

В работе [23] представлены три  метода масштабирования, позво-

ляющие избежать переполнений разрядной сетки представления  чисел, для

алгоритмов БПФ Кули –  Тьюки по основанию 2:

1) сдвиг вправо на один  разряд на каждом этапе БПФ.  Если модули

отсчетов исходной последовательности БПФ меньше 1/2 и результаты ка-

ждого этапа БПФ (кроме  последнего) сдвигаются на один разряд вправо

(делятся на два), то  переполнения не произойдет;

2) контроль последовательности, гарантирующий условие Xk(n) < 1/2

для всех n. На каждом этапе БПФ вычисляется массив Xk(n), и если хотя бы

для одного отсчета массива  не выполняется условие Xk(n) < 1/2, весь мас-

сив масштабируется сдвигом  вправо на один разряд (делением на два);

3) проверка на переполнение. При этом исходная последователь-

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

и мнимых частей были меньше единицы (а не 1/2 как в двух предыдущих

методах). Если в ходе базовой  операции фиксируется переполнение, то все

числа последовательности, включая результаты уже выполненных  на дан-

ном этапе (без переполнений) базовых операций, сдвигаются на один раз-

ряд вправо (делятся на два), после чего итерация продолжается с  той базо-

вой операции, где произошло  переполнение.

Первый метод связан с  наименьшими затратами времени  и наиболее

прост в реализации. Однако он дает наименьшую точность, так как  мас-

штабирование на каждом этапе  приводит к ненужному ухудшению  точно-

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

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

так как весь массив всегда масштабируется таким образом, чтобы  модули

всех его элементов  были бы меньше 1/2, поэтому один двоичный разряд

памяти данных не используется. Третий метод является самым точным, но

здесь приходится повторно обрабатывать всю последовательность отсче-

тов БПФ, когда обнаруживается переполнение.

Ниже рассмотрены вопросы  оценки точности реализации обобщен-

ного алгоритма Кули –  Тьюки с прореживанием по частоте  и обобщенного

гнездового алгоритма  БПФ, а также выбор способов масштабирования, по-

– 64 –

зволяющих избежать разрядной  сетки представления чисел при  допусти-

мой точности реализации БПФ.

2.10.1. Обобщенный алгоритм  БПФ по смешанным основаниям

Рассмотрим приведенный  в подразд. 2.7 обобщенный алгоритм БПФ

по смешанным основаниям в режиме замещения (2.36), (2.37).

Очевидно, что увеличение модулей значений отсчетов БПФ возмож-

но только при выполнении rk -точечных ДПФ в выражении (2.37). При

этом максимально модули отсчетов могут быть увеличены в rk раз. Умно-

жение на фазовые множители, не изменяя модулей отсчетов, может  увели-

чивать их действительные или мнимые части. Учитывая выше сказанное,

приведем три метода масштабирования, аналогичных [23], но позволяю-

щих реализовывать алгоритмы  БПФ по смешанным основаниям:

1) деление на rk на каждом этапе БПФ. Если модули отсчетов исход-

ной последовательности БПФ  меньше 1/r0 и результаты каждого этапа

БПФ (кроме последнего) делятся  на rk + 1, то переполнения не произойдет;

2) контроль последовательности, гарантирующий условие

Xk-1(n) < 1/rk для всех n. На каждом этапе БПФ вычисляется массив Xk(n), и,

если хотя бы для одного отсчета массива не выполняется  условие Xk-1(n) <

1/rk, все элементы массива делятся на rk;

3) проверка на переполнение. При этом исходная последователь-

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

и мнимых частей были меньше единицы (а не 1/rk, как в двух предыдущих

методах). Если в ходе базовой  операции фиксируется переполнение, то все

числа последовательности, включая результаты уже выполненных  на дан-

ном этапе (без переполнений) базовых операций, сдвигаются на один раз-

ряд вправо (делятся на два), после чего итерация продолжается с  той базо-

вой операции, где произошло  переполнение. При этом переполнения на

каждом этапе могут  возникать тем чаще, чем больше основание этапа rk.

В смысле точности наилучшим  опять является третий метод, отли-

чающийся наибольшей трудоемкостью.

На практике для обеспечения  меньшей трудоемкости алгоритма  БПФ

по смешанным основаниям часто выбирают основания, равные степени

двойки rk = (2, 4, 8, 16). Это дает выигрыш в трудоемкости и при масшта-

бировании. Деление на rk можно заменить сдвигом делимого вправо на

log2[rk] двоичных разрядов. Далее, при исследовании обобщенного алго-

ритма БПФ по смешанным  основаниям, будут рассматриваться  только эти

основания.

Если основания алгоритма  являются степенями двойки, то упроща-

ется оценка точности реализации БПФ по смешанным основаниям с  фик-

сированной арифметикой. Предположим, что rk-точечные ДПФ (2.33) ба-

зовой операции алгоритма  выполняются по алгоритму БПФ (2.32) – (2.34)

по основанию 2. Тогда, с  точки зрения точности реализации (ошибок ок-

– 65 –

ругления), алгоритм (2.32) – (2.34) по смешанным основаниям ничем не

будет отличаться от алгоритма  Кули – Тьюки с прореживанием  по частоте

по основанию 2. При этом трудоемкость алгоритма (2.32) – (2.34) по сме-

шанным основаниям может  быть ниже трудоемкости алгоритма Кули –

Тьюки по основанию 2.

При оценке верхней границы  дисперсии ошибки округления полага-

ют, что переполнения (при  основании алгоритма 2) происходят на каждом

этапе алгоритма БПФ. Обозначим  за k не номер этапа БПФ, а номер пере-

полнения разрядной сетки  представления чисел, возникшего при  реализа-

ции алгоритма БПФ по смешанным  основаниям (2.32) – (2.34). Тогда вы-

ражение для k-й дисперсии ошибки округления (Dk) можно записать (2.57)

Dk = Dk-1 + 4k(ak D2 + 6 D2), (2.57)

где ak = [0, 1] – коэффициент, учитывающий долю отсчетов этапа БПФ,

которые необходимо умножать на фазовые множители при возникновении

переполнения. Если предположить, что j-е переполнение происходит на

k-м этапе БПФ, выражение для ak можно записать

ï ï ï

î

ïï ï

í

ì

-

-

a =

на фазовыемножители,

если переполнение возникло при умножении

точечногоДПФ;

0, если переполнение возникло  при выполнении

N

N

r

k

k

k

где Nk – количество отсчетов k-го этапа БПФ, которые нужно умножать на

фазовые множители. Тривиальные  умножения на мнимую и действитель-

ную единицы можно не учитывать; N – размерность блока данных БПФ.

Предлагаемое определение ak становится приближенным, если осно-

ваниями алгоритма являются числа 8, 16, так как 8- и 16-точечные алго-

ритмы БПФ содержат умножения  на фазовые множители. Однако точность

оценки дисперсии ошибки округления на основе (2.57) согласуется  с экс-

периментальными оценками, получаемыми при цифровом моделировании

алгоритма БПФ для смешанных  оснований с прореживанием по частоте

для операндов с фиксированной  запятой. Начальное значение дисперсии

D-1 = 0.

Выражение (2.43) получено, исходя из следующих положений:

1) при каждом переполнении  происходит масштабирование (сдвиг

вправо на один разряд) всех отсчетов БПФ. Поэтому дисперсия  ошибки

предыдущего переполнения включается в дисперсию ошибки текущего

переполнения;

2) в связи с тем, что  ошибка округления как при  масштабировании

(дисперсия – 6 D2), так  при умножении на фазовые множители  (дисперсия

– D2) при переполнении увеличивается  в два раза, их дисперсия должна

увеличиться в четыре раза.

– 66 –

Для определения верхней  границы дисперсии ошибки округления

для алгоритма (2.32) – (2.34) положим, что переполнения разрядной сетки

представления чисел на каждом этапе БПФ происходят максимально  воз-

можное число раз.

Учитывая, что все основания  алгоритма БПФ равны степеням двой-

ки, и все rk-точечные ДПФ (при rk > 2) выполняются по алгоритму (2.32) –

(2.34), выражение для 2-точечных  ДПФ примет вид b[0] = a[0] + a[1], b[1]

= a[0] - a[1]. Из выражения (2.33) умножения на фазовые множители легко

исключить тривиальные умножения  на 1. Это соответствует условию, ко-

гда l = 0 или j = 0. Если N-точечный алгоритм БПФ выполняется достаточ-