Анализ и синтез цифровых устройств

1.

Новгородский государственный университет имени Ярослава Мудрого
Научно-исследовательская лаборатория цифровой обработки сигналов
АНАЛИЗ И СИНТЕЗ ЦИФРОВЫХ
УСТРОЙСТВ
И Л Л ЮС Т Р А Т И В Н Ы Й М А Т Е Р И А Л К К О Н С ПЕ К Т У Л Е К Ц И Й
Реганов Владислав Михайлович
ауд. 4301
Великий Новгород 2014

2.

Литература
?????
1.
А.Б.Сергиенко. Цифровая обработка сигналов. – СПб.: Питер, 2003 г.
2.
Лайонс Р. Цифровая обработка сигналов. пер. с англ. под ред. Бритова А.А. – М.:
Бином, 2006.
3.
Айфичер Э.С, Джервис Б.У. Цифровая обработка сигналов: практический подход, 2-е
издание .Пер. с англ. – М.: Издательский дом «Вильямс», 2004
4.
Рабинер Л., Гоулд Б.. Теория и применение цифровой обработки сигналов. /пер. с
англ. – Мир, 1978
5.
Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов, М., Мир, 1989
6.
С.Л. Марпл-мл. Цифровой спектральный анализ и его приложения
АНАЛИЗ И СИНТЕЗ ЦИФРОВЫХ УСТРОЙСТВ. СЛАЙД 2

3.

Темы
1.
Спектральный анализ
БПФ
Гребенка фильтров
Непараметрические методы оценивания СПМ
Полифазное БПФ
Другие методы
2. Формирование цифровых случайных сигналов
3. Построение цифровых приемных устройств
Цифровой гетеродин
Преобразователь Гильберта
CIC фильтры
Полуполосные (диадные) фильтры
Полифазные фильтры
4. Цифровое формирование сигнала на несущей частоте
Прямой цифровой синтез
5. Основы вейвлет-преобразования
6. Метод CORDIC
АНАЛИЗ И СИНТЕЗ ЦИФРОВЫХ УСТРОЙСТВ. СЛАЙД 3

4.

Методы цифрового спектрального анализа
Основные приложения:
радиолокация, радионавигация, радиоастрономия;
гидроакустика, гидролокация;
системы распознавания речи;
сжатие полосы речевых сигналов;
вибрационный анализ.
Спектральный анализ – это измерение, которое дает точные или приближенные
значения Z - преобразования дискретного сигнала в заданном множестве точек
Z - плоскости.
Различают “мгновенный” спектр и оценку спектральной плотности мощности.
Разновидности спектрального анализа:
вычисление “мгновенного” спектра с использованием окон;
оценивание СПМ классическими методами;
оценивание СПМ параметрическими методами:
оценивание блочных данных;
рекурсивное оценивание;
многомерный спектральный анализ.
АНАЛИЗ И СИНТЕЗ ЦИФРОВЫХ УСТРОЙСТВ. СЛАЙД 4

5.

Алгоритмы БПФ
Быстрое преобразование Фурье (БПФ) – метод вычисления ДПФ
{x(n)}, 0 n N-1 – комплексный сигнал.
N 1
ДПФ:
X ( k ) x ( n) e
N 1
j
2
nk
N
, где k 0,1,2...N-1
n 0
X ( k ) x ( n) W
nk
где
W e
j
2
N
- множитель вращения
n 0
{Wnk} периодична по n и k с периодом N:
W(n+mN)(k+lN) = (WN)nk , где m, l = 0, 1, 2…, WN – множитель вращ-я с периодом N.
Количество операций для ДПФ размерности N:
(N-1)2 – комплексных умножений, N(N-1) – комплексных сложений.
Основная идея БПФ – разбиение длинной последовательности на короткие.
N/2
N
Кол ~
N2
ДПФ
Кол=N2/4
ДПФ
Кол=N2/2
N/2
ДПФ
Кол=N2/4
АНАЛИЗ И СИНТЕЗ ЦИФРОВЫХ УСТРОЙСТВ. СЛАЙД 5

6.

