Математические модели и быстрые алгоритмы векторно-разностного кодирования цифровых речевых сигналов

ОБРАБОТКА ИНФОРМАЦИИ И УПРАВЛЕНИЕ X

УДК 621.3

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

К. Ю. Гагарин,

канд. техн. наук, докторант

Санкт-Петербургский государственный политехнический университет

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

In this paper we present a mathematical models and algorithms of vector-differential coding of speech signals based on multi-channel linear systems theory. Efficient algorithms of autocorrelation arrays computation through hyper complex Fourier transformations are also proposed.

Разностное кодирование относится к методам сжатия цифровых сигналов через кодирование их формы.

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

cf

где х{п) - п-й отсчет кодирования сигнала; х{п) -предсказанное значение для x{n)\ d{n) - погрешность предсказания.

На основе разностного уравнения(1)разработаны алгоритмы дельта-модуляции (двухуровневое квантование) и дифференциальной импульсно-ко-довой модуляции(многоуровневое квантование), а также алгоритмы с кратко- и долгосрочным предсказанием [1, 2].

В данной статье предложены математические модели векторно-разностного кодирования речевых сигналов с многоканальным линейным предсказанием, которые могут служить одним из способов теоретического обобщения других известных методов сжатия, например, с кратко- и долгосрочным предсказанием или с векторным квантованием [2].

В работах [3, 4] было предложено использовать для кодирования формы речевых сигналов векторно-разностные (ВР) уравнения

d[m) = X

где d(m), X(m) и X{m) - векторы соответственно погрешностей предсказания, последовательностей отсчетов сигнала {х(л)| и последовательности

предсказанных значений (х(л)}. Схема кодера ВР-кодирования (рис. 1) отличается от скалярно-разно-стных схем наличием Фв-блока формирования векторов и операции сложения-вычитания и квантования выполняются над векторами, т. е. над каждым элементом вектора отдельно и независимо друг от друга. Такой способ кодирования относится к кодированию формы сигналов, образованных одноименными х,{к) компонентами последовательности векторов {Х(Аг).}

Для случая, когда длина вектора определяется величиной периода основного тона речевого сигнала, на рис. 2 приведены графики сигналов {х1{к)} и |х(л)}-Приведенные примеры форм сигналов х.(к) и х(п) указывают на высокую степень корреляции между соседними отсчетами внутри и между векторов.

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

В работе [5] были предложены математические модели предсказателей в схемах ВР-кодирования в виде многоканальных линейных систем. Рассмотрим более подробно методы ВР-кодирования с учетом особенностей используемых математических моделей.

ВР-кодирование с независимой межка-нальной обработкой отсчетов сигнала

При независимой межканальной обработке отсчетов сигнала квантование и кодирование осуществляется для каждого /-го сигнала, по которому пе-

Рис. 1. Схема ВР-кодирования с адаптацией по шагу квантования и по длине вектора

ствляется для каждого /-го сигнала, по которому передается сигнал х((/с). При этом, согласно векторноразностному уравнению (2), предсказанные значения (х,(/с)) формируются независимо друг от друга.

Для определения вектора Хт(к) предсказанных значений кодируемого вектора Х(к) можно записать векторно-матричное разностное уравнение

Хт(к) = '£от{1)Х(к-1), /=1

где от(/) = сПад{а,(/)}™~1 - диагональная матрица коэффициентов предсказания; Х{к - /) - вектор квантованных значений кодируемого сигнала. Для р = 1 выражение может быть записано в виде

Хт(к) = От(1 )Х(к - 1),

где От(1) = 1т - единичная матрица.

Для/-го сигнала (хДАг)} являются справедливыми известные соотношения [6], определяющие каче-

а)

б)

в)

150 х\(к) 100

50

1—I—!—Г * X

II

0 1 2 3 4 5 6 7 8 9 10 11 12

0 1 2 3 4 5 6 7

9 10 И 12

Рис. 2. Графики сигналов: а - х(п), п - 0,900; б - х^п), л = 0,13; в - х2(к), к = 0,12

ство кодирования. Например, отношение сигнал/ шум (С/Ш) можно записать через отношение дис-2

Персии погрешности предсказания к дисперсии

2

погрешности квантования ое.

(С/Ш), = /о|..

Для коэффициентов усиления в /-м канале имеем

ср, = <з% /<&г

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

При этом для определения оптимальных коэффициентов предсказания, представленных матрицей

о£>Ю = сИ ад{а«(/)}"\

