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



Сторінка3/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 (1.42)

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

[ f0 f2 f4 f6 ] [ f1 f3 f5 f7 ]

X0 w0 w0 w0 w0 w0 w0 w0 w0

X1 w0 w2 w4 w6 w1 w3 w5 w7

X2 w0 w4 w8 w12 w2 w6 w10 w14
  1. X3 = w0 w6 w12 w18 + w3 w9 w15 w21


X4 w0 w8 w16 w24 w4 w12 w20 w28

X5 w0 w10 w20 w30 w5 w15 w25 w35

X6 w0 w12 w24 w36 w6 w18 w30 w42

X7 w0 w14 w28 w42 w7 w21 w35 w49


[ f0 f2 f4 f6 ] [ f1 f3 f5 f7 ]

X0 w0 w0 w0 w0 w0 w0 w0 w0 w0

X1 w0 w2 w4 w6 w1 w1 w3 w5 w7

X2 w0 w4 w8 w12 w2 w2 w6 w10 w14
  1. X3 = w0 w6 w12 w18 + w3 w3 w9 w15 w21


X4 w0 w8 w16 w24 w4 w4 w12 w20 w28

X5 w0 w10 w20 w30 w5 w5 w15 w25 w35

X6 w0 w12 w24 w36 w6 w6 w18 w30 w42

X7 w0 w14 w28 w42 w7 w7 w21 w35 w49


[ f0 f2 f4 f6 ] [ f1 f3 f5 f7 ]

X0 w0 w0 w0 w0 w0 w0 w0 w0 w0

X1 w0 w2 w4 w6 w1 w0 w2 w4 w6

X2 w0 w4 w0 w4 w2 w0 w4 w0 w4
  1. X3 = w0 w6 w4 w2 + w3 w0 w6 w4 w2 (1.43)


X4 w0 w0 w0 w0 w4 w0 w0 w0 w0

X5 w0 w2 w4 w6 w5 w0 w2 w4 w6

X6 w0 w4 w0 w4 w6 w0 w4 w0 w4

X7 w0 w6 w4 w2 w7 w0 w6 w4 w2

Используя закономерности рис.1.14, получаем равенства:



После подстановки их в (1.43) имеем:



[ f0 f2 f4 f6 ] [ f1 f3 f5 f7 ]

X0 1 1 1 1 w0 1 1 1 1

X1 1 -j -1 j w1 1 -j -1 j

X2 1 -1 1 -1 w2 1 -1 1 -1
  1. X3 = 1 j -1 -j + w3 1 j -1 -j


X4 1 1 1 1 -w0 1 1 1 1 (1.44)

X5 1 -j -1 j -w1 1 -j -1 j

X6 1 -1 1 -1 -w2 1 -1 1 -1

X7 1 j -1 -j -w3 1 j -1 -j

Существует несколько алгоритмов разных авторов для расчётов БПФ как во временной так и в частотной областях. Наиболее известны алгоритм Кули и Тьюки (1965г.) и Винограда,


1.21. Более строгое обоснование БПФ
Все алгоритмы быстрого дискретного преобразования Фурье основаны на периодичности поворачивающего множителя.

Идея сокращения общего объёма вычислений состоит в следующем:

1) Исходная N-точечная последовательность х(n) разделяется на две N/2 - точечные последовательности с нечётными и чётными элементами, затем вычисляются ДПФ каждой из них и конструируется ДПФ Х( k).

Объем вычислений сокращается в 2 раза.

2) Аналогично вместо ДПФ N/2 - точечные последовательности можно вычислить ДПФ по две N/4 - точечные последовательности и вновь уменьшить количество вычислений в 2 раза.

3) Процесс уменьшения количества вычислений, называемый прореживанием, продолжается до тех пор, пока не останутся только двухточечныеточечные последовательности, рассчитываемые ДПФ.

Если , т.е. , то объем вычислений можно уменьшить в N/m раз. Например, при N = 1024 =210 это составляет примерно раз.

Указанная процедура уменьшения числа вычислений называется прореживанием. Прореживание исходной N-элементной последовательности X(n) может производиться по времени или по частоте.


1.21.1. Прореживание последовательности х(n) по времени
Пусть N = 2m . Обозначим исходную N – точечную последовательность как -. Разделим ее на две N/2 - точечные последовательности для чётных и нечётных членов.

- четные члены

- нечетные члены

Тогда N-точечную ДПФ можно записать в виде



(1.45)

Учитывая, что , получаем



(1.46)

Для четных и нечётных элементов последовательности

получим выражения:

(1.47)
Поскольку Хm(k) должно быть определено для N точек ( k = 0, 1, ..., N-1), а (1.47) определено только для N/2 точек (k = 0,1,... , N/2 -1). Поэтому необходимо доопределить его для k =N/2; N/2+1,….N-1. При этом принимается во внимание, что Хm-1,0,Xm-1(k) - периодические функции с периодом N/2. Тогда

