Цифровая обработка динамических данных тема автореферата и диссертации по математике, 01.01.07 ВАК РФ

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

На правах рукописи

Пахомов Сергей Николаевич

ЦИФРОВАЯ ОБРАБОТКА ДИНАМИЧЕСКИХ ДАННЫХ

01.01.07 — вычислительная математика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

ч^о^ком,''

Санкт-Петербург 2005 г.

Работа выполнена на кафедре исследования операций

математико-механического факультета Санкт-Петербургского Государственного Университета

НАУЧНЫЙ РУКОВОДИТЕЛЬ:

доктор физико-математических наук, профессор МАЛОЗЕМОВ Василий Николаевич

ОФИЦИАЛЬНЫЕ ОППОНЕНТЫ:

доктор физико-математических наук, профессор ДЕМЬЯНОВИЧ Юрий Казимирович,

кандидат физико-математических наук ТРЕТЬЯКОВ Алексей Андреевич

ВЕДУЩАЯ ОРГАНИЗАЦИЯ:

Санкт-Петербургски й Государственны й Электротехнический Университет «ЛЭТИ»

Защита состоится 26 мая 2005 г. в 14 часов на заседании диссертационного совета Д 212.232.49 по защите диссертаций на соискание ученой степени доктора наук при Санкт-Петербургском Государственном Университете по адресу: 199004, Санкт-Петербург, 14 линия Васильевского острова, д. 29, ауд. 31.

С диссертацией можно ознакомиться в Научной библиотеке им М Горького Санкт-Петербургского государственного университета по адресу: 199034, Санкт-Петербург, Университетская наб., 7/9.

Автореферат разослан « £6 » _2005 г.

Ученый секретарь диссертационного совета

¿шг-ч

Общая характеристика работы

Актуальность темы. В дискретном гармоническом анализе фундаментальную роль играет дискретное преобразование Фурье (ДПФ). С момента изобретения в 1965 г. алгоритма быстрого преобразования Фурье (БПФ) последний находится в центре внимания как математиков, так и инженеров, занимающихся цифровой обработкой сигналов. В последние годы интерес к быстрым преобразованиям повысился в связи с тем, что возникла необходимость обрабатывать непериодические сигналы, имеющие огромное число отсчетов. В первую очередь это относится к цифровой обработке звука и изображений.

При решении различных задач обработки непериодических сигналов в реальном масштабе времени требуется оперативный анализ частотного спектра конечной выборки сигнала, скользящей вдоль оси дискретного времени. Применение периодической техники в таких задачах позволяет повысить оперативность анализа спектра. Однако все классические БПФ по своей сути являются алгоритмами статического типа, поскольку оперируют только с отсчетами, накопленными к моменту анализа, и не учитывают результаты расчетов на предыдущих шагах скольжения. В то же время при незначительном сдвиге выборки основная часть информации остается неизменной. Это создает предпосылки для разработки более эффективных в вычислительном плане алгоритмов.

В диссертационной работе развиваются существующие идеи вычисления скользящего спектра Фурье и предлагаются новые методы вычисления как статического, так и скользящего сегмента спектра сигнала.

Цель работы. Целью работы является разработка и исследование быстрых алгоритмов обработки дискретных непериодических данных. Для достижения этой цели в диссертации решались следующие задачи:

1) Разработка алгоритмов анализа сегмента спектра Фурье и синтеза сегмента входного сигнала.

3

РОС. НАЦИОНАЛЬНАЯ

Б К ЕЛ И ОТ!. К Л Петербург

2) Разработка алгоритмов анализа скользящего сегмента спектра Фурье.

3) Создание программного обеспечения для решения задачи восстановления высоких гармоник звуковых сигналов и проведение экспериментальных исследований с использованием разработанного программного продукта.

Методика исследования. В диссертационной работе использовался математический аппарат дискретного гармонического анализа и цифровой обработки сигналов.

Научная новизна. В диссертации получены следующие основные результаты.

1) Разработаны и исследованы алгоритмы анализа сегмента спектра Фурье по полному сигналу и алгоритмы синтеза сегмента входного сигнала по полному спектру с прореживанием по времени и по частоте.

2) Разработаны и исследованы алгоритмы анализа центрального сегмента спектра Фурье и синтеза центрального сегмента входного сигнала.

