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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Графік перших чотирьох функцій Уолша

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

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

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

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

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

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

Визначення[ред.ред. код]

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

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

Формування[ред.ред. код]

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

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

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

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

Приклад:

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

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

Властивості[ред.ред. код]

1. Ортогональність[ред.ред. код]

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

Приклад:

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

2. Мультиплікативність[ред.ред. код]

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

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

Приклад:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Використання[ред.ред. код]

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

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

Див. також[ред.ред. код]

Джерела[ред.ред. код]

  1. Walsh, Joseph (1923). "A closed set of normal orthogonal functions" (Англійська). 
  2. Fine, N.J (1949). "On the Walsh functions" (Англійська). 
  3. Баскаков С. И (2005). "Радиотехнические цепи и сигналы". 
  4. Голубов Б. И., Ефимов А. В., Скворцов В. А. (1987). "Ряды и преобразования Уолша: теория и применения". 
  5. "Преобразования Фурье, Уолша, Хаара и их применение в управлении, связи и других областях". 1989. 
  6. Romance V.V. ON THE POINT OF GENERALIZING THE WALSH FUNCTIONS TO SURFACES. 
  7. Romance V.V. EQUIDISTANTLY DISCRETE ON THE ARGUMENT AXIS FUNCTIONS AND THEIR REPRESENTATION IN THE ORTHONORMAL BASES SERIES.