По дисциплине Системы цифровой обработки информации

Министерство образования и науки Украины

Севастопольский национальный технический университет

 

 

КУРС ЛЕКЦИЙ

по дисциплине «Системы цифровой обработки информации»

Для студентов очной и заочной форм обучения

специальности «Компьютерные системы и сети»

Севастополь

СОДЕРЖАНИЕ

Лекция 1.Цифровая обработка сигналов. Основные понятия.........1

Лекция 2. Преобразование Фурье и обобщенные функции............4

Лекция 3 Восстановление дискретного сигнала....................7

Лекция 4. Дискретное преобразование Фурье (ДПФ)...............10

Лекция 5. Цифровые фильтры. Основные понятия..................13

Лекция 6. Z-преобразование. Фильтры первого порядка...........16

Лекция 7. Фильтры второго и высших порядков..................18

Лекция 8. Фильтры Баттеруорта.................................20

Лекция 9. Осциллятор. FIR фильтры.............................22

Лекция 10. Квадратурный зеркальный фильтр.....................25

Лекция 11. Wavelet- преобразования............................27

Лекция 12 Wavelet фильтрация..................................29

Лекция 13. Шум от квантования сигнала.........................31

Лекция 14. Быстрые схемы дискретного преобразования Фурье.....34

Лекция 15.Свертка последовательностей и ее вычисление.........36

Лекция 16. Автокорреляция и ее вычисление.....................38

Лекция 17. Применения автокорреляционной функции..............40

Лекция 18. Эффект Доплера и смежные вопросы...................42

Лекция 19. Преобразование Хартли..............................43

Лекция 20. Строение матрицы Адамара...........................45

Лекция 21. Преобразования Адамара и Хаара.....................47

Лекция 22. Фильтрация и преобразование Адамара................49

Лекция 23. Метод главных компонентов в задаче сжатия..........51

Лекция 24. Линейное предсказание..............................53

 

Лекция 1.Цифровая обработка сигналов. Основные понятия

Введение

В настоящее время методы цифровой обработки сигналов, digital signal processing (DSP) находят все более широкое применение, вытесняя постепенно методы, основанные на аналоговой обработке. В данном курсе рассматриваются основы теории, и наиболее употребляемые алгоритмы обработки.

При работе над данным конспектом автор пользовался следующими источниками

1. Р.Отнес, Л.Энокон. Прикладной анализ временных рядов. М.:Мир, 1982.

2. A.Oppenheim, R.Schafer. Discrete-time signal processing. Prentice-Hall, 1989.

Кроме того, при изложении вопросов, связанных с Wavelet теорией использованы статьи, о которых будет сказано в соответствующем месте.

Постановка задачи.

Пусть имеется непрерывный сигнал x(t), заданный на интервале . При переходе к оцифровке происходит следующая операция. Выбирается шаг дискретизации , и вместо исходного сигнала получается последовательность . Далее, выбирается формат оцифровки r. Обычно он бывает кратным 8, хотя это не обязательно. Предположим, что существует такое число М, что выполнены неравенства: для всех n. Интервал [-M,M] разбивается на частей. После этого каждое значение заменяется номером интервала, в который попало соответствующее значение. В результате последовательность заменяется новой последовательностью , но теперь каждый член новой последовательности принимает значения из интервала . При желании вместо указанного представления можно перейти к представлению сигнала целыми числами со знаком.

На каждом из упомянутых шагов происходит огрубление сигнала. Первая задача цифровой обработки заключается в оценке искажения исходного сигнала. Дальнейшая обработка состоит в извлечении из полученного сигнала нужной информации и подавлении шумов. Это осуществляется с помощью цифровой фильтрации. Даже оцифрованный сигнал занимает много места, и следующий шаг обработки заключается в сжатии сигнала. Обычно имеется в виду сжатие с потерей информации. Здесь важно установить критерии допустимой потери информации. В зависимости от выбранного критерия выбирается способ сжатия. Хотя последовательность бесконечна, в реальных условиях мы имеем дело лишь с конечными последовательностями. В этой связи нужна оценка потерь, связанных с усечением последовательностей.

 

Преобразование Фурье

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

(1)

Функция или ее модуль трактуется как интенсивность исходного сигнала на частоте . Обратное преобразование задается аналогичной формулой:

