Функция Уолша

Функция Уолша
Графики первых четырёх функций Уолша

Функциями Уолша называется семейство функций, образующих ортогональную систему, принимающих значения только 1 и −1 на всей области определения.

В принципе, функции Уолша могут быть представлены в непрерывной форме, но чаще их определяют как дискретные последовательности из 2^n элементов. Группа из 2^n функций Уолша образует матрицу Адамара.

Функции Уолша получили широкое распространение в радиосвязи, где с их помощью осуществляется кодовое разделение каналов (CDMA), например, в таких стандартах сотовой связи, как IS-95, CDMA2000 или UMTS.

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

Содержание

Обозначение

Пусть функция Уолша определена на интервале [0, T]; за пределами этого интервала функция периодически повторяется. Введём безразмерное время ~\theta = t / T. Тогда функция Уолша под номером k обозначается как wal(k,\theta). Нумерация функций зависит от метода упорядочения функций. Существует упорядочение по Уолшу — в этом случае функции обозначаются так, как описано выше. Также распространены упорядочения по Пэли (pal(p,\theta)) и по Адамару (had(h,\theta)).

Относительно момента \theta = 0 функции Уолша можно разделить на чётные и нечётные. Они обозначаются как ~cal(k,\theta) и ~sal(k,\theta) соответственно. Эти функции аналогичны тригонометрическим синусам и косинусам. Связь между этими функциями выражается следующим образом:

~cal(k,\theta) = wal(2k,\theta)
~sal(k,\theta) = wal(2k-1,\theta)

Формирование

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

H_{2^n} = \begin{bmatrix}
H_{2^{n-1}} & H_{2^{n-1}} \\
H_{2^{n-1}} & -H_{2^{n-1}}
\end{bmatrix}\,

Так может быть сформирована матрица Адамара длины 2^n:

H_1 = \begin{bmatrix}
1
\end{bmatrix}\,
H_2 = \begin{bmatrix}
1 & 1 \\
1 & -1
\end{bmatrix}\,
H_4 = \begin{bmatrix}
1 & 1 & 1 & 1 \\
1 & -1 & 1 & -1 \\
1 & 1 & -1 & -1 \\
1 & -1 & -1 & 1
\end{bmatrix}\,

Каждая строка Матрицы Адамара и является функцией Уолша.

В данном случае функции упорядочены по Адамару. Номер функции по Уолшу вычисляется из номера функции по Адамару путём перестановки бит в двоичной записи номера в обратном порядке с последующим преобразованием результата из кода Грея.

Пример

Номер по Адамару Двоичная форма Перестановка бит Преобразование из кода Грея Номер по Уолшу
0 00 00 00 0
1 01 10 11 3
2 10 01 01 1
3 11 11 10 2

В итоге получается матрица Уолша, в которой функции упорядочены по Уолшу:

W_4 = \begin{bmatrix}
1 & 1 & 1 & 1 \\
1 & 1 & -1 & -1 \\
1 & -1 & -1 & 1 \\
1 & -1 & 1 & -1
\end{bmatrix}\,

Свойства

1. Ортогональность

Скалярное произведение двух разных функций Уолша равно нулю:

{\int\limits_0^1 wal(n, \theta) \cdot wal(k, \theta) d\theta = 0} \qquad {\mbox{if } k \neq n}

Пример

Допустим, что n = 1, k = 3 (см. выше). Тогда,

\int\limits_0^1 wal(1, \theta) \cdot wal(3,\theta)d\theta = \,
= \int\limits_0^{1/4} 1^2 d\theta + \int\limits_{1/4}^{1/2} 1 \cdot (-1) d\theta
+ \int\limits_{1/2}^{3/4} (-1) \cdot 1 d\theta + \int\limits_{3/4}^1 (-1)^2 d\theta = 0\,

2. Мультипликативность

Произведение двух функций Уолша даёт функцию Уолша.

wal(n, \theta) \cdot wal(k, \theta) = wal(i, \theta)\,

где i = n \oplus k — сложение по модулю 2 номеров в двоичной системе.

