Учебно-методический комплекс по дисциплине Цифровая обработка сигналов - файл n133.htm

приобрести
Учебно-методический комплекс по дисциплине Цифровая обработка сигналов
скачать (11114.3 kb.)
Доступные файлы (132):
!BaseCustomizer.exe
n2.jpg124kb.14.09.2011 15:06скачать
n5.doc1089kb.14.09.2011 15:06скачать
n6.htm328kb.14.09.2011 15:06скачать
n7.jpeg63kb.14.09.2011 15:06скачать
n8.exe
n9.ini
n10.mbd
n12.db
n13.exe
n14.inf
n15.ini
n16.jpeg48kb.14.09.2011 15:06скачать
n17.db
n19.mcd
n20.mcd
n21.mcd
n22.mcd
n23.mcd
n24.mcd
n25.mcd
n26.mcd
n27.mcd
n28.mcd
n29.mcd
n30.mcd
n31.mcd
n32.prn
n33.prn
n34.mcd
n35.mcd
n36.mcd
n37.mcd
n38.mcd
n39.mcd
n40.mcd
n41.mcd
n42.prn
n43.prn
n44.mcd
n45.mcd
n46.mcd
n47.mcd
n48.mcd
n49.mcd
n50.mcd
n51.mcd
n52.mcd
n53.mcd
n54.mcd
n55.mcd
n56.mcd
n57.prn
n58.prn
n59.mcd
n60.mcd
n61.mcd
n62.mcd
n63.mcd
n64.mcd
n65.mcd
n66.prn
n67.prn
n68.mcd
n69.mcd
n70.mcd
n71.mcd
n72.mcd
n73.mcd
n74.mcd
n75.mcd
n76.mcd
n77.prn
n78.prn
n79.prn
n80.mcd
n81.mcd
n82.mcd
n83.mcd
n84.mcd
n85.mcd
n86.mcd
n87.mcd
n88.mcd
n89.mcd
n90.prn
n91.prn
n92.mcd
n93.mcd
n94.mcd
n95.mcd
n96.mcd
n97.mcd
n98.mcd
n99.mcd
n100.mcd
n101.prn
n102.prn
n103.jpg22kb.14.09.2011 15:06скачать
n104.jpeg48kb.14.09.2011 15:06скачать
n106.htm138kb.14.09.2011 15:06скачать
n107.htm231kb.14.09.2011 15:06скачать
n108.htm386kb.14.09.2011 15:06скачать
n109.htm276kb.14.09.2011 15:06скачать
n110.htm189kb.14.09.2011 15:06скачать
n111.htm206kb.14.09.2011 15:06скачать
n112.htm94kb.14.09.2011 15:06скачать
n113.htm282kb.14.09.2011 15:06скачать
n114.htm209kb.14.09.2011 15:06скачать
n115.htm121kb.14.09.2011 15:06скачать
n116.htm97kb.14.09.2011 15:06скачать
n117.htm133kb.14.09.2011 15:06скачать
n118.htm265kb.14.09.2011 15:06скачать
n119.htm285kb.14.09.2011 15:06скачать
n120.htm236kb.14.09.2011 15:06скачать
n121.doc2344kb.14.09.2011 15:06скачать
n122.doc3719kb.14.09.2011 15:06скачать
n123.txt2kb.14.09.2011 15:06скачать
n124.jpg22kb.14.09.2011 15:06скачать
n125.jpeg48kb.14.09.2011 15:06скачать
n127.htm68kb.14.09.2011 15:06скачать
n128.htm71kb.14.09.2011 15:06скачать
n129.htm58kb.14.09.2011 15:06скачать
n130.htm186kb.14.09.2011 15:06скачать
n131.htm97kb.14.09.2011 15:06скачать
n132.htm47kb.14.09.2011 15:06скачать
n133.htm224kb.14.09.2011 15:06скачать
n134.htm61kb.14.09.2011 15:06скачать
n135.txt6kb.14.09.2011 15:06скачать
n136.ask
n137.csk
n138.ico

