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

Натуральная упорядоченная матрица Адамара (средняя матрица) порядка 16, которая представляет собой последовательность, упорядоченную для вывода матрицы Уолша (правая матрица).
Оба содержат 16 функций Уолша 16-го порядка в виде строк (и столбцов).
В правой матрице количество смен знака в строке является последовательным.

В математике , точнее в гармоническом анализе , функции Уолша образуют полный ортогональный набор функций , который можно использовать для представления любой дискретной функции — точно так же, как тригонометрические функции можно использовать для представления любой непрерывной функции в анализе Фурье . ^[1] Таким образом, их можно рассматривать как дискретный цифровой аналог непрерывной аналоговой системы тригонометрических функций на единичном интервале . Но в отличие от функций синуса и косинуса , которые являются непрерывными, функции Уолша являются кусочно- постоянными . Они принимают значения −1 и +1 только на подинтервалах, определяемых двоичными дробями .

Система функций Уолша известна как система Уолша . Это расширение системы ортогональных функций Радемахера . ^[2]

Функции Уолша, система Уолша, ряд Уолша ^[3] и быстрое преобразование Уолша-Адамара названы в честь американского математика Джозефа Л. Уолша . Они находят различные применения в физике и технике при анализе цифровых сигналов .

Исторически использовались различные нумерации функций Уолша; ни один из них не превосходит другого. В этой статье используется нумерация Уолша – Пэли .

Определение

Определим последовательность функций Уолша следующим образом. ${\displaystyle W_{k}:[0,1]\rightarrow \{-1,1\}}$ ${\displaystyle k\in \mathbb {N} }$

Для любого натурального числа k и действительного числа пусть ${\displaystyle x\in [0,1]}$

${\displaystyle k_{j}}$быть j -м битом в двоичном представлении k , начиная с младшего бита, и ${\displaystyle k_{0}}$

${\displaystyle x_{j}}$быть j- м битом в дробном двоичном представлении , начиная с самого старшего дробного бита. ${\displaystyle x}$ ${\displaystyle x_{1}}$

Тогда по определению

${\displaystyle W_{k}(x)=(-1)^{\sum _{j=0}^{\infty }k_{j}x_{j+1}}}$

В частности, всюду на интервале, поскольку все биты k равны нулю. ${\displaystyle W_{0}(x)=1}$

Обратите внимание, что это именно функция Радемахера r _m . Таким образом, система Радемахера является подсистемой системы Уолша. Более того, каждая функция Уолша является произведением функций Радемахера: ${\displaystyle W_{2^{m}}}$

${\displaystyle W_{k}(x)=\prod _{j=0}^{\infty }r_{j}(x)^{k_{j}}}$

Сравнение функций Уолша и тригонометрических функций

Функции Уолша и тригонометрические функции представляют собой системы, которые образуют полный ортонормированный набор функций, ортонормированный базис в гильбертовом пространстве функций, интегрируемых с квадратом на единичном интервале. Обе являются системами ограниченных функций , в отличие, скажем, от системы Хаара или системы Франклина. ${\displaystyle L^{2}[0,1]}$

И тригонометрическая система, и система Уолша допускают естественное расширение по периодичности от единичного интервала до действительной прямой . Кроме того, как анализ Фурье на единичном интервале ( ряд Фурье ), так и на реальной линии ( преобразование Фурье ) имеют свои цифровые аналоги, определенные через систему Уолша, ряд Уолша, аналогичный ряду Фурье, и преобразование Адамара , аналогичное преобразованию Фурье.

Характеристики

Система Уолша — абелева мультипликативная дискретная группа , изоморфная Понтрягину , двойственному к группе Кантора . Его идентичность равна , и каждый элемент имеет второй порядок (то есть самоинверсный). ${\displaystyle \{W_{k}\},k\in \mathbb {N} _{0}}$ ${\displaystyle \coprod _{n=0}^{\infty }\mathbb {Z} /2\mathbb {Z} }$ ${\displaystyle \prod _{n=0}^{\infty }\mathbb {Z} /2\mathbb {Z} }$ ${\displaystyle W_{0}}$

Система Уолша является ортонормированным базисом гильбертова пространства . Ортонормальность означает ${\displaystyle L^{2}[0,1]}$

${\displaystyle \int _{0}^{1}W_{k}(x)W_{l}(x)dx=\delta _{kl}}$,

и быть базисом означает, что если для каждого мы установим то ${\displaystyle f\in L^{2}[0,1]}$ ${\displaystyle f_{k}=\int _{0}^{1}f(x)W_{k}(x)dx}$

${\displaystyle \int _{0}^{1}(f(x)-\sum _{k=0}^{N}f_{k}W_{k}(x))^{2}dx\;\ {\xrightarrow[{N\rightarrow \infty }]{}}\;\ 0}$

Оказывается , для каждого ряд сходится к почти для каждого . ${\displaystyle f\in L^{2}[0,1]}$ ${\displaystyle \sum _{k=0}^{\infty }f_{k}W_{k}(x)}$ ${\displaystyle f(x)}$ ${\displaystyle x\in [0,1]}$

Система Уолша (в нумерации Уолша-Пэли) образует базис Шаудера в ,   . Обратите внимание, что в отличие от системы Хаара и, как и тригонометрической системы, этот базис не является безусловным , и система не является базисом Шаудера в . ${\displaystyle L^{p}[0,1]}$ ${\displaystyle 1<p<\infty }$ ${\displaystyle L^{1}[0,1]}$

Обобщения

Системы Уолша-Ферлегера

Пусть – компактная группа Кантора , наделенная мерой Хаара , и – ее дискретная группа характеров . Элементы легко отождествляются с функциями Уолша. Конечно, характеры определены на, а функции Уолша определены на единичном интервале, но поскольку между этими пространствами с мерой существует изоморфизм по модулю нуля , измеримые функции на них идентифицируются посредством изометрии . ${\displaystyle \mathbb {D} =\prod _{n=1}^{\infty }\mathbb {Z} /2\mathbb {Z} }$ ${\displaystyle {\hat {\mathbb {D} }}=\coprod _{n=1}^{\infty }\mathbb {Z} /2\mathbb {Z} }$ ${\displaystyle {\hat {\mathbb {D} }}}$ ${\displaystyle \mathbb {D} }$

Тогда базовая теория представлений предлагает следующее широкое обобщение понятия системы Уолша .

Для произвольного банахова пространства пусть – сильно непрерывное , равномерно ограниченное точное действие на X. Для каждого рассмотрим его собственное пространство . Тогда X — замкнутая линейная оболочка собственных пространств: . Предположим, что каждое собственное пространство одномерно , и выберите такой элемент , что . Тогда система , или та же система в нумерации персонажей Уолша-Пэли, называется обобщенной системой Уолша, связанной с действием . Классическая система Уолша становится частным случаем, а именно, для ${\displaystyle (X,||\cdot ||)}$ ${\displaystyle \{R_{t}\}_{t\in \mathbb {D} }\subset \operatorname {Aut} X}$ ${\displaystyle \mathbb {D} }$ ${\displaystyle \gamma \in {\hat {\mathbb {D} }}}$ ${\displaystyle X_{\gamma }=\{x\in X:R_{t}x=\gamma (t)x\}}$ ${\displaystyle X={\overline {\operatorname {Span} }}(X_{\gamma },\gamma \in {\hat {\mathbb {D} }})}$ ${\displaystyle w_{\gamma }\in X_{\gamma }}$ ${\displaystyle \|w_{\gamma }\|=1}$ ${\displaystyle \{w_{\gamma }\}_{\gamma \in {\hat {\mathbb {D} }}}}$ ${\displaystyle \{w_{k}\}_{k\in {\mathbb {N} }_{0}}}$ ${\displaystyle \{R_{t}\}_{t\in \mathbb {D} }}$

${\displaystyle R_{t}:x=\sum _{j=1}^{\infty }x_{j}2^{-j}\mapsto \sum _{j=1}^{\infty }(x_{j}\oplus t_{j})2^{-j}}$

где сложение по модулю 2. ${\displaystyle \oplus }$

В начале 1990-х годов Серж Ферлегер и Федор Сукочев показали, что в широком классе банаховых пространств (так называемых УМД- пространств ^[4] ) обобщенные системы Уолша обладают многими свойствами, подобными классическим: они образуют базис Шаудера ^[5] и равномерное конечномерное разложение ^[6] в пространстве, обладают свойством случайной безусловной сходимости. ^[7] Одним из важных примеров обобщенной системы Уолша является фермионная система Уолша в некоммутативных пространствах L ^p , связанных с гиперконечным фактором типа II .

Фермионная система Уолша

Фермионная система Уолша является некоммутативным или «квантовым» аналогом классической системы Уолша. В отличие от последнего, он состоит из операторов, а не функций. Тем не менее, обе системы обладают многими важными свойствами, например, обе образуют ортонормированный базис в соответствующем гильбертовом пространстве или базис Шаудера в соответствующих симметричных пространствах. Элементы фермионной системы Уолша называются операторами Уолша .

Термин «фермион» в названии системы объясняется тем, что обертывающее операторное пространство, так называемый гиперконечный фактор типа II , можно рассматривать как пространство наблюдаемых системы счетного бесконечного числа различных спиновых фермионов . Каждый оператор Радемахера действует только на одну конкретную координату фермиона, и там это матрица Паули . Его можно отождествить с наблюдаемым измерением спиновой компоненты этого фермиона вдоль одной из осей спинового пространства. Таким образом, оператор Уолша измеряет спин подмножества фермионов, каждый вдоль своей оси. ${\displaystyle {\mathcal {R}}}$ ${\displaystyle 1/2}$ ${\displaystyle \{x,y,z\}}$

система Виленкина

Зафиксируйте последовательность целых чисел с и пусть наделенную топологией произведения и нормализованной мерой Хаара. Дайте определение и . Каждый может быть связан с действительным числом ${\displaystyle \alpha =(\alpha _{1},\alpha _{2},...)}$ ${\displaystyle \alpha _{k}\geq 2,k=1,2,\dots }$ ${\displaystyle \mathbb {G} =\mathbb {G} _{\alpha }=\prod _{n=1}^{\infty }\mathbb {Z} /\alpha _{k}\mathbb {Z} }$ ${\displaystyle A_{0}=1}$ ${\displaystyle A_{k}=\alpha _{1}\alpha _{2}\dots \alpha _{k-1}}$ ${\displaystyle x\in \mathbb {G} }$

${\displaystyle \left|x\right|=\sum _{k=1}^{\infty }{\frac {x_{k}}{A_{k}}}\in \left[0,1\right].}$

Это соответствие представляет собой изоморфизм нулевого модуля между и единичным интервалом. Он также определяет норму, которая генерирует топологию . Ибо пусть где ${\displaystyle \mathbb {G} }$ ${\displaystyle \mathbb {G} }$ ${\displaystyle k=1,2,\dots }$ ${\displaystyle \rho _{k}:\mathbb {G} \to \mathbb {C} }$

${\displaystyle \rho _{k}(x)=\exp \left(i{\frac {2\pi x_{k}}{\alpha _{k}}}\right)=\cos \left({\frac {2\pi x_{k}}{\alpha _{k}}}\right)+i\sin \left({\frac {2\pi x_{k}}{\alpha _{k}}}\right).}$

Набор называется обобщенной системой Радемахера . Система Виленкина представляет собой группу ( комплекснозначных ) характеров , которые все являются конечными произведениями . Для каждого неотрицательного целого числа существует уникальная последовательность такая, что и ${\displaystyle \{\rho _{k}\}}$ ${\displaystyle {\hat {\mathbb {G} }}=\coprod _{n=1}^{\infty }\mathbb {Z} /\alpha _{k}\mathbb {Z} }$ ${\displaystyle \mathbb {G} }$ ${\displaystyle \{\rho _{k}\}}$ ${\displaystyle n}$ ${\displaystyle n_{0},n_{1},\dots }$ ${\displaystyle 0\leq n_{k}<\alpha _{k+1},k=0,1,2,\dots }$

${\displaystyle n=\sum _{k=0}^{\infty }n_{k}A_{k}.}$

Тогда где ${\displaystyle {\hat {\mathbb {G} }}={\chi _{n}|n=0,1,\dots }}$

${\displaystyle \chi _{n}=\sum _{k=0}^{\infty }\rho _{k+1}^{n_{k}}.}$

