Конспект установочных лекций по комплексному курсу Информатика, Теория информации




Коды и кодирование - часть 2


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

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

      

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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




Содержание  Назад  Вперед