можно, например, воспользоваться известным [6] соотношением, связывающим коэффициенты предсказания на у-м интервале времени с кратковременной автокорреляционной функцией

/=Гр я</»

/=1

которое может быть представлено в матричной форме

Йр = [Яр]ар,

где - вектор значений я[;)(у); [Яр] - автокорреляционная матрица; - вектор коэффициентов предсказания а5)(/).

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

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

ВР-кодирование с межканально-зависи-мым линейным предсказанием

При межканально-зависимом ВР-кодировании речевых сигналов в качестве математической модели предсказателя может выступать векторно-матричное уравнение

Хт

/ = 1

где Ат{1) = [сх,у(/)], /, у = 1, т - квадратная матрица коэффициентов предсказания.

Разностному уравнению (6) может быть сопоставлена структурная схема предсказателя (рис. 3), где входами являются компоненты х,{к - I) вектора Х(к-1), а выходами - компоненты х;(/с) вектора предсказанных значений х(/с), определяемые в виде скалярных произведений (а/(/), Х{к - /)) векторов а,(/) и Х{к - /).

При подстановке (6) в уравнение (2) выражение для вектора погрешности предсказания принимает вид

ОД = Х(М(7) /= 1

Оптимальные коэффициенты предсказания, заданные в форме матрицы Ат{1), можно определить из условия минимизации дисперсий а| элементов вектора д{!) посредством решения системы уравнений

дац

где о| = Е{д2(к)) = Е[(Х{к) - Х{к)2), £(•) - оператор осреднения.

При этом предполагается, что среднее ггц = 0.

Выполнив преобразования для каждого элемента с/Д/с), аналогичные скалярно-разностным алгоритмам кодирования, можно получить следующую векторно-матричную форму, связывающую коэффициенты предсказания с блочными корреляционными матрицами

ад=£4гдоя*г(/-/),

/71

У = 1 А

От последовательностной векторно-матричной формы (8) можно перейти к блочно-матричной форме, через которую будет задана система линей-

Х

ных уравнении, решаемых относительно оптимальных коэффициентов предсказания ау(/):

RP = RpAp’

где Rp - блочно-матричный вектор-столбец Rp=R'xxO)’ R’xx(2)’ •>R'xx(PY’ А{р) - блочно-матрич-ный вектор-столбец А'= А'{ 1), А'(2), ...,A'(py, Rp -блочно-теплицева корреляционная матрица [7]

Ro —

" ЯхкР)

я«

я«

^хх

,^хх

Ях*

2)

^хх

где Яхх(/с) = — ^ {Х(п + к) Х'(п)) - смещенная

W л=0

оценка многоканальной корреляционной матрицы

'і l

Г1 2Ік) r22

Гплік) Гт2

Г2тік)

rmn

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

Яхх

( *xx(V

I **x(2) Г

Раскрывая в уравнении (10) блоки-матрицы, получим

/гц

r2l

/11

r2l0) r220) r2l

ац

«и

Гц(1) /12(1) Л

r2l0) г220)

Г, 1(2) г12(2) г21(2) г22(2) }

11

Таким образом, от блочно-матричной формы (10) удалось перейти к двум обычным векторно-матричным формам представления систем линейных уравнений, для решения которых относительно коэффициентов предсказания «,/(/) можно применить метод Холецкого в обычной векторно-матричной форме.

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

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

Разностное кодирование с двумерным линейным предсказанием

При двумерном предсказании речевого сигнала х(/, п) уравнения разностного кодирования могут быть записаны в следующем виде:

с/(/, п) = х(/, п) — х(/, п),

где / = 1, т, п - 0, р - 1.

В этом случае в качестве математической модели предсказателя можно использовать двумерное разностное уравнение

pi-ip2-i

Х

/=1 /с—1

Несложно заметить, что модель (6) отличается от модели (12) лишь формой представления: модель (6) представлена в векторно-матричной форме, а модель (12) — в последовательностной форме.

Аналогичным образом отличаются корреляционные модели.

Для двумерного сигнала можно записать блочно-теплицевую автокорреляционную матрицу в виде

' Р\Р2

я*х

Я*х

я*х(0>

ftxx

Я*ЛРі~1) Я*х

где

Я^/с)

Гххік, 0)

гж{к, 1)

Гххік, 1) Гххік, 0)

Гххік, Р2-1) Осх^. Рг-2)

Гххік, Р2~1) Гххік, Р2- 2)

Гххік, 0)

