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

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

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

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

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

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

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

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

Визначення

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

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

$cal(k,\theta )=wal(2k,\theta )$

$sak(k,\theta )=wal(2k-1,\theta )$

Формування

Існує кілька способів формування. Розглянемо один з них, найбільш наочних: Матриця Адамара може бути сформована рекурсивним методом за допомогою побудови блокових матриць за такою загальною формулою:

$H_{2^n}=\left[\begin{array}{cc}{H}_{2^{n-1}}& H_{2^{n-1}}\\ H_{2^{n-1}}& -H_{2^{n-1}}\end{array}\right]$

Так може бути сформована матриця Адамара довжини $2^n$:

$H_1=\left[\begin{array}{c}1\end{array}\right]$

$H_2=\left[\begin{array}{cc}1& 1\\ 1& -1\end{array}\right]$

$H_4=\left[\begin{array}{cccc}1& 1& 1& 1\\ 1& -1& 1& -1\\ 1& 1& -1& -1\\ 1& -1& -1& 1\end{array}\right]$

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

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

Приклад:

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

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

$W_4=\left[\begin{array}{cccc}1& 1& 1& 1\\ 1& 1& -1& -1\\ 1& -1& -1& 1\\ 1& -1& 1& -1\end{array}\right]$

Властивості

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

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

$\underset{0}{\overset{1}{\int }}wal(n,\theta )\cdot wal(k,\theta )d\theta =0\text{if }k\ne n$

Приклад:

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

$\underset{0}{\overset{1}{\int }}wal(1,\theta )\cdot wal(3,\theta )d\theta$$=\underset{0}{\overset{1/4}{\int }}{1}^{2}d\theta +\underset{1/4}{\overset{1/2}{\int }}1\cdot (-1)d\theta +\underset{1/2}{\overset{3/4}{\int }}(-1)\cdot 1d\theta +\underset{3/4}{\overset{1}{\int }}(-1{)}^{2}d\theta =0$

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

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

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

Приклад:

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

$n\oplus k=01_2\oplus 11_2=10_2=2$

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

$\begin{array}{ccccc}& & & & n\\ 1& 1& -1& -1& wal(1,\theta )\\ 1& -1& 1& -1& wal(3,\theta )\\ 1& -1& -1& 1& wal(2,\theta )\end{array}$

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

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

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

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

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

Узагальнений ряд Фур'є представляється формулою:$S(t)=\sum _{i=0}^{\mathrm{\infty }}{c}_i\cdot u_i(t)$

де $u_i$ — це одна з базисних функцій, $c_i$- коефіцієнт.

Розклад сигналу по функціям Уолша має вигляд:

$S(t)=\sum _{k=0}^{\mathrm{\infty }}{c}_k\cdot wal(k,t/T)$

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

$S(n)=\sum _{k=0}^{\mathrm{\infty }}{c}_k\cdot wal(k,n)$

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

$c_k=\frac{1}{T}\underset{0}{\overset{T}{\int }}S(t)\cdot wal(k,t/T)dt$

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

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

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

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

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

Див. також

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