(2)

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

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

Если то

Сверткой двух функций называется функция , заданная формулой: . Имеет место соотношение

Двойственное соотношение имеет вид .

Вообще говоря, не предполагается, что функция - вещественная. Если же это так, то

. Эта формула получается формальным дифференцированием под знаком интеграла в (2).

Обобщенные функции

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

Обозначим через множество бесконечно дифференцируемых функций с компактным носителем. По определению, последовательность , если все эти функции имеют общий компактный носитель, принадлежат и в каждой точке имеет место обычная сходимость. Функционал это отображение , причем . Если - интегрируемая функция, то ей соответствует функционал . Однако существуют функционалы, не представимые в указанной форме. Например, . Этот функционал записывают в форме . Наряду с указанным функционалом определяют функционалы , исходя из формального правила замены переменных в интеграле. Хотя этот функционал нельзя представить с помощью обычной функции, можно ввести -образную последовательность. Положим при и 0 в остальных точках. Интеграл от нее равен 1. При больших функция представима в виде при , поэтому (второе слагаемое исчезает в силу симметричности).

Лемма. Пусть имеет интегрируемую производную. Тогда

Доказательство проводится интегрированием по частям. Аналогичное утверждение справедливо и для .

Задача 1. Доказать, что

 

Лекция 2. Преобразование Фурье и обобщенные функции

Вспомогательные утверждения

Лемма. Справедлива формула

(1)

Доказательство. Хотя формула (1) хорошо известна, мы приведем ее доказательство, поскольку она является основой многих дальнейших выкладок. Рассмотрим контур, изображенный на рис.1

Рис. 1. Контур интегрирования

и интеграл по контуру в указанном направлении от аналитической функции . Имеем , поскольку у функции нет особенностей внутри области интегрирования. Здесь контур - дуга окружности радиуса , а контур - дуга окружности радиуса . Обе дуги имеют центр в начале координат. За исключением крайних точек, на контуре выполнено неравенство , поэтому с ростом интеграл по этому контуру стремится к 0. Интегралы по контурам в сумме дают . Найдем теперь интеграл по контуру . Сделаем замену . В результате интеграл по этому контуру примет вид . Последняя оценка получена в результате разложения подынтегральной функции в ряд. Устремляя к 0, завершаем доказательство.

Следствие 1.

при любом .

Доказательство проводится путем замены переменной

Следствие 2

.

Для любого

Доказательство. . Второе слагаемое стремится к 0 когда .

Из соображений симметрии вытекает формула

(2)

Пример отыскания обобщенных функций

Под обобщенной функцией понимается непрерывный функционал. Примером такой функции является -функция.

Предложение 1. .

Доказательство. Очевидно, что обычное преобразование Фурье от 1 не существует. Положим . Не существует обычного предела у этой функции при . Найдем функционал . Если 0 не попадает в интервал интегрирования, подынтегральная функция не имеет особенностей, и весь интеграл стремится к 0. В противном случае, интеграл стремится к , где произвольное малое положительное число. Второе слагаемое исчезает в силу симметричности, и при получаем, используя (2), конечный результат.

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

Производные от обобщенных функций

Производная определяется путем формального применения интегрирования по частям с учетом компактности носителя функций из : . В качестве примера рассмотрим обобщенную функцию , заданную равенством: и найдем производную от нее. Имеем . Это означает, что .

Замечание.Следует быть очень осторожным применяя к обобщенным функциям формулы, связывающие производную от функции и ее преобразование Фурье. В качестве примера рассмотрим отыскание преобразование Фурье от . Действуя формально, можем получить: , откуда . Теперь, исходя из определения, найдем правильный ответ. Положим и подсчитаем . Если точка 0 не входит в интервал интегрирования, то интеграл стремится к , то есть ожидаемый результат. Если же точка 0 принадлежит интервалу интегрирования, то наряду с указанным слагаемым появится еще одно.

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

Замечание. Интеграл существует в смысле главного значения для функции из . Это означает существование соответствующего функционала.

Задача 2. Дать строгое доказательство утверждения

 

Лекция 3 Восстановление дискретного сигнала

Наша цель - найти необходимые условия, при которых сигнал может быть восстановлен по дискретной выборке