г^Д/с, т) - коэффициенты двумерной корреляции.

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

Быстрые алгоритмы вычисления оценок апериодических автокорреляционных функций

Методы скалярно- и векторно-разностного кодирования с линейным предсказанием базируются на

решении системы линейных уравнений, заданной через автокорреляционную матрицу, относительно коэффициентов предсказания. В свою очередь, автокорреляционная матрица строится на основе апериодической автокорреляционной функции (АКФ), заданной в последовательностной форме:

N,-k-1

г

N1 л=0

где к = О, Л/-, - 1.

Выражение (13) характеризует смещенную оценку последовательности, которая может рассматриваться как стационарный в широком смысле случайный процесс. Согласно работе [7], использование смещенной оценки АКФ гарантирует положительную полуопределенность автокорреляционной матрицы, необходимую для разрешимости системы линейных уравнений. Заметим, что, пользуясь выражением (13), можно получить лишь первую половину значений АКФ. Вторая половина значений может быть получена за счет симметрии значений АКФ.

Быстрые алгоритмы вычисления оценки АКФ можно получить либо через векторно-матричные, либо через полиноминальные формы представления периодических АКФ, через которые в том числе можно выразить апериодические АКФ, заданные выражением (13).

Оценку периодической АКФ можно также задать в последовательностной форме

-I л/~1

= Т, X х^х

/V п=О

где аргумент п + к дискретной функции х{п + к) вычисляется по mod N. Легко показать, что после дополнения в выражении (13) последовательности {х(п)}лГ0 А/1 нулями с помощью периодической АКФ можно вычислить оценки апериодической АКФ длины 2/V-i = N. В вектрно-матричной форме оценку периодической АКФ можно записать в виде

rN=-jjSNXN,

где г,\ - вектор значений оценки АКФ; Sn - матрица - правый циркулянт с образующим вектором-строкой SN = xN = (х0, X/v-i), соответствующим

