автореферат диссертации по радиотехнике и связи, 05.12.04, диссертация на тему:Минимизация распространения ошибок при неравномерном кодировании символов сообщений

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

НТО БИССЕ ЖАКИ ТЕРЕЗ

МИНИМИЗАЦИЯ РАСПРОСТРАНЕНИЯ ОШИБОК ПРИ НЕРАВНОМЕРНОМ КОДИРОВАНИИ СИМВОЛОВ СООБЩЕНИЙ

Специальность 05.12.04. Радиотехника, в том числе системы и устройства радионавигации, Радиолокации и телевидения

АВТОРЕФЕРАТ

Диссертации на соискание ученой степени Кандидата технических наук

Москва-2004

Работа выполнена на кафедре радиотехнических приборов Московского энергетического института (технического университета).

Научный руководитель: Официальные оппоненты:

Ведущая организация:

кандидат технических наук, проф. Александр Кириллович Нарышкин

доктор технических наук, Вадим Николаевич Безруков

кандидат технических наук, Леонид Алексеевич Белов

ОКБ МЭИ (г. Москва)

¿0

Защита состоится & 2004 г. в $ часов на засе-

дании диссертационного совета Д 212.157.03 при Московском энергетическом институте (техническом университете) по адресу: 111250, Москва, Красноказарменная ул., д 17, аудитория А - 400

Отзывы в двух экземплярах, заверенные печатью, просим направлять по адресу: 111250, Москва, Красноказарменная ул., д. 14, Ученый совет МЭИ (ТУ).

С диссертацией можно ознакомиться в библиотеке Московского энергетического института (технического университета).

Автореферат разослан

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

Д 212.157.03. . '» /

Кандидат технических наук, доцент. ! ¿///А/ (Х^ '('^У Т.И.Курочкина

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

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

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

Значительный вклад в развитие статистического кодирования информации внесен К. Шенноном, Р. Фано, Д.А. Хаффменом, А. Лемпелем, Д. Зивой, Р. Кричевским, Левенштейном, П. Нейманом, Трофимовым и др.

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

РОС НАЦИОНАЛЬНАЯ БИБЛИОТЕКА

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

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

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

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

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

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

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

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

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

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

- Разработано устройство, декодирующее предлагаемый код.

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

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

б

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

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

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

Структура и объем работы. Работа состоит из введения, четырёх глав, заключения, списка литературы содержащего 72 наименования и приложение. Объем диссертации составляет 111 страницы, включая 18 таблиц и 24 рисунка.

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

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

В первой главе - рассматривается на основе УДК и другие источников обобщенная классификация кодов по следующим критериям.

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

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

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

Рис. 2. Упрошенная схема классификации кодов

Во второй главе анализируются методы кодирования источника сообщения. Использование неравномерных кодов позволяет уменьшить избыточность. Но поскольку существует связь между элементами сообщения (букв), то необходимо учитывать корреляцию между этими элементами источника для улучшения коэффициента сжатия. Рассматривается количество информации, содержащейся в. текстовых сообщениях, уменьшение избыточности в текстовых сообщениях на французском и русском языках: осуществлен синтез алгоритма и разработаны программы обработки текстов с целью определить статистику, рассчитать вероятности и информативность попарных элементов сообщений во французском и русском текстах. Например, энтропия по буквенной сообщений на французском языке равняется 3,90, а по попарной букв 3,15. Установлено, что частота отсутствия попарной корреляции элементов сообщений мало зависит от объема текста. Это изменение показано на рис.3, где X! =10000 знаков, а х5 = 50000 знаков. При попарной корреляции букв, энтропия уменьшается. Но в реальном языке общения, особенно письменном, невозможно полностью убрать избыточность.

Рис.3. Изменение попарных элементов сообщений в разных объемов текстах.

В третьей главе рассматривается, во-первых, принцип, используемый при разных методах неравномерного кодирования и состоящий в том, что буквы с самыми большими вероятностями кодируются минимальным числом кодовых комбинаций. Отмечается, что это не всегда обеспечивает сжатие. Должно соблюдаться и условие, чтобы средняя длина кодовых комбинации была меньше или равна энтропии («ф £ log,/» где т - число букв в алфавите с учетом интервала). Обсуждается код "Симоновича", где Wq, = 5,15 для латинского алфавита, как пример из таких неравномерных кодов, которые не оптимальны, однако статистически помехоустойчивы.

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

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

