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

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

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

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

Обобщением функций Уолша на случай более чем двух значений являются функции Виленкина — Крестенсона .

Обозначение

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

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

${\displaystyle \operatorname {cal} (k,\theta )=\operatorname {wal} (2k,\theta ),}$

${\displaystyle \operatorname {sal} (k,\theta )=\operatorname {wal} (2k-1,\theta ).}$

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

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

${\displaystyle H_{2^{n}}={\begin{bmatrix}H_{2^{n-1}}&H_{2^{n-1}}\\H_{2^{n-1}}&-H_{2^{n-1}}\end{bmatrix}}.}$

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

${\displaystyle H_{1}={\begin{bmatrix}1\end{bmatrix}},}$

${\displaystyle H_{2}={\begin{bmatrix}1&1\\1&-1\end{bmatrix}},}$

${\displaystyle H_{4}={\begin{bmatrix}1&1&1&1\\1&-1&1&-1\\1&1&-1&-1\\1&-1&-1&1\end{bmatrix}},}$

${\displaystyle H_{8}={\begin{bmatrix}1&1&1&1&1&1&1&1\\1&-1&1&-1&1&-1&1&-1\\1&1&-1&-1&1&1&-1&-1\\1&-1&-1&1&1&-1&-1&1\\1&1&1&1&-1&-1&-1&-1\\1&-1&1&-1&-1&1&-1&1\\1&1&-1&-1&-1&-1&1&1\\1&-1&-1&1&-1&1&1&-1\end{bmatrix}},}$

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

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

Пример

Номер по Уолшу	Двоичная форма	Преобразование из кода Грея	Перестановка бит	Номер по Адамару
0	000	000	000	0
1	001	001	100	4
2	010	011	110	6
3	011	010	010	2
4	100	110	011	3
5	101	111	111	7
6	110	101	101	5
7	111	100	001	1

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

${\displaystyle W_{8}={\begin{bmatrix}1&1&1&1&1&1&1&1\\1&1&1&1&-1&-1&-1&-1\\1&1&-1&-1&-1&-1&1&1\\1&1&-1&-1&1&1&-1&-1\\1&-1&-1&1&1&-1&-1&1\\1&-1&-1&1&-1&1&1&-1\\1&-1&1&-1&-1&1&-1&1\\1&-1&1&-1&1&-1&1&-1\end{bmatrix}}.}$

Свойства

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

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

${\displaystyle \int \limits _{0}^{1}\operatorname {wal} (n,\theta )\cdot \operatorname {wal} (k,\theta )\,d\theta =0\qquad {\text{при }}k\neq n.}$

Пример

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

${\displaystyle \int \limits _{0}^{1}\operatorname {wal} (1,\theta )\cdot \operatorname {wal} (3,\theta )\,d\theta =}$

${\displaystyle =\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. Мультипликативность

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

${\displaystyle \operatorname {wal} (n,\theta )\cdot \operatorname {wal} (k,\theta )=\operatorname {wal} (i,\theta ),}$

где ${\displaystyle i=n\oplus k}$ — поразрядное сложение по модулю 2 номеров в двоичной системе.

Пример

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

${\displaystyle n\oplus k=01_{2}\oplus 11_{2}=10_{2}=2.}$

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

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

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

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

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

${\displaystyle S(t)=\sum _{i=0}^{\infty }c_{i}\cdot u_{i}(t),}$

где ${\displaystyle u_{i}}$ это одна из базисных функций, а ${\displaystyle c_{i}}$ — коэффициент.

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

${\displaystyle S(t)=\sum _{k=0}^{\infty }c_{k}\cdot \operatorname {wal} (k,t/T).}$

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

${\displaystyle S(n)=\sum _{k=0}^{\infty }c_{k}\cdot \operatorname {wal} (k,n).}$

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

${\displaystyle c_{k}={\frac {1}{T}}\int \limits _{0}^{T}S(t)\cdot \operatorname {wal} (k,t/T)\,dt.}$

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

Существует также быстрое преобразование Уолша . Оно является в значительной степени более эффективным, чем преобразование Уолша — Адамара . Кроме того, для частного случая с двумя переменными функции Уолша обобщены как поверхности . Также существуют восемь аналогичных функциям Уолша базисов ортогональных бинарных функций , отличающихся нерегулярной структурой, которые также обобщены на случай функций двух переменных. Для каждого из восьми базисов доказано представление «ступенчатых» функций в виде конечной суммы бинарных функций, взвешиваемых с соответствующими коэффициентами .

Литература

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

См. также

• Матрица Адамара
• Коэффициент Уолша
• Ортонормированная система
• Ортогональный базис
• Ряд Фурье

Примечания