n133.htm

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


Дискретное Фурье преобразование (ДПФ) конечной последовательности {x(n)}0£n<N определяется как

,                         (1)

или в форме

                               (2)

где . Легко показать, что  является периодичной функцией с периодом N., т.е.

,                                (3)

Из соотношения (1) следует, что если последовательность {x(n)} является комплексной, то при прямом вычислении требуется (N-1)2 комплексных умножений и N(N-1) комплексных сложений. Основная идея БПФ состоит в том, чтобы исходную последовательность разбить на две более короткие последовательности, ДПФ которых могут быть скомбинированы таким образом, чтобы объединение их дало исходную N точечную ДПФ. Так, например, если N четное, то исходную последовательность можно разбить на две N/2 точечные последовательности, то для вычисления N точечную ДПФ потребуется (N/2) 22=N2/2 комплексных умножений, т.е. в двое меньше, чем раньше. Эту операцию можно повторить, если N/2 является четной.

Алгоритм БПФ с прореживанием по времени


Считаем, что N равно степени 2. Введем две последовательности {x1(n)} и {x2(n)}, состоящие из четных и нечетных членов {x(n)}, т.е.

                          (4)

N точечное конечное ДПФ последовательности {x(n)} можно записать как

             (5)

Выражение (5) получилось из (2), где мы отделили слагаемые с четными номерами от слагаемых с нечетными номерами исходной последовательности. Заметим, что , перепишем (5) с учетом (4) в виде

                    (6)

или

                                         (7)

где  равны N/2 точечному ДПФ последовательностей {x1(n)} и {x2(n)} соответственно.

Из (7) следует, что N точечное ДПФ может быть разложено на два N/2 точечному ДПФ, результаты которых объединяются согласно (7). Если бы N/2 точечное ДПФ вычислялось бы обычным образом, то потребовалось N2/2+N комплексных умножений. При больших N (когда N2/2 >>N) это позволяет сократить вычисления на 50%.

         Поскольку X(k) определено при 0 £k<N, а X1(k), X2(k) при 0 £k<N/2, необходимо доопределить (7) при k>N/2. Сделаем это следующим образом, используя периодичность ДПФ и тот факт, что

                       (8)

Выражение (8) описывает получение N -точечного Фурье преобразования из двух N/2 точечных Фурье. Видно, что для получения каждого коэффициента Фурье X(k) необходимо выполнить одно умножение и одно сложение (или вычитание). Почему мы выполняем только N/2 умножений на каждом шаге, а не N умножений? Давайте посмотрим на выражение (8). Запишем вычисление X(0) и X(N/2).

                                                                      (9)



Как видно из (9) X(0) и X(N/2) вычисляются почти одинаково, за исключением того, что в X(0) надо сложить, а в X(N/2) отнять одно и тоже произведение. Это произведение  можно посчитать один раз, а затем добавить и отнять к и от для получения соответственно X(0) и X(N/2). Таким образом, чтобы вычислить два коэффициента Фурье, необходимо вычислить только одно произведение.

Если мы продолжим разбиение последовательности на две последовательности и применим тот же механизм, то мы еще в два раза уменьшим количество умножений. Таким образом, на каждом шаге мы выполняем N/2 умножений, а таких шагов log2N. Число умножений равно N/2 log2N, что значительно меньше N2  (при N=1024 число умножений меньше в 100 раз).

Рассмотрим на примере 8-ми точечной последовательности, т.е. N=8. Выражение (8) можно "нарисовать " в виде


4-x точечное ДПФ
 
x1(0)=x(0)                       X1(0)                                       X(0)

x1(1)=x(2)                       X1(1)                                       X(1)

x1(2)=x(4)                       X1(2)                                       X(2)