Алгоритм БПФ с прореживанием по времени
Пусть N – степень 2.
Разобьем {x(n)} на {x1(n)} – четные отсчеты, {x2(n)} – нечетные отсчеты.
N
n
0,1...
1
x1(n) = x(2n), x2(n) = x(2n+1), для
2
N 1
N
1
2
N
1
2
n 0
n 0
n 0
X (k ) x(n) WNnk x(2n) WN2 nk x(2n 1) WN(2 n 1) k
Поскольку WN2 [e
j
2
N 2
] e
2
j
N
2
N
1
2
WN
N
1
2
то X (k ) x1 (n) WNnk WNk x2 (n) WNnk
2
2
n 0
X1 ( k )
2
n 0
X 2 (k )
k
Тогда X (k ) X 1 (k ) WN X 2 (k )
Вычисление X1(k) и X2(k) – 2N 2/4 MAC + объединение X1(k) и X2(k) – N MAC
Всего N 2/2+N N 2/2 при больших N
АНАЛИЗ И СИНТЕЗ ЦИФРОВЫХ УСТРОЙСТВ. СЛАЙД 6

7.

Алгоритм БПФ с прореживанием по времени
Доопределение X(k) для k N/2 на основании периодичности N/2 точечных ДПФ:
N
k
X
(
k
)
W
X
(
k
),
0
k
1
N
2
1
2
X (k )
X (k N ) W k X (k N ), N k N 1
N
2
1
2
2
2
Из-за WNk - период X(k) не равен периоду X1(k).
k
Т.к. W WN
k
N
N
2
N
k
X
(
k
)
W
X
(
k
),
0
k
1
N
2
1
2
то X (k )
N
k
N
X (k ) W 2 X (k N ), N k N 1
N
2
1
2
2
2
АНАЛИЗ И СИНТЕЗ ЦИФРОВЫХ УСТРОЙСТВ. СЛАЙД 7

8.

Пример алгоритма БПФ размерности 8 по основанию 2 с прореживанием по времени
Разложение ДПФ размерности 8 на два ДПФ размерности 4.
Этап 3
x1(0)=x(0)
x1(1)=x(2)
x1(2)=x(4)
X(0)
X1(1)
X(1)
X1(2)
X(2)
X1(3)
X(3)
"бабочка"
a
a+b
b
a-b
X2(2)
X2(3)
X(4)
1
w
x2(3)=x(7)
w
x2(2)=x(5)
X2(1)
w
X(5)
2
x2(1)=x(3)
4-х
точечн.
ДПФ
X2(0)
X(6)
3
x2(0)=x(1)
w
0
x1(3)=x(6)
4-х
точечн.
ДПФ
X1(0)
АНАЛИЗ И СИНТЕЗ ЦИФРОВЫХ УСТРОЙСТВ. СЛАЙД 8
X(7)
a wk awk

9.

Пример алгоритма БПФ размерности 8 по основанию 2 с прореживанием по времени
N
1
2
2
N
k
2k
X 2 (k ) C (k ) WN D(k ) C (k ) WN D(k ), 0 k 1
2
2
Этап 2
Этап 3
2-х
X (0)
a(0)=x (0)=x(0)
A(0)
X (0)
точечн.
a(1)=x (2)=x(4)
A(1)
X (1)
X (1)
ДПФ
X 1 (k ) A(k ) WNk B(k ) A(k ) WN2 k B(k ), 0 k
1
1
1
X1(3)
X (3)
C(0)
X2(0)
w
0
X (2)
C(1)
X2(1)
X (4)
X (5)
d(1)=x2(3)=x(7)
D(0)
D(1)
X2(2)
3
0
2-х
точечн.
ДПФ
X (6)
w
d(0)=x2(1)=x(3)
w
2
c(1)=x2(2)=x(5)
2-х
точечн.
ДПФ
B(1)
X1(2)
1
c(0)=x2(0)=x(1)
B(0)
w
b(1)=x1(3)=x(6)
2-х
точечн.
ДПФ
w 2w
b(0)=x1(1)=x(2)
0
1
w 2w
Этап 2
X2(3)
АНАЛИЗ И СИНТЕЗ ЦИФРОВЫХ УСТРОЙСТВ. СЛАЙД 9
X (7)

10.

