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

РОССИЙСКАЯ АКАДЕЛ1ИЯ НАУК р рдИНСТф^'Т ПРОБЛЕМ ПЕРЕДАЧИ ИНФОРМАЦИИ

= ' A at' }Qc./,

"■■'' На правах рукописи

ПОТАПОВ Владимир Георгиевич

УДК 621.391.15

АЛГОРИТМЫ ДЕКОДИРОВАНИЯ В СПИСОК И ИХ РЕАЛИЗАЦИЯ

Специальности:

05.13.01 Управление в технических системах 05.13.17 Теоретические основы информатики

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

Москва 1994 г.

УДК 621.391.15

Работа выполнена в Институте проблем передачи информации Российской Академии Наук

Научный руководитель: доктор технических наук,

В. В. Зяблов

Официальные оппоненты: доктор технических наук,

В. Д. Колесник

кандидат физико-математических паук,

Г. К. Голубев кандидат технических наук, Л. С. Чудновский

Ведущая организация: Московский государственный

технический университет гражданской авиации.

Защита состоится « »-1994 г. в-час.

на заседании специализированного совета Д.003.29.01 в Институте проблем передачи информации РАН по адресу: 101447, Москва, ГСП-4, ул. Ермоловой, 19.

С диссертацией можно ознакомиться в библиотеке ИППИ РАН.

Автореферат разослан «._»-- 1994 г.

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

доктор технических наук ( С. Н. Степанов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы диссертации.

Использование сложных кодовых конструкций для систем передачи и хранения информации становится все Солее актуальным, поскольку позволяет сувественно увеличить энергетический выигрыш по сравнению с простыми кодовыми конструкциями. Одним из путей построения сложных кодовых конструкций является каскадированне кодов, предложенное Д. Форни и В. В, Зябловым в конце 60-х начале 70-х кодов. Суцествуюаие сегодня системы каскадного кодирования для декодирования, внутренних кодов используют, как правило, алгоритмы с единственным ревением на выходе. • что обуславливается (существовавшими до недавнего времени) техническими ограничениям« и недостаточным количеством теоретических исследований в области списочного декодирования. В последнее время появились новые высокопроизводительные сигнальные и RISC процессоры, которые позволяют для систем каскадного кодирования на практике реализовать алгоритмы списочного декодирования внутренних кодов с последующим анализом п обработкой полученных списков внешним декодером. Важнейякм результатом применения алгоритмов декодирования каскадных кодов со списочным декодированием внутренних кодов является получение значительного энергетического выигрыва. в сравнении с традиционным .алгоритмом декодирования каскадных кодов.

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

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

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

- г - .

Цель работы.

Цель работы • заключается в разработке и исследовании:

- характеристик декодирования каскадных кодов и кодов, представи-мых как каскад!ые, при списочном декодировании внутренних кодов для полунепрерывного канала; V

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

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

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

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

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

- оценивания периода основного тона речевого сигнала в пумах;

- сегментации речевого сигнала на вокализованные-невокали-■ зованные и переходные-стационарные участки.

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

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

- исследован рекурсивный алгоритм декодирования в список фиксированной длины на каждом шаге векторного представления Плоткина кодов Хэмминга с параметрами (2", 2"-т-1,4).

- разработан и исследован рекурсивный алгоритм декодирования в список фиксированной длины на каждом иаге матричного представления кодов Хэмминга с параметрами (2", 2"-т-1,4).

- разработан и исследован помехоустойчивый алгоритм предварительной оценки периода основного тона слитной речи, выходом которого является список из подсписков случайной длины значений периода ОТ;

- разработан и исследован помехоустойчивый алгоритм выделения< периода основного тона речи из списка с одновременной синхронизацией речевого сигнала к периоду основного тона; ■ • а

- предложен метод сегментации речевого сигнала на вокализованные п невокализованные участки речевого сигнала;

- предложен метод сегментации речевого сигнала на переходные и стационарные участки.

Положения, выносимые на защиту.

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

2. Рекурсивные алгоритмы декодирования кодов Хэмминга с параметрами (2".2"-1и-1,4) на основе матричного и векторного представления со списочным декодированием подкодов.

3. Алгоритм предварительной оценки периода основного тона речевого сигнала.

4. - Алгоритм сегментации речевого сигнала по периодам основного тона. '

5. Метод сегментации речевого сигнала на вокализованные и невокализованные участки.

6. Метод сегментации речевого сигнала на стационарные и переходные участки.

Практическая ценность. •

Применение разработанных алгоритмов списочного декодирования позволяет:

- при использовании в уже суиествуюдих системах каскадного кодирования существенно увеличить помехоустойчивость- кодирования;

- при проектирования новых систем каскадного кодирования снизить кодовую избыточность при заданных вероятностных характеристиках;

: при использовании блоковых кодов, представимых как каскадные или обобиенные каскадные (Хэмминга. Галея, Рида-Наллера, БЧХ и др.). суяественно уменьвить сложность декодера по сравнению с декодером максимума правдоподобия без сувественных потерь в смысле вероятности оипбки.

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

Практическая значимость работы.подтверждена актами о внесро-

нии.

Апробация работы.

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

Результаты работы, касающиеся рекурсивных алгоритмов декодирования кодов Хэмминга, докладывались на международном симпозиуме по теории связи и ее приложениям (Лэйк Дистрикт, Великобритания, 1993 г.).

Результаты работы, касающиеся алгоритмов помехоустойчивой сегментации речевых сигналов, докладывались на всесоюзной конференции "Современные вопросы информатики, вычислительной техники и автоматизации" (Москва, 21-23 апреля, 1985 г.)-На научных семинарах в ИППИ РАН и ВЦ РАН. Работа В. Г. Потапова и А. 0. Шевердяева "Некоторые алгоритмы анализа временной структуры речи* заняла 1-ое место на конкурсе "Лучшая научная работа года ИППИ АН СССР" в 1985 г.

По теме диссертации опубликовано 7 печатных работ.

Структура диссертации.

Диссертационная работа состоит из Введения, трех глав. Заключения и списка литературы.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ -

Во Введении обоснована актуальность работы. Сформулированы цели и задачи исследования* приведены основные научные результаты, выносимые на защиту, дан краткий обзор содержания диссертации.

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

Известная модификация алгоритма Витерби имеет сложность порядкаЬЬ|VI, где Ь - длина списка, Ь - количество ребер, входящих в узел решетки, |\г|-число узлов в решетке.

, В главе предлагается новый алгоритм,построения списка, имею-щиП сложность порядка Ъ|\г|+пЬ(Ь+Ъ), которип основан на использовании дополнительной обработки информации, получаемоП в результате

работы алгоритма Витерби. Здесь п - длина кодового слова.

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

Идея предложенного алгоритма построения списка из I, слов заключается в следующем. На первом этапе с помощью обратного прохода по реиетке стандартного алгоритма Витерби находится путь »/'- . ..,»'). называемый наилучшим. На втором этапе, опираясь на наилучший путь, строится список из Ь путей. При этом используется тот факт, что каждый путь из списка по отноиению к наилучшему пути и' образует либо "петлю", либо "сумму петель". Точки слияния петель с иаилучшш путем находятся перебором по узлам наилучшего пути, затем по узлам найденных петель. После того, как нужное число петель найдено, их комбинированием строится искомый список.

С точки зрения практической реализации наибольнкп интерес представляют частные случаи для длин списка 2 и 3, алгоритмы построения которых опираются на доказательство справедливости слелую-кей леммы:

второй V2 и третий по величине метрики пути являются однопетлевими.

Однопетлевым путем назван путь, имеющий лииь одно ответвление от наилучшего и представимый в виде

V1 ' ' V1 -

V* . — V* --'-.у' .........и V1 —...—■=- и' .

О , « - I 1 J-\ « } ч

J

Рассмотрим алгоритм поиска второго пути. Обозначим через

v1 - (v^ ......) последовательность узлов на наилучшем пути

w1. Введем следующие обозначения: (v) • (и ,v ,.....v J - ино-

0 1 п

жество, элементами которого являются координаты вокторэ v; и - путь, проходящий через узлы v; и| J - отрезок пути и. ведуяиА

'" I

из узла в узел v : u{v) - отрезок пути, ведущий из узла v в

3 О

узел V. Тогда, для поиска второго пути sr необходимо вычислить

метрики путей v*(yj - ог(у) I w' I ve[v') и выбрать путь, импг>-

t *

яий минимальную метрику, т. е. найти

v - arg min Д {v>, y€(v* J*

- б" -

IV

Здесь через Л2(у) -. - н1*' ] - и1и*(у>) - и[ч'(у)] -

- и[ил(у)) - «и- (V)] обозначена разность метрик я-го и первого путей, сливающихся в узле V, -и^у) - ребро, по которому привел к-ый по величине метрики путь среди 'путей, сливающихся в узле V. Таким образом, сложность алгоритма построения списка из двух слов складывается: из сложности собственно алгоритма Витерби; сложности вычисления Д3 (V- > для } порядка и сложности нахождения

минимума порядка п. Таким образом, дополнительная по отношению к стандартному алгоритму Витерби сложность алгоритма поиска второго пути составляет величину порядка г^.

Алгоритм построения списка из Ь наиболее вероятных слов основывается на вспомогательном алгоритме построения списка из лучвих однопетлевых слов, идея которого сострит в следующем. По мере просмотра узлов V1, через которые проходит наилучший путь, просматриваются и узлы ответвления у' е{\Л(у)}\(у1 } пути и*(у), проходящие через узлы у*(у). Другими словами, просматриваются однопетлечые пути по отношению как к наилучвему, так и к найденным лучиим путям. Очевидно, что для работы такого рода алгоритма понадобится дополнительная память (стек), куда вместе с каждым узлом V будет

■ заноситься отрезок пути ^ (у) - о1ип, по которому мы пЬпалн из конца решетки в узел у, счетчик £(у) ребер, использованных для построения сливающихся в' узле.у путей, а также вычисленные разности метрик. При ь<<п дополнительная сложность для вычисления разности метрик составит величину порядка п!Л, а сложность сортировки памяти узлов по разности метрик порядка п1>3, т. е. дополнительная сложность по отношению к алгоритму Витерби порядка пЬ(Ь+0.

Четвертый путь к4 в списке наиболее вероятных путей может быть произвольным, поэтому произвольный путь «представляется в виде суммы взаимно аддитивных однопетлевых путей, при этом два пути *.' и м" названы взаимно аддитивными по отношению к пути м', если их участки ответвления не пересекаются, т. е.

{*' 1М*1} П {»"М*1} - и. Суммой взаимно аддитивных путей м' и«" назван путь, ответвления которого являются объединением ответвлений слагаемых:

+ к" - [«'"]\{«Ч и [«"Мч1) и {*' )ПЫ' }П(»"}.

Тогда алгоритм нахождения списка путей V - дли-'

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

метрике список уже найденных путей текущего однопетлевого пути; 2) просмотром и возможной вставкой в список всех с/мм текущего однопетлевого пути и путей," составляют« список при условии, что они удовлетворяют условию аддитивности. Сложность этих шагов составляет величину порядка Ь* операций.

