автореферат диссертации по радиотехнике и связи, 05.12.13, диссертация на тему:Сжатие текстовых сообщений при передаче по телефонным каналам связи

БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ

АССАНОВИЧ Борис Алиевич

СЖАТИЕ ТЕКСТОВЫХ СООБЩЕНИЙ ПРИ ПЕРЕДАЧЕ ПО ТЕЛЕФОННЫМ КАНАЛАМ СВЯЗИ

Специальность 05.12,13. -Системы и устройства радиотехники и средств связи

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

Минск, 1998

УДК 621.391

гг ОД

Работа выполнена в Гродненском государственном университете им. Я.Купалы

Научный руководитель - кандидат технических наук С-ЮРИН В.Н. Официальные оппоненты:

доктор технических наук, профессор КЛЮЕВ Л.Л. кандидат технических наук, доцент КВАША В.И.

Оппонирующая организация - НПО «Агат»

Защита состоится « 4 » июня 1998 г. в 14. 00 на заседании совета по защите диссертаций Д. 02 Л 5.02 в Белорусском государственном университете информатики и радиоэлектроники по адресу: 220027, г. Минск, ул. П. Бровки, 6.

С диссертацией можно ознакомиться в библиотеке Белорусского государственного университета информатики и радиоэлектроники.

Автореферат разослан «¿3» о И - 1998 г.

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

С.Б.САЛОМАТИН

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

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

Наиболее распространенными каналами для передачи данных все же остаются проводные линии связи коммутируемой телефонной сети. Одним из направлений повышения скорости передачи информации является разработка эффективных процедур компрессии сообщений, в том числе текстовых, которые являются наиболее простой и удобной формой представления информации. После принятия протокола сжатия У.42Ыз новых международных и промышленных стандартов опубликовано не было. Однако, используемые телефонные каналы подвержены действию помех, поэтому существует проблема комплексного решения вопросов сжатия данных и их защиты от ошибок. С другой стороны в цифровых системах передачи информации (ЦСП) возникает необходимость эффективного преобразования данных в многопозиционные коды, а в мобильных системах требуется сокращение времени на прием-передачу текстовых сообщений. Поэтому проблема сжатия текстовых данных является актуальной и ее решение позволит повысить эффективность современных систем телекоммуникаций.

Связь с научными программами, темами. Основные результаты диссертационной работы представлены в хоздоговорной НИР "Исследование условий прохождения сигналов по каналу с помехами", проводившейся между кафедрой радиофизики и электроники Гродненского госуниверситета и НИИ средств автоматизации НПО "Агат", и госбюджетной НИР "Разработка элементов информационных технологий, выполняемой творческим коллективом с участием автора, № ГР 199961190 и координируемой НАН Беларуси в рамках республиканской программы фундаментальных исследований "Электроника". *

Цель и задачи исследования. Целью диссертационной работы является разработка и исследование методов сжатия текстовых сообщений для

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

1. Разработать алгоритм построения недвоичного неравномерного кода для сжатия символов с одинаковой вероятностью;

2. Найти алгоритм построения двоичного неравномерного кода для символов с заданным распределением вероятностей, ограничивающий распространение ошибок при передаче по телефонным каналам связи;

3. Разработать способ сжатия текстовых данных при пословном их кодировании для передачи по телефонным каналам;

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

5. Проверить эффективность разработанных методов моделированием на ЭВМ.

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

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

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

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

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

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

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

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

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

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

Основные положения, выносимые па защиту: ' Переход от неравномерной структуры потока сжатых данных к блочной равномерной с одновременным объединением с процессами помехоустойчивого кодирования позволяет: ограничить процесс

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

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

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

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

Личный вклад соискателя. Основные научные положения, теоретические и практические выводы, содержащиеся в диссертации, были получены автором самостоятельно. К ним относятся: разработка алгоритма построения q-ичнoгo неравномерного кода для источника с равновероятными символами; разработка алгоритма рекуррентного неравномерного кодирования; разработка способа пословного сжатия текстов; разработка способов объединения неравномерного кодирования с помехоустойчивым; разработка методики обнаружения ошибок при блочной передаче неравномерных кодов; модификация математической модели потоков ошибок в дискретных каналах связи; разработка программ и устройств, реализующих предложенные методы.

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

Апробация результатов диссертации. Основные положения