x1(3)=x(6)                       X1(3)                                  X(3)


4-x точечное ДПФ
 
x2(0)=x(1)                       X2(0)                                  X(4)

x2(1)=x(3)                       X2(1)                                  X(5)

x2(2)=x(5)                       X2(2)                                  X(6)

x2(3)=x(7)                       X2(3)                                       X(7)

 

Рассмотренная схема может быть применена и для последовательностей {x1(n)} и {x2(n)} разбиваются четыре N/4 точечные последовательности.

   

A(k)  и B(k) N/4 точечные ДПФ от последовательностей

a(n)=x1(2n), n=0,…,N/4-1

b(n)=x1(2n+1), n=0,…,N/4-1

,

где C(k) D(k) N/4 точечные ДПФ от последовательностей

c(n)=x2(2n), n=0,…,N/4-1

d(n)=x2(2n+1), n=0,…,N/4-1

 

a(0)=x1(0)=x(0)                       A(0)                      X1(0)                              X(0)

a(1)=x1(2)=x(4)                        A(1)                      X1(1)                              X(1)

b(0)=x1(1)=x(2)                        B(0)                 X1(2)                              X(2)

b(1)=x1(3)=x(6)                        B(1)                 X1(3)                              X(3)

c(0)=x2(0)=x(1)                        C(0)                     X1(0)                        X(4)

c(1)=x2(2)=x(5)                        C(1)                     X2(1)                        X(5)

d(0)=x2(1)=x(3)                        D(0)                X2(2)                        X(6)

d(1)=x2(3)=x(7)                        D(1)                X2(3)                        X(7)

A(k). B(k), C(k), D(k) - это 2-х точечные Фурье преобразования, которые можно вычислить по формулам.





Распишем последний блок

 

a(0)=x1(0)=x(0)                       A(0)                      X1(0)                              X(0)

a(1)=x1(2)=x(4)                   A(1)                      X1(1)                              X(1)

b(0)=x1(1)=x(2)                        B(0)                 X1(2)                              X(2)

b(1)=x1(3)=x(6)                   B(1)                 X1(3)                              X(3)

c(0)=x2(0)=x(1)                        C(0)                     X1(0)                        X(4)

c(1)=x2(2)=x(5)                   C(1)                     X2(1)                        X(5)

d(0)=x2(1)=x(3)                        D(0)                X2(2)                        X(6)

d(1)=x2(3)=x(7)                   D(1)                X2(3)                        X(7)

Во всех выше приведенных схемах ключевым моментом является "бабочка", операция, которую можно представить

A                          a+bW

         W

B                          a-bW

Стрелка обозначаем умножение (в данном случае на W), направление вверх приводит к сложению (a+bW), направление вниз приводит к вычитанию (a-bW)

Алгоритм БПФ с прореживанием по частоте


В предыдущем пункте мы разбивали входную последовательность {x(n)} на две последовательности, полученные выборкой четных и нечетных элементов последовательности. Ничего не мешает нам разбить входную последовательность по другому правилу, например, выделим первую половину и обозначим ее как {x1(n)}, а вторую половину как {x2(n)}.

x1(n)=x(n),            n=0,1,..,N/2-1

x2(n)=x(n+N/2),    n=0,1,..,N/2-1                                                      (10)

Распишем, чему равно преобразование Фурье, используя соотношение (2)

        (11)

 

Выражение (11) можно рассмотреть, когда k четное и нечетное

                   (12)

Выражение (12) является быстрым преобразованием Фурье от суммы двух последовательностей x1(n) и x2(n).  Рассмотрим нечетные элементы X(2k+1)

                (13)

Выражение (13) представляет собой Фурье преобразование от последовательности вида

 