Во второй главе рассматривается задача построения быстрых алгоритмов декодирования блоковых кодов, представимых как каскадные, для полунепрерывного канала. Показано, что применяя различные каскадные представления кодов Хэмминга с параметрами НМ(тп) - (2*, 2"-и-1,4), можно построить декодеры, имеющие линейную сложность и приближающиеся по вероятности ошибки к декодеру максимального правдоподобия (МП декодеру) во всем рабочем диапазоне отнооений сигнал/шум. Разработанные алгоритмы являются рекурсивными и предъявляют суиественно меньииэ требования к объему памяти.

Сложность рекурсивного алгоритма декодирования на основе векторного представления Плоткина составляет величину порядка 12п, а декодера, построенного на основе матричного представления, - величину порядка 46п. Сложность НП декодера оценивается величиной порядка па. •

Кратко остановимся неиспользованных каскадных представлениях кода Хэмминга.

.„-.. На рис. I показано известное векторное представление (разложение Плоткина), примененное для кода Хэмминга; где кодовое слово С* е НИ(я) представимо в виде сушга (^-(С"'^"' 'в С"*') --"(С"'* .С-'). С"-*€ НЖга-1). Г"'« Р(и-1), а'р(и) - (2" .2*-1.2) -

I г к р

- код с проверкой па четность.

С"» с*" »

9

С--" ь

Рис- I Векторное разложение кода Хэнминга.

Декодирование кода Хэмминга км(ш) длины п сводится к рекурсии по

декодированию кодов HM(m-l) длины п/2, НЫ(п-2) длины п/4..... и

коду с повторением (4,1.4).

Предложено матричное разложение кода Хэмминга. которое получается в результате представления о в виде суммы в - at+ аг. тогда кодовое слово Се НИСш^ а^) ножет бить представлено бинарной кат-

- в -

рицей размера 2 ц 2 . Обозначим через .-. АМт ,та) прямое произ-ведяаив двух кодов-с проверкой на Четность АЯСп^.п^) - РСп^) в в Р(та), тогда кодовое слово С(т) в ЮКа^* иа) можно представить в виде, изображенное.иа Рис. 2, '..

I

Рис. 2. Матричное разложение кода Хэмминга.

где С

е нмс^), С

€ НМ(п1а), а С

е ЛЯ (т.

,та).

Т. е. является

словом итеративного кода АН(ш|,оа) с проверкой иа четность по , строкам и столбцам. Для матричного представления кода Хэмминга построен соответствувдий рекурсивный алгоритм декодирования. При этом, в зависимости от показателя степени в, а также от разложения т на сумму т| я та представление копа по рекурсии может быть как чисто матричным, так и требовать на определенных этапах рекурсии векторного представления. «

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

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

Оценка сложности алгоритма декодирования кода Хэмминга при его матричном представлении дана для случая, когда количество узлов в уровне решетки равно 8. ■ «

Проведено статистическое моделирование алгоритмов с единственным решением на каждом уровне рекурсии для обоих способов представления кодов Хэмминга НИ(4) п НМ(6). Ниже приведены результаты

для кода Ш(6):

- декодер на основе матричного представления кода НМ(6) выигрывает 0,2 дБ по помехоустойчивости у декодера на основе векторного разложения Плоткина, но проигрывает декодеру ЦП порядка 0,5 дБ.

Относительно большой проигрыш обоих алгоритмов декодирования кодов Хэыминга объясняется двумя причинами: 1) иум в преобразованном в результате рекурсий канале становится негауссовским вследствие определения операции сложения по модулю 2 в пространстве Я"; 2) на каждом ваге рекурсии декодер выдает единственное решение.

В результате была произведена модификация алгоритмов декоди-вания кода Хэмминга для обоих видов представления в соответствии с алгоритмом декодирования в список длины 2 внутренних кодов для систем каскадного кодирования (описанного в первой главе).

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

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

Г Для векторного представления на этапах ракурсна возникает ' проблема сокращения списка с 4-х кодовых слов до 2-<х. для матричного - ч 8-ми до 2-х.

Для рассматриваемого случая наибольвий энергетический выигрив от применения списочного декодирования достигается тогда, когда процедура сокращения списка до двух слов на каждом ваге рекурсии сохраняет обе Ветви представления, соответствующие кодовым словам (0,0,0,0) а (1.1,1.1) кода с повторением (4.1,4).

При организации процедуры сокращения списка подобный образом декодер кода НН(6) с матричным представлением кода Хэмминга проигрывает декодеру ВП порядка 0.2 дБ, т.е. энергетический выигрыш составляет 0.3 дБ о сравнении с декодером с единственным реиениеи на . этапах рекурсия. Функции, еираяавщие завнсииость вероятности ошибка от отисиенил сигнал/щум для декодеров обоих внл'п представления кода КМ(4), практически совпадают с соответствую! гунхцнеП ЦП декодера.

В третьей главе рассматриваются вопросы разработка >мехоустоЛчм-

вых методов и алгоритмов предварительной оценки периода основного тона и сегментации Ьигнала слитной речи, предназначенных для использования в цифровых системах передачи и хранения речевой информации на примере кодера речевых сигналов, отвечающего федеральному стандарту США №1016 (СЕЬР). Дается краткое описание декодера и кодера СЕЬР. В основе системы схатия речевых сигналов СЕЬР лежит авторегрессионная модель речевого сигнала. Сигнал возбуждения линейного фильтра кодируется с помощью двух кодовых книг. Адаптивная кодовая книга в кодере оценивает квазипериодическую компоненту, а стохастическая - случайную (непредсказуемую) компоненту сигнала возбуждения. Скорость передачи составляет величину 4800 бит/с.

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

Из литературы по первичной обработке речевых сигналов известно, что речевой сигнал на "стационарных" вокализованных участках речи не представляет собой отрезок строго периодической функции. • Больше того, отсутствие флюктуаций (микровариаций) значения периода основного тона отмечается слушателями как потеря естественности речи. Происходит и изменение энергии сигнала на соседних пе- * риодах. В частотной области данные флюктуации приводят к перераспределению энергии по гармоникам ОТ и расширению спектра вокруг средней частоты ОТ и его {-армоник. Поэтому для оценки значения периода ОТ речевого сигнала предложена двухэтапная процедура пред-? варительной оценки периода ОТ, где на первом, используя периодическое приближение речевого сигнала, строится список из подсписков возможных средних значений периода, а на втором производится окончательный выбор с использованием алгоритма синхронизации (сегментации) по периодам ОТ. Элементы подсписка находятся между собой в гармоническом или субгармоническом отновении. За вероятность ошибки решения списком принимается вероятность того, что истинный период с точностью до половины интервала, задающего "малые" и "большие" овибки, не входит в список. Вероятность выхода оценки за интервал названа вероятностью "больших ошибок", которые в допорого-вой области для широкого класса статистик складываются в основном® пз "перескоков" на кратные и дробные значения среднего периода ОТ. "Налив ошибки" в пределах интервала обусловлены дисперсией шума.

Наличие обоих типов овибок и диктует организацию списка.

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

Однако, применительно к речевому сигналу необходимо оценить функционал, т. е. необходимо оценить значения периода отрезка периодической функции в присутствия белого•гауссовского иума.

Точнее, пусть п - длина выборки сигнала; мнохество векторов. Б - (в , а , ... , в )' е таких, что з, - а. , 1 < 1 < п-р

12. и 1 1 ♦ Р

образует векторное пространство Рр размерности р; Р» - проектор на подпространство к; X - Б * И; N - вектор пума, элементы которого независимы и распределены с «(я,в2), где и(а,ь> - гауссовское распределение с параметрами а и Ь.

Применительно к речевому сигналу для решения сформулированной задачи широко использовалась статистика вида:

Е(р,Х) - | РррХ |2.

где | А | - норма вектора А. Однако, использование в алгоритмах

статист'ихи Е(р,Х) требует знания дисперсии пума, т.к.

£<| РррХ |») - £(Е(р,Х)) - | Б |1 + а'р,

о(| РРрХ |а) - о(Б(р,Х>) - 4в*| Б |а + 20*р,

где £ - символ математического ожидания, а о - дисперсии.

• В работе для оценки среднего на анализируемом отрезке значе-ния'периода ОТ речевого сигнала предлагается использовать статистику, независяаую от дисперсии пума, вида:-

I Рр^Х

. П - П

- 1 - рр. ' а к - —7Г-

ГДЭ

- » - ГР,

Статистику Г(р,Х) принято называть статистикой Фишера, плй Г-ста-тпстикой. При достаточно больпом п справедливы соотношения:

Л Рр X р„ X

Е(Р(р,Х)) « Е Р* I. 0(Р(р,Х)) ~ 0 —р—- I.

1 а2 р ' ^ в р '

Иди С(Р(р,Х) ) » А ♦ 1 - «<А+1,

0(Р(р,Х)) - >) - -|(-АП).

где

I Э

А - --— - отношение сигнал/шум,

по

А п

4. - —с— - — - выигрив в отношении сигнал/иум ш сигнала А Р Б « р, .

1 Рр х I*

А - -£-а-— - отношение сигнал/шум в подпространства р».

4 ч<»

При ч-Р. достаточно большом п можно построить оценку откования сигнал/шум в виде

Г(р.Х) - 1

д - -,

Л

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

Однако, при переборе априорного интервала значения периодов ч меняются степени свободы как у числителя, так и у знаменателя статистики

| Р_ * |* п-ч X

Г(Ч.Х) - -—г -—а

п~ч

I V* I1 Ч х* р«

где х* - случайная величина с распределением хя - квадрат с ч

степенями свободы, поэтому применялась аппроксимация Фввврл

Г(Ч.Х) ->¡4- . 4- -огн^чг)-

