4.4. Вывод алгоритма

Вывод алгоритма [7, 8] наиболее нагляден при , поэтому запишем

(4.4.1)

где . Выразим в двоичной системе счисления

(4.4.2)

Из (4.3.2), (4.4.1) и (4.4.2) следует, что

(4.4.3)

В выражении (4.4.3) внутреннее суммирование по обозначим через , что записывается как

Подставляя в это выражение двоичное представление k и учитывая, что , получим

Поскольку значение можно записать в виде

(4.4.4)

В выражении (4.4.4) суммирование по приводит к величине, которая является функцией и . Поэтому вводится обозначение

(4.4.5)

Подстановка (4.4.5) в выражение (4.4.3) дает

(4.4.6)

Вновь рассмотрим внутреннее суммирование в (4.4.6) и обозначим его через что запишем в виде

(4.4.7)

В выражении (4.4.7) , и поэтому запись упрощается:

(4.4.8)

Суммирование по в (4.4.8) приводит к функции, зависящей от , т.е.

(4.4.9)

Подставляя (4.4.9) в (4.4.6), получаем

Обозначим суммирование по через , что можно записать в виде

Рассмотрение формулы (4.4.10) приводит к выводу, что дальнейшее упрощение невозможно. Суммирование по , как и ранее, приводит к функции, зависящей от и , которую обозначим через , т. е.

(4.4.11)

Это означает, что

(4.4.12)

и, следовательно, (4.4.5), (4.4.9) и (4.4.11) позволяют выполнить действия, необходимые для получения коэффициентов ДПФ . Однако остается неясным, как в дальнейшем пользоваться этими формулами. В качестве первого шага для ответа на этот вопрос сделаем два замечания.

1. При получаем такие формулы.

2. Коэффициенты и в этих формулах выражаются через корень из единицы, . Очевидно, что и являются соответственно корнями 2, 4 и 8-й степени из единицы. Поэтому введем обозначение

(4.4.13)

где является -м первообразным корнем из единицы. Непосредственно можно показать, что обладают следующими свойствами:

(4.4.14а)

(4.4.14б)

где ;

(4.4.14в)

Теперь выражение (4.4.5) можно записать с помощью

Откуда

(4.4.15)

В (4.4.15) может принимать значение 0 или 1. Соответственно для каждого значения запишем по четыре уравнения при переменных и .

Случай 1:

(4.4.16а)

Случай 2:

(4.4.16б)

Приведенная последовательность сложений и вычитаний, показанная на рис. 4.1, обозначена как итерация , что соответствует

Рис. 4.1. Граф БПФ при N=8

в (4.4.13). Формула (4.4.9) с помощью также записывается в виде

В результате получаем по два уравнения для каждого значения . Так как принимает четыре значения, то рассмотрим следующие четыре случая:

Случай 1:

(4.4.17а)

Случай 2:

(4.4.17б)

Случай 3:

Случай 4:

Последовательность арифметических операций в обозначается как итерация на рис. 4.1, что соответствует в (4.4.13). Наконец, формулу (4.4.11) с помощью запишем в виде

(4.4.18)

что приводит к следующим случаям.

Случай 1:

Случай 2:

(4.4.19б)

Случай 3:

Случай 4:

Случай 5:

Последовательность арифметических операций в (4.4.19а)-(4.4.19), показанная на рис. 4.1, обозначена как итерация #3, что соответствует в (4.4.13). Для получения желаемых значений вспомним, что

(4.4.20)

Двоичные коэффициенты и появляются в в инвертированном порядке, в отличие от , где они появляются в естественном порядке. Такой порядок называется двоичной инверсией. Итак, связаны с следующим образом:

(4.4.21)

Остальные коэффициенты могут быть получены как , т. е. и . Коэффициенты и могут быть вычислены по (4.4.22) и (4.4.18) следующим образом:

(4.4.22)

Арифметические операции, приведенные в (4.4.22), показаны в итерации #3 на рис. 4.1 штриховыми линиями. Рисунок 4.1 представляет собой граф БПФ для .

Примечания. В отношении приведенного выше графа БПФ можно сделать следующие выводы.

1. Максимальное значение индекса итерации определяется как при .

2. В итерации, , используются следующие множители .

(4.4.23)

При в итерации используются множители . Так как , то в этой итерации осуществляются только сложения и вычитания. При в итерации используются множители и при в итерации — множители и .

3. На итерации промежуточный массив содержит групп по величин в каждой группе. Для каждой группы используется один множитель вида . Половина величин, входящих в группу, связывается с , а остальные с .

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

Таблица 4.4.1

5. , соответствующие каждому , получают следующим образом:

а) выражают последовательность в двоичной форме 000, 001, 010, 011, 100, 101, 110, 111;

б) осуществляют двоичную инверсию каждой трехразрядной двоичной последовательности, указанной в п. "а": 000, 100, 010, 110, 001, 101, 011, 111;

в) записывают двоичную последовательность, приведенную в п. "б", в виде десятичных чисел 0, 4, 2, 6, 1, 5, 3, 7.

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

6. Все операции, связанные с вычислением и , действительные. Таким образом, и являются действительными числами, что согласуется со свойством комплексной сопряженности ДПФ.

7. Если действительные и мнимые части считать отдельно, то числу величин исходного массива данных при будет точно соответствовать 8 независимых величин, входящих в .

8. Выходные величины итерации можно хранить в тех же ячейках памяти, что и величины исходного промежуточного массива данных. Чтобы подтвердить это положение, рассмотрим, например, выходные величины итерации и . Ясно, что и могут храниться в двух рабочих ячейках и , что записывается как и . Поскольку и в дальнейших вычислениях, проводимых на итерации, не используются, содержимое ячеек и можно записать в ячейки, в которых хранились и . Таким образом, и хранятся в ячейках, ранее использованных для хранения и . Также хранятся в ячейках соответственно. Эта же процедура используется при перезаписи величин промежуточного массива в ячейки, где до этого хранились величины , и так далее. Это свойство графа БПФ, изображенного на рис. 4.1, называется «вычислением на месте» [1]. В этом случае не требуется дополнительных ячеек оперативной памяти для хранения различных промежуточных массивов.

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

9. Общее число арифметических операций (т. е. умножений с последующим сложением или вычитанием), необходимых для получения всех , равно примерно .

10. Алгоритм БПФ не зависит от того, являются исходные величины действительными или комплексными. Следовательно, он может быть использован для вычисления ОДПФ с незначительными изменениями, которые следуют из (3.1.4) и (4.1.1):

W заменяется на ;

опускается множитель , стоящий после последней итерации.

Такая модификация алгоритма БПФ будет в дальнейшем именоваться обратным быстрым преобразованием Фурье (ОБПФ).

11. Множители, используемые в графе БПФ, могут быть выражены непосредственно через степени W в соответствии с тем, что . Ниже (пример 4.5.4) показано, что соответствующий граф БПФ может быть построен непосредственно с использованием степеней W с помощью простого правила.