Принципы эффективного кодирования.

Введение

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

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

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

Кодирование информации.

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

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

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

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

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

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

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

Основными задачами кодирования являются:

1) Обеспечение экономичности передачи информации посредством устранения избыточности.

2) Обеспечение надежности (помехоустойчивости) передачи информации.

3) Согласование скорости передачи информации с пропускной способностью канала.

Кодирование бывает побуквенное и блочное.

Побуквенное кодирование: каждому знаку внешнего алфавита ставиться в соответствие кодовое слово из знаков внутреннего алфавита.

Блочное кодирование: слову из знаков внешнего алфавита ставиться в соответствие кодовое слово из знаков внутреннего алфавита.

Процесс кодирование и декодирования бывает обратимым и необратимым.

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

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

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

Чтобы код был обратимым, необходимо выполнение следующих условий:

1. чтобы разным символам входного алфавита А были сопоставлены разные кодовые комбинации;

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

3.

Систематические коды.

Систематический код – это код, который содержит информационные и контрольные разряды. Контрольные разряды содержат информацию об исходном числе. Поэтому систематический кодобладает избыточностью. Абсолютная избыточность будет выражаться количеством контрольных разрядов k. Относительная избыточность – отношением k/n, где n=m+k – общее количество разрядов в кодовом слове (m – количество информационных разрядов).

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

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

.

Число кодовых комбинаций, каждая из которых содержит k искаженных элементов, равна числу сочетаний из n по k:

.

Тогда вероятность искажения

.

Так как на практике P от 10^-3 до 10^-4, наибольший вес в сумме вероятностей имеет вероятность искажения одного символа. Следовательно, основное внимание нужно обратить на обнаружение и исправление одиночной ошибки.

С корректирующей способностью кода связывается понятие кодового расстояния. Кодовое расстояние d(A,B), где А и В – кодовые комбинации, определяется как вес такой третьей кодовой комбинации, которая получается сложением исходных комбинаций по модулю 2.

Вес кодовой комбинации V(A)– это количество единиц, которые содержатся в кодовой комбинации.

Систематический код обладает способностью обнаруживать ошибки. Это происходит только тогда, когда минимальное кодовое расстояние для него больше или равно 2t, т.е., где t – кратность обнаруживаемых ошибок t=1 (в случае обнаружения одиночных ошибок t=1). Другими словами, это означает, что между соседними кодовыми комбинациями должна существовать хотя бы одна кодовая комбинация.

Несистематические коды.

Несистематические коды рассмотрим на примере кода Бергера.

Существует несколько вариантов построения кодов Бергера. В наиболее простом варианте кодирование происходит следующим образом: в информационной части кода подсчитывается число единиц, после чего формируются проверочные разряды, представляющие инвертированную запись этого числа в двоичной форме. Таким образом, число проверочных разрядов R равно наименьшему целому числу, превышающему Log₂(k), т.е. R >= Log₂(k).

Например, сообщение 011010, закодированное кодом Бергера, выглядит как 011010100.

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

Пример:

Подлежащие передачи информационные символы: 011010.

Двоичная запись количества единиц: 011.

Инвертированная двоичная запись: 100.

Переданное слово (закодированное): 011010100.

Слово, принятое с двумя ошибками: 001010000.

Двоичное число, полученное путем подсчета информационных единиц: 010.

Инвертированное двоичное число принятых проверочных символов: 111.

Таким образом, проверочное число, вычисленное по принимаемым информационным символам 010, не равно числу принятых проверочных символов 111.

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

В симметричных каналах такие коды обнаруживают все одиночные ошибки и некоторую часть многократных. Можно построить коды с лучшими обнаруживающими свойствами для симметричных каналов. В таких кодах каждой информационной позиции приписывают различный вес, причем ни один вес не является степенью двух (3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17 и т.д. ). Проверочные знаки этого образуются путем суммирования весов, соответствующих тем информационным разрядам, в которых расположены единицы, затем происходит инверсия полученного числа. Такой код обнаруживает в симметричном канале все двойные ошибки и обнаруживает и исправляет одиночные ошибки.

Количество проверочных символов определяется из соотношения:

(1)

где k - количество информационных символов, а m определяется из двойного неравенства:

(2)

Пример:

Закодировать кодом Бергера, обнаруживающим двойные ошибки, сообщение: 0110100001.

Запишем распределение весов в данном сообщении: 1-ый разряд - 3, 2 - 5, 3 - 6, 4 - 7, 5 - 9, 6 - 10, 7 - 11, 8 - 12, 9 - 13, 10 - 14. Следовательно, сумма весов (5 + 6 + 9 + 14) равна 34. Из (2) находим m = 4, из (1) r = 7.

Двоичная запись суммы весов для семиразрядной проверочной части, имеет вид: 0100010.

Инвертированный вид: 1011101.

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

Принципы эффективного кодирования.

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

Различают избыточность естественную и искусственную. Естественная избыточность характерна для первичных алфавитов, а искусственная - для вторичных.

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

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

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

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

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

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

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

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

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

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

Для двоичных кодов

Разность (L_cp - H) будет тем меньше, чем больше Н, а H достигает максимума при равновероятных и взаимно независимых символах. Отсюда вытекают основные свойства эффективных кодов:

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

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

Из свойств оптимальных кодов вытекают принципы их построения.

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

Принципы эффективного кодирования определяют методику построения эффективных кодов.

Коды Хемминга

Коды Хемминга – это самоконтролирующиеся и самокорректирующиеся коды, наиболее известные и первые в своем роде. Построены они применительно к двоичной системе счисления.

Самоконтролирующийся код.

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

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

Самокорректирующийся код

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

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

Количество контрольных разрядов k должно быть выбрано так, чтобы удовлетворялось неравенству или , где m - количество основных двоичных разрядов кодового слова.

Пример кода Хэмминга

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

Полное количество разрядов такого кода будет m+k+1, а цифра в разряде двойного контроля устанавливается такой, чтобы общее количество единиц во всех m + k + 1 разрядах кода было четным. Этот разряд не включается в общую нумерацию и не входит ни в одну контрольную группу.

Например, код Хэмминга с m=7 и k=4. Пусть информационное кодовое слово – 0110101.

Таблица 7

При этом могут возникать следующие случаи.

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

Таблица 8

Таблица 9

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

Таблица 10

Таблица 11

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

Таблица 12

Таблица 13

Из таблицы следует, что ошибка произошла в 11-м разряде и что её можно исправить.

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

Таблица 14

Таблица 15

Исправление двойных ошибок здесь невозможно.

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

Заключение

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

Список литературы

1. Котенко В.В. Теория информации. Часть 1. Кодирование источников информации: Учебное пособие. Таганрог: Изд-во ТРТУ, 2003. 138с.

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

3. Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение: Пер. с англ. - М.: ТЕХНОСФЕРА, 2006. - 320с.

4. Панин В.В. Основы теории информации: учебное пособие для вузов. – М.: БИНОМ. Лаборатория знаний, 2007. – 436с.

5. Самсонов Б.Б., Плохов Е.М., Филоненков А.И., Кречет Т.В. Теория информации и кодирование. – Ростов-на-Дону: "Феникс", 2002, 288с.

6. Семенюк В.В. Экономное кодирование дискретной информации. - СПб.: СПбГИТМО (ТУ), 2001 - 115с.

7. Сэломон Д. Сжатие данных, изображений и звука: Пер. с англ. - М.: Техносфера, 2004. - 368с.

8. Шульгин В.И. Основы теории передачи информации. Часть 1 Экономное кодирование. - Харьков, ХАИ, 2003. - 103с.