1.6 Обработка информации
Кодирование. Код Морзе. Архиваторы. Шифрование. Арифметические операции и операнды.
Преобразованием или обработкой информации называется целенаправленное изменение содержащего ее сообщения. Преобразование, не изменяющее содержание сообщений, обычно называется кодированием. Широко распространенным примером кодирования является перевод с одного языка на другой.
Другое важное применение кодирования относится к технике и связано с сокращением объема памяти, необходимого для хранения нужной информации, или времени, необходимого для ее передачи по линии связи. По-видимому, впервые это удалось сделать американскому изобретателю и художнику С. Морзе. До Морзе все передаваемые по телеграфу символы кодировались последовательностями одинаковой длины, состоящими из электрических сигналов различной длительности. Короткий сигнал назвали точкой, а сигнал, продолжительность которого была в три раза больше, стал называться тире. Такие последовательности в теории кодирования принято называть кодовыми словами. Легко видеть, что количество различных кодовых слов длины выражается числом . Поэтому при кодировании букв, образующих алфавит, длина кодовой последовательности одной буквы должна удовлетворять неравенству . Из него следует, что при алфавите, например, из букв .
Морзе предложил использовать для кодирования букв кодовые слова разной длины. Чем реже буква появлялась в тексте, тем длиннее должно быть для нее кодовое слово. Предположим, что в длинном тексте буква с номером повторяется с относительной частотой . Доказано, что средняя длина кодового слова при кодировании алфавита из букв подсчитывается по формуле
.
Наибольшее значение , равное , соответствует случаю, когда частота появления всех букв одинакова, то есть , . В остальных случаях (когда буквы имеют разную частоту повторения) .
Применим сформулированный результат для кодирования сообщений на русском языке. Наибольшая относительная частота появления буквы в тексте, равная 0.175, отмечена у пробела. За ним следует буква ’О’ с относительной частотой 0.090. На последнем месте с относительной частотой 0.002 находится буква ’Ф’. Средняя длина кодовой последовательности для буквы на основании приведенной формулы составляет двоичных символов. С другой стороны, при равномерном кодировании, когда каждая из букв кодируется последовательностью одной и той же длины, ее длина равняется 5. Следовательно, использование кода Морзе позволяет сократить объем памяти или время передачи сообщения на 12%.
Различные способы кодирования информации широко применяются в настоящее время для сокращения объема памяти необходимой для хранения информации в запоминающих устройствах компьютеров и для сокращения времени ее передачи по компьютерным сетям. В качестве хорошо известных примеров можно назвать популярные приложения RAR и ZIP, обеспечивающие кодирование и декодирование (восстановление) информации.
Очевидно, что сообщение, отправленное конкретному адресату, может оказаться доступным и другими лицами, которым удалось получить доступ к каналу связи. Особенно легко это сделать при использовании радиосвязи. Для защиты содержания передаваемого сообщения его перед отправкой в канал связи подвергают определенному преобразованию, которое называют шифрованием. Целью такого преобразования является приведение сообщения к виду, затрудняющему получение содержащейся в нем информации для посторонних лиц. Адресат, получив зашифрованное сообщение, выполняет над ним обратное преобразование, которое называется дешифрированием, и узнает содержащуюся в нем информацию. Очевидно, что шифрование так же является кодированием.
Другими примерами очень важных и хорошо изученных способов обработки информации являются арифметические операции над числами. С точки зрения сформулированного выше определения обработки информации, сложение двух чисел A и B необходимо рассматривать как замену сообщения, содержащего числа A, B и символ +, на сообщение, содержащее сумму A+B. Числа, над которыми выполняются операции, принято называть операндами. Очевидно, что один и тот же результат можно получить, выполняя операции над различными парами операндов. Это означает, что арифметические операции не являются кодированиями.