Дикарев А. В. По основам цифрой обработки сигналов киев 2014



Сторінка2/7
Дата конвертації15.04.2016
Розмір1.78 Mb.
1   2   3   4   5   6   7

X3 = w0 w3 w6 w9 w12 w15 w18 w21 * f3


X4 w0 w4 w8 w12 w16 w20 w24 w28 f4

X5 w0 w5 w10 w15 w20 w25 w30 w35 f5

X6 w0 w6 w12 w18 w24 w30 w36 w42 f6

X7 w0 w7 w14 w21 w28 w35 w42 w49 f7

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

Примем во внимание линейную и круговую периодичность и взаимное соответствие N≡2π, N/2≡π, N/4≡π/2, N/8≡π/4 и т.д., откуда вытекает периодичность степенного ряда поворачивающего множителя w при различных кратностях N выборок на периоде 2π (рис.1).

w22, w14, w6

j

w21, w13, w5, –3π/4 w7, w15, w23, π/8


w20, w12, w4,-1 w0, w8, w16, 1

Re


w9, w11, w3, 5π/8 w1, w9, w17, π/8

φ= 2π/8


w2, w10, w18, –j

Рис. 1.13. Степенной ряд поворачивающих множителей w


Какой же вывод можно сделать из рисунка степенного ряда w? Все значения поворачивающего множителя w, начиная с w8, равны ТОЛЬКО соответственному значению w в интервале от w0 до w7. Если остаток от деления на 8 показателя w “n” записать как n mod 8, то значения показателей степени w(n) после понижения их значений можно представить как

w(n)=w(n mod 8).

В частности, 8 mod 8=0, 9 mod 8=1, 10 mod 8=2, 11 mod 8=3 и т.д. Тогда через показатели степени матрица Фрэнкса записывается следующим образом:

X0 w0 w0 w0 w0 w0 w0 w0 w0 f0

X1 w0 w1 w2 w3 w4 w5 w6 w7 f1

X2 w0 w2 w4 w6 w0 w2 w4 w6 f2

  1. X3 = w0 w3 w6 w1 w4 w7 w2 w5 * f3


X4 w0 w4 w0 w4 w0 w4 w0 w4 f4

X5 w0 w5 w2 w7 w4 w1 w6 w3 f5

X6 w0 w6 w4 w2 w0 w6 w4 w2 f6

X7 w0 w7 w6 w5 w4 w3 w2 w1 f7

Быстрое преобразование Фурье – это алгоритм эффективного вычисления коэффициентов разложения на основании закономерностей, скрытых в матрице Фрэнкса при последующем понижении степени n на каждом шаге в два раза, в частности от n=27=128 к n=26=64, от n=26=64 к n=25=32, от n=25=32 к n=24=16, от n=24=16 к n=23=8 и от n=23=8 к n=22=4, которую можно считать БАЗОВОЙ. В этом случае выборка состоит из четырех членов f0, f1, f2, f3. Рассмотрим особенности БПФ для этого базового случая.


1.20.1. БПФ для ряда из четырёх членов
Для указанного случая с учетом рис.1.13 – степенного ряда нормированных частот w для N=4 - ДПФ можно выразить в виде произведения матрицы Фрэнкса на вектор сигнала следующим образом:

Im j w7, w3

w6, w2 w0, w4, w8

-1 1
-j w1, w5, w9

Рис. 1.14. Степенной ряд w для N=4
X0 w0 w0 w0 w0 f0

X1 = w0 w1 w2 w3 * f1

X2 w0 w2 w4 w6 f2 (1.34)

  1. X3 w0 w3 w6 w9 f3


Учитывая структуру и знак “минус” в поворачивающем множителе , легко понять соответствия между углом сдвига φ и поворачивающим множителем w, которые приведены в нижеследующей матрице Френкса для N=4 (3):

  • n=0 соответстует углу поворота поворачивающего множителя φ=0 или в радианах ω=1 и w0, w4, w8;

  • n=1 соответстует φ=2π*1/4, ω=j, w3, w7;

  • n=2 соответстует φ=2π*2/4, ω=-1, w2, w6;

  • n=3 соответстует φ=2π*3/4, ω=-j, w1, w5, w9.

В результате таких замен матрица Фрэнкса приобретает вид:

X0 1 1 1 1 f0

X1 = 1 -j -1 j * f1 (1.35)

