Цифровая обработка сигналов

1. Цифровая обработка сигналов

Профессор Луцив Вадим Ростиславович
Кафедра № 14

2.

3.

Литература
1. Васильев А.Н. MATLAB. Самоучитель. Практический
подход. – СПб.: Наука и техника, 2012. – 448 с.
2. Ануфриев И., Смирнов А., Смирнова Е. MATLAB 7 (+CDROM). – СПб.: БХВ-Петербург, 2005. – 1102 с.
3. Солонина А.И., Арбузов С.М. Цифровая обработка
сигналов. Моделирование в MATLAB. – СПб.: БХВ-Петербург,
2008. – 816 с.
4. Сергиенко А.Б. Цифровая обработка сигналов. 3-е
издание. – СПб.: БХВ-Петербург, 2011. – 758 с.
5. Рабинер Л., Гоулд Б. Теория и применение цифровой
обработки сигналов. – М.: Мир, 1978. – 848 с.
6. Stanley W.D. Digital signal processing. – Englewood, USA:
Reston Publishing Co., Inc., 1975. – 323 p.

4.

Цифровая и аналоговая обработка сигналов

5.

Дискретное представление сигнала

6.

Достоинства и недостатки дискретных систем
Достоинства дискретных систем
1. Возможность реализации сколь угодно сложных алгоритмов
обработки сигналов.
2. Простота перестройки алгоритмов.
3. Неограниченная временная стабильность характеристик.
4. Простота обработки низкочастотных (НЧ) сигналов.
5. Высокая стабильность и надежность работы и хорошая
воспроизводимость получаемых результатов.
6. Неограниченную во времени и практически неограниченную
по объему память для запоминания сигналов и параметров.
7. Снижается риск самовозбуждения системы и открывает почти
неограниченные возможности микроминиатюризации.
Недостатки дискретных систем
1. Необходимо применение АЦП и ЦАП.
2. Возникают специфические ошибки обработки сигналов,
связанные с их дискретизацией и квантованием.

7.

Спектр непрерывного периодического сигнала
Для периодических сигналов, для которых выполняется условие
xн(t) = xн(t + kТп) ( Тп – период сигнала, k = 0, 1, 2 …),
спектр может быть определен путем разложения в ряд Фурье
где 0 = 2 /Тп – основная частота преобразования. Множество
значений {Сk} – амплитудный спектр, множество { k} – фазовый.
Спектр периодического сигнала – линейчатый с дискретом 0.

8.

Спектр непрерывного непериодического сигнала
Спектр Xн(jω) непериодического сигнала является комплексной
функцией и связан c непрерывном сигналом xн(t) прямым (ППФ)
и обратным (ОПФ) преобразованиями Фурье:
(1)
Амплитдный спектр:
Фазовый спектр:
Аx( ) =|Xн(j )|,
x( ) = arg(Xн(j )) = Xн(j ).

9.

Спектр дискретизированных сигналов
Ведем обозначения:
xн(t) – непрерывный по времени сигнал,
Xн(jω)– спектр непрерывного сигнала, полученный
преобразованием Фурье,
x(nT) – дискретизированный сигнал,
X(e j T) – спектр дискретизированного сигнала, полученный
преобразованием Фурье.
6

10.

Спектры дискретизированных
и непрерывных сигналов,
теорема отсчетов

11.

Преобразование Фурье дискретизированного
сигнала
Прямое и обратное преобразования Фурье для
дискретизированного сигнала записываются в виде:
(2)
Отсчеты дискретизированного сигнала совпадают по величине с
соответствующими значениями непрерывного сигнала
(квантование по уровню в данном случае не рассматривается).
x(nT) = xн(t=nT) = xн(nT).
(3)

12.

(1)
x(nT) = xн(t=nT) = xн(nT). (3)
Из формул (1) и (3) следует:
Разобьем ось частот на отрезки размером д:
(2)

13.

Из сравнения (4) и (2) следует, что
Спектр дискретизированного сигнала состоит с точностью до
множителя 1/Т из суммы бесконечного числа спектров
непрерывного сигнала, следующих с периодом д.
Графики, приведенные на рис. 8, иллюстрируют, как формируется
спектр сигнала при низкой ( д < 2 в) и высокой ( д 2 в) частотах
дискретизации, где в – верхняя частота спектра сигнала. Как видно
из графиков, при д < 2 в происходит наложение спектров.
необходимо выбирать частоту дискретизации д из соотношения
д ≥ 2 в .
В этом случае при < д/2 X(e j T) = (1/T) X(j ) , - тогда
спектры дискретизированного сигнала и сигнала непрерывного
времени будут совпадать.

14.

Возникновение эффекта наложения спектров при
недостаточной частоте дискретизации сигнала
7-

15.

Восстановление непрерывного
сигнала по его дискретным
отсчетам

16.

Если Xн(j ) = 0 при > в, и д 2 в, эффект наложения
спектров отсутствует, и можно восстановить сигнал непрерывного
времени по его дискретным отсчетам: x(nT) → xн(t).
< д/2 X(e j T) = (1/T) Xн(j )
По формуле прямого дискретного преобразования Фурье

17.

Непрерывный сигнал xн(t) получается суммированием функций
n(t) с весами, определяемыми значениями отсчетов
дискретного сигнала x(nT). Рассмотрим функцию n(t):
T/2 = 1/ д и по формуле Эйлера e j z = cos(z) j·sin(z)

18.

Рассмотрим некоторые характерные точки функции n(t).
При n = 0
0(t) = 0 при
0(t) = 0 при
n = 1 соответствует функции 0(t), задержанной на Т, и т.д.:
Рисунок 8 –
Cуммирование
функций n(t) c
весами x(nT)

19.

Непрерывный сигнал можно восстановить, пропуская дискретную
последовательность через идеальный фильтр низких частот
(ФНЧ) (см. на рис. 9 и рис. 10) с частотой среза c = д/2 и с АЧХ
А( ) = Т в полосе пропускания:
Рисунок 9 – Восстановление непрерывного
сигнала из дискретизированного
Рисунок 10 –
Восстановление
непрерывного сигнала из
дискретизированного:
вверху – периодический
спектр
дискретизированного
сигнала, посредине –
амплитудно-частотная
характеристика ФНЧ,
внизу – результат
применения ФНЧ к
дискретизированному
сигналу

20.

Линейные дискретные системы

21.

Виды дискретных сигналов
Рисунок 11 – Произвольный сигнал,
дискретизированный по времени.
x(nT) = x(n) при Т = const, – < n <
Рисунок 12 – Произвольный сигнал,
задержанный на m тактов, здесь m=1.
Рисунок 13 – Единичный импульс

22.

Представление произвольного сигнала в виде взвешенной
суммы задержанных единичных импульсов:
Рисунок 14 – Аналоговый
и дискретизированный
гармонический сигнал
Непрерывный гармонический сигнал имеет вид
xн(t) = A sin( t) = A sin(2 f t),
где f – циклическая частота. После дискретизации с интервалом
Т = 1/fд = 2 / д он описывается формулой x(nT) = A sin(2 f nT).
Введем понятие относительной (нормированной) частоты :
= f / fд = / д = fT. Тогда x(n) = A sin(2 n).

23.

В комплексной форме гармонический непрерывный сигнал имеет вид:
x(t) = A Re {e j t} = A Re{cos( t) + j sin( t)} = A/2 Re{e j t + e -j t}.
После дискретизации сигнал описывается формулой
x(nT) = A Re{e j nT} = A Re{cos( nT)+j sin( nT)} = A/2 Re{e j nT +e -j nT}.
Операции над дискретными сигналами
Рисунок 15 – Графические обозначения операций над дискретными сигналами

24.

Свойства и параметры
дискретных систем

25.

Линейность
Линейная сумма сигналов на входе системы вызывает на выходе
сигнал в виде линейной суммы соответствующих откликов системы:
x(n) = a1x1(n) + a2x2(n) y(n) = a1y1(n) + a2y2(n)
Инвариантность в сдвигу
Задерживание сигнала на входе системы на m тактов вызывает
задержку ее отклика на этот сигнал на m тактов:
x(n-m) y(n-m)
Импульсная характеристика
Импульсная характеристика (ИХ) h(n) – это реакция системы на
единичный импульс x0(n) :
x0(n) y(n) = h(n)
Системы с конечной ИХ: h(n) = 0 при n < n1 и n > n2 (n1 < n2)
и бесконечной ИХ:
h(n) = 0 при n < n1

26.

Описание работы системы с помощью
формулы свертки
Было показано, что любой сигнал можно представить в виде
взвешенной суммы задержанных единичных импульсов:
По определению реакцией системы на единичный импульс x0(n)
является ее импульсная характеристика h(n). Тогда реакцию y(n)
системы на входной сигнал x(n) можно представить так:
Это и есть формула свертки.
Формула свертки записывается как y(n)=x(n)*h(n)=h(n)*x(n),
т.е. формула свертки симметрична.
В аналоговой записи формула свертки соответствует интегралу
Дюамеля:

27.

Соединение систем
Рисунок 16 – Последовательное соединение
систем
При последовательном
соединении систем ИХ h(n)
эквивалентной системы
определяется как свертка ИХ
h1(n) и h2(n) подсистем:
h(n) = h1(n) * h2(n)
При параллельном
соединении систем
h(n) = h1(n) + h2(n)
Рисунок 17 – Параллельное соединение систем

28.

Устойчивость системы
Система называется устойчивой, если ограниченный по величине
сигнал на входе вызывает ограниченный по величине сигнал на
выходе, т.е. при x(n) на входе y(n) на выходе.
Необходимое и достаточное условие устойчивости системы:
Докажем от противного: пусть
Сформируем сигнал на входе системы так (см. рис. 18):
Тогда сигнал на выходе при n = n0
будет
Рисунок 18 – Формирование входного
сигнала системы на основе формы ИХ
Значит, необходимость выполнения
этого условия доказана.

29.

Устойчивость системы
Докажем достаточность выполнения условия
Предположим, что это условие выполняется.
Ограничим величину входного сигнала x(n) M. Тогда на выходе
что и требовалось доказать!
Физическая реализуемость системы
Система физически реализуема, если сигнал y(n0) на ее выходе на
временном такте n0 зависит от текущего и ему предшествующих
входных сигналов x(n n0) и не зависит от последующих входных
сигналов x(n n0). Т.е. следствие не может опережать причину.
Так как единичный импульс x0(n < 0) = 0, то и ИХ h(n<0) = 0.

30.