Прежде всего, отметим часто часто используемый факт:

Преобразование Фурье от последовательности

Определение.Преобразованием Фурье от последовательности называется функция (1) Отметим, что функция является периодической. Часто ради простоты обозначений полагают , и в этом случае период функции…

Связь между непрерывным и дискретным преобразованиями Фурье. Частота Найквиста.

, где , откуда вытекает (4) Эта формула устанавливает связь между непрерывным и дискретным преобразованиями Фурье. Как и следовало ожидать, имеет…

Теорема Котельникова-Шеннона

Если исходный сигнал имеет ограниченный спектр и выполнено условие (5), то непрерывный сигнал можно восстановить по дискретному. Доказательство. Пусть спектр сигнала находится в интервале . Выберем… . (6)

Формула обращения

Свертка

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

Пример вычисления ДПФ

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

Предложение.

Доказательство. Положим =. Теперь

Задача 3. Доказать, что

Линейные инвариантные системы.

Рассматриваются последовательности . Очевидным образом определяются сумма последовательностей и произведение на число. В результате сдвига получается новая последовательность . Дальнейшее работа с последовательностью, полученной в результате дискретизации, заключается в преобразовании с помощью различных устройств.

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

Определение. Система называется инвариантной, если для любого .

Примеры.

1.Точечные системы: , где произвольная функция ,- инвариантная система..

2.для произвольного фиксированного - инвариантная система

3.не будет инвариантной. Действительно, пусть . Согласно определению

Определение. Система называется линейной инвариантной (ЛИС), если она линейна и инвариантна.

Преобразование в примере 2 осуществляется ЛИС.

Лекция 5. Цифровые фильтры. Основные понятия

Цифровые фильтры являются частным случаем линейных инвариантных систем. Существенное ограничение связано с физической реализуемостью системы.

Определение. Система называется физически реализуемой, если сигнал на выходе в момент времени t зависит от входных сигналов в моменты времени .

Пусть имеется ЛИС . Рассмотрим сосредоточенную в одной точке последовательность . Пусть , а по определению . Для произвольной последовательности справедливо разложение . В силу линейности а в силу инвариантности . Окончательно, если , то

(1)

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

 

Если имеются две последовательно соединенных ЛИС, то в силу ассоциативности операции свертки, результирующая функция отклика получается как свертка функций отклика отдельных систем. Отсюда следует неожиданный вывод о коммутативности последовательного соединения. При параллельном соединении в качестве функции отклика получаем сумму функций, отвечающих отдельным слагаемым.

Вообще говоря, сумма в (1) бесконечная. Чтобы она имела смысл, надо ввести дополнительные ограничения.

Определение.Система (1) называется устойчивой, если она переводит любую ограниченную последовательность в ограниченную.

Предложение. Система устойчива тогда и т.т., когда

.

Доказательство. Достаточность условия очевидна. Для доказательства необходимости заметим, что функция отклика ограничена, поскольку это реакция на ограниченную последовательность. Возьмем в качестве входной последовательности , если . Реакция в нуле на эту последовательность имеет вид .

Рекуррентные системы

, , (2) где - натуральное, а - любые целые числа.. Эта система будет инвариантна, если соблюдены описанные выше ограничения.…

Фильтры

(3). Уравнение (3) является основным в теории фильтрации. Функция называется…

Фильтры с конечным временем отклика.

  . Переходя к преобразованиям Фурье и учитывая, что , получим, что . Другими… (4)

Фильтры с бесконечным временем отклика

IIR фильтр является линейной инвариантной системой, а его функцию отклика…

Лекция 6. Z-преобразование. Фильтры первого порядка

Z-преобразование

(1) В формуле (1) ряд является формальным, если же он сходится, то определяет… (2)

Идеальный фильтр

Фильтр первого порядка

Это общий вид фильтра первого порядка. Его передаточная функция имеет вид (3)

Лекция 7. Фильтры второго и высших порядков

Определение фильтра второго порядка

. Это означает, что фильтр есть последовательное соединение двух фильтров первого порядка. Для устойчивости достаточно потребовать, чтобы все корни… Другими словами, если точка с координатами попадает внутрь треугольника,…  

