Методы эффективного кодирования информации

 

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

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

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

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

При отсутствии статистической взаимосвязи между буквами конструктивные методы построения эффективных кодов были даны впервые К.Шенноном и Н.Фано. Их методики существенно не различаются, поэтому соответствующий код получил название кода Шеннона–Фано.

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

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

 

Таблица 4.1 Таблица 4.2

Вычислим энтропию набора букв

 

и среднее число символов на букву

 

где n (zi) – число символов в кодовой комбинации, соответствующей букве zi.

Значения z и l срне очень различаются по величине.

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

Множество вероятностей в предыдущей таблице можно было разбить иначе (табл. 4.2). При этом среднее число символов на букву оказывается равным 2,80. Таким образом, построенный код может оказаться не самым лучшим. При построении эффективных кодов с основанием q > 2 неопределенность становится еще больше.

От указанного недостатка свободна методика Д.Хаффмена. Она гарантирует однозначное построение кода с наименьшим для данного распределения вероятностей средним числом символов на букву (табл. 4.3).

Таблица 4.3

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

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

Рис. 11. Кодовое дерево

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

z 1 z 2 z 3 z 4 z 5 z 6 z 7 z 8

01 00 111 110 100 1011 10101 10100

 

4.2. Кодирование по методу четности–нечетности

 

Если в математическом коде выделен один контрольный разряд (k = 1), то к каждому двоичному числу добавляется один избыточный разряд и в него записывается 1 или 0 с таким условием, чтобы сумма цифр в каждом числе была по модулю 2 равна 0 для случая четности или 1 для случая нечетности. Появление ошибки в кодировании обнаружится по нарушению четности (нечетности). При таком кодировании допускается, что может возникнуть только одна ошибка. В самом деле, для случая четности правильной будет только половина возможных комбинаций. Чтобы одна допустимая комбинация превратилась в другую, должно возникнуть, по крайней мере, два нарушения или четное число нарушений. Пример реализации метода четности представлен в таблице 4.4.

 

Таблица 4.4

Такое кодирование имеет минимальное кодовое расстояние, равное 2. Можно представить и несколько видоизмененный способ контроля по методу четности – нечетности. Длинное число разбивается на группы, каждая из которых содержит q разрядов. Контрольные разряды выделяются всем группам по строкам и по столбцам согласно следующей схеме:

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

 

Пример. Определить и исправить ошибку в передаваемой информации вида

Для контроля использовать метод четности по строкам и столбцам (контрольный столбец 8, контрольная строка 6).

Решение. Прежде всего осуществим проверку на четность по каждой строке:

k 1=0; k 2=1; k 3=0; k 4=0; k 5=0.

Затем проверим на четность информацию по столбцам:

k 6=0; k 7=1; k 8=0; k 9=0; k 10=0; k 11=0; k 12=0.

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

Ответ:

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

 

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

 

Коды, предложенные американским ученым Р. Хэммингом, способны не только обнаружить, но и исправить одиночные ошибки. Эти коды – систематические.

Предположим, что имеется код, содержащий m информационных разрядов и k контрольных разрядов. Запись на k позиций определяется при проверке на четность каждой из проверяемых k групп информационных символов. Пусть было проведено k проверок. Если результат проверки свидетельствует об отсутствии ошибки, то запишем 0, если есть ошибка, то запишем 1. Запись полученной последовательности символов образует двоичное, контрольное число, указывающее номер позиции, где произошла ошибка. При отсутствии ошибки в данной позиции последовательность будет содержать только нули. Полученное таким образом число описывает n = (m + k +1) событий. Следовательно, справедливо неравенство

 

2 k  (m + k +1).

 

Определить максимальное значение m для данного k можно из следующего:

 

n........ 1 2 3 4… 8…15 16…31 32…63 64

m....... 0 0 1 1… 4…11 11…26 26…57 57

k........ 1 2 2 3… 4…4 5…5 6…6 7

 

