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

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

15.04.2021


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

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

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

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

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

Обозначение

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

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

cal ⁡ ( k , θ ) = wal ⁡ ( 2 k , θ ) , {displaystyle operatorname {cal} (k, heta )=operatorname {wal} (2k, heta ),} sal ⁡ ( k , θ ) = wal ⁡ ( 2 k − 1 , θ ) . {displaystyle operatorname {sal} (k, heta )=operatorname {wal} (2k-1, heta ).}

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

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

H 2 n = [ H 2 n − 1 H 2 n − 1 H 2 n − 1 − H 2 n − 1 ] . {displaystyle H_{2^{n}}={egin{bmatrix}H_{2^{n-1}}&H_{2^{n-1}}H_{2^{n-1}}&-H_{2^{n-1}}end{bmatrix}}.}

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

H 1 = [ 1 ] , {displaystyle H_{1}={egin{bmatrix}1end{bmatrix}},} H 2 = [ 1 1 1 − 1 ] , {displaystyle H_{2}={egin{bmatrix}1&11&-1end{bmatrix}},} H 4 = [ 1 1 1 1 1 − 1 1 − 1 1 1 − 1 − 1 1 − 1 − 1 1 ] , {displaystyle H_{4}={egin{bmatrix}1&1&1&11&-1&1&-11&1&-1&-11&-1&-1&1end{bmatrix}},} H 8 = [ 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 ] , {displaystyle H_{8}={egin{bmatrix}1&1&1&1&1&1&1&11&-1&1&-1&1&-1&1&-11&1&-1&-1&1&1&-1&-11&-1&-1&1&1&-1&-1&11&1&1&1&-1&-1&-1&-11&-1&1&-1&-1&1&-1&11&1&-1&-1&-1&-1&1&11&-1&-1&1&-1&1&1&-1end{bmatrix}},}

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

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

Пример

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

W 8 = [ 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 ] . {displaystyle W_{8}={egin{bmatrix}1&1&1&1&1&1&1&11&1&1&1&-1&-1&-1&-11&1&-1&-1&-1&-1&1&11&1&-1&-1&1&1&-1&-11&-1&-1&1&1&-1&-1&11&-1&-1&1&-1&1&1&-11&-1&1&-1&-1&1&-1&11&-1&1&-1&1&-1&1&-1end{bmatrix}}.}

Свойства

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

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

∫ 0 1 wal ⁡ ( n , θ ) ⋅ wal ⁡ ( k , θ ) d θ = 0 при  k ≠ n . {displaystyle int limits _{0}^{1}operatorname {wal} (n, heta )cdot operatorname {wal} (k, heta ),d heta =0qquad { ext{при }}k eq n.}

Пример

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

∫ 0 1 wal ⁡ ( 1 , θ ) ⋅ wal ⁡ ( 3 , θ ) d θ = {displaystyle int limits _{0}^{1}operatorname {wal} (1, heta )cdot operatorname {wal} (3, heta ),d heta =} = ∫ 0 1 / 4 1 2 d θ + ∫ 1 / 4 1 / 2 1 ⋅ ( − 1 ) d θ + ∫ 1 / 2 3 / 4 ( − 1 ) ⋅ 1 d θ + ∫ 3 / 4 1 ( − 1 ) 2 d θ = 0. {displaystyle =int limits _{0}^{1/4}1^{2},d heta +int limits _{1/4}^{1/2}1cdot (-1),d heta +int limits _{1/2}^{3/4}(-1)cdot 1,d heta +int limits _{3/4}^{1}(-1)^{2},d heta =0.}

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

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

wal ⁡ ( n , θ ) ⋅ wal ⁡ ( k , θ ) = wal ⁡ ( i , θ ) , {displaystyle operatorname {wal} (n, heta )cdot operatorname {wal} (k, heta )=operatorname {wal} (i, heta ),}

где i = n ⊕ k {displaystyle i=noplus k} — сложение по модулю 2 номеров в двоичной системе.

Пример

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

n ⊕ k = 01 2 ⊕ 11 2 = 10 2 = 2. {displaystyle noplus k=01_{2}oplus 11_{2}=10_{2}=2.}

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

n 1 1 − 1 − 1 wal ⁡ ( 1 , θ ) 1 − 1 1 − 1 wal ⁡ ( 3 , θ ) 1 − 1 − 1 1 wal ⁡ ( 2 , θ ) {displaystyle {egin{array}{|c|c|c|c||c|}&&&&nhline 1&1&-1&-1&operatorname {wal} (1, heta )1&-1&1&-1&operatorname {wal} (3, heta )hline 1&-1&-1&1&operatorname {wal} (2, heta )end{array}}}

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

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

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

S ( t ) = ∑ i = 0 ∞ c i ⋅ u i ( t ) , {displaystyle S(t)=sum _{i=0}^{infty }c_{i}cdot u_{i}(t),}

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

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

S ( t ) = ∑ k = 0 ∞ c k ⋅ wal ⁡ ( k , t / T ) . {displaystyle S(t)=sum _{k=0}^{infty }c_{k}cdot operatorname {wal} (k,t/T).}

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

S ( n ) = ∑ k = 0 ∞ c k ⋅ wal ⁡ ( k , n ) . {displaystyle S(n)=sum _{k=0}^{infty }c_{k}cdot operatorname {wal} (k,n).}

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

c k = 1 T ∫ 0 T S ( t ) ⋅ wal ⁡ ( k , t / T ) d t . {displaystyle c_{k}={frac {1}{T}}int limits _{0}^{T}S(t)cdot operatorname {wal} (k,t/T),dt.}

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

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