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

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

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

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

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

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

Задача: В некотором сообщении используются только буквы А, Б, В, при этом чаще всего встречается буква А, а реже всего - буква В. Необходимо составить для этих букв коды наименьшей длины.

Решение: Строим дерево Фано.

Дерево Фано АБВ

Так как буква А встречается чаще всего, чтобы код был наименьшей длины, ветвь 0 из вершины сразу завершаем этой буквой. Из узла ветви 1 строим ветви 0 и 1, которые завершаем буквами Б и В.

Дерево Фано. коды

Записываем получившиеся коды: А - 0, Б - 10, В - 11

Кодирование текста

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

В современных системах широкое распространение получила шестнадцатиразрядная кодировка Unicode. Младшие 128 кодов в этой кодировке соотвествуют таблице ASCII, а остальные коды предзначены для кодирования символов национальных языков.

Кодирование изображения

Возьмем к примеру небольшое черно-белое изображение:

Кошка

Представим, что это изображение разлиновали вертикальными и горизонтальными линиями, иначе говоря, наложили на нее мелкую сетку (растр):

Растровое изображение кошки

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

Если для пикселя использовать не один бит, а восемь, то можно закодировать цветное изображение, где каждый пиксель, может быть окрашен в один из 256 цветов. Количество бит, предусмотренных для пикселя называется глубиной цвета. А ширина и высота изображения в пикселях - разрешающей способностью.

В современных компьютерных системах для пикселя отводят 3 байта, один байт для каждого из основных цветов: красного, зеленого и синего. То есть 24 бита обеспечивают представление 22416 777 216 цветов.

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

Задача: Какой объем видеопамяти в байтах требуется для хранения растрового изображения, занимающего весь экран монитора с разрешающей способностью 640×480 пикселей, если используется палитра из 65536 цветов?

Решение: Глубина цвета составляет log265536 = 16 бит. Следовательно для хранения одно пикселя требуется 2 байта. Объем видеопамяти: 640 ⋅ 480 ⋅ 2 = 614400 байт.

 Кодирование звуковой информации

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

Кодирование звукового сигнала

Частота, с которой производится измерение сигнала, называется частотой дискретизации. Для качественного кодирования по теореме Найквиста эта частота должна быть в два раза выше частоты кодируемого сигнала. Так как человек слышит звук частотой до 20 кГц, то достаточно кодировать его частотой свыше 40 кГц. К примеру, на компакт-дисках применяется частота дискретизации 44 кГц, а для человеческого голоса при кодировании для передачи по каналам связи достаточно 8 кГЦ. 

Для каждого отсчета при измерения амплитуды сигнала применяется его квантование, то есть значению амплитуды ставится в соответствие стандартный уровень в зависимости от того, какое количество этих уровней (шагов квантования) выбрано. Количество бит, необходимых для обеспечения квантования называется глубиной кодирования. Естественно, что квантование производится с некоторой погрешностью, но она тем ниже, чем больше глубина кодирования.

Итак, частота дискретизации при кодировании означает количество отсчетов в секунду. Частота 44 кГц - это 44000 отсчетов в секунду. Чтобы вычислить объем информации в битах, необходимый для кодирования звукового сигнала нужно частоту дискретизации умножить на глубину кодирования и на количество секунд, в течении которого сигнал кодируется. Если каналов звукового сигнала больше чем один, то полученный объем надо умножить еще и на количество каналов, например, на 2 при стерео-звуке.

Задача: Сколько байтов требуется для кодирования 1 минуты речи с частотой дискретизации 8 кГц и глубиной кодирования 10 бит.

Решение: Так как в минуте 60 секунд, то требуемый объем 8000 ⋅ 60 ⋅ 10 =  4800000 бит. Делим на 8, получаем 600000 байтов.

Скорость передачи информации

Каналы связи для передачи информации имеют ограничение скорости (пропускную способность). Это ограничение связано с физическими свойствами аппаратуры.

Зная пропускную способность канала можно вычислить объем передаваемой информации за какое-то время.

Задача: Скорость передачи данных (пропускная способность) через ADSL─соединение равна 64000 бит/c. Передача файла через это соединение заняла 30 секунд. Определить размер файла в байтах.

Решение: 640000 ⋅ 30 = 1920000 бит. переведем в байты, 1920000 : 8 =  240000 байт.

 

Задачи для самостоятельного решения