6.4. Ортогональные преобразования в диадных базисах
Ортогональные преобразования в диадных (или иначе говоря, двузначных знакопеременных) базисах определены для данных, представленных векторами длиной N= 2M. К таким преобразованиям относятся преобразования Адамара, Пэли, Уолша, Трахтмана, Качмарджа и ряд других [6,11,21]. Матрица ядра любого из подобных преобразований содержит целочисленные коэффициенты из множества {-1; +1}. Очевидно, что при выполнении подобных преобразований существенно сокращается объем вычислений за счет исключения умножения в каждой базовой операции.
Матрица ядра преобразования Уолша - Адамара для N =2m может быть описана как результат кронекеровского произведения m матриц ДЭФ E2 размера 2х2 [6,12]:
, (6.14)
где символ - операция кронекеровского умножения векторов, в результате чего порождается матрица блочной структуры. Заметим, что операция кронекеровского умножения двух матриц и состоит в получении блочной матрицы, блоками которой является умноженная на соответствующий элемент правой матрицы левая матрица, т.е.:
аналогично можно получить и для N = 8:
Матрица ядра Адамара обладает следующими свойствами:
1) цикличностью aN+k = ak; aN-k = a-k
2) мультипликативностью ak+l = ak * al
3) симметричностью AN = ANT
В задачах ЦОС используются и другие, подобные Адамару, преобразования - Пэли, Уолша, Трахтмана и других. Ядра (матрицы) этих преобразований могут быть получены на основе матрицы ядра преобразования Адамара при определенном переупорядочении их строк. Поэтому перед рассмотрением указанных преобразований рассмотрим правила переупорядочения матриц, применяемые для формирования ядер таких преобразований.
Переупорядочим элементы вектора таким образом, чтобы первые элементы вектора были бы чётными, а вторые - нечётными. Повторим эту процедуру до тех пор, умножая каждый раз длину соответствующего вектора вдвое, пока длина подвектора не станет равной 2. В результате получится переупорядоченный вектор, элементы которого упорядочены по закону так называемой двоичной инверсии.
В частности, для N=8 такое переупорядочение будет выполняться следующим образом:
Вектор можно получить изX, если задать следующее правило формирования индекса текущего элемента вектора из индекса элементаисходного вектораX:
1) записывается двоичный код текущего индекса i;
2) двоичный код записывается в обратном порядке как рефлексивный или отраженный код (т.е. начиная с младших разрядов);
3) полученный код определяет индекс текущего элемента вектора ;
4) переводим полученный индекс в десятичную систему.
Для рассмотренного выше случая (N=8) получим:
Процедура перестановки в терминах векторно-матричных операций может быть записана как:
, (6.15)
где - перестановочная матрица. Для случая двоично-инверсной перестановки перестановочная матрица будет иметь вид:
Элементы вектора могут быть также переупорядочены по коду Грея:
В терминах векторно-матричных операций подобная перестановка элементов вектора может быть описана так:
,
где - перестановочная матрица, в частности, дляN=8:
Ядро преобразования Пэли можно получить из ядра преобразования Адамара, переупорядочив строки матрицы AN по закону двоичной инверсии, в частности, для N =8 получаем:
В общем случае правило перехода от матрицы Адамара к матрице Пэли может быть представлено как [6]:
(6.16)
Если теперь переупорядочить строки матрицы ядра преобразования Пэли по коду Грея, то получим матрицу ядра преобразования Уолша[8]
Или в общем виде:
(6.18)
Очевидно, что свойства матриц PN и WN аналогичны свойствам матрицы AN. Матрицы ядер преобразования Трахтмана и Качмарджа также могут быть получены на основе матрицы ядра Адамара, но при использовании обратной перестановки по коду Грея.
Заметим, что матрицы преобразований в указанных базисах отличаются порядком строк. Очевидно, что при обработке одного и того же вектора исходных данных в различных базисах вектор результата будет содержать одинаковые по своей величине элементы, отличаясь для каждого преобразования лишь порядком их следования. Поэтому для всех подобных преобразований можно использовать одну и ту же матрицу ядра ( например,AN), а для получения вектора F с нужным для каждого преобразования порядком следования элементов, переупорядочить элементы исходного вектора . Так, для преобразования Пэли необходима двоично-инверсная перестановка, а для преобразования Уолша - двоично-инверсная перестановка и затем перестановка по коду Грея.
Если проанализировать все рассмотренные во второй главе преобразования, то можно придти к выводу, что их сущность состоит в разложении исходной функции на ряд чётных и нечётных составляющих, которые задаются строками матриц EN, HN, AN, WN и PN. Так, для матриц EN и HN это набор гармонических функций cos[…] и sin[..], а для AN, WN и PN - наборы прямоугольных знакопеременных функций.
Тем самым, в зависимости от вида исходной функции, в её составе будут определены отдельные компоненты (и их частотное значение), которые задаются строками матрицы ядра преобразования. Очевидно, что разложение по ортогональным функциям, задаваемым строками матрицы EN ,позволяет определить частотный состав исходной функции (сигнала), что имеет вполне понятный физический смысл.
Точно также при разложении по функциям, задаваемым строками матриц AN, WN и PN, можно определить, какой вклад вносит та или иная знакопеременная функция в состав исходного сигнала.
Очевидно, что исходный сигнал может быть разложен по различным ортогональным составляющим. При этом вклад таких составляющих в исходный сигнал будет различен для разных матриц ортогональных преобразований.
Согласно теореме Коруэна-Лоева [21], может быть определено оптимальное разложение исходной функции по набору ортогональных функций в смысле наименьшего числа отличных от нуля компонент такого разложения.
На практике для сигналов гармонической природы удобно использовать различные гармонические функции, т.е. для определения частотного состава сигнала выполнить преобразование Фурье или Хартли (ДПФ или БПФ). Действительно, для моногармонического сигнала лишь одна компонента разложения по строкам матрицы EN будет отлична от “0” (при условии, что f0 кратно kπ).
Для сигналов, описываемых знакопеременными функциями, близким к оптимальному является разложение по знакопеременным функциям типа Уолша, Адамара. Поэтому в задачах кодирования и распознавания речи, где для представления сигналов широко используется метод широтно-импульсной модуляции, удобно выполнять разложение по ортогональным функциям, задаваемым строками матриц AN, WN или PN.
- Цифровая обработка сигналов
- Санкт-Петербург
- Содержание
- 7.2. Вейвлеты 106
- Введение
- 1. Основные понятия цифровой обработки сигналов
- Понятие о первичной и вторичной обработке сигналов
- Основные требования к системам цос
- 2. Понятие сигналов. Виды сигналов
- 2.1. Виды сигналов
- 2.2. Энергия и мощность сигнала
- 2.3. Представление периодических сигналов в частотной области
- 2.4. Представление в частотной области непериодических сигналов
- Введение в теорию ортогональных преобразований
- 2.4.2. Интегральное преобразование Фурье
- 2.5. Свойства преобразования Фурье
- 2.5.1. Фурье-анализ неинтегрируемых сигналов
- 2.6. Интегральное преобразование Хартли
- 2.7. Случайные сигналы
- 2.7.1.Модели случайных процессов
- 2.7.2. Вероятностные характеристики случайного процесса Функциональные характеристики.
- Числовые характеристики
- Примеры случайных процессов с различными законами распределения
- 3. Корреляционный анализ сигналов
- 3.1. Корреляционная функция (кф):
- 3.2. Взаимная корреляционная функция
- 3.3. Взаимный спектр сигналов
- 3.4. Корреляционные функции случайных процессов
- 3.4.1. Стационарные и эргодические случайные процессы
- 3.5. Спектральные характеристики случайных процессов
- 3.5.1. Теорема Винера-Хинчина
- 3.6. Комплексная огибающая сигнала
- 4. Переход от аналоговых сигналов к цифровым
- 4.1. Дискретизация сигналов
- 4.1.1. Влияние формы дискретизирующих импульсов
- 4.1.2. Теорема Котельникова
- 4.1.3. Дискретизация при использовании квадратурных сигналов
- 4.1.4. Определение шага временной дискретизации при восстановлении сигнала полиномами 0-го порядка
- 4.1.5. Определение шага дискретизации при заданной автокорреляционной функции
- Изменение частоты дискретизации. При решение различных задач обработки сигналов достаточно часто требуется изменение частоты дискретизации сигнала.
- 4.2. Квантование непрерывных сигналов по уровню
- 5. Основные типы дискретных алгоритмов цифровой обработки сигналов
- 5.1. Линейные и нелинейные преобразования
- 5.2. Характеристики линейных систем
- 5.4. Апериодическая свертка и корреляция
- 5.5. Двумерная апериодическая свертка и корреляция
- 5.6 Нерекурсивные и рекурсивные фильтры
- 5.7. Метод синхронного или когерентного накопления
- 5.8. Адаптивные фильтры.
- 5.8.1. Фильтр Винера-Хопфа.
- 5.10. Фильтр Калмана.
- 6. Дискретные ортогональные преобразования
- Задачи цос, решаемые методами дискретных ортогональных преобразований
- 6.1. Дискретное преобразование Фурье
- 6.2. Дискретное преобразование Хартли
- 6.3. Двумерные дискретные преобразования Фурье и Хартли
- 6.4. Ортогональные преобразования в диадных базисах
- 6.5. Дискретное косинусное преобразование
- 6.6. Оконное преобразование Фурье
- 6.7. Выполнение фильтрации в частотной области
- Виды фильтров
- 7. Вейвлет преобразования или разложение по всплескам
- 7.1. Понятие о Wavelet-преобразованиях. Преобразование Хаара
- 7.2. Вейвлеты
- 7.2.1. Непрерывные вейвлет преобразования
- 7.2.2. Частотный подход к вейвлет преобразованиям
- 7.2.3. Вейвлет-ряды дискретного времени
- 7.2.4. Дискретное вейвлет-преобразование
- 7.2.4.1. Условия полного восстановления сигнала
- 7.2.5. Пакеты вейвлетов (алгоритм одиночного дерева)
- 7.2.6. Целочисленное вейвлет-преобразование
- Целочисленное вычисление вейвлет–преобразование (2,2). Это преобразование эквивалентно вейвлет-преобразованию Хаара, использующему следующие фильтры декомпозиции:
- Целочисленное вычисление вейвлет-преобразования (2,6). Данное преобразование эквивалентно использованию следующих фильтров анализа:
- Целочисленное вычисление вейвлет –преобразования (5,3). Такое преобразование также является разновидностью биортогонального преобразования и использует следующую пару фильтров:
- 7.3. Применение вейвлет-преобразований для сжатия изображения
- 8. Быстрые алгоритмы ортогональных преобразований
- 8.1. Вычислительная сложность дпф и способы её сокращения
- 8.2. Запись алгоритма бпф в векторно-матричной форме
- 8.3. Представление алгоритма бпф в виде рекурсивных соотношений
- 8.4. Алгоритмы бпф с прореживанием по времени и по частоте
- 8.6. Вычислительная сложность алгоритмов бпф
- 8.7. Выполнение бпф для случаев
- 8.8. Быстрое преобразование Хартли
- 8.9. Быстрое преобразование Адамара
- 8.10. Выбор метода вычисления свертки / корреляции
- 9. Алгоритмы нелинейной обработки сигналов
- 9.1. Ранговая фильтрация
- 9.2. Взвешенная ранговая фильтрация
- 9.3. Скользящая эквализация гистограмм
- 9.4. Преобразование гистограмм распределения
- Контрольные вопросы и задания. Разделы 1-3.
- Раздел 4
- Разделы 5 и 6
- Раздел 5
- Раздел 8
- Раздел 9
- Кафедра вычислительной техники