последовательности {х(л)|. Для выражения (15) известен быстрый алгоритм вычисления АКФ через быстрое преобразование Фурье (БПФ):

г« = ~-

где - факторизованная форма матрицы преобразования Фурье в поле комплексных чисел, соответствующая тому или иному алгоритму БПФ; d~n -диагональная матрица, элементами которой являются компоненты вектора комплексных коэффициентов БПФ от вектора xN, т. е.

(Уы = <*ад{с4 с/;,

с/д, = СУо, С/2, с//V—1, ^ы-Рыхы.

Если ввести р = Хд/ =0^/Г(ф,хл/ - вектор квадрата модуля коэффициентов БПФ от вектора хн, то из выражения (16) можно получить известное соотношение для корреляционного метода оценки спектральной плотности мощности сигнала

л/-1 л

Рх(К) = г{т) ехр(-/2л/ст / /V).

п-0

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

Алгоритмы вычисления АКФ на основе быстрых гиперкомплексных преобразований Фурье

В работах [7, 8] были предложены алгоритмы быстрых гиперкомплексных преобразований Фурье (ГПФ). Рассмотрим возможности применения данных алгоритмов для быстрого вычисления АКФ.

Матрица гиперкомплексных преобразований Фурье задается в виде

рЦР = иТъ

где к, т — О, Л/-1, и - мнимая единица, образующая мультипликативную циклическую группу из всех мнимых единиц. Данные ГПФ образованы в расширениях поля рациональных чисел, являющихся также полями.

Матрично-факторизованную форму представления алгоритмов БПФ по основанию два с прореживанием по частоте можно записать

^ГФ, = 'Л/*ад{р ^\\ х...

^N/2 1ы/2

^N/2 ~&Ы/2

где 0^2 = С||ад{1, ]Ь /2, ..., /Л//2-1}, °2 = (о /1 / =

= >/^1 - мнимая единица в поле комплексных чисел, 1к - к-я мнимая единица в гиперкомплексной алгебре с (N/2-1) мнимыми единицами.

Блок-схема алгоритма вычисления Л/-точечной периодической АКФ через ГПФ представлена на рис. 4, где через Яхх(/с) обозначена оценка АКФ в области ГПФ. Применяя к ней обратное ГПФ, получаем значения АКФ во временной области г^т).

Использование алгоритмов ГБПФ лучше всего продемонстрировать на примере. На рис. 5 и 6 приведены графы прямого и обратного ГБПФ, соот-

I Вход {х{т)}

ы- 1

Х(к) = X

ПП— 0

> 1

Ихх

> і

гхх(т) = ^тц^)кт м к=о

МЛ/-1

т=О

Рис. 4. Блок-схема алгоритма вычисления апериодической АКФ через ГПФ

ветствующие вычислению апериодической АКФ через восьмиточечную периодическую АКФ. Значения коэффициентов ГПФ представлены в гиперкомплек-сной четырехортовой алгебре - алгебре квантерни-онов {1,У, /', к}, / = у[Ц, у =77, к = уП-Значения АКФ в области ГПФ:

Я(1) = Я(7) = а + уЬ-кЬ,

2 2 2 2 а = Хр + Х1 + Х2 + Х§,

Ь = ХфХ3 + Х^2 + х0х1 + х2х3 =

= х0(х-) - х3) + х2(х1 + х3);

Я(3) = Я (5) = а - у'Ь + кЬ,

Я(2) = Я(6) = (х0 - х2)2 + (х1 - х3)2;

Я(4) = (х0 + х2 - Хт - х3)2;

Я(0) = (х0 + Хт + х2 + х3)2.

Таким образом, алгоритм вычисления АКФ на основе ГБПФ для N = 8; количества арифметических операций в поле рациональных чисел; число умножений М = 10; число сложений А= 18.

X

0

х

1

X

2

X

3

х =0

4

х =0

5

х =0

6

X =0 7

Рис. 5. Гоаф обратного ГБПФ

Заметим, что алгоритм вычисления апериодических АКФ через быстрое преобразование Хартли (БПХ) может быть получен посредством подстановки в выражение (16) матрицы

где Ры = — Рл)НЫ - переходная матрица от матрицы

Ны к матрице Яд/.

В результате получим

3$ = Ныхы, ^ - к-й компонент вектора Jk-^ Ты_ь 7д/-1 - матрица инверсной перестановки.

Выводы факторизованных форм матриц Нн приведены в работе [9].

Аппроксимация нормированных апериодических АКФ функциями среднего значения

разностей

Функции среднего значения разностей (ФСР) было предложено [5] использовать для определения величины периода основного тона вокализованной речи, В отличие от модифицированных АКФ они не имеют операций умножения вещественных чисел. В работе [3] был предложен метод прореженных весовых функций, применение которых к ФСР позволяет снизить количество арифметических операций в несколько раз без заметного снижения точности величины периода основного тона.

Покажем, каким образом можно использовать ФСР для аппроксимации нормированных апериодических АКФ, через которые строятся автокорреляционные матрицы.

В общем виде для оценки ФСР можно записать выражение

Хд +Х-) +Х2 +Хд

Хд+Х?-Х,-Х.я

X (5) = х0 + іх2 — ух і - кх3

Х(1) =

*0 + 1*2

-\х1 -кх3

Я

Рис.

А/—1

У(/<) = — I |х(т)^(т) - х(т ± /с)и/2(т ± /с)|, ^ т=0

/< = 0, Л/, -1.

Применительно к определению величины периода основного тона параметр А/1 много больше величины А/.

Рассмотрим возможность применения оценки у(/с) для аппроксимации нормированных смещенных оценок апериодических АКФ.

Для упрощения выкладок в дальнейшем будем использовать прямоугольные весовые функции с амплитудой, равной единице, так что выражение (17) приобретает вид

у

N—1

X Ит)

/77=0

х{т + к)\,

!18)

где т, к - 0, N -1, т + к = (т + к) .

Функцию (18) по аналогии с АКФ можно рассматривать как периодическую, если параметр (т + к) вычисляется по тос! N.

Периодическая функция у(к), также, как и периодическая АКФ, обладает симметрией, т. е.

у (к) = у(Л/ -к), к = 1, Л/ — 1.

Введем дискретную функцию, образованную через дополнения у(Аг) = утах - у(к). Полученная функция у(к) будет иметь максимальное значение при к~ 0 (при нулевом сдвиге окна, так же, как АКФ).

Если допустить, что с помощью Л/-точечной периодической ФСР вычисляется Л//2 точечная апериодическая ФСР, то исходная последовательность

отсчетов цифрового сигнала {х,]^2-1 должна быть

дополнена Л//2 нулями (так же, как АКФ). Тогда минимальное значение периодической ФСР равно Ттт = Т(Л//2) = 0. Пронормировав значения у(ЛУ/2), получим соотношения

Ттт ~ / 2) = Я(Л/ / 2) = 0,

Утах - у(0) - Ятах = Я(0).

