11.3. БЫСТРЫЕ ПРЕОБРАЗОВАНИЯ ФУРЬЕ

Дискретное преобразование Фурье (ДПФ) в той форме, как оно задается:

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

Рис. 11.8. (см. скан) Некоторые алгоритмы БПФ.

Фурье в двумерное преобразование или в нечто ему подобное. С вычислительной точки зрения это приводит к существенно более эффективной форме, хотя понять ее структуру труднее. Алгоритмы подобного рода известны под общим названием быстрого преобразования Фурье Некоторые рассматриваемые в этом параграфе алгоритмы, а именно алгоритм Кули-Тьюки и алгоритм Гуда-Томаса, приведены на рис. 11.3.

Начнем с БПФ-алгоритма Кули-Тьюки. Предположим, что . В выражении для преобразования Фурье сделаем следующую перестановку входных и выходных символов:

Тогда

Раскроем скобки в показателе степени и положим Так как порядок элемента а равен пп то член можно опустить. Определим теперь двумерные переменные, которые также обозначим через и V, задавая их равенствами

Это задает отображение входного и выходного векторов данных в двумерные таблицы, причем

Хотя эта формула сложнее исходной, число сложений и умножений при вычислении по ней гораздо меньше, а именно требуется не более умножений по сравнению с необходимых в исходном варианте. Заметим, что при каждом значении внутренняя сумма представляет собой -точечное преобразование Фурье и при каждом значении внешняя сумма представляет собой -точечное преобразование Фурье. Если соответствующая длина является составным числом, то каждое из этих преобразований в свою очередь можно упростить с помощью быстрого преобразования Фурье. Преобразование длины с делителями таким образом представляется в форме, требующей около умножений.

БПФ-алгоритм Кули-Тыоки можно наглядно представить в виде отображения двумерной таблицы в двумерную таблицу, пример которого для приведен на рис. 11.4. Преобразование Фурье сначала применяется к каждой строке, а затем к каждому столбцу. Перед применением преобразования Фурье к столбцам производится поэлементное умножение. Отметим, что компоненты спектра упорядочены иначе, чем компоненты

сигнала. Таксе упорядочение называется перестановкой адресов. Поля Галуа, в которых преобразование Фурье вычисляется наиболее просто, имеют вид где число является простым. Известно, что если не является степенью двойки, то не является простым числом. Обратное утверждение

Рис. 11.4. (см. скан) Примеры переиндексации.

неверно, так как известно, что число является составным. Но для и 16 числа и 65 537 являются простыми и известны под названием простых чисел Ферма. В поле Галуа где простое число Ферма, все делители числа включая и само это число, являются степенью двойки. Преобразование Фурье

существует для всех делящих всех элементов а, порядок которых равен Таким образом, в поле существуют преобразования Фурье длин, равных Построенный в таком поле систематический код Рида-Соломона может быть превращен в двоичный код, исправляющий пакеты ошибок. Этот код можно использовать для систематического кодирования -битовых байтов; одно из значений запрещается использовать в качестве информационных символов. Проверочные символы принимают значений, так что для их двоичною представления требуется битов.

Так как в поле порядок элемента 2 равен 32, то преобразование Фурье длины не более 32 является чрезвычайно простым. Чтобы показать это, заметим, что в поле справедливо равенство так что Преобразование Фурье имеет вид

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

где а — элемент порядка 1024. БПФ-алгоритм Кули-Тыоки приводит эту формулу к виду

Внутренняя сумма при каждом является -точечным преобразованием Фурье, а внешняя сумма является -точечным преобразованием Фурье при каждом Только со степенью элемента а связаны нетривиальные умножения, но их число равно 1024. В общем случае для вычисления преобразования Фурье в поле требуется около умножений в этом поле, (1/2) и сложений и сдвигов.

Другим алгоритмом БПФ является алгоритм Гуда-Томаса для взаимно простых делителей. По сравнению с алгоритмом Кули-Тыоки он немного сложнее в принципе, но и немного проще в вычислительном отношении. В алгоритме Гуда-Томаса форма переиндексации линейного массива в двумерную (я X -таблицу, позволяющая вычислять одномерное преобразование Фурье с помощью двумерного преобразования Фурье, отличается от формы переиндексации в алгоритме Кули-Тьюки. Алгоритм Гуда-Томаса по идее существенно отличается от алгоритма Кули-Тьюки. В нем и предполагаются взаимно простыми, и в основе отображения лежит китайская теорема об остатках. Способ упорядочения данных иллюстрируется рис. 11.4. Упорядочение начинается с левого верхнего угла таблицы, и компоненты записываются вдоль продолжения диагонали. Так как число строк и число столбцов взаимно просты, то продолженная диагональ пройдет через все элементы таблицы. После выполнения двумерного преобразования Фурье компоненты спеитра выписываются в двумерной таблице в другом порядке.

БПФ-алгоритм Гуда-Томаса основан на китайской теореме об остатках для целых чисел. Входные индексы определяются саоими вычетами по правилу

задающему отображение входного индекса в пару индексов лежащих на продолженной диагонали двумерной таблицы. Согласно китайской теореме об остатках, существуют целые числа такие, что

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

Выходные индексы упорядочиваются несколько иным способом. Определим

В эквивалентном виде это можно записать так:

Тогда выходной индекс можно вычислить следующим образом:

Чтобы проверить это, запишем

При такой переиндексации формула принимает вид

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

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

Для выполнения преобразования Фурье можно выбрать как алгоритм Кули-Тьюки, так и алгоритм Гуда-Томаса. Иногда возможно даже использование обоих алюритмов одновременно. Например, используя БПФ-алгоритм Гуда-Томаса, можно

разбить -точечное преобразование на -точечпое и -точечное, а затем, используя БПФ-алгоритм Кули-Тьюки, свести 9 точечное преобразование к двум -точсчным. Организованное так вычисление будет аналогично -точечному трехмерному преобразованию Фурье.