Гармонический анализ на базе дискретного преобразования Виленкина-Крестенсона

Открытие в 1965 г. быстрого преобразования Фурье явилось мощным стимулом для развития дискретного гармонического анализа [36, 15, 5]. Появление цифровой электронной вычислительной техники способствовало проникновению в классический дискретный гармонический анализ других ортогональных преобразований, таких как дискретное преобразование Уолша, дискретное преобразование Хаара, дискретное косинусное, пилообразное и другие преобразования [4, 31, 10, 9, 12]. В их числе стоит и дискретное преобразование Виленкина-Крестенсона [30, 10].

В последние полтора десятилетия бурно развивается (в основном, за рубежом) новый аппарат обработки сигналов — вейвлеты (всплески) [34, 45, 40]. Отличительной чертой вейвлетов является их способность одновременно характеризовать как частотные, так и временные особенности сигнала. Отправной точкой лавинообразного развития вейвлетной теории принято считать работы И. Добеши [37, 38] (перевод последней книги на русский язык, с некоторыми исправлениями и дополнениями, совсем недавно вышел в свет под редакцией А. П. Петухова [11]). Успехи этого нового направления чистой и прикладной математики столь существенны, что говорят о «вейвлетной революции». Из огромного количества публикаций по этой теме следует выделить монографии [33, 44, 27, 8] и русскоязычные статьи [29, 28, 26, 3, 13].

Одной из последних наработок вейвлетной теории являются вейвлет-пакеты — наборы из нескольких вейвлетных базисов. Вейвлет-пакеты позволяют получать детальные частотно-временные портреты сигналов, варьируя разрешение (масштабность) по времени и по частоте. В этом смысле анализ сигналов с помощью вейвлет-пакетов можно рассматривать как мощное дополнение к традиционному анализу Фурье. С другой стороны, использование сразу всех базисов из вейвлет-пакета приводит к крайне избыточному представлению сигнала. Это обеспечивает возможность выбирать из пакета ортогональный базис, адаптированный к определенному классу сигналов или даже к отдельному сигналу [34, 3−5, 45].

В последние годы был разработан новый подход к быстрому преобразованию Фурье, при котором результаты промежуточных вычислений интерпретируются как коэффициенты разложений по некоторым ортогональным базисам [21, 20]. При длине периода ТУ, равной 2% в пространстве дискретных периодических сигналов построены рекуррентные последовательности ортогональных базисов, имеющих блочную структуру. В каждом блоке сигналы различаются лишь сдвигом аргумента. Из блоков, принадлежащих разным базисам рекуррентной последовательности, формируются обобщенные вейвлетные базисы. Это значительно расширяет возможности цифровой обработки сигналов. В работе [22] с аналогичных позиций проанализировано дискретное преобразование Уолша.

В диссертационной работе рассматривается более общая по сравнению с [22] ситуация, когда длина периода N равна пв. В пространстве дискретных Лт-периодических сигналов строятся несколько рекуррентных последовательностей ортогональных базисов. Финальным базисом во всех последовательностях является дискретный базис Виленкина-Крестенсона. Соответствующие обобщения оказались возможными благодаря тому, что удалось разобраться с источником рекуррентных соотношений для базисов. Если в [21, 20, 22] при N = 2е такие соотношения, по существу, предъявлялись, то теперь они выводятся на основе различных факторизаций матрицы Виленкина-Крестенсона порядка N — Эффективные расчетные формулы получаются путем использования индексной техники, когда при умножении разреженной матрицы на вектор убираются все операции с нулевыми элементами матрицы. После построения последовательности ортогональных базисов естественным образом формируется обобщенный вейвлет-пакет.

Большинство из описанных выше ортогональных преобразований используется с целью получения спектра сигнала для его дальнейшей цифровой обработки или анализа [12, 2]. Для решения этих задач часто требуется умение устанавливать связь между спектрами исходных сигналов и спектрами их сдвига, свертки и корреляции. В случае дискретных преобразований Фурье, Уолша, Виленкина-Крестенсона это не вызывает затруднений (см., например, [30]). В общем случае этот вопрос рассмотрен в [1, 14]. Полученные в этих работах результаты отражают свойства дискретных ортогональных преобразований, являющихся собственными по отношению к некоторому оператору сдвига. В отличие от классических ортогональных преобразований, вейвлет-преобразования не являются собственными по отношению к традиционным операторам сдвига, и поэтому результаты работ [1, 14] к ним неприменимы. Однако вопрос о спектрах сигналов в вейвлетных базисах остается актуальным. В частном случае (для базисов Хаара) этот вопрос изучался в [17. 18, 42].

