2.4. Основы построения неизбыточных кодов

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

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

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

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

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

Полученные комбинации отличаются одна от другой не менее чем одним элементом.

Из табл. 6 видно, что запись комбинаций на все сочетания является записью чисел от 0 до 7 в двоичной системе счисления. Такой код называют простым двоичным кодом. Построение всех кодовых комбинаций этого кода удобнее всего достигается посредством написания

Таблица 6 (см. скан)

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

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

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

Наиболее известными представителями неравномерных двоичных кодов являются код Шеннона — Фано и код Хаффмена [134].

На рис. 8 показана классификация неизбыточных двоичных кодов.