Частотная характеристика системы
Частотная характеристика (ЧХ) определяет реакцию системы на
входной гармонический сигнал.
Пусть на входе линейной системы гармонический сигнал частоты
амплитудой Ax дискретизированный c интервалом Т:
x (nT) = Ax( ) e j nT,
тогда сигнал на выходе может отличаться от входного амплитудой
Ay и фазовым сдвигом :
y (nT) = Ay( ) e j[ nT+ ( )].
Для конкретной заданной частоты ЧХ H(e j T) связывает значения
выходного и входного сигналов:
y (nT) = x (nT) H(e j T).
H(e j T) = y (nT) / x (nT) = [Ay( ) / Ax( )] e j ( ).

31.

Частотная характеристика системы
Частотная характеристика
H(e j T) = y (nT) / x (nT) = [Ay( ) / Ax( )] e j ( )
включает амплитудночастотную характеристику (АЧХ), которая
определяется как модуль ЧХ и характеризует коэффициент
усиления системы на различных частотах:
K( ) = H(e j T) = Ay( ) / Ax( ),
0 K( ) ;
и фазочастотную характеристику (ФЧХ), характеризующую
фазовый сдвиг выходного сигнала по отношению к входному:
( ) = arg [H(e j T)] = H(e j T),
– ( ) .

32.

Методы вычисления частотной характеристики
Сформируем на входе системы комплексную синусоиду
следующего вида:
x(nT) = e j nT (Ax( ) = 1).
Сигнал y(nT) на выходе системы определяется с помощью
свертки входного сигнала с ее ИХ h(mT):
Но по определению частотной характеристики
.
Сравнивая последние две формулы получаем
т.е. ЧХ
системы вычисляется как преобразование Фурье от ее ИХ.

33.

Методы вычисления частотной характеристики
Вычислим входной сигнал x(nT) и выходной сигнал y(nT) через их
Фурье-спектры X(e j T) и Y(e j T) :
Сигнал на выходе системы можно также определить, если каждую
составляющую спектра входного сигнала умножить на
соответствующее значение ЧХ:
Из сравнения двух последних формул следует, что
ЧХ вычисляется как отношение спектров сигналов на входе и выходе

34.

Свойства частотной характеристики
1. ЧХ есть непрерывная функция частоты .
2. ЧХ – периодическая функция с периодом, равным частоте
дискретизации д.
Так как спектры дискретизированных входного и выходного сигналов
– периодические функции с периодом д, то аналогичным свойством
обладает и ЧХ. Значит, ЧХ достаточно определить на интервале
частот [0, д] (для нормированных частот – на интервале [0, 1]).
3. Если ИХ h(mT) системы – вещественная функция, то АЧХ К( ) –
__четная функция, а ФЧХ ( ) – нечетная.
Докажем это.
Положим = 1, тогда
Пусть теперь = 2 = – 1, тогда
Функции
и
– комплексно сопряженные. При
смене знака аргумента модуль не меняет знак а фаза - меняет.
Следовательно, АЧХ четная функция, а ФЧХ - нечетная, ч.т.д. Их
достаточно вычислять на интервале частот [0, д/2]

35.

Преобразование Лапласа
Прямое и обратное преобразования Лапласа соответственно
описываются формулами
где s – переменная Лапласа, С – контур, включающий все
особенности X(s).
Z-преобразование
Аналогом преобразования Лапласа при работе с системами
дискретного времени является Z-преобразование. Z-преобразование
последовательности x(n) описывается выражением
Например, для x(n) =[ 2 –3,5 1,4 –0,6….] X(z) = [2 –3,5z –1 1,4z –2 –
0,6z -3….]. Существует и обратное Z-преобразование, позволяющее по
X(z) определить x(n).

36.

Свойства Z-преобразования
1. Свойство линейности
Если Z[x1(n)] = X1(z) и Z[x2(n)] = X2(z), то
Z[а1x1(n) + а2x2(n)] = а1 X1(z) + а2 X2(z) (это правило
распространяется на любое число слагаемых).
2. Z-преобразование задержанной на m тактов последовательности
Если x(n) = x1(n–m), то X(z) = z –m X1(z).
Передаточная функция
Передаточная функция H(z) системы есть Z-преобразование ее ИХ:
Если y(n), x(n) и h(n) связаны между собой формулой свертки
то
Значит, передаточную функцию определяется как отношение Zпреобразований сигналов на выходе и входе: H(z) = Y(z) / X(z) .

37.

Связь передаточной функции с частотной
характеристикой
ЧХ H(e j ) может быть получена из передаточной функции H(z)
путем подстановки z = e j :

38.

Цифровые фильтры

39.

Разностные уравнения
Система фильтрации сигнала как и системы вообще могут быть описаны
дифференциальными уравнениями связывающим входной и выходной сигналы
x(n) и y(n) :
N
N
k
k
d x t
d y t
bk
ak
k
dt
dt k
k 0
k 0
d k x t N
d k y t
y t bk
ak
k
dt
dt k
k 0
k 1
N
или
,
где N – порядок уравнения, ak и bk – постоянные коэффициенты. Вспомним
формулу вычисления производной :
dx
x t t x t
lim
.
t
0
dt
t
Допустим, переходя к случаю дискретизированного времени, что интервал
дискретизации t равен 1, тогда в качестве производной можно использовать
разность двух соседних отсчетов сигнала, и от дифференциальных уравнений
переходят к разностным (в общем случае количества слагаемых в первой и
второй суммах могут различаться):

40.

Цифровые фильтры
Рисунок 19 – Вычислительная схема цифрового фильтра,
соответствующего рассмотренному разностному уравнению
Порядок N ЦФ определяется максимальным числом элементов задержки в
прямом или обратном регистрах. Если все коэффициенты в регистре обратной
связи равны нулю (ak = 0 для k = 1…N), то такой ЦФ называется
нерекурсивным (регистр обратной связи отсутствует). Если хотя бы один
коэффициент аk не равен нулю, то ЦФ является рекурсивным.

41.

Пример цифрового фильтра
Рассмотрим рекурсивный фильтр 1-го порядка (см. рис. 20), описываемый
разностным уравнением
y(n) = x(n) + a y(n–1),
(N = 1, b0 =1, b1 = 0, a1 = –a).
Рисунок 20 – Пример цифрового фильтрр 1-го порядка
1. Свойство линейности. Так как схема ЦФ состоит из линейных элементов, то
для нее справедлив принцип суперпозиции: если на входе фильтра
x(n) = c1·x1(n) + ... + cp·xp(n),
то на его выходе y(n) = c1·y1(n) + ... + cp·yp(n).
2. Система инвариантна к сдвигу (b0 = const, a1 = const), то есть это система с
постоянными во времени параметрами.
3. ИХ h(n) фильтра равна:
следовательно, это БИХ-фильтр.

42.

Пример цифрового фильтра
4. Сигнал на выходе определяется с помощью свертки:
5. Проверка устойчивости
0 < a < 1, то по определению суммы геометрической прогрессии
сумма S модулей отсчетов ИХ (см. рис. 21) определяется как
Если
Рисунок 21 – Импульсный отклик устойчивой системы
В этом случае система устойчива.

43.

Пример цифрового фильтра
Если a 1, то по определению суммы геометрической прогрессии сумма
модулей отсчетов ИХ определяется как
Поэтому в этом случае система неустойчива. Ее отклик на единичный
импульс показан на рис 22.
Рисунок 22 – Импульсный отклик
неустойчивой системы
6. Система физически реализуема, т.к. h(n
7. ЧХ системы описывается выражением
< 0) = 0.
S

44.

Пример цифрового фильтра
Рисунок 23 – АЧХ
исследуемого фильтра
К( ) = H(e j )
Рисунок 24 –ФЧХ
исследуемого фильтра
ЧХ – непрерывная функция частоты .
( ) = arg[H(e j )]
для угловых ,
циклических f, и
нормированных частот
ЧХ – периодическая функция с периодом, равным д.
К( ) – четная функция частоты (К( 1) = К(– 1)).
( ) – нечетная ( ( 1) = – (– 1)).
8. ИХ может быть вещественной только при вещественных ak и bk.
9. Передаточная функция:

45.

Связь передаточной функции с разностным
уравнением
Передаточная функция может быть вычислена через коэффициенты разностного
уравнения
a0 = 1
.
Выполнив Z-преобразование от обеих частей разностного уравнения, получим

46.

Полюса и нули передаточной функции
Передаточная функция системы:
Разложим числитель и знаменатель передаточной функции H(z) на множители:
Здесь
K – коэффициент усиления, вещественная величина,
b0
K
b0 .
a0
zк – нули ПФ (zero), pk – полюса ПФ (pole), – вещественные или комплексно
сопряженные величины. Таким образом, система задается множествами
К, {zk}, {pk}.

47.

Полюса и нули передаточной функции
Система устойчива, если для всего множества полюсов справедливо: pk
Для устойчивой системы полюса ПФ должны лежать внутри окружности
единичного радиуса (r = 1). См. примеры, приведенные на рис. 25.
Рисунок 25 – Слева – устойчивая система, справа - неустойчивая
1.

48.

Полюса и нули передаточной функции
Проанализируем устойчивость системы, описанной разностным уравнением
y(n) = x(n) + a y(n-1) .
Передаточная функция этой системы имеет вид:
b0
H z
.
1
1 az
z1 = 0. Если подобрать такое значение параметра a, что p1 = 0,5, система
будет устойчива, если p1 = 1,5 – система неустойчива (см. на рис. 26).
Рисунок 26 – Положение полюсов ПФ для устойчивой
системы
(p1 ) и неустойчивой (p1 )

49.

Пример исключения из правил
Нерекурсивные фильтры (НРФ) всегда имеют конечную ИХ длины
причем bk = h(k), k = 0 … N, где N и
и коэффициенты разностного уравнения.
N + 1,
bk – соответственно порядок фильтра
Рекурсивные фильтры (РФ), как правило, обладают бесконечной ИХ, но могут
иметь и конечную. Например, фильтру на рис. 27 соответствует уравнение
y(n) = x(n) – x(n–2) + y(n–1)
(b0 = 1, b1 = 0, b2 = –1, a1 = –1),
но этот РФ имеет ИХ длины 2, как это проиллюстрировано рисунком 28.
Рисунок 27 – Рекурсивный фильтр
2-го порядка
Рисунок 28 – Входной (сверху) и
выходной (снизу) сигналы этого ЦФ

50.