Направленный граф алгоритма БПФ размерности N = 8 по основанию 2
с прореживанием по времени и с замещением (алгоритм Кули-Тьюки).
F (0) f (0) f1 WN0 f (0) f (1);
Этап 1
N
F (1) f (0) f1 WN 2 f (0) f (1);
Этап 1
x(0)
x(4)
w
Этап 2
Этап 3
X(0)
0
X(1)
0
x(2)
X(2)
w
2
w
X(3)
0
x(6)
w
0
X(4)
0
2
w
w
3
0
x(3)
w
w
x(5)
w
1
w
x(1)
X(5)
X(6)
2
x(7)
w
0
w
АНАЛИЗ И СИНТЕЗ ЦИФРОВЫХ УСТРОЙСТВ. СЛАЙД 10
X(7)

11.

Свойства алгоритма БПФ по основанию 2
1. Алгоритм состоит из этапов. На каждом этапе происходит изменение размерности
БПФ вдвое по сравнению с предыдущим.
Kэт = log2 N
2. На каждом этапе необходимо выполнить N/2 операций “бабочка”.
A
B
K
X = A + B WN
2 операции комплексного сложения и
1 операция комплексного умножения
Y = A - B WNK
3. Общее число базовых операций "бабочка":
N
K оп log 2 N
2
4. Для вычисления базовой операции достаточно иметь одну
дополнительную ячейку для хранения произведения. Остальные результаты
размещаются в освободившиеся ячейки. Это алгоритм с замещением.
АНАЛИЗ И СИНТЕЗ ЦИФРОВЫХ УСТРОЙСТВ. СЛАЙД 11

12.

Сравнение вычислительных затрат
KДПФ/БПФ2
2500
K ДПФ / БПФ 2
N2
N log 2 N
КДПФ/БПФ2
2000
70
1500
50
30
1000
10
0 5 10 15 20 25 30 N
500
0
2
16
64
256
1024
4096
16384
N
Выигрыш в количестве операций алгоритма БПФ2 по сравнению с ДПФ в
зависимости от размерности N
АНАЛИЗ И СИНТЕЗ ЦИФРОВЫХ УСТРОЙСТВ. СЛАЙД 12

13.

Перестановка данных и двоичная инверсия
Для алгоритма по основанию 2 и прореживанием по времени закон
чередования входных отсчетов описывается двоично-инверсным порядком.
Пример: N = 8 L = log2 8 = 3
№ п/п
0
1
2
3
4
5
6
7
Двоичное
представление
000
001
010
011
100
101
110
111
Двоичная
инверсия
000
100
010
110
001
101
011
111
Двоич.-инверс.
номер
0
4
2
6
1
5
3
7
Способы получения поворачивающих множителей
1. Табличный – требует много памяти, но имеет наибольшее быстродействие
2. Последовательный – не требует много памяти, но имеет низкое быстродейст.
3. Рекуррентный WNK WNK L WNL с изменением шага от этапа к этапу и
0
с начальным условием WN 1 на каждом этапе
АНАЛИЗ И СИНТЕЗ ЦИФРОВЫХ УСТРОЙСТВ. СЛАЙД 13

14.

Алгоритм БПФ с прореживанием по частоте
Входная последовательность разбивается на 2 половины:
N
x1 (n) x(n), при n 0, 1, 2 ... 1
2
N
N
x2 (n) x(n ), при n 0, 1, 2 ... 1
2
2
Тогда N-точечное ДПФ последовательности {x(n)}:
N
1
2
X ( k ) x ( n) W
nk
N
n 0
Т.к.
N
k
2
N
W
N 1
x ( n) W
nk
N
n
e j k
то
N
2
N
1
2
x1 (n) W
n 0
nk
N
N
1
2
N
1
2
x 2 ( n ) WN
n 0
X (k ) [ x1 (n) e j k x2 (n)] WNnk
n 0
АНАЛИЗ И СИНТЕЗ ЦИФРОВЫХ УСТРОЙСТВ. СЛАЙД 14
( n
N
)k
2

15.

