В дискретном гармоническом анализе [1, 8, 9, 31, 32] фундаментальную роль играет дискретное преобразование Фурье (ДПФ) [3, 6, 17, 33]. С момента изобретения в 1965 г. алгоритма быстрого преобразования Фурье (БПФ) [2, 5, 10, 11, 12, 13, 15, 36] последний находится в центре внимания как математиков, так и инженеров, занимающихся цифровой обработкой сигналов [4, 7, 16, 28, 29, 38]. В последние годы интерес к БПФ повысился в связи с тем, что возникла необходимость обрабатывать непериодические сигналы, имеющие огромное число отсчетов. В первую очередь это относится к цифровой обработке звуковых сигналов [25, 26, 27] и изображений [18, 24, 34].
При обработке непериодических данных перед вычислением спектра Фурье выбирается отрезок сигнала, на котором будет проводиться спектральный анализ, после чего к этому отрезку применяют алгоритм БПФ. При этом предполагается, что выбранный участок периодически продолжен на все целые индексы. Однако при вычислении спектра таким образом может возникнуть следующий нежелательный эффект. Выбирая следующий отрезок сигнала, мы вновь предполагаем его периодичность. Тем самым на стыке двух последовательных участков возникает несоответствие, которое влечет за собой искажение спектра.
В настоящее время существует три различных метода для устранения этого эффекта: работа с внутренним сегментом спектра (входного сигнала), применение взвешивающих окон и динамические алгоритмы вычисления спектра. Рассмотрим каждый из этих методов подробнее.
Наиболее простым способом избежать описанного эффекта является работа не со всем спектром, а лишь с его внутренним сегментом. Попутно отметим, что в задачах цифровой обработки сигналов возникают не только проблемы анализа (вычисления спектра), но и проблемы синтеза (восстановления сигнала по его спектру). В таких задачах во избежание эффекта искажения восстанавливают не весь сигнал, а лишь его внутренний сегмент. И в случае анализа, и в случае синтеза обычно используют два подхода: вычисление всех компонент с отбрасыванием ненужных и поточечное вычисление необходимых компонент.
Первый подход может быть реализован с применением любого известного быстрого преобразования (в частности, алгоритма Кули-Тьюки). Достоинством этого метода является быстрота, достигаемая за счет использования периодической техники. Однако существенным недостатком такого метода являются производимые им лишние операции, направленные на вычисление неиспользуемых в дальнейшем компонент.
Второй подход реализуется с использованием алгоритма Герце-ля [14, 37], вычисляющего индивидуальную компоненту спектра. В отличие от алгоритма Кули-Тьюки, этот метод не производит лишних вычислений. Однако его недостатком является низкое быстродействие при больших длинах сегмента.
В первой главе диссертационной работы предлагается новый подход, отличающийся от двух рассмотренных тем, что вычисляются только требуемые компоненты спектра (входного сигнала), и при этом лишних операций не производится. Отдельное внимание уделяется вычислению центральных сегментов, поскольку этот случай наиболее распространен в практических приложениях. Разработаны различные алгоритмы вычисления внутреннего сегмента спектра (входного сигнала). Для полученных вычислительных схем проведена оценка эффективности в сравнении с существующими алгоритмами.
Вторым способом устранения эффекта искажения спектра является применение так называемых взвешивающих (или весовых) окон [35]. Выбранный для анализа отрезок сигнала домножается на весовое окно, которое плавно сводит его к нулю на концах анализируемого участка. Существует множество окон, все они имеют похожую форму и в значительной степени устраняют рассмотренные искажения спектра. Однако, выбор весовой функции влияет на многие показатели гармонического анализа. В том числе, на обнаружимость, степень достоверности и легкость реализуемости вычислительных операций. Для каждого конкретного приложения предпочтительно использовать свое окно. Это является существенным недостатком, поскольку в большинстве случаев про анализируемый сигнал заранее ничего не известно. По этой причине взвешивающие окна в диссертационной работе не рассматриваются.
Наконец, третий способ борьбы с искажением заключается в анализе спектра Фурье, скользящего вдоль оси дискретного времени. Т. е. каждый раз при сдвиге сигнала его спектр вычисляется заново. В настоящее время существует два подхода к вычислению скользящего спектра: статические и динамические алгоритмы пересчета.
К разряду статических относятся все классические алгоритмы БПФ (в частности, алгоритм Кули-Тьюки). Однако статические алгоритмы не являются оптимальными, поскольку в своей работе не принимают во внимание результаты расчетов, полученные на предыдущих шагах скольжения.
Динамическими являются алгоритмы, работающие с учетом накопленной информации. Основные подходы к синтезу таких вычислительных схем рассмотрены в [30]. В вычислительном плане предложенные в этой работе алгоритмы значительно эффективнее статических. Но они имеют существенный недостаток, поскольку применимы для сдвига (скольжения) спектра только на один отсчет.
Во второй главе диссертационной работы развиваются предложенные в указанной работе идеи. Разработаны динамические алгоритмы пересчета спектра Фурье, применимые при двоичном сдвиге сигнала (т.е. сдвиге на число отсчетов, являющееся степенью двойки). Для пересчета сегмента спектра также получены алгоритмы, применимые при сдвиге сигнала на один отсчет и при двоичном сдвиге сигнала. Для всех вычислительных схем проведена оценка эффективности в сравнении с существующими алгоритмами.
Третья глава диссертационной работы посвящена применению разработанных алгоритмов для решения прикладных задач. Ставится задача восстановления высоких гармоник звуковых однои двух-канальных сигналов, приводится алгоритм решения и требования к программно-аппаратному комплексу. Дается описание разработанного программного продукта и приводятся результаты экспериментальных исследований по восстановлению монои стереосигналов. В заключение приводится краткий обзор других задач обработки звука, в которых могут быть использованы разработанные в диссертации алгоритмы.
На защиту диссертации выносятся следующие основные результаты:
1) Алгоритмы анализа сегмента спектра Фурье по полному сигналу и алгоритмы синтеза сегмента входного сигнала по полному спектру с прореживанием по времени и по частоте.
2) Алгоритмы анализа центрального сегмента спектра Фурье и синтеза центрального сегмента входного сигнала.
3) Алгоритмы анализа скользящего сегмента спектра Фурье при сдвиге входного сигнала на один отсчет и при двоичном сдвиге сигнала.
Для всех предложенных алгоритмов проведена оценка эффективности в сравнении с существующими вычислительными схемами. Разработано программное обеспечение для решения задачи восстановления высоких гармоник монои стереосигналов.
Основные результаты диссертационной работы опубликованы в работах [19, 20, 21, 22, 23].
Диссертант приносит искреннюю благодарность научному руководителю, Малоземову Василию Николаевичу, за помощь в постановке задач, анализе полученных результатов и постоянное внимание к работе над диссертацией.
1. Ахмед Н., Рао К. Р. Ортогональные преобразования при обработке цифровых сигналов. М.: Связь, 1980.
2. Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов. М.: Мир, 1989.
3. Богнер РКонстантинидис А.
Введение
в цифровую фильтрацию. М.: Мир, 1976.
4. Гольденберг Л. М., Матюшкин Б. Д., Поляк М. Н. Цифровая обработка сигналов. М.: Радио и связь, 1985.
5. Дагман Э. Е., Кухарев Г. А. Быстрые дискретные ортогональные преобразования. Новосибирск: Наука, 1983.
6. Залманзон Л. А. Преобразования Фурье, Уолша, Хаара и их применение в управлении, связи и других областях. М.: Наука, 1989.
7. Лукин А.
Введение
в цифровую обработку сигналов. М., 2002.
8. Макклеллан Дж.Х., Рейдер Ч. М. Применение теории чисел в цифровой обработке сигналов. М.: Радио и связь, 1983.
9. Малоземов В. Н., Машарский С. М. Основы дискретного гармонического анализа. СПб.: НИИММ, 2003.
10. Малоземов В. Н., Машарский С. М. Формула Глассмана, быстрое преобразование Фурье и вейвлетные разложения // Труды Санкт-Петербургского математического общества. 2001. Т. 9. С. 97−119.
11. Малоземов В. Н., Третьяков А. А. Алгоритм Кули-Тьюки и дискретное преобразование Хаара // Вестн. С.-Петербург, ун-та. Сер. 1. 1998. Вып. 3 (№ 15). С. 31−34.
12. Малоземов В. Н., Третьяков А. А. Новый подход к алгоритму Кули-Тьюки // Вестн. С.-Петербург, ун-та. Сер. 1. 1997. Вып. 3 (№ 15). С. 57−60.
13. Малоземов В. Н., Третьяков А. А. Секционирование, ортогональность и перестановки // Вестн. С.-Петербург, ун-та. Сер. 1. 1999. Вып. 1 (№ 1). С. 16−21.
14. Мысовских И. П. Лекции по методам вычислений. СПб., 1998.
15. Нуссбаумер Г. Быстрое преобразование Фурье и алгоритмы вычисления сверток. М.: Радио и связь, 1985.
16. Оппенгейм А. В., Шафер Р. В. Цифровая обработка сигналов. М.: Связь, 1979.
17. Отнес Р., Эноксон Л. Прикладной анализ временных рядов. М.: Мир, 1982.
18. Павлидис Т. Алгоритмы машинной графики и обработки изображений. М.: Радио и связь, 1986.
19. Пахомов С. Н. Анализ скользящего сегмента спектра Фурье // Вестник молодых ученых. Сер. «Прикладная математика и механика». 2004. № 1. С. 21−26.
20. Пахомов С. Н. Вычисление внутреннего сегмента спектра Фурье // Вестн. С.-Петербург, ун-та. Сер. 1. 2003. Вып. 3 (№ 17). С. 7983.
21. Пахомов С. Н. Вычисление скользящего спектра Фурье // Вестн. С.-Петербург, ун-та. Сер. 1. 2004. Вып. 3 (№ 17). С. 45−49.
22. Пахомов С. Н. Анализ сегмента спектра Фурье и синтез сегмента входного сигнала // Электронный архив препринтов С.-Петербургского матем. общества. Препринт № 2005;04.http://www.mathsoc.spb.ru/preprint/2005/index.html04.
23. Пахомов С. Н., Просеков О. В. Вычислительные аспекты быстрого преобразования Фурье // Вестн. С.-Петербург, ун-та. Сер. 1. 2004. Вып. 4. С. 44−50.
24. Прэтт У. Цифровая обработка изображений. М.: Мир, 1982.
25. Рабинер Л., Голд Б. Теория и применение цифровой обработки сигналов. М.: Мир, 1978.
26. Рабинер Л., Шафер Р. Цифровая обработка речевых сигналов. М.: Радио и связь, 1981.
27. Рыбин С. В. Основы компьютерной обработки звука // Компьютерные инструменты в образовании. 2000. № 2. С. 52−64.
28. Сато Ю. Обработка сигналов. Первое знакомство. М., 2002.
29. Сергиенко А. Б. Цифровая обработка сигналов. СПб.: Питер, 2002.
30. Сюзев В. В. Быстрые преобразования Фурье для скользящего анализа спектра // Вестник МГТУ. Сер. Приборостроение. 1998. № 2. С. 29−38.
31. Трахтман A.M., Трахтман В. А. Основы теории дискретных сигналов на конечных интервалах. М.: Советское радио, 1975.
32. Френке Л. Теория сигналов. М.: Советское радио, 1974.
33. Хемминг Р. В. Цифровые фильтры. М.: Советское радио, 1980.
34. Хуанг Т. С. Быстрые алгоритмы в цифровой обработке изображений. М.: Радио и связь, 1984.
35. Хэррис У.Дж. Использование окон при гармоническом анализе методом дискретного преобразования Фурье j j ТИИЭР, 1978. Т. 66. № 1. С. 60−96.
36. Cooley J. W., Tukey J. W. An algorithm for the machine calculation of complex Fourier series // Math. Comput. 1965. Vol. 19. P. 297 301.
37. Goertzel G. An algorithm for the evaluation of finite trigonometric series // Amer. Math. Monthly. 1958. Vol. 65. P. 34−35.
38. Smith S. The Scientist and Engineer’s Guide to Digital Signal Processing. California Technical Publ., 1999.