диссертации обсуждались на кафедре радиофизики и электроники Гродненского госуниверситета, на кафедре радиотехнических систем БГУИР. Апробация результатов диссертации проводилась на всесоюзной конференции "Микропроцессорные средства локальной автоматики" (Гродно, ГрГу, май 1989 г.), на 3-м межреспубликанском семинаре "Физика быстропротекагощих плазменных процессов" (Гродно, ГрГу, май 1992 г.), на 25-ой юбилейной научно-технической конференции МВВИУ "Проблемы совершенствования и эксплуатации радиоэлектронного и радиотехнического вооружения и АСУ" (Минск, МВВИУ, май 1993 г.), на международной научно-технической конференции "Современные средства связи" (Нарочь, БГУИР, октябрь 1995 г.), на научно-технической конференции "Современные методы обработки сигналов в системах измерения, контроля, диагностики и управления" (Минск, БГУ, декабрь 1995 г.), на республиканском научно-техническом семинаре-сессии "Организация и технология средств связи" (Минск, Высш. колледж связи, июнь 1996 г.), на 2-ой международной конференции "Новые информационные технологии в образовании" (Минск, БГЭУ, ноябрь 1996 г.), на 2-ой международной научно-технической конференции "Современные средства связи" (Нарочь,БГУИР,сентябрь 1997 г.).

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

Структура и объем диссертации. Диссертационная работа включает в себя введение, общую характеристику работы, 4 главы, выводы, список использованных источников, включающий 71 наименование на 5 стр., 10-ть приложений на 29 стр., 13 иллюстрации на 10 стр., 18 таблиц на 9 сгр. Полный объем диссертации составляет 130 страниц. Список использованных источников дан в порядке следования ссылок по тексгу.

ОСНОВНОЕ СОДЕРЖАНИЕ В первой главе диссертации проводится обзор и анализ методов сжатия в системах хранения и передачи информации. Рассмотрены свойства неравномерных кодов, которые находят применение в системах сжатия текстовых сообщений, методы компрессии, использующиеся в программах архивации данных, протоколы сжатия. В результате анализа литературных данных показано недостаточное исследование применения методов укрупнения алфавита и недвоичных кодов, обоснована необходимость использования при сжатии дополнительных мер по защите информации от ошибок.

Во второй главе разработан алгоритм построения оптимального неравномерного ц-ичного кода для источников с равновероятными сообщениями. Если рассмотреть источник, порождающий N символов одинаковой вероятности и поставить в соответствие символам источника кодовые слова некоторого кода с основанием ц, то, в случае некратности объема алфавита (числа N ) степени q, избыточность источника позволяет построить кодовый словарь из N слов с длинами и ]Iog2N[+l. Для

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

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

МЮ- ]1о8,М + —1—( чСЫ-ч^^Мч'^'-ЮтосКч-!)).

Показано возможное применение таких кодов для ЦСП, где достигается сжатие с коэффициентом 1.2-1.3.

Рассмотрен алгоритм построения рекуррентного неравномерного двоичного кода для вероятное гного источника и оценена его средняя длина в сравнении с неравномерным кодом Шенноиа-Фано. Показано, что в случае наличия некоторого источника с заданным распределением вероятностей появления N символов {Pi, Р2, ..., Pn}, можно построить рекуррентный двоичный неравномерный код путем k-кратного расширении шагов алгоритма построения рассмотренного q-ичного кода. Найденный код будет содержать 2к +1 двоичных кодовых комбинаций. При этом значение к можно найти из неравенства: 2k + lzN.

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

В работе построены рекуррентные неравномерные коды для русского и английского алфавитов. Найден неравномерный код для нерасширенного набора 128 ASCII символов с заданным с распределением вероятностей. Средняя длина кода составила 5.45 бит на символ, что дало возможность получить коэффициент сжатия К„=1.28 по сравнению с равномерным кодированием символов 7-ю битами.

Предложен способ сжатия информации, основанный на укрупнении алфавита путем кодирования слов английского языка блоками из 3-х байт. Для этой цели используется основной словарь, объемом Ni слов, содержащий кодируемые слова и их адреса, являющиеся фактически кодом сжимаемого слова, и вспомогательные словари, содержащие конечные и начальные символы, которые образуются из знаков препинания, окончаний, суффиксов, префиксов слов языка и управляющих символов текста. Каждому слову (символу) такого укрупненного алфавита ставится в соответствие двоичное слово из [log}Ni] разрядов, определяющее его номер в основном словаре, и код

