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

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

Функциями Уолша называется семейство функций, образующих ортогональную систему, принимающих значения только 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. ↑ БЫСТРОЕ ПРЕОБРАЗОВАНИЕ УОЛША. В.Н.Малозёмов