Алгоритм БПФ с прореживанием по частоте
N
k
2
N
Поскольку W
e j k 1 то X(k) для четных и нечетных k:
N
1
2
N
1
2
n 0
n 0
X (2k ) [ x1 (n) x2 (n)] WN2 nk [ x1 (n) x2 (n)] WNnk
2
f(n)
N
1
2
N
1
2
n 0
n 0
X (2k 1) [ x1 (n) x2 (n)] WNn (2 k 1) {[ x1 (n) x2 (n)] WNn } WNnk
2
g ( n)
X(2k) получаются из N/2-точечных ДПФ последовательности:
f(n) = x1(n) + x2(n) ; n = 0, 1, 2…N/2 – 1
X(2k+1) получаются из N/2-точечных ДПФ последовательности:
g(n) = [x1(n) - x2(n)]WNn n = 0, 1, 2…N/2 – 1
АНАЛИЗ И СИНТЕЗ ЦИФРОВЫХ УСТРОЙСТВ. СЛАЙД 15

16.

Пример построения алгоритма БПФ размерности 8 с прореживанием по
частоте
Этап 1
X1 (u)
X(0)
- f(0) -
X(1)
- f(1) -
X(2)
- f(2) -
X(3)
- f(3) -
X(6)
X(7)
0
X2 (u)
X(5)
w 1 2
w
3
ww
X(4)
- g(0) - g(1) - g(2) - g(3) -
4-х
точечн.
ДПФ
4-х
точечн.
ДПФ
АНАЛИЗ И СИНТЕЗ ЦИФРОВЫХ УСТРОЙСТВ. СЛАЙД 16
X(0)
X(4)
X(2)
X(6)
X(1)
X(5)
X(3)
X(7)

17.

Алгоритмы БПФ по основанию 2
Направленный граф алгоритма БПФ по основанию 2 с прореживанием по частоте.
x(0)
X(0)
x(1)
X(4)
x(2)
X(2)
x(3)
X(6)
x(4)
X(1)
x(5)
X(5)
x(6)
X(3)
x(7)
X(7)
АНАЛИЗ И И СНТЕЗ ЦИФРОВЫХ УСТРОЙСТВ. СЛАЙД 17

18.

Различия алгоритмов БПФ с прореживанием
по времени и по частоте
по времени
по частоте
1. Порядок следования входных отсчетов:
прямой
двоично-инверсный
2. Порядок следования выходных отсчетов:
прямой
двоично-инверсный
3. Базовая операция “бабочка”
A
B
K
X = A + B WN
Y = A - B WNK
A
B
АНАЛИЗ И СИНТЕЗ ЦИФРОВЫХ УСТРОЙСТВ. СЛАЙД 18
X=A+B
Y = (A – B) W KN

19.

Вычисление обратного ДПФ по алгоритму прямого
Обратное ДПФ {x(n)} для последовательности {X(k)}, k=0,1,…,N-1
1 N 1
x(n) X (k ) W nk
N k 0
N x ( n)
*
N 1
X
*
(k ) W nk
k 0
- обратное ДПФ
* - знак комплексного сопряжения
ДПФ послед-ти X * (k )
Тогда:
1 N 1 *
x(n) [ X (k ) W nk ]*
N k 0
Т.о. можно использовать алгоритмы БПФ для вычисления ДПФ и ОДПФ
АНАЛИЗ И СИНТЕЗ ЦИФРОВЫХ УСТРОЙСТВ. СЛАЙД 19

20.

Алгоритмы БПФ по основанию 4
По аналогии с основанием 2 можно построить алгоритмы БПФ по основанию 4.
ДПФ размерности 4 не требует операций комплексного умножения, так
как умножение на
2
W exp j
4
выполняется
перестановкой реальной и мнимой компонент
3 комплексных
умножения
12 комплексных
сложений
Операция «бабочка» по основанию 4 с прореживанием по
времени
Выигрыш по количеству операций комплексного умножения по сравнению с алгоритмом БПФ по
основанию 2 около 25%.
АНАЛИЗ И СИНТЕЗ ЦИФРОВЫХ УСТРОЙСТВ. СЛАЙД 20

21.

Алгоритм БПФ по основанию 4 размерности 16
0
0
4
0
1
8
0
0
2
3
12
0
1
5
9
0
0
0
10
6
0
0
0
7
8
4
9
6
10
11
0
3
11
2
2
0
0
0
14
7
5
0
2
6
1
3
13
4
3
12
6
13
9
14
15
15
АНАЛИЗ И СИНТЕЗ ЦИФРОВЫХ УСТРОЙСТВ. СЛАЙД 21