для цепочки из конечных и начальных символов из //о&лу и /7о£?Лу бит, указывающих на их номера во вспомогательных словарях. С учетом объемов известных словарей английского языка и возможного числа дополнительных цепочек символов, Л^ было ограничено величиной 216, а N2 - 26. В результате проведения исследований для достижения необходимой эффективности сжатия в алгоритме было решено анализировать 4 состояния кодируемого слова: наличие конечного символа; появление заглавной буквы; наличие заглавной буквы и конечного символа; наличие начального символа. Для кодирования этих 4-х состояний достаточно ввести флаг-указатель из двухбитовой комбинации, что в сумме с 6-ю битами кода конечного или начального символа дает полный байт. Для кодирования адреса слова в основном словаре используются 2 байта. Таким образом, выходной код слова составляет 3 полных байта, т.е. состоит из следующих частей: адреса слова в основном словаре, адреса символа во вспомогательном словаре и флага-указателя. Для возможности работы алгоритма с произвольными текстами, при отсутствии эквивалента кодируемого слова в основном словаре вместо его адреса на выход схемы сжатия передается зарезервированное значение двухбайтового флага-вставки и байт, содержащий двоичный код длины не найденного слова. При этом кодируемое слово без изменения следует за указанными 3 байтами. При декомпрессии достаточно дешифрировать значения 3-х байтов кодового блока. Абсолютный коэффициент сжатия способа может быть определен как: К.=и,-11оЕ2п1/(|1о82М1]+{1од2Ыв1+(1оВ2р1)1 где Ьс,- средняя длина слова; п- число двоичных символов, приходящихся на букву слова; М,-тах{И2Мз}- максимальное количество слов во вспомогательных словарях; Р- число двоичных символов, использующихся для флага-указателя.

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

В третьей гллпе разработано 2 метода функционального объединения процедур сжатия с помехоустойчивым кодированием. Сущность 1-го метода заключается в следующем. На передаче к последовательности кодовых символов переменной длины к', составленной из совокупности неравномерных кодовых комбинаций, добавляется служебная комбинация фиксированной длины /. С помощью ее кодируется расстояние от конца информационной части переменной длины к' до начала служебной комбинации, выраженное в числе незаполненных позиций /'. Затем определяются значения г проверочных символов корректирующего кода в зависимости от значений символов информационной части фиксированной длины к=к'+1' и служебной комбинации I. Сформированный кодовый блок длинной п=к+г передается в канал. Таким образом, для правильного разделения неравномерных комбинаций формируется плавающая меткаопределяющая местоположение конца последовательности к'. На приеме кодовой блок из п символов сначала декодируется как (п,к) код. После исправления ошибок в соответствии со служебной комбинацией /, содержащей двоичный код, соответствующий числу /', определяется местоположение границы / или длина группы к'. Затем последовательность к' разделяется на ряд неравномерных комбинаций, соответствующих совокупности символов кодируемого источника. При таком кодировании улучшение использования пропускной способности Б в числе двоичных символов для источника с заданным распределением вероятностей и равновероятного составит соответственно

где п - длина кодового блока; Ь - средняя длина кодового слова неравномерного кода; N - число символов источника; 1т„ - максимальная длина неравномерной комбинации;

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

Предложен также другой способ объединения неравномерного кодирования с помехоустойчивым, когда в зависимости от суммарной длины неравномерных комбинаций могут изменяться параметры помехоустойчивого кода, т.е. его информационная длина к избыточность г=п-к, кратность исправляемой ошибки /. Рассмотрим структуру кодового блока такого кода. Совокупность неравномерных комбинаций . обозначим как к)', число проверочных символов корректирующего кода как г,. При условии, что величина ri имеет изменяющуюся длину в зависимости от изменения общей длины неравномерных комбинаций V- К блоку из к символов добавим служебную комбинацию длины /, которая будет указывать на номер помехоустойчивого кода, которым кодирован текущий кодовый блок. Это позволит однозначно его декодировать декодером соответствующего корректирующего кода. Общая длина блока составит т= к+г+1 символов. В отличии от предыдущего способа формирования блочной структуры из неравномерных комбинаций здесь отсутствует комбинация из нулевых символов заполнителей /', что позволяет более эффективно использовать применяемый для передачи данных канал связи,

Рассмотрена реализация методов объединения неравномерного алфавита с корректирующим кодированием, выполненная на уровне функциональных схем с использованием ПЗУ и стандартных цифровых элементов.

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

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

