Теоретическое обоснование. Описание принципов построения кодов

Описание принципов построения кодов

При передаче сообщений по линиям связи всегда приходится пользоваться тем или иным кодом, т. е. представлением сообщения в виде ряда сигналов. Примером такого кода является азбука Морзе, в которой любое сообщение представляется в виде комбинации элементарных сигналов: точка, тире, пауза (пробел между буквами), длинная пауза (пробел между словами) [3].

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

Наиболее простым случаем кодирования является случай, когда обе системы X и Y (отображаемая и отображающая) имеют конечное число возможных сообщений. Так обстоит дело при передаче записанных буквами сообщений, например при телеграфировании. Ограничимся рассмотрением этого простейшего случая кодирования.

Пусть имеется некоторая система X, которая может случайным образом принять одно из состояний x₁,x₂,...,x_n. Необходимо закодировать ее с помощью другой системы Y, возможные состояния которой y₁,y₂,...,y_m. Если m < n (число состояний системы Y меньше числа состояний системы Х), то нельзя каждое состояние системы X закодировать с помощью одного-единственного состояния системы Y. В таких случаях одно состояние системы X приходится отображать с помощью определенной комбинации (последовательности) состояний системы Y. Так, в азбуке Морзе буквы отображаются различными комбинациями элементарных символов (точка, тире). Выбор таких комбинаций и установление соответствия между передаваемым сообщением и этими комбинациями и называется "кодированием" в узком смысле слова

Коды различаются по числу элементарных символов (сигналов), из которых формируются комбинации, т.е. по числу возможных состояний системы Y. В азбуке Морзе элементарных символов четыре – точка, тире, короткая пауза, длительная пауза. Передача символов может осуществляться в различной форме: световые вспышки, посылки электрического тока различной длительности, звуковые сигналы и т.п. Широко распространены коды с двумя элементарными символами (0 и 1), такие коды называются двоичными [2]. Двоичные коды используются, например, при вводе, обработке и выводе информации в ЭВМ.

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

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

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

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

а ~ 00000

б ~ 00001

в ~ 00010

г ~ 00011

.........

я ~ 11110

- ~ 11111

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

В связи с этим рассмотрим другой способ кодирования [1]. Так как одни буквы (а, е, о) встречаются часто, а другие (щ, э, ф) редко, то часто встречающиеся буквы целесообразно закодировать меньшим числом символов, а реже встречающиеся - большим. Чтобы составить такой код, нужно знать частоты букв в русском тексте. Они известны и приведены в табл. 1.

Таблица 1

буква	частота	буква	частота	буква	частота	буква	частота
-	0.145	р	0.041	я	0.019	х	0.009
о	0.095	в	0.039	ы	0.016	ж	0.008
е	0.074	л	0.036	з	0.015	ю	0.007
а	0.064	к	0.029	ъ,ь	0.015	ш	0.006
и	0.064	м	0.026	б	0.015	ц	0.004
т	0.056	д	0.026	г	0.014	щ	0.003
н	0.056	п	0.024	ч	0.013	э	0.003
с	0.047	у	0.021	й	0.01	ф	0.002

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