Целью диссертационной работы является:

1) Построить ортогональные вейвлетные базисы в пространстве дискретных N-периодических сигналов при N = п8.

2) Исследовать спектральные свойства дискретных сигналов в этих базисах.

3) Установить более тесную связь между дискретным гармоническим анализом и вейвлетной теорией.

Приведем краткий обзор содержания диссертации. Работа состоит из двух глав, разбитых на тринадцать параграфов, двух таблиц, двух рисунков и списка литературы. Порядок ссылок на теоремы и формулы определяется двумя числами: первое число указывает номер параграфа, второе — номер теоремы или формулы в параграфе. Нумерация параграфов сквозная.

Первая глава посвящена дискретному преобразованию Виленкина-Крестенсона. На основе четырех вариантов факторизации матрицы функций Виленкина-Крестенсона построены четыре рекуррентных последовательности ортогональных базисов в пространстве дискретных 7У-периодических сигналов при Дг = С помощью этих последовательностей базисов получены четыре варианта быстрого преобразования Виленкина-Крестенсона.

В первом параграфе вводится терминология и описываются основные объекты дискретного гармонического анализа. Дается определение и основные свойства перестановки reverse и операций поразрядного сложения и вычитания по модулю п [30]. Приводятся необходимые сведения о функциях и матрице Виленкина-Крестенсона [6, 32, 30, 10]. Матрица Виленкина-Крестенсона имеет порядок N — ns и является s-й кронекеровой степенью матрицы Фурье порядка п. Она стандартным приемом раскладывается на множители (факторизуется) [39], причем сомножители в таком разложении допускают перестановку в любом порядке. Выделяются два порядка сомножителей, соответствующие в устоявшейся терминологии прореживанию по частоте и прореживанию по времени. Кроме того, матрица Виленкина-Крестенсона может быть двумя способами представлена в виде обычной степени разреженной матрицы порядка N [39, 24].

Во втором и третьем параграфах на основе представлений матрицы Виленкина-Крестенсона в виде s-й степени большой разреженной матрицы строятся две последовательности ортогональных базисов в пространстве дискретных /V-периодических сигналов при N = ns. Для базисных сигналов указывается явный вид и приводятся рекуррентные формулы пересчета. Особенностью этих формул является постоянство индексации базисных сигналов на каждом уровне.

В четвертом параграфе описаны в явном виде быстрые алгоритмы разложения сигнала по всем промежуточным базисам. На заключительном этапе вычисляются коэффициенты разложения по базису Виленкина-Крестенсона. Дается строго математический анализ понятия частоты для дискретных функций Виленкина-Крестенсона, введенного на интуитивном уровне в монографии [30, с. 79−84].

В пятом и шестом параграфах на основе разложений матрицы Виленкина-Крестенсона на попарно различные множители строятся еще две рекуррентные последовательности ортогональных базисов. Получены явные формулы для базисных сигналов. Показано, что базисные сигналы каждого уровня разбиваются на блоки, в каждом из которых сигналы различаются лишь сдвигом аргумента. Отмечается, что построенные ортогональные базисы с точностью до нумерации сигналов совпадают с базисами, построенными в § 2,3.

В седьмом параграфе с помощью разложений по построенным выше ортогональным базисам получены два алгоритма быстрого преобразования Виленкина-Крестенсона (при п = 2 аналогичный результат приведен в [22]).

В восьмом параграфе устанавливается связь между четырьмя вариантами факторизации матрицы Виленкина-Крестенсона, представленными в § 1. При этом проясняется роль перестановки reverse в формировании матриц-сомножителей.

Вторая глава посвящена вопросам оснащения дискретного гармонического анализа вейвлетной теорией. Получены вейвлетные разложения пространства дискретных периодических сигналов. Изучаются спектральные свойства сигналов в вейвлетных базисах.

