Код называется равномерным (или кодом постоянной длины), если все его кодовые слова содержат одинаковое число букв (одинаковую длину слов). Соответственно, кодирование называется равномерным, если соответствующий ему код имеет постоянную длину. В настоящее время в информатике более употребительно равномерное кодирование, оно проще и более удобно. В компьютерах при кодировании информации в основном используются равномерные коды, соответствующие размерам компьютерных ячеек.
К равномерным кодам относится телеграфный код Бодо (Baudot code). Его можно считать двоичным равномерным алфавитным кодом. Первоначальный вариант этого кода разработал Эмиль Бодо в 1870 году для своего телеграфа. Код вводился прямо клавиатурой, состоящей из пяти клавиш, нажатие или ненажатие клавиши соответствовало передаче или непередаче одного бита в пятибитном коде. Например, буква А передавалась как - - + - - , что соответствовало нажатию средней клавиши. В двоичном коде это можно записать как 00100. Таким образом, каждая буква записывалась пятью битами. Следовательно, кодом Бодо можно было передать 25=32 различных символа.
Другим интересным примером равномерного кода является код Трисиме, в котором знакам латинского алфавита ставятся в соответствие кодовые слова длины 3 над алфавитом из 3-х символов: {1, 2, 3}. Этот код представлен в следующей таблице :
Понятно, что код Трисиме не может кодировать более чем 33=27 символов.
Число букв в алфавите кода называется основанием кода, а длина кодовых слов равномерного кода называется порядком кода. Коды с основанием 2, как уже говорилось, называются двоичными, а с основанием 3 – троичными, и так далее. Так код Бодо имеет основание 2, а порядок 5, а у кода Трисиме и основание, и порядок равны 3.
Код называется неравномерным (или кодом переменной длины), если его кодовые слова имеют разное число букв (неодинаковую длину слов). Соответственно, кодирование называется неравномерным, если соответствующий ему код неравномерный.
Типичным примером неравномерного кода является телеграфный код, который принято называть азбукой Морзе. На следующей таблице представлен код азбуки Морзе для русского алфавита:
A
• −
И
• •
P
• − •
Ш
− − − −
• − − − −
− − − − •
Б
− • • •
Й
• − − −
С
• • •
Щ
− − • −
• • − − −
− − − − −
В
• − −
К
− • −
Т
−
Ъ
• − − • − •
• • • − −
Точка
• • • • • •
Г
− − •
Л
• − • •
У
• • −
Ь
− • • −
• • • • −
Запятая
• − • − • −
Д
− • •
М
− −
Ф
• • − •
Ы
− • − −
• • • • •
/
− • • − •
Е
•
H
− •
Х
• • • •
Э
• • − • •
− • • • •
?
• • − − • •
Ж
• • • −
О
− − −
Ц
− • − •
Ю
• • − −
− − • • •
!
− − • • − −
З
− − • •
П
• − − •
Ч
− − − •
Я
• − • −
− − − • •
@
• − − • − •
Как видим, азбука Морзе состоит из слов над алфавитом из двух символов: точка и тире. Но, строго говоря, этот код не является двоичным, так как он при кодировании слов предполагает еще один символ для разделения букв в слове (символ «пауза»). Без этого символа не было бы однозначности при декодировании текстов. Например, код из четырех тире можно было бы декодировать по-разному: или как код одной буквы Ш, или как код сочетаний из двух букв - ММ, ОТ или ТО. Разделяющий символ позволяет однозначно декодировать любую кодовую последовательность, полученную кодированием сообщений при помощи азбуки Морзе, но тогда код азбуки Морзе следует считать троичным, так как его алфавит содержит три символа.
Американский изобретатель телеграфа Сэмюель Морзе разработал этот код в 1838 году для передачи телеграфных сообщений в виде последовательности электрических сигналов, передаваемых от одного телеграфного аппарата по проводам к другому телеграфному аппарату. Этот код был придуман Морзе задолго до научных исследований
СэмюэлМорзе (1791-1872)
относительной частоты появления различных букв в текстах, но, тем не менее, Морзе при составлении кода использовал принцип частоты букв. Буквам, используемым чаще, им присвоены короткие кодовые комбинации, редко используемым буквам – длинные. Морзе оценил относительную частоту букв английского языка подсчетом литер в ячейках типографской наборной машины. Наиболее часто используемой букве «Е» (в английском языке) он присвоил наиболее короткий код «точка». Следующей по количеству литер букве он присвоил код несколько большей длительности и так далее.
При составлении азбуки Морзе для букв русского алфавита учет относительной частоты букв не производился, и это повысило его избыточность. Расчеты избыточности кода Морзе на основании проведенных исследований частоты появления букв показали, что для букв английского алфавита она составляет 19%, для букв русского алфавита 22%.
Самым знаменитым телеграфным сообщением является сигнал бедствия "SOS" (Save Our Souls - спасите наши души). Вот как он выглядит: «• • • – – – • • •»
Преимущество у неравномерных кодов перед равномерными как раз и состоит в том, что сообщения можно передавать более экономным способом, так как часто передаваемые кодовые слова более короткие, а значит, кодовая последовательность может иметь меньшую длину, чем для равномерных кодов. Ниже это будет показано.
Но у неравномерных кодов есть серьезный недостаток по сравнению с равномерными кодами. У равномерных кодов кодовая последовательность всегда декодируется однозначно за счет того, что кодовые слова имеют одинаковую длину (кодовая последовательность легко делится на кодовые слова). Но не для всех неравномерных кодов достигается однозначность декодирования кодовых последовательностей. Мы уже видели это, пытаясь рассматривать азбуку Морзе как двоичный код.
Приведем более простой пример. Пусть S = {s1,s2, …, s7} - множество сообщений, кодирование которых задается кодовыми словами над алфавитом {0,1} при помощи функции F :
Этот код неравномерный (кодовые слова разной длины).
Закодируем последовательность сообщений: s7s7. Имеем F(s7s7)=B=111111. Но эта последовательность может быть декодирована и по-другому, так как: B=F(s3s3s3)= F(s1s3s7)=F(s3s7s1)=F(s1s1s1s1s1s1s1s). Как видим, способов декодирования много (подсчитайте: сколько их?). Неоднозначно декодируется и следующая последовательность:
11011011 (а сколько здесь способов декодирования?). Очевидно, что такой код практически использовать нельзя. А если мы изменим код так, чтобы он стал равномерным, например, доопределим функцию F так:
