СПОСОБЫ ВЫЧИСЛЕНИЯ ЛИНЕЙНЫХ СПЕКТРАЛЬНЫХ ЧАСТОТ

METHODS FOR CALCULATION OF THE LINEAR SPECTRAL FREQUENCIES

Andrey Korsunskiy

candidate of Engineering, Chief Specialist at FRPC JSC “RPA “Mars”,

Russia, Ulyanovsk

Tatiana Maslennikova

candidate of Engineering, Head of R&D Laboratory at FRPC JSC “RPA “Mars”,

Russia, Ulyanovsk

Aleksey Boyko

adjutant at the Military Communications Academy named after S.M. Budenniy,

Russia, St. Petersburg

Andrey Popov

candidate of Engineering , Professor at the Military Communications Academy named after S.M. Budenniy,

Russia, St. Petersburg

АННОТАЦИЯ

Проблема вычисления линейных спектральных частот (ЛСЧ) возникла в середине 70-х годов прошлого века и остаётся актуальной по настоящее время в различных речевых технологиях. ЛСЧ обычно определяются из коэффициентов линейного предсказания (КЛП) и их расчет должен быть выполнен в реальном времени. Вычисление ЛСЧ это только одна из функций реализуемых кодеком.

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

ABSTRACT

The problem of calculation of the linear spectral frequencies (LSF) emerged in the middle of 70s of the XX century and currently remains relevant in various speech technologies. LSF are usually determined from the linear prediction coefficients (LPC) and their calculation must be performed in real time. Therefore, the techniques that reduce the complexity of this procedure are very interesting. Computational procedures of LSFs using the quotient-difference scheme, cepstral domain interpretations of LSF, the modified method Newton’s are considered in the article. A brief analysis their efficiency, complexity and convergence.

Ключевые слова: Кодирование речи, линейное предсказание, коэффициенты линейного предсказания, линейные спектральные частоты.

Keywords: Speech coding, linear prediction, linear prediction coefficients, line spectral frequencies.

Введение

Кодирование речи на основе метода линейного предсказания (Linear Predictive Coding – LPC) заключается в том, что по линии связи передаются не параметры речевого сигнала, а параметры некоторого фильтра, в определенном смысле эквивалентного голосовому тракту, и параметры сигнала его возбуждения (тон/шум). В процессе покадровой адаптивной фильтрации рассчитывается нерекурсивный фильтр линейного предсказания (ЛП), параметры которого  называются КЛП. Эти коэффициенты полностью описывают состояние фильтра-предсказателя и могли бы использоваться для восстановления фильтра на приёме. Однако многочисленные исследования показали невозможность непосредственной передачи КЛП по каналу связи, и породили в свою очередь необходимость поиска математически-эквивалентных параметров фильтра-восстановителя.

Линейные спектральные частоты

ЛСЧ – параметры представления КЛП модели речевого тракта [5], и большинство речевых кодеков, используемых сегодня, основано на них. ЛСЧ широко используются в кодировании, синтезе и распознавании речи. Обычно ЛСЧ определяются напрямую из коэффициентов фильтра ЛП и их расчет должен быть выполнен в реальном времени. Вычисление ЛСЧ это только одна часть всей работы кодека, но большая часть процессорного времени, как правило, тратится именно на эту задачу. В связи с чем методы, снижающие сложность этой процедуры, представляют большой интерес, что в свою очередь определяет актуальность исследований в этом направлении.

Существует множество алгоритмов вычисления ЛСЧ. Лучшим выбором являются алгоритмы, которые предлагают компромисс между точностью и сложностью вычислений.

Проблема поиска ЛСЧ для полинома предсказания N-го порядка, может быть сведена к проблеме поиска корней пары полиномов степени N/2 с действительными корнями [1].

Полином фильтра ЛП  порядка  описывается как

где:  - КЛП порядка N. Из полинома (1) формируются симметричный  и антисимметричный  вспомогательные полиномы:

где: , а , и , а  и .

Полиномы (2,3) имеют тривиальные вещественные корни, не зависящие от коэффициентов линейного предсказания:  и , если N – четное, а также , если N – нечетное.

Для исключения тривиальных корней разделим  на , а  на  для четного N, или полином разделим на для нечетного N соответственно.

Удаление корней  дает

   - четное                                                         

 - нечетное                                                                    

Следует отметить, что в любом случае, полиномы и  четной степени, с корнями расположенными на единичной окружности.

ЛСЧ равны углам этих корней,  и поскольку фильтр ЛП устойчив, удовлетворяют условию:

Полиномы  и  могут быть определены с помощью действительных коэффициентов и  соответственно как:

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

где: .

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

получим тригонометрические полиномы вида:

где:

 и , .

В работе [11] полиномы и  преобразовываются в полиномы по , используя соотношения кратных дуг, в то время как в работе [6] использовали полиномы Чебышёва первого рода, после чего задача сводится к поиску простых вещественных корней обычных алгебраических полиномов:

