Новый метод вычисления линейных спектральных частот речевых сигналов, основанный на универсальном алгоритме решения трансцендентных уравнений
Предложен новый эффективный метод вычисления линейных спектральных частот (ЛСЧ) речевых сигналов, который основан на разработанном алгоритме полного численного решения трансцендентных уравнений, не имеющих кратных корней. Принципиально алгоритм состоит из двух частей - выделения отрезков, содержащих...
Saved in:
| Date: | 2002 |
|---|---|
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут гідромеханіки НАН України
2002
|
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/915 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Новый метод вычисления линейных спектральных частот речевых сигналов, основанный на универсальном алгоритме решения трансцендентных уравнений / В.Ю. Семенов // Акуст. вісн. — 2002. — Т. 5, N 4. — С. 38-50. — Бібліогр.: 18 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859655860061470720 |
|---|---|
| author | Семенов, В.Ю. |
| author_facet | Семенов, В.Ю. |
| citation_txt | Новый метод вычисления линейных спектральных частот речевых сигналов, основанный на универсальном алгоритме решения трансцендентных уравнений / В.Ю. Семенов // Акуст. вісн. — 2002. — Т. 5, N 4. — С. 38-50. — Бібліогр.: 18 назв. — рос. |
| collection | DSpace DC |
| description | Предложен новый эффективный метод вычисления линейных спектральных частот (ЛСЧ) речевых сигналов, который основан на разработанном алгоритме полного численного решения трансцендентных уравнений, не имеющих кратных корней. Принципиально алгоритм состоит из двух частей - выделения отрезков, содержащих единственный корень, и последующего нахождения корней с помощью одной из стандартных итерационных процедур. Эффективность различных модификаций предложенного метода поиска ЛСЧ проверена на реальных речевых сигналах. Исследованы два подхода к нахождению ЛСЧ - прямое решение трансцендентных уравнений относительно тригонометрических функций и решение полиномиальных уравнений, полученных в результате разложения по чебышевским полиномам. Свойство упорядоченности ЛСЧ использовано для снижения вычислительных затрат. В отличие от большинства существующих методов определения ЛСЧ, предложенный метод обладает произвольно высокой точностью вычислений и гарантирует устойчивость соответствующего авторегрессионного фильтра. Показано, что данный метод может быть применен в системах реального времени.
Запропоновано новий ефективний метод обчислення лінійних спектральних частот (ЛСЧ) мовних сигналів, який базується на розробленому алгоритмі повного чисельного розв'язку трансцендентних рівнянь, що не мають кратних коренів. Принципово алгоритм складається з двох частин - виділення відрізків, які містять єдиний корінь, та подальшого знаходження кореня за допомогою однієї зі стандартних ітераційних процедур. Ефективність різних модифікацій запропонованого методу пошуку ЛСЧ перевірено на реальних мовних сигналах. При цьому досліджені два підходи до знаходження ЛСЧ - пряме розв'язання трансцендентних рівнянь відносно тригонометричних функцій та розв'язання поліноміальных рівнянь, отриманих внаслідок розкладу за Чебишевськими поліномами. Властивість упорядкованості ЛСЧ використано для зниження обчислювальних витрат. На відміну від більшості існуючих методів обчислення ЛСЧ, запропонований метод забезпечує довільно високу точність обчислень та гарантує стійкість відповідного авторегресійного фільтра. Показано, що даний метод може бути застосований в системах реального часу.
The new efficient method of calculation of the line spectral frequencies (LSF) is proposed. The method is based on a developed algorithm of full numerical solution of transcendental equation having no multiple roots. This algorithm is composed of two parts - location of intervals containing a single root and folowing refinement of root's value by one of standard rootfinding procedures. Efficiency of different modifications of the proposed LSF calculation method is verified on real speech signals. Two approaches to computation of LSF are considered - the direct solution of transcendental equations containing trigonometric functions and the solution of polynomial equations obtained by the series expansion in Chebyshev polynomials. The LSF's ordering property is used for decreasing the computational expenses. In opposite to majority of existing LSF computation algorithms, the proposed method provides arbitrary high accuracy and guarantees the stability of a corresponding autoregressive filter. It is shown that the developed method can be applied in real-time processing systems.
|
| first_indexed | 2025-12-07T13:39:41Z |
| format | Article |
| fulltext |
ISSN 1028 -7507 Акустичний вiсник. 2002. Том 5, N 4. С. 38 – 50
УДК 621.391.266
НОВЫЙ МЕТОД ВЫЧИСЛЕНИЯ ЛИНЕЙНЫХ
СПЕКТРАЛЬНЫХ ЧАСТОТ РЕЧЕВЫХ СИГНАЛОВ,
ОСНОВАННЫЙ НА УНИВЕРСАЛЬНОМ АЛГОРИТМЕ
РЕШЕНИЯ ТРАНСЦЕНДЕНТНЫХ УРАВНЕНИЙ
В. Ю. СЕ МЕНО В
Институт гидромеханики НАН Украины, Киев
Получено 1.11.2002
Предложен новый эффективный метод вычисления линейных спектральных частот (ЛСЧ) речевых сигналов, кото-
рый основан на разработанном алгоритме полного численного решения трансцендентных уравнений, не имеющих
кратных корней. Принципиально алгоритм состоит из двух частей – выделения отрезков, содержащих единствен-
ный корень, и последующего нахождения корней с помощью одной из стандартных итерационных процедур. Эффе-
ктивность различных модификаций предложенного метода поиска ЛСЧ проверена на реальных речевых сигналах.
Исследованы два подхода к нахождению ЛСЧ – прямое решение трансцендентных уравнений относительно триго-
нометрических функций и решение полиномиальных уравнений, полученных в результате разложения по чебышев-
ским полиномам. Свойство упорядоченности ЛСЧ использовано для снижения вычислительных затрат. В отличие
от большинства существующих методов определения ЛСЧ, предложенный метод обладает произвольно высокой
точностью вычислений и гарантирует устойчивость соответствующего авторегрессионного фильтра. Показано, что
данный метод может быть применен в системах реального времени.
Запропоновано новий ефективний метод обчислення лiнiйних спектральних частот (ЛСЧ) мовних сигналiв, який
базується на розробленому алгоритмi повного чисельного розв’язку трансцендентних рiвнянь, що не мають кра-
тних коренiв. Принципово алгоритм складається з двох частин – видiлення вiдрiзкiв, якi мiстять єдиний корiнь,
та подальшого знаходження кореня за допомогою однiєї зi стандартних iтерацiйних процедур. Ефективнiсть рiзних
модифiкацiй запропонованого методу пошуку ЛСЧ перевiрено на реальних мовних сигналах. При цьому дослiдже-
нi два пiдходи до знаходження ЛСЧ – пряме розв’язання трансцендентних рiвнянь вiдносно тригонометричних
функцiй та розв’язання полiномiальных рiвнянь, отриманих внаслiдок розкладу за Чебишевськими полiномами.
Властивiсть упорядкованостi ЛСЧ використано для зниження обчислювальних витрат. На вiдмiну вiд бiльшостi
iснуючих методiв обчислення ЛСЧ, запропонований метод забезпечує довiльно високу точнiсть обчислень та гаран-
тує стiйкiсть вiдповiдного авторегресiйного фiльтра. Показано, що даний метод може бути застосований в системах
реального часу.
The new efficient method of calculation of the line spectral frequencies (LSF) is proposed. The method is based on a
developed algorithm of full numerical solution of transcendental equation having no multiple roots. This algorithm is
composed of two parts – location of intervals containing a single root and folowing refinement of root’s value by one of
standard rootfinding procedures. Efficiency of different modifications of the proposed LSF calculation method is verified
on real speech signals. Two approaches to computation of LSF are considered – the direct solution of transcendental
equations containing trigonometric functions and the solution of polynomial equations obtained by the series expansion
in Chebyshev polynomials. The LSF’s ordering property is used for decreasing the computational expenses. In opposite to
majority of existing LSF computation algorithms, the proposed method provides arbitrary high accuracy and guarantees
the stability of a corresponding autoregressive filter. It is shown that the developed method can be applied in real-time
processing systems.
ВВЕДЕНИЕ
Развитие современных приложений цифровой
связи, таких как сотовая и IP-телефония, приве-
ло к необходимости разработки высокоэффектив-
ных алгоритмов кодирования речи, работающих
на все более низких скоростях (обеспечивающих
большую степень сжатия речевой информации).
История алгоритмов кодирования речи начинае-
тся с 1940-х годов, когда появились первые воко-
деры [1]. Рассмотрим основные причины, ведущие
к необходимости сжатия речевых сигналов.
1. Ограниченная пропускная способность типо-
вых каналов связи. Стоимость цифровых ка-
налов связи обычно пропорциональна коли-
честву передаваемых по ним цифровых дан-
ных. Хотя стоимость этих средств с каждым
годом уменьшается, потребность в них еще бо-
лее увеличивается.
2. Необходимость криптографической защиты
информации. Кодирование речи, особен-
но низкоскоростное (со скоростью менее
4 кбит/с), открывает широкие возможности
для шифрования передаваемой информации.
Только преобразовав речь в цифровую форму
и применив шифрование, можно гарантиро-
ванно защититься от перехвата. Аналоговые
средства шифрования (скремблеры) дают
лишь временную защиту.
3. Необходимость компактного хранения рече-
вых сигналов. Стоимость цифровой памяти
38 c© В. Ю. Семенов, 2002
ISSN 1028 -7507 Акустичний вiсник. 2002. Том 5, N 4. С. 38 – 50
примерно пропорциональна количеству нака-
пливаемых данных. Стандартные алгоритмы
сжатия (Хафмена, Лемпеля – Зива и др.), ле-
жащие в основе популярных архиваторов zip
и arj, применительно к речевым сигналам да-
ют очень низкую степень сжатия (менее, чем
1.5÷2 раза).
Напомним вкратце основные понятия, связан-
ные с кодированием речи и ее передачей по ци-
фровым каналам связи.
Количество бит, необходимое для представления
одной секунды речевого сигнала, называют ско-
ростью кодирования. Как правило, под несжатым
речевым сигналом подразумевается его представ-
ление с помощью импульсно-кодовой модуляции
(ИКМ), при которой речь дискретизируется с ча-
стотой 8 кГц и оцифровывается по фиксированной
256-уровневой шкале, образуя скорость кодирова-
ния 64 кбит/с (отметим, что в мультимедийных
приложениях исходная скорость кодирования, как
правило, существенно более высокая).
Алгоритмы кодирования речи можно разбить на
три основные группы, в зависимости от степени
сжатия, которую они обеспечивают:
1) высокоскоростные (скорость кодирования
16÷64 кбит/c);
2) среднескоростные (4÷16 кбит/c);
3) низкоскоростные (менее 4 кбит/c).
Высокоскоростные методы сжатия речи, такие
как ИКМ, дифференциальная ИКМ (ДИКМ),
адаптивно-дифференциальная ИКМ (АДИКМ),
не используют специфические особенности речи и
могут быть применены для кодирования широкого
класса сигналов.
Методы среднескоростного и низкоскоростно-
го сжатия, важность которых в настоящее вре-
мя особенно высока, основаны на моделях рече-
образования. Наибольшее распространение полу-
чила авторегрессионная (АР) модель речеобразо-
вания [1 –3], в которой речевой сигнал моделиру-
ется, как результат прохождения управляющего
(возбуждающего) процесса через авторегрессион-
ный (полюсной) фильтр. Принципиально эта мо-
дель отображена на рис. 1.
Возбуждающий процесс моделирует поток воз-
духа на выходе голосовых связок человека. В дан-
ной модели он представляет собой белый шум в
случае произнесения глухих звуков (невокализо-
ванная речь) или последовательность импульсов,
идущих друг за другом с периодом, соответству-
ющим частоте колебания голосовых связок (вока-
лизованная речь).
Рис. 1. Авторегрессионная модель формирования
речевого сигнала
Работа полюсного фильтраH(z), моделирующе-
го форму голосового тракта в момент произнесе-
ния звука, может быть описана в разностной фор-
ме:
s(n) = −
p∑
k=1
aks(n − k) + gw(n), (1)
где s(n) – речевой сигнал; w(n) – возбужда-
ющий процесс; g – коэффициент усиления; ak,
k=1, 2, . . ., p – АР коэффициенты. Порядок АР
модели p выбирается, как правило, от 8 до 20. Оче-
видно, что повышение порядка модели позволяет
более точно моделировать спектральные характе-
ристики речи.
Основным свойством параметров АР модели яв-
ляется их относительно медленное изменение с те-
чением времени. Можно считать, что они остаются
неизменными на отрезках длиной 10÷30 мс (свой-
ство квазистационарности речевых сигналов).
Традиционно АР коэффициенты определяю-
тся с помощью методов линейного предсказа-
ния, в частности, автокорреляционного метода
(АКМ) [1, 2]. На использовании данной модели
речеобразования основано большинство средне- и
низкоскоростных методов сжатия речи. Как пра-
вило, отличие между этими алгоритмами состоит
лишь в способе кодирования возбуждающего про-
цесса.
Таким образом, задача кодирования речи ра-
збивается на две основные подзадачи: коди-
рование возбуждающего процесса (кодирование
источника) и кодирование АР параметров ak,
k=1, 2, . . ., p.
Однако непосредственное квантование АР ко-
эффициентов на практике не используется. Это
объясняется их чрезвычайно высокой спектраль-
ной чувствительностью. Небольшие ошибки кван-
тования приводят к относительно большим спе-
ктральным искажениям в восстанавливаемом ре-
чевом сигнале и даже могут вызвать неустойчи-
вость синтезирующего фильтра приемника. Кроме
В. Ю. Семенов 39
ISSN 1028 -7507 Акустичний вiсник. 2002. Том 5, N 4. С. 38 – 50
того, АР коэффициенты не имеют четких дина-
мических диапазонов изменения, что также серье-
зно затрудняет их квантование. Аналогичная про-
блема возникает в связи с задачей интерполяции
АР коэффициентов: как уже отмечалось, в систе-
мах кодирования речи вычисление и квантование
АР коэффициентов выполняется поблочно, на ин-
тервалах длиной от 10 до 30 мс. Столь медленное
обновление параметров приводит к резким измене-
ниям в АР коэффициентах на смежных фреймах,
вследствие чего наблюдаются “щелчки” и другие
заметные на слух нежелательные искажения. Для
решения этой проблемы в принимающих устрой-
ствах необходимо вводить линейную интерполя-
цию АР коэффициентов.
Непосредственная интерполяция АР коэффици-
ентов не может использоваться в силу тех же при-
чин, что и в задаче квантования. Поэтому АР па-
раметры перед кодированием обычно преобразу-
ются нелинейным образом в эквивалентный набор
параметров, например, в коэффициенты отраже-
ния или логарифмы отношений поперечных сече-
ний модели речевого тракта [2, 3]. Существенную
роль в последнее время играют также методы ве-
кторного квантования АР коэффициентов [3 –5].
Наиболее популярным способом кодирования
АР параметров в настоящее время становится их
однозначное преобразование в набор линейных
спектральных частот (ЛСЧ), квантование кото-
рых является наиболее эффективным по сравне-
нию с другими эквивалентными представлениями
АР модели.
Понятие ЛСЧ было впервые введено Итаку-
ра [6]. То, что ЛСЧ кодируют спектр речи бо-
лее эффективно, чем другие наборы параметров,
можно объяснить близостью их природы к приро-
де формантных частот [7]. Поэтому ЛСЧ могут
квантоваться с учетом особенностей восприятия
речи человеком. Кроме того, понятие о ЛСЧ тесно
связано с акустической моделью голосового трак-
та [8].
ЛСЧ применяются в американских федераль-
ных стандартах CELP (code excited linear predicti-
on, 4800 бит/с) [9], MELP (mixed excitation linear
prediction, 2400 бит/с) [10], стандарте CS-ACELP
(8000 бит/с) [11], используемого в IP-телефонии,
и многих других алгоритмах сжатия речи. Напри-
мер, в стандарте MELP речь разбивается на ка-
дры длиной 22.5 мс, каждый из которых кодиру-
ется 54-ю битами (результирующая скорость ко-
дирования 54×1000/22.5=2400 бит/с), из которых
34 бита отводится на кодирование десяти ЛСЧ, а
остальные – на возбуждающий процесс и коэффи-
циент усиления.
Кроме того, ЛСЧ продемонстрировали высокую
эффективность в задачах распознавания речи [12]
и идентификации диктора [13]. В работе [14] прои-
ллюстрировано применение ЛСЧ к решению про-
блемы очистки речи от шума.
Таким образом, определение ЛСЧ по задан-
ным АР коэффициентам ak, k=1, 2, . . . , p являе-
тся актуальной научно-технической задачей, име-
ющей важное прикладное значение. В то же вре-
мя, вычисление ЛСЧ, как будет показано, со-
пряжено со значительными вычислительными и
аппаратными затратами. Существующие методы
поиска ЛСЧ, как правило, являются результа-
том компромисса между количеством вычислений
и их точностью. Обычно приемлемое быстродей-
ствие обеспечивается за счет увеличения погре-
шности определения ЛСЧ. Это может приводить к
неустойчивости соответствующих авторегрессион-
ных фильтров, что сказывается на качестве и ра-
зборчивости восстанавливаемого речевого сигна-
ла. Вероятность таких сбоев особенно высока при
использовании АР моделей относительно высоких
порядков.
Цель данной работы – поиск более эффектив-
ных, по сравнению с известными, алгоритмов вы-
числения ЛСЧ. Основу предлагаемого подхода со-
ставляет развитый в работе универсальный метод
решения трансцендентных уравнений f(x)=0 для
непрерывно дифференцируемых функций, не име-
ющих кратных корней.
Предложенный метод обладает высокой точно-
стью вычислений и гарантирует устойчивость со-
ответствующего авторегрессионного фильтра. В
отличие от многих существующих методов, он не
требует никакой априорной информации о распо-
ложении ЛСЧ. Кроме того, точности определения
частот не зависят друг от друга и могут легко ре-
гулироваться. Показано, что данный метод может
быть применен в системах реального времени.
1. СВОЙСТВА ЛИНЕЙНЫХ СПЕКТРАЛЬ-
НЫХ ЧАСТОТ
Рассмотрим преобразование АР коэффициентов
ak, k=1, 2, . . ., p в набор ЛСЧ. Пусть задан отбе-
ливающий фильтр с характеристикой
A(z) = 1 +
p∑
k=1
akz
−k. (2)
Предположим, что этот фильтр является
минимально-фазовым, то есть все его нули
лежат внутри круга единичного радиуса (это все-
гда верно для АР коэффициентов, определенных
40 В. Ю. Семенов
ISSN 1028 -7507 Акустичний вiсник. 2002. Том 5, N 4. С. 38 – 50
с помощью АКМ) [1].
Введем в рассмотрение следующие симметри-
чный и асимметричный фильтры:
{
Fs(z) = A(z) + z−p−1A(z−1),
Fa(z) = A(z) − z−p−1A(z−1).
(3)
Предполагая, что порядок модели p являе-
тся четным числом (p=2M), получим, что
Fs(−1)=A(−1)−A(−1) = 0, т. е. Fs(z) имеет три-
виальный корень z=−1. Аналогично получаем,
что многочлен Fa(z) имеет тривиальный корень
z=1.
Деление полиномов (3) на сомножители, отвеча-
ющие за указанные корни, приводит к выражени-
ям
G1(z) =
Fs(z)
1 + z−1
,
G2(z) =
Fa(z)
1 − z−1
,
(4)
также являющимся многочленами, каждый из ко-
торых можно представить в виде
Gm(z) =
p∑
k=0
g
(m)
k z−k, g
(m)
0 = g(m)
p = 1,
m = 1, 2.
(5)
Коэффициенты этих симметричных полиномов
могут быть вычислены по приводимым ниже ре-
куррентным зависимостям:
• полином G1(z):
g
(1)
k =
−1+a1+ap,
k=1,
−g(1)
k−1+ak+ap+1−k,
k=2, . . . ,M,
g
(1)
p−k,
k=M+1, . . . , p−1;
(6)
• полином G2(z):
g
(2)
k =
1+a1−ap,
k=1,
g
(2)
k−1 + ak − ap+1−k,
k=2, . . . ,M,
g
(2)
p−k,
k=M+1, . . . , p−1.
(7)
Можно показать [16, 17], что полиномы G1(z)
и G2(z) обладают рядом следующих важных
свойств.
1. Все их корни расположены на единичной
окружности, то есть имеют вид zk =eiωk . Ар-
гументы корней полиномов G1(z) и G2(z), ле-
жащие в диапазоне (0;π), называются линей-
ными спектральными частотами (ЛСЧ) ωk,
соответствующими полиному (2). Количество
ЛСЧ в точности равно p, поскольку каждый
из многочленов (4) имеет p=2M корней на
единичной окружности, ровно половина из ко-
торых лежит в верхней полуплоскости.
2. Если обозначить как ω(1)
1 , ω(1)
2 , . . . , ω(1)
M ЛСЧ,
соответствующие G1(z), а ω(2)
1 , ω(2)
2 , . . . , ω(2)
M –
ЛСЧ, соответствующие G2(z), то оказывае-
тся, что они перемежаются:
ω
(1)
1 <ω
(2)
1 <ω
(1)
2 <ω
(2)
2 <. . .<ω
(1)
M <ω
(2)
M (8)
(отметим, что все неравенства здесь строгие,
т. е. не существует ЛСЧ, совпадающих между
собой). В дальнейшем мы будем именовать
это свойство упорядоченностью ЛСЧ.
3. Одновременное выполнение первых двух
свойств является необходимым и достато-
чным условием того, что корни многочлена
A(z) находятся внутри круга единичного ра-
диуса. Таким образом, если выбранная схема
квантования ЛСЧ сохраняет первые два свой-
ства, то этим гарантируется устойчивость син-
тезирующего фильтра 1/A(z).
Для получения компактных уравнений относи-
тельно ЛСЧ преобразуем многочлены (4), заменив
в них z на eiωk :
Gm(z)=
2M∑
k=0
g
(m)
k z−k =e−iMω×
×
[ M∑
k=0
g
(m)
k
(
ei(M−k)ω+e−i(M−k)ω
)
+g
(m)
M
]
=
= e−iMω
[ M∑
k=0
2g
(m)
k cos(M−k)ω+g
(m)
M
]
=
= e−iMω
M∑
k=0
r
(m)
k cos kω, m=1, 2,
(9)
где
r
(m)
k =
g
(m)
M , k = 0,
2g
(m)
M−k, k = 1, . . . ,M.
(10)
В. Ю. Семенов 41
ISSN 1028 -7507 Акустичний вiсник. 2002. Том 5, N 4. С. 38 – 50
Таким образом, задача поиска ЛСЧ сводится к ре-
шению относительно ω двух уравнений вида
M∑
k=0
r
(m)
k cos(kω) = 0, m = 1, 2, (11)
где коэффициенты r
(m)
k связаны с параметрами
исходной АР модели соотношениями (6), (7), (10).
Трансцендентное уравнение (11) может быть
преобразовано к полиномиальному путем заме-
ны x=cosω. Значения для кратного аргумента
(cos nω) могут быть выражены с помощью че-
бышевских полиномов
Tn(x) = cos(ω) = cos(n arccos(x)) =
n∑
k=0
t
(n)
k xn−k.
Известно [18], что полиномы Чебышева могут
быть рассчитаны по рекуррентным соотношениям
Tk(x) = 2xTk−1(x) − Tk−2(x),
k = 2, 3, . . . :
(12)
T0(x) = 1, T1(x) = x,
T2(x) = 2x2 − 1, T3(x) = 4x3 − 3x,
T4(x) = 8x4 − 8x2 + 1 . . .
Таким образом, уравнение (11) может быть за-
писано в виде
r
(m)
0 +
M∑
k=1
r
(m)
k Tk(x) = 0, m = 1, 2. (13)
С учетом рекуррентных соотношений (12) пре-
образуем уравнение (13) к виду
M∑
k=0
r
′(m)
k xM−k = 0, m = 1, 2. (14)
После выполнения описанных преобразований
получаем пару вещественных полиномов, корни
которых:
1) различны;
2) перемежаются между собой;
3) действительны и лежат в диапазоне [−1; 1].
Если определены корни уравнения (14) – x
(1)
k ,
k=1, . . . ,M , соответствующие Fs(z), и x
(2)
k ,
k=1, . . . ,M , соответствующие Fa(z), – то ЛСЧ
могут быть вычислены с помощью обратного
нелинейного преобразования ω = arccos x.
Таким образом, проиллюстрировано наличие
двух следующих подходов к определению ЛСЧ.
1. Прямое решение уравнения (11). В рам-
ках существующих методов решения дан-
ной задачи отрезки, содержащие единствен-
ный корень, определяются путем вычисления
функции
R(eiω) = r0 +
M∑
k=1
rk cos kω
на большой сетке частот с помощью быстро-
го преобразования Фурье [15]. Такие мето-
ды имеют очевидный недостаток – заранее
неизвестен размер сетки, которую необходимо
взять, поскольку нули функции R(eiω) могут
находиться сколь угодно близко друг к дру-
гу. Слишком большой же размер сетки при-
водит к существенному увеличению вычисли-
тельных затрат.
2. Решение полиномиального уравне-
ния (14) с последующим применением
обратного нелинейного преобразования
для возврата в частотную область.
Существующие методы решения полученных
полиномиальных уравнений [7, 16, 17] можно
разделить на две подгруппы.
Типичным представителем первой из них яв-
ляется метод Кабала – Рамачандрана [7]. Как и в
случае уравнения (11), отрезки, содержащие един-
ственный корень, выявляются путем вычисления
значений полинома на большой (но фиксирован-
ной) сетке значений. Такая сетка вычисляется пу-
тем анализа ЛСЧ у достаточно большого количе-
ства дикторов. В статье [7] обсуждаются предель-
ные значения погрешностей этого метода. К не-
достаткам такого подхода следует отнести необхо-
димость исследования большого тестового объема
речевых данных для формирования эффективных
сеток для каждого отдельно взятого порядка АР
модели. Кроме того, следует ожидать ухудшения
производительности при работе с дикторами, ко-
торые не участвовали в исследованиях по необхо-
димому размеру сетки.
Еще одна подгруппа методов [16, 17] с приме-
нением чебышевских полиномов использует мето-
дологию последовательного понижения степени.
Определяется наибольший корень полинома, на
который он затем делится (с помощью, напри-
мер, модифицированной схемы Горнера [17]). У
полученного многочлена, степень которого мень-
ше исходной на единицу, опять определяется наи-
больший корень, на который затем делится мно-
гочлен. Так продолжается до получения много-
члена первой степени. Таким образом находятся
42 В. Ю. Семенов
ISSN 1028 -7507 Акустичний вiсник. 2002. Том 5, N 4. С. 38 – 50
все корни исходного полинома, которые затем пе-
реводятся с помощью нелинейного преобразова-
ния в частотную область. Зачастую, данная ите-
рационная процедура может быть остановлена по-
сле получения многочлена четвертой степени [17],
после чего применяются формулы Феррари для
точного определения корней [18]. Общей пробле-
мой указанного подхода является то, что числен-
ные ошибки, вводимые при делении полиномов на
приближенные значения корней, существенно ска-
зываются на точности определения последующих
корней. Такое накопление ошибок особенно суще-
ственно при работе с полиномами высоких поряд-
ков [15], что может привести к неустойчивости
используемых АР фильтров [16].
Как видно из вышеизложенного, существующие
методы поиска ЛСЧ обладают рядом недостатков.
Основной проблемой “сеточных методов” является
выбор необходимого размера сетки. При использо-
вании методов последовательного понижения сте-
пени накапливающаяся погрешность определения
ЛСЧ может приводить к неустойчивости соответ-
ствующего АР фильтра, что сказывается на каче-
стве и разборчивости восстанавливаемого речево-
го сигнала. Вероятность таких сбоев повышается
при возрастании порядка используемой АР моде-
ли [15].
В следующем разделе предложен универсаль-
ный метод решения трансцендентных уравне-
ний, который затем применен к решению уравне-
ний (11) и (14). Кроме того, показано, что свойство
упорядоченности ЛСЧ (8) может быть эффектив-
но использовано для сокращения количества вы-
числений при их поиске.
Отметим, что обратное преобразование от ЛСЧ
к АР коэффициентам является существенно более
простой процедурой. Прямой способ решения этой
задачи – восстановить коэффициенты r′k по кор-
ням уравнения (14) и произвести действия, обра-
тные формулам (6), (7) (10). Быстрый и эффе-
ктивный способ проведения этой процедуры пред-
ставлен в работе [7].
2. УНИВЕРСАЛЬНЫЙ МЕТОД РЕШЕНИЯ
ТРАНСЦЕНДЕНТНЫХ УРАВНЕНИЙ
В данном разделе предлагается метод полного
численного решения произвольных трансценден-
тных уравнений вида f(x)=0. Единственным его
ограничением является непрерывная дифферен-
цируемость функции f(x) и отсутствие у нее кра-
тных корней. Данный алгоритм всегда гарантиру-
ет сходимость ко всем корням трансцендентного
уравнения и не требует априорной информации об
их расположении. Кроме того, погрешности опре-
деления корней независимы друг от друга.
2.1. Вспомогательные утверждения
Прежде чем перейти к изложению сути алгорит-
ма, рассмотрим ряд вспомогательных утвержде-
ний.
Нас интересует нахождение всех корней урав-
нения f(x)=0 на отрезке X=[a; b]. Предположим,
что известна константа Mj , ограничивающая мо-
дуль j-ой производной данной функции:
sup
x∈[a;b]
f(x) ≤Mj . (15)
Рассмотрим конкретные примеры.
1. Для уравнения (11) ограничение j-го порядка
имеет вид
Mj =
M∑
k=0
kj |rk|. (16)
2. Очевидно, для полинома (14) ограничения на
отрезке [−1; 1] могут быть выбраны как
Mj =
M−j∑
k=0
(M − k)(M − k − 1) × . . .
. . .× (M − k − j + 1)|r′k|.
(17)
Рассмотрим два простых утверждения.
Лемма 1. Если на отрезке [c; d]⊂X для некото-
рого j выполняется неравенство
f [0.5(c+ d)] +
j−1∑
k=1
|f (k)[0.5(c+ d)]|(d− c)k
2kk!
+
+
Mj (d− c)j
2jj!
< 0
или
f [0.5(c+ d)]−
j−1∑
k=1
|f (k)[0.5(c+ d)]|(d− c)k
2kk!
−
−Mj(d− c)j
2jj!
> 0,
то функция f(x) не имеет корней на [c; d].
Лемма 2. Если на отрезке [c; d]⊂X для некото-
рого j выполняется неравенство
f ′[0.5(c+d)]+
j−1∑
k=2
|f (k)[0.5(c+d)]|(d−c)k−1
2k−1(k−1)!
+
+
Mj(d−c)j−1
2j−1(j−1)!
<0
В. Ю. Семенов 43
ISSN 1028 -7507 Акустичний вiсник. 2002. Том 5, N 4. С. 38 – 50
или
f ′[0.5(c+d)]−
j−1∑
k=2
|f (k)[0.5(c+d)]|(d−c)k−1
2k−1(k−1)!
−
−Mj(d−c)j−1
2j−1(j−1)!
>0,
то функция f ′(x) не имеет корней на [c; d].
Доказательство лемм дано в приложении.
С помощью приведенных лемм всегда мож-
но проанализировать поведение функций f(x) и
f ′(x) на произвольном отрезке [c; d]. При этом для
функции f(x) возможны две ситуации:
1) f(x) не имеет корней на [c; d];
2) однозначного ответа о знакопостоянстве f(x)
дать нельзя, т. е. ситуация является неопреде-
ленной.
Аналогично имеем две возможных ситуации для
производной f ′(x):
1) f ′(x) не имеет корней на [c; d], т. е. функция
f(x) монотонна на [c; d],
2) ситуация является неопределенной.
Число j, фигурирующее в условиях лемм 1 и 2, в
дальнейшем будем называть порядком аппрокси-
мации. Его выбор зависит от специфики решае-
мой задачи и, как будет показано далее, являе-
тся решающим фактором, влияющим на величину
вычислительных затрат алгоритма. В данной ра-
боте мы ограничимся рассмотрением случая, ко-
гда порядки аппроксимации функции и производ-
ной совпадают.
2.2. Описание алгоритма
С помощью лемм, сформулированных в пре-
дыдущем разделе, проанализируем поведение
функций f(x) и f ′(x) на исходном отрезке [a; b].
Возможны следующие случаи.
1. f(x) не имеет корней на [a; b].
2. Ситуация для f(x) является неопределенной,
но f ′(x) не имеет корней на [a; b], то есть f(x)
монотонна на [a; b]. Тогда наличие корня на
отрезке можно определить по знаку выраже-
ния f(a)f(b). Если f(a)f(b)>0, то корней на
отрезке [a; b] нет. В противном случае f(x)
имеет один корень на данном интервале, ко-
торый может быть определен любым мето-
дом поиска единственного корня функции на
отрезке.
3. Если ситуация является неопределенной и в
случае с f(x), и в случае с f ′(x), то описанные
в предыдущем пункте действия выполняются
для отрезков [a; 0.5(a+b)], [0.5(a+b); b] и т. д.
В силу предположения об отсутствии кратных
корней (в реальных ситуациях это практически
всегда верно), на некотором этапе разбиения не
окажется отрезков, где одновременно для функ-
ции и ее производной ситуация является неопреде-
ленной. Таким образом, рекурсивное разбиение за-
вершится, и будут выделены все отрезки, содержа-
щие по одному корню функции f(x). На каждом
из таких отрезков точное значение корня опреде-
ляется с помощью одной из стандартных итераци-
онных процедур [18].
Отметим, что уточнение корня методами,
использующими деление на производную функ-
ции (например, Ньютона и Ньютона – Рафсона),
является гарантированно “безопасным”, посколь-
ку разработанный алгоритм обеспечивает знако-
постоянство производной на каждом из выделен-
ных отрезков. Кроме того, наличие вычисленных
производных в срединной точке отрезка позволяет
без дополнительных затрат эффективно выбрать
начальное приближение.
Блок-схема, соответствующая данной процеду-
ре, приведена на рис. 2. Алгоритму решения соот-
ветствует дерево конечной длины, в конечных пун-
ктах которого находятся отрезки, для которых си-
туации для f(x) и f ′(x) не являются одновремен-
но неопределенными. Важнейшая характеристика
данного алгоритма, указывающая на скорость его
работы – количество рекурсивных разбиений исхо-
дного отрезка. Эта величина существенно зави-
сит от порядков аппроксимации, выбранных для
функции и ее производной.
Существенная особенность выбранного метода
состоит в том, что с его помощью находится по-
следовательность корней трансцендентного урав-
нения в строго монотонном порядке (возрастаю-
щем или убывающем – в зависимости от порядка
выбора отрезков, получающихся в результате по-
ловинного деления). Кроме того, точности опре-
деления корней не зависят друг от друга и поэто-
му могут регулироваться, в зависимости от специ-
фики решаемой задачи. Это означает, что набор
ЛСЧ, определяемый с помощью данного алгорит-
ма, является монотонным и, согласно свойству 3
для ЛСЧ из раздела 1, всегда соответствует устой-
чивому АР фильтру.
44 В. Ю. Семенов
ISSN 1028 -7507 Акустичний вiсник. 2002. Том 5, N 4. С. 38 – 50
f(x)
[c,d]?
:
c:=a;d:=b;
f(c)f(d) ?
f(1)(x)
[c,d]?
“-”
“+”
f(x)
[c,d]?
f(c)f(d) ?
f(1)(x)
[c,d]?
“-”
“+”
f(x)
[c,d]?
f(c)f(d) ?
f(1)(x)
[c,d]?
“-”
“+”
……... ……...
c:=c; d:=0.5(c+d); c:=0.5(c+d);d:=d;
Рис. 2. Блок-схема алгоритма
3. ЭКСПЕРИМЕНТАЛЬНЫЕ РЕЗУЛЬТАТЫ
В предыдущих разделах показано, что, приме-
нительно к задаче поиска ЛСЧ, разработанный
метод решения трансцендентных уравнений обе-
спечивает произвольно высокую точность вычис-
лений и гарантирует устойчивость АР фильтра.
Теперь необходимо проверить эффективность пре-
дложенного подхода при работе с реальными ре-
чевыми сигналами. При этом будут исследованы
модификации данного метода, основанные как на
решении уравнений (11), так и на решении поли-
номиальных уравнений (14).
Эффективность различных модификаций пре-
дложенного метода была оценена для различных
четных порядков АР моделей: от 8 до 20. В ка-
честве тестовых сигналов использовались пятими-
нутные записи шести дикторов (четырех мужчин
и двух женщин), дискретизированные с частотой
fs =8000 Гц. Для каждого из исследуемых поряд-
ков АР модели выполнялась следующая последо-
вательность действий. Речевой сигнал разбивался
на отрезки длиной 20 мс (160 дискретных отсче-
тов). На каждом из них предварительно были
определены АР коэффициенты с помощью АКМ.
Для каждого из этих наборов затем подсчитыва-
лись ЛСЧ. При этом исследовались среднее число
элементарных арифметических операций для под-
В. Ю. Семенов 45
ISSN 1028 -7507 Акустичний вiсник. 2002. Том 5, N 4. С. 38 – 50
Табл. 1. Среднее количество операций в секунду, необходимое для вычисления ЛСЧ
посредством решения уравнения (11)
Порядок
аппроксимации
p = 8 p = 10 p = 12 p = 14 p = 16 p = 18 p = 20
2 129160 190820 271390 372020 507860 622480 765620
3 138260 196260 280080 372870 501260 599220 734310
4 159640 223370 317220 415550 556710 661580 808720
5 185620 254840 361660 473510 627930 738850 899740
Табл. 2. Среднее рекурсивных разбиений, необходимое для вычисления ЛСЧ
путем решения уравнения (11)
Порядок
аппроксимации
p = 8 p = 10 p = 12 p = 14 p = 16 p = 18 p = 20
2 13.21 16.33 20.33 25.29 32.09 35.45 40.11
3 10.87 12.57 15.69 18.49 23.16 24.44 27.70
4 10.39 11.98 14.83 17.12 21.24 22.42 25.36
5 10.25 11.68 14.54 16.86 20.55 21.53 24.27
счета всех ЛСЧ и среднее количество рекурсивных
разбиений исходного отрезка.
3.1. Определение ЛСЧ с помощью решения
уравнения (11)
Каждый набор АР параметров ak, k=1, 2, . . ., p
с помощью соотношений (7), (10) был преобра-
зован в коэффициенты r
(2)
k , k=0, . . . ,M . Для ре-
шения уравнения (11) на отрезке [0;π] в соответ-
ствии с алгоритмом, описанным в разделе 2, были
рассмотрены различные порядки аппроксимации
функции и ее производной. При порядке аппро-
ксимации, равном j, ограничение для модуля j-ой
производной определялось формулой (16). После
того, как определены отрезки, содержащие един-
ственный корень функции
f(x) = r
(2)
0 +
M∑
k=1
r
(2)
k cos kx,
точное значение корня находится с помощью
итерационного метода Ньютона [18]. В качестве
критерия остановки алгоритма выбрано условие
|f(x)|<10−6. Таким образом, определяются кор-
ни второго уравнения (11), которые являются ли-
нейными спектральными частотами ω2, ω4, . . . , ωp.
После этого по формулам (6) и (10) вычисляются
коэффициенты уравнения (11), соответствующие
полиному Fs(z). Заметим, что выполнять поиск
отрезков, содержащих единственный корень, нет
необходимости, поскольку таковыми являются ин-
тервалы [0;ω2], [ω2;ω4], . . . , [ωp−4;ωp−2], [ωp−2;ωp]
(в силу свойства упорядоченности (8)). Значения
оставшихся частот ω1, ω3, . . . , ωp−1 определялись
методом Ньютона. В том случае, если на неко-
торой итерации процедура выходила за преде-
лы исходного интервала (такая ситуация встреча-
лась очень редко), точное значение корня опре-
делялось методом ложного положения (результат
работы которого на каждой итерации гаранти-
рованно остается в пределах анализируемого ин-
тервала). Следует отметить, что описанная лока-
лизация ЛСЧ с помощью полинома Fa(z) оказа-
лась более эффективной с точки зрения вычисли-
тельных затрат, по сравнению с полиномом Fs(z).
Это может быть объяснено различным характе-
ром распределения ЛСЧ, соответствующих Fs(z)
и Fa(z) [7,17].
Указанная процедура выполнялась на всех
фреймах тестового речевого сигнала. Средние зна-
чения количества операций в секунду приведены в
табл. 1, а средние значения количества рекурсив-
ных разбиений исходного отрезка [0;π] – в табл. 2.
Для каждого порядка АР модели p рассмотрены
порядки аппроксимации от 2 до 5.
Как видно из табл. 1, оптимальный порядок ап-
проксимации для значений p=8, 10, 12, 14 равен 2.
Для p=16, 18, 20 минимум вычислительных за-
трат достигается при аппроксимации третьего по-
рядка. Заметим, однако, что хотя дальнейшее по-
вышение порядка аппроксимации влечет за собой
46 В. Ю. Семенов
ISSN 1028 -7507 Акустичний вiсник. 2002. Том 5, N 4. С. 38 – 50
Табл. 3. Среднее количество операций в секунду, необходимое для вычисления ЛСЧ
путем решения уравнения (14)
Порядок
аппроксимации
p = 8 p = 10 p = 12 p = 14 p = 16 p = 18 p = 20
2 71100 166250 337520 655520 1238870 2297890 4240270
3 46340 87490 152220 256110 401240 648310 997360
4 48850 75390 127090 177250 267710 384650 538950
5 79490 124250 172030 235580 314110 422870
6 131110 177210 241920 315440 381240
7 185890 254220 329020 401640
8 265320 344520 422130
9 357580 440160
10 454550
Табл. 4. Сравнение предложенного алгоритма поиска ЛСЧ с методом Кабала – Рамачандрана
Метод Локализация корней ε = 10−3 ε = 10−6
Предложенный алгоритм + метод Ньютона 39750 64550 76550
Алгоритм Кабала – Рамачандрана 61050 107500 177000
Алгоритм Кабала – Рамачандрана + метод Ньютона 61050 74980 87420
уменьшение количества разбиений (см. табл. 2),
вычислительные затраты при этом начинают ме-
дленно возрастать. Это объясняется увеличением
количества вычислений в формулах, фигурирую-
щих в условиях лемм 1 и 2.
При наиболее распространенном порядке АР
модели p=10 максимальное зафиксированное чис-
ло разбиений составило 41, а порог в 25 рекурсив-
ных разбиений превышен лишь в 2.7 % всех случа-
ев. Следовательно, применение данного алгоритма
в приложениях реального времени не должно вно-
сить дополнительных задержек.
Из табл. 1 видно, что необходимое количество
элементарных операций в секунду составляет от
129160 при p=8 до 734310 при p=20. Таким обра-
зом, можно утверждать, что с точки зрения воз-
можностей современных средств сигнальной обра-
ботки реализация данного подхода не представля-
ет сложностей. При этом следует помнить, что вы-
числение ЛСЧ – наиболее ресурсоемкий этап ра-
боты большинства современных низкоскоростных
речепреобразующих устройств.
Отметим, что при подсчете среднего количе-
ства элементарных операций один вызов тригоно-
метрической функции считался как одна элемен-
тарная операция. Это объясняется тем, что на ста-
дии выделения отрезков, содержащих единствен-
ный корень, значения функций cos x и sinx мо-
гут браться из фиксированной таблицы (при реа-
лизации алгоритма на цифровом сигнальном про-
цессоре операции обращения к памяти и сложе-
ния/умножения имеют примерно одинаковый вес).
Необходимый размер такой таблицы составляет
примерно psup{Nd}, где sup{Nd} – величина, огра-
ничивающая сверху количество разбиений. Отме-
тим, что максимальное число разбиений, зафи-
ксированное для p=20, составило 42, т. е. доста-
точным оказался размер единой для всех поряд-
ков таблицы, равный 1000. На стадии же точного
вычисления корней количество вызовов тригоно-
метрических функций очень невелико. Например,
для p=10 его среднее значение равно всего 9980
в течение одной секунды, что составляет 5.2 % от
общего количества выполненных операций. Таким
образом, данный алгоритм выгодно отличается от
традиционных методов численного решения урав-
нения (11), основным недостатком которых явля-
лось именно большое количество вычислений три-
гонометрических функций [15].
Перечисленные факторы свидетельствуют о
том, что алгоритм, основанный на прямом реше-
нии уравнения (11) с помощью предложенного ме-
тода решения трансцендентных уравнений, может
быть применен в системах реального времени.
В. Ю. Семенов 47
ISSN 1028 -7507 Акустичний вiсник. 2002. Том 5, N 4. С. 38 – 50
3.2. Определение ЛСЧ с помощью решения по-
линомиального уравнения (14)
На каждом фрейме тестового речевого сигнала
набор АР параметров ak, k=1, 2, . . . , p преобразо-
вывался с помощью соотношений (7), (10), (12)
в коэффициенты r
′(2)
k уравнения (14), соответ-
ствующего полиному Fa(z). Для решения уравне-
ния (14) на отрезке [−1; 1] использовались ограни-
чения (17). После локализации отрезков, содержа-
щих корни функции
f(x) =
M∑
k=0
r
′(m)
k xM−k,
точные значения корней определялись точно так
же, как при решении уравнения (11). В каче-
стве критерия остановки алгоритма было выбрано
условие |f(x)|<10−6. После нахождения всех кор-
ней двух уравнений (14), соответствующих Fa(z)
и Fs(z), ЛСЧ вычислялись с помощью обратного
нелинейного преобразования ω=arccos x.
Средние оценки количества элементарных опе-
раций в секунду представлены в табл. 3. Для ка-
ждого порядка АР модели p рассмотрены поряд-
ки аппроксимации от 2 до p/2 (производные более
высоких порядков здесь равны нулю).
Из табл. 3 видно, что минимум вычислительных
затрат для каждого порядка АР модели достига-
ется при разных порядках аппроксимации. Опти-
мальный порядок аппроксимации монотонно сту-
пенчато возрастает по мере увеличения числа p.
Оптимальное количество элементарных операций,
выполняемых для вычисления ЛСЧ на протяже-
нии одной секунды речевого сигнала, составляет
от 46340 при p=8 до 381240 при p=20. Из приве-
денных данных видно, что алгоритм, основанный
на решении уравнения (14), может быть применен
в системах реального времени.
Сравнение табл. 1 и 3 показывает, что при p=20
и 8 вычислительные затраты при решении урав-
нений (14) для соответствующих оптимальных по-
рядков аппроксимации примерно в 1.9 и 2.8 раза
меньше, чем в случае применения подхода, осно-
ванного на решении (11). Кроме того, преимуще-
ством “полиномиального” подхода является отсут-
ствие вызовов тригонометрических функций.
Теперь сопоставим эффективность предложен-
ного алгоритма с сеточным методом Кабала –
Рамачандрана [7] при определении ЛСЧ для по-
рядка АР модели p=10 (именно этот порядок ча-
ще всего используется в алгоритмах средне- и
низкоскоростного сжатия речи). Метод Кабала –
Рамачандрана является одним из наиболее рас-
пространенных способов поиска ЛСЧ и использу-
ется в современных стандартах кодирования ре-
чи [11]. Заметим, что его применение требует зада-
ния шага сетки, равного минимально возможному
расстоянию между корнями уравнений (14). В ка-
честве этого параметра нами было выбрано реко-
мендуемое для порядка p=10 значение δ=0.02 [7].
Если два корня одного из полиномов (14) распо-
ложены ближе, чем на величину δ, алгоритм Ка-
бала – Рамачандрана оказывается неприменимым
(очевидно, что уменьшение δ приводит к увели-
чению вычислительных затрат).
Для объективности сравнения необходимо пе-
рейти к критерию завершения поиска корней
|xk−xk−1|<ε, где xk, xk−1 – приближенные зна-
чения корня, полученные на двух последователь-
ных итерациях. В табл. 4 представлены средние
количества операций, необходимых для реализа-
ции метода Кабала – Рамачандрана и метода, пре-
длагаемого в данной статье. Поскольку в алгори-
тме Кабала – Рамачандрана используется уточне-
ние корней с помощью метода половинного деле-
ния (для фиксированности количества операций),
то рассмотрена также его модификация, соответ-
ствующая уточнению корней методом Ньютона
(при значениях порога ε, равных 10−3 и 10−6), а
также вычислительные затраты, необходимые для
локализации отрезков, содержащих единственный
корень.
Среднее количество операций для локализа-
ции корней в методе Кабала – Рамачандрана, рав-
ное 61050, объясняется следующим образом. Не-
обходимое количество вызовов полиномиальной
функции составляет 2/δ+p+1=111 [7]. Вычис-
ление полинома 5-го порядка требует выполне-
ние 11-ти элементарных операций. Таким образом,
на каждом фрейме локализация корней занима-
ет 111×11=1221 операций. Поскольку на каждом
фрейме количество вычислений, требуемое для ра-
боты алгоритма Кабала – Рамачандрана, одинако-
во (это его главное свойство), то на одну секунду
приходится 1221×50=61050 операций.
Из табл. 4 видно, что преимущество предло-
женного подхода к поиску ЛСЧ перед методом
Кабала – Рамачандрана составляет 35 % опера-
ций при локализации корней, а также 40 % и
57 % операций при точностях вычисления корней
ε=10−3 и 10−6 соответственно. Также имеет место
выигрыш перед комбинацией алгоритма Кабала –
Рамачандрана и метода Ньютона. Заметим, одна-
ко, что для практической реализации метода в си-
стемах реального времени важно также знать ма-
ксимальное количество требуемых операций в еди-
ницу времени (в этом смысле алгоритм Кабала –
48 В. Ю. Семенов
ISSN 1028 -7507 Акустичний вiсник. 2002. Том 5, N 4. С. 38 – 50
Рамачандрана всегда имел преимущество перед
другими методами, так как его вычислительная
загрузка фиксирована). Поэтому при тестирова-
нии предложенного нами метода были установле-
ны максимальные количества вычислений, прихо-
дящееся на один фрейм, для локализации корней
и их вычисления с точностями ε=10−3 и 10−6. Эти
предельные значения составили 1206, 1798 и 2200
соответственно, что меньше аналогичных величин
для алгоритма Кабала – Рамачандрана (1221, 2150
и 3540).
Принципиальный недостаток большинства су-
ществующих подходов к задачам, требующим ре-
шения уравнений (полиномиальных или трансцен-
дентных), состоит в использовании фиксирован-
ных равномерных множеств точек, в которых ана-
лизируется поведение функции. Преимущество же
разработанного в данной работе метода объясня-
ется тем, что он использует неравномерную се-
тку точек, подбираемую адаптивно под анализи-
руемую функцию (размер сетки определяется ко-
личеством рекурсивных разбиений области опре-
деления функции).
ЗАКЛЮЧЕНИЕ
В статье рассмотрена проблема поиска линей-
ных спектральных частот, являющихся альтерна-
тивным представлением авторегрессионной моде-
ли.
Для решения этой задачи разработан уни-
версальный метод полного численного определе-
ния всех корней произвольного трансцендентно-
го уравнения. Принципиально данный метод со-
стоит из двух частей – выделения отрезков, содер-
жащих единственный корень, и последующего на-
хождения корней с помощью любого стандартно-
го итерационного алгоритма. Основными параме-
трами предложенного метода являются порядки
аппроксимации функции и ее производной. Важ-
ным показателем эффективности работы метода,
тесно связанным с его вычислительными затра-
тами, служит количество рекурсивных разбиений
исходного отрезка. Данный алгоритм всегда га-
рантирует сходимость к корням трансцендентного
уравнения и не требует никакой априорной инфор-
мации об их расположении. Точность определения
каждого из корней не зависит друг от друга и мо-
жет регулироваться, в зависимости от специфики
решаемой задачи.
Продемонстрировано применение различных
модификаций данного метода решения трансцен-
дентных уравнений к задаче поиска ЛСЧ. При
этом исследованы два традиционных подхода – ре-
шение трансцендентного уравнения относительно
тригонометрических функций и решение полино-
миального уравнения с последующим нелинейным
преобразованием его корней в ЛСЧ. Показано, что
данный метод обеспечивает произвольно высокую
точность определения ЛСЧ и гарантирует устой-
чивость соответствующего им АР фильтра.
В результате экспериментов, проведенных на ре-
альных речевых сигналах, установлены оптималь-
ные порядки аппроксимации для каждого из под-
ходов и их зависимости от порядков используемых
АР моделей. Для сокращения вычислительных
затрат было эффективно использовано свойство
упорядоченности ЛСЧ. Установлено, что вычисли-
тельные затраты при “полиномиальном” подходе
примерно в 2÷2.5 раза меньше затрат, чем при
“тригонометрическом”. Тем не менее “тригономе-
трический” подход характеризуется очень малым
количеством вызовов тригонометрических функ-
ций, что всегда являлось существенным недоста-
тком методов этого типа. Продемонстрировано со-
кращение вычислений, по сравнению с наиболее
широко используемым в настоящее время методом
Кабала – Рамачандрана.
Показано, что алгоритмы, развитые на основе
обоих обсуждаемых подходов к поиску ЛСЧ, мо-
гут быть применены в системах реального време-
ни.
ПРИЛОЖЕНИЕ
Доказательство леммы 1
Рассмотрим случай j=1. Согласно теореме Ла-
гранжа [18], для любой точки x отрезка [c; d]
выполняется следующее равенство:
f(x) = f(0.5(c + d)) + f ′(ξ)[x− 0.5(c+ d)]. (18)
Из соотношения (18) следует, что
f(0.5(c + d))−
− sup
ξ∈[c;d]
|f ′(ξ)| sup
ξ∈[c;d]
|x− 0.5(c+ d)| ≤
≤ f(x) ≤ f(0.5(c + d))+
+ sup
ξ∈[c;d]
|f ′(ξ)| sup
ξ∈[c;d]
|x− 0.5(c+ d)|.
(19)
Принимая во внимание, что
sup
ξ∈[c;d]
|x− 0.5(c+ d)| = 0.5(d− c),
В. Ю. Семенов 49
ISSN 1028 -7507 Акустичний вiсник. 2002. Том 5, N 4. С. 38 – 50
из неравенства (19) получаем
f(0.5(c + d)) − 0.5 sup
ξ∈[c;d]
|f ′(ξ)|(d− c) ≤
≤ f(x) ≤ f(0.5(c + d))+
+0.5 sup
ξ∈[c;d]
|f ′(ξ)|(d− c).
(20)
Сопоставив соотношение (20) с условиями леммы,
имеем
∀x ∈ [c; d] : f(x) < 0 или ∀x ∈ [c; d] : f(x) > 0,
что и требовалось доказать.
Отметим, что выбор в качестве “опорной” точки
0.5(c+d) обусловлен тем, что для любой другой
точки y∈ [c; d] имеет место соотношение
sup
x∈[c;d]
|x− y| > 0.5(d− c),
то есть неравенство (20) стало бы более слабым.
Доказательство леммы в случае j≥2 аналогич-
но приведенному выше. При его проведении сле-
дует применить разложение функции f(x) в ряд
Тейлора с записью остаточного члена в форме Ла-
гранжа.
Доказательство леммы 2 полностью аналогично
доказательству леммы 1.
1. Рабинер Л., Шафер Р. Цифровая обработка рече-
вых сигналов.– М.: Радио и связь, 1981.– 496 с.
2. Маркел Дж., Грей А. Линейное предсказание
речи.– М.: Cвязь, 1977.– С. 26–41.
3. Макхоул Дж., Русос C., Гиш Г. Векторное кванто-
вание при кодировании речи // ТИИЭР.– 1985.–
73.– С. 19–61.
4. Buzo A., Gray A. H., Gray R. M., Markel J. D.
Speech coding based on vector quantization // IEEE
Trans. Acoust. Speech Signal Proces.– 1980.– 28.–
P. 562–574.
5. Калюжный А. Я., Семенов В. Ю. Экономичный
метод очистки речи от шума, основанный на блоч-
ном представлении сигнала в пространстве состо-
яний и векторном квантовании // Акуст. вiсн.–
2002.– 4, N 3.– С. 28–34.
6. Itakura F. Line spectrum representation of linear
predictive coefficients of speech signals // J. Acoust.
Soc. Amer.– 1975.– 57, N 1, Suppl. 1.– P. S35.
7. Kabal P., Ramachandran R. P. The computation of
line spectral frequencies using Chebyshev polynomi-
als // IEEE Trans. Acoust. Speech Signal Proces.–
1980.– 28.– P. 562–574.
8. Pan J., Fischer T. R. Vector quantization of speech
line spectrum pair parameters and reflection coeffici-
ents // IEEE Trans. Speech Audio Proces.– 1998.–
6.– P. 106–115.
9. Campbell J., Welch V., Tremain T. An expandable
error-protected 4800 bps CELP coder (US federal
standard 4800 bps voice coder) // Proc. IEEE
Int. Conf. Acoust. Speech Signal Proces.– Glasgow,
1989.– P. 735–738.
10. McCree A. V., Barnwell T. P. A mixed excitati-
on LPC vocoder model for low bit rate speech cod-
ing // IEEE Trans. Speech Audio Proces.– 1995.– 4.–
P. 242–249.
11. Salami R. Design and description of CS-ASELP: a toll
quality 8 kb/s speech coder // IEEE Trans. Speech
Audio Proces.– 1998.– 6.– P. 116–128.
12. Paliwal K. A study of line spectrum pair frequenci-
es for speech recognition // Proc. IEEE Int. Conf.
Acoust. Speech Signal Proces.– New York, USA,
1988.– P. 485–488.
13. Liu C., Lin M.,Wang W., Wang H. A study of line
spectrum pair frequencies for speaker recognition //
Proc. IEEE Int. Conf. Acoust. Speech Signal Proces.–
Alburquerque, USA, 1990.– P. 277–280.
14. Hansen J., Clements M. Constrained iterative speech
enhancement with application to speech recogniti-
on // IEEE Trans. Acoust. Speech Signal Proces.–
1991.– 4.– P. 795–805.
15. Schmidt C. E., Rabiner L. R. A study of techniques
for finding the zeros of linear phase FIR digital fi-
lters // IEEE Trans. Acoust. Speech Signal Proces.–
1977.– 25.– P. 96–98.
16. Rothweiler J. A rootfinding algorithm for line spectral
frequencies // Proc. IEEE Int. Conf. Acoust. Speech
Signal Proces.– Phoenix, USA, 1999.– P. 661–664.
17. Wu C.-H., Chen J.-H. A novel two-level method
for the computation of LSP frequencies using
a decimation-in-degree algorithm // IEEE Trans.
Speech Audio Proces.– 1997.– 5.– P. 106–115.
18. Корн Г., Корн Т. Справочник по математике для
научных работников и инженеров.– М.: Наука,
1977.– 832 с.
50 В. Ю. Семенов
|
| id | nasplib_isofts_kiev_ua-123456789-915 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1028-7507 |
| language | Russian |
| last_indexed | 2025-12-07T13:39:41Z |
| publishDate | 2002 |
| publisher | Інститут гідромеханіки НАН України |
| record_format | dspace |
| spelling | Семенов, В.Ю. 2008-07-08T13:52:12Z 2008-07-08T13:52:12Z 2002 Новый метод вычисления линейных спектральных частот речевых сигналов, основанный на универсальном алгоритме решения трансцендентных уравнений / В.Ю. Семенов // Акуст. вісн. — 2002. — Т. 5, N 4. — С. 38-50. — Бібліогр.: 18 назв. — рос. 1028-7507 https://nasplib.isofts.kiev.ua/handle/123456789/915 621.391.266 Предложен новый эффективный метод вычисления линейных спектральных частот (ЛСЧ) речевых сигналов, который основан на разработанном алгоритме полного численного решения трансцендентных уравнений, не имеющих кратных корней. Принципиально алгоритм состоит из двух частей - выделения отрезков, содержащих единственный корень, и последующего нахождения корней с помощью одной из стандартных итерационных процедур. Эффективность различных модификаций предложенного метода поиска ЛСЧ проверена на реальных речевых сигналах. Исследованы два подхода к нахождению ЛСЧ - прямое решение трансцендентных уравнений относительно тригонометрических функций и решение полиномиальных уравнений, полученных в результате разложения по чебышевским полиномам. Свойство упорядоченности ЛСЧ использовано для снижения вычислительных затрат. В отличие от большинства существующих методов определения ЛСЧ, предложенный метод обладает произвольно высокой точностью вычислений и гарантирует устойчивость соответствующего авторегрессионного фильтра. Показано, что данный метод может быть применен в системах реального времени. Запропоновано новий ефективний метод обчислення лінійних спектральних частот (ЛСЧ) мовних сигналів, який базується на розробленому алгоритмі повного чисельного розв'язку трансцендентних рівнянь, що не мають кратних коренів. Принципово алгоритм складається з двох частин - виділення відрізків, які містять єдиний корінь, та подальшого знаходження кореня за допомогою однієї зі стандартних ітераційних процедур. Ефективність різних модифікацій запропонованого методу пошуку ЛСЧ перевірено на реальних мовних сигналах. При цьому досліджені два підходи до знаходження ЛСЧ - пряме розв'язання трансцендентних рівнянь відносно тригонометричних функцій та розв'язання поліноміальных рівнянь, отриманих внаслідок розкладу за Чебишевськими поліномами. Властивість упорядкованості ЛСЧ використано для зниження обчислювальних витрат. На відміну від більшості існуючих методів обчислення ЛСЧ, запропонований метод забезпечує довільно високу точність обчислень та гарантує стійкість відповідного авторегресійного фільтра. Показано, що даний метод може бути застосований в системах реального часу. The new efficient method of calculation of the line spectral frequencies (LSF) is proposed. The method is based on a developed algorithm of full numerical solution of transcendental equation having no multiple roots. This algorithm is composed of two parts - location of intervals containing a single root and folowing refinement of root's value by one of standard rootfinding procedures. Efficiency of different modifications of the proposed LSF calculation method is verified on real speech signals. Two approaches to computation of LSF are considered - the direct solution of transcendental equations containing trigonometric functions and the solution of polynomial equations obtained by the series expansion in Chebyshev polynomials. The LSF's ordering property is used for decreasing the computational expenses. In opposite to majority of existing LSF computation algorithms, the proposed method provides arbitrary high accuracy and guarantees the stability of a corresponding autoregressive filter. It is shown that the developed method can be applied in real-time processing systems. ru Інститут гідромеханіки НАН України Новый метод вычисления линейных спектральных частот речевых сигналов, основанный на универсальном алгоритме решения трансцендентных уравнений The new method of line spectral frequencies calculation based on the universal algorithm of solution of transcendental equations Article published earlier |
| spellingShingle | Новый метод вычисления линейных спектральных частот речевых сигналов, основанный на универсальном алгоритме решения трансцендентных уравнений Семенов, В.Ю. |
| title | Новый метод вычисления линейных спектральных частот речевых сигналов, основанный на универсальном алгоритме решения трансцендентных уравнений |
| title_alt | The new method of line spectral frequencies calculation based on the universal algorithm of solution of transcendental equations |
| title_full | Новый метод вычисления линейных спектральных частот речевых сигналов, основанный на универсальном алгоритме решения трансцендентных уравнений |
| title_fullStr | Новый метод вычисления линейных спектральных частот речевых сигналов, основанный на универсальном алгоритме решения трансцендентных уравнений |
| title_full_unstemmed | Новый метод вычисления линейных спектральных частот речевых сигналов, основанный на универсальном алгоритме решения трансцендентных уравнений |
| title_short | Новый метод вычисления линейных спектральных частот речевых сигналов, основанный на универсальном алгоритме решения трансцендентных уравнений |
| title_sort | новый метод вычисления линейных спектральных частот речевых сигналов, основанный на универсальном алгоритме решения трансцендентных уравнений |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/915 |
| work_keys_str_mv | AT semenovvû novyimetodvyčisleniâlineinyhspektralʹnyhčastotrečevyhsignalovosnovannyinauniversalʹnomalgoritmerešeniâtranscendentnyhuravnenii AT semenovvû thenewmethodoflinespectralfrequenciescalculationbasedontheuniversalalgorithmofsolutionoftranscendentalequations |