22.

Принцип построения алгоритма БПФ с произвольным основанием
Если N – составное число, то одномерный массив отсчетов можно записать в виде
матрицы размерности N=MxL.
Алгоритм вычисления ДПФ размерности N:
Преобразовать одномерный массив в матрицу (заполнение по строкам!)
n m L l , n 0..N 1, m 0..M 1( №столбца), l 0..L 1( №строки).
Вычислить ДПФ каждого столбца
M 1
X c k , l x m, l WMmk , k 0..M 1, l 0..L 1
m 0
Умножить элементы матрицы
X c k , l X c k , l WNkl , k 0..M 1, l 0..L 1
L 1
Вычислить ДПФ каждой строки
X r k , i X c k , l WLli , k 0..M 1, i 0..L 1
l 0
Преобразовать матрицу в одномерный массив (считывание по строкам!).
Если размерность строки или столбца - составное число, разбиение можно
повторить.
Для произвольных составных N наиболее быстрый алгоритм со смешанным
основанием – АВПФ (алгоритм Винограда преобразования Фурье).
АНАЛИЗ И СИНТЕЗ ЦИФРОВЫХ УСТРОЙСТВ. СЛАЙД 22

23.

Сравнение БПФ и гребенки фильтров.
Гребенка фильтров:
X 0 i
+
Z-1
W0
X1 i
+
x i
W1
Z-N
X k i
+
Требует N операций умножениянакопления на 1 отсчет сигнала.
БПФ без перекрытия:
Z-1
-
выдает N спектральных отсчетов в
каждый момент времени;
Z-1
Выдает N спектральных отсчетов через
N отсчетов сигнала;
Требует
1 log N
2
2
операций умножения-накопления на 1
отсчет сигнала.
Wk
X N 1 i
+
Z-1
БПФ с перекрытием:
N
K
Выдает N отсчетов через
WN-1
Анализатор спектра в виде гребенки отсчетов сигнала;
фильтров
Требует в K раз больше операций
АНАЛИЗ И СИНТЕЗ ЦИФРОВЫХ УСТРОЙСТВ. СЛАЙД 23

24.

Использование «окон» при спектральном анализе
Импульсная характеристика
2π k
exp
j
n , 0 n N -1
h n =
N
0, остальные n
одного из гребенки фильтров:
Частотная характеристика
H e j
(без фазового множителя):
N
sin
2
k
sin
2
N
k=0,1..N-1
Проблема: маскировка слабых спектральных компонент сильными из-за высоких боковых лепестков АЧХ
фильтра.
40
дБ
Амплитуды
сигналов:
30
20
А1 – 1 (0 дБ)
10
0
А2 – 0.01 (-40 дБ)
-10
А3 –0.001(-60 дБ)
-20
-30
200
300
400
500
600
700
АНАЛИЗ И СИНТЕЗ ЦИФРОВЫХ УСТРОЙСТВ. СЛАЙД 24
800

25.

Использование «окон» при спектральном анализе
Во временной области – умножение
сигнала на весовую функцию «окна».
В спектральной области – свертка
спектра сигнала с частотной
характеристикой «окна».
Временные отсчеты
Временные отсчеты
Умножение на
весовую функцию
Анализатор спектра
(БПФ)
Анализатор спектра
(БПФ)
Свертка с ЧХ «окна»
(сглаживание спектра)
Спектральные отсчеты
1 умножение на отсчет для всех видов
окон
Спектральные отсчеты
Для окна Ханна порядок фильтра -3
( окно Хэмминга – без умножений).
Для окна Блэкмана порядок фильтра - 5.
АНАЛИЗ И СИНТЕЗ ЦИФРОВЫХ УСТРОЙСТВ. СЛАЙД 25

26.