Соотношение параметров, характеризующих ЦФ
Сигнал на выходе ЦФ
можно описать:
Разностным уравнением:
y(n) = f [ bk, ak, x(n–m), y(n–m) ].
Сверткой:
Частотной характеристикой:
x(n) → ППФ → X(e j ),
Y(e j ) = X(e j )H(e j ),
Y(e j ) → ОПФ → y(n).
Здесь используются прямое
(ППФ) и обратное (ОПФ)
преобразования Фурье.
Передаточной функцией:
Рисунок 29 – Соотношение параметров ЦФ
x(n) → Z-преобразование → X(z),
Y(z) = X(z)H(z),
Y(z) → обр. Z-преобр. → y(n).

51.

Соотношение параметров, характеризующих ЦФ
Связь характеристик ЦФ:
5. Разностного уравнения и
импульсной характеристики:
подаем на вход единичный импульс:
x(n) = x0(n)→ разностн. уравнение
→ y(n) = h(n).
6. Передаточной функции с
разностным уравнением:
H(z) =
= Z{f [bk, ak, x(n–m), y(n–m)]}.
7. Импульсной и частотной
характеристик:
h(n) → ППФ → H(e j ).
8. Импульсной характеристики и
передаточной функции:
h(n)→ Z-преобразование → H(z).
9. Передаточной функции и
частотной характеристики:
Рисунок 29 – Соотношение параметров ЦФ
H(z = e j ) = H(e j ).

52.

Классификация ЦФ по форме АЧХ
По параметрам полосы пропускания ЦФ делятся на следующие типы:
1. Фильтры низких частот (ФНЧ) – пропускают частоты
среза (см. на рис. 30.а).
< 0, где 0 – частота
2. Фильтры высоких частот (ФВЧ) – пропускают частоты
> 0. (рис. 30.б).
3. Полосовые фильтры (ПФ) – пропускают частоты 01 < < 02 ( 01, 02
–
частоты среза) (см. на рис. 30.в).
4. Режекторные фильтры (РФ) – пропускают частоты < 01 и > 02 (рис. 30.г).
5. Другие ЦФ, например, имеющие несколько полос пропускания или подавления.
Рисунок 30 – Классификация ЦФ по параметрам полосы пропускания:
а – ФНЧ, б – ФВЧ, в – ПФ, г – РФ
Реальные АЧХ отличаются от приведенных идеальных:
1. Переходные полосы не имеют нулевой ширины.
2. АЧХ в полосах пропускания и подавления может не быть строго постоянной.

53.

Классификация ЦФ по форме реальной АЧХ
Баттерворта – АЧХ в пределах полос пропускания и задерживания изменяется
монотонно. (см. рис. 31 и 32)
На рис. 31 и рис. 32 использованы следующие обозначения:
p – граница полосы пропускания,
p = { p(1), p(2)} – границы полосы пропускания,
s – граница полосы подавления,
s = { s(1), s(2)} – границы полос подавления,
Rp – уровень пульсаций в полосе пропускания в дБ,
Rs – минимальное затухание в полосе задерживания в дБ.

54.

Классификация ЦФ по форме АЧХ
Чебышева 1 рода – имеются пульсации в полосе пропускания, крутизна АЧХ в
переходной полосе выше, чем у фильтра Баттерворта (см. рис. 33).
Чебышева 2 рода – имеются пульсации в полосе задерживания, крутизна АЧХ в
переходной полосе выше, чем у фильтра Баттерворта (см. рис. 34).
Эллиптический (Кауэра) – имеются пульсации в полосах пропускания и
задерживания, крутизна АЧХ в переходной полосе наиболее высокая (см. рис.
35).

55.

Прямая форма реализации ЦФ
Рисунок 36 – Структурная схема прямой формы реализации ЦФ
Прямая форма непосредственно соответствует разностному уравнению
При реализации этой схемы требуется от N до 2N элементов задержки (N
порядок ЦФ).
–

56.

Каноническая форма реализации ЦФ
Передаточная функция ЦФ описывается формулой
Представим выражение для передаточной функции в виде
Это соответствует следующей укрупненной вычислительной схеме (см. рис. 37)
Рисунок 37 – Представление ЦФ в виде пары последовательно соединенных
фильтров

57.

Каноническая форма реализации ЦФ
Выполним прямое а затем обратное Z-преобразование входного x(n),
выходного
y(n)
и «промежуточного»
w(n)
сигналов:

58.

Каноническая форма реализации ЦФ
Этим формулам соответствует
схема, представленная на рис. 38
Рисунок 38 – Преобразованная форма ЦФ
Получаем каноническую форму
реализации ЦФ, используя вместо двух
регистров сдвига один (см. на рис. 39).
Рисунок 39 – Каноническая форма
представления ЦФ
Таким образом можно сократить число
элементов задержки до двух раз.

59.

Транспонированная форма реализации ЦФ
Преобразуем основное разностное уравнение ЦФ следующим образом:
Изменим прямую форму
реализации ЦФ как
показано на рис. 40:
• изменим порядок
выполнения операций
задержки и умножения
сигналов,
• включим в каждый канал
умножения задержки разной
величины,
• один многовходовой
сумматор заменим на
несколько 2-х и 3-входовых.
Рисунок 40 – «Промежуточная» вычислительная схема ЦФ

60.

Транспонированная форма реализации ЦФ
Преобразуем схему,
представленную на рис. 40:
• поменяем местами схемы
сложения и задержки
сигналов,
• объединим задержки в
соответствующих каналах,
• будем использовать только
схемы задержки на 1 такт.
Рисунок 40 – «Промежуточная» вычислительная схема ЦФ
Рисунок 41 – Транспонированная форма представления ЦФ

61.

Дискретные преобразования

62.

Переход к дискретному преобразованию Фурье
Выше анализировалась обработка дискретизированных во времени сигналов,
имеющих непрерывный по частоте Фурье-спектр. Рассмотрим теперь случаи,
когда и частота имеет дискретную форму.
Сигнал x(nT), дискретизированный с частотой д
= 2 /T, при – n <
связан со своим спектром X(e j T) прямым и обратным преобразованиями Фурье:
Спектр X(e j T) – это непрерывная периодическая (с периодом д) функция
частоты.
Рассмотрим функции:
бесконечную во времени периодическую: xp(nT) c периодом Тп
= NT,
xр(nT) = xр[(n+kN)T] при k = 0, 1, 2 … ;
конечную: x(nT) = 0 при n<0 и n >N–1, имеющую длительность NT = Tп.

63.

Дискретное преобразование Фурье
Для таких функций существуют прямое и обратное дискретные преобразования
Фурье (ПДПФ и ОДПФ):
k – отсчеты частоты
n – отсчеты времени
Они получены из непрерывных преобразований путем дискретизации оси частот
с шагом
= 2 /Tп = 2 /(NT) = д/N.
X(k ) представляет собой дискретную периодическую (с периодом N = д)
функцию, состоящую из отсчетов непрерывного спектра X(e j T), взятых с
интервалом :
X(k ) = X(e j k nT).
Если Т = const, то
д = const и = const. Поскольку = 2 NT, запишем:

64.

Дискретное преобразование Фурье
Введем в этих формулах обозначение:
.
Тогда получим следующие формы записи для прямого и обратного ДПФ:

65.

Свойства дискретного преобразования Фурье
1.
ДПФ – решетчатая функция, отсчеты которой совпадают с соответствующими
значениями преобразования Фурье и следуют с шагом
2.
= д/N по частоте.
ДПФ – периодическая функция с периодом в N отсчетов:
X(k) = X(k + mN), m = 0, 1, 2 …
3. Свойство линейности:
x n ДПФ
X k , y n ДПФ
Y k
a1 x n a2 y n ДПФ
a1 X k a2Y k .
при любом числе слагаемых.
4. ДПФ задержанной на
m
тактов последовательности:
x n ДПФ
Y k x n m ДПФ
W mkY k .
__Для конечных последовательностей осуществляется циклический сдвиг.
5. Свойство симметрии для действительных последовательностей:
X(k) = X(N–k).

66.

Свойства дискретного преобразования Фурье
6. Связь с Z-преобразованием:
По определению
Подстановка
дает
Так можно вычислить
__преобразование Фурье по результатам вычисления z-преобразования.
7. Квадратичная зависимость числа умножений от длины
N является основным недостатком ДПФ. Требуется
__N2 комплексных умножений (4N2 умножений действительных чисел) и
__N(N–1) комплексных сложений (2N(N–1) действительных).
__последовательности
8. Размер оперативной памяти: для записи N отсчетов входной
__последовательности и N отсчетов ДПФ необходимо 2N ячеек для хранения
__комплексных чисел (4N – для хранения действительных чисел).

67.

Вычисление дискретного преобразования
Фурье действительных последовательностей
Можно вычислить ДПФ двух действительных последовательностей, применив
ДПФ один раз.
Пусть x(n) и y(n) – действительные последовательности (n = 0, … , N−1).
Последовательности разной длины, их можно выровнять, дополнив нулями.
Определим спектры X(k) и Y(k) последовательностей:
1. Сформируем последовательность v(n)
= x(n) + j y(n) и вычислим её ДПФ:
Определим значения вещественных и мнимых частей V(k) и V(N–k) учитывая,
что для ДПФ действительных последовательностей x(n) и y(n) справедливы
следующие соотношения:
Re [X(k)] = Re [X(N–k)],
Re [Y(k)] = Re [Y(N–k)],
Im [X(k)] = – Im [X(N–k)],
Im [Y(k)] = – Im [Y(N–k)].

68.

Вычисление дискретного преобразования
Фурье действительных последовательностей
V(k)=Re[X(k)]+jIm[X(k)]+jRe[Y(k)]-Im[Y(k)]
Re [V(k)] = Re [X(k)] – Im [Y(k)],
(1)
Im [V(k)] = Im [X(k)] + Re [Y(k)],
(2)
Re [V(N–k)] = Re [X(N–k)] – Im [Y(N–k)] = Re [X(k)] + Im [Y(k)], (3)
Im [V(N–k)] = Im [X(N–k)] + Re [Y(N–k)] = – Im [X(k)] + Re [Y(k)]. (4)
Попарно складывая или вычитая равенства (1) – (4), получим значения
вещественных и мнимых частей X(k) и
(1) + (3)
(2) – (4)
(2) + (4)
(3) – (1)
→
→
→
→
Y(k)
Re [X(k)] = ½ { Re [V(k)] + Re [V(N–k)]},
Im [X(k)] = ½ {Im [V(k)] – Im [V(N–k)]},
Re [Y(k)] = ½ {Im [V(k)] + Im [V(N–k)]},
Im [Y(k)] = ½ {Re [V(N–k)] – Re [V(k)]}.
Таким образом вычислено ДПФ двух действительных последовательностей путем
выполнения единственной операции ДПФ.