Корни этих полиномов различны, вещественны, перемежаются и лежат в диапазоне [-1, +1].

Известно несколько методов решения алгебраических уравнений, большое количество из которых уже использовалось и проверялось при вычислении ЛСЧ (метод дихотомии, золотого сечения, метод Ньютона и т. д. [1]), однако компромисс между точностью и сложностью не всегда возможен [2; 3].

Существует несколько способов сочетающих в себе преимущества сразу нескольких методов. Самые известные из них представлены ниже.

Вычисление ЛСЧ с использованием схемы разделенных разностей

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

Действительный полином  степени  может быть определен вещественными коэффициентами  или его корнями , например:

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

Необходимые операции для одной итерации метода представлены графически на рис. 1.

Рисунок 1. Одна итерация схемы разделенных разностей

Каждая итерация дает новую оценку положения корня, основываясь на результатах прошлой итерации, и на основании вспомогательных переменных  как в выражении (14), (итерация обозначается как ).

Шаг алгоритма - разность, сопровождаемая шагом деления, который используется для обновления вспомогательных переменных:

Начальные значения  и  вычисляются с помощью коэффициентов :

Если условие (13) удовлетворено, то оценки  сходятся к фактическим корням, в то время как вспомогательные переменные  сходятся к нулю, т. е.:

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

Эта последняя замена гарантирует, что все корни  и  положительны, как того требует алгоритм разделенных разностей и удовлетворяют неравенству:

Коэффициенты  могут быть определены из , используя простой рекурсивный алгоритм, который требует только суммирование ( обозначает номер итерации, ).

где: начальные данные:

После последней итерации (), знаки нечетных коэффициентов меняются, в результате получаются желаемые :

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

Достоинства метода заключаются в том, что он позволяет вычислять все ЛСЧ одновременно. При низкой точности, метод еще более эффективен, чем например быстро сходящийся метод Ньютона-Рафсона, но в то же время исключительно прост. Для улучшения сходимости, можно использовать нелинейное преобразование ЛСЧ. Если полиномы и  преобразовать в полиномы  и  так, что , то это даст новое положение корней, которые лучше подходят для алгоритма. Это хорошо известное нелинейное преобразование по оси частот, предложенное Константинидисом и широко применяемое при синтезе БИХ-фильтров. Однако для этого преобразования необходимо определить оптимальный параметр сжатия , что требует дополнительных исследований речевых данных. Кроме того, так как все корни определяются одновременно, скорость сходимости будет определять корень с самой медленной сходимостью.

Вычисление ЛСЧ через интерпретацию в кепстральной области

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

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

где:  и  -е кепстральные коэффициенты симметричного и антисимметричного полиномов соответственно. Коэффициенты  и  в выражениях (24) и (25) могут быть выражены через  и  из выражений (2) и (3) через рекурсии описанные в [8]. Для этого берутся производные обоих выражений по , таким образом получаются кепстральные рекурсии:

В работе [8] обратное -преобразование  определяется как псевдо-кепстр. Так как , подставляя  и  в результате получаем:

где:  это -я ЛСЧ, которая преобразуется из полинома линейного предсказания -го порядка.

Также, мы можем получить разность между  и используя обратное – преобразование  и . Из определения в выражении (2), для – четного можно переписать как

Также можно переписать как

Так как  это обратное -преобразование , мы имеем

Кроме того, для - нечетного,

и

Таким образом, мы имеем

Здесь в выражении (28) и  в выражении (31) а также (34) относятся к кепстрам умноженного и разделенного полиномов соответственно и обозначаются как  и . Вычисления ЛСЧ из псевдо-кепстра происходит в кепстральной области и дает описание полной пары преобразований между ЛСЧ и псевдо-кепстром. ЛСЧ  получаются из псевдо-кепстра, .

Выражение (28) может быть переписано как

где: . Заметим, что кепстр умноженного полинома  идентичен псевдо кепстру определенному в [8].

Пусть  для . Тогда выражение (35) можно переписать как

где:  является -м полиномом Чебышёва первого рода. Пусть  для . Тогда мы можем получить следующее уравнение:

где:

и . Рассмотрим полином порядка  определяемого как

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

Подставляя выражение (37) в (40), мы получим равенство . ЛСЧ получают нахождением корней выражения (39). Используя рекурсию полученную в [8], равенство (57) можно переписать как

где:

Находя корни выражения (41), мы можем получить нулей которые обозначаются как . Наконец -тая ЛСЧ, , получается путем установки .

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

Вычисление ЛСЧ с использованием модифицированного метода Ньютона

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

.                                                                                     

Случай когда  – стандартная итерация Ньютона, в то время как случай когда  соответствует ускоренной процедуре, которая будет рассмотрена ниже.

Теорема 1. Пусть  действительный полином степени , все корни которого действительны, . Пусть  наибольший корень : . (Для , требуется чтобы ). Тогда для каждого , выполняется:

где:

Графическое пояснение теоремы на рис. 2. Здесь  начальное предположение корня, а  результат одного двойного шага итерации. В результате двойного шага итерации возможны три варианта: ,  и .

Рисунок 2. Графическое пояснение модифицированного метода Ньютона

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

Неравенство  гарантирует, что «проскакивание» локального корня может быть определено различием в знаках между  и .

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

Заключение

На сегодняшний день имеется множество способов вычисления ЛСЧ, с использованием различных алгоритмов и методов. Все они отличаются сложностью, сходимостью, требованиям к хранению вспомогательной информации, используемой при вычислениях. Во всех случаях задача вычисления ЛСЧ сводится к задаче решения алгебраических уравнений степени . Как известно из теоремы Н. Абеля алгебраические уравнения степени  в общем случае в радикалах не решаются, т.е. не существует формул, которые давали бы возможность вычислить корни уравнения по его коэффициентам. Однако, корни уравнения -й степени могут быть найдены с любой наперед заданной точностью при помощи итеративных алгоритмов, дающих на каждой итерации очередное приближение к решению: .

Все перечисленные выше методы вычисления ЛСЧ имеют квадратичную сходимость и асимптотическую сложность  с точностью до постоянного множителя. Однако не всегда сходятся глобально. Например метод Ньютона сходится локально. Для глобальной сходимости начальная точка должна быть достаточно близка к решению, т. е. находиться в, так называемой, области притяжения.

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

Симметричный P(z) и антисимметричный Q(z) полиномы представляют собой семейства ортогональных полиномов, подчиняющихся трёхчленной рекурсии вида:  при  В свою очередь, каждое такое семейство порождает трёхдиагональную симметричную матрицу Т, а само семейство  является семейством характеристических полиномов для этой матрицы:  где  – главная подматрица порядка j.

Тогда согласно теореме Коши о разделении, которая решает вопрос о связи собственных значений главной подматрицы с собственными значениями всей матрицы, имеем, что нули полинома с индексом j – 1 разделяют нули полинома с индексом j. Отсюда следует другой факт: указанная последовательность полиномов представляет собой последовательность Штурма.

Можно также показать, что в результате замены переменной z в полиномах P(z) и Q(z) на  при  формируются семейства полиномов такие, которым соответствуют трёхдиагональные матрицы  и . Собственные числа этих матриц оказываются корнями полиномов P(z) и Q(z), т. е. представляют собой линейные спектральные частоты , обладающие свойством чередуемости, или разделимости.

Таким образом, сведя задачу поиска ЛСЧ к вычислению собственных чисел матрицы можно снизить объём вычислений и повысить эффективность анализатора вокодера с линейным предсказанием.

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

Список литературы:

1. Ланнэ А.А., Улахович Д.А. Передача информации о состоянии фильтра-предсказателя с помощью спектральных пар // Радиоэлектроника и связь. – 1991. – № 1. – С. 12–17.
2. Попов А.С., Иваненко Р.В., Корсунский А.С. Влияние преднамеренных и непреднамеренных помех на обнаружение импульсных сверхширокополосных сигналов // Автоматизация процессов управления. – 2012. – № 3 (29). – С. 76–82.
3. Попов А.С., Киселев О.Н, Корсунский А.С. Обработка импульсных сверхширокополосных сигналов как задача обнаружения-различения // Автоматизация процессов управления. – 2012. – № 1 (27). – С. 67–70.
4. Atal B.S. Effectiveness of linear prediction characteristics of the speech wave for automatic speaker identification and verification. / J. Acoust. Soc. Amer. 55 (6) 1304–1312.
5. Itakura F. Line spectrum representation of linear predictive coefficients of speech signals," Journal of Acoustical Society of America, vol. 57, Р. 535, Apr.1975.
6. Kabal P., Ramachandr R.P. The computation of line spectral frequencies using Chebyshev polynomials. / IEEE Trans. Acoust. Speech Signal Proces. Vol. ASSP-34, № 6, 1986. P. 1419–1426.
7. Kim H.K., Choy S.H. Cepstral domain interpretations of the spectral frequencies. / Signal Processing 88 (2008) 756–760.
8. Kim H.K., Choi S.H., Lee H.S., On approximating line spectral frequencies to LPC cepstral coefficients, IEEE Trans, Acoust, Speech Audio Process. 8 (2) (2000) 195–199.
9. Petrinovic D. Calculation of the Line Spectrum Frequencies Using the Quotient-Difference Sheme. / IEEE Electrotechnical Conference, 2000. Melecon 2000. 10th Mediterranean, vol. 2, Р. 831–834.
10. Rothweiler J.A rootfinding algorithm for Line Spectral Frequencies. / Proc. Of IEEE IC ASSP99, Phoenix, Mar 1999, Vol. 2, Р. 661–664.
11. Soong F.K. and Juang B.H. Line spectrum pair (lsp) and speech data compression. / Proc. IEEE Int. Conf. on Acoustics, Speech, and Signal Processing, vol. 5, № 2, Р. 1.10.1–1.10.4, May 1984.