При построении обычных статистических методов, кодирование проводится «индивидуально» шаг за шагом, производится разделение (Шеннон - Фано) или суммирование (Хаффмен) вероятностей появления символов, расставленных в порядке убывания вероятностей (табл.1). Эти методы наиболее эффективны с точки зрения конечного результата, т.е. сжатия информации, так. как они обеспечивают минимальную среднюю длину кодовых слов. Но с точки зрения распространения ошибок, такие методы кодирования не дают хорошего результата, так как приводят к искажению информации. Рассматриваются и другие неравномерные методы кодирования источника.

Таблица 1. Алфавитный источник с вероятностями

символ А В С D Е

вероятность 0,4 0,2 0,2 0,1 0,1

Кодовые комбинации 00 01 10 110 111

- Если кодируется сообщение ADEBCCAB, то кодовая комбинация будет 001101110110100001. Если ошибка происходит в выделенном- 0 (т.е. вместо 0 получаем 1), то декодированное сообщение будет АЕЕВССАВ, т.е. меняется только одна буква. В таком случае неравномерные коды ведут себя как равномерные коды.

- Если кодируется то же сообщение (ADEBCCAB), и в кодовой комбинации 001101110110100001 ошибка происходит в выделенной 1 (т.е. вместо 1 получаем 0), то декодированное сообщение будет ABBDDCAB. Изменяются < сразу 4 буквы. Анализы показывают, что чем. ближе мы подходим к первому символу, тем сильнее оказывается ошибка, и декодирование в таком случае бывает затруднено.

Предлагаемый код осуществляется при использовании букв латинского (или русского) алфавита с известными вероятностями появления символов PxhP(x2)....,P(xi).....Р(хт).

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

Для обозначения элементов предлагаемого кода используем арифметику в конечных полях или полях Галуа (Galois Field). Конечное поле может иметь Т элементов, где Т- простое число и h 21. Такое конечное поле часто обозначаетсяСБ( Г*).