Поведение функций у(/с) и я (к) в промежуточных точках между значениями утах и ут,п, можно оце-

а)

в)

0,75

0,5

0,25

\ \ Щ) /

ч V л У

Г(к) У ч, Чч ч- у/

\ х ж-

10

12

14 к

я Рис. 7. Гэафики нормированных АКФ и у(/с): а - фрагмент вокализованного речевого сигнала; б - при N = 16; в- при N = 32;

6. Граф прямого ГБПФ

Оценки количества арифметических операций быстрых алгоритмов

А/- длина дополненных /1/2 нулями п ос л едовател ьностеи Ы/=0 Количество нетривиальных умножений Количество сложений-вычитаний

АКФ через БПХ ФСР ГБПФ АКФ через БПХ ФСР ГБПФ

4 4 - 12 4

8 12 - 10 44 16 18

16 48 - 24 128 64 39

32 152 - 68 348 256 110

64 427 - 220 884 1024 385

128 1096 - 780 2146 4096 1441

256 2696 - 1924 5042 8384 4608

нить с помощью функции А{к), отражающей погрешность отклонения

А

_ Ш у

Rmax Углах

где

я.

пгвх

i=О

Tmax

-i W-1,

=-Ek

Для практического применения интерес представляет возможность использования дополненных нормированных ФСР для вычисления N/2 оптимальных коэффициентов предсказания из системы линейных уравнений, заданных через теплицеву матрицу, образующей строкой которой может быть использованы N/2 значений ФСР вместо N/2 значений АКФ.

В таблице представлены сравнительные оценки количества арифметических операций для вычисления апериодических АКФ через БПХ, ГБПФ и через /V-точечные периодические ФСР. По таблице можно заключить, что для длин периодических АКФ и ФСР от N = 4 до N= 64 в алгоритмах вычисления АКФ через БПХ общее количество арифметических операций сложений и умножений больше количества сложений-вычитаний, необходимых для вычислений ФСР, которое может быть отражено выражением АфСР = N2 /4.

Литер атур а /

1. Брауде-Золотарев Ю. Сжатие речи. - Компьютерра. -1998.-№ 15 (293).-С. 28-31.

2. SpaniasA. Speech codig: A Tutorial Review ASU — TR.C.Technical

report. T.R.C. - C.P. - ASP - 9201. - July 1992. - P. 21-23.

3. Гагарин К. Ю. Быстрые алгоритмы векторно-разностного ко-

дирования речевых сигналов. Сб. научн. тр. СПбГТУ сер. ВТА-РЭ. - № 457. - СПб., 1995. - С. 84-89.

4. Гагарин Ю. И., Раххал М. Математические модели предска-

зателей в схемах векторно-разностного кодирования речевых сигналов на основе многоканал ьных линейных систем. Сб. научн. тр. - сер. ВТАРЭ. - № 487. - СПбГПУ, 2002. - С. 80-81.

5. Рабинер Л. В., Шафер Р. В. Цифровая обработка речевых сигналов. - М.: Радио и связь, 1981. - 495 с.

В заключение следует отметить, что опубликованные в данной работе результаты были получены при финансовой поддержке Минобразования РФ НИР-грант Т02-03.2-2731.

На рис. 7 приведены графики функций Я(/е) и у(к), из которых можно заключить, что характер изменения значений Я(/с) и у {к) является одинаковым, хотя в отдельных случаях наблюдается отклонение значений Я{к) и у (к) до 30 %. [10]

Выводы

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

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

6. МарплС. Л. Цифровой спектральный анализ и его приложе-

ния. - М., Мир, 1990. - 584с.

7. Гагарин Ю. И,, Гагарин К. Ю. Гиперкомплексные быстрые преобразования Фурье в расширениях поля рациональ-ныхчисел //Труды СПбГТУ, серия ВТАРЭ. - 1998. - №472.-С. 77-80.

8. Гагарин К. Ю. Быстрые гиперкомплексные преобразования Фурье в расширениях поля рациональных чисел с длиной преобразования, факторизованной взаимно простыми множителями //Труды СПбГТУ, серия ВТАРЭ. - 2000. - №480. -С. 89-92.

9. Гагарин Ю. И. Математические модели и алгоритмы быстрых ортогональных преобразований. - СПбГТУ, 1999 - 400 с.

10. Раххал М. Методы и алгоритмы вектор но-разностного кодирования цифровых аудиосигналов. - СПбГПУ, кандидатская диссертация, 2004. - 126 с.