В четвертой главе произведена модификация математической модели дискретного канала, что позволило реализовать генерацию как независимых ошибок с некоторым распределением, так и отдельных пакетов ошибок. Процесс формирования потока ошибок рассматривается как марковский, имеющий два состояния- "хорошее" Е0 и "плохое''-Ej. В "хорошем" состоянии количество искаженных сигналов имеет биномиальное распределение с вероятностью одиночной ошибки е0. В "плохом" состоянии в канале возникают пакеты ошибок, вероятность ошибки на двоичный символ здесь ei>e0. Если описать такой процесс матрицей переходных вероятностей 2-го порядка, выбрать значения двух ее элементов, скажем, Роо и Рц, то остальные два P<¡i и Р,о будут зависимы от них. Для такой цепи Маркова существуют предельные, стационарные вероятности Ро и Р|, характеризующие состояния Е0 и Ej. Полная вероятность ошибки Рош передачи одного кодового символа будет равна

Рош=Ро-е0 + Рге|

Для заданных величин еь Рош . Р0о, Рц остальные параметры могут быть найдены на основе выражений связи между ними. Тогда, задавая «пакетирование ошибок» вероятностью е'|, значение ео можно найти как

(1-Я,,)/(2-?„-/>„)•

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

накладывать их на информационные последовательности, проводить имитацию передачи информации.

Для расчета эффективности компрессии текстовых сообщений в соответствии с предложенным методом рекуррентного неравномерного кодирования, путем моделирования, была проведена оценка сжатия английских текстов по научно-технической тематике. Для найденного неравномерного кода со средней длиной 5.45 бит на символ, абсолютный Ка и относительный К0 коэффициенты сжатия получили в среднем значения 1.4 и 71%, что незначительно отличается от параметров оптимального неравномерного кода Хаффмена, которые для него имели значения 1.5 и 67%. Сравнение свойств восстановления синхронизации этих кодов при возникновении и размножении ошибок проводилось на основе разработанной модели для различных состояний имитируемого канала при значениях Р0ш—0.01 и 0.05. Найденная средняя длина распространения ошибок для рекуррентного кода и кода Хаффмена составила 4.7 для Ррш= 0.05; 2.6 для Рош= 0.01 и 6.8 для Рош= 0.05; 3.1 для Рош= 0.01 для обоих кодов соответственно. Это подтвердило преимущество свойств ограничения распространения ошибок первого кода.

Исследованы свойства обнаружения ошибок различных неравномерных кодов при передаче их блоками с использованием кода Хемминга, исправляющего однократную ошибку. Результаты моделирования показали, что способность обнаружения двухкратной ошибки при фиксации ошибочного блока зависит от структуры используемого кода и изменяется от 30 до 50%. Определение зависимости вероятности ошибочного блока от его длины при разных значениях Рош, показало, что количество блоков с необнаруженной ошибкой резко возрастает до тех пор пока длина блока не достигнет 2Ьтах, а затем почти не изменяется и принимает значение 60-90% в зависимости от используемого кода и количества ошибок в канале.

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

осуществляющие компрессию-декомпрессию на основе созданных основного н вспомогательных словарей. При этом основной словарь содержал более 30000 слов, а два вспомогательных по 64 цепочки каждый. Исследование степени сжатия проводилось для 6-ти различных по содержанию текстовых файлов. Результаты показали, что для созданного словаря но тематике телекоммуникаций коэффициент К„ имеет в среднем значение 1.45 и изменяется в пределах от 1.36 до 1.67 в зависимости от степени ориентированности текста на использующиеся словари. Из сравнения архиватора arj версии 2.41 с двухступенчатой схемой компрессии (пословное кодирование + arj-архивирование) следовало превосходство последней по коэффициенту К0 порядка на 5%. Проведенное дополнительное сжатие предварительно подвергнутых компрессии 6-ти указанных файлов с использованием протокола V.42bis, аппаратно реализованного в модеме US Robotics Sporter 14400, при передаче по телефонному каналу показало, что предварительно сжатые пословным кодированием файлы дополнительно сжимались еще в 1.5 раза. В итоге это дало результирующий коэффициент сжатия, равный 2.2, что значительно выше коэффициента Ка=1.7 при передаче исходных текстов. Найденное время работы программы позволило сделать вывод, что используя даже простой дихотомический поиск по словарю, можно пословно сжимать текст в реальном масштабе времени при передаче информации по телефонным каналам связи со скоростью 9600-14400 бит/сек.