Двоичный код определяется как: СР(2|н3) —У СР(2"), где п - длина кодовой комбинации; определяет длину второй части;

общая длина, т.е. первой и второй части. Первая часть кодового слова представляется как префиксная, и вторая часть - информационная.

При п - 0, СР(23) ОР(2°). Это означает, что длина кодовой комбинации в первой части будет равна 3 и во второй части отсутствовать, и тогда получаем комбинации 000 и 001. Мы опираемся на трёх разрядах префикса, поэтому можно выбирать любые два значения (как 100, 101, НО 111 и т. д.), а дальше, надо только обеспечить условие, чтобы они не попадали во второй части, т.е., просто, изменить значения

где Ф определяет объединение (конкатенацию).

Например, при п = 1, СР(24)"+ ОР(2'), т.е. длина второй части равняется 1 (так как % * 0). Такой код представлен в табл. 2.

В данном коде все кодовые слова начинаются двумя нулями и заканчиваются 1 (кроме пробела). Если «0» и «1» имеют определенное место

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

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

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

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

В четвёртой главе приведен синтез устройства, декодирующего предложенную последовательность.

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

Работа устройства начинается после подачи сигнала «пуск», которым устанавливаются все 8 разрядов регистра сдвига в единичное

Рис.4. Структурная схема устройства, декодирующего предложенную последовательность

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

Через восемь тактов 8 разрядов кодовой последовательности войдут в регистр сдвига, и три разряда префикса (000 или 001) займут в нём крайние положения. Счетчик тактов обнуляется, что приводит выход обнаружителя нулевого состояния счетчика в нулевое состояние. Этот нуль включает обнаружители префикса (первой части) кодового слова. Один из обнаружителей префикса кодового слова выдает на выход единицу, которая стимулирует работу декодера информационной (второй) части кодового слова.

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

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

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

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

Рассматривается также синтез каждого блока. Показана, например, работа приоритетного шифратора.

Поскольку для этого приоритетного шифратора номера символов требуется 27 информационных входов и 5 выходов, промышленностью выпускаются интегральные микросхемы только на 8 или 10 входов при 3 или 4 выходах, приходится производить наращивание разрядности, т.е. проводится логический синтез требуемого устройства.

Так структурная схема показана состоит из приоритетных шифраторов 8/3, элементов Пирса, Шеффера, И-ИЛИ-НЕ и инверторов.

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

1. Рассмотрена обобщенная классификация кодов по разным • критериям. Уделено внимание статистическому кодированию.

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

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

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

5. По теме диссертации автором опубликованы 5 работ [48,49,50,51,52]

В приложении сравнивается код Хаффмана и предлагаемый код. Последний

проигрывает по сжатию на 7,6% по сравнению с кодом Хаффмана, за то существенно превосходит в отношении распространения ошибок.

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

1. Обобщение классификации информационных кодов. Нго Биссе Ж. Т., А.К. Нарышкин // 6-ая международная научно-техническая конференция студентов и аспирантов. «Радиоэлектроника, электротехника и энергетика»: Тез. Докл. - М.: Изд. МЭИ, 2000-Т.1-С. 100-101.

2. Исследование статистических кодов. Нго Биссе Ж. Т., А.К. Нарышкин // 8-ая международная научно-техническая конференция студентов и аспирантов «Радиоэлектроника, электротехника и энергетика»: Тез. Докл. - М.: Изд. МЭИ, 2002. - Т. 1 - С107.

3. Неравномерное кодирование и борьба с ошибкой синхронизации, Нго Биссе Ж. Т., А.К. Нарышкин // 9-ая международная научно-техническая конференция студентов и аспирантов «Радиоэлектроника, электротехника и энергетика»: Тез. Докл. - М.: Изд. МЭИ, 2003 -Т .1- С 123.

4. Нго Биссе Ж. Т. Статистика попарной корреляции букв французского и русского текстов и количество информации, содержащееся в них // Радиотехнические тетради -2003 - № 26 - С. 78-80.

5. Нго Биссе Ж. Т. Исследование средней длины неравномерного кодирования и борьба с ошибкой синхронизации // Радиотехнические тетради-2003-№26-С. 76-78.

Печл. № Тираж \00 Заказ ¡05

Типография МЭИ, Краноказарменная, 13.

Введение.

Глава 1. Обобщенная классификация кодов.

1.1. Основные положения теории кодирования.

1.2. Классификация кодов по назначению.

1.2.1. Извлечение информации.

1.2.2. Хранение и передача информации.

1.2.3. Коды для предотвращения несанкционированного доступа.

1.2.4. Классификация кодов по области применения.

1.3. Классификация кодов по критерию обнаружения и исправления ошибок.

1.3.1. Общие сведения о дискретных кодах.

1.3.2. Блочные коды.

1.3.3. Непрерывные коды.

1.4. Классификация кодов по критерию числа элементов и длительности.

Выводы.

Глава 2. Анализ методов кодирования источника информации.

2.1. Избыточность дискретных источников.

2.2. Количество информации, содержащейся в текстовых сообщениях.

2.3. Статистика попарной корреляции букв французского и русского текстов.

2.4. Синтез алгоритма и программы обработки текста.

2.5. Расчет вероятности и информативность попарных элементов сообщений в тексте.

2.5.1. Французский текст.

2.5.2. Русский текст.

2.6. Частота попарной корреляции букв при большом объеме текста.

Выводы.

Глава 3. Разработка нового метода кодирования источника.

3.1.0 распространении ошибок неравномерных кодов.

3.2. Эффективное кодирование источника.

3.3. Код "Симоновича".

3.4. Синхронизация при наличии шума.

3.5. Эффективный метод кодирования источника.

3.6. Синтез алгоритма кода.

3.7. Сравнение предлагаемого кода с "кодом Симоновича", дополненных корректирующими символами по методу Хеммин

Выводы.

Глава 4. Разработка устройства, декодирующего предлагаемый код

4.1. Описание структурной схемы устройства, декодирующего предложенную.

4.2. Синтез регистра сдвига, счетчика, обнаружителей нулевого состояние счетчика и префикса кодового слова.

4.3. Декодеры информационной части кода.

4.4. Синтез приоритетного шифратора номера символов.

4.5. Определитель длины кодового слова.

Выводы.

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

Для устранения избыточности первым эффективным статистическим кодом для источника был код, созданный С. Морзе в 1837 году [41]. Принцип его построения основан на том, что часто встречающимся буквам алфавита источника были поставлены в соответствие короткие кодовые слова, а редким — более длинные. За счет этого средняя длина кодового слова получается короче, чем при равномерном кодировании. С развитием теории информации, появились коды К. Шеннона, Р. Фано [39, 45], Д.А. Хаффмена [42], А. Лемпеля, Д. Зива, Р. Кричевского [14, 15, 71, 72] и др. Некоторые, как и код Морзе, строятся для заранее известной статистики источника, поэтому получили название статистических. В коде Морзе, каждая кодовая комбинация должна отделяться от другой специальным разделительным знаком. Таким знаком служит пауза, соответствующая по длительности тире (т.е. тройной длительности точки). В отличие от кода Морзе, в кодах Шеннона и Хаффме-на нет необходимости отделять друг от друга буквы (кодовые комбинации) специальным знаком, так как и без этого декодирование выполняется однозначно, и средняя длина кодовой комбинации намного уменьшается.

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

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

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

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

В связи с этим понятием, в 40-х годах XX века, К. Шеннон разработал математическую теорию, которая имеет дело к наиболее фундаментальными аспектами теории связи [45]. Заслуга Шеннона состоит в том, что различные виды информации, хотя они имеют различную природу, описываются одним числом - энтропией Н. f * •

ШУМ

Рис. В.1. Структурная схема канала извлечения, передачи и приема информации

Слово энтропия происходит от греческого ev (в) и тротсц (поворот, превращение). Данное понятие энтропии по разному вводится и используется в физике (термодинамике), химии и кибернетике (теории информации) [26]. Понятие энтропии является одним из самых важных в теории информации.

Энтропия - мера неопределенности случайной ситуации. Смысл понятия энтропии заключается в следующем: если передается определенное сообщение, то тем самым получается некоторая информация об источнике, и неопределенность, заключенная в выборе сообщения для передачи, тем самым снимается. Таким образом, реализация любого сообщения заключается в снятии той неопределенности, которая предшествовала выбору этого сообщения. Чем больше была эта неопределенность, тем лучше должна оцениваться та информация, которая получается в результате ликвидации этой неопределенности. Поэтому считается, что количество информации, даваемое реализацией какого-либо сообщения, равно энтропии этого источника [20]. Энтропия равна нулю, если с вероятностью единица источником выдается всегда одно и то же сообщение (в этом случае неопределенность в поведении источника отсутствует). Можно сказать, что наиболее важной характеристикой дискретного источника сообщений является энтропия. Она показывает, насколько используются современные каналы связи и какие резервы заключены в передаваемых сообщениях для эффективности передачи.

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

Вся совокупность элементов х/, Х2, хз,.,хь.,хт называется алфавитом источника. Все, что ещё кроме алфавита известно для данного источника, это распределение вероятностей появления отдельных символов алфавита Р и Р2, Pj,.,Pi,.,Pm. Всякий ансамбль сообщений описывается некоторой неопределенностью. Степень этой неопределенности для различных источников разная, она тем большая, чем более равномерным является распределение вероятностей символов алфавита этого источника. Эта степень реализации любого сообщения из данного источника удобным образом описывается энтропией как: т н = -If£ fiiog^, (B.I) i где п — число символов (длина) сообщения.

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

Если рассматривать случаи оптимального использования каналов с поЛ мехами путем надлежащего кодирования, то можно ожидать, что при передаче сообщений по каналам связи, работающих с ошибками, достижение передачи с достаточно малой ошибкой связано с уменьшением скорости передачи. В действительности, как показал Шеннон, пропускная способность каналов имеет вполне определенное значение даже при сколь угодно малой частоте ошибок. В теории Шеннона приводятся 2 основные теоремы информации [45].

Теорема 1. Если пропускная способность канала С такого, что С > Н /Т, где Н — энтропия источника, Т - интервал времени передачи, то можно закодировать сообщение этого источника так, чтобы вероятность правильного приема была равна 1- е, где с - сколь угодно малое число.

• Теорема 2. Пусть С пропускная способность канала и Н /Т > С, тогда можно так закодировать сообщение источника, чтобы скорость передачи информации была сколько угодно близка к Н IT. Это обеспечивает передачу сообщений по каналу со сколь угодно малой ненадежностью.

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

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

Но, несмотря на достижения в области методов сжатия информации и кодирования источника, существует ряд нерешенных проблем. Например, теоретически доказано, что неравномерные коды лучше, чем равномерные, при кодировании и символов источника. Но все-таки до сих пор все больше используются равномерные коды [49, 59]. Дело в том, что неравномерные коды обладают следующими существенными недостатками [46]:

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

А Л

ЦЕЛЬ НАСТОЯЩЕЙ РАБОТЫ: разработка алгоритма кодирования с минимальным распространением ошибок по символам сообщения в неравномерных кодах.

НАУЧНАЯ НОВИЗНА состоит в новом принципе кодирования сообщения при помощи кодов с двумя специфическими частями кодовых символов префиксом и информационной частью.

НА ЗАЩИТУ ВЫНОСЯТСЯ следующие научные результаты, полученные лично автором:

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

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

3. Разработано устройство декодирующее предлагаемый код.

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

5. Установлена корреляция между буквами вне зависимости от объема текста.

ПРАКТИЧЕСКАЯ ЦЕННОСТЬ. Работа носит теоретический и приклад-« ной характер. Полученные в ней результаты являются развитием теории кодирования источника и разработанные устройства могут быть использованы на практике.

АПРОБАЦИЯ РАБОТЫ. Результаты работы докладывались на международных научно-технических конференциях студентов и аспирантов и также в журнале «Радиотехнические тетради» [48,49,50].

ПУБЛИКАЦИИ. По теме диссертации автором опубликованы 5 работ [48,49,50,51,52].

СТРУКТУРА ДИССЕРТАЦИИ. Диссертация состоит из введения, четырёх глав, заключения, списка литературы и приложение.

Основные результаты полученные в диссертации:

1. Рассмотрена обобщенная классификация кодов по разным критериям. Уделено внимание статистическому кодированию.

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

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

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

5. По теме диссертации автором опубликованы 5 работ [48,49,50,51,52].

Заключение

1. Баева Н. Н. И др. Многоканальные системы передачи. М.: Радио и связь, 1997.

2. Банкет B.JI. Сверточные коды в системах передачи информации. Одесса: Изд. Электротех. Ин-т связи, 1986.

3. Баскаков А. И и др. Зондирующие радиолокационные сигналы. М.: Изд. МЭИ, 1990.

4. Баскаков С. И. Радиотехнические цепи и сигналы. М.: Высшая школа, 2000.

5. Блейхут Р. Теория и практика кодов, контролирующих ошибки. М.: Мир, 1986.

6. Борисов В. А. и др. под ред. Калмыкова В.В. Радиотехнические системы передачи информации. М.: Радио и связь, 1990.

7. Бриллюэн JI. Наука и теория информации. М.: Изд. Физ-мат. 1960.

8. Вентцель Е.С. Теория вероятностей. М.: Изд. Наука, 1969.

9. Гармаш В.А. Исследование статистики сигналов и сообщений и методы статистического кодирования. Диссертация. М.: МЭИС, 1959.

10. Гитлиц М. В., Лев А. Ю. Теоретические основы многоканальной связи. М.: радио и связь 1985.

11. Зюко А.Г., Кловский Д. Д., Назаров М. В., Финк Л.М. Теория передачи сигналов. М. Радио и связь, 1986.

12. Кларк Дж., Кейн Дж. Кодирование с исправлением ошибок в системах цифровой связи. М.: Радио и связь, 1987.

13. Колмогоров А. Н. Алгоритм, информация, сложность. М.: Знание, 1991.

14. Кричевский Р.Е. Сложность сжатия информации. Диссертации. Новосибирск, 1985.

15. Кричевский Р.Е. Сжатие и поиск информации. М.: Изд. Радио и связь, 1989.

16. Лазарева Е.Е. Циклические и сверточные коды. М.: МЭИ, 1986.

17. Левенштейн В.И. Самонастраивающийся автоматы для декодирования сообщений. // Доклады Академии Наук СССР. Т. 141, 1961. №6, стр. 13201323.

18. Левенштейн В. И. Элементы теории кодирования. // Дискретная математика и математические вопросы кибернетики. Изд. Физ. Мат. Т.1. 1974.

19. Лёч М. Исследование некоторых методов специального кодирования источника. Диссертация. Москва, 1977.

20. Липкин И. А. Статистическая радиотехника. Теория информации и кодирования. М.: Вузовская книга, 2002.

21. Мейерс С. Наиболее эффективное использование С++. М.: Дмк Пресс, 2000.

22. Макаров А.А., Гернецкий Г. А. Корректирующие коды в системах передачи информации. Новосибирск: Гос. Ун-т Телекоммуникации и информатики, 2000.

23. Мак-Вильямс и др. Теория кодов и исправляющих ошибки. М.: Изд. Связь, 1979.

24. Марков А. А. Введение в теорию кодирования. М. Изд. Наука, 1982.

25. Нарышкин А. К. Информативность радиолокационных объектов, сигналов и систем. М.: МЭИ, 1994.

26. Нарышкин А.К. Основы теории радиотехнических систем извлечения информации. М.: МЭИ, 1996.

27. Нарышкин А.К. Основы статистического кодирования. М.: Изд. МЭИ, 2002.

28. Нарышкин А. К. Комбинационные Цифровые устройства. М.: Изд. МЭИ, 2002.

29. Никитин Г. И., Подцубный С. С. Помехоустойчивые циклические коды СПБ.: Гос. Ун-т аэрокосм. Приборостроение, 1998.

30. Норенков И. П. и др. Телекоммуникационные технологии и сети. М.: МГТУ, 2000.

31. Петцольд Ч. Код—тайный язык информатики. М.: Русская редакция, 2001.

32. Прокис Д. Цифровая связь. М.: Радио и связь, 2000.

33. Сергириенко А. Б. Цифровая обработка сигналов. СПБ.: Питер, 2003.

34. Симонович С.В. Информатика (учебник для вузов). СПБ.: Питер, 2001.

35. Стиффлер Дж. Дж. Теория синхронной связи. М.: Изд. Связь, 1975.

36. Суприн Б. А. Первичные коды. М.: Связь, 1970.

37. Трофимов В. К. Кодирование источников с неизвестной и неточно известной статистикой сообщений. Диссертация. Новосибирск, 1988.

38. Универсальная десятичная классификация (сокращенные таблицы) М.: машиностроение, 1999.

39. Фано Р. Передача информации. Статистическая теория связи. М.: Изд. Наука, 1965.

40. Фитингоф Б.М. Сжатие дискретной информации. // Проблемы передачи информации. Т. 3, 1967, № 3, стр. 28-36,.

41. Харкевич А.А. Очерки общей теории связи. М.: Гостехизд.1955.

42. Хаффмен Д.А. Метод построения кодов с минимальной избыточностью. // Кибернетический сборник. 1963, вып. 3.

43. Хенкок, Лес и др. Введение в программирование на языке С. М.: Радио и связь, 1986.

44. Цымбал В. П. Теория информации кодирование. К.: Изд. Вища школа, 1982.

45. Шеннон К. Работы по теории информации и кибернетике. М.: ИЛ., 1963.

46. Шувалов В.П. Передача дискретных сообщений. М.: Радио и связь, 1990.

47. Якубовский С. В. и др. Цифровые и аналоговые интегральные микросхемы: справочник. М.: Радио и Связь, 1990.

48. Нго Биссе Ж. Т., А.К. Нарышкин Обобщение классификации информационных кодов. // 6-ая международная научно-техническая конференция студентов и аспирантов. «Радиоэлектроника, электротехника и энергетика»: Тез. Докл.- М.:Изд.МЭИ,2000-Т. 1-С. 100-101.

49. Нго Биссе Ж. Т., А.К. Нарышкин Исследование статистических кодов. // 8-ая международная научно-техническая конференция студентов и аспирантов «Радиоэлектроника, электротехника и энергетика»: Тез. Докл. — М.: Изд. МЭИ, 2002. -Т.1- С 107.

50. Нго Биссе Ж. Т. Статистика попарной корреляции букв французского и русского текстов и количество информации, содержащееся в них // Радиотехнические тетради -2003. № 26. С. 78-80.

51. Нго Биссе Ж. Т. Исследование средней длины неравномерного кодирования и борьба с ошибкой синхронизации // Радиотехнические тетради— 2003. № 26. С. 76-78.

52. Andrian Е., Perkins Е., Perkins S. Binary Huffman equivalent codes with a short synchronizing codeword. // IEEE. Inform. Theory. Vol. 44, № 1, pp-346. January 1998.

53. Battail G. Codage de source adaptif par Palgorithme de Guazzo. // Annales des telecommunications. Vol. 45, № 11-12, p. 679.1990.

54. Beulah Rudner, Construction of minimum-redundancy codes with an optimum synchronizing property. // ,IEEE. Trans.Inform. Theory, vol.17, № 4, pp. 478487, July 1971.

55. Cohen G., Charpin. Eurocode 90. Lecture notes in computer. Udine-Italy, 1990.

56. Davisson L. Universal noiseless coding. // IEEE Trans. Inf. Theory. Vol 19, № 6, pp. 783-795,1973.

57. Ferguson Thomas J., Rabinowitz Joshua H., Self synchroning Huffman codes. // IEEE. Trans. Inform.Theory. Vol. 30, № 4, pp. 687-692 July 1984.

58. Fong A.C.M., Higgie G.R., Fong B. Multimedia applications of self-synchronizing T-codes. // International conference on Inform. Technology coding and computing, pp. 519 523, Las vegas, Nevada 2001.

59. Gilbert E.N., Moore E. F. Variable length binary encodings. // Bell syst. Tech. vol.38, 1959.

60. Hagenauer J., Bauer R. The Turbo Principle in Joint Source Channel Decoding of Variable Length Codes. // Proc. IEEE Information Theory Workshop, Cairns, Australia, pp. 33-35, Sept. 2001.

61. Johnsen O. On the redundancy of binary Huffman codes. // IEEE. Trans. Inform. Theory. Vol. 26, № 2, pp. 220-222, March 1980.

62. Langdon G. G. Comment on "A Universal Data Compression System". // IEEE. Trans. Inform. Theory. Vol. 32, № 6, p. 857, Nov. 1986.

63. Maxted J. C., Robinson J. P. Error recovery for variable length codes. // IEEE. Trans. Inform. Theory. Vol31, № 6, pp. 794-801, Nov. 1985.

64. Minimax E. P. Optimal universal codework set. // IEEE. Trans. Inf. Theory. Vol. 29 № 4, pp. 491-502, 1983.

65. Moffat Alistair. Implementing the PPM data compression scheme. // IEEE. Trans. Inform. Theory. Vol. 38, №11, pp. 1917-1921. Nov. 1990.

66. Montgomery B. L., Abrahams J. Synchronization of binary sources codes. // IEEE. Trans. Inform. Theory. Vol. 32, № 6, pp. 849-857, Nov. 1986.

67. Neumann P. G. Efficient error-limiting variable-length codes. // IRE. trans, of inf. Theory, pp. 292-304, July 1961.

68. Pascal B. Pensees Classique francais. Paris, 1995.

69. Ryabko B. Y. Fast and effective coding of information sources. // IEEE. Trans. Inf. Theory. Vol. 40, № 1, p. 96-99. 1994.

70. Ziv J., Lempel A. An universal algorithm for sequental Data Compression. // IEEE Transactions of Information Theory. Vol, 23, № 3, p. 337. May 1977.

71. Ziv J., Lempel A. Compression of individual sequences via variable- rate encoding. // IEEE. Trans. Inform. Theory. Vol. 24, № 5, p. 530-536. Sept. 1978.