3) Разработаны и исследованы алгоритмы анализа скользящего сегмента спектра Фурье при сдвиге входного сигнала на один отсчет и при двоичном сдвиге сигнала.

4) Для всех предложенных алгоритмов проведена оценка эффективности в сравнении с существующими вычислительными схемами.

Практическая ценность. Разработан программный продукт, позволяющий производить обогащение звуковых моно- и стереосигналов высокими частотами. Проведены экспериментальные исследования с использованием созданного программного обеспечения.

Апробация работы и публикации. По результатам диссертации сделан цикл докладов на семинаре по дискретному гармоническому анализу и доклад на семинаре кафедры исследования операций математико-механического факультета СПбГУ. По теме диссертации опубликовано 5 работ.

* Структура и объем работы. Диссертация состоит из введе-

ния, трех глав и списка литературы. Первая глава включает в себя 8 параграфов, вторая и третья — б и 7 параграфов соответственно. | Объем диссертации — 99 страниц. Список литературы насчитывает

38 наименований.

Содержание работы

Во введении дан краткий исторический обзор и сформулированы основные результаты диссертации.

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

Пусть Ъ — множество целых чисел; а : Ь — множество последовательных целых чисел {о, а + 1,..., 6}. Целое число ] можно единственным образом представить в виде ] — /г + /', где г — натуральное число и/'б0:г-1. Для неполного частного / и остатка используются обозначения / = У/г\, ]" = (з)г. Пусть $ — натуральное число и N — 2я. Обозначим через С/у линейное пространство комнлекснозначных ^/-периодических функций целочисленного аргументах = х{з), j €Е Z. Элементы пространства Сдг будем называть сигналами, а величины х(з) — компонентами (или отсчетами) сигнала. Дискретное преобразование Фурье У/у : Слг —♦ Сдг сопоставляет сигналу х сигнал X = с компо-

нентами

ЛГ-1

= Лег,

з~о

где и/р! = ехр(27гг//У). Сигнал X называется спектром Фурье сигнала х, а величины Х{к) — компонентами спектра.

Положим ЛГ„ = N/2", Д„ = 2"-1 и введем в рассмотрение перестановку геУу, которая сопоставляет числу ] е 0 : 2" — 1 число геу„(Д Двоичный код которого равен перевернутому //-разрядному двоичному коду числа

Пусть необходимо анализировать только часть компонент спектра, индексы которых принадлежат заданному промежутку а : 6, 0<O<6<A'' — 1. Назовем такую выборку сегментом спектра Фурье. Обозначим п = 6 — а +• 1, г = п\.

Теорема 1. Компоненты сегмента спектра Х(к), к £ а : Ь могут быть вычислены по полному сигналу х согласно формулам:

х0(к) = ж(геул(А)), к £ 0 : N - 1; (1)

хи(1 + рА.+х) = х^1(1 + 2рА1/)+и1[нх1/-1{1 + {2р+1)А1/), хи{1 + Д„ + рА„+1) = + 2рА„) -ш^х^Ц + (2р + 1)Д„), р € 0 : - 1, / € 0 : Д„ — 1, и £ 1 : г;

(2)

х„(1 Л-рАу+х) = Же-ЖОд,, + 2рАи)+

+ (2р + 1)Д„), (3)

р £ 0 : - 1, / = (а>д,+1 , (а + ,..., <Ь>Д^ , и £ г + 1 : Й;

Х(Л) = я, (А), к £ а : Ь. (4)

Вычисления по формулам (1)-(4) назовем анализом сегмента спектра Фурье с прореживанием по времени. Для этих вычислений требуется выполнить

М = ~г + п(М ■ 2~г - 1) (5)

А

комплексных умножений и

А = ^ + -2~г-I) (6)

комплексных сложений.

Теорема 2. Компоненты сегмента спектра У (к), к £ а: Ь могут быть вычислены по полному сигналу у согласно формулам:

Уо{к)=У{к), ке 0 : ЛГ — 1; (7)

Л+р) = Уи-^Шг-! +р)+Ш~ы1тЛ21)у^1(Ш^1 + К+ р), у„((21 + 1)ЛГ„ + р) = + р) - и~ы1ечЛ21)у^(Ши-Х + + р),