Использование «окон» при спектральном анализе
дБ
40
30
20
rectangular
window
Амплитуды
сигналов:
Hann
window
C hebyshev
window
А1 – 1 (0 дБ)
10
0
А2 – 0.01 (-40 дБ)
-10
А3 –0.001(-60 дБ)
-20
-30
-40
-50
200
300
400
500
600
700
800
Стратегия выбора «окна» по одному из параметров:
по скорости спадания БЛ – при большой разнице амплитуд и частот;
по максимальному уровню БЛ – при разных амплитудах и неизвестных
(распределенных в большом диапазоне) частотах;
по ширине основного лепестка АЧХ – при сопоставимых амплитудах и близко
расположенных частотах.
АНАЛИЗ И СИНТЕЗ ЦИФРОВЫХ УСТРОЙСТВ. СЛАЙД 26

27.

Классические методы спектрального оценивания
Задача: получить оценку спектральной плотности мощности сигнала с
минимальной среднеквадратической ошибкой по зашумленной реализации
конечной длительности.
Основные характеристики:
Диапазон анализируемых частот
Определяется частотой дискретизации Fs:
от 0 до ½ Fs для действительных сигналов;
от - ½ Fs до + ½ Fs для комплексных сигналов.
Разрешающая способность по частоте
N 1
W k
Определяется эффективной шириной
главного лепестка ЧХ окна Be:
Be
k 0
W k
max
k 0, N 1
Достоверность
Определяется относительной
среднеквадратической ошибкой Q
оценки СПМ
Q k
S k S k
S k
АНАЛИЗ И СИНТЕЗ ЦИФРОВЫХ УСТРОЙСТВ. СЛАЙД 27
2
2
, k 0,1..N 1

28.

Классические методы спектрального оценивания
Особенность оценки СПМ при наличии шума:
При увеличении размерности БПФ ошибка оценки СПМ не уменьшается, так как
определяется спектральной плотностью шума.
Для ее снижения необходимо усреднение спектральных оценок.
При ограниченной длине реализации случайного процесса:
Повышение достоверности оценки приводит к ухудшению разрешающей
способности;
Повышение разрешающей способности приводит к потере достоверности оценки.
Если влияние шума пренебрежимо мало, то
Be Te 1
Te- эффективная длительность реализации.
Если необходимо усреднение оценок СПМ для повышения достоверности, то
2
N 1
W k
k 0
Q Te BS 1
BS
- статистическая ширина
N 1
2
полосы «окна»
W
k
k 0
АНАЛИЗ И СИНТЕЗ ЦИФРОВЫХ УСТРОЙСТВ. СЛАЙД 28

29.

Периодограммный метод оценки СПМ
Последовательность операций:
1.
2.
Реализация процесса длиной L отсчетов разбивается на M сегментов размером N отсчетов каждый
xm n , n 0,1,..N 1, m 1,2..M .
Вычисляется БПФ от каждого сегмента
X m k , k 0,1,..N 1, m 1,2..M .
3.
Усредняется оценка СПМ
PX k 1
M
M
X m k X m* k , k 0,1..N 1
m 1`
Для снижения потерь из-за взвешивания функцией «окна» применяется перекрытие сегментов на ½ или ¼.
Увеличение длины сегмента соответствует улучшению разрешающей способности и снижению
достоверности (возрастанию ошибки), и наоборот.
АНАЛИЗ И И СНТЕЗ ЦИФРОВЫХ УСТРОЙСТВ. СЛАЙД 29

30.

Коррелограммный метод оценки СПМ
Основан на дискретном аналоге теоремы Винера-Хинчина.
Последовательность операций:
1.
Вычислить АКФ реализации процесса в диапазоне [0,N-1] дискретных задержек:
L 1
RX m x n x* n m , m 0,1..N 1.
n 0
2.
Вычислить ДПФ размерности N от АКФ c использованием «окна»:
2
PX k RX m exp j
k m , k 0,1..N 1.
N
m 0
N 1
Увеличение диапазона задержек АКФ соответствует улучшению разрешающей
способности, и снижению достоверности
(возрастанию ошибки), и наоборот.
Рекомендуется: начинать оценку СПМ с высокой достоверности, продвигаясь в направлении
более высокого разрешения по частоте.
АНАЛИЗ И И СНТЕЗ ЦИФРОВЫХ УСТРОЙСТВ. СЛАЙД 30

31.

Формирование случайных сигналов (шумов)
Формирование случайного сигнала с равномерным распределением
Пусть