Определим теперь позиции, которые надлежит проверить в каждой из k проверок. Если в кодовой комбинации ошибок нет, то контрольное число содержит только нули. Если в первом разряде контрольного числа стоит 1, то, значит, в результате первой проверки обнаружена ошибка. Имея таблицу двоичных эквивалентов для десятичных чисел, можно сказать, что, например, первая проверка охватывает позиции 1, 3, 5, 7, 9 и т. д., вторая проверка – позиции 2, 3,6,7,10.

 

Проверка Проверяемые разряды

1… 1,3,5,7,9,11,13,15...

2… 2,3,6,7, 10, 11, 14, 15, 18, 19,22,23..,

3… 4, 5, 6, 7, 12, 13, 14, 15, 20, 21, 22, 23...

4… 8,9, 10, 11, 12, 13,14, 15,24...

 

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

В таблице 4.5 представлены примеры кодирования информации по методу Хэмминга для семиразрядного кода.

 

Таблица 4.5

Как видно из таблицы 4.5, в этом случае n =7, m =4, k =3 и контрольными будут разряды 1, 2, 4.

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

 

Пример. Определить правильность передачи информации А =0,111000 по каналу, если для контроля использован метод Хэмминга.

Решение. Прежде всего определим контрольное число:

k 1=1; k 2=0; k 3=1.

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

Ответ: правильная информация А = 0,111100.

 

Контроль по модулю

 

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

Рассмотрим основные положения из теории сравнений.

Если целым числам А и В соответствует один и тот же остаток от деления на третье число р, то числа А и В равноостаточны друг другу по модулю p или сравнимы по модулю p:

A  B (mod p). (4.1)

 

Сравнения – уравнения типа (4.1).

Сравнимость двух чисел равносильна возможности представить их в алгебраическом виде

А = В + р 1. (4.2)

 

Сравнения обладают рядом свойств:

1. Сравнения можно почленно складывать. Если А 1 B 1(mod p); А 2 B 2(mod p); …; Аn  Bn (mod p), то А 1+ А 2+…+ Аn = В 1+ В 2+…+ Вn (mod p).

Следовательно, слагаемое, стоящее в какой-либо части сравнения, можно переносить в другую часть, поменяв при этом его знак, т. е. A + B  C (mod p) или A  С – B (mod р).

2. Два числа, сравнимые с третьим числом, сравнимы и между собой: если А  В (mod р); С  B (mod р), то А  C (mod р).

3. Сравнения можно почленно перемножить. Пусть А 1 B 1(mod p); А 2 B 2(mod p). Тогда на основании уравнения (4.2) А 1= В 1+11 р; А 2= В 2+12 р.

После умножения получаем А 1 А 2= В 1 В 2+ В 112 р + В 211 р + 1112 pp. Следовательно: А 1 А 2= В 1 В 2+ Np, или в общем случае

А 1 А 2 А 3... Аm  В 1 В 2 В 3... Вm (mod p).

 

Из свойства 3 также следует, что обе части сравнения можно умножить на одно и то же целое число.

Пусть А  B (mod p); К = K (mod p). Тогда АК  BK (mod p).

4. Обе части сравнения и модуль можно умножить на одно и то же число:

А = В + 1 p; Am = Вm + m 1 p, т. е. Am = Bm (mod m p).

 

5. Обе части сравнения и модуль можно разделить на любой общий делитель. Пусть А  В (mod р), где А = ad, В = bd, Р = p 1 d. Тогда А = В + 1 p.

Подставив в это выражение значения А, В и Р, получим

ad = bd + 1 p 1 d.

 

Разделив уравнение на d, получим а = b + 1 р 1, т.е. а = b (mod р 1).

6. Обе части сравнения можно возвести в степень. Если А = B (mod p), то An = Bn (mod p).

Из свойства 6 следует, что над сравнениями можно провести операцию извлечения корня n -й степени.

Рассмотренные выше свойства сравнений используются для осуществления операции контроля.