I € о : Д„ - 1, р £ 0 : - 1, I/ € 1 : г;

(8)

I = [теуД«)/^] , [геу„(а + 1)/Лд |геу.,(6)/Л^ , 1 > реО: N„-1, I/ € г + 1 : в;

У(к) = г/ДгсуДА:)), кеа:Ь. (10)

Вычисления по формулам (7)—(10) назовем анализом сегмента спектра Фурье с прореживанием по частоте. Для этих вычислений также требуются комплексные умножения и сложения в количестве, определяемом соотношениями (5), (6).

В задачах цифровой обработки сигналов возникают не только проблемы анализа (вычисления спектра), по и проблемы синтеза (восстановления сигнала по его спектру). В таких задачах зачастую восстанавливают не весь сигнал, а лишь его внутренний сегмент. В параграфах 5-7 первой главы разработаны соответствующие алгоритмы.

Теорема 3. Компоненты сегмента входного сигнала х(к), к € £а:6 могут быть вычислены по его полному спектру X согласно формулам:

хя(к)=Х(к), к & 0 : N — V, (И)

х„-\(! + 2рА„) = Ых„(1 + рА„+1) + х„(1 + Д„ +рД„+1)], Хи-\(I + (2р + 1)Д„) = з^д^Ы* - + Д„ +рА„+1)},

ре 0:7У„-1, / € 0 : Д„ — 1, и = в, в - 1,..., 5 - г + 1;

®„_i(í + рД„) = + \p/2\ Д„+1)+

+(-l)pav(¿ + Д„ + b/2j Дн-i)]- (13)

p = |_геу„(а)/Д„], |rev„(a + l)/A„J,..., |_геу.,(6)/Д„] , le O : Д„ - 1, Í/ = e — г, a — r — 1,..., 1;

= xo(rev.,(A;)), к € a : b. (14)

Вычисления по формулам (11)—(14) назовем синтезом сегмента входного сигнала с прореживанием по времени. Для этих вычислений также требуются комплексные умножения и сложения и количестве, определяемом соотношениями (5), (6).

Теорема 4. Компоненты сегмента входного сигнала у (к), к 6 € а : b могут быть вычислены по его полному спектру Y согласно формулам:

у,{k) =» y(rev,(fc))f к € 0 : N - 1; (15)

Vv-iílNy-i +р) = \[yv{2lNu +р) + y„((2J + l)Nv +р), у^г(1К.х + = lu^Ví^ + р) - у„((2/ + 1)Л„ +р)],

í € 0 : Д„ - 1, р € О': - 1, i/ = s, s - 1,..., s - r + 1;

(16)

y^ilN^+p) = i 4,/A,"Jrev'(2i)[l/,(2Z7V1/ + <р)„>

i/ = s — r, s — r — 1,..., 1;

y{k) = y0{k), kea-.b. (18)

Вычисления по формулам (15)—(18) назовем синтезом сегмента входного сигнала с прореоюиванием по частоте. Для этих вычислений также требуются комплексные умножения и сложения в количестве, определяемом соотношениями (5), (6).

В восьмом параграфе первой главы для всех полученных вычислительных схем проведена оценка эффективности в сравнении с существующими алгоритмами.

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

Рассматриваются комплекснозначные функции целочисленного аргумента х — х(]), ] € не являющиеся периодическими. Множество таких функций обозначим С«,.

Назовем скользящим спектром спектр конечной выборки функции х, перемещающийся вдоль временной оси:

ы-1

= к Е 0 : N — I,

7=0

где I б Ъ — некоторый момент дискретного времени. Выборку Х^к), к € а : Ь, где 0<а<6</У — 1, назовем сегментом скользящего спектра.

Кроме того, введем в рассмотрение сигналы Х\ при и е 0 : я, ¿6 2, с компонентами

ХГ(к) к € 0 : ЛГ„ - 1.

j=o

Теорема 5. Пусть известны компоненты Х"_^(к), к е 0 : Л^ — 1, у е 1 : а. Тогда компоненты Х®(к), к £ 0 : N — 1 могут быть вычислены по формулам

хг\к) =хг(к)+^_х;'_^(к),

хгЧя + к) = х?(к) - ш^хим (19)

к 6 0 : К - 1, I/ = 5,5- 1,... ,1.

Вычисления по формуле (19) назовем анализом спектра Фурье при сдвиге сигнала на один отсчет. Эти вычисления требуют выполнения

Мг = N - 1, А\ = 2ЛГ - 2

комплексных умножений и комплексных сложений соответственно. При этом необходимо хранить в памяти

Ri = ¿N\og2N вспомогательных компонент.

Теорема 6. Пусть известны компоненты k = (a)N¡ ,

(a+l)N¡r,...,(b)Nv,v 6 1 : s-r, и ХЦА¿k), к G 0 : N„ - Í, // G s — г + 1 : s. Тогда компоненты Xf(k), к € а : b могут быть вычислены по формулам

хгг(к)^хг(к)+ш^хим ХГЧК + к) = ХПк) - ш^хим (20)

/с е 0 : Af„ — 1, u = s,s — l,...,s — г 4-1;

ХГ(к) = X?((k)K) 4- Л <*>*.)'

к = <aW,. (а + I ■ ■ • > . f = s - г, s - г - 1,..., 1.

(21)

Вычисления по формулам (20)—(21) назовем анализом сегмента спектра Фурье при сдвиге сигнала на один отсчет. Эти вычисления требуют выполнения

М2 = n(s - г) 4- 2Г - 1, А2 = n(s - г) 4- 2r+1 - 2

комплексных умножений и комплексных сложений соответственно. При этом необходимо хранить в памяти

R2 = 1лГг 4- п(2я-г - 1)

вспомогательных компонент.

В четвертом и пятом параграфах второй главы аналогичные алгоритмы получены для двоичного сдвига сигнала. Положим т — 2l, t G 0 : s.

Теорема 7. Пусть известны компоненты Xjf_ ^(к), к £ О : 7V„— — 1, р £ О : т—1, у £ í+1 : s. Тогда компоненты Xf (к), к £ 0 : N—1 могут быть вычислены по формулам

+ к)= Х?_р(к) - ¿к), (22)

к £ 0 : N„ - 1, ре 0 : min{m, Д^} — 1, v = s, s — 1,..., 1.

Вычисления по формуле (22) назовем анализом спектра Фурье при двоичном сдвиге сигнала. Эти вычисления требуют выполнения

М3 = ^N1 + N-m, A3 = Nt + 2N -2т

комплексных умножений и комплексных сложений соответственно. При этом необходимо хранить в памяти

R3 = \N(s-t)

вспомогательных компонент.-

В случае анализа сегмента спектра при двоичном"сдвиге сигнала форма алгоритма зависит от соотношения величин s, L и г. Рассмотрим отдельно два случая: 0 < í < s — ras — г < L < s (при t = s — г полученные алгоритмы совпадают).

Теорема 8. Пусть 0 < t < s — г и при р £ 0 : т - 1 известны компоненты X¡_p_^(k), k = (a)N¡/, (а + l)Wi/,..., (b)N¡/, v £ 1+ +1 : s - г и X"_p_^v{k), к £ 0 : Nu- 1, v £ s - г + 1 \ s. Тогда компоненты Xf{k), k £ a : b могут быть вычислены no формулам

X£¡{k) = Xr_p(k)+u-NlX[_p_Ai/(k), Xp; (TV, + k) = Xlp{k) - ^_ХГ_Р.АМ (23)

k e 0 : N„ - 1, p £ 0 : m — 1, и = s,s - 1,... ,s - r + 1.

(k) = (k)N„) + (<*>n„),

k = Или,. + »• • •, (ь)к-1' P e 0 : min{™> M - !»

и = s - r, s - r — 1, . . . , 1.

Вычисления по формулам (23)-(24) требуют выполнения

М4 = п(т - 1) + nm(s -r-t) + т( Т - 1), А4 = п(гп - 1) + nm(s -r-t) + 2m(2r - 1)

комплексных умножений и комплексных сложений соответственно. При этом необходимо хранить в памяти

JU = ^Nr + п(2"~г - тп) ¿1

вспомогательных компонент.

Теорема 9. Пусть s — г < t < s и известны компоненты х1-р-д,(*0» к £ 0 : Nv - 1, р е 0 : т - 1, v e-t + 1 : s. Тогда компоненты Х^(к), к £ а : b могут быть вычислены по формулам

Xfiik) = Xlv{k) + u-NlXlp_^k),

