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

Эта статья находится на начальном уровне проработки, в одной из её версий выборочно используется текст из источника, распространяемого под свободной лицензией
Материал из энциклопедии Руниверсалис
Графики первых четырёх функций Уолша

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

Функции Уолша могут быть определены как функции непрерывного (вещественного) аргумента, но чаще их определяют как функции дискретного аргумента — последовательности из [math]\displaystyle{ 2^n }[/math] элементов. Матрица [math]\displaystyle{ 2^n\times2^n }[/math], каждая строка которой является функцией Уолша является матрицей Адамара.

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

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

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

История описания и применения

Джозеф Леонард Уолш

Функции Уолша известны с 1923 года[1], когда американский математик Джозеф Леонард Уолш (1895—1973) опубликовал статью «A closed set of normal orthogonal functions» (с англ. — «Замкнутый набор нормальных ортогональных функций») в «Американском математическом журнале»[2].

К моменту написания статьи о функциях Уолш уже получил докторскую степень в Гарвардском университете (1920) и с 1921 года там преподавал. Изначально статья об ортогональных функциях не считалась особо значимой. Но со временем описанные в статье функции нашли своё практическое применение, помогли Уолшу в продвижении по работе и получили название по его фамилии[3].

Работы о применении функций Уолша в системах связи, для решения различных инженерных проблем публиковал в 1960-х годах Х.Ф. Хармут (англ. H. F. Harmuth)[4][1]. В СССР о функциях писали Л. А. Балашов и А. И. Рубинштейн[5]. В середине 1970-х математик Теодор Ривлин[en] оценил функции Уолша как ценный математический инструмент для различных прикладных наук, в первую очередь для инженерии коммуникаций[6].

Обозначение

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

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

[math]\displaystyle{ \operatorname{cal}(k,\theta) = \operatorname{wal}(2k,\theta), }[/math]
[math]\displaystyle{ \operatorname{sal}(k,\theta) = \operatorname{wal}(2k-1,\theta). }[/math]

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

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

Формирование через двоичную запись аргумента

Аргумент [math]\displaystyle{ \theta }[/math] и номер [math]\displaystyle{ k }[/math] функции Уолша могут быть записаны в двоичной записи

[math]\displaystyle{ \theta=2^{-n}\sum_{j=0}^{n-1} \theta_j\cdot 2^j,\quad \theta_j\in\{0,1\}. }[/math]
[math]\displaystyle{ k=\sum_{j=0}^{n-1} k_j\cdot 2^j,\quad k_j\in\{0,1\}. }[/math]

Функции Уолша в нумерации Адамара определяются как

[math]\displaystyle{ \operatorname{had}(k,\theta)=\prod_{j=0}^{n-1} (-1)^{k_j\theta_j}=(-1)^{\sum_{j=0}^{n-1} k_j\theta_j}. }[/math]

Формирование через матрицы Адамара

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

[math]\displaystyle{ 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]\displaystyle{ 2^n }[/math]:

[math]\displaystyle{ H_1 = \begin{bmatrix} 1 \end{bmatrix}, }[/math]
[math]\displaystyle{ H_2 = \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}, }[/math]
[math]\displaystyle{ H_4 = \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 \end{bmatrix}, }[/math]
[math]\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}, }[/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]\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}. }[/math]

Свойства

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

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

[math]\displaystyle{ \operatorname{wal}(m, \theta) \cdot \operatorname{wal}(k, \theta) = \operatorname{wal}(i, \theta), }[/math]

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

[math]\displaystyle{ \operatorname{wal}^2(m, \theta)= \operatorname{wal}(0, \theta)=1. }[/math]

Таким образом, [math]\displaystyle{ 2^n }[/math] функций Уолша образуют коммутативную группу относительно умножения изоморфную [math]\displaystyle{ \mathbb{Z}^n(2) }[/math][1], с единичным элементом [math]\displaystyle{ \operatorname{wal}(0, \theta). }[/math]

Пример

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

[math]\displaystyle{ m \oplus k = 01_2 \oplus 11_2 = 10_2 = 2. }[/math]

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

[math]\displaystyle{ \begin{array}{|c|c|c|c||c|} 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]


2. Ортонормированность

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