ВЫВОДЫ

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

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

1. Разработанный оптимальный q-ичный неравномерный код для символов с одинаковой вероятностью появления содержит кодовые слова, отличающиеся на единицу и может быть применим в кодопреобразователях ЦСП, что позволяет получить выигрыш по пропускной способности в 1.2-1.3 раза по сравнению с кодированием линейным кодом типа 2ВЗТ.

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

3. Разработан способ сжатия текстовых сообщений на основе пословного их кодировании блоками из трех байт, позволяющий получить коэффициент сжатия в пределе равный трем при полной ориентированности текста на созданные основной и вспомогательный словари. Незначительное изменение побайтовой статистики после компрессии позволяет дополнительно применить стандартные процедуры сжатия, например протокол У.42Ыэ или архивацию данных. Эффективность предложенного способа пословного сжатия при использовании схем двухступенчатой компрессии выше в среднем в 1.5 по сравнению со стандартными процедурами сжатия.

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

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

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

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

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

1. Иванов H.H., Сюрин В.Н., Ассанович Б. А. Проектирование каналов связи локальной управляющей сети // Микропроцессорные средства локальной автоматики: Тез. докл. на всесоюз. конф.- Гродно, 1989.- с.80-82.

2. A.c. 1651385 AI СССР, МКИ Н 03 М 13/00. Помехоустойчивый кодек для передачи дискретных сообщений / В.Н.Сюрин, Б.А.Ассанович, Н.В.Беланович, В.М.Дубко (СССР). - № 4664539/25; Заявл. 20.03.89; Опубл. 23.05.91, Бюл. №19.-8 с.

3. Ассанович Б.А., Сюрин В.Н. .Статистическое кодирование дискретных сообщений с исправлением ошибок // Сб. науч. тр. учеб. завед. связи. Элементы и устройства систем связи,- JI.. изд. ЛЭИС, 1991.- с. 51-56.

4. A.c. 1727201 A2 СССР, МКИ Н 03 М 13/00. Помехоустойчивый кодек для передачи дискретных сообщений / Б.А.Ассанович, Т.А.Ситкевич (СССР).-№ 4851062/24; Заявл. 10.07.1990; Опубл. 15.04.92, Бюл. № 14,- 9с.

5. Ассанович Б.А., Каширский B.C., Лохницкий A.A. Обнаружение ошибок при передаче статистических данных // Физика быстропротекающих плазменных процессовгТез. докл. на 3 Межресп. сем.- Гродно, 1992.- с.50.

6. Ассанович Б.А., Хомбак И.Л. О методе сжатия информации в системах приема-передачи сигналов И Проблемы совершенствования и эксплуатации радиоэлектронного и радиотехнического вооружения и АСУ: Тез. докл. 25-ой юбилейной науч.-тех. конф. МВВИУ.- Минск, 1993.

7. Ассанович Б.А. Оптимальный q-ичный код для источника с равновероятными сообщениями II Современные средства связи: Матер, междун. науч.- тех. конф. - Нарочь, 1995, с.18 -20.

8. Ассанович Б.А., Олешкевич С.Б. Моделирование каналов связи с помехами // Современные средства связи: Матер, междун. науч.- тех. конф,-Нарочь, 1995.-с. 15-17.

9. Ассанович Б.А. Передача данных с использованием нового класса неравномерных кодов // Современные методы обработки сигналов в системах измерения, контроля, диагностики и управления: Матер, науч.-тех. конф. Ч. 1.- Минск, БГУ, 1995.- с.10-12.

10. Ассанович Б.А. Сжатие сообщений на основе методов синтаксического кодирования / Организация и технология средств связи: Магер. Республ. науч.-тех. семинара-ссесии // Вестшк Сувязь- 1996, № 2.- с.6.

11. Ассанович Б.А., Сюрин В.Н., Олешкевич С.Б. Применение технологии сжатия в образовании// Тр. 2-оймежд. конф,- Минск, 1996.-с. 299-300.

12. Ассанович Б.А. Программная реализация метода пословного сжатия информации / Современные средства связи: Матер. 2-ой международной науч.-тех. конференции // Спец. выпуск жур. «Известия Инженерной Академии«-1997, №1(3/1).-с. 33-37.

/?

17

