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

UptoLike

ВУЗ: 

ВГУ | Воронеж

Составители: 

Рубрика: 

12
- сначала вычисляются N
1
преобразований
21
, nk
D
&
&
, соответствующих
N
1
различным значениям k
1
:
22
2
2
2
12121
1
0
,
nk
N
N
k
kkNnk
WsD
∑
−
=
+
=
&
&
.
Затем
21
, nk
D
&
&
умножаются на фазовые множители
21
nk
N
W
и , наконец ,
n
C
&
&
получаются вычислением N
2
N
1
– точечных преобразований :
∑
−
=
+
=
1
0
,
1
1
11
1
21
21212
1
N
k
nk
N
nk
NnknnN
WWD
N
C
&
&
&
&
.
Эти вычисления могут выполняться и в обратном порядке, при этом
сначала выполняются умножения на фазовые множители, затем - два
последовательных преобразования Фурье. В этом случае
11
1
2
2
1
1
21
121
22
2212
)(
1
1
0
1
0
nk
N
N
k
N
k
nk
NkkN
nk
NnnN
WWsW
N
C
∑∑
−
=
−
=
++
=
&
&
.
Таким образом , оба типа БПФ – алгоритма эквивалентны по
вычислительной сложности . В обоих случаях порядок индексов входного и
выходного столбцов меняется . Так, если входная последовательность
представлена N
2
полиномами с N
1
членами, то выходная
последовательность представляется N
1
полиномами с N
2
членами.
Следовательно, процедура перестановки должна быть добавлена к трем
основным шагам БПФ – алгоритма.
Эффективность БПФ – алгоритма обусловливается заменой одного
большого ДПФ на несколько малых . Так как число операций , требуемое
для прямого вычисления N – точечного ДПФ , пропорционально N
2
, то
число операций резко уменьшается при замене прямого вычисления на
серию вычислений малоточечных ДПФ . В простейшем случае прямое
вычисление N – точечного ДПФ , N=N
1
⋅N
2
, требует N
2
умножений . Если
вычислить это ДПФ с помощью БПФ – алгоритма, то число умножений
уменьшится до
M= N
1
⋅N
2
(N
1
+N
2
+1), что, очевидно, меньше N
2
1
N
2
2
. На практике БПФ –
алгоритм значительно более эффективен , так как если N – точечное
преобразование содержит большее число множителей , то алгоритм БПФ
может применяться рекурсивно. В таких случаях для описанной 
                                                               12


     - сначалавычисля ю тся N1 преобразований                                             D&
                                                                                           & , соответствую щ их
                                                                                            k1 , n 2
N1 различным значения м k1 :
                       N 2 −1
        D&
         &
          k1 , n 2 =   ∑s
                                                           k2 n2
                                N 1 k 2 + k1   WN2                 .
                       k2 =0


Затем     D&
           &
            k 1 , n 2 ум нож аю тся на ф азовые м нож ители                                              WN
                                                                                                              k1 n2
                                                                                                                      и, наконец,
C&n получаю тся вычислением N2 N1 – точечных преобразований:



                           N1 −1
     &
                           ∑ D&
                    1
    C&N 2 n1 + n2 =           &                     k1 n2          k1 n 1
                                    k1 , n2   WN            W N1            .
                    N      k1 = 0


    Э ти вычисления м огут выполня ться и в обратном поря дке, при этом
сначала выполня ю тся ум нож ения на ф азовые м нож ители, затем - два
последовательных преобразования Ф урье. В этом случае

                           N 2 −1                 N 1 −1
     &              1
    C&N 2 n1 + n2 =        ∑W                     ∑ (s
                                         k 2 n2                                 k1 n2            k1 n1
                                    N2                      N1 k 2 + k1   WN            ) W N1           .
                    N      k2 =0                  k1 = 0


     Т аким образом , оба типа БПФ – алгоритм а эквивалентны по
вычислительной слож ности. В обоих случая х поря докиндексов вх одногои
вых одного столбцов м еня ется . Т ак, если вх одная последовательность
представлена N2 полином ам и с N1 членам и, то вых одная
последовательность представля ется N1 полином ам и с N2 членам и.
Следовательно, процедура перестановки долж на быть добавлена к трем
основным ш агам БПФ – алгоритм а.
     Э ф ф ективность БПФ – алгоритм а обусловливается зам еной одного
больш ого Д ПФ на несколько м алых . Т ак как число операций, требуем ое
для пря м ого вычисления N – точечного Д ПФ , пропорционально N2 , то
число операций резко ум еньш ается при зам ене пря м ого вычисления на
серию вычислений м алоточечных Д ПФ . В простейш ем случае пря м ое
вычисление N – точечного Д ПФ , N=N1⋅N2 , требует N2 ум нож ений. Е сли
вычислить это Д ПФ с пом ощ ью БПФ – алгоритм а, то число ум нож ений
ум еньш ится до
M= N1⋅N2(N1+N2+1), что, очевидно, м еньш е N21N22. Н а практике БПФ –
алгоритм значительно более эф ф ективен, так как если N – точечное
преобразование содерж ит больш ее число м нож ителей, то алгоритм БПФ
м ож ет прим еня ться рекурсивно. В таких случая х для описанной

Страницы