[math]\displaystyle{ \int\limits_0^1 \operatorname{wal}(m, \theta) \cdot \operatorname{wal}(k, \theta) \,d\theta=\int\limits_0^1 \operatorname{wal}(m\oplus k, \theta) \,d\theta =\left\{\begin{array}{cc}1 \qquad \text{при } k=m,\\0 \qquad \text{при } k \neq m.\end{array}\right. }[/math]

Пример

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

[math]\displaystyle{ \int\limits_0^1 \operatorname{wal}(1, \theta) \cdot \operatorname{wal}(3,\theta) \,d\theta = }[/math]
[math]\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. }[/math]


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

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

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

[math]\displaystyle{ S(t) = \sum_{i=0}^\infty c_i \cdot u_i(t), }[/math]

где [math]\displaystyle{ u_i }[/math] это одна из базисных функций, а [math]\displaystyle{ c_i }[/math] — коэффициент.

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

[math]\displaystyle{ S(t) = \sum_{k=0}^\infty c_k \cdot \operatorname{wal}(k, t/T). }[/math]

В дискретной форме (при [math]\displaystyle{ t=0,\dots,2^n-1 }[/math]) формула запишется следующим образом:

[math]\displaystyle{ S(t) = \sum_{k=0}^{2^n-1} c_k \cdot \operatorname{wal}(k, t/2^n). }[/math]

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

[math]\displaystyle{ c_k = \frac{1}{T} \int\limits_0^T S(t) \cdot \operatorname{wal}(k, t/T) \,dt. }[/math]

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

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

Примечания

  1. ↑ 1,0 1,1 Никитин, 2003, с. 49.
  2. ↑ Walsh, 1923.
  3. ↑ MacTutor History of Mathematics Archive, 2023.
  4. ↑ См. Хармут Х.Ф. Передача информации ортогональными функциями. Пер. с англ. — М.: Связь, 1975. — 272 с. и Хармут Х.Ф. Теория севентного анализа. Пер. с англ. — М.: Мир, 1980. — 576 с.
  5. ↑ Балашов Л. А. , Рубинштейн А. И. Ряды по системе Уолша и их обобщения. — Итоги науки. Сер. Математика. Мат. анал. 1970, ВИНИТИ, М., 1971, 147–202; J. Soviet Math., 1:6 (1973), 727–763
  6. ↑ Marden M. Joseph L. Walsh in Memoriam (англ.) // Bulletin of the American Mathematical Society. — 1975. — January (vol. 81, no. 1). — P. 49.
  7. ↑ БЫСТРОЕ ПРЕОБРАЗОВАНИЕ УОЛША. В. Н. Малозёмов Архивная копия от 4 марта 2016 на Wayback Machine.
  8. ↑ Fast Walsh Transform Архивная копия от 27 марта 2014 на Wayback Machine.
  9. ↑ Romanuke V. V. ON THE POINT OF GENERALIZING THE WALSH FUNCTIONS TO SURFACES Архивная копия от 16 апреля 2016 на Wayback Machine.
  10. ↑ Romanuke V. V. GENERALIZATION OF THE EIGHT KNOWN ORTHONORMAL BASES OF BINARY FUNCTIONS TO SURFACES Архивная копия от 5 октября 2016 на Wayback Machine.
  11. ↑ Romanuke V. V. EQUIDISTANTLY DISCRETE ON THE ARGUMENT AXIS FUNCTIONS AND THEIR REPRESENTATION IN THE ORTHONORMAL BASES SERIES Архивная копия от 10 апреля 2016 на Wayback Machine.

Литература

  • Баскаков С. И. Радиотехнические цепи и сигналы. — М.: Высшая школа, 2005. — ISBN 5-06-003843-2.
  • Голубов Б. И., Ефимов А. В., Скворцов В. А. Ряды и преобразования Уолша: теория и применения. — М.: Наука, 1987.
  • Залманзон Л. А. Преобразования Фурье, Уолша, Хаара и их применение в управлении, связи и других областях. — М.: Наука, 1989. — ISBN 5-02-014094-5.
  • Никитин Г.И. Применение функций Уолша в сотовых системах связи с кодовым разделением каналов: Учеб. пособие. — Санкт-Петербург: СПбГУАП, 2003. — 86 с.
  • Walsh J.L. A closed set of normal orthogonal functions (англ.) // American Journal of Mathematics. — 1923. — Vol. 45. — P. 5—24.
  • O'Connor, John J.; Robertson, Edmund F. Joseph L. Walsh (англ.). MacTutor History of Mathematics Archive. University of St Andrews. Дата обращения: 19 июля 2023.

См. также

Источник — https://xn--h1ajim.xn--p1ai/index.php?title=Функция_Уолша&oldid=20561578