Computer Science

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

Введение

Для того чтобы хранить и передавать информацию, её необходимо как-то зафиксировать, например записать с помощью символов (знаков) на каком-то языке.

Язык
это система знаков, используемая для хранения, передачи и обработки информации.
Естественные языки возникли в ходе развития человеческого общества (английский, русский, арабский, ...). Одно и то же слово может иметь различный смысл в зависимости от контекста, т. е. фрагмента текста, в котором оно употребляется. Например, в книге по географии слово «рукав», скорее всего, будет означать ответвление русла реки, а не деталь одежды.
Формальныые языки созданы людьми для кодирования различных видов информации. Однозначно определяется значение каждого слова, а также правила построения предложений и придания им смысла.
Вот некоторые примеры формальных языков:
• математические формулы: у = 3 sin х + 1;
• химические формулы и правила записи реакций: 2Н2 + О2 = 2Н2О;
• системы счисления (правила записи чисел с помощью специальных знаков — цифр): 2023, MMXXIII, 11111100111;
• язык записи шахматных партий: 1. е2-е4 е7-е5...;
Кодирование
преобразование информации без изменения ее содержания в другой вид с помощью определенного кода (из одной формы представления в другую). Если код секретный, то это шифрование. Декодирование — это восстановление информационного сообщения из последовательности кодов.
Код
набор правил преобразования для кодирования, перевода на другой язык.

Например, если эти предложения написать на английском, то это пример кодирования текста. Для человека преобразованная информация выглядит непривычно:

Чтобы передать информацию, ее необходимо закодировать согласно природе канала передачи. В компьютере носителями информации являются электрические или магнитные сигналы, которые могут иметь только два значения: 0 — отключено (нет тока) или 1 — включен (есть ток). С помощью 0 и 1 кодируется любая информация, которую обрабатывает компьютер.

Как правило, представления сообщения подбираются так, чтобы его передача была как можно быстрее и надежнее, а его обработка была как можно более удобной для адресата.
Одно и то же сообщение можно кодировать по-разному. Одной из систем кодирования является азбука. Можно кодировать и звуки. Одна из таких систем кодирования — ноты. Хранить можно не только текстовую и звуковую информацию. В виде кодов хранятся и изображения. Если рассмотреть рисунок через увеличительное стекло, то видно, что он состоит из точек. Координаты каждой точки можно запомнить в виде чисел. Цвет каждой точки также можно запомнить в виде чисел. Такие числа могут храниться в памяти компьютера и передаваться на расстоянии.

продолжение...

Для представления и обработки информации в компьютере используют двоичные коды, содержащие только два символа — 0 и 1.
Бит — наименьшая единица двоичного кода.
Байт — это последовательность из 8 бит.

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

Нам известно, что для обозначения количества, мы пользуемся цифрами, для обозначения звуков на письме — буквами. Можно сказать, что цифры и буквы — это коды.

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

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

Итог:
Люди издавна занимались кодированием информации. Сначала это были закодированные с помощью палочек числа, буквы и звуки, потом — слова с помощью иероглифов или рун, затем придумали алфавит. Каждый язык на земле – это отдельный способ кодирования информации. Например, слово «книга» на разных языках звучит по-разному. Сэмюель Морзе разработал азбуку, которую позже назвали в его честь «азбукой Морзе». Ею до сих пор активно пользуются моряки.
В компьютере для передачи информации используют только два числа – 1 и 0. С их помощью кодируется вся информация: и текст, и графика, и звук. Самая маленькая единица измерения информации – бит. Также используют байты, килобайты, мегабайты, гигабайты.


Очень полезные уроки:


Равномерное кодирование

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

Чаще всего используется равномерный код, когда все символы исходного сообщения кодируются с помощью одинакового количества двоичных знаков. Каждый знак соответствует выбору одного из двух вариантов (0 или 1), поэтому несёт 1 бит информации. Длина кода i определяется количеством вариантов, которые нужно закодировать. 2i ≥ N - количества символов.