69.

Вычисление обратного ДПФ (ОДПФ) с
помощью операции прямого ДПФ (ПДПФ)
Пусть известно ДПФ X(k) последовательности x(n) для k
= 0, … , N–1.
Формула ОДПФ имеет вид
Обозначим как
Тогда
x*(n) и X*(k) функции, комплексно-сопряженные с x(n)
и X(k).
Умножение левой и правой части равенства на N дает
где X(n) – ДПФ функции X*(k).
Следовательно, ОДПФ вычисляется с помощью прямого ДПФ следующим образом:
X(k) →*→ X*(k) →ПДПФ→ X(n) →/N→ x*(n) →*→ x(n).

70.

Быстрое преобразование Фурье с
прореживанием во времени (алгоритм Кули-Тьюки)
x(n), n = 0, …, N–1, N = 2L, L >0 – целое число.
Определим её ДПФ X(k), k = 0, … , N–1.
Разобьем x(n) на две подпоследовательности (см. на рис. 42), в одну из которых
попадут четные члены (x1(n)), а в другую – нечетные (x2(n)):
x1(n) = x(2n),
n = 0, … , N/2–1.
x2(n) = x(2n+1),
n = 0, … , N/2–1.
Дана последовательность
Рисунок 42 – Деление
входной
последовательности
(сверху) на
подпоследовательности
четных (посредине) и
нечетных (снизу) отсчетов

71.

Быстрое преобразование Фурье с
прореживанием во времени
Определим ДПФ от x(n):
Выполнение преобразования:
и подставим результат преобразования в формулу для X(k):

72.

Быстрое преобразование Фурье с
прореживанием во времени
X(k) определено для k = 0, …, N–1, но X1(k) и X2(k) определены для
k = 0, …, N/2–1. Будем вычислять X (k) так:
Выполним во второй формуле следующее преобразование:
Вычисляем ДПФ последовательности так:
x(n) → {x1(n), x2(n)} → {X1(k), X2(k)} → X(k).
Число комплексных умножений вместо N2 равно
2 (N/2)2+N/2=N/2 (N+1)≈N2/2.

73.

Быстрое преобразование Фурье с
прореживанием во времени
Конечные результаты ДПФ попарно образуются из одних и тех же элементов:
и так далее.
Для получения результатов каждой пары вычислений может быть использована
единая базовая функция, показанная на рис. 43 и рис. 44:
Рисунок 43 – Вычислительный граф
для единой базовой вычислительной
функции ДПФ
Рисунок 44 – Вычислительный
граф «бабочка» для БПФ с
прореживанием по времени

74.

Быстрое преобразование Фурье с
прореживанием во времени
Дальнейшего ускорения вычислений можно достичь, осуществив аналогичное
разбиение подпоследовательностей x1(n) и x2(n) прореживанием по времени.
Пусть, например, последовательность x(n) имеет длину N
окончательный алгоритм формируется в 3 этапа (L
= 23 = 8. Тогда
= 3).
1-й этап. Полученный вычислительный граф можно представить в виде,
показанном на рис. 45. Требуется 2×16+4=36<64=N2 комплексных умножений.
Рисунок 45 – Вычислительный граф, полученный после 1-го этапа преобразований

75.

Быстрое преобразование Фурье с
прореживанием во времени
2-этап. Теперь последовательности x1(n) и x2(n) длины N/2
= 4 делятся
соответственно на подпоследовательности a(n), b(n), c(n), d(n) длины N/4=2:
x1(n) → a(n), b(n);
x2(n) → c(n), d(n).
где A(k), B(k) – ДПФ от a(n), b(n). Аналогично преобразуем X2(k). Тогда
вычислительный граф ДПФ на 2-м этапе принимает вид, приведенный на рис. 46.
Рисунок 46 – Вычислительный граф ДПФ, полученный на 2-м этапе преобразований

76.

Быстрое преобразование Фурье с
прореживанием во времени
3-й этап. Покажем, что двухточечное ДПФ можно выполнитьс помощью базовой
операции БПФ. На рис. 47 представлен граф двухточечного ДПФ, полученный с
учетом того, что
Рисунок 47 – Вычислительный граф двухточечного ДПФ
Тогда граф базовой операции БПФ для 2-точечной последовательности можно
представить в виде, показанном на рис. 48.
Рисунок 48 – Вычислительный граф базовой двухточечного операции БПФ

77.

Быстрое преобразование Фурье с
прореживанием во времени
Учитывая, что
окончательный граф вычисления 8-точечного БПФ
принимает вид, представленный на рис. 49.
Рисунок 49 – Вычислительный граф 8-точечного БПФ с прореживанием по времени
R = L = log2(N) = 3. S = N/2 = 4
умножений на каждом этапе. Всего M = R×S = N/2 log2 (N) = 12 < 64 = N2
Количество этапов преобразования
умножений. Поскольку
, число комплексных умножений уменьшено до 5.

78.

Быстрое преобразование Фурье с
прореживанием по частоте (алгоритм Кули-Тьюки)
x(n), n = 0, …, N–1, N = 2L, L >0 – целое число.
Определим её ДПФ X(k), k = 0, … , N–1.
Разобьем x(n) на две подпоследовательности (см. на рис. 50), в одну из которых
попадает первая половина членов x(n), а в другую – вторая:
Дана последовательность
Рисунок 50 – Деление входной
последовательности (вверху) на
подпоследовательности первой
половины (посредине) и второй
половины (внизу) отсчетов

79.

Быстрое преобразование Фурье с
прореживанием по частоте
По определению ДПФ от x(n) имеет вид:
Далее выполняются преобразования, аналогичные разделу, посвященному БПФ с
прореживанием во времени.
Основное отличие:
- определяются по разным формулам четные и нечетные отсчеты БПФ;
- и в качестве базовой вычислительной операции используется граф “бабочка”
показанный на рис. 51.
Рисунок 51 – Вычислительный граф «бабочка» для БПФ с прореживанием
по частоте

80.

Быстрое преобразование Фурье с
прореживанием по частоте
Проводя соответствующие преобразования для последовательности длины
N = 8, получим результирующий граф вычисления БПФ, показанный на рис. 52.
Рисунок 52 – Вычислительный граф 8-точечного БПФ с прореживанием по частоте
Как и при применении прореживания по времени, количество комплексных
умножений М
= 12, или при исключении умножений на W80 = 1 число
комплексных умножений М1 = 5.

81.

Быстрое преобразование Фурье (БПФ)
Оба алгоритма (с прореживанием по времени и по частоте) выполняют
дискретное преобразование Фурье числовой последовательности :
x(n), n = 0, …, N–1;
→
X(k), k = 0, …, N–1;N = 2L;
где L – целое положительное число. Если это условие не выполняется, то можно
дополнить последовательность нулями до длины, равной ближайшему N
= 2 L.
Для обоих алгоритмов БПФ количество комплексных умножений можно еще
уменьшить, принимая во внимание, что
j
WN0 = 1, WNN /4 =e 2 = cos - j sin = - j.
2
Для получения коэффициентов ,
2
можно применять:
• Табличный метод – требует N/2 комплексных ячеек памяти.
• Программный метод – требует использования подпрограмм sin(x) и cos(x),
__что замедлит работу.
• Рекуррентный метод: основан на использовании соотношения
при
Его применение возможно, т.к. на каждом этапе показатель степени
m меняется с одним и тем же шагом.
Например, для N
трех этапах имеют вид
соответственно. Необходимо запомнить только шаги
= 8 коэффициенты на
и
и
,
.

82.

Быстрое преобразование Фурье (БПФ)
Пересортировка входных или выходных данных
Меняется порядок
следования входных
данных
Рисунок 49 – Вычислительный граф 8-точечного
БПФ с прореживанием по времени
Меняется порядок
следования входных
данных
Рисунок 52 – Вычислительный граф 8-точечного
БПФ с прореживанием по частоте

83.

Быстрое преобразование Фурье (БПФ)
Пересортировка входных или выходных данных
Пересортировка данных может быть выполнена с помощью двоичной инверсии.
Если номер элемента массива до пересортировки записывается L-разрядным
двоичным числом
a0 a1 ... aL-1
aL-1 ... a1 a0 ,
то его двоичная инверсия имеет вид
. Она и определяет номер элемента массива данных после
пересортировки, как это показано на рис 53.
Рисунок 53 – Пример изменения (пересортировки) номеров элементов
последовательности методом двоичной инверсии
Например, элемент x(6) массива после пересортировки окажется на месте
элемента x(3):
x(610) = x(1102) → x(0112) = x(310).

84.

Единый подход к алгоритмам БПФ
При вычислении БПФ мы считали длину преобразуемой последовательности
N=2L, где L – целое число. Если это не выполнялось, последовательность
дополнялась нулями до ближайшей длины N=2L . Основой подхода была
возможность представления одномерной последовательности в виде
многомерного массива, например:
0, 1, 2, 3, 4, 5, 6, 7
2
Длина: N
= 8 = 2 2 2
2
2
Если длина последовательности простое
число, представить совокупность ее данных в
виде многомерного массива не получится.
Непростые числа можно разложить на
множители, например, 60 = 4 3 5,
тогда одномерную последовательность можно
представить как многомерную и выполнить
БПФ.
4
5
3

85.

Единый подход к алгоритмам БПФ
0, 1, 2, …………………………………………………………., 59
60 = 12 5 = 4 3 5,
разложена на строки длиной 12, каждая строка также
раскладывается на подстроки длиной 4.
Последовательность длиной

86.

Единый подход к алгоритмам БПФ
(1)
Пусть после выполнения ДПФ двумерной последовательности получим
также двумерную последовательность, строки которой нумеруются
переменной s, а столбцы нумеруются переменной r. Тогда номер k
текущего элемента массива вычислим как
Тогда от одномерного ДПФ (1) можно перейти к многомерному
следующим образом:
(2)

87.

Единый подход к алгоритмам БПФ
.
(2)
Перемножим содержимое скобок в показателе степени в формуле (2) и
учтем при этом, что длина последовательности N=М L, а
WMLlr = WNlr = 1, т.к. по определению:
.
,
.
(3)
где q(s, m) – L-точечное ДПФ m-того столбца исходного массива с ядром
WM преобразования.
Теперь найдем новый массив h(s, m) = q(s, m) Wms, где Wms –
поворачивающий множитель. Тогда формула (3) примет вид:
.
Это M-точечное преобразование каждой из строк матрицы h(s, m) с
ядром преобразования WL.

88.