+ *) = Xlv{k) - ы^д¿к), (25)

keO:N,,-l, p£ 0 : min{7n, Д„} - 1,

// = S-, S — 1, . . . , 5 — Г + 1.

*#(*) = <*)„„) + (/c)NJ,

fc = (o)^.,, (a + , • • •, WA^ P € 0 : Д„ - 1, (26)

V — s — r, s — r — 1, . . . , 1.

Вычисления по формулам (25)-(26) требуют выполнения

Мь = n(2"~r -1) + \N(t -s + r)+N-m, A5 = n(2,,-r - 1) + iV(i - s + r) + 2N - 2m

комплексных умножений и комплексных сложений соответственно. При этом необходимо хранить в памяти

R5 = ^N{s - i)

вспомогательных компонент.

В шестом параграфе второй главы для всех полученных вычислительных схем проведена оценка эффективности в сравнении с существующими алгоритмами.

Третья глава посвящена применению разработанных алгоритмов для решения прикладных задач.

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

Основные результаты диссертации опубликованы в работах

1. Пахомов С.Н. Анализ скользящего сегмента спектра Фурье // Вестник молодых ученых. Сер. «Прикладная математика и механика». 2004. № 1. С. 21-26.

2. Пахомов С.Н. Вычисление внутреннего сегмента спектра Фу-1>ье И Вестп. С.-Петербург, ун-та. Сер. 1. 2003. Вып. 3 (№ 17). С. 79-83.

3. Пахомов С.Н. Вычисление скользящего спектра Фурье // Вести. С.-Петербург, ун-та. Сер. 1. 2004. Вып. 3 (№ 17). С. 45-49.

4. Пахомов С.Н. Анализ сегмента спектра Фурье и синтез сегмента входного сигнала // Электронный архив препринтов С.-Петербургского матем. общества. Препринт № 2005-04.

5. Пахомов С.Н., Просеков О.В. Вычислительные аспекты быстрого преобразования Фурье // Вестн. С.-Петербург, ун-та. Сер. 1. 2004. Вып. 4. С. 44-50.

Подписано в печать 14 04.05 Формат 60x84/16. Бумага офсетная. Печать офсетная. Усл. печ. л. 0,7. Тираж 100 экз. Заказ № 13

Типография Издательства СПбГУ. 199061, С-Петербург, Средний пр., 41.

л

РНБ Русский фонд

2005-4 41990

Введение

1 Анализ сегмента спектра Фурье и синтез сегмента входного сигнала

1.1 Предварительные сведения.

1.2 Алгоритм вычисления сегмента спектра Фурье с прореживанием по времени.

1.3 Алгоритм вычисления центрального сегмента спектра Фурье с прореживанием по времени.

1.4 Алгоритм вычисления сегмента входного сигнала с прореживанием по времени.

1.5 Алгоритм вычисления сегмента спектра Фурье с прореживанием по частоте.

1.6 Алгоритм вычисления сегмента входного сигнала с прореживанием по частоте.

1.7 Алгоритм вычисления центрального сегмента входного сигнала с прореживанием по частоте.

1.8 Сравнение с существующими алгоритмами.

2 Анализ скользящего сегмента спектра Фурье

2.1 Предварительные сведения.

2.2 Алгоритм вычисления полного спектра при сдвиге сигнала на один отсчет

2.3 Алгоритм вычисления сегмента спектра при сдвиге сигнала на один отсчет

2.4 Алгоритм вычисления полного спектра при двоичном сдвиге сигнала.

2.5 Алгоритм вычисления сегмента спектра при двоичном сдвиге сигнала.

2.6 Сравнение с существующими алгоритмами.

3 Применение алгоритмов обработки динамических данных

3.1 Предварительные сведения.

3.2 Задача восстановления высоких гармоник звуковых одно- и двухканальных сигналов.

3.3 Алгоритм решения.

3.4 Требования к программно-аппаратному комплексу

3.5 Описание разработанного программного продукта

3.6 Эксперименты по восстановлению моно- и сетеросиг-налов.

3.7 Другие задачи обработки звука.

В дискретном гармоническом анализе [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.html^04

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. 297301.

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.