Коды и кодирование

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

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

Особенно элементарным запасом знаков является множество В:

В={L.,0}.

Элемент множества В называется двоичным знаком или битом

(Bit – от Binary Digit).

Множество конечных последовательностей знаков над запасом знаков А называется также множеством слов над А. При множестве В* = {L О}* говориться о двоичных словах. Элементы множества

называются также п-битовыми словами или двоичными словами длины п. Множество n-битовых слов часто само снова используется в качестве запаса знаков.

Отображения между запасами знаков А и В, и в частности между словами над запасами знаков, называются кодами

или кодировкой..

Специальные случаи кодировки предусматривают представление не для всех слов из А*. Такие кодировки соответствуют частичным

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

В общем случае предполагается, что кодировка является инъективным отображением: различные знаки и слова в этом случае отображаются на разные кодовые слова. Тем самым каждая кодировка

обратима на ее прообраз. Обратное отображение

для отображения кодировки с называется декодировкой или дешифровкой. Тогда справедливо следующее: d(c(a))=a.

Коды постоянной длины

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

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

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

Хэмминга математически соответствует отображение

       Расстояние отображения кодировки

для длины кодов n определяется через минимальное расстояние Хэмминга между двумя различными кодами:

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

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

Пример (4-битовый код Грэя для десятичных цифр). Четырехбитовый код Грэя для десятичных цифр соответствует кодировке

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

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

Коды переменной длины

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

Пример (коды переменной длины).

(1) Код Морзе в двоичном кодировании

Код Морзе строится из трех знаков, которые соответствуют «короткой». «длинной» передаче (точки и тире) и пробелу («паузе»). Двоичная кодировка

с : { ., -, «пауза»} -^ { OL, OLLL, 000} определяется следующим образом:

с(.) = OL, с(-) = OLLL. с(«пауза») = 000.

(2) Код для телефонных систем

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

Цифра        Код

1                             LO

2                             LLO

3                             LLLO

4                             LLLLO

5                             LLLLLO

6                             LLLLLLO

7                             LLLLLLLO

8                             LLLLLLLLO

9                             LLLLLLLLLO

                                 0              LLLLLLLLLLO

Таблица 7.1. Код для телефонных cucmem

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

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

Последовательное и параллельное кодирование последовательностей знаков

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

(1)

Последовательная кодировка слов. Для заданной кодировки

отдельных знаков рассмотрим ее расширение на слова над А. Это значит, что рассматривается кодировка с* над А*, индуцированная кодировкой с.

Таким образом, при последовательной кодировке слов кодируются слова w над А путем конкатенации кодов отдельных знаков слова w.

(2) Параллельная кодировка cлoв. Для заданной кодировки с с постоянной длиной кодов рассматривается индуцированное отображение с'.

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

Содержание раздела