eng
Содержание
Список сокращений и обозначений 9
Глава 1. Элементы функционального анализа и спектрального
представления функций 11
1.1.
Линейные нормированные пространства 11
1.2.
Пространства со скалярным произведением 18
1.3.
Примеры ортогональных систем в пространстве L2 26
1.4.
Тригонометрические ряды Фурье. Явление Гиббса 32
1.5.
Интеграл Фурье 37
1.6.
Принцип неопределенности время-частотного
представления сигналов 43
1.7.
Обобщенное преобразование Фурье 49
1.8.
Энергетический спектр. Спектр мощности 53
Глава 2. Дискретизация и квантование сигналов.
Дискретные ортогональные преобразования 58
2.1.
Преобразование непрерывных сигналов в дискретные 58
2.2.
Дискретизация по критерию наибольшего отклонения 60
2.3.
Частотный критерий выбора шага дискретизации 61
2.4.
Спектр дискретного сигнала 66
2.5.
Дискретизация узкополосных сигналов 70
2.6.
Дискретное преобразование Фурье (ДПФ) 77
2.7.
Быстрое преобразование Фурье (БПФ).
Алгоритм БПФ с прореживанием по времени 85
2.8.
Алгоритм БПФ с прореживанием по частоте 98
2.9.
Дискретное преобразование Уолша 103
2.10.
Дискретное преобразование Хаара 109
2.11.
Некоторые применения дискретных ортогональных
преобразований 113
2.12.
Квантование дискретных сигналов 116
Глава 3. Описание и анализ линейных дискретных систем (ЛДС) 126
3.1.
Нормирование временной и частотной осей 126
3.2.
Z-преобразование 127
3.3.
Линейные дискретные фильтры (ЛДФ) 132
3.4.
Соединения и структурные схемы фильтров 137
3.5.
Устойчивость ЛДФ 145
3.6.
Частотная характеристика ЛДФ 147
3.7.
Минимально-фазовые системы. Фазовые звенья 155
3.8.
Нахождение отклика фильтра с использованием БПФ 161
3.9.
Многоскоростная обработка сигналов 164
3.10.
Изменение частоты дискретизации сигналов при помощи
полифазных фильтров 170
3.11.
Эффекты квантования в цифровых системах 177
3.12.
Согласованный дискретный фильтр 187
3.13.
Линейная дискретная система как генератор случайных
сигналов. Полюсная модель сигналов 194
3.14.
Фильтр Калмана 199
Глава 4. Введение в методы синтеза цифровых фильтров 206
4.1.
Этапы разработки цифровых фильтров 206
4.2.
КИХ-фильтры с линейной фазой.
Синтез КИХ-фильтров методом частотной выборки 212
4.3.
Оконный метод синтеза КИХ-фильтров 221
4.4.
Синтез оптимальных КИХ-фильтров 232
4.5.
Специальные КИХ-фильтры: преобразователь Гильберта
и цифровой дифференциатор 241
4.6.
Основные характеристики аналоговых линейных систем
и их связь с характеристиками ЛДС 250
4.7.
Синтез БИХ-фильтров по аналоговым прототипам 256
4.8.
Синтез БИХ-фильтров методом инвариантности
импульсной характеристики 268
4.9.
Синтез БИХ-фильтров методом билинейного
Z-преобразования 273
4.10.
Выбор структуры для реализации фильтра 280
4.11.
Адаптивная фильтрация. Фильтр Винера 286
Глава 5. Основы прикладной теории информации 299
5.1.
Мера количества информации для дискретного источника
сообщений без памяти 299
5.2.
Основные теоремы о кодировании источника без памяти 305
5.3.
Эффективное кодирование дискретного источника без
памяти по методам Шэннона — Фано и Хаффмана 315
5.4.
Кодирование длин серий 321
5.5.
Арифметическое кодирование 324
5.6.
Условная энтропия 333
5.7.
Кодирование дискретного источника с памятью 337
5.8.
Статистическое моделирование источника 344
5.9.
Непрерывный источник сообщений.
Дифференциальная энтропия 345
5.10.
Передача дискретного сообщения по каналу с помехами 349
5.11.
Словарные методы кодирования 356
Глава 6. Применение дискретных ортогональных преобразований
для компрессии и спектрального анализа сигналов 363
6.1.
Корреляция как мера статистической зависимости
данных. Преобразование Карунена — Лоэва 363
6.2.
Эффективность использования дискретных
ортогональных преобразований для кодирования
коррелированных данных 369
6.3.
ДПФ в вещественной форме. Дискретное преобразование
Хартли 376
6.4.
Дискретное косинусное преобразование (ДКП) 378
6.5.
Компрессия изображений на основе двумерного ДКП 386
6.6.
Дискретное псевдокосинусное преобразование 392
6.7.
Оптимизация алгоритмов сжатия данных с потерями 401
6.8.
Аппроксимационный подход к выбору преобразований
для кодирования дискретных сигналов. Частотная трактовка 408
6.9.
Время-частотный анализ. Оконное преобразование Фурье 412
6.10.
Использование ДПФ для спектрального анализа 419
Глава 7. Вейвлет-преобразования и их приложения
для обработки дискретных сигналов 429
7.1.
Кратно-масштабный анализ (КМА) 429
7.2.
Проектирование функций на подпространства КМА 435
7.3.
Вычисление дискретных вейвлет-преобразований (ДВП) 441
7.4.
Квадратурно-зеркальные фильтры (КЗФ) 445
7.5.
Свойства КЗФ 451
7.6.
Построение масштабирующих функций и вейвлетов
по масштабирующим уравнениям 458
7.7.
Вейвлеты Добеши 462
7.8.
Биортогональные вейвлет-преобразования 468
7.9.
Применение дискретных вейвлет-преобразований для
сжатия сигналов 472
7.10.
Подавление шумов фильтрацией в базисе дискретных
вейвлет-преобразований 476
7.11.
Двумерные дискретные вейвлет-преобразования 479
7.12.
Метод сжатия цифровых изображений JPEG 2000 487
7.13.
Вейвлет-пакеты 494
7.14.
Вычисление ДВП по схеме лифтинга 506
Заключение 524
Литература 525
Предисловие
В последние два десятилетия методы цифровой обработки сигна-
лов (ЦОС) в радиотехнике, электронике, системах связи, контроля
и управления стали преобладающими, активно вытесняя методы
аналоговой обработки. Этому способствовала стремительно уве-
личивавшаяся производительность вычислительной техники,
которая уже проникла практически во все области человеческой
деятельности. Сегодня, например, говоря о записи или обработке
аудио- и видеоинформации, мы не уточняем, что речь идет о циф-
ровых форматах, подразумевая это само собой разумеющимся.
Важность изучения методов ЦОС трудно переоценить: вопросы,
связанные с цифровой обработкой и представлением сигналов,
давно перестали быть узкоспециальными. Основы знаний в дан-
ной области требуются большинству инженеров, а для специали-
стов в области электроники, радиотехники и телекоммуникаций,
информатики и вычислительной техники необходимо более глубо-
кое понимание основных методов ЦОС и математической теории,
лежащей в их основе. Предлагаемое вниманию читателя учебное
пособие посвящено изучению данных вопросов.
Изначально ЦОС развивалась как ветвь, растущая из теории об-
работки аналоговых сигналов, и рассматривалась как раздел элек-
троники и радиотехники. Однако внедрение в системы обработки
сигналов цифровых программируемых процессоров и контролле-
ров, расширение спектра и увеличение сложности алгоритмов ЦОС,
реализация которых стала возможна в том числе в реальном мас-
штабе времени, превратили ЦОС в политехническую дисциплину.
Сегодня для математиков-программистов, специалистов в области
информатики и вычислительной техники эта область знаний пред-
ставляет собой постоянно расширяющееся поле для приложения
усилий. Данную тенденцию необходимо учитывать при подготовке
инженерных кадров. В предлагаемом вниманию читателя учебном
пособии рассматриваются основы теории ЦОС, изложение которой
по формату и содержанию ориентировано в первую очередь именно
на студентов, обучающихся по инженерным направлениям «При-
кладная математика» и «Информатика и вычислительная техника»
(бакалавриат и магистратура). Однако при написании пособия ав-
тор старался опираться лишь на курс высшей математики, общий
для всех инженерных направлений подготовки, поэтому оно может
быть рекомендовано также для студентов, обучающихся по профи-
лям подготовки в области радиотехники, связи и телекоммуника-
ций.
Первая глава носит вводный характер и содержит изложение тех
основных положений функционального анализа и теории преобра-
зования Фурье, которые потребуются далее в последующих главах.
Помимо этого, в первой главе вводятся популярные в ЦОС функ-
циональные системы Уолша и Хаара.
Вторая глава посвящена вопросам дискретизации непрерыв-
ных сигналов и преобразований, прежде всего преобразования
Фурье. Значительное внимание уделено частотным аспектам дис-
кретизации (как широкополосных, так и узкополосных сигналов)
и построению быстрых алгоритмов вычислений дискретных пре-
образований Фурье, Уолша, Хаара. Кроме того, рассматривается
скалярное и векторное квантование сигналов.
В третьей главе вводятся основные понятия теории линейных
дискретных систем (фильтров). Основное внимание уделено ана-
лизу систем. Рассматриваются вопросы передискретизации сигна-
лов и влияния эффектов квантования в цифровых системах. Также
изу чаются некоторые вопросы согласованной фильтрации и ска-
лярных фильтров Калмана.
В четвертой главе изложены основные классические методы
синтеза КИХ- и БИХ-фильтров по заданной частотной характе-
ристике. Завершает главу рассмотрение основ теории адаптивных
фильтров.
Пятая глава представляет собой введение в теорию информа-
ции, а также содержит описание ряда используемых на практике
методов эффективного статистического (энтропийного) кодирова-
ния.
Первые пять глав включают в себя рассмотрение общих тео-
ретических вопросов ЦОС. В сокращенном варианте этот мате-
риал может быть использован для базовой подготовки бакалавров
по различным инженерным направлениям обучения. В полном
объеме материал этих глав может составить основу учебного курса
для подготовки магистров, имеющих профиль обучения со специ-
ализацией в ЦОС, прежде всего, по направлениям «Информатика
и вычислительная техника» и «Прикладная математика».
Две последние главы (шестая и седьмая) представляют собой
более углубленное теоретическое рассмотрение таких специальных
разделов ЦОС, как эффективное представление и компрессия сиг-
налов, цифровой спектральный анализ. Седьмая глава целиком по-
священа применению дискретных вейвлет-преобразований в ЦОС
и может составить основу отдельного спецкурса.
В книге используется двойная нумерация для рисунков, фор-
мул, примеров и теорем: первая цифра обозначает главу, вторая —
порядковый номер формулы (примера, теоремы) в главе. При ну-
мерации (обозначении) аксиом и свойств используется значок °,
например 1°. Начало и окончание доказательств теорем, решений
примеров обозначается соответственно символами ◄ и ►. Упражне-
ния (задачи) для самостоятельного решения приводятся непосред-
ственно в тех местах, где их появление логически наиболее связано
с излагаемым материалом, а не в конце глав или разделов, как это
чаще всего практикуется в учебной литературе.
Основу данного пособия составляют учебные курсы, читаемые
автором на протяжении ряда лет в Национальном исследователь-
ском университете «Московский институт электронной техники»
(МИЭТ) для бакалавров и магистров, обучающихся по направле-
нию «Прикладная математика». Большое значение в работе над
пособием имело обсуждение его содержания с коллегами. Автор
выражает глубокую признательность доценту кафедры высшей
математики № 1 МИЭТ В. В. Лесину и рецензентам, внимательно
ознакомившимся с текстом рукописи и высказавшим ряд ценных
замечаний, которые были учтены при подготовке издания.
Список сокращений и обозначений
АЦП — аналого-цифровое преобразование
АЧХ — амплитудно-частотная характеристика
БИХ — бесконечная импульсная характеристика
БПУ — быстрое преобразование Уолша
БПФ — быстрое преобразование Фурье
БПХ — быстрое преобразование Хаара
ВДПФ — вещественное дискретное преобразование Фурье
ВЧ — верхние частоты
ГВЗ — групповое время задержки
ДВП — дискретное вейвлет-преобразование
ДКП — дискретное косинусное преобразование
ДПГ — дискретный преобразователь Гильберта
ДПКП — дискретное псевдокосинусное преобразование
ДПЛ — дискретное преобразование Лапласа
ДПУ — дискретное преобразование Уолша
ДПФ — дискретное преобразование Фурье
ДПХ — дискретное преобразование Хаара
ИХ — импульсная характеристика
КИХ — конечная импульсная характеристика
КЗФ — квадратурно-зеркальные фильтры
КМА — кратно-масштабный анализ
КФ — ковариационная функция
ЛДС — линейная дискретная система
ЛДФ — линейный дискретный фильтр
ЛИВС — линейная инвариантная во времени система
ЛНП — линейное нормированное пространство
НОД — наибольший общий делитель
НЧ — нижние частоты
ОДКП — обратное ДКП
ОДПФ — обратное ДПФ
ОПФ — оконное преобразование Фурье
ПФ — передаточная функция
ЧХ — частотная характеристика
ФВЧ — фильтр верхних частот
ФНЧ — фильтр нижних частот
ФЧХ — фазочастотная характеристика
ЦД — цифровой дифференциатор
ЦОС — цифровая обработка сигналов
ЦФ — цифровой фильтр
ЭНП — элемент наилучшего приближения
C — множество комплексных чисел
N — множество натуральных чисел
R — множество действительных чисел
Z — множество целых чисел
x >>y — число x много больше числа y
[x] — целая часть числа x ≥ 0
round(x) = sign(x) [|x| + 0,5] — округление х до ближайшего целого
x mod p — остаток от деления целого числа x ≥ 0 на число p ∈ N
a ⊕ b(a + b) mod 2 — сложение по модулю 2, где a ∈ {0, 1} и b ∈{0, 1}
A ⊕ B — ортогональная сумма подпространств A и B
||x|| — норма элемента x
〈x, y〉 — скалярное произведение элементов x, y
Ā — замыкание множества A
z = Rez = i Imz — комплексное сопряжение числа z ∈ C
Res[ f (z), z0] — вычет функции f(z) в точке z0
F{f(t)} — преобразование Фурье функции f(t)
F-1{F(v)} — обратное преобразование Фурье функции F(v)
L{f (t )} — преобразование Лапласа функции f(t)
L-1{G(p)} — обратное преобразование Лапласа функции G(p)
Z{x(n)} — Z-преобразование последовательности x(n)
Z-1{X(z)} — обратное Z-преобразование функции X(z)
M(X) — математическое ожидание случайной величины Х
D(X) — дисперсия случайной величины X
В последние два десятилетия методы цифровой обработки сигна-
лов (ЦОС) в радиотехнике, электронике, системах связи, контроля
и управления стали преобладающими, активно вытесняя методы
аналоговой обработки. Этому способствовала стремительно уве-
личивавшаяся производительность вычислительной техники,
которая уже проникла практически во все области человеческой
деятельности. Сегодня, например, говоря о записи или обработке
аудио- и видеоинформации, мы не уточняем, что речь идет о циф-
ровых форматах, подразумевая это само собой разумеющимся.
Важность изучения методов ЦОС трудно переоценить: вопросы,
связанные с цифровой обработкой и представлением сигналов,
давно перестали быть узкоспециальными. Основы знаний в дан-
ной области требуются большинству инженеров, а для специали-
стов в области электроники, радиотехники и телекоммуникаций,
информатики и вычислительной техники необходимо более глубо-
кое понимание основных методов ЦОС и математической теории,
лежащей в их основе. Предлагаемое вниманию читателя учебное
пособие посвящено изучению данных вопросов.
Изначально ЦОС развивалась как ветвь, растущая из теории об-
работки аналоговых сигналов, и рассматривалась как раздел элек-
троники и радиотехники. Однако внедрение в системы обработки
сигналов цифровых программируемых процессоров и контролле-
ров, расширение спектра и увеличение сложности алгоритмов ЦОС,
реализация которых стала возможна в том числе в реальном мас-
штабе времени, превратили ЦОС в политехническую дисциплину.
Сегодня для математиков-программистов, специалистов в области
информатики и вычислительной техники эта область знаний пред-
ставляет собой постоянно расширяющееся поле для приложения
усилий. Данную тенденцию необходимо учитывать при подготовке
инженерных кадров. В предлагаемом вниманию читателя учебном
пособии рассматриваются основы теории ЦОС, изложение которой
по формату и содержанию ориентировано в первую очередь именно
на студентов, обучающихся по инженерным направлениям «При-
кладная математика» и «Информатика и вычислительная техника»
(бакалавриат и магистратура). Однако при написании пособия ав-
тор старался опираться лишь на курс высшей математики, общий
для всех инженерных направлений подготовки, поэтому оно может
быть рекомендовано также для студентов, обучающихся по профи-
лям подготовки в области радиотехники, связи и телекоммуника-
ций.
Первая глава носит вводный характер и содержит изложение тех
основных положений функционального анализа и теории преобра-
зования Фурье, которые потребуются далее в последующих главах.
Помимо этого, в первой главе вводятся популярные в ЦОС функ-
циональные системы Уолша и Хаара.
Вторая глава посвящена вопросам дискретизации непрерыв-
ных сигналов и преобразований, прежде всего преобразования
Фурье. Значительное внимание уделено частотным аспектам дис-
кретизации (как широкополосных, так и узкополосных сигналов)
и построению быстрых алгоритмов вычислений дискретных пре-
образований Фурье, Уолша, Хаара. Кроме того, рассматривается
скалярное и векторное квантование сигналов.
В третьей главе вводятся основные понятия теории линейных
дискретных систем (фильтров). Основное внимание уделено ана-
лизу систем. Рассматриваются вопросы передискретизации сигна-
лов и влияния эффектов квантования в цифровых системах. Также
изу чаются некоторые вопросы согласованной фильтрации и ска-
лярных фильтров Калмана.
В четвертой главе изложены основные классические методы
синтеза КИХ- и БИХ-фильтров по заданной частотной характе-
ристике. Завершает главу рассмотрение основ теории адаптивных
фильтров.
Пятая глава представляет собой введение в теорию информа-
ции, а также содержит описание ряда используемых на практике
методов эффективного статистического (энтропийного) кодирова-
ния.
Первые пять глав включают в себя рассмотрение общих тео-
ретических вопросов ЦОС. В сокращенном варианте этот мате-
риал может быть использован для базовой подготовки бакалавров
по различным инженерным направлениям обучения. В полном
объеме материал этих глав может составить основу учебного курса
для подготовки магистров, имеющих профиль обучения со специ-
ализацией в ЦОС, прежде всего, по направлениям «Информатика
и вычислительная техника» и «Прикладная математика».
Две последние главы (шестая и седьмая) представляют собой
более углубленное теоретическое рассмотрение таких специальных
разделов ЦОС, как эффективное представление и компрессия сиг-
налов, цифровой спектральный анализ. Седьмая глава целиком по-
священа применению дискретных вейвлет-преобразований в ЦОС
и может составить основу отдельного спецкурса.
В книге используется двойная нумерация для рисунков, фор-
мул, примеров и теорем: первая цифра обозначает главу, вторая —
порядковый номер формулы (примера, теоремы) в главе. При ну-
мерации (обозначении) аксиом и свойств используется значок °,
например 1°. Начало и окончание доказательств теорем, решений
примеров обозначается соответственно символами ◄ и ►. Упражне-
ния (задачи) для самостоятельного решения приводятся непосред-
ственно в тех местах, где их появление логически наиболее связано
с излагаемым материалом, а не в конце глав или разделов, как это
чаще всего практикуется в учебной литературе.
Основу данного пособия составляют учебные курсы, читаемые
автором на протяжении ряда лет в Национальном исследователь-
ском университете «Московский институт электронной техники»
(МИЭТ) для бакалавров и магистров, обучающихся по направле-
нию «Прикладная математика». Большое значение в работе над
пособием имело обсуждение его содержания с коллегами. Автор
выражает глубокую признательность доценту кафедры высшей
математики № 1 МИЭТ В. В. Лесину и рецензентам, внимательно
ознакомившимся с текстом рукописи и высказавшим ряд ценных
замечаний, которые были учтены при подготовке издания.
Список сокращений и обозначений
АЦП — аналого-цифровое преобразование
АЧХ — амплитудно-частотная характеристика
БИХ — бесконечная импульсная характеристика
БПУ — быстрое преобразование Уолша
БПФ — быстрое преобразование Фурье
БПХ — быстрое преобразование Хаара
ВДПФ — вещественное дискретное преобразование Фурье
ВЧ — верхние частоты
ГВЗ — групповое время задержки
ДВП — дискретное вейвлет-преобразование
ДКП — дискретное косинусное преобразование
ДПГ — дискретный преобразователь Гильберта
ДПКП — дискретное псевдокосинусное преобразование
ДПЛ — дискретное преобразование Лапласа
ДПУ — дискретное преобразование Уолша
ДПФ — дискретное преобразование Фурье
ДПХ — дискретное преобразование Хаара
ИХ — импульсная характеристика
КИХ — конечная импульсная характеристика
КЗФ — квадратурно-зеркальные фильтры
КМА — кратно-масштабный анализ
КФ — ковариационная функция
ЛДС — линейная дискретная система
ЛДФ — линейный дискретный фильтр
ЛИВС — линейная инвариантная во времени система
ЛНП — линейное нормированное пространство
НОД — наибольший общий делитель
НЧ — нижние частоты
ОДКП — обратное ДКП
ОДПФ — обратное ДПФ
ОПФ — оконное преобразование Фурье
ПФ — передаточная функция
ЧХ — частотная характеристика
ФВЧ — фильтр верхних частот
ФНЧ — фильтр нижних частот
ФЧХ — фазочастотная характеристика
ЦД — цифровой дифференциатор
ЦОС — цифровая обработка сигналов
ЦФ — цифровой фильтр
ЭНП — элемент наилучшего приближения
C — множество комплексных чисел
N — множество натуральных чисел
R — множество действительных чисел
Z — множество целых чисел
x >>y — число x много больше числа y
[x] — целая часть числа x ≥ 0
round(x) = sign(x) [|x| + 0,5] — округление х до ближайшего целого
x mod p — остаток от деления целого числа x ≥ 0 на число p ∈ N
a ⊕ b(a + b) mod 2 — сложение по модулю 2, где a ∈ {0, 1} и b ∈{0, 1}
A ⊕ B — ортогональная сумма подпространств A и B
||x|| — норма элемента x
〈x, y〉 — скалярное произведение элементов x, y
Ā — замыкание множества A
z = Rez = i Imz — комплексное сопряжение числа z ∈ C
Res[ f (z), z0] — вычет функции f(z) в точке z0
F{f(t)} — преобразование Фурье функции f(t)
F-1{F(v)} — обратное преобразование Фурье функции F(v)
L{f (t )} — преобразование Лапласа функции f(t)
L-1{G(p)} — обратное преобразование Лапласа функции G(p)
Z{x(n)} — Z-преобразование последовательности x(n)
Z-1{X(z)} — обратное Z-преобразование функции X(z)
M(X) — математическое ожидание случайной величины Х
D(X) — дисперсия случайной величины X