В девятом и десятом параграфах показывается, как, пользуясь последовательностью ортогональных базисов, сформировать обобщенный вейвлет-пакет. Детально исследуются вейвлетные базисы Хаара-Крестенсона, связанные с прореживанием по времени (§ 9) и прореживанием по частоте (§ 10). Выясняется структура вей-влетных подпространств. Выводятся формулы декомпозиции и реконструкции. Предлагается «наивный» подход к построению ортогональных вейвлетных базисов, использующий разложение сигнала по собственным сдвигам. При этом поясняется роль операций поразрядного слолсения и вычитания по модулю п при прореживании по частоте. В случае п = 2 эти вопросы (за исключением модулярной арифметики) рассматривались в [19, 20].

В одиннадцатом параграфе вводится понятие спектра сигнала в базисах Хаара-Крестенсона. Вычисляются спектры Ха-ара-Крестенсона сдвигов единичного импульса — элементов естественного ортонормированного базиса в пространстве дискретных периодических сигналов. Доказываются аналоги известных теорем о спектре сдвига, свертки и корреляции в базисах Ха-ара-Крестенсона. При этом, в зависимости от базиса, в качестве оператора сдвига может выступать циклический или п-ичный сдвиг. Соответственно, свертка и корреляция может быть циклической или п-ичной. Для базиса Хаара-Крестенсона, связанного с прореживанием по частоте, в качестве оператора сдвига выступает п-ичный сдвиг. Устанавливается, что сдвиг сигнала приводит к сдвигам внутри блоков его спектра с одновременным поворотом спектральных коэффициентов в комплексной плоскости, а свертка и корреляция двух сигналов — соответственно к поблочной свертке и корреляции их спектров. В случае базиса Хаара-Крестенсона, связанного с прореживанием по времени, оператором сдвига является циклический сдвиг. Для спектра сдвига в этом базисе получен результат, аналогичный случаю прореживания по частоте. Для спектров свертки и корреляции результаты более тонкие: свертка и корреляция двух сигналов приводят соответственно к модифицированной свертке и корреляции соответствующих блоков их спектров (модификация заключается в том, что при вычислении осуществляется поворот части слагаемых). В случае п = 2 (для дискретных базисов Хаара) теоремы о сдвиге и свертке изучались в [18].

В двенадцатом параграфе устанавливается взаимосвязь базисов Хаара-Крестенсона, связанных с прореживанием по частоте и прореживанием по времени. Ключевую роль здесь играет перестановка reverse. Вводится понятие логарифмически автореверсного спектра Хаара-Крестенсона. Устанавливается связь между сигналами, имеющими в различных базисах Хаара-Крестенсона одинаковый спектр, при условии, что этот спектр является логарифмически автореверсным. В качестве иллюстрации вычислен спектр Хаара — Крестенсона кусочно-линейного сигнала, связанный с прореживанием по времени. Подсчитана размерность множества логарифмически автореверсных спектров. Аналогичное исследование в частном случае п — 2 проведено в [17].

В тринадцатом параграфе представлены два обобщенных крат-номасштабных анализа по основанию п пространства дискретных iV-периодических сигналов при N = ns, которые приводят к базисам Хаара-Крестенсона. Тем самым устанавливается связь полученных результатов с общей вейвлетной теорией [11, 26, 27].

На защиту выносятся следующие основные результаты:

1) В пространстве дискретных N-периодических сигналов при N = п'5 построены рекуррентные последовательности ортогональных базисов.

2) С помощью этих последовательностей базисов построены четыре варианта быстрого преобразования Виленкина-Крестенсона (БПВК).

3) Установлено, что в процессе реализации алгоритмов БПВК второго рода вычисляются коэффициенты вей-влетных разложений (в частности, разложений по базисам ХаараКрестенсона).

4) Доказаны теоремы о спектре сдвига, свертки и корреляции дискретных сигналов в базисах Хаара-Крестенсона.

5) Установлена связь между базисами Хаара-Крестенсона, связанными с прорежтванием по частоте и прореживанием по времени, в том числе с использованием понятия логарифмически автореверсного спектра.

6) Построены два обобщенных кратно масштабных анализа по основанию п пространства дискретных N-периодических сигналов при N = п1*.