Таким образом, формулы (12), (13) представляют собой Фурье преобразование исходной последовательности, вычисленное как Фурье преобразования от двух последовательностей, составленных как сумма и разность {x1(n)} и {x2(n)}. Разность умножается на . Для того, чтобы получить ДПФ для X(k), необходимо N/2 умножение и N сложений, и плюс то, что необходимо для ДПФ N/2 - точечных последовательностей: N2/2 умножений.  Если мы и дальше будем разбивать последовательности на две части, то опять придем к тому же результату, что и для алгоритма с прореживанием по времени, т.е. число умножений можно уменьшить до .

Рассмотрим алгоритм на примере 8-ми точечной последовательности (N=8).

x1(0)=x(0)                                                                X(0)                

x1(1)=x(1)                                                                X(2)                 

x1(2)=x(2)                                                            X(4)                 

x1(3)=x(3)                                                            X(6)                 

x2(0)=x(4)                                                            X(1)                 

x2(1)=x(5)                                                           X(3)                  

x2(2)=x(6)                                                                X(5)                 

x2(3)=x(7)                                                                X(7)                 

 

Теперь рассмотрим те последовательности, которые представляли сумму и разность двух последовательностей {x1(n)} и {x2(n)}.

, n=0,1,..,N/2-1

,  n=0,1,..,N/2-1

Применим к этим последовательностям ту же схему. Пусть

f1(n)=f(n), n=0,1,..,N/4-1

f2(n)=f(n+N/4), n=0,1,..,N/4-1

g1(n)=g(n), n=0,1,..,N/4-1

g2(n)=g(n+N/4), n=0,1,..,N/2-1

Тогда преобразование Фурье от последовательности f(n) может быть записано в виде



F(k) =X(2k), т.е. четные части коэффициентов Фурье. G(k)=X(2k+1), т.е. нечетные части коэффициентов Фурье.



Выберем четные и нечетные элементы последовательности

                                               (14)



Таким образом, Фурье преобразование последовательности f(n) можно вычислить по формуле (14). Отобразим это


2-x точечное ДПФ
 
x1(0)=x(0)                                         f(0)                                                   F(0)=X(0)


2-x точечное ДПФ
 
x1(1)=x(1)                                         f(1)                                               F(2)=X(4)

x1(2)=x(2)                                     f(2)                                               F(1)=X(2)

x1(3)=x(3)                                     f(3)                                                   F(3)=X(6)


2-x точечное ДПФ
 
x2(0)=x(4)                                     g(0)                                                    G(0)=X(1)


2-x точечное ДПФ
 
x2(1)=x(5)                                     g(1)                                              G(2)=X(5)

x2(2)=x(6)                                         g(2)                                              G(1)=X(3)

x2(3)=x(7)                                         g(3)                                                  G(3)=X(7)

Наконец, раскроем 2-х точечное ДПФ по аналогии с предыдущим алгоритмом.

 

x1(0)=x(0)                                         f(0)                       f1(0)            F(0)=X(0)

x1(1)=x(1)                                         f(1)                  f1(1)       F(2)=X(4)

x1(2)=x(2)                                     f(2)                  f2(0)            F(1)=X(2)

x1(3)=x(3)                                     f(3)                       f2(1)       F(3)=X(6)

x2(0)=x(4)                                     g(0)                      g1(0)           G(0)=X(1)

x2(1)=x(5)                                     g(1)                 g1(1)      G(2)=X(5)

x2(2)=x(6)                                         g(2)                 g2(0)           G(1)=X(3)

x2(3)=x(7)                                         g(3)                      g2(1)      G(3)=X(7)

 

Бабочка в алгоритме с прореживанием по частоте имеет вид

A                 a+b

 

B       W      (a-b)W

На выходе БПФ с прореживанием по частоте имеем инвертированный порядок следования. Для того, чтобы получить правильную последовательность, необходимо переставить (инвертировать) порядок следования. В алгоритме с прореживание по времени, необходимо инвертировать входную последовательность. [kgl]

 

 

практические занятия
содержание


№7.Быстрое преобразование Фурье
Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации