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

Натуральная упорядоченная матрица Адамара (средняя матрица) порядка 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-х годов Серж Ферлегер и Федор Сукочев показали, что в широком классе банаховых пространств (так называемых пространствах UMD ^[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. AN Akansu и R. Poluri, «Нелинейные фазовые ортогональные коды типа Уолша для CDMA-коммуникаций с прямой последовательностью», IEEE Trans. Signal Process., т. 55, № 7, стр. 3800–3806, июль 2007 г.

Ссылки

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

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

• "Функции Уолша". MathWorld .

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

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

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