РЭЗЮМЭ

Ассанов1ч Барыс Ал!ев1ч СЦ1СКАННЕ ТЭКСТАВЫХ ДАННЫХ ПРЫ ПЕРАДАЧЕ ПАТЭЛЕФ0Ш1ЫМ КАНАЛАМ СУВЯ31

Клтчавыя словы: шфармацыя, сцкканне тэкста, недваичны нераунамерны код, рэкуррэнтны нераунамерны код, паслоунае кадаванне, зналежванне иамылак, матэматычная мадэль.

У рабоце праведзенна даследаванне метадау сщ'скання тэкставых данных для перадачы па тэлефонных каналах сувязк Мэтай работы з'явшася распрацоука метадау сцккання тэкставых павядамленняу на аснове ¡х нераунамернага 1 паслоунага кадавання з магчымасшо перадачы па каналах з перашкодамь

Методыка даследавання асновывалась на выкарастанш тэорьн верагоднасцяу, метадау матзматычнай статыстьш, тэорьи л!чбау, метадау матэматычнага праграммфавання. Таксама праводз!уся эксперымент з выкарастаннем рыяльных каналау с увяз! ] устройств перадачы данных.

Распрацован алгарытм пабудавання недва1чнага нераунамернага кода для ¡сточн!ка з равнаверагодным» амвалам!, найдзена сярэдняя длша кода, распрацован алгарытм пабудавання нераунамернага кода, як1 абмяжовывае распраусюджаванне памылак, прапанован алгарытм сцккання тэкста на аснове паслоунага кадавання, як1 дазвол!у дасягнуць трохразовага сцккання, распрацованы спосабы аб'яднання памехаустойл!вага кадавання з нераунамерным, дазвол1ушыя дадаткова выяуляць памылю.

Распрацаваныя у рабоце метады сцккання у выглядзе праграм 1 устройствау могуць быць выкарыстаны пры кадаванш 1 перадачы тэкста па тэлефонных аналагавых 1 лобовых каналах сувяз! з выкарастаннем ¡снугочых пратаколау абмена данным!, а таксама прымяняцца у новых сктэмах пэйджынга 1 транка.

РЕЗЮМЕ

Ассанович Борис Алиевич СЖАТИЕ ТЕКСТОВЫХ СООБЩЕНИЙ ПРИ ПЕРЕДАЧЕ ПО ТЕЛЕФОННЫМ КАНАЛАМ СВЯЗИ

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

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

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

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

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

19

SUMMARY

Assanovich Boris Alievich COMPRESSION OF TEXT MESSAGES FOR TRANSMISSION THROUGH TELEPHONE CHANNELS

Key words: information, compression of text, variable length notbinary code, recurrent variable length code, whole word coding, error detection, mathematical model.

In work was done the investigation of compression methods of text data for transmission through telephone channels. The aim of work was the elaborating of compression methods of text messages on the basis of runlength and whole word coding with the possibility of transmission through noise channels. The apparatus of investigation consisted in the use of theory of probability, methods of mathematical statistics, numerical theory, methods of mathematical modelling. Also experiment was done with the use of real communication channels and data communication equipment.

Algorithm of notbinary variable length code for source of symbols with the same probability was elaborated, it's cost was found; algorithm of building variable length code, confining the spread of errors was elaborated; new manner of text compression on the basis of whole word coding with up to 3 times reducing it's size was offered, association methods of error correcting and variable length coding with additional error detection were elaborated.

The elaborated in work methods of compression as programmes and devices can be used for coding and transmission of text messages through telephone analog and digital channels v/ith the use of existing protocols of data exchanging and also can be applicated in new systems of trunk and paging.

АССАНОВИЧ Борис Алиевич

СЖАТИЕ ИНФОРМАЦИИ ПРИ ПЕРЕДАЧЕ ПО ТЕЛЕФОННЫМ КАНАЛАМ СВЯЗИ

Специальность 05.12.13 -Системы и устройства радиотехники и средств связи

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

Подписано в печать 09.04. 98 . Формат бумаги 60 х 84 1/16. Бумага офсетная. Печать офсетная.Усл печ. л. 1,28. Уч. - изд. л. 1,0. Тираж 90 экз. Заказ 206 .

Белорусский государственный университет информатики и радиоэлектроники.Отпечатано в БГУИР. Лицензия ЛП № 156. 220027, Минск, ул. П.Бровки, 6.