Представление информации, языки, кодирование

Письменность и кодирование информации Под словом «кодирование» понимают процесс представления информации, удобный для ее хранения и/или передачи. Декодирование – это обратный процесс.

Цели и способы кодирования Может существовать много способов кодирования одного и того же текста на одном и том же языке. Русский текст - 1) можно записывать с помощью русского алфавита; 2) можно использовать латинский алфавит; 3) стенографировать. Для кодирования одной и той же информации могут быть использованы разные способы; их выбор зависит от цели кодирования, условий, имеющихся средств.

Выбор способа кодирования информации может быть связан с предполагаемым способом ее обработки. Пример. Число мы можем записать: 1)«тридцать пять». 2)35. Какая запись удобнее для выполнения расчетов: 1)«тридцать пять умножить на сто двадцать семь» или 2)«35 х 127»? Первая запись использовала естественный русский язык, вторая формальный язык математики. Переход от представления на естественном языке к представлению на формальном языке можно также рассматривать как кодирование. Широко используемыми в информатике формальными языками являются языки программирования.

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

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

Равномерный телеграфный код был изобретен французом Жаном Морисом Бодо в конце XIX века. В нем использовалось всего два вида сигналов. В коде Бодо длина кодов всех символов алфавита одинакова и равна пяти. В таком случае не возникает проблемы отделения букв друг от друга: каждая пятерка сигналов это знак текста. Код Бодо это первый в истории техники способ двоичного кодирования информации. Из курса информатики основной школы вам известно, что в современных компьютерах для кодирования текстов также применяется равномерный двоичный код.

Решение упражнений 1. Валя шифрует русские слова (последовательности букв), записывая вместо каждой буквы ее код. Некоторые цепочки можно расшифровать не одним способом. Например, может означать не только СКА, но и СНК. Даны три кодовые цепочки: Найдите среди них ту, которая имеет только одну расшифровку, и запишите в ответе расшифрованное слово. Ответ НОС

2. От разведчика была получена следующая шифрованная радиограмма, переданная с использованием азбуки Морзе: При передаче радиограммы было потеряно разбиение на буквы, но известно, что в радиограмме использовались только следующие буквы: Расшифруйте радиограмму. Запишите в ответе расшифрованную радиограмму. Ответ АДЛТДТАТ

3. Ваня шифрует русские слова, записывая вместо каждой буквы ее номер в алфавите (без пробелов). Номера букв даны в таблице. Некоторые шифровки можно расшифровать несколькими способами. Например, может означать «ВАЛЯ», может – «ЭЛЯ», а может – «ВААВВВ». Даны четыре шифровки: Только одна из них расшифровывается единственным способом. Найдите ее и расшифруйте. Получившееся слово запишите в качестве ответа. Ответ БИТЬ

4. Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А– 00, Б–010, В–011, Г–101, Д–111. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по- прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. Выберите правильный вариант ответа. 1) для буквы Б – 01 2) это невозможно 3) для буквы В – 01 4) для буквы Г – 01

Кодирование может быть равномерное и неравномерное; при равномерном кодировании все символы кодируются кодами равной длины; при неравномерном кодировании разные символы могут кодироваться кодами разной длины, это затрудняет декодирование. Закодированное сообщение можно однозначно декодировать с начала, если выполняется условие Фано: никакое кодовое слово не является началом другого кодового слова. Закодированное сообщение можно однозначно декодировать с конца, если выполняется обратное условие Фано: никакое кодовое слово не является окончанием другого кодового слова. Решение задачи

Решение: для однозначного декодирования достаточно, чтобы выполнялось условие Фано или обратное условие Фано; проверяем последовательно варианты 1, 3 и 4; если ни один из них не подойдет, придется выбрать вариант 2 («это невозможно»); проверяем вариант 1: А–00, Б–01, В–011, Г–101, Д–111. «прямое» условие Фано не выполняется (код буквы Б совпадает с началом кода буквы В); «обратное» условие Фано не выполняется (код буквы Б совпадает с окончанием кода буквы Г); поэтому этот вариант не подходит; проверяем вариант 3: А–00, Б–010, В–01, Г–101, Д–111. «прямое» условие Фано не выполняется (код буквы В совпадает с началом кода буквы Б); «обратное» условие Фано не выполняется (код буквы В совпадает с окончанием кода буквы Г); поэтому этот вариант не подходит; проверяем вариант 4: А–00, Б–010, В–011, Г–01, Д–111. «прямое» условие Фано не выполняется (код буквы Г совпадает с началом кодов букв Б и В); но «обратное» условие Фано выполняется (код буквы Г не совпадает с окончанием кодов остальных буквы); поэтому этот вариант подходит; правильный ответ – 4.

5. По каналу связи передаются сообщения, содержащие только 4 буквы Э, Ю, Я, Ы. Для передачи сообщений нужно использовать неравномерный двоичный код, допускающий однозначное декодирование. В любом сообщении больше всего букв Я, следующая по частоте буква Ю, затем Э. Буква Ы встречается реже, чем любая другая. Какой из перечисленных ниже кодов нужно использовать, чтобы передаваемые закодированные сообщения были как можно более короткими? 1) Э 0, Ю 1, Я 00, Ы – 11 2) Я 1, Ю – 0, Э 01, Ы 10 3) Э 1, Ю 01, Я 001, Ы 000 4) Я 0, Ю 11, Э 101, Ы – 100 Решение задачи

Решение. Допускают однозначное декодирование: 3) Э 1, Ю 01, Я 001, Ы 000 4) Я 0, Ю 11, Э 101, Ы – 100 Обозначим буквой а – частоту буквы Я, b – частоту буквы Ю, с – частоту буквы Э, d – частота буквы Ы. L 3 =3a+2b+с+3d L 4 =a+2b+3c+3d L 3 -L 4 =2a-2c 0, следовательно L 4 – меньше, т.е. код 4 более экономичный.