Основные результаты диссертации опубликованы в работах [16, 23, 24, 25, 41, 43].

— 13.

Автор приносит глубокую благодарность своему научному руководителю профессору В. Н. Малоземову за помощь в постановке задач и анализе результатов, а также за постоянное внимание в течение всего времени работы над диссертацией. Автор также выражает признательность руководителям и участникам С.-Петербургского городского семинара «Всплески и их приложения» (http://www.math.spbu.ru/user/dmp) за конструктивные замечания и обсуждение материала диссертации.

Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (грант 99−01−747).

1. Айзенберг Н. Н., Трофимлюк О. Т. Сдвиг, свертка и корреляционная функция дискретных сигналов в произвольном базисе // ДАН СССР. 1980. Т. 250. № 1. С. 47−51.

2. Алексеев А. А., КирилловА. Б. Технический анализ сигналов и распознавание радиоизлучений. СПб.: ВАС, 1998. 368 с.

3. Астафьева Н. М. Вейвлет-анализ: основы теории и примеры применения // Успехи физ. наук. 1998. Т. 166. № 11. С. 11 451 170.

4. Ахмед Н., Рао К. Р. Ортогональные преобразования при обработке цифровых сигналов. М.: Связь, 1980. 248 с.

5. Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов. М.: Мир, 1989. 448 с.

6. Виленкин Н. Я. Об одном классе полных ортогональных систем // Изв. АН СССР. Сер. матем. 1947. Т. И. № 4. С. 363 400.

7. Воеводин В. В., Кузнецов Ю. А. Матрицы и вычисления. М.: Наука, 1984. 318 с.

8. Воробьев В. И., Грибунин В. Г. Теория и практика вейвлет-преобразования. СПб.: Изд-во ВУС, 1999. 208 с.

9. Голубов Б. И., Ефимов А. В., Скворцов В. А. Ряды и преобразования Уолша. М.: Наука, 1987. 344 с.

10. Дагман Э. Е., Кухарев Г. А. Быстрые дискретные ортогональные преобразования. Новосибирск: Наука, 1983. 232 с.

11. Добеши И. Десять лекций по вейвлетам. Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001. 464 с.

12. Залманзон Л. А. Преобразования Фурье, Уолша, Хаара и их применение в управлении, связи и других областях. М.: Наука. Гл. ред. физ.-мат. лит., 1989. 496 с.

13. Кирушев В. А., Малоземов В. Н., Певный А. Б. Вейвлет-ное разложение пространства дискретных периодических сплайнов // Матем. заметки. 2000. Т. 67. Вып. 5. С. 712−720.

14. Кухарев Г. А. Основные теоремы сдвига, свертки и корреляции для задач цифровой обработки сигналов // Изв. вузов. Радиотехника. 1985. Т. 28. № 8. С. 26−31.

15. Макклеллан Дж. X., Рейдер Ч. М. Применение теории чисел в цифровой обработке сигналов. М.: Радио и связь, 1983. 264 с.

16. Малоземов В. Н., Машарский С. М. Обобщенные вейвлетные базисы, связанные с дискретным преобразованием Виленки-на-Крестенсона // Алгебра и анализ. 2001. Т. 13. № 1. С. 111 157.

17. Малоземов В. Н., Машарский С. М. Сравнительное изучение двух вейвлетных базисов // Проблемы передачи информации. 2000. Т. 36. Вып. 2. С. 27−37.

18. Малоземов В. Н., Машарский С. М. Хааровские спектры дискретных сверток // Ж. вычисл. мат. и мат. физ. 2000. Т. 40. № 6. С. 954−960.

19. Малоземов В. Н., Певный А. Б., Третьяков А. А. Быстрое вейвлетное преобразование дискретных периодических сигналов и изображений // Проблемы передачи информации. 1998. Т. 34. Вып. 2. С. 77−85.

20. Малоземов В. Н., Третьяков А. А. Алгоритм Кули-Тьюки и дискретное преобразование Хаара // Вестник СПбГУ. Сер. 1. 1998. Вып. 3 (№ 15). С. 31−34.

21. Малоземов В. Н., Третьяков А. А. Новый подход к алгоритму Кули-Тьюки // Вестник СПбГУ. Сер. 1. 1997. Вып. 3 (№ 15). С. 57−60.

22. Малоземов В. Н., Третьяков А. А. Секционирование, ортогональность и перестановки // Вестник СПбГУ. Сер. 1. 1999. Вып. 1 (№ 1). С. 16−21.

23. Машарский С. М. Автореверсные спектры Хаара-Крестен-сона // Вестник СПбГУ. Сер. 1. 2001. Вып. 2 (№ 9). С. 57−65.

24. Машарский С. М. Быстрое преобразование Виленкина-Крес-тенсона на основе факторизации Гуда // Электронный архив препринтов С.-Петербургского Мат. Общества. Препринт № 2000;14. 10 с. http://www.mathsос.spb.ru/preprint/2000/index.html#14.

25. Машарский С. М. Свертка и корреляция дискретных сигналов в базисах Хаара-Крестенсона // Вестник молодых ученых. Прикл. матем. и механика. 2000. № 4. С. 31−40.

26. Новиков И. Я., Стечкин С. Б. Основы теории всплесков // Успехи матем. наук. 1998. Т. 53. № 6 (324). С. 53−128.

27. Петухов А. П.

Введение

в теорию базисов всплесков. СПб.: Изд-во СПбГТУ, 1999. 132 с.

28. Петухов А. П. Периодические всплески // Матем. сборник. 1997. Т. 188. № 10. С. 69−94.

29. Петухов А. П. Периодические дискретные всплески // Алгебра и анализ. 1996. Т. 8. № 3. С. 151−183.

30. Трахтман А. М., Трахтман В. А. Основы теории дискретных сигналов на конечных интервалах. М.: Советское радио, 1975. 208 с.

31. Хармут X. Теория секвентного анализа. Основы и применения. М.: Мир, 1980. 576 с.

32. Chrestenson Н. Е. A class of generalized Walsh functions // Pacific J. Math. 1955. Vol. 5. No. 1. P. 17−31.

33. Chui С. K. An Introduction to Wavelets. Academic Press, San Diego, CA, 1992. 264 p.

34. Coifman R. R., Meyer I., Wickerhauser M. V. Adapted waveform analysis, wavelet packets and applications // Proc. ICIAM'91. Philadelphia, 1992. P. 41−50.

35. Coifman R. R., Wickerhauser M. V. Entropy-based algorithms for best basis selection // IEEE Trans. Inform. Theory. 1992. Vol. 38. No. 2. P. 712−718.

36. Cooley J. W., Tukey J. W. An algorithm for the machine calculation of complex Fourier series // Math. Comput. 1965. Vol. 19. No. 90. P. 297−301.

37. Daubechies I. Orthonorrnal bases of compactly supported wavelets // Comm. Pure and Appl. Math., № 41, 1988. P. 909 996.

38. Daubechies I. Ten Lectures on Wavelets. SIAM/CBMS-NSF Regional Conf. Series in Appl. Math., Vol. 61, 1992. 378 p.

39. Good I. J. The interaction algorithm and practical Fourier analysis //J. Royal Stat. Soc. (London). 1958. Vol. B-20. No. 2. P. 361 372.

40. Mallat S. A Wavelet Tour of Signal Processing. Academic Press, 1998. 578 p.

41. Malozemov V. N., Masharsky S. M. Adaptive signal processing based on discrete Vilenkin-Chrestenson transform // Proc. Int. Conf. «Neural Networks and Artificial Intelligence». Minsk, Belarus, 2001. V. lW-Zft .

42. Malozemov V. N., Masharsky S. M. Haar spectra of discrete signals // Abstracts of the 2nd Int. Conf. «Tools for Mathematical Modelling». St. Petersburg, 1999. P. 86−87.

43. Masharsky S. M. Haar-Chrestenson spectra of discrete signals // Abstracts of the Int. Conf. «Optimization of Finite Element Approximations & Splines and Wavelets». St. Petersburg, 2001. P. 153−154.

44. Strang G., Nguyen T. Wavelets and Filter Banks. Wellesley-Cambridge Press, 1996. 512 p.

45. Wickerhauser M. V. Adapted Wavelet Analysis from Theory to Software. IEEE Press, New York, 1994. 504 p.