Фильтры высших порядков

, где в числителе и знаменателе стоят вещественные многочлены, причем имеет степень выше двух. В этом случае имеет место разложение на неприводимые… Фильтр Баттеруорта (Butterworth) Это один из базисных фильтров. Фильтр низких частот имеет передаточную функцию

Лекция 8. Фильтры Баттеруорта

Отыскание параметров фильтра

, откуда , где - корень степени из -1. Каждое из этих уравнений сводится к квадратному уравнению. Найдем корни этих уравнений и выберем те из них,…

Упражнение

Рассмотреть пример для . Для отыскания коэффициента достаточно положить . Тогда .

Какие изменения произойдут в случае ?

Фильтр высоких частот

Полосовой фильтр

Полосовой фильтра как последовательное соединение фильтров высоких и низких частот

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

Задача. Написать фильтр 4-ого порядка, полученного указанным способом из двух фильтров 2-ого порядка.

Тангенциальный фильтр

. Теперь получается передаточная функция с нулем при . Если , то . Используя тот же прием, получим, что . Для отскания коэффициентов многочленов в…

Лекция 9. Осциллятор. FIR фильтры

Полосовой фильтр на основе фильтра низких частот

Пусть имеется сигнал с преобразованием Фурье . Рассмотрим новую последовательность . По определению . Если нам нужен полосовой фильтр, можем… Непосредственное применение указанного способа не удобно, поскольку приходится…

Фильтр как осциллятор

Для устойчивости фильтра достаточно, чтобы все корни находились внутри единичной окружности. Если корни лежат на окружности, фильтр можно… (1) Уравнение имеет два корня , поэтому (1) можно записать в виде . Из полученного равенства следуют два рекуррентных…

Фазовый сдвиг сигнала в результате фильтрации

, где -любое число,. Это устойчивый фильтр, а его передаточная фукнция имеет вид . Модуль этой передаточной функции равен 1, а аргумент меняется…

Фильтры с конечным временем отклика

(2) Это фильтр с конечным временем отклика (FIR). После преобразования Фурье…

Проектирование FIR фильтров. Сглаживающие окна

  Она напоминает функцию, но содержит и боковые лепестки. В результате свертки с… Чтобы снизит указанный эффект вместо прямоугольных окон используются другие окна: треугольные окна, окно Хэмминга ,…

Лекция 10. Квадратурный зеркальный фильтр

Проектирование FIR фильтра на основе аппроксимации

. (1) Пусть задана вещественная передаточная функция . Положим . В результате замены… Аппроксимацию указанного вида используют в случае, когда критерием является не средне квадратическое отклонение, а…

Квадратурный зеркальный фильтр

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

Лекция 11. WaveLet- преобразования

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

Непрерывное преобразование.

