Лабораторный практикум по разделу "Сигналы и спектры в системах подвижной радиосвязи" специальной дисциплины "Мобильные телекоммуникационные системы". Нечаев Ю.Б - 11 стр.

                                                                    11

эф ф ективна, чем та или иная очевидная процедура [9]. Быстрым
преобразованием Ф урье (БПФ ) называю т набор алгоритм ов, реализация
которых     обеспечивает сущ ественную      эконом ию    вычислительных
операций Д ПФ , в особенности наиболее слож ных – операций
ком плексного ум нож ения .
     В    общ ем   случае (при ком плексных         вх одных   м ассивах )
непосредственное вычисление Д ПФ по ф орм улам (1.16), (1.17) требует
прим ерно N2 ум нож ений и N2 слож ений ком плексных чисел. Э то значит,
что при больш их N непосредственное вычисление Д ПФ требует больш их
затрат м аш инного врем ени. Д ля перех ода от Д ПФ к БПФ необх одим о,
чтобы число дискретных значений сигнала было составным , то есть
разлагалось на м нож ители, к прим еру – N=8=2*2*2 или N=60=3*4*5. В
зависим ости от состава и числа м нож ителей удается получить разные
алгоритм ы БПФ . Н аиболее распространены алгоритм ы для N=2m , N=4m
или N=8m , где целое число m>0.
    Рассм отрим N – точечное Д ПФ                                    C&n , где N – составное число:

     & 1
                 N −1
                                                                                                            2π      
    C&n =        ∑s          ⋅W N                                                                W N = exp  − i     .
                                     kn
                        k                 , n=0, 1, … , (N-1);
          N      k =0                                                                                           N   
    Е сли N=N1⋅N2 , то индексы k и n м ож но преобразовать следую щ им
образом :
    k=N1⋅k2 + k1 , k1 , n1 = 0, … , (N1 – 1),
    n=N2⋅n1 + n2 , k2 , n2 = 0, … , (N2 – 1).
Подставля я k и n в выраж ение для                             C&n , получаем
                            N1 −1                                   N 2 −1
     &              1
    C&N 2 n1 + n2 =         ∑W                                      ∑s
                                          N 2 k1 n1        k1 n 2                                N1 k 2 n 2
                                     N                WN                     N 1 k 2 + k1   WN
                    N       k1 = 0                                  k2 =0


или, учитывая , что

                         2π 
                 = exp  − i      = W N 1
            N2
                                                                                              = WN 2 ,
                                                                                         N1
       WN                                                            и          WN
                             N 1 

                            N1 −1                              N 2 −1
     &              1
    C&N 2 n1 + n2 =         ∑W                                 ∑s
                                          k1 n1        k1 n2                                  k 2 n2
                                     N1           WN                     N1 k 2 + k1   WN2             .
                    N       k1 = 0                             k 2 =0


    О тсю даследует, что N1N2 – точечное Д ПФ м ож но рассм атривать как
                                                                                                                      k1 n2
Д ПФ м ассива (N1×N2), заисклю чением ф азо в ы х м но ж и телей                                                 WN           .
Т аким образом , вычисление C&
                             n выполня ется в три этапа: