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

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

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

ВОЛОХОВИЧ Алексей Валерьевич

СЖАТИЕ ЦИФРОВОМ ЗВУКОВОЙ ИНФОРМАЦИИ АДАПТИВНЫМ АЛГОРИТМОМ ТИПА «СТОПКА КНИГ» И ЕГО МОДИФИКАЦИЯ

Специальность: 05.13.17-Теоретическне основы информатики

Автореферат диссертации на соискание ученой степени кандидата технических наук

Ж'

Нижний Новгород 1998

Работа выполнена на кафедре «Теория цепей и телекоммутации» Нижегородского государственного технического университета

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

Официальные оппоненты: доктор технических наук, профессор Кирьянов К.Г., кандидат технических наук, старший научный сотрудник Палочкин Ю.П.

Ведущая организация: Научно исследовательский институт измерительных систем.

Защита состоится в/} час в аудитории «а заседании

диссертационного совета №Д 63.85.02 Нижегородского государственного технического университета по адресу: 603600,г. Нижний Новгород, ГСП-41, ул. Минина, 24.

С диссертацией можно ознакомиться в библиотеке НГТУ.

Автореферат разослан «/3 » . /У # 1998 г.

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

Иванов А.П.

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

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

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

В теории информации доказана теорема кодирования для источника гнала неравномерным кодом в отсутствии шума. Согласно данной теореме ществуют коды, средняя длина которых может быть сколь угодно близка к 1жней границе для длины кодового слова. Коды, удовлетворяющие дан-1м требованиям, являются оптимальными. Существую^ методики по-роения оптимальных кодовых алфавитов, например коды Шеннона- Фано, д Хаффмена, арифметические коды, предложенные Риссаненом. Постро-ные на базе данных кодов архиваторы позволяют эффективно сжимать }бую информацию, обрабатываемую не в режиме реального времени, вне висимости от природы источника. К сожалению, данные коды эффектив-I только в случае известной заранее вероятности появления букв на выхо-источника.

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

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

Основной проблемой на пути применения универсальных информ; ционных методов кодирования является обычно неизвестная в большей ил меньшей степени статистика источника при поступлении информации с различных источников в режиме реального времени. Это не позволяет ис пользовать перечисленные выше оптимальные методы кодирования. Тольк в последнее время появились интересные результаты в данной области [ ним относятся работы Фитингофа Б.М., Кричевского P.E., Рябко Б..Я Штарькова Ю.М.].

К универсальным методам кодирования относится и алгоритм кож рования цифровой информации типа «стопка книг». Данный алгоритм бы исследован Рябко Б.Я. в 1980 году, Ситняковский И.В. в книге «Цифровг сельская связь» приводит результаты исследований по сжатию данным ai горитмом речевых источников информации для случая использования HKN АДМ и ДИКМ входного сигнала. Исследования показали, что применена метода «стопка книг» позволяет сжимать исходную информацию в 2-4 ра: в зависимости от загруженности канала.

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

• исследование возможностей применения алгоритма не только дs речевых источников, но и для произвольных источников звукового диапаз( на;

• возможная модификация исходного алгоритма для повышения ст пени сжатия и скорости обработки информации.

Научная новизна работы заключается в следующем:

•автором разработана модификация алгоритма типа «стопка книг» использованием кластеризации;

• реализована списочная организация алфавита для модифицирова! ного метода с использованием кластеризации, позволяющая снять огранич ния по мощности алфавита, связанные со скоростью обработки информаци

• математически доказана эффективность по сжатию модифицир ванного метода типа «стопка книг» с использованием кластеризации i сравнению со стандартным методом;

• математически доказано неулучшение верхней границы по сжатию (формации при использовании древовидной структуризации кодового ал-звита источника;

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

Практическая значимость. На основании результатов исследований 1тор считает перспективным использование разработанных им методик для зименения в линиях связи между речевыми источниками, работающих в жиме реального времени, с высокими требования к качеству передаваемой :чи при скоростях передачи 32 Кбит/с, а также при передачи высококаче-венной музыкальной информации с частотой дискретизации 44 кГц для элучения стерео звучания без увеличения пропускной способности канала сохранении исходного качества передачи. Данные выводы полностью под-(ерждаются результатами экспериментов, проведенных на обширном статическом материале.

На защиту выносится:

1. Модифицированный алгоритм сжатия цифровой информации типа «стопка книг» с использованием кластеризации алфавита.

2. Динамические характеристики стандартного и модифицированного методов.

3. Неулучшаемость алгоритма с точки зрения степени сжатия при использовании разбиения алфавита на подмножества.

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

5. Реализация работы модифицированного метода «стопка книг» в виде списка.

6. Результаты экспериментального исследования использования стандартного и модифицированного методов сжатия цифровой информации типа «стопка книг» для обработки реальных источников звуковой информации.

Апробация работы. Основные положения и результаты работы док-адывались на научно-технической конференции факультета «Радиоэлек-эоники и технической кибернетики» Нижегородского государственного ;хнического университета, посвященной 100-летию изобретения Радио А. . Поповым; на международной конференции, объединенной с 50-й науч-

ной сессией, посвященной Дню радио; на научно-технической копференщ факультета радиоэлектроники и технической кибернетики, посвященной 81 летию Нижегородского Государственного технического университета.

Публикации. Основные теоретические положения, практические р зультаты и выводы, сделанные при работе по теме диссертации, нашли свс отражение в 8 опубликованных печатных работах.

Структура и объем работы. Диссертационная работа состоит из вв дения, четырех глав, заключения, библиографического списка (38 наимен< ваний) и приложения. Основной текст диссертации изложен на 168 стран! цах. Иллюстративный материал представлен в виде 65 рисунков и 15 табли

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

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

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

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

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

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

1. Источники речевой информации (пять файлов, содержащих речевь сообщения.) Общий объём анализируемой информации 24,4 Мбайта.

2. Источники звуковой информации (шесть файлов, содержащих муз! кальную информацию). Общий объём анализируемой информащ 39,4 Мбайта.

3. Источники не звуковой информации (шесть файлов случайных пр< цессов и компьютерных файлов). Общий объём анализируемой и!

формации 5,9 Мбайта.

Исследование каждой группы источников проводилось по следующей :хеме. Расчет максимального теоретически достижимого сжатия исходного |)айла путём подсчета энтропии. Расчет максимального теоретически дос-ижимого сжатия исходного файла при уменьшении разрядности. При этом вдовое слово формируется следующим образом: первая часть представляет юбой закодированные старшие разряды исходной последовательности; вто-)ая часть - передаваемые без изменений младшие разряды. Такой способ ко-щрования исходной буквы, в случае если общее сжатие при этом не умень-иается, позволяет не увеличивать размер алфавита для учёта знака разност-юго значения двух соседних букв последовательности. Кроме этого произ-юдится расчет максимального теоретически достижимого сжатия исходного [)айла при кодировании разности между соседними отсчётами.

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

• применение предварительного разностного кодирования со сдвигом фиводит к лучшим результатам для тех случаев, когда буквы алфавита федставляют собой последовательности отсчётов коррелированных слу-1айных величин;

• это является характерным для звуковых источников информации;

« в остальных случаях для сжатия исходной информации предпочти-ельнее произвести увеличение мощности алфавита;

• при этом для звуковых источников с |у!|=65536 кодирование младших >аз рядов равномерным кодом, а старших с помощью оптимального стати-тического кода, позволяет получить уменьшение размера кодового алфави-а при сохранении степени сжатия. А любое уменьшение размера алфавита окращает затраты на аппаратную реализацию алгоритма, так как происхо-1иг уменьшение размера кодового дерева для процедур кодирования и деко-шрования.

В качестве общего вывода по первой главе можно заключить:

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

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

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

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

Глава 2 содержит теоретическое обоснование адаптивного метода кодирования «стопка книг» и его модификации с использованием разделения на кластеры.

В разделе 2.1 содержится описание работы стандартного алгоритма «стопка книг» и его анализ.

В разделе 2.2 приводится модифицированный метод кодирования и его анализ с точки зрения возможностей по сжатию информации, а также сравнение со стандартным методом.

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

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

Пусть х- слово в алфавите А, /(х)-его код, полученный при разделении алфавита на кластеры, тогда верхняя граница длины кодового слов: на выходе кодера не будет превосходить величины, определяемой по фор муле 1:

(\а\

|/(х)|<|.г|*1о8 у *Мк +|дг|*(|о8(1о8И+1) + с), (1)

V

где N- число кластеров в алфавите, Л/'- величина, равная математиче-кому ожиданию N кластеров.

N

Как видно из полученной формулы (1), при м' (случай равно-

ероятного источника с максимальной энтропией) код по избыточности удет хуже наилучшего кодирования по методу Хаффмена для конкретно-о источника с известной заранее статистикой на величину Г 1о8Ы+ 1

»е —-- + С . Стандартный метод «стопка книг», предложенный Ряоко,

уже. Его избыточность имеет величину 1о§(1о§|л |+1)+С. Таким образом, ведение кластеров повышает экономичность кодирования. Этот выигрыш аиболее заметен, если величина -ь 1 о 0(1), то есть при малых разме-ах алфавита, что является актуальным при практической реализации, так ак с увеличением мощности алфавита усложняется аппаратная реализация лгоритма (требования по необходимой для работы памяти и быстродейст-ию). Для случая 8-ми разрядных букв (|л|=256) среднее чиСло символов ода на букву входного слова х не превосходит в худшем случае 12,169925 а ¡рядов, что на 12,5% лучше, чем для стандартного алгоритма «стопка ни г».

Введение кластеров можно осуществлять различными способами. При гом предельным случаем является введение границ между всеми буквами пфавита А. Размер кластера в этом случае равен единице. Можно разбить пфавит на кластеры равного размера. Например, при мощности алфавита л |=16 размер кластера может быть две, четыре или восемь букв в кластере. 1ожно также объединять в кластеры блоки алфавита \А |, в которых кодовые оследовательности, соответствующие буквам алфавита источника, имеют динаковое число разрядов.

В разделе 2.3 анализ динамических характеристик модифицированно-э метода.

К динамическим характеристикам настройки алфавита «стопки книг» ожно отнести, во-первых, общее время, затрачиваемое алгоритмом на об-аботку поступившей на его вход информации, а также время, затрачивае-ое на поиск и передачу одной буквы, во-вторых, время настройки «стопки ниг» под входной процесс в случае изменения статистики источника на ходе кодера.

Рассмотрим первую характеристику.

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

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

Максимальная (верхняя) оценку сложности алгоритма при обработк входного информационного потока в случае стандартного метода «стопк книг» будет:

Ч^ЬИМ7-.,-. - г*.)- (2)

