» » »

58. Оптимальное статистическое кодирование сообщений. Оптимальное кодирование для канала без помех.

Оптимальное кодирование

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

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

Общепризнанным в настоящее время является позиционный принцип образования системы счисления. Значение каждого символа (цифры) зависит от его положения - позиции в ряду символов, представляющих число. Единица каждого следующего разряда больше единицы предыдущего в т раз, где т - основание системы счисления. Полное число получаем, суммируя значения по разрядам. (Пример: в десятичном коде class=normal. т =10; младший разряд - 1, второй - 10, третий - 100, то есть единица старшего разряда в десять раз больше единицы предыдущего разряда - единицы, десятки, сотни; также и в других системах счисления.)

Чем больше основание системы счисления, тем меньшее число разрядов требуется для представления данного числа, а следовательно, и меньшее время для его передачи. Однако с ростом основания усложняются устройства передачи и приема сигналов, так как логические элементы в этом случае должны иметь большее число устойчивых состояний. Если учитывать оба эти обстоятельства, то целесообразно выбрать систему, обеспечивающую минимум произведения основания кода т на количество разрядов п для выражения любого числа. Найдем этот минимум по графику для большого числа 60000class=normal.

class=normal

Рис. 2.4 - График зависимости числа разрядов п от основания кода т для числа 60000class=normal

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

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

Действительно, арифметические операции в двоичной системе достаточно просты:

сложение вычитание умножение
0+0=0; 0 - 0=0; 0·0=0;
0+1=1; 1 - 0=1; 0·1=1;
1+0=1; 1 - 1=0; 1·0=1;
1+1=10 10 - 1=1 1·1=1


Сложение по модулю в двоичной системе также просто:

0class=normal0=0;

0class=normal1=1;

1class=normal1=0;

1class=normal0=1

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

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

class=normal

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

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

Таблица 2.1

Число в десятичном

коде

Двоично-десятичный

код 8-4-2-1

Двоично-десятичный

код 5-1-2-1

0 0000 0000
1 0001 0001
2 0010 0010
3 0011 0011
4 0100 0111
5 0101 1000
6 0110 1001
7 0111 1010
8 1000 1011
9 1001 1111


Код 8-4-2-1 обычно используется как промежуточный при введении в вычислительную машину данных, представленных в десятичном коде.

Перевод чисел из десятичного в двоично-десятичный код осуществляется перфоратором в процессе переноса информации на перфоленту или перфокарту. Последующее преобразование в двоичный код осуществляется по специальной программе в самой машине. Двоично-десятичные коды с весами 5-1-2-1 и 2-4-2-1 используются при поразрядном уравновешивании в цифровых измерительных приборах (цифровые вольтметры и т.п.).

Недостатки взвешенных кодов: при передаче информации по каналам связи под действием помех отдельные элементы кода могут так исказиться, что будут приняты неверно. Например, вместо «0» будет принят элемент «1» или наоборот. Если будет искажен старший разряд, то ошибка будет значительно больше, чем при искажении младшего разряда. С этой точки зрения лучше применять невзвешенный код, у которого ошибки, вызванные помехами, были бы одинаковыми для любого разряда.

В невзвешенных кодах позициям (разрядам) кодовой комбинации не приписывают определенных весов. Вес имеет лишь вся кодовая комбинация в совокупности. Рассмотрим невзвешенный двоичный рефлексный код Грея (табл. 2.2).

Таблица 2.2

Десятичное

число

Двоичный код

вес 8-4-2-1

Код Грея
0 0000 0000
1 0001 0001
2 0010 0011
3 0011 0010
4 0100 0110
5 0101 0111
6 0110 0101
7 0111 0100
8 1000 1100
9 1001 1101
... ... ...
15 1111 1000


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

class=normal

Характерные особенности кода Грея:

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

2) смена значений элементов в каждом разряде (1 на 0 или 0 на 1) при переходе от комбинации к комбинации в коде Грея происходит вдвое реже, чем в натуральном двоичном коде. Это свойство кода Грея позволяет получить точность кодирования выше по сравнению с натуральным двоичным кодом при том же быстродействии схемы кодирования;

3) при сложении двух соседних комбинаций кода Грея по модулю 2 (mod2) число единиц равно числу разрядов минус три (n-3). Это свойство кода Грея можно использовать для проверки правильности принятых комбинаций.

В коде Грея можно выделить оси симметрии (оси отражения), относительно которых наблюдается идентичность элементов в некоторых разрядах. Так, например, имеет место симметрия относительно оси, проведенной между числами 7 и 8 (идентичны три символа младших разрядов). Эта особенность и послужила основанием для введения термина «рефлексный», то есть отраженный код.

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

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

Преобразование кода Грея в натуральный двоичный код выполняется по правилу: старший разряд записывается без изменения, каждый следующий символ кода Грея нужно инвертировать, если в натуральном коде перед этим была получена «1», и оставить без изменения, если в натуральном коде был получен «0». (Пример: class=normal).


Друзья! Приглашаем вас к обсуждению. Если у вас есть своё мнение, напишите нам в комментарии.