Глава 3 основы теории кодирования

3.1. Назначение и классификация кодов

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

Пусть источник выдает некоторое дискретное сообщение А, которое можно рассматривать как последовательность элементарных сообщений или символов а_i (i = 1, 2, . . . К). Совокупность символов а_i называется алфавитом источника, а К - объемом алфавита.

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

При кодировании отдельным символам а_i удобно сопоставить целые числа от 0 до К-1, обозначив их, например, M_i

Любое число M может быть представлено в позиционной системе счисления с основанием m в виде

M = b_n-1m^n-1 + b_n-2m^n-2 +. . . + b₁m¹ + b₀m⁰ (3.1)

Основанием позиционной системы счисления называется количество символов в алфавите системы счисления, а в качестве коэффициентов b_i в (3.1) могут использоваться только символы, входящие в алфавит этой системы, т.е. b_i могут принимать значения 0, 1, . . . , m-1.

Тогда кодирующее преобразование можно отобразить так

а_i  M_i  (b_n-1 b_n-2 . . . b₁ b₀), (3.2)

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

Число m символов в алфавите кода называется основанием кода.

Число разрядов n в каждой кодовой комбинации постоянно при всех i, т.е. n=const, то такой код называется равномерным.

Необходимость замены каждого символа а_i из К символов источника последовательностью кодовых символов (b_n-1 b_n-2 . . . b₁ b₀) или кодовой комбинацией объясняется тем, что в большинстве случаев объем алфавита K>m, т.е. основания кода или объема алфавита кодовых символов. Например, в телеграфном коде каждая буква русского алфавита (К=32) кодируется кодовой комбинацией из n=5 двоичных (m=2) символов (0 и 1).

Если сообщение «а» заменяется кодовой комбинацией «b» при условии их однозначного соответствия и обратимости преобразования, то на основе свойств взаимной информации (2.13. и 2.14) можно записать I(a,b) = H(a) = =H(b), где I(a,b) - количество информации в кодовой последовательности «b» относительно сообщения «а», H(a) - энтропия сообщения, H(b) - энтропия кодовой последовательности. Следовательно, при кодировании энтропия не меняется.

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

Число возможных кодовых комбинаций из n разрядов для кода с основанием m равно N=mⁿ . Если из этих N комбинаций для кодирования используется только часть, равная N_р, которые называются рабочими или разрешенными, то величина N_р называется мощностью кода.

Избыточность кода характеризуется коэффициентом избыточности

_к = 1 - (log_mN_p / log_mN). (3.3)

Код, у которого N_р = N , т.е. используются все возможные комбинации, имеет _к = 0 и называется безизбыточным или неизбыточным.

Простейшим безизбыточным равномерным кодом является обычный двоичный (m=2) n-разрядный код, называемый иногда кодом на все сочетания. Число комбинаций такого кода N = 2ⁿ.

К таким кодам можно отнести уже упомянутый телеграфный код, а также стандартные коды для обмена информацией КОИ-7, КОИ-8, ASCII и другие.

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

Например: 1101

1101

1011

Или, другими словами, если начинать преобразование с младшего (правого) разряда, то алгоритм выглядит следующим образом: «Если последующий разряд равен 1, то данный разряд инвертируется, если последующий разряд равен 0, то данный разряд остается неизменным. Старший разряд остается неизменным».

Пример 3.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
10	1010	1111
11	1011	1110
12	1100	1010
13	1101	1011
14	1110	1001
15	1111	1000

Функциональная схема преобразователя обычного двоичного кода в код Грея для четырехразрядных комбинаций представлена на рис. 3.1

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

Рис. 3.1 Преобразователь обычного кода в код Грея	Рис. 3.2. Преобразователь кода Грея в обычный код

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

Решение. Функциональная схема четырехразрядного преобразователя кода Грея в обычный двоичный код представлена на рис. 3.2

Преимущества кода Грея проявляются при преобразованиях аналоговых (непрерывных) величин в код. Если при таком преобразовании используется обычный двоичный код, то некоторые комбинации отличаются друг от друга во всех разрядах и при считывании такого кода может возникнуть ошибка, достигающая максимальной величины 2^n-1, где n - число разрядов кода. Например, комбинация 0111 при неправильном считывании старшего разряда преобразуется в комбинацию 1111, т.е. ошибка составит величину 15-7 =8 = 2^4-1. При тех же значениях и при той же ошибке, но при использовании кода Грея (см. таблицу) комбинация 0100 будет считана как 1100, т.е. ошибка составит величину 8-7=1, т.е. единицу младшего разряда.

Еще одним классом примитивных кодов, используемых при различных промежуточных преобразованиях, являются двоично-десятичные коды. В таком коде каждая цифра (декада) десятичного числа записывается в виде четырехразрядного двоичного числа (тетрады). С помощью 4 разрядов можно образовать 2⁴ = 16 различных комбинаций, из которых любые 10 могут составить алфавит двоично-десятичного кода. В связи с этим существует большое количество различных двоично-десятичных кодов. Наиболее употребительные из них представлены в таблице.

Десятичная цифра	Код 8421	Код 5421	Код 2421	Код «с избытком 3»
0	0000	0000	0000	0011
1	0001	0001	0001	0100
2	0010	0010	0010	0101
3	0011	0011	0011	0110
4	0100	0100	0100	0111
5	0101	1000	1011	1000
6	0110	1001	1100	1001
7	0111	1010	1101	1010
8	1000	1011	1110	1011
9	1001	1100	1111	1100

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

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

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

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