Ортогональні швидкі хвильові перетворення

 

За останні роки широкого розвитку набули методи, які базуються на дискретних хвильових перетвореннях (ДХП). Ці перетворення також називаються вейвлетними (wavelets) або хвильовими [4,9]. Використання ДХП забезпечує ефективне вирішення багатьох існуючих задач обробки сигналів. Оскільки швидкі алгоритми ДХП (ШХП) потребують виконання тільки арифметичних операцій, де – довжина перетворення, то їх доцільно використовувати при обмежених апаратних або обчислювальних ресурсах. Крім того, ДХП добре представляють нестаціонарні сигнали, а також локально стаціонарні сигнали, тому ДХП особливо часто використовуються в задачах кодування (стиску) даних та задачах фільтрації.

 

Рис. 4.12 Загальний вигляд одного етапу ДХП

 

Нехай , вхідний дискретний сигнал. Загальний вигляд одного етапу прямого (аналіз) та оберненого (синтез) дискретного хвильового перетворення (ДХП) графічно показаний на рис.4.12 [].

Тут , , , імпульсні характеристики СІХ–фільтрів, а квадрати, де вони вказані, відповідають операції згортки

 

. (4.23)

 

Вихідний сигнал запізнюється на відліків стосовно вхідного сигналу . Оператор Ї2 відповідає операції прорідження сигналу – із нього вилучається кожен другий відлік, починаючи з першого, а оператор ­2 відповідає операції розширення сигналу – після кожного відліку вставляється нульовий відлік, за рахунок чого загальна кількість відліків збільшується в два рази.

 

Рис.4.13 Пірамідальна схема продовження

Класичною схемою продовження одноетапного ДХП є пірамідальна (рис.4.13.), що відповідає змішаному частотно–часовому поданню сигналу. Якщо ,то пірамідальна схема складається з послідовних одноетапних –точкових ДХП, де при прямому та при оберненому перетвореннях. При цьому в ортогональних фільтрах з скінченою імпульсною характеристикою (СІХ-фільтри) імпульсні характеристики мають однакову довжину, позначимо її літерою [4].

Приведемо оцінку обчислювальних затрат такого алгоритму ШХП. Нехай і відповідно задають кількість множень та додавань, що використовуються в –точковому –етапному прямому ДХП. Обчислення одного відліку згортки (1) при –точковій імпульсній характеристиці потребує множень та додавань.. Відомо, що в загальному випадку ортогональних ШХП, обчислювальні затрати добре оцінюються виразами

 

;

 

Тут враховано те, що операція прорідження вилучає з вихідних послідовностей відліків, відповідно обчислення яких опускається. Таким чином, на один відлік вихідного сигналу потрібно множень і додавань або сумарно арифметичних операцій.