Единый подход к алгоритмам БПФ
0, 1, 2, 3, 4, …, 59
(1)
.
,
(3)
Таким образом ДПФ (1) размерности N = М L (вычислительная
сложность пропорциональна N2 = М2 L2 ) было заменено на (3) последовательным применением ДПФ размерности M и размерности L
и дополнительным N-кратным умножением на поворачивающий
множитель (вычислительная сложность пропорциональна
M2+L2+N << N2) .

89.

Единый подход к алгоритмам БПФ
.
.
(3)
В формуле (3) можно изменить порядок суммирования.
(4)
Варианты (3) и (4) можно уподобить выполнению алгоритма Кули-Тьюки
соответственно с прореживанием по времени или по частоте.

90.

Единый подход к алгоритмам БПФ
Вычислительная сложность
Рассмотрим случай представления одномерной последовательности
трехмерной:
0, 1, 2, 3, …, N-1
L
Длина последовательности:
N = L M P
P
M
В этом случае ДПФ будет выполняться в виде следующей
последовательности операций:
Вычислительная сложность:

91.

Единый подход к алгоритмам БПФ
Вычислительная сложность: общий случай
N=N1 N2 N3 N4 … NJ
Рисунок – Пример
выполнения БПФ с
непостоянным
основанием

92.

Быстрая круговая свертка
Обозначим через
xp(n)
и
hp(n)
дискретные периодические
последовательности с одинаковыми периодами, равными N. Свертка yp(n) этих
последовательностей имеет вид:
yp(n) – периодическая последовательность с периодом, равным N.
Запишем выражения для ДПФ последовательностей-операндов свертки:
Это теорема о свертке: Фурье-спектр свертки равен произведению спектров ее
операндов. Таким образом, алгоритм вычисления быстрой свертки имеет вид:
xp(n), hp(n)→БПФ→Xp(k), Hp(k)→×→Yp(k)→ОБПФ→yp(n).

93.

Теорема Бореля
Для аналоговых сигналов теорема, сходная с теоремой о свертке была доказана
с применением преобразования Лапласа как теорема Бореля.
Для функций непрерывного времени свертка описывается интегралом Дюамеля:
Преобразование Лапласа от y(t) имеет вид:
Рисунок – Изменение
пределов интегрирования
Здесь был изменен порядок интегрирования, были сделаны замены переменных
(t1 = t–s; t = t1+s; dt = dt1) и изменены пределы интегрирования (см. рисунок).

94.

Быстрая линейная (апериодическая) свертка
Пусть x(n) – входной сигнал (n= 0, …, Nx–1), h(n) – ИХ ЦФ (n = 0, …,
Тогда сигнал на выходе ЦФ определяется с помощью прямой свертки:
Сигнал y(n), вычисленный с помощью свертки, имеет
ненулевых отсчетов.
Nh–1).
N = Nx + Nh – 1
Вычисление быстрой сверткой осуществляется в следующем порядке:
1.Последовательности x(n) и h(n) удлиняются до длины N путем добавления
в каждую соответствующего числа нулей и рассматриваются как периодические
xp(n)
и hp(n) с периодом N; при выполнении БПФ длина
N обеих
последовательностей должна быть дополнительно увеличена до Ne
–
ближайшего значения, требуемого применяемым алгоритмом БПФ, например,
при применении алгоритма Кули-Тьюки до Ne=2L, где
L – целое число.
2.Для функций xp(n) и hp(n) вычисляются их БПФ Xp(k) и Hp(k).
3.Определяется произведение спектров:Yp(n) = Xp(k) Hp(k).
4.С помощью обратного ДПФ по Yp(n) находится функция yp(n).
Подразумевается, что это один период длины Ne выходнго сигнала yp(n).

95.

