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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

13
двухфакторной процедуры каждый множитель N
1
и N
2
сам представляет
составное число и, следовательно, N
1
- и N
2
– точечные ДПФ снова
вычисляются с помощью БПФ – алгоритма. При таком подходе каждый
шаг рекурсивного применения БПФ уменьшает число операций , в
результате чего эффективность алгоритма возрастает, если N содержит
большое число сомножителей . Это обстоятельство и желание иметь
достаточно регулярную структуру БПФ – алгоритма обусловливают
особое внимание к использованию его к входным последовательностям ,
длина которых – степень целого числа. Как правило, выбирается степень
двойки.
Рассмотрим ДПФ
n
C
&
&
последовательности s
k
длиной N=2
m
. В этом
случае первый шаг БПФ выполняется при N
1
=2 и N
2
=2
m-1
, что
эквивалентно разбиению N – точечной последовательности s
k
на две (N/2)
– точечные последовательности s
2k
и s
2k+1
, соответствующие четным и
нечетным отсчетам s
k
. При этом
)(
1
2
1
2
0
12
1
2
0
2
2
nk
N
N
k
k
N
k
n
N
nk
Nkn
WsWWs
N
C
∑∑
−
=
+
−
=
+⋅=
&
&
(1.18)
и, так как
1
2
−=
N
N
W
, то
.1
2
,...,0),(
1
2
1
2
0
12
1
2
0
2
2
2
−=−⋅=
∑∑
−
=
+
−
=
+
N
nWsWWs
N
C
nk
N
N
k
k
N
k
n
N
nk
NkN
n
&
&
При таком способе, называемом прореживанием по времени , N–
точечное ДПФ сводится к двум N/2 – точечным ДПФ , N сложениям и N/2
умножениям на
n
N
W
. Эта же процедура применяется теперь для
замены двух N/2 – точечных ДПФ на четыре N/4 – точечных ДПФ , N
сложений и N/2 умножений . Последовательное применение метода
вычисления N– точечных ДПФ , N=2
m
, приводит к m=log
2
N, на каждом из
которых 2
p
2
m-p
- точечных ДПФ сводится к 2
p+1
2
m-p-1
– точечным ДПФ
за N сложений и N/2 умножений . Следовательно, число комплексных
умножений М и число комплексных сложений А , требуемых для
вычисления N– точечного ДПФ по основанию 2, таковы :
M=(N/2)log
2
N, A=Nlog
2
N.
Другая форма БПФ – алгоритма получается разбиением входной
последовательности s
k
на две части - s
k
и s
k+N/2
– из N/2 членов,
соответствующих N/2 первым и N/2 последним отсчетам s
k
. Этот метод
называется прореживанием по частоте. При этом 
                                      13

двух ф акторной процедуры каж дый м нож итель N1 и N2 сам представля ет
составное число и, следовательно, N1 - и N2 – точечные Д ПФ снова
вычисля ю тся с пом ощ ью БПФ – алгоритм а. При таком подх оде каж дый
ш аг рекурсивного прим енения БПФ ум еньш ает число операций, в
результате чего эф ф ективность алгоритм а возрастает, если N содерж ит
больш ое число сом нож ителей. Э то обстоя тельство и ж елание им еть
достаточно регуля рную структуру БПФ – алгоритм а обусловливаю т
особое вним ание к использованию его к вх одным последовательностя м ,
длина которых – степень целого числа. К ак правило, выбирается степень
двойки.
    Рассм отрим Д ПФ C&                                       m
                         n последовательности sk длиной N=2 . В этом
случае первый ш аг БПФ выполня ется при N1=2 и N2=2m-1, что
эквивалентно разбиению N – точечной последовательности sk надве (N/2)
– точечные последовательности s2k и s2k+1 , соответствую щ ие четным и
нечетным отсчетам sk . При этом
              N                      N
                −1                     −1

    C&
              2                      2
     & = 1 ( s ⋅W 2 k n + W n
            ∑              N ∑ s 2 k +1W N
                                           2k n
      n         2k N                            )                       (1.18)
         N k =0               k =0

                 N
и, таккак   WN       2   = −1 , то
                     N                      N
                       −1                     −1
     &       1       2                      2
    C&n + N = ( ∑ s 2 k ⋅W N      − W N ∑ s 2 k +1W N ), n = 0, ... , N − 1 .
                             2k n      n             2k n

           2 N k =0                      k =0
                                                                       2

    При таком способе, называем ом про реж и в ани ем по в рем ени , N–
точечное Д ПФ сводится к двум N/2 – точечным Д ПФ , N слож ения м и N/2
                             n
ум нож ения м на    W N . Э та ж е процедура прим еня ется теперь для
зам ены двух N/2 – точечных Д ПФ на четыре N/4 – точечных Д ПФ , N
слож ений и N/2 ум нож ений. Последовательное прим енение м етода
вычисления N– точечных Д ПФ , N=2m, приводит к m=log2N, на каж дом из
которых 2p 2m-p - точечных Д ПФ сводится к 2p+1 2m-p-1 – точечным Д ПФ
за N слож ений и N/2 ум нож ений. Следовательно, число ком плексных
ум нож ений М и число ком плексных слож ений А , требуем ых для
вычисления N– точечного Д ПФ по основанию 2, таковы:
    M=(N/2)log2N, A=Nlog2N.
    Д ругая ф орм а БПФ – алгоритм а получается разбиением вх одной
последовательности sk на две части - sk и sk+N/2 – из N/2 членов,
соответствую щ их N/2 первым и N/2 последним отсчетам sk. Э тот м етод
называется про реж и в ани ем по час то те. При этом

Страницы