(1) Если , то в результате получаем обычное преобразование Фурье ( параметр не…  

Шкалирование

(2) Такую функцию назовем шкалирующей. Например, любая функция, имеющая носитель… Предложение. Имеет место формула

Лекция 12 Wavelet фильтрация

Детализация сигнала

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

Wavelet фильтрация

= . Коэффициенты в (1) можно найти следующим образом. Положим . Тогда =(2) Формула (2) представляет собой свертку последовательностей. Она позволяет найти коэффициенты разложение для меньших…

Лекция 13. Шум от квантования сигнала.

Multiresolution - переменная разрешающая способность

Дискретный сигнал

Начиная с этого момента дальнейшее изложение ориентируется на компьютерную обработку сигнала. Основное отличие состоит в отсутствии понятия непрерывности, на котором базировался предыдущий материал.

Шум от дискретизации

Дискретное преобразование Фурье

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

Связь ряда Фурье и дискретного преобразования Фурье

. Выберем и найдем дискретное преобразование, используя значения функции в точках . Легко видеть, что равно если и 0 в противном случае. Отсюда…

Преобразование вещественных последовательностей.

В этой связи рассматривают только коэффициенты (целая часть ). В качестве примера рассмотрим . У нее два обычных коэффициента: . Учитывая эффект подмены, получим, что дискретные…

Лекция 14. Быстрые схемы дискретного преобразования Фурье.

Случай Любое число в интервале однозначно представляется двоичным вектором длины .… . В дальнейшем, что упростить изложение, введем обозначение , откуда . Имеем

Случай с взаимно простыми сомножителями

(1) При этом можно считать выполненными неравенства .(2)

Лекция 15.Свертка последовательностей и ее вычисление

Сдвиг последовательности

(1)

Циклическая свертка

(2) Операция свертки является коммутативной, и кроме того, последовательность,… (3)

Использование окон

Кратковременное преобразование Фурье

Лекция 16. Автокорреляция и ее вычисление

(1)

Случай конечной последовательности

(2) Если для заданного существует схема БПФ, то выгоднее для отыскания значений… В случае конечных последовательностей мы имеем дело с циклической сверткой. Для того, чтобы избавиться от эффекта…

Практическое оценивание частот

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

Лекция 17. Применения автокорреляционной функции

Частота основного тона

Амплитудное ограничение. Выбирается порог, и исходный сигнал заменяется последовательностью нулей и единиц: в точках, где сигнал превышает порог,… Пересечение с нулем. Рассмотрим график функции . Значение можно оценить по…

Поиск сигнала с помощью кросс корреляционной функции

Процессор малой мощности

Предположим, что процессор быстро производит лишь операции сложения и вычитания с целыми числами. Для подсчета произведения используется следующий прием. Имеем . В памяти хранятся значения квадратов возможных значений, а деление на 4 в двоичном коде сводится к логическому сдвигу на две позиции.

Использование БПФ

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

Лекция 18. Эффект Доплера и смежные вопросы

. (1) Здесь , - расстояние до объекта, а - скорость распространения волны. Если же… (2)

Лекция 19. Преобразование Хартли

Связь с преобразованием Фурье

Из определения вытекает формула, позволяющая найти преобразование Фурье, если известно преобразование Хартли.

Обратно

Дискретное преобразование Хартли

Преобразование Хартли используется для вычисления спектра, который аналогичен спектру Фурье. Недостаток заключается в отсутствии простой зависимости…

Преобразование Адамара.

Лекция 20. Строение матрицы Адамара

Предложение. Элемент матрицы . Доказательство. Для утверждение очевидно. Рассмотрим , где каждый блок есть… Данное предложение позволяет при работе с матрицами высокого порядка генерировать элементы матрицы, а не хранить их в…

Код Грея.

Обратим внимание на два обстоятельства. Таблица обладает симметрией, которую можно описать следующим образом. Таблица для состоит из двух… Предложение. В коде Грея коды соседних чисел различаются лишь в одном… Доказательство. Рассмотрим двоичные представления двух соседних чисел: и . . Число , где серия из единиц может быть и…

Лекция 21. Преобразования Адамара и Хаара

Подсчет числа перемен знаков в матрице Адамара

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

Быстрое преобразование Адамара.

Преобразование Хаара.

Здесь 1 и -1 обозначают строки длины . Очевидна ортогональность строк этой матрицы. Множитель вводят для того, чтобы выровнять длину строк.…

Сжатие сигнала с помощью ортогонального преобразования.

Лекция 22. Фильтрация и преобразование Адамара

Аналог фильтра с конечным временем отклика для преобразования Адамара.

Пусть исходный сигнал задан в точках. Можем считать, что он задан функцией на строках . Функция раскладывается по характерам группы: . В силу… Другими словами, числа (1)

Проектирование фильтра.

Разложить вектор по строкам Упорядочить коэффициенты разложения в порядке не возрастания модуля Выбрать первые коэффициентов из списка и соответствующие номера строк.

Реализация фильтра.

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

Лекция 23. Метод главных компонентов в задаче сжатия

Предложение 1. Пусть имеется вещественная симметрическая матрица и натуральное , меньше чем размер матрицы. Среди матриц вида , где - ортогональная… Доказательство. Очевидно, что максимум достигается на некоторой матрице .…

Постановка задачи

  (1) Его содержательный смысл - сумма квадратов отклонений от проекций на плоскость, порожденную векторами минимальна.…

Лекция 24. Линейное предсказание

(1) Положим . Заметим, что . В этих обозначениях равенства (1) принимают вид…

Алгоритм Durbin'а

, (2) Представим вектор . Теперь =. Имеем . Применяя (2), получим . По определению… (3)