Ч,п

Нецентральные хи-квадрат аппроксимировались по Тыжи: , « * 20 „ х-*т ттт V

(в ♦ 6)»

9 ---, где 6 - параметр нецентральиости.

■ ♦ 20

Аппроксимации позволили построить и исследовать алгоритмы оценки перкода функции со списком сиу чайной длины при фиксированной вероятности оиибки типа 'ложной тревоги* для каждое гипотезы о зш&че-*ти периода.

Для периодических сигналов искусственного происхождения (с цольв сравнения с известными алгоритмами) проведено статистическое моделирование алгоритма обнаружения сигнала, Испольэуюиего F-ста-Тистику в канале с аддитивным белым гауссовскям вумом.

Точнее, при |РР|Х|а- 0. заданном векторе 0 априорных значении возможных периодов сигналов таких, что q( взаимно просты и

I

в - »Пч,.

I

где п - целое положительное число, неравное нулю. Алгоритм определения периода (обнаружения) сигнала при фиксированном X имеет вил:

р - arg max(r(q,X)). Прячем в панно* постановке

lpP,S|*" И Для всех q(* р,

т. е. пространства 1Ч( - взаимно ортогональны. Получены следующие результаты моделирования.

Для сигнала с известной начальной фазой данный алгоритм в смысла вероятности правильного обнаружения проигрывает: 4 дБ алгоритму шксшгального правдоподобия (когерентному приемнику) при условии, что ранение принимается списком; и 6 дБ, если выносится единственное ревение. . .

Для сигнала со случайной фазой, равномерно распределенной на интервале 0-2». предлагаемый алгоритм проигрывает в смысле вероятности правильного обнаружения 3 дБ алгоритму максимального правдо-водоЗжя (некогерентному приемнику), если за реиение принимается пертЯ алэшоит списка я I дБ в случае, веля реиеняе принимается стскод пря этом выборочное среднее длииы списка равно 1,5 (выворотах» среднее длины списка при условия неправильного обнаружения рам» 0,,5).

Исследовалось характеристики двух алгоритмов предварительной одаязя' згрч-о.та ОТ речевого сигнала: 1) со списком максимальной (3 я жгачм « 2) со списком случайной (т.е. используюивй аппрок-с®шип> р-етатестят») длиш. Эксперимент проводился при следующих усяоькия: ¡интэраал аиалмза по периодам от 7,5 мс до 15 ис; диапа-зоа «тва%я№& счпгал/нуы от -18 дБ до «6 дБ; пум аддитивный белый гаувесйеаай» м разноверный. ,

Для врмыкяшеадЯ организация списка получены следующие результаты:

т ,ш «.»гор.чтма'со списком случайной длины общий объем списка я ноявтвстэе пояепчеков уменьшается с ухудоеипем отновения сигнал/ /с.уи;

- выборочное сродчэо количества подспискоя равно 1,4; .

- выборочное.среднее длины неправильного подсписка алгоритма со списком случайной длины равно 1,1;

- выборочное среднее длины правильного подсписка алгоритма со списком случайной длины равно 2,3;

- выборочное среднее количества подсписков на левокавизованных участках и паузах равно 0,8;

- выборочное среднее длины подсписха на невокализованных участках й паузах равно 1,7.

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

Далее рассматривается вопрос выбора окончательного реионяя о значении периода ОТ из списка возможных значений.

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

Ваг 1. Выбрать предполагаемое значение периода ОТ р(.

, Шаг 2. Выбрать окно кратное периоду - г( pt.

Ваг 3. Вычислять проекцию смеси речевого сигнала я «ума X - S+M на пространство p»t .

Шаг 4. Сгенерировать пилообразный сигнал V.e р» такой.

что - 1 я приравнять в - в.

ваг 5. Вычислить я запомнить значения

(р,

С(р га) » —----—»i-

глв (а.Ь) - скалярное произввквияе векторов ь к Ь.

WP ((в) - вектор Wptциклически сдвинутый на s

. элементов.

Шаг 6. Повторить иаг 5 для □ - i,p -1. ;

Шаг 7. Найти и запомнить

С(р( ,э) ) - ma* с(р( ,s) .

Шаг 8. Повторить ваги 1-7 для всех р( .

Шаг 9. Найти пару

(р.з)- arg max С(р .s. ).

р i »

Если допускать решение.списком, или использовать список как • основу для принятия окончательного решения, то необходимо повторить ваги 2-9 при сдвиге на долю окна. В этом случае, преимувест-во решения списком заключается в том. что позволяет уменьшить дисперсию положения точки синхронизации. Величина сдвига и количество повторений зависит от желательного объема списка И допустимого числа операций.

Предложена аппроксимация вокализованных участков речевого сигнала следующего вида:

S - m¿n m¿n leBc-SI1,

где S - выборка речевого сигнала, em", с « Rp, n - r'p, 9- символ тензорного произведения, Мр - многообразие векторов вида е8с. В соответствии аппроксимацией вводится следующие определения: в - называется огибающей, а с - образующей речевого сигнала, и предлагаются числовые меры нестационарностей:

. г

по огибающей - e(p,S) - Е (1-е );

» , » •

по образующей - ¿ ■ ■

I S I*

»(P.S) - —: *

I s |a . .

à также мэра удаленности вектора S от л

I S |а

Здесь Is!

a s a s а а*

é _ /_« _р р» » р» < г » г -1 ) ♦ i pr \

..... V V ..... е2 " " е, " " вг

- сигнал с выравненной огйбавцей,

S - Р0 S - приближение вектора S элементом из Р». p.p.1

Указанные мери нестационарностей позволяют построить алгоритмы сегментации речевого сигнала на переходные И стационарные участки. При этом переходные участки классифицировать по скорости измения параметров на быстрые и медленные. Под быстрыми переходными участками подразумеваются те. параметры которых претерпевают сукествен-ные изменения на 2-3 соседних периодах ОТ. Среди переходных участков рассматриваются следующие:

вокализованный-вокализованный, невокализованный-вокализованный, вокализованный-невокализованный. J

Применение алгоритмов сегментации речи на вокализованный--невокализованный и определения.среднего периода ОТ для системы сжатия CELP позволило снизить вероятность 'больших* ошибок оценки значения задержки, используемой при построении адаптивной книги примерно в 5 раз по сравнению со стандартным алгоритмам при сохранении качества синтезируемой речи.

Заключение..

Все перечисленные алгоритмы были запрограммированы на алгоритмическом языке Си. Статистическое моделирование проводилось на RISC процессорах ИС86100 фирмы Uotorola и i860 фирмы Intel. С целью увеличения объема статистического моделирования ряд алгоритмов был запрограммирован на языке ассемблера указанных процессоров.

К наиболее существенным результатам диссертационной работы относятся следующие:

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

?.. Разработана и исследована программная реализация рекурсивных алгоритмов декодирования для векторного и матричного каскадного представления кодов Хэмминга с параметрами (2",2"-га-1.4) пра списочном декодировании на каждом уровне представления. Сложность предложенных алгоритмов декодирования в отличии от ЧП декодеров линейно зависит от длины кодового слова при том. что характеристики помехоустойчивости приближаются к характеристикам состоят-ствугипх МП декодеров.

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

ны помехоустойчивые алгоритмы сегментации: сигнала слитного речевого сигнала, основанные на обработке списков: по периодам ОТ, а такхе на вокализованные-новокализованныа и переходные-стационарные ' участки сигнала. ,

4. Разработана и исследована программная реализация стандартного кодера CELP. Применение алгоритмов сегментации речевого сигнала на участки вокализоваиный-невокализовагашй и определения периода ОТ в системе CELP с целью сокращения перебора по априорному интервалу задержек, предусмотренному стандартом, позволяет суиественно сократить время, необходимое для построения адаптивной кодовой книги, и уменьшить вероятность больиих ояибок в оценке задержки при сохранении качества синтезированной речи. ■" "

Основные результаты диссертации опубликованы в следующих «зданиях: . ■

1. В. В.Зяблов, В. Г.Потапов, В.Р.Сидоренко, Декодирование в список максимального правдоподобия с помощью кодовой реиетки, Проблемы передачи информации, том 29, Й4 октябрь-декабрь 1993г..с. 3-10.

2. V.Zyablov, V.Potapov, V.Sidorenko, B.Honary, G.Markarian, Recursive Decoding Algorithms' for Hamming Codes, 2nd Inter. Syrsposius on Communication Theory and Applications, Lake District, July. 1993, United Kingdom. *"-.''

3. V.Zyablov, V.Potapov. V.Sidorenko, Decoding of Convolutional Code into Li3t, Proc. of Algebraic and Combinatorial Coding Theory,Int. Workshop, 1992, Voneshta Voda, Bulgaria.

4. В. Г.Потапов, А. Ю. Иевердяев, О переходах в вокализованной речи, в сб. Анализ сложных информационных систем, часть 1. Институт вроблом передачи информации АН СССР, 1984, с. 7-9.

5. В. Г. Потапов, А. В. Шевердяев. Сегментация речевого сигнала по периодам основного тона речи. - В кн. : Современине вопросы информатики. вычислительной техники и автоматизации: Тезисы докладов и сообщений. Всесоюзная конференция (Москва, 21-23 апреля 1985 г. ). Москва Всесоюзный институт научной и технической информации АН СССР я ГКНТ, 1985. с. 48.

6. В. Г. Потапов,. А. Ю. йевердкез. Оценивание параметров премойиоП структур!-! речи. - В кн. : Автоматическое распознавание слуховых образов: Тезисы докладов и сообцониЯ 12-го Всесоюзного семинара (АРС0-12), (Киев-Одесса, сбит. 1982 г. ). Киев: РИО ИК АН УССР.

1982. с. 128-131.

7. В. Г. Потапов. Интерактивная система сегментации и оценки параметров речевого сигнала. - В кн.: Автоматическое распознавание слуховых образов: Тезисы докладов и сообщений 11-го Всесоюзного семинара (АРСО-11). ( Ереван, 3-9 декабря 1980 г.) с.67-69. _ '