Существует два метода получения контрольного кода: числовой и цифровой.

 

Числовой метод контроля. При числовом методе контроля код заданного числа определяется как наименьший положительный остаток от деления числа на выбранный модуль p:

rA = А –{ А / р } р,

 

где в фигурных скобках {} – целая часть от деления числа; А – контролируемое число.

Величина модуля р существенно влияет на качество контроля; если р = q (q – основание системы счисления, в которой выражено число) и имеет место числовой контроль, то контролируется только младший разряд числа и контроль как таковой не имеет смысла; для р = qm справедливы аналогичные соображения, так как если m < n, то опять не все разряды числа участвуют в контроле и ошибки в разрядах старше m вообще не воспринимаются.

При числовом методе контроля по модулю р для определения остатка используют операцию деления, требующую больших затрат машинного времени. Для числового метода контроля справедливы основные свойства сравнений (сложение, умножение сравнений и т.д.). Поэтому, если A  r А(mod р); В = rВ (mod р), где 0 r А  р –1; 0  rВ  р –1, то А + В  r А+ rВ (mod р). Отсюда

r А+ В  r А+ rВ (mod р).

 

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

r А- В  r А– rВ (mod р).

r А В  r А rВ (mod р).

 

Пример. Для заданных чисел А =125 и В =89 определить контрольные коды самих чисел, их суммы и разности, если модуль р = 11.

Решение. Определяем контрольные коды чисел:

r А= 125–{125/11}11 = 4; rВ = 89–{89/11}11 = 1.

 

Аналогично находим контрольные коды для суммы и разности:

А + В = 214, r А+ В =214 – {214/11}11=5;

А – В = 36, r А- В = 36 – {36/11}11 = 3.

 

Проведем проверку правильности определения контрольных кодов суммы и разности:

r А+ В = 4 +1  5(mod 11); r А- В = 4 –1  3(mod 11).

 

Ответ: r А= 4; rВ = 1; r А+ В = 5; r А- В = 3.

 

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

 

или

.

 

Возможны два пути получения контрольного кода: 1) непосредственное деление суммы цифр на модуль р; 2) суммирование цифр по модулю p.

Второй путь проще реализуется, так как если аi < р, то контрольный код получается только операцией суммирования.

 

Пример. Определить контрольные коды чисел А = 153 и В = 41, их суммы и разности, если р =11.

Решение. Определяем контрольные коды исходных чисел. Для этого находим суммы цифр и делим их на модуль: = 9; = 5.

Следовательно, r ’А= 9; r ’ В = 5.

Аналогично определяем контрольные коды суммы и разности:

С = А + В = 194; =14; r ’С= 3(mod 11);

D = A – В = 112; =4; r ’ D = 4(mod 11);

Ответ: r ’А= 9; r ’ В = 5; r ’А+ В = 3; r ’А- В = 4.

 

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

Пусть заданы числа А и В и соответственно их контрольные коды

 

,,.

 

Найдем контрольный код r ’С.

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

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

 

, (4.3)

 

где l – количество переносов, возникших при сложении.

Так как r ’А(mod p); r ’ В  (mod p), то r ’С (mod p).

Подставив эти значения в формулу (4.3), получим

r ’С [ r ’А + r ’ В – l (q –1) ] (mod p), (4.4)

 

Аналогичными рассуждениями можно показать, что для разности чисел С = А – В

r ’С[ r ’А– r ’ В + s(q -1) ] (mod p), (4.5)

 

где s – количество заемов при выполнении операции.

 

Пример. Определить контрольные коды чисел А = 589 и В = 195, их суммы и разности, если р =11.

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

 

,,

,.

 

Контрольный код суммы определяем по формуле (4.4) – в этом случае l = 2:

.

 

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

Контрольный код разности получим по формуле (4.5) – в этом случае s = 1:

.

Ответ: r ’А= 0; r ’ В = 4; r ’А+ В = 8; r ’А- В = 5.