Пример

Допустим, что n = 1, k = 3. Тогда,

n \oplus k = 01_2 \oplus 11_2 = 10_2 = 2

В результате умножения получим:

\begin{array}{|c|c|c|c||c|}
  \, & \, & \, & \, & n \\
  \hline
  1 & 1 & -1 & -1 & wal(1,\theta) \\
  1 & -1 & 1 & -1 & wal(3,\theta) \\
  \hline
  1 & -1 & -1 & 1 & wal(2,\theta) \\
\end{array}

Преобразование Уолша-Адамара

Является частным случаем обобщённого преобразования Фурье, в котором базисом выступает система функций Уолша.

Обобщённый ряд Фурье представляется формулой:

S(t) = \sum_{i=0}^{\infty} {c_i \cdot u_i(t)}\,

где u_i это одна из базисных функций, а c_i — коэффициент.

Разложение сигнала по функциям Уолша имеет вид:

S(t) = \sum_{k=0}^{\infty} {c_k \cdot wal(k, t/T)}\,

В дискретной форме формула запишется следующим образом:

S(n) = \sum_{k=0}^{\infty} {c_k \cdot wal(k, n)}\,

Определить коэффициенты c_i можно, осуществив скалярное произведение раскладываемого сигнала на соответствующую базисную функцию Уолша:

c_k = \frac{1}{T} \int\limits_0^T {S(t) \cdot wal(k, t/T)}dt\,

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

Существует также быстрое преобразование Уолша[1].

Литература

Баскаков С. И. Радиотехнические цепи и сигналы. — М.:Высшая школа, 2005 — ISBN 5-06-003843-2

См. также

Ссылки

  1. БЫСТРОЕ ПРЕОБРАЗОВАНИЕ УОЛША. В.Н.Малозёмов



Wikimedia Foundation. 2010.

Смотреть что такое "Функция Уолша" в других словарях:

  • Функция Радемахера — Графики функций Радемахера с Функция Радемахера  кусочно постоянная периодическая функция, принимающая только два значения 1 и −1 на всей обл …   Википедия

  • УОЛША СИСТЕМА — функций {Wn(x)} на отрезке [0, 1] функции и при где k=0,1, 2, . . ., функции Радемахера, v1>v2>...>vm>0 двоичное представление числа Эта система была определена и исследована Дж. Уолтом [1], хотя еще в 1900 году Баррет использовал функции этой… …   Математическая энциклопедия

  • Коэффициент Уолша — булевой функции это величина , где . Коэффициенты Уолша являются спектральной характеристикой булевой функции, то есть являются аналогом коэффициентов Фурье. Вычисление коэ …   Википедия

  • Матрица Адамара — Для улучшения этой статьи желательно?: Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное. Матрица …   Википедия

  • Ряд Фурье — Добавление членов ряда Фурье …   Википедия

  • Ряды Фурье — Ряд Фурье  представление произвольной функции f с периодом τ в виде ряда Этот ряд может быть также переписан в виде . где Ak  амплитуда k го гармонического колебания (функции cos),   кру …   Википедия

  • Фурье ряд — Ряд Фурье  представление произвольной функции f с периодом τ в виде ряда Этот ряд может быть также переписан в виде . где Ak  амплитуда k го гармонического колебания (функции cos),   кру …   Википедия

  • Rabbit — Схема работы алгоритма Rabbit высокоскоростной поточный шифр впервые представленный [1] в феврале 2003 года на 10 м симпозиуме FSE. В мае 2005, он был отправлен на конку …   Википедия

  • Псевдослучайная двоичная последовательность — частный случай ПСП, в которой элементы принимают два возможных значения 0 и 1 (или 1 и +1 ). Постулаты Голомба Одна из первых формулировок некоторых основополагающих правил для статистических свойств периодических псевдослучайных… …   Википедия

  • Администрация США — (Administration of USA) Определение администрации США, высшие руководители США Определение администрации США, высшие руководители США, административные учреждения Содержание Содержание Определение Административное право Служба высших… …   Энциклопедия инвестора


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»