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

Материал из testwiki
Перейти к навигации Перейти к поиску
Графики первых четырёх функций Уолша

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

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

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

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

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

Обозначение

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

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

cal⁡(k,θ)=wal⁡(2k,θ),
sal⁡(k,θ)=wal⁡(2k−1,θ).

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

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

H2n=[H2n−1H2n−1H2n−1−H2n−1].

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

H1=[1],
H2=[111−1],
H4=[11111−11−111−1−11−1−11],
H8=[111111111−11−11−11−111−1−111−1−11−1−111−1−111111−1−1−1−11−11−1−11−1111−1−1−1−1111−1−11−111−1],

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

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

Пример

Номер по Уолшу Двоичная форма Преобразование из кода Грея Перестановка бит Номер по Адамару
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

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

W8=[111111111111−1−1−1−111−1−1−1−11111−1−111−1−11−1−111−1−111−1−11−111−11−11−1−11−111−11−11−11−1].

Свойства

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

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

∫01wal⁡(n,θ)⋅wal⁡(k,θ)dθ=0при k≠n.

Пример

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

∫01wal⁡(1,θ)⋅wal⁡(3,θ)dθ=
=∫01/412dθ+∫1/41/21⋅(−1)dθ+∫1/23/4(−1)⋅1dθ+∫3/41(−1)2dθ=0.

2. Мультипликативность

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

wal⁡(n,θ)⋅wal⁡(k,θ)=wal⁡(i,θ),

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

Пример

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

n⊕k=012⊕112=102=2.

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

n11−1−1wal⁡(1,θ)1−11−1wal⁡(3,θ)1−1−11wal⁡(2,θ)

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

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

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

S(t)=∑i=0∞ci⋅ui(t),

где ui это одна из базисных функций, а ci — коэффициент.

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

S(t)=∑k=0∞ck⋅wal⁡(k,t/T).

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

S(n)=∑k=0∞ck⋅wal⁡(k,n).

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

ck=1T∫0TS(t)⋅wal⁡(k,t/T)dt.

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

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

Литература

См. также

Примечания

Шаблон:Примечания

  1. ↑ БЫСТРОЕ ПРЕОБРАЗОВАНИЕ УОЛША. В. Н. Малозёмов Шаблон:Wayback.
  2. ↑ Fast Walsh Transform Шаблон:Wayback.
  3. ↑ Romanuke V. V. ON THE POINT OF GENERALIZING THE WALSH FUNCTIONS TO SURFACES Шаблон:Wayback.
  4. ↑ Romanuke V. V. GENERALIZATION OF THE EIGHT KNOWN ORTHONORMAL BASES OF BINARY FUNCTIONS TO SURFACES Шаблон:Wayback.
  5. ↑ Romanuke V. V. EQUIDISTANTLY DISCRETE ON THE ARGUMENT AXIS FUNCTIONS AND THEIR REPRESENTATION IN THE ORTHONORMAL BASES SERIES Шаблон:Wayback.
Источник — https://ru.wiki.beta.math.wmflabs.org/w/index.php?title=Функция_Уолша&oldid=8073