Для модифицированного алгоритма:

т п)

*ср..н т \-> i

Произведём сравнение обоих методов по максимальным характеристи кам (формулы 2 и 3).

к т + т

" гтиия UtiLi- ГМВМ лЛ_

(4)

£ __ стинд макс _ еравн_обм

~ К......... "Z

мол Макс Т I об*

ср"" \А\

Здесь С - безразмерная константа, показывающая во сколько раз моди фицированный метод быстрее стандартного при обработке одинакового ело ва на входе кодера.

Так-как « гср,„, то (4) можно привести к виду

С=1+^=-. (5)

ерявн

К)

В том случае если Т^»Т^, то выигрыш, получаемый при использо-ании модифицированного алгоритма равен мощности алфавита | А |.

Из формул 5 следует, что при достаточно большом входном слове при одировании модифицированным методом будет затрачиваться не больше ремени, чем при кодировании стандартным алгоритмом. А в случае, когда гяичины Т^ и имеют примерно один и тот же порядок (в зависимо-ги от конкретной аппаратуры, на которой реализуется алгоритм), выигрыш удет составлять примерно 2 раза при использовании кластеризации на нажую букву алфавита.

Рассмотрим вторую характеристику.

При использовании адаптивного алгоритма сжатия цифровой инфор-ации типа «стопка книг» в режиме реального времени встаёт задача оценки зксимальной продолжительности адаптации алфавита под новую входную гатистику. Расчет максимального времени адаптации необходим по сле-ующим причинам. В момент перестройки алфавита «стопки книг» на но-ую входную статистику избыточность потока на выходе кодера значитель-□ возрастает. Для устранения этого на выходе кодера необходимо постаять накопительный буфер. Размер этого буфера будет зависеть от периода лаптации алфавита.

Для оценки необходимого объема накопительного буфера воспользуйся следующей формулой

С = N * (/„- О, (6)

где С- объём буфера в битах; - среднее число разрядов кодового ал-авита на входную букву для данного процесса; максимальное число прядов буквы кодового алфавита; ТУ- число букв источника, после поступ-:ния которых система адаптируется под входной процесс.

Величину /„„ можно рассчитать по формулам, полученным Б.Я. Рябко. еличина /,, подсчитывается по формуле

'ч.=ХаЧ. (7)

/-1

»

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

Расположение букв алфавита адаптивного алгоритма «стопка книг» в обой произвольный момент времени будем рассматривать как п-мерный

вектор, размерность которого определяется мощностью алфавита. Назове! его вектором статистики алфавита в произвольный момент времени. Точк на п-мерной плоскости, в которой выполняется условие монотонности дл данной входной статистики (то есть Р; < Р2 <....< Р„,Р„- вероятность появле ния п-ой буквы во входном слове), назовем точкой абсолютной настройки н статистику входного потока. Так как согласно принципу работы как стаи дартного, так и модифицированного алгоритмов «стопка книг» с поступль нием очередной буквы на вход кодера происходит её перемещение на пер вую позицию в «стопке книг» и изменение положения вектора статистик алфавита в п-мерном пространстве. Работа алгоритма направлена на то, чтс бы как можно ближе подойти к точке абсолютной настройки.

Процесс адаптации схематично можно представить рисунком 1.

д

Рис 1.

Здесь точка 1 соответствует начальному положению вектора статистн ки. Точка 2 соответствует положению абсолютной настройки. Будем сч1: тать, что «стопка книг» настроилась, если вектор статистики для данног входного процесса попал в область д.

Среднее отклонение вектора статистики для кодирования входног цифрового потока по методу «стопка книг», приходящееся на букву алфав! та, оценим по формуле:

И

(8)

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

Для получения оценочного значения N необходимо найти

[Л^А^Х,;/), (9)

где Ха- исходное положение вектора статистики, определяемое ра: мещением букв алфавита источника в «стопке книг»; Х1 - стационарное пс

жение этого же вектора после настройки; Р- матрица переходов для букв много вектора во все возможные состояния в «стопке книг».

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

иг». Поэтому целесообразно в качествеХ„ выбирать именно этот вектор, ационарное положение вектора статистики также можно считать извест-'

ш при наличии вероятностного описания источника. Вектор х„ определя-

исходный вид матрицы переходов. Вектор X, даёт стационарное распо-жение букв в «стопке книг». Будем считать, что буква настроилась на ста-стнку источника, если выполняется следующее соотношение

А.., +©

(10)

=<"„„ -е

Здесь ',„„ - стационарное положение /-ой буквы в «стопке книг»; ©-еднее отклонение, приходящееся на букву при данном входном процессе, ссчитывается по формуле (8); рв -вероятности перехода /-ой буквы и на-

льного положения, определяемого вектором Х„, в у положение в «стопке иг» через N шагов. Для нахождения значений р9 можно либо производить посредственное /V кратное перемножение матриц, либо воспользоваться юизводящими функциями.

Вся дальнейшая процедура расчета числа шагов сводится к следующей ерационной схеме: расчет области © для каждой буквы по формуле (8); счет матрицы переходов за n шагов; проверка попадания букв алфавита в ласть настройки, найденную по граничным условиям (формула (10); если ловия формулы (10) выполняются для всех букв, то считаем, что период аптации закончен и равен /V; если формула (10) выполняется не для всех кв, то увеличиваем число шагов и повторяем весь цикл действий до нахо-юния результата.

Найденное значение N подставляем в формулу (6) и получаем размер фера памяти в битах, необходимый для устранения перегрузок в канале.

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

Так как при использовании стандартного алгоритма «стопка книг» емя обработки как одной буквы, так и всей входной последовательности щественно зависит от размера алфавита согласно формулам (2) и (3), то

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

При анализе данной возможности было доказано следующее утвс ждение:

При разделении исходного алфавита \а \ на подмножества :

1. Значительное сокращение числа операций.

2. Ухудшается степень сжатия информации по сравнению с исходнь методом «стопка книг» без использования разделения алфавита подмножества.

Данное утверждение справедливо как для стандартного, так и для м дифицированного методов типа «стопка книг».

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

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

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

Учитывая приведённые выше выводы, формула для оценки длины п следовательности на выходе кодера для стандартного метода «стопка кни принимает вид

|/(x]|s|*|*F(jf)+|*|*(log(log |л|+1)+2+ д)

|/4| = 2s'a

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

Для модифицированного метода «стопка книг» формула для оцен длины последовательности на выходе кодера в случае введения кластеров каждую букву имеет следующий вид

|/(*]| < |xj * logM + |xj * (log(log|^| +1)+ 2 + Д)

И=2-

И - (12)

Л/ <

2

В разделе 2.6 предлагается методика реализации модифицированного етода при организации алфавита в виде списка.

Число операций, выполняемое при поступлении очередной буквы на сод кодера, при такой организации «стопки книг» строго фиксировано и не [висит от мощности алфавита. Это позволяет увеличить мощность алфави-1. то есть перейти от кодирования отдельных букв источника к кодировало блоков из букв источника. При этом происходит учет статистических ¡язей между соседними отсчетами.

По результатам второй главы можно сделать следующие выводы:

® на базе адаптивного алгоритма сжатия цифровой информации типа :топка книг» разработана его модификация с использованием кластериза-лп, повышающая степень сжатия информации;

• предложена методика для оценки динамических параметров адап-1вных алгоритмов, позволяющая получить оценку для накопительного буера при построении практических схем реализации алгоритма;

• математически доказан рост верхней границы по сжатию информа-1И при использовании древовидного построения алфавита;

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

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

В главе 3 приводятся алгоритмы работы программной модели кодера для стандартного и модифицированного алгоритмов типа «стопка книг» и 1ализ вероятности возникновения ошибки при использовании данных ме->дов кодирования.

В разделе 3.1 анализируются алгоритмы работы стандартного и мо-1фицированных методов адаптивных алгоритмов типа «стопка книг». Экс-¡риментальная проверка результатов, теоретически обоснованных в главе проводилась с использованием программной модели адаптивного кодека 1я стандартного и модифицированного алгоритмов типа «стопка книг», рограммные модели были построены для следующих вариантов реализа-1и алгоритма.

Стандартный алгоритм «стопка книг».

«Жесткая» кластеризация на каждую букву алфавита «стопки» с перио-

дической подстройкой.

3. Кластеризация на блоки с равным размером кодов и непрерывной адап тивной подстройкой.

4. Кластеризация на каждую букву алфавита «стопки» с непрерывной адаг тивной подстройкой.

5. Кластеризация на каждую букву алфавита «стопки» с непрерывной ада! тивной подстройкой и предварительной первоначальной настройкой помощью стандартного алгоритма «стопка книг».

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

В разделе 3.2 анализируется вероятность возникновения ошибки пр использовании стандартного и модифицированного алгоритмов типа «стог ка книг», вызванная канальным ошибкам.

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

Согласно полученным данным, влияние ошибки, вызванной непр; вильным декодированием номера позиции для модифицированного метод значительно меньше, чем для стандартного алгоритма, что объясняется осс бенностями функционирования модифицированного алгоритма, подроби рассмотренными в главе 2.

Из результатов, приведенных в третьей главе, следует:

• принцип действия модифицированного алгоритма типа «стопк книг» позволяет добиться в случае кластеризации на каждую букву незав! симости времени выполнения операции кодирования от мощности алфав! та, что невозможно в случае стандартного метода «стопки книг».

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

Глава 4 содержит результаты исследований звуковых источников ш формации при использовании в качестве сжимающих алгоритмов стандар ного и модифицированного методов.типа «стопка книг».

В данной главе экспериментально исследуются возможности алп ритмов при сжатии звуковой информации. При этом исследования провод:

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

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

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

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

• время настройки минимально для стандартного метода стопки книг;

• минимальным отклонением от положения настройки обладает моди-ицированный метод с использованием кластеризации на каждую букву;

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

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

• адаптивный алгоритм сжатия цифровой информации типа «стопка 1иг» и его модифицированные варианты могут успешно использоваться 1я передачи данных от звуковых источников на скоростях в два раза мень-с, чем при использовании ИКМ с сохранением того же субъективного ка-:ства сигнала. Это превосходит значение субъективной оценки качества по капе MOS, полученное для адаптивной дифференциальной импульсного вой модуляции (стандарт G.726 при скорости передачи информации 32 бит/с).

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

• математически доказано, что при использовании модификации вер; няя граница по сжатию меньше границы для стандартного алгоритма «стог ка книг».

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

• математически доказан рост верхней границы по сжатию информаци при использовании древовидного построения алфавита.

• предложен метод предварительного разностного кодирования и > основе экспериментальных результатов показано, что для звуковых исто1 ников он даёт лучший результат, чем кодирование разностного сигнала.

На основании результатов проведенных экспериментов автор считас перспективным применение разработанных им методик для применения линиях связи для речевых источников, работающих в режиме реальног времени, с высокими требования к качеству передаваемой речи при скор< стях передачи 32 Кбит/с, а также при передаче высококачественной музь кальной информации с частотой дискретизации 44 кГц для получения стере звучания без увеличения пропускной способности канала и сохранении и ходного качества передачи.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ ОПУБЛИКОВАНЫ В РАБОТАХ

1. Волохович А. В. Анализ алгоритмов стандартного и модифицированно1 метода кодирования цифровой информации типа «стопка книг» с точь зрения их быстродействия//Тез. докл. на научно-технической конфере: ции факультета «Радиоэлектроники и технической кибернетики» Ниж городского государственного технического университета, посвящённс 80-летию Нижегородского государственного технического университет -Н.Новгород, 1997.

2. Волохович А. В. Сравнительный анализ алгоритмов работы программно модели кодера для стандартного и модифицированного алгоритмов пи «стопка книг».// В печати.

3. Волохович А. В. Анализ модифицированного адаптивного алгоритл сжатия цифровой информации типа «стопка книг»//Вестник Верхн Волжского отделения Академии технологических наук Российской Фед рации, серия: «Высокие технологии в радиоэлектронике».-1996.-1(2).-| 137-140.

4. Волохович А. В. Динамические характеристики адаптивного алгори™ сжатия цифровой информации типа «стопка книг» с использованием кл

стеризации»//Вестник Верхне-Волжского отделения Академии технологических наук Российской Федерации, серия: «Высокие технологии в радиоэлектронике» 1996,-1 (2).-С. 141-142.

5. Волохович А. В. Модификация метода сжатия цифровой информации «стопка книг»//Системы обработки информации и управления. Межвузовский сборник научных трудов.-Н.Новгород, 1995.-140 с.

6. Волохович А. В., Крылов В. В. Реализация модифицированного метода «стопка книг»//Тез. докл. на научно-технической конференции факультета «Радиоэлектроники и технической кибернетики» Нижегородского государственного технического университета, посвященной 100-летию изобретения Радио А. С. Поповым и 50-летию победы в Великой Отечественной войне. - Н. Новгород, 1995.-46 с.

7. Волохович А. В. Экспериментальное исследование энтропийных характеристик звуковых источников информации// Тез. докл. на научно-технической конференции факультета «Радиоэлектроники и технической кибернетики» Нижегородского государственного технического университета, посвященной 80-летию Нижегородского Государственного технического университета. - Н. Новгород, 1997.

8. Крылов В. В., Волохович А. В. Модификация метода сжатия цифровой информации «стопка книг»// «100-летие начала использования электромагнитных волн для передачи сообщений и зарождения радиотехники»: Тез. докл. Международной конф., объединённой с 50-й Научной' сессией, посвященной Дню радио, ч. 2.-Москва, 1995.-328 с.

Поли, к печ. 9.04.98. Формат60x84 '/16. Бумага Офсетная. Печать офсетная. Уч.-изд.л. 1,0 .Тираж 100 экз. Заказ 187.

Типография НГТУ. 603600, Нижний Новгород, ул.Минина, 24.