Главная > Разное > Теория и применение цифровой обработки сигналов
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

10.4. Сопоставление объема вычислений при использовании  оснований 2, 4 и 8

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

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

.             (10.1)

Упрощая формулу (10.1), получим

                                                     (10.2)

При  из формулы (10.2) следует, что . Заметим, что эта формула верна также при  и , когда . Формула (10.2) справедлива, если  равно степени двойки.

2. Формулу, аналогичную (10.2), можно вывести и для БПФ с основанием 4, но в данном случае проще подсчитать количество умножений, используемых в алгоритме фиг. 10.14. На первом этапе при выполнении поворотов требуются 44 умножения, на втором — 32, а на третьем они не используются. Всего получается 76 умножений — заметно меньше по сравнению с предыдущим случаем.

3. В алгоритмах с основаниями 2 и 4 операция вычисления ДПФ не содержит умножений, т. е. все умножения являются поворачивающими. При более высоких основаниях ситуация меняется. В частности, для восьмиточечного ДПФ, выполняемого методом БПФ, в соответствии с формулой (10.2) требуются два умножения (на числа вида  и ). Таким образом, в алгоритме БПФ с основанием 8 умножения фигурируют при выполнении и ДПФ, и поворотов. На фиг. 10.15 представлен алгоритм 64-точечного БПФ с основанием 8. Он включает 16 восьмиточечных ДПФ (незачерненные кружки на фиг. 10.15), требующих 32 умножений, а также 48 нетривиальных умножений на поворачивающие множители, так что всего выполняется 32 + 48 = 80 умножений.

Фиг. 10.15. 64-точечное БПФ по основанию 8 с прореживанием повремени и с замещением.

Поэтому представляется, что основание 4 является в некотором смысле «оптимальным» по крайней мере для 64-точечных БПФ. Эту «оптимальность», конечно, не следует понимать буквально и использовать всегда только основание 4. Скорее она означает, что при разработке любой достаточно большой системы необходимо проанализировать возможность применения всех трех оснований.

 

<< Предыдущий параграф Следующий параграф >>
Оглавление