Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO
3.9. Преобразование Уолша и родственные емуПодобно дискретному преобразованию Фурье можно рассматривать дискретное преобразование Уолша как дискретный аналог непрерывного преобразования сигнала по базису, составленному из функций Уолша. Существует три версии этого преобразования, отличающиеся способом упорядочивания базисных функций, составляющих ядро преобразования: преобразование Уолша — Адамара, преобразование Пэли и преобразование Уолша. Все они определены на последовательностях, количество членов которых равно целой степени 2. Начнем с преобразования Уолша. Выше уже приводилось определение функций Уолша (§ 1.3). Как и дискретное преобразование Фурье, дискретное преобразование Уолша строится как преобразование последовательности отсчетов сигнала по базису из отсчетов функций Уолша, взятых в дискретной последовательности точек:
Пусть количество отсчетов сигналов N равно
где Подставив (3.111) в (3.110), получим
Поскольку
суммирование в (3.112) по к можно выполнить как многомерное по
Такое представление является основой построения алгоритмов быстрых преобразований Уолша (см. гл. 4). Формула обратного преобразования Уолша совпадает с формулой прямого преобразования (3.106):
Как следует из формулы (3.111), функции Уолша в преобразовании Уолша упорядочены в соответствии с двоично-инвертированными (т. е. читаемыми в обратном порядке) кодами Грея их номера. Если вспомнить, что функции Уолша порождаются функциями Радемахера, то смысл такого упорядочения в том, что каждая следующая по номеру функция Уолша отличается от предыдущей добавлением или изъятием только одной функции Радемахера. Можно упорядочить те же функции просто по их двоичным номерам. Преобразование по таким функциям
носит название преобразования Уолша—Адамара (в некоторых источниках — преобразование Адамара или BIFOR-преобразование [80])
Способ упорядочения базисных функций определяется только соображениями удобства, так как независимо от нумерации каждый коэффициент преобразования соответствует своей базисной функции из одного и того же множества функций. Обычно удобно связывать порядок базисных функций со сходимостью представления по ним сигналов, считая, что каждый старший по номеру коэффициент представления, соответствующий старшей по номеру базисной функции, вносит меньший вклад в сигнал. С этой точки зрения иногда оказывается лучше упорядочение базисных функций Уолша в соответствии с двоично-инвертированным двоичным кодом. Такое упорядочение было введено Пэли [57]:
Описанные дискретные преобразования могут быть представлены в матричной форме как умножение матрицы-столбца исходной последовательности а на матрицу преобразования. В результате получается матрица-столбец преобразования а:
где Например, матрицы (см. скан) Справа от каждой матрицы в (3.120) указано число перемен знака в соответствующей строке матрицы. Сравнивая эти данные, можно видеть, что строки матрицы Уолша Матрицы преобразований Уолша являются симметрическими, т. е. не меняющимися при транспонировании, и ортогональными, так как они обратны самим себе. Таким образом, преобразования Уолша, так же как и ДПФ, относятся к классу унитарных преобразований (для действительных матриц, какими являются матрицы преобразований Уолша, понятия унитарности и ортогональности совпадают). Матрицы WAL можно свести к матрице Адамара HAD; если домножить их на соответствующие матрицы перестановки, содержащие единицу на том элементе строки Пусть МТ—матрица двоичной инверсии;
Поскольку матрица Уолша-Пэли, матрица двоичной инверсии и матрица Адамара являются симметрическими, то справедливо также соотношение
Важной особенностью матрицы Адамара является то, что она принадлежит к так называемым кронекеровским матрицам
где Признак Замечательной особенностью кронекеровских матриц является то, что они представимы (факторизуются) в виде произведения слабо заполненных матриц, т. е. матриц, большинство элементов которых равно нулю. Благодаря этому при умножении на кронекеровскую матрицу требуется выполнить значительно меньше операций, чем обычно при матричном умножении (см. гл. 4). Поскольку двумерные функции Уолша определяются как произведение одномерных, от одномерных преобразований Уолша нетрудно перейти к двумерным. Проще всего их записывать как произведение матриц, например:
где
|
1 |
Оглавление
|