Электронные промышленные устройства. Кузнецов Б.Ф. - 18 стр.

18

ции, а время запаздывания готовности результатов уменьшается в N раз по сравнению с рассмот-
ренным ранее случаем.


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

       Можно предложить такие вычислительные процедуры, которые позволили бы существенно
сократить число требуемых вычислительных операций, учитывая конкретные особенности ис-
пользуемой системы базисных функций. Широко используется быстрое преобразование Фурье
(БПФ) - вычислительный алгоритм, обеспечивающий быстрое и эффективное вычисление ДПФ.
Идея БПФ заключается в том, что анализируемая выборка дискретных данных путем прорежива-
ния по времени разбивается на две (или более) промежуточные выборки и спектр сигнала выража-
ется через спектры этих выборок. Полагая        целой степенью числа 2, включим в первую выборку
дискретные отсчеты сигнала с четными номерами, т. е. x (0), x (2ў t), x (4ў t), x ((N Ў 2) ў t), а во
вторую - отсчеты с нечетными номерами, т.е. x (ў t), x (3ў t), x ((N Ў 1) ў t), Тогда спектры этих
выборок:
                                      N / 2Ў 1               µ          ¶
                             ( 1)   2 X                         j 4k1 i
                            ck 1 =             x (2i ў t) exp Ў
                                   N i= 0                         N      ,
                                          N /P2Ў 1                       і          ґ
                              (2)
                             ck 1 =   2
                                      N              x ((2i + 1) ў t) exp Ў j 4k
                                                                               N
                                                                                 1i
                                                                                      ,           (1.16)
                                           i= 0
где k 1 не превышает числа N / 2, т. е. k1 2 [0; N / 2]. Искомые коэффициенты:
                                                 µ          ¶       ё
                                 1 (1)               j 2ј k1 (2)
                          ck =       c + exp Ў                 ck 1    k = k1
                                 2 k1                   N                     ,
                                        µ                     ¶      ё
                        1 (1)               j 2ј (k1 + N / 2) (2)
                  ck =     c + exp Ў                            ck 1    k = k1 + N / 2
                        2 k1                       N
           Используя следующее свойство комплексной экспоненциальной функции:
                                                                                          ,

можно переписать последние соотношения:




                                                                                              ,
или, с учетом введенных обозначений,

                                                                          ;

                                                                    ;                 .

      При вычислении N коэффициентов ck по (1.14) требуется выполнить N 2 операций сложе-
                                                                                      ±
ния и N 2операций умножения, тогда как при использовании (1.16), (1.17) достаточно N 2 2 + N
                       ±
операций сложения и N 2 2 + N операций умножения.
                                                                                  ±
      Следовательно, общее число арифметических операций уменьшается в 2N 2 2 + N раз,
вдвое сокращается и число требуемых отсчетов базисных функций (весовых коэффициентов w Nk 1).
                                                                                                     (1)
Аналогичным образом снижается объем расчетов и при вычислении промежуточных спектров ck1
     (2)
и ck2 . В пределе каждая промежуточная выборка содержит лишь два отсчета сигнала, а общее чис-