Лекция "Кодирование информации"



Формы представления информации

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

Текстовая информация основана на использовании цифр, знаков и т.д. Информация заложена не только в этих символах, но и в их сочетании. Так, слова «кот» и «ток» состоят из одинаковых букв, но содержат различную информацию. Благодаря взаимосвязи символов и письменному отображению речи человека, текстовая информация чрезвычайно удобна и широко используется.

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

Числовая информация представляется в виде чисел, определяющих количество чего-либо.

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

Знаки, наборы знаков и алфавиты

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

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

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

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

Примеры:
  • алфавит десятичных цифр: {0,1,2,3,4,5,6,7,8,9},
  • алфавит заглавных латинских букв (А, В, С, D...);
  • алфавит заглавных букв кириллицы;
  • нотная запись в музыке также представляет собой своеобразный алфавит и может быть представлена латинскими буквами: {С-до, D-pe, Е-ми, F-фа, G-соль, А-ля, В-си}.
Вот некоторые наборы знаков, в которых нет какого-либо общепринятого порядка:
  • набор знаков клавиатуры пишущей машинки;
  • набор знаков мастей игральных карт;
  • набор знаков генетического кода, состоящий из четырех букв А,Ц,Г и Т, которые обозначают соответственно химические соединения (адеин, цитозин, гуанин и тимин).
С появлением электрического телеграфа, а позднее – технологии обработки данных возникли важные технические коды:
  • набор знаков азбуки Морзе;
  • набор знаков международного телеграфного кодаCCIT-2;
  • набор знаков кода IBM для пробивки перфокарт;
  • набор знаков 7-разрядного международного кода ISO (International Standards Organization), содержащий 128 различных символов.
Особое значение имеют наборы, состоящие из двух знаков. Такие наборы называются двоичными наборами, а сами знаки – двоичными знаками. Вместо термина «двоичный знак» часто употребляют сокращение БИТ (от английского BInary digiT – двоичная цифра).

Примерами двоичных наборов являются:
  • пара цветов {красный, зеленый};
  • пара яркостей {светлый, темный};
  • пара цифр {0, 1};
  • пара состояний {пробивка, нет пробивки};
  • пара состояний {включено, выключено};
  • пара состояний {намагничено, размагничено};
  • пара ответов {да, нет} и т.д.

Коды и кодирование дискретных сообщений

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

Пусть имеется предложение некоторого естественного языка, тогда его можно рассматривать как последовательность знаков, по крайней мере, тремя различными способами:
  1. как последовательность букв, цифр и знаков препинания;
  2. как последовательность слов, которые в другом контексте могут сами рассматриваться как знаки (например, в стенографии);
  3. все предложение целиком можно рассматривать как знак (например, при переводе пословицы на другой язык она не переводится дословно, а подбирается аналогичная по смыслу).
Таким образом, можно констатировать:
  • дискретные сообщения представляют собой последовательности знаков (конечные или бесконечные). При этом их обычно разбивают на конечные последовательности знаков, называемые словами.
  • На более высоком уровне каждое слово может снова рассматриваться как знак, при этом соответственно набор знаков будет шире первоначального (алфавит - 33 буквы, слов – 150 тысяч).
  • Наоборот, данный набор знаков можно получить с помощью составления слов, исходя из некоторого набора с меньшим числом знаков, в частности из двоичного набора знаков.
Сформулируем ряд определений.
  • Кодом называется правило, описывающее отображение одного набора знаков в другой набор знаков (или слов). Кодом также называют и множество образов (то есть конкретных графических изображений знаков) при этом отображении.
  • Если каждый образ при кодировании является отдельным знаком (но не словом!), то такое отображение называют шифровкой, а образы – шифрами. Обращение этого отображения (то есть процесс возврата к первоначальному виду), если оно однозначно, называется декодированием, или дешифровкой.
Нас будут интересовать технические коды, используемые в вычислительной технике. В них буквы, цифры и другие знаки почти всегда кодируются словами, записанными в двоичном коде.

Решение задач по кодированию

Разберём в качестве примеров несколько задач:

Используя шифр «Цезаря» зашифруйте слово МИР

Решение: Этот шифр реализует следующее преобразование текста: каждая буква исходного текста заменяется третей после неё буквой в алфавите, который считается написанным по кругу:

  • Букву М заменяем на П (т.к. 3-я буква после М – П)
  • Букву И заменяем на М (т. к. 3-я буква после И – М)
  • Букву Р заменяем на У (т. к. 3-я буква после Р – У)

Ответ: код слова МИР – ПМУ

Расшифруйте слово ПМУ, закодированное с помощью шифра Цезаря

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

  • Букву П заменяем на М (т.к. 3-я буква перед П – М)
  • Букву М заменяем на И (т. к. 3-я буква перед М – И)
  • Букву У заменяем на Р (т. к. 3-я буква перед У – Р)

Ответ: декодируем ПМУ и получаем МИР

Закодируйте слова шифром «Винжера» (ключевое слово ВАЗА) слово МИР

Это шифр представляет шифр «Цезаря» с переменной величиной сдвига. Величину сдвига задают ключевым словом. Например, слово ВАЗА означает следующую последовательность сдвигов букв исходного текста: 3 1 9 1 3 1 9 1 и т.д.

Т.к.
В – 3-я буква алфавита
А – 1-я буква алфавита
З – 9-ая буква алфавита
А – 1-я буква алфавита

Итак, кодируем слово МИР:

  • первую букву М сдвигаем на 3 и получаем П
  • вторую букву И сдвигаем на 1 и получаем К
  • третью букву Р сдвигаем на 9 и получаем Щ


Ответ: код слова МИР – ПКЩ