Русская Википедия:Функция Уолша
Функциями Уолша называется семейство функций, образующих ортогональную систему, принимающих значения только +1 и −1 на всей области определения.
В принципе, функции Уолша могут быть представлены в непрерывной форме, но чаще их определяют как дискретные последовательности из <math>2^n</math> элементов. Группа из <math>2^n</math> функций Уолша образует матрицу Адамара.
Функции Уолша получили широкое распространение в радиосвязи, где с их помощью осуществляется кодовое разделение каналов (CDMA), например, в таких стандартах сотовой связи, как IS-95, CDMA2000 или UMTS.
Система функций Уолша является ортонормированным базисом и, как следствие, позволяет раскладывать сигналы произвольной формы в обобщённый ряд Фурье.
Обобщением функций Уолша на случай более чем двух значений являются функции Виленкина — Крестенсона.
Обозначение
Пусть функция Уолша определена на интервале [0, T]; за пределами этого интервала функция периодически повторяется. Введём безразмерное время <math>\theta = t / T</math>. Тогда функция Уолша под номером k обозначается как <math>\operatorname{wal}(k,\theta)</math>. Нумерация функций зависит от метода упорядочения функций. Существует упорядочение по Уолшу — в этом случае функции обозначаются так, как описано выше. Также распространены упорядочения по Пэли (<math>\operatorname{pal}(p,\theta)</math>) и по Адамару (<math>\operatorname{had}(h,\theta)</math>).
Относительно момента <math>\theta = 0</math> функции Уолша можно разделить на чётные и нечётные. Они обозначаются как <math>\operatorname{cal}(k,\theta)</math> и <math>\operatorname{sal}(k,\theta)</math> соответственно. Эти функции аналогичны тригонометрическим синусам и косинусам. Связь между этими функциями выражается следующим образом:
- <math>\operatorname{cal}(k,\theta) = \operatorname{wal}(2k,\theta),</math>
- <math>\operatorname{sal}(k,\theta) = \operatorname{wal}(2k-1,\theta).</math>
Формирование
Существует несколько способов формирования. Рассмотрим один из них, наиболее наглядный: матрица Адамара может быть сформирована рекурсивным методом с помощью построения блочных матриц по следующей общей формуле:
- <math>H_{2^n} = \begin{bmatrix}
H_{2^{n-1}} & H_{2^{n-1}} \\ H_{2^{n-1}} & -H_{2^{n-1}} \end{bmatrix}.</math>
Так может быть сформирована матрица Адамара длины <math>2^n</math>:
- <math>H_1 = \begin{bmatrix}
1 \end{bmatrix},</math>
- <math>H_2 = \begin{bmatrix}
1 & 1 \\ 1 & -1 \end{bmatrix},</math>
- <math>H_4 = \begin{bmatrix}
1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 \end{bmatrix},</math>
- <math>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},</math>
Каждая строка матрицы Адамара и является функцией Уолша.
В данном случае функции упорядочены по Адамару. Номер функции по Уолшу вычисляется из номера функции по Адамару путём перестановки битов в двоичной записи номера в обратном порядке с последующим преобразованием результата из кода Грея.
Пример
| Номер по Уолшу | Двоичная форма | Преобразование из кода Грея | Перестановка бит | Номер по Адамару |
|---|---|---|---|---|
| 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 |
В итоге получается матрица Уолша, в которой функции упорядочены по Уолшу:
- <math>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}.</math>
Свойства
1. Ортогональность
Скалярное произведение двух разных функций Уолша равно нулю:
- <math>\int\limits_0^1 \operatorname{wal}(n, \theta) \cdot \operatorname{wal}(k, \theta) \,d\theta = 0 \qquad \text{при } k \neq n.</math>
Пример
Допустим, что n = 1, k = 3 (см. выше). Тогда
- <math>\int\limits_0^1 \operatorname{wal}(1, \theta) \cdot \operatorname{wal}(3,\theta) \,d\theta = </math>
- <math>= \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.</math>
2. Мультипликативность
Произведение двух функций Уолша даёт функцию Уолша:
- <math>\operatorname{wal}(n, \theta) \cdot \operatorname{wal}(k, \theta) = \operatorname{wal}(i, \theta),</math>
где <math>i = n \oplus k</math> — поразрядное сложение по модулю 2 номеров в двоичной системе.
Пример
Допустим, что n = 1, k = 3. Тогда
- <math>n \oplus k = 01_2 \oplus 11_2 = 10_2 = 2.</math>
В результате умножения получим:
- <math>\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} </math>
Преобразование Уолша — Адамара
Является частным случаем обобщённого преобразования Фурье, в котором базисом выступает система функций Уолша.
Обобщённый ряд Фурье представляется формулой
- <math>S(t) = \sum_{i=0}^\infty c_i \cdot u_i(t),</math>
где <math>u_i</math> это одна из базисных функций, а <math>c_i</math> — коэффициент.
Разложение сигнала по функциям Уолша имеет вид
- <math>S(t) = \sum_{k=0}^\infty c_k \cdot \operatorname{wal}(k, t/T).</math>
В дискретной форме формула запишется следующим образом:
- <math>S(n) = \sum_{k=0}^\infty c_k \cdot \operatorname{wal}(k, n).</math>
Определить коэффициенты <math>c_i</math> можно, осуществив скалярное произведение раскладываемого сигнала на соответствующую базисную функцию Уолша:
- <math>c_k = \frac{1}{T} \int\limits_0^T S(t) \cdot \operatorname{wal}(k, t/T) \,dt.</math>
Следует учитывать периодический характер функций Уолша.
Существует также быстрое преобразование Уолша[1]. Оно является в значительной степени более эффективным, чем преобразование Уолша — Адамара[2]. Кроме того, для частного случая с двумя переменными функции Уолша обобщены как поверхности[3]. Также существуют восемь аналогичных функциям Уолша базисов ортогональных бинарных функций[4], отличающихся нерегулярной структурой, которые также обобщены на случай функций двух переменных. Для каждого из восьми базисов доказано представление «ступенчатых» функций в виде конечной суммы бинарных функций, взвешиваемых с соответствующими коэффициентами[5].
Литература
См. также
- Базис Хаара
- Матрица Адамара
- Коэффициент Уолша
- Ортонормированная система
- Ортогональный базис
- Ряд Фурье
Примечания
- ↑ БЫСТРОЕ ПРЕОБРАЗОВАНИЕ УОЛША. В. Н. Малозёмов Шаблон:Wayback.
- ↑ Fast Walsh Transform Шаблон:Wayback.
- ↑ Romanuke V. V. ON THE POINT OF GENERALIZING THE WALSH FUNCTIONS TO SURFACES Шаблон:Wayback.
- ↑ Romanuke V. V. GENERALIZATION OF THE EIGHT KNOWN ORTHONORMAL BASES OF BINARY FUNCTIONS TO SURFACES Шаблон:Wayback.
- ↑ Romanuke V. V. EQUIDISTANTLY DISCRETE ON THE ARGUMENT AXIS FUNCTIONS AND THEIR REPRESENTATION IN THE ORTHONORMAL BASES SERIES Шаблон:Wayback.
