Меню Главная Случайная статья Настройки Функция Уолша Материал из https://ru.wikipedia.org Функциями Уолша называется семейство функций, образующих ортогональную систему, принимающих значения только +1 и 1 на всей области определения. В принципе, функции Уолша могут быть представлены в непрерывной форме, но чаще их определяют как дискретные последовательности из ${\displaystyle 2^{n}}$ элементов. Группа из ${\displaystyle 2^{n}}$ функций Уолша образует матрицу Адамара. Функции Уолша получили широкое распространение в радиосвязи, где с их помощью осуществляется кодовое разделение каналов (CDMA), например, в таких стандартах сотовой связи, как IS-95, CDMA2000 или UMTS. Система функций Уолша является ортонормированным базисом и, как следствие, позволяет раскладывать сигналы произвольной формы в обобщённый ряд Фурье. Обобщением функций Уолша на случай более чем двух значений являются функции Виленкина — Крестенсона. Содержание 1 Обозначение 2 Формирование 2.1 Пример 3 Свойства 3.1 1. Ортогональность 3.1.1 Пример 3.2 2. Мультипликативность 3.2.1 Пример 4 Преобразование Уолша — Адамара 5 Литература 6 См. также 7 Примечания Обозначение Пусть функция Уолша определена на интервале [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}},}$ Каждая строка матрицы Адамара и является функцией Уолша. В данном случае функции упорядочены по Адамару. Номер функции по Уолшу вычисляется из номера функции по Адамару путём перестановки битов в двоичной записи номера в обратном порядке с последующим преобразованием результата из кода Грея. Номер по Уолшу Двоичная форма Преобразование из кода Грея Перестановка бит Номер по Адамару 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 В итоге получается матрица Уолша, в которой функции упорядочены по Уолшу: ${\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. См. также Базис Хаара Матрица Адамара Коэффициент Уолша Ортонормированная система Ортогональный базис Ряд Фурье Примечания БЫСТРОЕ ПРЕОБРАЗОВАНИЕ УОЛША. В. Н. Малозёмов Архивная копия от 4 марта 2016 на Wayback Machine. Fast Walsh Transform Архивная копия от 27 марта 2014 на Wayback Machine. Romanuke V. V. ON THE POINT OF GENERALIZING THE WALSH FUNCTIONS TO SURFACES Архивная копия от 16 апреля 2016 на Wayback Machine. Romanuke V. V. GENERALIZATION OF THE EIGHT KNOWN ORTHONORMAL BASES OF BINARY FUNCTIONS TO SURFACES Архивная копия от 5 октября 2016 на Wayback Machine. Romanuke V. V. EQUIDISTANTLY DISCRETE ON THE ARGUMENT AXIS FUNCTIONS AND THEIR REPRESENTATION IN THE ORTHONORMAL BASES SERIES Архивная копия от 10 апреля 2016 на Wayback Machine.