(1.48)

Знак ‘ - ’ появился, так как




(1.49)

Выражения (1.48) и (1.49) определяют алгоритм вычисления N-точечного ДПФ через два N/2 - точечных ДПФ.

Аналогично можно выразить N/2 - точечные ДПФ

через N/4 - точечные ДПФ



(1.50)
Здесь - точечные ДПФ для:

k = 0 – четных номеров

k = 1 – нечетных номеров

k = 2 - четных номеров

k = 3 – нечетных номеров .
Процесс продолжается до тех пор , пока на m-шаге не окажутся только два двухточечных ДПФ. Обозначим их Ф (k) k = 0, 1. Они соответствуют 2- точечным последовательностям ,.

(1.51)

Рассмотрим случай для N = 8 = 23 , т.е. m = 3.

Исходная последовательность



Рис. 1.17. ДПФ для N=8


1.21.2. Графическое представление БПФ

Рис. 1.17. Графическое представление алгоритма ДПФ


1.21.3. Перестановка членов входной последовательности
Перестановка производится в соответствии с двоичной инверсией номеров , т.е. элементом с номером () записывается в ячейку с номером ()
НомерДвоичный кодДвоичная инверсияИнверсный номер0000000010011004201001023011110641000011510110156110011371111117

1.21.4. Общий алгоритм БПФ
Из графического представления БПФ следует:

  1. БПФ выполняется поэтапно. Число этапов равно . Должен быть организован цикл

  2. На каждом l-м этапе получаем - точечная последовательность. Должен быть организован цикл

  3. Целесообразно один и тот же поворачивающий множитель использовать для соответствующих элементов всех последовательностей на каждом этапе. Эти элементы отстоят друг от друга на l1 индексов. Должен быть организован цикл

  4. Результаты каждой операции «бабочка» должны записываться на место операндов, обеспечивая принцип замещения.


1.22. Свёртка сигналов
В цифровой обработке сигналов широко используется линейная и круговая дискретная свёртка. Линейной свёрткой двух конечных последовательностей x(nT) и g(nT) по N и M называется последовательность y(nT), определяемая соотношением , которая является конечной и имеет отсчётов.

Круговой или циклической дискретной свёрткой двух периодических последовательностей x(nT) и g(nT) с периодом N называется последовательность y(nT), определяемая соотношением .

Для непрерывных сигналов используется аналогичная дискретной аналоговая свёртка.

Свертка сигналов является одной из главных операций линейных систем. В соответствии с фильтрующим свойством дельта-функции, любой сигнал на входе линейной системы можно представить в виде непрерывной свертки, под знаком интеграла, которая находится как произведение входного сигнала и дельта-функции, следующим образом:



В процессе прохождения сигнала по линейной системе дельта-функция превращается в её импульсную характеристику и сигнал на выходе линейной цепи находится как свертка входного сигнала и импульсной характеристики канала g(t-) или: Аналогично находится выходной сигнал дискретного канала. Интеграл при этом заменяется бесконечной или конечной суммой.

Порядок выполнения операций дискретной линейной и круговой свертки иллюстрируют рис.1.18. и 1.19.


1.22.1. Вычисление линейной дискретной свёртки
1 2 4 8

2 3 4 5

Сигналы: x( kT) g(kT)



2

4

82

1

3

4



2

5
y(0)=1*2=2


1

2



4

8

2



3

4

5



y(1)=1*3+2*2=7

4

1



2

3

2



4

8
5


y(2)=1*4+2*3+4*2=18
1

2

4



8

5

4



3

2

y(3)=1*5+2*4+4*3+8*2=41



1

2

4



8

5

4



3

2

y(4)=2*5+4*4+8*3=50



1

2

4



8

5

4



3

2

y(5)=4*5+8*4=52



1

2

4



8

5

4



3

2

y(6)=8*5=40



Результат

2

7



18

41

50



52

40


Рис.1.18. Линейная дискретная свертка

1.22.2. Вычисление круговой дискретной свёртки
Исходные сигналы x(kT) и g(kT)

1

2

4 8 2

5 4 3

y(0)=1*2+2*5+4*4+8*3=52

1 2 4 8 3 2 5 4

y(1)=1*3+2*2+4*5+8*4=59
1 2 4 8 4 3 2 5

y(2)=1*4+2*3+4*2+8*5=58
1 2

4 8 5 4

3 2

y(3)=1*5+2*4+4*3+8*2=41
Результат
52 59

58 41

Рис.1.19. Круговая дискретная свертка

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

Сомножители в линейной и круговой свёртках могут меняться местами, что видно из приведенного ниже расчёта линейной и круговой свёртки. Конечные результаты при этом совпадают.





1.23. Преобразование Лапласа, Фурье и z-преобразование
На практике для математического описания аналоговых и дискретных линейных систем и сигналов используется три способа, между которыми существует взаимн однозначное соответствие.

1   2   3   4   5   6   7


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

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