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

Функції Уолша це сімейство функцій, які утворюють ортогональну систему, що приймають значення тільки 1 та -1 на всій області визначення.

Графік перших чотирьох функцій Уолша

В математиці, більш конкретно в гармонійному аналізі, функції Уолша утворюють ортонормований базис, який може бути викоритсаний для подання будь-якої дискретної функції, так само, як тригонометричні функції можуть бути використані для подання будь-якої неперервної функції в аналізі Фур'є^[1]. Таким чином, їх можна розглядати як дискретний, цифровий аналог безперервної, аналогової системи тригонометричних функцій на одиничному інтервалі.

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

В принципі, функції Уолша можуть бути представлені в безперервній формі, але частіше їх визначають як дискретні послідовності з ${\displaystyle 2^{n}}$ елементів Група з ${\displaystyle 2^{n}}$ елементів утворює матрицю Адамара.

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

Історично склалося, що були використані різні нумерації функцій Уолша. Жодна з них не має особливих плюсів над іншою. Далі всі викладки будуть приведені використовуючи нумерацію Уолша-Пелі.

Визначення

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

Щодо моменту ${\displaystyle \theta =0}$ функції Уолша можна розділити на парні і непарні. Вони позначаються як ${\displaystyle cal(k,\theta )}$ та ${\displaystyle sal(k,\theta )}$ відповідно. Ці функції аналогічні тригонометричним синусам і косинусам. Зв'язок між цими функціями виражається наступним чином:

${\displaystyle cal(k,\theta )=wal(2k,\theta )}$

${\displaystyle sak(k,\theta )=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}}}$

Кожен рядок матриці Адамара і є функцією Уолша.

В даному випадку функції впорядковані по Адамару. Номер функції по Уолшу обчислюється з номера функції по Адамара шляхом перестановки біт в двійковій запису номера в зворотному порядку з подальшим перетворенням результату з коду Грея:

Приклад:

Номер по Адамару	Двійкова форма	Перестановка біт	Перетворення з коду Грея	Номер по Уолшу
0	00	00	00	0
1	01	10	11	3
2	10	01	01	1
3	11	11	10	2

У підсумку виходить матриця Уолша, в якій функції впорядковані по Уолшу:

${\displaystyle W_{4}={\begin{bmatrix}1&1&1&1\\1&1&-1&-1\\1&-1&-1&1\\1&-1&1&-1\end{bmatrix}}}$

Властивості

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

Скалярний добуток двох різних функцій Уолша дорівнює нулю:

${\displaystyle {\int \limits _{0}^{1}wal(n,\theta )\cdot wal(k,\theta )d\theta =0}\qquad {{\mbox{if }}k\neq n}}$

Приклад:

Припустимо, що ${\displaystyle n=1,k=3}$ тоді,

${\displaystyle \int \limits _{0}^{1}wal(1,\theta )\cdot 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 1d\theta +\int \limits _{3/4}^{1}(-1)^{2}d\theta =0}$

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

Добуток двох функцій Уолша дає функцію Уолша.

${\displaystyle wal(n,\theta )\cdot wal(k,\theta )=wal(i,\theta )}$ де ${\displaystyle i=n\oplus k}$ — додавання по модулю 2 номерів у двійковій системі.

Приклад:

Припустимо, що ${\displaystyle 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&wal(1,\theta )\\1&-1&1&-1&wal(3,\theta )\\\hline 1&-1&-1&1&wal(2,\theta )\\\end{array}}}$

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

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

Обидві системи допускають природне продовження по періодичності з одиничного інтервалу дійсної прямої ${\displaystyle \mathbb {R} }$. Крім того, як аналіз Фур'є на одиничному інтервалі (ряд Фур'є) і на дійсній прямій (перетворення Фур'є) мають свої цифрові аналоги, визначеної за допомогою системи Уолша, ряд Уолша аналогічний ряду Фур'є, і перетворення Адамара аналогічне перетворенню Фур'є

Перетворення Уолша — Адамара

Докладніше: Перетворення Адамара

Є окремим випадком узагальненого перетворення Фур'є, в якому базисом виступає система функцій Уолша.

Узагальнений ряд Фур'є представляється формулою:${\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 wal(k,t/T)}}$

У дискретній формі формула запишеться наступним чином:

${\displaystyle S(n)=\sum _{k=0}^{\infty }{c_{k}\cdot wal(k,n)}}$

визначити коефіцієнт ${\displaystyle c_{i}}$ можна, здійснивши скалярний добуток розкладуваного сигналу на відповідну базисну функцію Уолша:

${\displaystyle c_{k}={\frac {1}{T}}\int \limits _{0}^{T}{S(t)\cdot wal(k,t/T)}dt}$

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

Існує також швидке перетворення Уолша^[3]. Воно є в значній мірі більш ефективним, ніж перетворення Уолша — Адамара^[4]. Крім того, для окремого випадку з двома змінними функції Уолша узагальнені як поверхні^[5] . Також існують вісім аналогічних функцій Уолша базисів ортогональних бінарних функцій^[6] , що відрізняються нерегулярної структурою, які також узагальнені на випадок функцій двох змінних. Для кожного з восьми базисів доведено уявлення «східчастих» функцій у вигляді кінцевої суми бінарних функцій, що зважуються з відповідними коефіцієнтами^[7].

Використання

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

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

Див. також

• Матриці Адамара
• Коефіцієнт Уолша
• Ортонормована система
• Перетворення Фур'є
• Ряд Фур'є
• Ортогональний базис