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

Функциями Уолша называется семейство функций, образующих ортогональную систему, принимающих значения только +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}},}$

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

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

Пример

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

${\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.}$

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

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

Литература

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

См. также

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

Примечания

Эта страница в последний раз была отредактирована 14 октября 2022 в 01:53.