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

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

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

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

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

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

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

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

Щодо моменту функції Волша можна розділити на парні і непарні. Вони позначаються як та відповідно. Ці функції аналогічні тригонометричним синусам і косинусам. Зв'язок між цими функціями виражається наступним чином:

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

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

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

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

Приклад: Номер за АдамаромДвійкова формаПерестановка бітПеретворення з коду ГреяНомер за Волшем00000000101101132100101131111102

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

Властивості

1. Ортогональність Скалярний добуток двох різних функцій Волша дорівнює нулю:

Приклад:

Припустимо, що тоді,

2. Мультиплікативність Добуток двох функцій Волша дає функцію Волша.

де  — додавання за модулем 2 номерів у двійковій системі.

Приклад:

Припустимо, що тоді,

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

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

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

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

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

Узагальнений ряд Фур'є представляється формулою:

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

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

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

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

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

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

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

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

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

Примітки

Джерела