Плюсы и минусы быстрой свертки
• При вычислении быстрой линейной свертки операндов x длиной Nx и h длиной
Nh требуется дополнить оба операнда до длины N=Nx+Nh-1 (для простоты
опущено дополнение до длины 2L при использовании алгоритма Кули-Тьюки).
• Вычислительная сложность выполнения БПФ каждого операнда и обратного
БПФ будет N/2 log2 (N). Учитывая выполнение N операций умножения при
перемножении спектров, получаем суммарную вычислительную сложность
быстрой свертки:
CБ = 3[N/2 log2 (N)]+N = 3[(Nx+Nh–1) /2 log2 (Nx+Nh–1)]+(Nx+Nh–1) .
• При вычислении прямой свертки выполняется СП=(Nx+Nh-1) Nh умножений
(для простоты оценки считается что Nh<<Nx, а умножения на нуль не
исключаются из рассмотрения. Не трудно убедиться, что использование быстрой
свертки позволяет существенно сократить количество вычислений в случае
близких значений длины ее операндов (в этом случае CП 2N2).
• Однако при существенном различии длины операндов использование быстрой
свертки может оказываться невыгодным. Например, при Nh=3, Nx >>Nh
CП 3Nx. Тогда CП<CБ даже без учета того что быстрая свертка всегда
использует комплексные умножения, которых вчетверо больше чем
действительных. Проблема решается использованием секционированной свертки.

96.

Секционированная свертка
h(m)
N
n
x(m)
n
ĥ(m)
2N
n
x0(m)
2N
n
x1(m)
2N
n
x2(m)
2N
n
x3(m)
2N
n
• ИХ считается
периодической с
длиной периода N
• Удвоение периода ИХ,
вторая половина
периода заполняется N
нулями
• Деление сигнала на
“периоды” длиной 2N.
Соседние периоды
налагаются на N
отсчетов. Первый
период начинается с N
нулевых отсчетов
• Вычисление свертки
каждого периода
сигнала с расширенной
ИХ, отбрасывание
первых N отсчетов
каждой свертки
• Конкатенация
результатов сверток в
единый сигнал.

97.

Ошибки квантования

98.

Источники и форма проявления ошибок
квантования
Квантование – это процесс представления чисел ограниченным числом разрядов.
На различных этапах
обработки входного сигнала
xн(t) квантуются следующие
сигналы и параметры (см.
рис . 65:
• входной сигнал xн(t);
Рисунок 65 – Этапы обработки сигнала, на
которых сказываются эффекты квантования
• коэффициенты ЦФ bk, ak;
• результаты
арифметических операций в
ЦФ;
• коэффициенты и
результаты ДПФ и БПФ;
• и др.
Рисунок 66 – Ошибки квантования методом
усечения
Рис. 66 иллюстрирует
ошибку, возникающую при
квантовании исходного
сигнала, подлежащего
обработке.

99.

Ошибки квантования сигнала
Рассмотрим равномерное квантование с шагом Q в b-разрядном АЦП (см. рис. 66):
• Количество уровней квантования
N = 2b ;
xн(n) –точное значение непрерывного входного
сигнала в момент времени t = nT;
x(n) – значение отсчетов квантованного сигнала. Рисунок 67 – Формирование
квантованного сигнала
e(n) = x(n) – xн(n) – ошибка квантования
(см. рис. 67).
1. e(n) – дискретный стационарный
случайный процесс,
2. e(n) и x(n) – не коррелированные
случайные величины,
3. e(n) и e(m n) – не
коррелированные случайные
величины,
4. e(n) равномерно распределена в
интервале Q = U / 2b,
где U – динамический диапазон
Рисунок 66 – Ошибки квантования
методом усечения
сигнала, в котором выполняется
квантование.

100.

Ошибки квантования сигнала методом усечения
Рисунок 67 – Формирование
квантованного сигнала
• e(n) = x(n)–xн(n) –
случайная величина,
равномерно распределенная в
(–Q, 0];
• m e = –Q/2 –
интервале
Рисунок 68 – Квантование методом усечения:
Кm = mQ – уровни квантования,
m – целое число,
Q – шаг квантования
Метод квантования:
Km xн(n) Km+Q x(n) = Km
математическое ожидание
ошибки;
• D e = Q 2/12 – дисперсия
ошибки;
• e max = Q – максимальное
по модулю значение ошибки.

101.

Ошибки квантования сигнала методом округления
• e(n) = x(n)–xн(n) –
случайная величина,
равномерно распределенная в
интервале
(–Q/2, Q/2];
• m e = 0 – математическое
ожидание ошибки;
• D e = Q 2/12 – дисперсия
ошибки;
Рисунок 69 – Квантование методом округления
Кm = mQ – уровни квантования,
m – целое число,
Q – шаг квантования
Метод квантования:
Km –Q/2 xн(n) Km+Q/2 x(n) = Km
• e max = Q/2 – максимальное
по модулю значение ошибки.

102.

Отношение сигнал/шум при квантовании
Пусть гармонический сигнал с амплитудой Us квантуется b-разрядным
квантователем по методу округления c шагом квантования Q. Дисперсия ошибки
квантования De = Q2/12. Отношение амплитуды сигнала к
среднеквадратической ошибке квантования:
Необходимое число уровней квантования:
Тогда отношение сигнал/(шум квантования) имеет вид:
Учитывая, что N
= 2b, предыдущую формулу можно представить в виде:

103.

Шумы квантования, приведенные к выходу ЦФ
Пусть квантованный сигнал на выходе ЦФ x(n)
= xн(n)+e(n),
где xн(n) –
сигнал до квантования. Статистические характеристики шумов квантования
e(n)
при квантовании с шагом Q по методу округления имеют следующие значения:
m e = 0,
D e = Q 2/12,
emax = Q/2,
Для ЦФ с ИХ h(n) сигнал на выходе
определяется с помощью свертки:
где yн(n) – выходной сигнал без квантования, евых(n) – шумы квантования на
выходе.
Можно при известной ИХ h(n)
и допустимой дисперсии Dвых
шумов квантования на выходе
определить необходимую
разрядность b квантователя,
учитывая, что Q
= 2–b.

104.

Пример расчета параметров шумов
квантования на выходе ЦФ
Определим дисперсию шумов квантования на выходе цифрового рекурсивного
фильтра 1-го порядка, показанного на рис. 70. и описываемого следующим
разностным уравнением:
y(n) = x(n) + a·y(n–1), a < 1.
Пусть De – дисперсия шумов квантования сигнала на входе ЦФ.
ИХ этого фильтра имеет вид:
a n , n 0;
h ( n)
0, n 0.
Дисперсия шумов квантования на
выходе ЦФ имеет вид:
Рисунок 70 – Пример рекурсивного
фильтра 1-го порядка
При
а 1, De .

105.

Шумы квантования при выполнении
арифметических операций в ЦФ
• При умножения целых чисел одинаковой разрядности разрядность результата
может удвоиться.
• Результат yн(n) умножения приводится к допустимой разрядности мантиссы
отбрасыванием ряда значащих разрядов.
• Отбрасывание младших разрядов приводит к ошибкам, сходным с ошибкам
квантования (см. рис. 71) и описывается выражением
y(n) = x(n)·a + e(n) = yн(n) + e(n).
Рисунок 71 – Модель ошибки квантования произведения
Рассмотрим шумы квантования, возникающие при умножении в различных
схемах ЦФ. Пусть квантование производится по методу округления.

106.

Шумы квантования при выполнении операций
умножения в нерекурсивном фильтре
Рисунок 72 –
Общий вид
нерекурсивного
фильтра
Рисунок 73 –
Нерекурсивный
фильтр с
ошибками
квантования при
умножении
ek(n) – ошибка квантования произведения в k-ом канале с
математическим ожиданием me = 0 и дисперсией Dе = Q2/12.
На рис. 73

107.

Шумы квантования при выполнении операций
умножения в нерекурсивном фильтре
Рисунок 73 –
Нерекурсивный
фильтр с
ошибками
квантования при
умножении
Рисунок 74 –
Эквивалентная
схема
нерекурсивного
ЦФ с ошибками
квантования
произведений

108.

Шумы квантования при выполнении операций
умножения в нерекурсивном фильтре
Рисунок 74 –
Эквивалентная
схема
нерекурсивного
ЦФ с ошибками
квантования
произведений
– сумма ошибок в каналах, равная ошибке
квантования на выходе ЦФ
– дисперсия ошибки на выходе ЦФ
вычисляется суммированием
дисперсий Dе в N каналах
Дисперсия Dвых шума квантования произведений на выходе фильтра зависит от
порядка N фильтра и шага квантования Q и не зависит от коэффициентов bk.

109.

Шумы квантования при выполнении операций
умножения в рекурсивном фильтре
Рисунок 75 – Рекурсивный фильтр с ошибками квантования при умножении

110.

ШумыквантованиярезультатовумноженияврекурсивномЦФ
Рисунок 76 –
Эквивалентная
схема
рекурсивного
фильтра с
ошибками
квантования
произведений
Обозначим как hос
ИХ системы
обратной связи ЦФ.
Тогда:
– сумма ошибок в каналах, D =(2N+1)Q2/12 – ее дисперсия;
, eвых(n) e (n), т.к. выходная ошибка зависит и
от сигналов на предыдущих тактах времени;
зависит от N, Q, ak, hос.

111.

Шумы квантования при выполнении
дискретного преобразования Фурье
Прямое ДПФ описывается формулой
Граф алгоритма ДПФ, учитывающий ошибки квантования произведений, показан
на рис. 77. Этот вычислительный граф может быть приведен к виду,
представленному на рис. 78, причем суммарная по всем каналам ошибка
e =eвых вычисляется по формуле:
Рисунок 77 – Вычислительный граф
алгоритма ДПФ, учитывающий ошибки
квантования произведений
Рисунок 78 – Приведенный
вычислительный граф алгоритма
ДПФ, учитывающий ошибки
квантования произведений

112.

Шумы квантования при выполнении
дискретного преобразования Фурье
Рисунок 77 –
Вычислительный граф
алгоритма ДПФ,
учитывающий ошибки
квантования произведений
Поскольку W – комплексный сомножитель, ошибки
являются комплексными величинами:
ek
в каналах также
ek = e k + je k .
Дисперсия каждой из составляющих e k и e k равна De = Q2/12, поэтому
дисперсия комплексного числа еk равна D = 2De = Q2/6, а дисперсия
ошибки квантования при вычислении каждого значения X(k) равна
DX = N·D = N·Q2/6.

113.

Шумы квантования при выполнении быстрого
преобразования Фурье
Рисунок 79 –
Вычислительный граф
базовой операции БПФ с
прореживанием по времени
Рисунок 80 –
Вычислительный граф
базовой операции БПФ,
учитывающий ошибки
квантования произведений
W = W +jW , b = b +jb . Тогда
bW+e = b W +e1 + j(b W +e2) + j(b W +e3) – b W –e4 .
Введем обозначения:
Ошибка на выходе равна
e = (e1 – e4) + j (e2 + e3).
Дисперсия каждой составляющей (действительной и мнимой) ошибки каждого из
= Q2/12. Дисперсия полной ошибки при
выполнении каждой базовой операции равна De = 4Dek = Q2/3.
выходов базовой операции равна Dek

114.

Шумы квантования при выполнении быстрого
преобразования Фурье
Количество
B
базовых операций, выполняемых последовательно при расчете
каждого отсчета БПФ (см. рис. 81, где N=2L=8,
членов геометрической прогрессии :
L=3), определяется как сумма
L 1
B 2k 2 L 1 N 1
k 0
Рисунок 81 –
Вычислительный граф
8-точечного БПФ с
прореживанием по
времени
Для рассматриваемого примера В = 7. Таким образом, дисперсия ошибки,
возникающей вследствие квантования результатов умножения при вычислении
каждого отсчета БПФ, может быть рассчитана по формуле
D = De B = (N–1) Q2/3.

115.

Предельные циклы
Если ЦФ устойчив, при прекращении сигнала на входе выходной сигнал должен
0, т. е. при x(n n0) = 0 y(n ) 0. При квантовании чисел
возможен эффект «предельных циклов»: y(n ) k0 0; k0 – мертвая
стремиться к
зона.
Рисунок 82 – Предельные циклы: сверху входной сигнал; посредине – выходной
сигнал при k0
= 0;
снизу – выходной сигнал при
k0 0

116.

Предельные циклы
Рассмотрим пример рекурсивного фильтра 1-го порядка, описываемого
разностным уравнением
y(n) = x(n)+a·y(n–1), а = 0,9 , n0 = 0 , y(–1) = 7. x(n 0) = 0
=> y(n 0) = a·y(n–1).
Для шага квантования Q = 1 расчет выходного сигнала приведен в таблице.
Таблица – Расчет сигнала на выходе фильтра
k0 мертвой зоны. При квантовании округлением:
y(n) = k если a·k k – 0,5 ;
=> k (1 – а) 0,5 ;
=> k 0,5 / (1 – а) .
Величина мертвой зоны находится как максимальное целое число k,
Определим величину
(*)
удовлетворяющее условию (*). Например, для рассматриваемого фильтра:
а = 0,9 => k 0,5 / 0,1 = 5
=> k0 = 5; => y(n) = 7, 6, 5, 5, 5 ;
а = 0,1 => k 0,5 / 0,9 = 0,55 => k0 = 0; => y(n) = 7, 1, 0, 0, 0 .

117.

Предельные циклы
Если а > 0, то k0 имеет постоянный знак, при
знакопеременны, как показано на рис. 83.
Рисунок 83 – Предельные циклы при
а<0
a > 0 (слева)
и
значения
k0
a < 0 (справа).

118.

Неравномерное квантование
• При равномерном квантовании усечением шум квантования не превышает
шага квантования Q.
• Неравномерное квантование учитывает статистические свойства сигнала, его
применяют для минимизации среднеквадратической величины шума квантования.
Шаги квантования меньше для более вероятных уровней сигнала (см. на рис. 84).
Рисунок 84 – Неравномерное квантование сигнала: справа – аналоговый сигнал
и результат его дискретизации по времени и квантования по уровню, слева –
плотность распределения вероятности значений аналогового сигнала

119.

Неравномерное квантование
x, описываемый плотностью
распределения вероятностей p(x), делится на N неодинаковых зон
квантования а0…а1, а1…а2, … аN-1...aN, каждой из которых ставится в
соответствие квантованное значение bk ( bk [ak-1,ak] ).
Диапазон возможных значений сигнала
Средний квадрат ошибки рассчитывается по формуле
Приравнивание к нулю частных производных этого выражения по ak и bk
позволяет определить оптимальные параметры квантования:
ak
bk 1 bk
.
2
В телефонии наиболее вероятны малые значения речевого сигнала, поэтому
• равномерное квантование потребует 12 двоичных разрядов (4096 уровней),
• неравномерное – только 8 двоичных разрядов (256 уровней квантования).

120.

Спектральный анализ
В контексте цифровой обработки сигналов с помощью спектрального анализа
будем
• обнаруживать на фоне шумов гармонического сигнала с неизвестными
__амплитудой и частотой;
• измерять эти его параметры с помощью ДПФ (БПФ).
Наблюдаем аналоговый сигнал xн(t) на интервале времени длиной Тs
(0<t<Ts):
- при отсутствии полезного сигнала это шум;
- или это смесь полезного сигнала и шума.
Полезный сигнал us(t) гармонический с неизвестными амплитудой Us и частотой fs:
Известно :
us(t) = Us cos(2 fs t) = Us cos( st).
• 1 s 2 .
• Uш (t) - аддитивный гауссов шум с математическим ожиданием 0, и дисперсией
__Dш = ш2 = Pш 0, где ш - СКО, Pш – мощность шума.
Дискретизируем сигнал xн(t) с интервалом Т = 2 / д (с частотой д = 2 fд) :
• xн(t) →x(nT), n=0 … N-1,
• N = [ Ts/T ], где [.] – результат округления.

121.

Спектральный анализ
Введем следующие обозначения для спектров сигналов:
• Xн(j ) – спектр непрерывного сигнала xн(t), полученный преобразованием
Фурье;
• X(e j t) – спектр дискретизированного сигнала x(nT), полученный с помощью
_преобразования Фурье;
• X(k ) – спектр дискретизированного сигнала x(nT), полученный с помощью
_ДПФ, где – основная частота ДПФ.
= 2 /(NT) = 2 /Ts = д /N.
• Номера отсчетов дискретного спектра, соответствующих границам
_анализируемого частотного диапазона,
k1
и
k2 (k1 = [ 1/ ], k2 = [ 2/ ]).

122.

Спектральный анализ
Будем анализировать амплитудные спектры X(k ) в диапазоне k
= k1, …, k2.
ωд/2
Рисунок 85 – Спектр сигнала при ш = 0 : вверху – аналогового; посредине –
дискретизированного; внизу –полученный с помощью ДПФ

123.

Спектральный анализ: обнаружение сигнала
Согласно статистической теории обнаружения сигнала при наличии шумов в
канале связи рассматриваются две статистические гипотезы :
X(k ) → ? → H0:(Us = 0) – гипотеза H0: сигнала нет;
X(k ) → ? → H1:(Us 0) – гипотеза H1: сигнал есть.
Если хотя бы один отсчет спектра в анализируемом диапазоне частот k
превышает по амплитуде X(k ) установленный порог Uп (см. также на рис.
86), принимается гипотеза H1, в противном случае принимается гипотеза H0 :
X(k ) > Uп → H1,
X(k ) < Uп → H0,
k [k1; k2], ( ш 0).
Рисунок 86 – Принятие решения о
наличии полезного сигнала;
здесь km – номер максимального
спектрального отсчета:

124.

Спектральный анализ: обнаружение сигнала
Статистическими характеристиками обнаружителя являются:
• вероятность F ложной тревоги – вероятность принятия гипотезы H1 при Us=0:
F = P{ X(km ) > Uп} при Us = 0;
• вероятность D правильного обнаружения – принятия гипотезы H1 при Us
0:
D = P{ X(km ) > Uп} при Us 0.
F + D 1, так как суммируются условные вероятности,
В общем случае
взятые при разных условиях.
Выбор порога Uп определяется принятым критерием обнаружения. В подобных
задачах часто используется критерий Неймана-Пирсона:
• сначала фиксируется допустимая вероятность ложной тревоги (F=F0=const);
• затем максимизируется вероятность правильного обнаружения
(D → max).

125.

Спектральный анализ: характеристики обнаружителя
• Находится зависимость вероятности ложной тревоги от величины порога:
F = func(Uп) при Us = 0
(как показано на рис. 87);
• По полученной кривой определяется порог Uп0, обеспечивающий допустимое
__значение F = F0 вероятности ложной тревоги.
• Находится зависимость D = func(Us) вероятности правильного обнаружения
__от амплитуды сигнала при F = F0 (Uп = Uп0).
• При заданной требуемой вероятности правильного обнаружения D = D0 (см.
__на рис. 88) определяют необходимое отношение сигнал/шум q = Us0 / ш,
__обеспечивающее заданные параметры F0 и D0. Обычно задается D0 0,9.
Рисунок 87 – Определение порогового
уровня, соответствующего допустимой
вероятности ложной тревоги
Рисунок 88 – Определение уровня
сигнала, обеспечивающего нужную
вероятность его обнаружения

126.

Спектральный анализ: измерение
параметров обнаруженного сигнала
• Измерение амплитуды
Us
и частоты
s
сигнала производится, только если
__на предыдущем этапе была принята гипотеза H1.
• Измеряемый сигнал – случайный процесс, следовательно, определяются не
__сами измеряемые величины, а их оценки Us* и
s* .
• Вся информация, необходимая для проведения измерений, содержится в
__положении
km
на частотной оси и величине X(km ) максимального
__спектрального отсчета в частотном диапазоне
• Оценки частоты s* и амплитуды сигнала
__приведенным формулам:
k1 k2 (см. на рис. 89).
Us*
находятся по ниже
_________ s* = km ,
______Us*=2 X(km ) / N .
Рисунок 89 – Измеряемые параметры сигнала

127.

Спектральный анализ: методические ошибки измерения
Если реальная частота
сигнала
s
не попадает на
дискретные точки k = k
оси частот, возникают
методические ошибки
измерения частоты и
амплитуды, как показано на
рис. 89 для
ш = 0.
Рисунок 89 – Методические ошибки изменения
• Ошибка измерения частоты s
= s – s* – случайная величина, равномерно
_ распределенная в интервале [– /2, /2]. Дисперсия ошибки D( s)= 2/12.
_
• Для уменьшения ошибки необходимо уменьшать основную частоту ДПФ.
__Т.к.
= 2 /Ts,
это достигается удлинением интервала Ts наблюдения сигнала.
• Ошибка измерения амплитуды X = X(j s) – X(j s*) зависит от случайной
_ величины – ошибки измерения частоты, расчет дисперсии ошибки осложнен.
• Ошибки измерения частоты и амплитуды не зависят от мощности шума в канале.
__С ростом амплитуды сигнала суммарная дисперсия ошибки может стремиться
__не к нулю, а к некоторому значению, определяемому методической ошибкой.

128.

Расчет статистических характеристик
обнаружения сигнала и измерения его параметров
Для расчета статистических характеристик обнаружения и измерений можно
использовать метод Монте-Карло следующим образом в контексте данной задачи:
• Проводится многократное формировании реализаций дискретизированного
__случайного входного сигнала x(nT) (M испытаний) c постоянными значениями
__параметров.
• По каждой сформированной реализации принимается решение о наличии или
__отсутствии полезного сигнала. Отношение числа К обнаружений к общему
__числу M испытаний определяет частоту
__значениях параметров.
p* = K/M обнаружений при данных
• Эта частота стремится при бесконечном возрастании М к вероятности p
__обнаружения
(M => p* p).
При наличии шумов величина и положение максимального отсчета ДПФ на
частотной оси являются случайными величинами, и возможно определение
только оценок
Us*
и
s*
амплитуды и частоты. Вследствие этого возникают:
• ошибка измерения амплитуды
• ошибка измерения частоты
– Us = Us* – Us ,
– s = s* – s .

129.

Расчет статистических характеристик
обнаружения сигнала и измерения его параметров
Для каждого i-того испытания, в котором обнаружен сигнала при данном наборе
его параметров, определяются оценки амплитуды Usi* и частоты si*.
Они позволяют вычислить следующие статистические характеристики:
• математические ожидания оценок амплитуды и частоты
и
• дисперсии ошибок
и
• среднеквадратические ошибки
и
• относительные среднеквадратические ошибки
Us = Us / Us
и
s = s / s .
Функциональные зависимости указанных характеристик от параметров сигнала и
шума строятся путем изменения значения одного из параметров и повторения
испытания. Наглядные зависимости получаются при числе испытаний М 1000.

130.

Двумерные унитарные
преобразования

131.

Двумерные унитарные преобразования
Двумерные унитарные преобразования используются для работы с
двумерными массивами данных (будем рассматривать изображения)
и применяются для:
Извлечения полезных признаков анализируемых данных
Сжатия данных
Кодирования данных
Сокращения объема вычислений
…
Унитарные преобразования являются частным случаем линейных
преобразований, когда:
• линейный оператор обратим
• ядро преобразования удовлетворяет условиям ортогональности
Матрица A унитарного преобразования обладает следующими свойствами:
A-1A = E,
где индекс A-1 – матрица, обратная матрице A; E – единичная матрица.

132.

Двумерные унитарные преобразования
В результате прямого унитарного преобразования матрица изображения
F(n1,n2) размерами N1 N2 преобразуется в матрицу F (n1,n2) того же
размера:
где AC (или BC) и AR (или BR) – соответственно одномерные операторы
преобразования столбцов и строк.

133.

Двумерные унитарные преобразования
Результат выполнения оператора разделимого двумерного унитарного
преобразования можно находить в два этапа:
Сначала выполняется одномерное преобразование по всем столбцам матрицы
изображения, и образуется матрица с элементами
Затем выполняется второе унитарное преобразование по всем строкам
полученной матрицы:
Представление двумерной матрицы
пикселов в виде одномерного вектора
путем растрового сканирования
содержимого матрицы
Унитарные преобразования можно записывать с помощью векторных операций.
Если F и f – соответственно матричное и векторное представление массива
пикселов, а
F
и f – матричное и векторное представление результата
преобразования A, тогда двумерное преобразование в векторной форме
запишется так:
f=Af.

134.

Преобразование Фурье изображения
Прямое и обратное
разделимые унитарные
преобразования
двумерных матриц
Заменяем номера {n1, n2}
строк и столбцов матриц на
пространственные координаты
– номера {j, k} строк и
столбцов пикселов.
Заменяем номера {m1, m2}
__на номера частотных
__отсчетов {u, v}
Подставив
соответствующие
комплексные
экспоненты в матрицы
преобразований
получаем прямое и
обратное дискретные
преобразования Фурье
[здесь i = (-1) ].
Ниже мы рассмотрим и другие полезные двумерные унитарные преобразования

135.

Преобразование Фурье изображения
Рисунок – Частный вид ядра
двумерного преобразования Фурье
для пространственной частоты 2 по
одной координате и частоты 3 – по
другой

136.

Преобразование Фурье изображения
Представим по
формулам Эйлера
комплексные
экспоненты в виде
сумм косинусов и
синусов.
Получаем набор гармонических
базисных функций разложения, как
показано на рисунке.
Рисунок – Косинусные и синусные
базисные функции дискретного
преобразования Фурье
последовательности длиной 16 отсчетов
Значение нулевой гармоники –
это N-кратно увеличенная средняя
яркость изображения

137.

Преобразование Фурье изображения
Подставив u=u+mN и v=v+nN, где m и n – постоянные, получим
т.е. вычисленный спектр периодический (см. на рисунке).
Рисунок – Справа –
периодическое исходное
изображение, слева – его
периодический двумерный
спектр, рассчитанный
дискретным
преобразованием Фурье

138.

Преобразование Фурье изображения
Можно показать, что
,
т.е. расчет значительной части спектра избыточен и некоторые части спектра
можно рассчитать по его ранее вычисленным значениям (см на рисунке)
Рисунок – Часть
спектральных отсчетов, для
вычисления которых не
требуется применение
преобразования Фурье

139.

Преобразование Фурье изображения
Рисунок – Спектральная
плоскость: слева –
естественное размещение
начала координат, справа
начало координат
расположено в левом
верхнем углу
спектральной плоскости,
рассчитанной с помощью
ДПФ
Особенности дискретного преобразования Фурье (ДПФ)
Физические спектрометры располагают низкочастотные гармоники в центре, а
___ДПФ располагает их по углам спектральной плоскости (см. на рисунке). Чтобы
___разместить нулевую гармонику в центре «изображения» спектра, можно перед
___вычислением преобразования Фурье каждый пиксел преобразуемого
___изображения умножить на (–1)j+k, где jϵ[0;
N–1], kϵ[0; M–1] – координаты
___пиксела, а N и M – количество пикселов по абсциссе и ординате.
ДПФ вычисляет действительную и мнимую чассти комплексного спектра, что
___увеличивает время вычислений и объем памяти, необходимый для хранения
___их результатов.
ДПФ медленно сходится из=за возникновения скачков яркости на границах
___«периодов» преобразуемых изображений.

140.

Симметричные дискретные косинусные
преобразования (ДКП)
ДПФ создает действительные косинусные базисные спектральные
___компоненты и мнимые синусные компоненты.
Для преобразуемых изображений, симметричных относительно начала
координат в результате ДПФ должны остаться только спектральные компоненты,
соответствующие четным (косинусным) базисным функциям.
Для создания симметричных преобразуемых изображений применяют два
___варианта отражения исходного изображения относительно «начала
___координат» как показано на рисунке.
Для четного
симметричного
дискретного
косинусного
преобразования
F
Для нечетного
симметричного
дискретного
косинусного
преобразования
Рисунок – два варианта построения симметричных изображений:
а – прикладывание друг к другу четырех зеркально отраженных изображений;
б – прикладывание зеркально отраженных изображений с наложением (в обоих
случаях одноименные углы наложенных изображений помечены крестиками)

141.

Симметричное четное ДКП
В соответствии с рисунком пикселы симметричного
Fs(j, k) для симметричного четного
ДКП формируется из исходного изображения F(j, k)
изображение
F
согласно следующим формулам:
,
Рисунок – Формирование
изображения для четного
ДКП
где в F (j, k) номера строк j и столбцов k меняются
в диапазоне [0;
N–1], а в преобразованном
(симметричном) изображении j, k [–N; N–1].
Массив Fs(j, k) симметричен относительно точки j=–1/2, k=–1/2. Поместив в
точку симметрии начало координат, вычислим от него ДПФ:
где пространственные частоты u и v меняются в диапазоне [–N;
N–1].

142.

Симметричное четное ДКП
Массив Fs(j, k) симметричен относительно начала координат и состоит из
действительных чисел, следовательно, разложение комплексной экспоненты
ДПФ по формулам Эйлера будет содержать только косинусные компоненты:
Четное симметричное ДКП вычисляют с дополнительной нормировкой:
где C(0)
= 2-1/2, а C(w) = 1, при w = 1, 2, …, N–1.

143.

Симметричное четное ДКП
Обратное четное симметричное ДКП вычисляют
с теми же значениями C(w):
.
На рисунке слева приведен пример базисных
функций, используемых в четном симметричном
ДКП.
Рисунок – Базисные функции симметричного четного
ДКП для преобразуемой последовательности ,
содержащей
N = 16 отсчетов.

144.

Базисные функции ДПФ и ДКП

145.

Сходимость унитарных преобразований
Рисунок – Дисперсии амплитуд
базисных функций унитарных
преобразований последовательности
длиной 16 отсчетов

146.

Симметричное нечетное ДКП
В соответствии с рисунком пикселы симметричного
Fs(j, k) для симметричного нечетного
ДКП формируется из исходного изображения F(j, k)
изображение
согласно следующим формулам:
Вычисление двумерного ДПФ для такого массива
дает:
Рисунок – Формирование
изображения для
нечетного ДКП
где
u, v = –N+1, …, -1, 0, 1, …, N-1.

147.

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

148.

Симметричное нечетное ДКП
Чтобы базисные функции нечетного симметричного ДКП стали
ортонормированными, вычисление производится по следующим формулам:

149.

Симметричное нечетное ДКП
Обратное преобразование
Базисные функции нечетного ДКП разделимы, поэтому двумерное
преобразование можно выполнить в виде последовательности
одномерных.

150.

Дискретное синусное преобразование
где j=0, …, N–1 – номера строк пикселов, а k=0, …, N–1 – номера
столбцов пикселов преобразуемого изображения F(j, k); u=0, …, N–1
– номера частотных отсчетов вдоль столбцов пикселов, а v=0, …, N–1
– номера частотных отсчетов вдоль строк пикселов преобразуемого
изображения.
Обратное преобразование вычисляется по такой же формуле, только
F(j, k) и (u, v) поменяются местами.

151.

Дискретное синусное преобразование
Рисунок – Базисные функции дискретного
синусного преобразования для
последовательности длиной 16 отсчетов

152.

Преобразование Карунена-Лоэва
Ковариационная матрица множества векторов
x m x
Cij E xi mi x j m j
mk E xk
i
i
j
m j p xi , x j dxi dx j ;
x p x dx .
k
k
k
C – ковариационная матрица
E – математическое ожидание
xk – k-тый компонент вектора
mk – математическое ожидание k-того
компонента вектора
p – функция плотности распределения
вероятности
Собственный вектор матрицы
Собственным вектором невырожденной матрицы A размером N N является
такой вектор x, для которого выполняется следующее соотношение:
Ax = lx,
где l – собственное число, соответствующее этому вектору. Невырожденная
матрица A размером N N имеет N линейно-независимых собственных векторов.

153.

Преобразование Карунена-Лоэва
Пусть имеется множество векторов x, заданных в N-мерном пространстве
признаков. Рассчитаем для них ковариационную матрицу C и вычислим
собственных векторов yi и собственных чисел li, i=1…N.
N ее
Упорядочим собственные векторы xi в порядке убывания величины
соответствующих им собственных чисел li . Выберем M собственных векторов,
соответствующих
M
наибольшим собственным числам. Транспонируем
выбранные собственные векторы и составим из них матрицу Y размером M N:
y1
y 2
Y ,
...
y
M
y`i = (yi1, yi2, …, yiN) – транспонированный i-тый собственный вектор.
Рассчитаем преобразованные векторы zi :
zi=Yxi,
это представление векторов xi в новом ортогональном базисе выбранных
собственных векторов y`i, поскольку скалярное умножение вектора строки y`i
на вектор столбец xi - это проекция вектора xi, на базисный вектор y`i .
где

154.

Дискретное синусное преобразование
Преобразование Карунена-Лоэва «поворачивает» исходный базис {x1,x2,…, xN}
представления векторов так, чтобы оси эллипсоида рассеяния векторов в
исходном пространстве признаков совпали с направлением ортов {y1,y2, …, yM}
y2
в новом базисе.
х2
y1
х1
Если разброс значений в направлении y2 пренебрежимо мал, можно сократить
размерность пространства, оставив только орт y1, так можно сжимать данные.

155.

Преобразование Карунена-Лоэва
Рисунок – Базисные функции
преобразования Карунена-Лоэва для
последовательности длиной 16 отсчетов

156.

Разложение по
негармоническим функциям

157.

Импульсы блока
Импульсы блока
• просты в цифровой реализации
• ортогональны
• но не образуют полную систему
Рисунок – Последовательность из 8
импульсов блока

158.

Функции Уолша
Функции Уолша
• ортогональны
• образуют полную систему
Рисунок – Функции Уолша для последовательности
длиной 16 отсчетов

159.

Преобразование Адамара
Преобразование Адамара (Hadamard) выполняется умножением вектора f
отсчетов сигнала на матрицу Адамара H, строки которой являются функциями
Уолша (см. на рисунке):
F=Hf.
Рисунок – Матрица Адамара: а – представление маатрицы в виде
изображения; b – графики функций Уолша, соответствующих строкам
матрицы; Двоичное представление матрицы Адамара
Матрицы Адамара генерируются следующим образом:
,
,
HN-1=HN.

160.

Двумерное преобразование Адамара
Для расчета двумерного преобразования Адамара можно сначала выполнить
одномерное преобразование Адамара DWT по всем столбцам матрицы
изображения B. Затем выполняется второе одномерное преобразование
Адамара по всем строкам полученной матрицы:
F=DWT B DWT.
Аналогично выполняется обратное двумерное преобразование:
B=DWT F DWT.
Рисунок – Двумерное преобразование Адамара выполняет
разложение изображения по таким двумерным функциям
Рисунок – Одна
из аналогичных
базисных
функций
преобразования
Фурье

161.

Двумерное преобразование Адамара
Для расчета двумерного преобразования Адамара можно сначала выполнить
одномерное преобразование Адамара DWT по всем столбцам матрицы
изображения B. Затем выполняется второе одномерное преобразование
Адамара по всем строкам полученной матрицы:
F=DWT B DWT.
Эти сложные многомерные операции можно описать следующими формулами:
1
F u, v
N
N 1 N 1
B j, k 1
p j , k ,u , v
,
j 0 k 0
j, k – соответственно номера строк и столбцов элементов двумерного
преобразуемого массива данных (например, пикселов); u, v – соответственно
где
номера базисных функций Адамара по строкам и столбцам преобразованного
массива; p(j,
k, u, v) вычисляется по следующему правилу:
N 1
p( j, k , u, v) ui ji vi ki ,
i 0
где переменные ui, vi, ji и ki равны цифрам в двоичном представлении чисел
v, j и k соответственно. Напимер, если u=13, то u3=1, u2=1, u1=0 и u0=1.
Для сравнения. Для
преобразования Фурье:
u,

162.

Преобразование Хаара
Вычисление одномерного преобразования Хаара F
выполняется умножением преобразуемого вектора b
на матрицу преобразования H:
F = Hb; b=H-1F=HTF.
Рекурсивное правило генерации матриц Хаара:
генерация начинается с матриц H2 второго порядка.
Матрицы последующих порядков вычисляются по
матрицам предыдущих порядков на основе
произведения Кронекера:
,
где E2k – единичная матрица размерами 2k 2k,
Рисунок – Базисные функции преобразования
Хаара для последовательности длиной 16 отсчетов
N=2k+1.

163.

Двумерное преобразование Хаара
Для расчета двумерного
преобразования Хаара F можно
сначала выполнить одномерное
преобразование Хаара DHT по
всем столбцам матрицы
изображения B. Затем
выполняется второе одномерное
преобразование Хаара по всем
строкам полученной матрицы:
F=DHT B DHT.
Рисунок – Двумерное преобразование
Хаара выполняет разложение изображения
по таким двумерным базисным функциям
Вычисление двумерного
преобразования Хаара
двумерного массива можно
представить как его разложение
по двумерным базисным
функциям, представленным на
рисунке.

164.

Наклонное преобразование (slant transform)
Вычисление одномерного наклонного преобразования
F выполняется умножением преобразуемого вектора
b на матрицу преобразования S:
F = Sb.
Рекурсивное правило генерации матриц
преобразования: генерация начинается с матриц S2
второго порядка.
Матрицы последующих порядков вычисляются по
матрицам предыдущих порядков согласно формуле:
где Ik – единичная матрица k-того порядка,
Рисунок – Базисные функции
наклонного преобразования для
последовательности из 16 отсчетов

165.

Сходимость унитарных преобразований
Рассмотренные унитарные
преобразования «концентрируют
энергию» в начальных компонентах
«спектра», что позволяет
отбрасывать часть высокочастотных
компонент. Осуществляя таким
образом сжатие данных.
Рисунок – Дисперсии амплитуд
базисных функций унитарных
преобразований последовательности
длиной 16 отсчетов

166.

Сингулярное преобразование

167.

Симметричное нечетное ДКП

168.

Симметричное нечетное ДКП

169.

Симметричное нечетное ДКП

170.

Симметричное нечетное ДКП

171.

Симметричное нечетное ДКП

172.

Симметричное нечетное ДКП