В частности, если , то является группой Кантора и является (действительнозначной) системой Уолша-Пэли. ${\displaystyle \alpha _{k}=2,k=1,2...}$ ${\displaystyle \mathbb {G} }$ ${\displaystyle {\hat {\mathbb {G} }}=\left\{\chi _{n}|n=0,1,\dots \right\}}$

Система Виленкина является полной ортонормированной системой на и образует базис Шаудера в ,  . ^[8] ${\displaystyle \mathbb {G} }$ ${\displaystyle L^{p}(\mathbb {G} ,\mathbb {C} )}$ ${\displaystyle 1<p<\infty }$

Нелинейные фазовые расширения

Разработаны нелинейные фазовые расширения дискретного преобразования Уолша-Адамара . Было показано, что нелинейные фазовые базисные функции с улучшенными свойствами взаимной корреляции значительно превосходят традиционные коды Уолша в связи множественного доступа с кодовым разделением каналов (CDMA). ^[9]

Приложения

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

Например, быстрое преобразование Уолша-Адамара (FWHT) может использоваться при анализе цифровых методов квази-Монте-Карло . В радиоастрономии функции Уолша могут помочь уменьшить влияние электрических перекрестных помех между сигналами антенн. Они также используются в пассивных ЖК- панелях в качестве сигналов двоичного управления X и Y, где автокорреляция между X и Y может быть сведена к минимуму для выключенных пикселей .

Смотрите также

• Дискретное преобразование Фурье
• Быстрое преобразование Фурье
• Гармонический анализ
• Ортогональные функции
• Матрица Уолша
• Функция четности

Примечания

1. Уолш 1923.
2. Прекрасно, 1949 год.
3. Шипп, Уэйд и Саймон 1990.
4. Писье 2011.
5. Сукочев и Ферлегер 1995.
6. Ферлегер и Сукочев 1996.
7. Ферлегер 1998.
8. Молодой 1976
9. А.Н. Акансу и Р. Полури, «Нелинейные фазовые ортогональные коды типа Уолша для связи CDMA с прямой последовательностью», IEEE Trans. Сигнальный процесс., вып. 55, нет. 7, стр. 3800–3806, июль 2007 г.

Рекомендации

• Ферлегер, Сергей В. (март 1998 г.). RUC-системы в некоммутативных симметричных пространствах (Технический отчет). МП-АРК-98-188.
• Ферлегер, Сергей В.; Сукочев, Федор А. (март 1996 г.). «О стягиваемости в точку линейных групп рефлексивных некоммутативных Lp-пространств». Математические труды Кембриджского философского общества . 119 (3): 545–560. Бибкод : 1996MPCPS.119..545F. дои : 10.1017/s0305004100074405. S2CID  119786894.
• Файн, Нью-Джерси (1949). «О функциях Уолша». Пер. амер. Математика. Соц . 65 (3): 372–414. дои : 10.1090/s0002-9947-1949-0032833-2 .
• Писье, Жиль (2011). Мартингалы в банаховых пространствах (в связи с типом и котипом). Курс IHP (PDF) .
• Шипп, Ференц; Уэйд, WR; Саймон, П. (1990). Серия Уолша. Введение в диадический гармонический анализ . Академик Киадо.
• Сукочев Федор А.; Ферлегер, Сергей В. (декабрь 1995 г.). «Гармонический анализ в (UMD)-пространствах: приложения к теории базисов». Математические заметки . 58 (6): 1315–1326. дои : 10.1007/bf02304891. S2CID  121256402.
• Уолш, Дж. Л. (1923). «Замкнутое множество нормальных ортогональных функций». амер. Дж. Математика. 45 (1): 5–24. дои : 10.2307/2387224. JSTOR  2387224. S2CID  6131655.
• Янг, В.-С. (1976). «Средняя сходимость обобщенных рядов Уолша-Фурье». Пер. амер. Математика. Соц. 218 : 311–320. дои : 10.1090/s0002-9947-1976-0394022-8 . JSTOR  1997441. S2CID  53755959.

Внешние ссылки

• «Функции Уолша». Математический мир .

• «Функции Уолша». Энциклопедия математики .

• «Система Уолша». Энциклопедия математики .

• «Функции Уолша». Стэнфордский исследовательский проект .