Кодирование информации

Одну и ту же информацию мы можем выразить разными способами.

Например, каким образом вы можете сообщить об опасности?

• Если на вас напали, вы можете просто крикнуть: «Помогите!» (англичанин крикнет)

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

• На оживленном перекрестке регулировщик помогает избежать аварии с помощью жестов.

• В театре пантомима вся информация передается зрителю исключительно с помощью мимики и жестов.

• Если ваш корабль тонет, то вы передадите сигнал «SOS» (…– – –…).

• На флоте помимо азбуки Морзе используются также семафорную и флажковую сигнализацию.

В каждом из этих примеров мы должны знать правила, по которым можно отобразить информацию об опасности тем или иным способом. Такое правило назовем кодом.

Обычно каждый образ при кодировании (иногда говорят – шифровке) представлен отдельным знаком.

Знак – это элемент конечного множества отличных друг от друга элементов. Знак вместе с его смыслом называют символом.

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

Существует множество алфавитов.

• алфавит кириллических букв {А,Б,В,Г,Д,Е, .. .}

• алфавит латинских букв {A,B,C,D, E, F, …}

• алфавит десятичных цифр {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

• алфавит знаков зодиака {, , , , , , , , , , , }

Имеются, однако, наборы знаков, для которых нет какого-то общепринятого порядка:

• набор знаков азбуки Брайля (для слепых);

• набор китайских идеограмм;

• набор знаков планет;

• набор знаков генетического кода (А, Ц, Г, Т).

Особенно важное значение имеют наборы, состоящие всего из двух знаков:

• пара знаков {+,-};

• пара цифр {0,1};

• пара ответов {да, нет};

Как вы назвали такие наборы знаков? Правильно вы подумали: их называют двоичными. Рассмотрим более подробно двоичный алфавит (0,1). Чтобы отличить выходящие в его состав знаки от привычных (десятичных) нуля и единицы, про каждый знак мы должны сказать: знак «0» из двоичного набора знаков; знак «1» из двоичного набора знаков. Удобнее было бы сказать; двоичный знак, но тогда нам безразлично-«0» это или «1», главное, что это какой-то один из двух знаков двоичного алфавита. Двоичный знак (анг.binary digit) получил название «бит».

Важнейшие технические коды возникли с пояевлением электрического телеграфа, например

• азбука Морзе;

• набор знаков второго международного телеграфного кода (телекс).

Код используется для представления информации в виде, удобном для хранения и передачи.

Пример. Попробуем закодировать числа от нуля до ста, не используя арабских или римских цифр.

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

Попробуем использовать в качестве букв нашего алфавита символы {*,+,#,&}, или знак {,,}, или гласные буквы русского алфавита.

Каждому числу, которое нужно закодировать, поставим в соответствие “букву” из выбранных нами алфавитов. Например:

Числа	1-й алф.	2-й алф.	3-й алф.
0	*		а
1	+		е
2	!		ё
3	#		и
4	&		о
5			н
6			ы
7			э
8			ю
9			я
10
11

Во всех трех случаях мы не решили поставленной задачи. Мы не смогли закодировать числа от одного до ста, используя предложенные алфавиты. Получается, что наш алфавит должен состоять из ста одного знака. Но с помощью всего десяти арабских цифр мы можем записать любое число, а римских цифр для кодирования чисел от одного до ста потребуется всего пять: I, V, X, L, C.

Нужен другой подход, другое правило. Какое? Покажем, что, используя всего три символа, например {,,}, можно закодировать (зашифровать, представить) любое число. Попробуем каждое число представлять не одним, а несколькими символами из нашего алфавита. Таким образом, в нашем правиле появляется понятие “длина кода”. Длиной кода назовем то количество знаков, которое используется для представления того или иного числа. (Количество символов в алфавите кодирования и длина кода-совершенно разные вещи. Например, в русском алфавите 33 буквы, а слова могут быть длиной в 16263 и.т.д. буквы.)

Посмотрим сколько чисел мы можем закодировать, если длина кода не больше двух символов.

0	1	2	3	4	5	6	7	8	9	10	11	12	13
													

  

        

  

Чтобы закодировать числа 12, 13 и. т. д., следует увеличивать длину кода.

Обратная задача: есть закодированное число   , коды известны. Определите исходное число.

Так как по нашему правилу длина кода может быть 1 или 2 символа, то:

• могли быть закодированы три числа –1, 2, 0;

• могли быть закодированы два числа – 1, 9;

• могли быть закодированы два числа – 8, 0;

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

Коды различной длины в технике встречаются довольно редко. Исключением является лишь код Морзе. ( Сэмюэль Финли Бриз Морзе был первым президентом Национальной академии искусств США. В 42 года он бросил живопись и целиком посвятил себя изобретению телеграфа.) Взгляните на международную азбуку Морзе.

A	. –	J	. – – –	S	…
B	– . . .	K	– . –	T	–
C	– . – .	L	. – . .	U	. . –
D	– . .	M	– –	V	. . . –
E	.	N	– .	W	. – –
F	. . – .	O	– – –	X	– . . –
G	– – . .	P	. – – .	Y	– . – –
H	….	Q	– – . – .	Z	– – . .
I	..	R	. – .

Для отправителя приведенная таблица выглядит вполне логично, ибо буквы в ней расположены в алфавитном порядке. Но для человека, получающего сообщения, она малопригодна. В каком же порядке следует расположить символы чтобы, получив сигнал, мы могли, не теряя времени, определить, какой букве соответствует данный сигнал. Представим азбуку Морзе в виде дерева.

При получении сигнала – это либо точка, либо тире – будем произвольно спускаться по дереву: если точка – влево от текущей вершины, если тире - вправо, если пауза – записываем букву текущей вершины, если длинная пауза – отмечаем конец слова.

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

Азбука Морзе – это троичный код с набором знаков: точка, тире, пауза. Необходимо использовать паузу в качестве разделителя между буквами и словами, так как длина кода непостоянна.

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

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

Вернемся к нашей задаче. Будем использовать для представления (кодирования) чисел от нуля до ста алфавит (,,) и код постоянной длины. Какова должна быть длина кода?

В случае, когда длина кода равняется, алфавитом, состоящим из трех символов, можно закодировать 3 различных состояний ( чисел, букв, комбинаций), двоичным алфавитом можно закодировать 2 различных состояний, алфавитом, состоящим из к символов, можно закодировать к различных состояний.

Решите обратную задачу: какой длины должен быть код, чтобы, используя разные алфавиты, закодировать 10, 33, 100, 200, 1000 различных символов? Проанализируйте таблицу.

Материал для запоминания

Знак – это элемент конечного множества отличных друг от друга элементов. Знак вместе с его смыслом называют символом.

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

Алфавит, состоящий из двух знаков, называется двоичным алфавитом.

Код (фр. code - кодекс, свод законов). Начиная XIX в. это слово помимо основного значения означало книгу, в которой словам естественного языка были сопоставлены группы цифр или букв.

Кодом называется правило для преобразования одного набора знаков в другой набор знаков.

Кодированием называется процесс преобразования одного набора знаков в другой набор знаков.

Кодирование – способ хранения и передачи информации, форма представления ее на носителе.

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

Длиной кода называется такое количество знаков, которое используется при кодировании.

Количество символов в алфавите кодирования и длина кода – совершенно разные вещи. Например, в русском алфавите 33 буквы, а слова могут быть длиной в 1,2,3, и т.д. буквы.

Код может быть постоянной и непостоянной длины. Коды различной (непостоянной) длины в технике используются довольно редко. Исключением является лишь троичный код Морзе. В вычислительной технике в настоящее время широко используется двоичное кодирование с алфавитом (0,1). Наиболее распространенными кодами являются ASCII (American standard code for information interchange – стандартный американский код для обмена информацией) и КОИ-8 (код обмена информации длиной 8 бит).

Одно и то же сообщение можно закодировать разными способами, т. е. выразить на разном языках. В процессе развития человеческого общества люди выработали большое число языков кодирования. К ним относятся:

• разговорные языки (русский, казахский, хинди и др. – всего более 2000);

• язык мимики и жестов;

• язык рисунков и чертежей;

• язык науки (математические, химические, биологические и другие символы);

• язык искусства (музыки, живописи, скульптуры и т.д.);

• специальные языки ( эсперанто, морской семафор, азбука Морзе, азбука Брайля для слепых и др.).

В специальных языках особо выделим языки программирования.

Для любознательных

Программирование – кодирование информации на языке, понятном компьютеру.

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

Троичное кодирование, несмотря на ряд технических попыток, успеха не умела. Четверичное кодирование в криптографических целях (криптография-тайнопись) использовалось еще в XV веке. Набор знаков «генетического кода» состоит из четырех букв – А, Ц, Г, Т обозначающих соответственно химические соединения (аденин, цитозин, гуанин, тимин).

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

Наиболее распространенные цели кодирования:

• экономность (уменьшение избыточности сообщения, повышение скорости передачи или обработки);

• надежность (защита от случайных искажений);

• сохранность (защита от нежелательного доступа к информации);

• удобство физической реализации (двоичное кодирование информации в ЭВМ);

• удобство восприятия (схемы, таблицы).

Интересный факт

В 1977 г. математики Р. Ривест, А. Шамил и Л. Эделман зашифровали фразу из нескольких слов, используя комбинацию из 129 цифр. Они утверждали, что на разгадку понадобятся триллионы лет, однако ключ к самому сложному в мире шифру РСА-129 был найден за 17 лет. Над де шифрованием работали 600 ученых и добровольцев на пяти континентах при помощи 1600 компьютеров. Сложность шифра заключалась в том, что для его разгадки было необходимо определить две группы простых чисел, которые при умножении давали код РСА-129. Зашифрованной оказалась бессмысленная фраза «волшебные слова – щепетильная скопа» (скопа – это хищная птица, живущая у водоемов и питающаяся рыбой). Эти слова были наугад выбраны из словаря в 1977г. «Такие шифры необходимы, если вы хотите сохранить в секрете рецепт приготовления кока-колы или формулы создания ядерного оружия», - сказал Р. Ривест на пресс-конференции в 1994г. Разгадка шифра за такой относительно короткий срок имеет огромное значение для государственных организаций и предпринимателей, которые пользуются аналогичными длинными цифровыми кодами для защиты секретных сведений в своих компьютерных базах данных. Задачи, связанные с кодированием и декодированием сообщений, изучаются в теории кодирования – одном из разделов теории информации.