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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Графики первых четырёх функций Уолша

Функциями Уолша называется семейство функций, образующих ортогональную систему, принимающих значения только 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]. Оно является в значительной степени более эффективным, чем преобразование Уолша — Адамара[2]. Кроме того, для частного случая с двумя переменными функции Уолша обобщены как поверхности[3]. Также существуют восемь аналогичных функциям Уолша базисов ортогональных бинарных функций[4], отличающихся нерегулярной структурой, которые также обобщены на случай функций двух переменных. Для каждого из девяти базисов доказано представление "ступенчатых" функций в виде конечной суммы бинарных функций, взвешиваемых с сответствующими коэффициентами[5].

Литература[править | править исходный текст]

  • Баскаков С. И. Радиотехнические цепи и сигналы. — М.:Высшая школа, 2005 — ISBN 5-06-003843-2
  • Голубов Б. И., Ефимов А. В., Скворцов В. А. Ряды и преобразования Уолша: теория и применения. — М.:Наука, 1987
  • Залманзон Л. А. Преобразования Фурье, Уолша, Хаара и их применение в управлении, связи и других областях. — М.: Наука, 1989 — ISBN 5-02-014094-5

См. также[править | править исходный текст]

Примечания[править | править исходный текст]