X2 1 -1 1 -1 f2
  1. X3 1 j -1 -j f3

Дальнейшие упрощения сводятся к следующему. Матрица (1.353) делится на 2 матрицы, а именно, матрицу, которая содержит нечетные столбцы исходной матрицы, и матрицу, содержащую четные столбцы исходной матрицы (вектор вырезок сигнала f(k) для иллюстрации соответствий приходится в виде матрицы-строки писать вверху, что не соответствует принятым правилам векторно-матричных преобразований):



[ f0 f2 ] [ f1 f3 ]

X0 w0 w0 w0 w0

X1 = w0 w2 + w1 w3

X2 w0 w4 w2 w6 (1.36)
  1. X3 w0 w6 w3 w9


На основании равенства становится возможным в (1.36) выполнить следующие преобразования:




[ f0 f2 ] [ f1 f3 ]

X0 w0 w0 w0w0 w0w0

X1 = w0 w2 + w1w0 w1w2

X2 w0 w4 w2w0 w2w4
  1. X3 w0 w6 w3w0 w3w6


или

[ f0 f2 ] [ f1 f3 ]

X0 w0 w0 w0 w0 w0

X1 = w0 w2 + w1 w0 w2

X2 w0 w4 w2 w0 w4 (1.37)
  1. X3 w0 w6 w3 w0 w6

На основании рис.2 разные степени поворачивающего


При этом надо учесть следующие соответствия:

w4=w0=1, w6=w2= -1, w2= -w0, w3=w1. (*)

После подстановки этих значений поворачивающего множителя в (6) имеем:



[ f0 f2 ] [ f1 f3 ]

X0 1 1 w0 1 1

X1 = 1 -1 + w1 1 -1

X2 1 1 -w0 1 1 (1.38)
  1. X3 1 -1 -w1 1 -1

Для дальнейшего объяснения алгоритма БПФ воспользуемся методом полной индукции: последующего перехода от БПФ для N=4 к БПФ для N=8 и нахождения имеющихся при этом аналогий.


1.20.2. Операциябабочкадля БПФ ряда из четырёх членов
Рассмотрим выражения ДПФ для Х(k) при N=4 и первой части этих выражений поставим в соответствие операцию “бабочка”:

(1.39)

Эти же выражения после подстановки соответствий поворачивающего множителя из предыдущих преобразований:



(1.40)

Соответствия между элементами четных и нечетных столбцов матрицы (7) и первыми двумя слагаемыми последних равенств и выражаются первой операцией “бабочка”:

+1

f(0) +1 +1 f(0)+w0f(0)



f(2) w0 -1 f(0)-w0f(0)

f(1) +1 f(1)+w0f(3)

+1 +1

f(3) w0 - f(1)-w0f(3) -1


Рис. 1.15. Первая “бабочка” для N=4

f(0) X(0)=f(0)+w0f(2)+w0f(1)+w0f(3)

f(2) w0 X(1)=f(0)-w0f(2)+w1f(1)-w0w1f(3)

-1

w0



f(1) -1 X(2)=f(0)+w0f(2)-w0f(1)-w0w1f(3)
f(3) w1 X(3)=f(0)-w0f(2)-w1f(1)+w0w1f(3)h

-1 -1


Рис. 1.16. Вторая “бабочка” для N=4
Таким образом, БПФ из ДПФ получается за счет того, что группируются столбцы с четными и нечетными показателями степени поворачивающего множителя, приводятся к одинаковому виду и программная обработка их приводит к одинаковову результату. Для иллюстрации общности метода БПФ перейдем к рассмотрению алгоритма дискретного преобразования Фурье последовательности из 8 вырезок аналогового сигнала.

1.20.3. БПФ ряда из восьми членов
Общая формула БПФ ряда из 8 членов:

(1.41)

Приведенную ранее матрицу Фрэнкса для N=8 разделим на две группы с четными и нечетными индексами и проделаем те же преобразования, как и для матрицы с N=4.


X0 w0 w0 w0 w0 w0 w0 w0 w0 f0

X1 w0 w1 w2 w3 w4 w5 w6 w7 f1

X2 w0 w2 w4 w6 w8 w10 w12 w14 f2
1   2   3   4   5   6   7


База даних захищена авторським правом ©shag.com.ua 2016
звернутися до адміністрації

    Головна сторінка