Содержание к диссертации
Введение
Глава 1. Обобщенная классификация кодов 12
1.1. Основные положения теории кодирования 12
1.2. Классификация кодов по назначению 13
1.2.1. Извлечение информации 13
1.2.2. Хранение и передача информации 16
1.2.3. Коды для предотвращения несанкционированного доступа 16
1.2.4. Классификация кодов по области применения 16
1.3. Классификация кодов по критерию обнаружения и исправления ошибок 17
1.3.1. Общие сведения о дискретных кодах 17
1.3.2. Блочные коды 19
1.3.3. Непрерывные коды 23
1.4. Классификация кодов по критерию числа элементов и длительности 27
Выводы 33
Глава 2. Анализ методов кодирования источника информации 34
2.1. Избыточность дискретных источников 34
2.2. Количество информации, содержащейся в текстовых сообщениях 35
2.3. Статистика попарной корреляции букв французского и русского текстов 41
2.4. Синтез алгоритма и программы обработки текста 42
2.5. Расчет вероятности и информативность попарных элементов сообщений в тексте 44
2.5.1. Французский текст 44
2.5.2. Русский текст 48
2.6. Частота попарной корреляции букв при большом объеме текста 52
Выводы 55
Глава 3. Разработка нового метода кодирования источника 56
3.1. О распространении ошибок неравномерных кодов 56
3.2. Эффективное кодирование источника 58
3.3. Код "Симоновича" 60
3.4. Синхронизация при наличии шума 62
3.5. Эффективный метод кодирования источника 64
3.6. Синтез алгоритма кода 68
3.7. Сравнение предлагаемого кода с "кодом Симоновича", дополненных корректирующими символами по методу Хеммин-га 77
Выводы..., 82
Глава 4. Разработка устройства, декодирующего предлагаемый код
4.1. Описание структурной схемы устройства, декодирующего предложенную 84
4.2. Синтез регистра сдвига, счетчика, обнаружителей нулевого состояние счетчика и префикса кодового слова 90
4.3. Декодеры информационной части кода 90
4.4. Синтез приоритетного шифратора номера символов 94
4.5. Определитель длины кодового слова 97
Выводы 97
Заключение 100
Список литературы
- Классификация кодов по назначению
- Классификация кодов по критерию обнаружения и исправления ошибок
- Расчет вероятности и информативность попарных элементов сообщений в тексте
- Эффективный метод кодирования источника
Введение к работе
Теория кодирования стала одним из важнейших ключей для решения ак
туальных проблем в таких областях как вычислительные машины, радиоло
кация, телевидение, связь и многое другое. Особенно в теории связи кодиро
вание играет большую роль для получения наилучшего качества работы сис
тем, так как передача информации требует ее предварительной обработки с
целью уменьшения ее избыточности, защиты от ошибок и т. д. Уменьшение
избыточности передаваемой информации, например, способствует увеличе
нию скорости передачи, уменьшению процессорного времени, необходимого
для обработки информации, и это — основная задача теории кодирования ис
точника. Современное общество для своего эффективного управления ис
пользует все более возрастающий поток информации, который следует пере-
ч давать, хранить и обрабатывать. Поэтому информационная технология быст-
-Z3BHBaercH: уменьшаются цены компьютеоов. запускаются новые мощные устройства, увеличиваются услуги в интернете, который является одним из самых используемых средств передачи данных. Поэтому очень актуально стараться передавать максимально возможное количество информации.
Для устранения избыточности первым эффективным статистическим кодом для источника был код, созданный С. Морзе в 1837 году [41]. Принцип его построения основан на том, что часто встречающимся буквам алфавита источника были поставлены в соответствие короткие кодовые слова, а редким - более длинные. За счет этого средняя длина кодового слова получается короче, чем при равномерном кодировании. С развитием теории информации, появились коды К. Шеннона, Р. Фано [39, 45], Д.А. Хаффмена [42], А. Лемпеля, Д. Зива, Р. Кричевского [14, 15, 71, 72] и др. Некоторые, как и код Морзе, строятся для заранее известной статистики источника, поэтому получили название статистических. В коде Морзе, каждая кодовая комбинация должна отделяться от другой специальным разделительным знаком. Таким
знаком служит пауза, соответствующая по длительности тире (т.е. тройной длительности точки). В отличие от кода Морзе, в кодах Шеннона и Хаффме-на нет необходимости отделять друг от друга буквы (кодовые комбинации) специальным знаком, так как и без этого декодирование выполняется однозначно, и средняя длина кодовой комбинации намного уменьшается.
* Повышение эффективности информационной системы можно получить
и за счет соответствующего выбора способа кодирования, например, стати
стические способы кодирования позволяют в определенной степени устра
нить избыточность, заключенную в передаваемых сообщениях. Поэтому эти
коды нашли большое применение при сжатии файлов, хранимых на внешних
носителях, в высокоскоростных модемах с целью увеличения пропускной
способности цифровых каналов и уменьшения необходимого объема памяти
в других устройствах хранения и передачи цифровой информации. Мы будем
разделять кодирование для источника и кодирование для канала, поскольку
это позволит нам строить кодер и декодер отдельно для источника и для ка
нала (рис.В.1).
Источники информации делятся на непрерывные и дискретные. В диссертации рассматриваются только дискретные источники.
Под дискретным понимается источник, который в каждую единицу времени порождает один символ из дискретного множество алфавита.
Характерными особенностями теории информации является не только широкое привлечение теории вероятностей и вывод об определяющем значении роли кодера и декодера для достижения заданного уровня качества передачи, но и свойства источников информации, которые играют большую роль при выборе способа кодирования сигнала.
В связи с этим понятием, в 40-х годах XX века, К. Шеннон разработал математическую теорию, которая имеет дело к наиболее фундаментальными аспектами теории связи [45]. Заслуга Шеннона состоит в том, что различные виды информации, хотя они имеют различную природу, описываются одним числом — энтропией //.
Источник
Кодер для источника
Кодер для канала
канал
Рис. В.1. Структурная схема канала извлечения, передачи и приема информации
Слово энтропия происходит от греческого ev (в) и тротгп (поворот, превращение). Данное понятие энтропии по разному вводится и используется в физике (термодинамике), химии и кибернетике (теории информации) [26]. Понятие энтропии является одним из самых важных в теории информации.
* Энтропия — мера неопределенности случайной ситуации. Смысл понятия эн-
тропии заключается в следующем: если передается определенное сообщение, то тем самым получается некоторая информация об источнике, и неопределенность, заключенная в выборе сообщения для передачи, тем самым снимается. Таким образом, реализация любого сообщения заключается в снятии той неопределенности, которая предшествовала выбору этого сообщения. Чем больше была эта неопределенность, тем лучше должна оцениваться та информация, которая получается в результате ликвидации этой неопределенности. Поэтому считается, что количество информации, даваемое реализаци-
» ей какого-либо сообщения, равно энтропии этого источника [20]. Энтропия
равна нулю, если с вероятностью единица источником выдается всегда одно и то же сообщение (в этом случае неопределенность в поведении источника отсутствует). Можно сказать, что наиболее важной характеристикой дискретного источника сообщений является энтропия. Она показывает, насколько используются современные каналы связи и какие резервы заключены в передаваемых сообщениях для эффективности передачи.
Предположим, что число различных элементов, из которых может быть получено любое сообщение, конечно и равно т.
Вся совокупность элементов Xft Х2, х^...,х/,...,хт называется алфавитом источника. Все, что еще* кроме алфавита известно для данного источника, это распределение вероятностей появления отдельных символов алфавита Р{, Р2, Рз,...,Р(,...,Рт. Всякий ансамбль сообщений описывается некоторой неопределенностью. Степень этой неопределенности для различных источников разная, она тем большая, чем более равномерным является распределение вероятностей символов алфавита этого источника. Эта степень реализации лю-
s бо го сообщения из данного источника удобным образом описывается энтропией как:
Н =-nfJPi\og2Pi, (В.1)
где и — число символов (длина) сообщения.
Задачей кодирования для источника является представление выхода источника с помощью последовательности двоичных символов, причем на этом шаге необходимо уменьшить избыточность источника до минимума» т. е. закодировать последовательность букв источника минимально возможным количеством двоичных символов. Задача кодирования для канала состоит в том, чтобы надежно воспроизвести двоичную последовательность данных на выходе декодера для канала на этом шаге для защиты от помех в канале (вносится избыточность в сообщение).
Если рассматривать случаи оптимального использования каналов с помехами путем надлежащего кодирования, то можно ожидать, что при передаче сообщений по каналам связи, работающих с ошибками, достижение передачи с достаточно малой ошибкой связано с уменьшением скорости передачи. В действительности, как показал Шеннон, пропускная способность каналов имеет вполне определенное значение даже при сколь угодно малой частоте ошибок. В теории Шеннона приводятся 2 основные теоремы информации [45].
Теорема 1. Если пропускная способность канала С такого, что С > И /Г, где Н —энтропия источника, Т— интервал времени передачи, то можно закодировать сообщение этого источника так, чтобы вероятность правильного приема была равна 1- е, где є — сколь угодно малое число.
Теорема 2. Пусть С пропускная способность канала и Н 1Т> С, тогда можно так закодировать сообщение источника, чтобы скорость передачи информации была сколько угодно близка к Н ІТ. Это обеспечивает передачу сообщений по каналу со сколь угодно малой ненадежностью.
За последние годы интерес к теории информации и, в частности, к построению статистических методов кодирования для источника резко увеличился.
Это связано с постоянно возрастающим объемом передаваемой по циф
ровым каналам связи и хранимые информации во внешней памяти компью-
щ теров, что побуждает исследователей во всем мире разрабатывать новые ме-
тоды сжатия информации и повышать эффективность существующих.
Но, несмотря на достижения в области методов сжатия информации и кодирования источника, существует ряд нерешенных проблем. Например, теоретически доказано, что неравномерные коды лучше, чем равномерные, при кодировании и символов источника. Но все-таки до сих пор все больше используются равномерные коды [49, 59]. Дело в том, что неравномерные коды обладают следующими существенными недостатками [46]:
Если произойдет случайная ошибка, то она распространится на все сле-
* дующие сообщения, т.е. возникает так называемая ошибка синхронизации;
при декодировании, особенно, при возникновении ошибки синхронизации, нужно использовать все передаваемое сообщение. Это потребует при передаче больших массивов информации огромный памяти. Ошибка синхронизации может быть непростительной, особенно для документа текстового процессора или файла электронной таблицы, в которых важна каждая цифра и буква. В силу сказанного, в настоящее время одной из актуальных задач теории кодирования источника является разработка эффективных и достаточно простых неравномерных кодов с хорошим коэффициентом сжатия и наименьшей -.--лтностью ошиоок синхронизации.
ЦЕЛЬ НАСТОЯЩЕЙ РАБОТЫ: разработка алгоритма кодирования с минимальным распространением ошибок по символам сообщения в неравномерных кодах.
НАУЧНАЯ НОВИЗНА состоит в новом принципе кодирования сообщения при помощи кодов с двумя специфическими частями кодовых символов префиксом и информационной частью.
НА ЗАЩИТУ ВЫНОСЯТСЯ следующие научные результаты, полученные лично автором:
Новый метод (алгоритм) неравномерного кодирования источника, позволяющий уменьшить ошибки синхронизации, которые возникают в обычных неравномерных способах кодирования.
Предложен новый класс кодов с двумя группами для кодирования источников.
Разработано устройство декодирующее предлагаемый код.
Рассмотрено уменьшение избыточности источника путем расчета попарной корреляции между буквами во французском и русском текстах.
Установлена корреляция между буквами вне зависимости от объема текста.
ПРАКТИЧЕСКАЯ ЦЕННОСТЬ. Работа носит теоретический и прикладной характер. Полученные в ней результаты являются развитием теории кодирования источника и разработанные устройства могут быть использованы на практике.
АПРОБАЦИЯ РАБОТЫ. Результаты работы докладывались на международных научно-технических конференциях студентов и аспирантов и также в журнале «Радиотехнические тетради» [48,49,50].
ПУБЛИКАЦИИ. По теме диссертации автором опубликованы 5 работ [48,49,50,51,52].
СТРУКТУРА ДИССЕРТАЦИИ. Диссертация состоит из введения, четырёх глав, заключения, списка литературы и приложение.
В первой главе диссертации рассматривается обобщенная классификация кодов по разным критериям. Уделено внимание статистическому кодированию.
Во второй главе предложены методы кодирования источника сообщения. Рассматривается уменьшение избыточности в текстовых сообщениях.
«
В третьей главе предлагается эффективный метод кодирования источника с целью уменьшения вероятности распространения ошибки неравномерных кодов.
В четвёртой главе рассматривается синтез устройства, декодирующего предлагаемый код.
В заключении сформулированы полученные в диссертации основные результаты.
Классификация кодов по назначению
Извлечение информации содержит в себе ряд последовательно осуществляемых процессов: излучение (генерирование), передачу, распространение, прием и обработку сигналов, предъявление и регистрацию информации. Здесь поступающая информация закодирована во временной и пространственной структуре приходящих от целей электромагнитных волн. Поэтому одна из задач радиолокационных систем является пространственно-временное декодирование сигналов и выделение из помех. Как известно в радиолокации часто используются сигналы с фазовой манипуляцией (ФМ). Они используются как в непрерывном, так и в импульсном режиме излучения, основные свойства ФМ сигнала определяются кодом, который применен для модуляции. Фазовая манипуляция может осуществляться кодами Барке-ра, Фрэнка и М — кодом [25].
Код Баркера, Фрэнка и М-код, представленные на рис. 1.1, являются бинарными кодовыми последовательностями. Они выбираются по регулярным правилам из условия обеспечения минимальных значений боковых лепестков двумерной автокорреляционной функции (ДАФ) при ширине главного пика to.
Он используется в радиолокации. В нем обеспечивается подавление боковых лепестков корреляционной функции вдоль временной оси до уровня где N— число элементарных импульсов (дискретов). Главным свойством кодов Баркера является вид их автокорреляционной функции, представляющей собой узкий высокий пик, окруженный треугольными лепестками малого уровня. Коды Баркера имеют максимально возможное для бинарных (т.е. принимающих два значения) сигналов отношение высоты центрального пика корреляционной функции к уровню ее боковых лепестков. Это число равно числу отчетов сигнала. Ограничение накладывается условием // 13 [4,32]. М-код Это — сигнал, манипулированной по фазе двоичной псевдослучайной последовательностью. Двоичные последовательности представляют собой набор N (дискреты) периодически повторяющихся символов, каждый из которых может принимать значение 0 или 1.
Задача формирования М-последовательности сводится к тому, чтобы найти функцию логики или, что то же самое, структуру обратной связи п-разрядного сдвигающего регистра, при которой период последовательности равен N= 2" — 1 (минус 1, так как существует запрещенная комбинация из и нулей). А если структуру обратной связи определять в соответствии с первообразным неприводимым характеристическим многочленом вида: /г(х) = йг„х"Єйл.1 " ... а\х & д0 (1-2) то получим М-код, где а/ коэффициенты, могущие принимать значение 0 или 1. Каждый /-й член последовательности является логической суммой по модулю 2 некоторых предыдущих членов. Основные сведения о М-кодах и свойствах сигналов, модулированных этими кодами, приведены в [3]. Код Фрэнка
Он позволяет получать низкий уровень боковых лепестков. Основные сведения о кодах Фрэнка и свойствах сигналов, модулированных этими кодами, приведены в [3] и [25]. Дискретные значения фаз комплексных огибающих таких сигналов определяются формулой: A(I) = (2!rPI/jB)ent(l/jB), (1.3) где Р — целое число, взаимно простое с числом -JB , которое тоже предполагается целым; сп\(у) — целая часть у.
Многие системы нуждаются в хранении информации. Обычно, для этой цели используются и коды для сжатия, о которых сказано ниже. Мы также рассмотрим подробно коды для передачи информации в пункте 1.4.
Существуют коды защиты от несанкционированного доступа, которые строятся, как правило, на основе сложения полученной в кодере канала последовательности дискретных символов с последовательностью максимальный длины, логика построения которой известна на стороне источника и получателя сообщений. В этой области может служить тоже М-код [3]. Аналогичную защиту от расшифровки передаваемых сообщений дает программная перестройка рабочих частот (режим ППРЧ) передатчика на стороне источника сообщений (ИС) и гетеродина приемника на стороне получателя сообщений (ПС), а также адекватная этому методу модуляция сигналов с применением частотно-временных матриц ЧВМ [29].
Коды применяются почти во всех областях: в промышленном производстве для идентификации заготовок деталей, изделий, упаковок; в банковских сие темах, в клиниках, в почтовых ведомствах, на транспорте, в информационных системах и пр. Но мы рассмотрим их применения только в информационных системах. В этой области, коды могут быть использованы для извлечения, хранения (сжатие), обработки и коррекции информации. Известно, что каналы, по которым передается информация, практически никогда не бывают идеальными (каналами без помех). В них почти всегда присутствуют помехи. Различие лишь в уровне помех и их спектральном со ставе. Помехи в каналах образуются по различным причинам, но результат воздействия их на передаваемую информацию всегда один — информация те » ряется (искажается).
Для предотвращения потерь информации в канапе кроме информационных символов, вводятся дополнительные (проверочные) символы, из-за этого получается избыточность. Преимущество избыточного кода в том, что при приеме его с искажением (количество искаженных символов зависит от степени избыточности и структуры кода) информация может быть восстановлена на приемнике.
Для различных помех в канале существуют различные по своей структуре и обнаруживающие, и исправляющие коды. Обычно избыточность кодов находится в пределах 10...60% или чуть больше. Избыточность 1/4 (25%) применяется при записи информации на лазерные диски и в системах цифрового спутникового ТВ.
Классификация кодов по критерию обнаружения и исправления ошибок
Совершенствование и усложнение буквенно-цифровых кодов шли, в основном, по пути добавления ряда служебных символов, которые требовались как для расширения числа комбинаций, так и для контроля правильности передаваемых сообщений. Наибольшее применение получили шестизначные коды. В США, в различных типах ЭВМ применяют около 25 разновидностей шестизначных кодов [14, 57]. Недостаток кода Бодо заключается в том, что он не имеет избыточности, поэтому труднее защитить от помех (чтобы уменьшить число ошибок, следует выделить группу символов, нуждающихся в усиленной защите, и подбирать комбинации кодов таким образом, чтобы уменьшить вероятность перехода передаваемых символов в запрещенные символы) [36].
К равномерным кодам, не обладающим корректирующей избыточно стью, относится и код Грея [5, 44]. Он представляет собой рефлексный код с двумя качественными признаками. В этом коде каждая последующая комби нация отличается от предыдущей одним символом. Он может обнаружить одиночные ошибки при соответствующих ограничениях. Несмотря на то, что код Грея не может исправлять ошибки, он удобен для передачи телемеханической информации о медленно изменяющихся процессах.
Международный телеграфный код № 3 относится к кодам с постоянным весом [12]. Коды с постоянным весом характеризуются тем, что их кодовые комбинации содержат одинаковое число единиц. Примером такого кода является код "3 из 7", в котором каждая кодовая комбинация содержит три единицы и четыре нуля.
В полностью асимметричных каналах, в которых имеет место только один вид ошибок (преобразование нулей в единицы или единиц в нули), такой код служит для обнаружения ошибки.
В симметричных каналах вероятность необнаруженной ошибки можно определить как вероятность одновременного искажения одной единицы и одного нуля. где PQM- вероятность искажения символа (ошибки), /"„.о. - вероятность необнаруженной ошибки.
Он широко используется в телеграфии и сам по себе обладает корректирующими способностями [12].
Код Плоткина также позволяет эффективно корректировать симметричные и независимые ошибки [44].
Мы не имеем возможности останавливаться на всех кодах, поэтому здесь дается только краткое представление о наиболее применяемых кодах.
Среди неравномерных кодов, отметим оптимальные неравномерные коды (ОНК), которые позволяют вести передачу с максимальной скоростью за счет сжатия данных. На практике, при передаче текстовых сообщений, ОНК используют в алфавитных системах, в которых алфавитный порядок букв соответствует числовому двоичному кодовых слов.
Разделимые коды
В разделимых кодах, информационные элементы и проверочные элементы во всех кодовых комбинациях занимают определенные для своей группы позиции. Поэтому разделяемые коды обычно обозначают в работе [16] как коды (и, к), где п - длина кода (общее число символов); к - число информационных символов.
Разделимые блочные коды делятся на систематические и несистематические (см. рис 1.2), в этом разделе предусматривается возможность четкого разграничения информационных и проверочных символов.
Несистематические коды применяются значительно реже, чем систематические коды. К этому классу кодов относится, например код Бергера [44], Он чаще всего применяется в технике передачи данных по телеграфным ка налам, и позволяет обнаружить пакетные ошибки с длиной пакета, не превышающей длины отдельного пол блока. Несистематические коды особенно эффективны для двоичных каналов с асимметричными ошибками.
Систематическими называют такие коды, в которых информационные и корректирующие символы расположены по строго определенной системе и всегда занимают определенные места в кодовых комбинациях. Среди разделимых систематических кодов различают линейные и нелинейные.
Среди линейных систематических кодов наиболее простой код (и, п-к), содержащий один проверочный символ, который равен сумме по модулю 2 всех информационных символов. Этот код, называемый кодом с проверкой на четность, позволяет обнаружить все сочетания ошибок нечетной кратности. Вероятность необнаруженной ошибки в первом приближении можно определить как вероятность искажения двух символов.
Циклические коды составляют большую группу, наиболее используемых на практике линейных систематических кодов, их основное свойство состоит в том, что каждый вектор получаемый из исходного кодового вектора путем циклической перестановки его символов, так же является разрешенным кодовым вектором. Принято описывать циклические коды при помощи порождающих полиномов. Операции кодирования и декодирования циклических кодов сводятся к известным процедурам умножения и деления полиномов. Для двоичных кодов, эти операции легко реализуются технически с помощью линейных переключательных схем (ЛПС), при этом получаются относительно простые схемы кодирующих устройств, в чем состоит одно из практических достоинств циклических кодов.
Расчет вероятности и информативность попарных элементов сообщений в тексте
Используется художественный текст французского писателя Блеза Пас каля, "Мысли" [69]. Здесь не принимаются во внимание все ударения: ё, ё, е, а и т.д. Текст может быть немножко неправилен с точки зрения грамматики, но он ясен и понятен для любого человека, знающего французский язык. С помощью программы рассчитывается частота появления пар букв. Результат представлен в табл.2.4. Из этой таблицы видно, что из 729 комбинаций, 453 "невозможные или маловероятные" (здесь эти вероятности получаются во обще равными нулю). Но все-таки это касается небольшого объема текста, как выше сказано. Наверно, есть такие комбинации, которые не встречаются в нашем тексте. Но большое количество "невозможных комбинаций" пока зывает, что есть буквы, которые не соединяются с другими, и их можно уб рать при кодировании. Можно ещё заметить, что "артикль" который указы вает род не так часто встречается (например, la). ш/», который часто упот ребляется в конце слова имеет большую вероятность. Информативность равняется 6,309 бит/пар букв, т.е. 3,15 бит/букв (при статистическом кодировании по буквам получается 3,90 бит/букв).
Используется научный текст из учебника Харкевича, «теория информация» ]. Название текста— "Белый шум". В тексте первые буквы расп о-лагаются в столбце, а вторые буквы в строке (табл. 2.5). Текст должен быть набран аккуратно, т.е. обратить внимание на большие и маленькие буквы, точки и другие знаки препинания. Из 1024 (без пробела) пар букв, 660 комбинаций оказываются невозможными. Выше сказанное для французского языка имеет то же значение для русского. Информативность здесь получается 7,8 бит/пар букв, т.е. практически 3,9 бит/букв. Статистическое Кодирование по буквам дает 4,42 бит/букв [8].
При расчета попарной корреляции букв в тексте с маленьким объемом, всегда кажется, что не все комбинации появились. Много невозможных комбинаций (нулей) появляются больше, чем возможных. Например, в тексте французского языка, как показано выше, количество нулей составляет 62,14%. Рассмотрим, так ли объем влияет на появления некоторых комбинации.
Возьмем тот же художественный текст французского писателя, как выше, увеличивая объем текста в 5 раз (вместе 9800, число знаков данного текста составляет 50400). Результаты представлены в табл. 2.6.
Как видно из таблицы, количество невозможных комбинаций составля « ет 403 (сочетание 27 символов т. е. 26 букв плюс пробел). Это значение со ставляет 55,28 % нулей (56,38 %, если ещё принимать значение диакритический знак или апостроф) от объема текста, т. е. в данном случае при увеличении объема текста в 5 раз, число невозможных комбинаций уменьшается лишь на 6,86 %. График этого изменения представлен на рис.2.3. Это ещё раз говорит о том, что существует определенное правило распределения (сочетания) букв, и это сочетание не так влияет на объем текста, а зависит от самого языка. Для текстового сообщения, даже если это касается целого учебника, невозможно найти все буквенные сочетания, так как некоторые комбинации просто не существуют в языке.
Основная задача при кодировании для источника — уменьшить избыточность. Это позволяет эффективно использовать канал связи или оперативную память.
Использование неравномерных кодов позволяет уменьшить избыточность. Но поскольку существует связь между элементами сообщения (букв), то необходимо учитывать корреляцию между этими элементами источника для улучшения коэффициента сжатия.
При попарной корреляции букв, энтропия уменьшается. Но в реальном языке общения, особенно письменном, невозможно полностью убрать избыточность. Результаты исследования доложены на конференциях [49] и опубликованы в статье [51]. Процедура кодирование заключается в том, что каждому символу Х\ из исходного ансамбля {Х(} ставится в соответствие определенный набор кодовых символов АЦ, АІ2„ АІЗ,. ,АІ„. При этом должно соблюдаться соответствие между элементами множества сообщений и множества кодовых комбинаций. Почти все статистические способы кодирования, описанные в главе 2, позволяют в определенной степени устранить избыточность, заключенную в передаваемых сообщениях, и соблюдают это соответствие. Игнорирование этого условия приводит к невозможности или неоднозначности восстановления по заданной последовательности кодовых посылок передаваемых сообщений.
Напоминаем, что существуют и нестатистические методы кодирования. По существу, кодирование в этом случае заключается в последовательной нумерации всех символов ансамбля. Если при кодировании избран двоичный алфавит (например 0 и 1), нумерация возможных сообщений при передаче осуществляется в системе счисления с тем же основанием (двоичный). Для нумерации всех т сообщений исходного ансамбля сообщений необходимо затратить не менее чем:
Данный раздел касается применения неравномерных методов кодирования источника при известной статистике. Неравномерные коды хотя имеют практически преимущество в том, что они минимизируют среднюю длину кодовых комбинаций, т.е. обеспечивают достаточную сжатость, их применение осложняется тем, что если произойдет случайная ошибка при кодировании или передаче одного кодового слова, это может повлиять на другие кодовые слова.
Эффективный метод кодирования источника
Из этого параграфа следует, что в коде "Симоновича" используется большее количество символов, чем в предлагаемом коде, соответственно и больше контрольных символов. Количество контрольных символов пк изменяется при передаче меньше или больше количество информационных символов. Приведенный выше пример показывает, что при разбиении общее число символов по 4 информационными у "Симоновича", требует я, = 32 (т. е. 76,2 % от общего число символов). Предлагаемый код имеет почти такой же соотношение (n = 33, пк — 25). Если взять по пятнадцати информационных символов, число пк существенно меняется и составляет только 30 % от общего число символов. Это говорит о том, что предлагаемый код и код "Симоновича" могут быть использованы при плохом отношении сигнал/шум.
Выводы
В настоящей главе представлен новый метод кодирования сообщений, отличающийся от традиционных тем, что он состоит из двух частей: первая часть имеет фиксированную длину и одинаковых два первых символа; вторая часть имеет переменную длину, но в ней никогда не встречаются подряд два одинаковых символа стоящих в начале первой части кода (или вообще первая часть кода не повторяется во второй части). Данная особенность нового кода позволяет исключить распространения одиночные ошибки при фактически переменной длине кода в целом [52].
При кодировании, добавление элементов сообщений как а ё, ё, ё, 9, ї, Ї» и т.п. не изменяет принцип кодирования. Это может повлиять только на устройство декодирующего символы (см. гл. 4).
Эффективное кодирование источника достигается при использовании определенный статистический метод кодирования, так как не всегда уменьшается длину кодируемого сообщения. Поэтому, надо учитывать, что средняя длина должно быть меньше или равна log т (/ й log2m) [50].
Рассмотрен пример распространения ошибок по методу Хаффмана и по предлагаемому методу, а также рассчитано их коэффициента сжатия (см. приложение). Структурная схема (рис.4.1) состоит из 8-разрядного регистра сдвига, обнаружителей обеих частей кодового слова, двух пятиразрядных декодеров информационной части кодового слова, 5-разрядного приоритетного шифра тора номера символов, 5-разрядного регистратора принятых символов, 4 разрядного определителя длины принятого кодового слова, 4-разрядного вы » читающего счетчика тактов, 4-разрядного обнаружителя нулевого состояния счетчика тактов. Работа устройства начинается после подачи сигнала «пуск» (рис.4.2.), которым устанавливаются все 8 разрядов регистра сдвига (Q7 Qo) в единич ное состояние, а 4-разрядный вычитающий счетчик тактов (уз„.уо), находив шийся в нулевом состоянии, — в состояние, соответствующее восьми, т.е. 1000. На выходе обнаружителя нулевого состояния счетчика появляется нуль, который, не только блокирует оба обнаружителя кодового слова, но и разрешает работу определителя длины кодового слова.
Через восемь тактов 8 разрядов кодовой последовательности войдут в регистр сдвига, и три разряда префикса (000 или 001) займут в нем крайние положения. Счетчик тактов обнуляется, что приводит выход обнаружитель нулевого состояния счетчика в нулевое состояние.
Этот нуль включает обнаружители префикса (первой части) кодового слова. Один из обнаружителей префикса кодового слова выдает на выход единицу, которая стимулирует работу декодера информационной (второй) части кодового слова. Выходы декодера используются: а) для определения номера обнаруженного символа приоритетным шиф ратором номера символа, который затем запоминается регистратором; б) для определения длины обнаруженного кодового слова, для чего так же используется приоритетный шифратор. Эта длина вводится в счетчик так тов с тем, чтобы дальнейший сдвиг кодовой последовательности внутри ре гистра сдвига был произведен именно на число разрядов обнаруженного символа.
На выходе обнаружителя нулевого состояния счетчика снова образуется нуль, который блокирует работу обнаружителей префикса кодового слова. Последнее предусмотрено для того, чтобы в информационной (второй) части кодового слова не было ложного обнаружения префикса кодового слова. Цикл повторяется.
Если длина кодового слова окажется равной нулю, когда код не обнаружен в результате ошибки в каком-нибудь разряде кодового слова, с выхода определителя длины кодового слова подается сигнал установки младшего разряда счетчика в единицу. При этом в каждом последующем такте также будет производиться попытка обнаружить префикс кодового слова, а затем и самого символа. Регистратор инициируется сигналом с выхода обнаружителей префикса кодового слова.