Пример: кодируем слово ГИГАБАЙТ

Заглянем втаблицу ASCIIи найдем коды символов. 1 символ содержит 8 бит = 1 байт информации.

Символы А Б Г И Й Т
Кодовое слово 11000000 11000001 11000011 11001000 11001001 11010010

8 символов • 8 бит = 64 бит длина сообщения.

Если учесть, что использовано 6 символов и закодировать их двоичным кодом по 3 бит, то 3•8 = 24 бит длина слова. (23 = 8 разных двоичных чисел)

Символы А Б Г И Й Т
Кодовое слово 000 001 010 011 100 101

Запомнили число 24 bit!

Неравномерное кодирование

Мультики:
Метод Шеннона-ФаноВАЖНО!
Кодирование источника (видео 4)KhanAcademyRussian

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

Неравномерный код — это код, в котором кодовые слова имеют разную длину.

Применим неравномерный код для ГИГАБАЙТ. Для этого составим таблицу

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

Создаем двоичное дерево

и таблицу

Символы А Г И Б Й Т
Кодовое слово 00 01 100 101 110 111

Длина слова ГИГАБАЙТ 4•2 + 4•3 = 8 + 12 = 20 бит

01100010010100110111

Слово Г И Г А Б А Й Т
Код 01 100 01 00 101 00 110 111

При равномерном кодировании было 3•8 = 24 бит

Вывод: код уменьшили в 1,2 раза. Это очень хороший результат! Мы молодцы!


Однозначное декодирование

Есть таблица
Символ А Г Р
Код 0 1 10

Попробуйте декодировать информацию

1010100

Вот варианты:
• Р10 Г1 А0 Г1 А0 А0
• Г1 А0 Р10 Г1 А0 А0
• и еще много других.

На самом деле было закодировано слово ГАГАРА (это птица 😇)

Код однозначно декодируемый
если любое кодовое сообщение можно расшифровать единственным способом (однозначно).

Сказанное означает, что представленный выше код НЕ является однозначно декодируемым.

А кодовая таблица для слова ГИГАБАЙТ допускает только однозначное декодирование!


Ответ на вопрос "Почему?" ищем в мультиках:

Ро́берт Ма́рио Фа́но

Как же определить, является ли заданный код однозначно декодируемым?

Условие Фано (прямое)
Никакое кодовое слово не совпадает с началом другого кодового слова.

Коды, для которых выполняется условие Фано, называют префиксными (префикс слова — это его начальный фрагмент). Все сообщения, закодированные с помощью префиксных кодов, декодируются однозначно.

Префиксные коды имеют важное практическое значение — они позволяют декодировать символы полученного сообщение по мере его получения, не дожидаясь, пока всё сообщение будет доставлено получателю.

Условие Фано (обратное)
никакое кодовое слово не совпадает с окончанием другого кодового слова.

Коды, для которых выполняется обратное условие Фано, называют постфиксными (постфикс или суффикс слова — это его конечный фрагмент). В этом случае тоже обеспечивается однозначное декодирование.

Сообщение декодируется однозначно, если для используемого кода выполняется прямое или обратное условие Фано.

Условие Фано (и обратное условие Фано) — это достаточное, но не необходимое условие однозначной декодируемости. Это значит, что:
• для однозначной декодируемости достаточно выполнение хотя бы одного из двух условий, или прямого, или обратного;
• могут существовать коды, для которых не выполняется ни прямое, ни обратное условие Фано, но они, тем не менее, обеспечивают однозначное декодирование.

Наиболее интересен второй вывод, который сразу вызывает два вопроса:
1) что это за коды? и 2) как в общем случае установить, что код декодируется однозначно?
И тут вы отправляетесь в самостоятельное плавание в океане информации...

Задачи для решения и шпаргалка для решения