Глава 3. Кодирование информации  

Информация передается в виде сообщений. Дискретная информация записывается с помощью некоторого конечного набора знаков, которые будем называть буквами, не вкладывая в это слово привычного ограниченного значения (например, «русские буквы» или «латинские буквы»). Буква в данном расширенном понимании – любой из знаков, которые некоторым соглашением установлены для общения. Например, при привычной передаче сообщений на русском языке такими знаками будут русские буквы – прописные и строчные, знаки препинания, пробел; если в тексте есть числа – то и цифры. Вообще, буквой будем называть элемент некоторого конечного множества (набора) отличных друг от друга знаков. Множество знаков, в котором определен их порядок, назовем алфавитом (например, общеизвестен порядок знаков в русском алфавите: А, Б,..., Я).

Алфавит – множество знаков, в котором определен их порядок (общеизвестен порядок знаков в русском алфавите: А, Б,..., Я). Пример:

1.     Алфавит прописных русских букв.

2.     Алфавит Морзе.

3.     Алфавит клавиатурных символов ПЭВМ IBM (русифицированная клавиатура).

4.     Алфавит знаков правильной шестигранной игральной кости.

5.     Алфавит арабских цифр.

6.     Алфавит шестнадцатиричных цифр.

7.     Алфавит двоичных цифр.

8.     Двоичный алфавит «точка, «тире».

9.     Двоичный алфавит «плюс», «минус».

10.   Алфавит прописных латинских букв.

11.   Алфавит римской системы счисления.

12.   Алфавит языка блок-схем изображения алгоритмов.

13.   Алфавит языка программирования.

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

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

Код – правило, описывающее соответствие знаков (или их сочетаний) первичного алфавита знаком (их сочетаниями) вторичного алфавита.

Кодирование – перевод информации, представленной сообщением в первичном алфавите, в последовательность кодов.

Декодирование – операция обратная кодированию.

Кодер – устройство, обеспечивающее выполнение операции кодирования.

Декодер – устройство, производящее декодирование.

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

Математическая постановка задачи кодирования:

-       А – первичный алфавит. Состоит из N знаков со средней информацией на знак I^А.

-       В – вторичный алфавит из М знаков со средней информацией на знак I^В.

-       Сообщение в первичном алфавите содержит n знаков, а закодированное – m знаков.

-       I_s(A) – информация в исходном сообщении, I_f(B) - информация в закодированном сообщении.

-       I_S(A) ≤ I_f (B) – условие обратимости кодирования, т.е не исчезновения информации.

-       n*I^А ≤ m*I^B (заменили произведением числа знаков на среднее информационное содержание знака).

-       m/n – характеризует среднее число знаков вторичного алфавита, который используется для кодирования одного знака первичного. Обозначим его К(А, В).

-       K(A, B) ≥ I^A/ I^B. Обычно К(А, В) >1.

K^min(A, B) = I^A/ I^B – минимальная длинна кода

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

Помехи в передаче информации – вполне обычное дело во всех сферах профессиональной деятельности и в быту. Один из примеров был приведен выше, другие примеры – разговор по телефону, в трубке которого «трещит», вождение автомобиля в тумане и т.д. Чаще всего человек вполне справляется с каждой из указанных выше задач, хотя и не всегда отдает себе отчет, как он это делает (т.е. неалгоритмически, а исходя из каких-то ассоциативных связей). Известно, что естественный язык обладает большой избыточностью (в европейских языках - до 7%), чем объясняется большая помехоустойчивость сообщений, составленных из знаков алфавитов таких языков. Примером, иллюстрирующим устойчивость русского языка к помехам, может служить предложение «в словох всо глосноо зомононо боквой о». Здесь 26% символов «поражены», однако это не приводит к потере смысла. Таким образом, в данном случае избыточность является полезным свойством.

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

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

Х = {x_i} – кодирующее устройство – В,

где X, В – соответственно входной и выходной алфавит. Под множеством х_i можно понимать любые знаки (буквы, слова, предложения). В – множество, число элементов которого в случае кодирования знаков числами определяется основанием системы счисления (например, т = 2). Кодирующее устройство сопоставляет каждому сообщению х_i из Х кодовую комбинацию, составленную из т_i символов множества В. Ограничением данной задачи является отсутствие помех. Требуется оценить минимальную среднюю длину кодовой комбинации.

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

Тогда:

K^min(A, B) = I^A/ log₂M = I^A

где I^A  – средняя информация на знак первичного алфавита.

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

1.  Первоначально последовательность Х = {x_i} кодируется символами из В так, что достигается максимальная пропускная способность (канал не имеет помех).

2. Затем в последовательность из В длины n вводится r символов и по каналу передается новая последовательность из n + r символов. Число возможных последовательностей длины n + r больше числа возможных последовательностей длины n. Множество всех последовательностей длины n + r может быть разбито на n подмножеств, каждому из которых сопоставлена одна из последовательностей длины n. При наличии помехи на последовательность из n + r символов выводит ее из соответствующего подмножества с вероятностью сколь угодно малой.

3. Это позволяет определять на приемной стороне канала, какому подмножеству принадлежит искаженная помехами принятая последовательность длины n + r, и тем самым восстановить исходную последовательность длины n.

Это позволяет определять на приемной стороне канала, какому подмножеству принадлежит искаженная помехами принятая последовательность длины n + r, и тем самым восстановить исходную последовательность длины n.

Эта теорема не дает конкретного метода построения кода, но указывает на пределы достижимого в создании помехоустойчивых кодов, стимулирует поиск новых путей решения этой проблемы.

1.     Способ кодирования только устанавливает факт искажения сообщения, что позволяет потребовать повторную передачу.

2.     Используемый код находит и автоматически исправляет ошибку передачи.

Особенности вторичного алфавита при кодировании:

-       Элементарные коды 0 и 1 могут иметь одинаковые длительности (t0 = t1) или разные (≠).

-       Длина кода может быть одинаковой для всех знаков первичного алфавита (код равномерный) или различной (неравномерный код)

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

Представление чисел в компьютере (равномерное алфавитное кодирование):

1.     Компьютерный алфавит С включает буквы латинского алфавита – 52 шт.

2.     Букв русского (прописные и строчные) – 66 шт.

3.     Цифры 0…9 –  10 шт.

4.     Знаки математических операций, препинания, спецсимволы – 20 штук

Итого: 148

К (С, 2) ≥ log2 148 ≥ 7,21, так как длина кода – целое число, следовательно,   К (С,2) = 8бит = 1байт.

 Именно такой способ кодирования принят в компьютерных системах. Один байт соответствует количеству информации в одном знаке алфавита при их равновероятном распределении. Это объемный способ измерения информации.

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

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

В англоязычных странах используются 26 прописных и 26 строчных букв (A … Z, a … z), 9 знаков препинания (. , : ! " ; ? ( ) ), пробел, 10 цифр, 5 знаков арифметических действий (+,-,*, /, ^) и специальные символы (№, %, _, #, $, &, >, <, |, \) – всего чуть больше 100 символов. Таким образом, для кодирования этих символов можно ограничиться максимальным 7-разрядным двоичным числом (от 0 до 1111111, в десятичной системе счисления – от 0 до 127).

Первой 7-разрядной кодовой таблицей была ASCII (American Standard Code for Information Interchange), опубликованная как стандарт в 1963 г. американской организацией по стандартизации American Standards Association (ASA), которая позднее стала именоваться ANSI (American National Standards Institute, поэтому данную кодовую таблицу называют также и ANSI). Таблица содержала 32 кода команд или управляющих символов (от 0 до 31), большая часть которых сегодня не используется, и 95 кодов (от 33 до 127) для различных знаков, достаточных для работы с английскими текстами.

Рисунок 11 - Таблица кодировки ASCII

Первоначально код обмена информации ASCII был первоначально 7 бит, N=2⁷=128 символов:

-       0…31- всевозможные управляющие  символы

-       32…127 – видимые на экране символы.

Далее он был расширен до 8 бит:

-       N=2⁸ =256 символов

-       128…255- национальные алфавиты,псевдографика

Пример, 01000001 = буква А = 65

Некоторые системы кодирования:

-       КОИ-7

-       КОИ-8

-       Windows-1251

-       ISO

-       Unicode

-       UTF-8

Кодирование различного рода информации

Кодирование текстовой информации. Если для кода символа был выбран размер I = log₂256 = 8 бит = 1 байт, то объем сообщения, содержащего N символов рассчитывается как V=8N.

Кодирование графической информации во многом зависит от того, является ли изображение растровым или векторным.

Растровое изображение представляет собой однослойную сетку точек, называемых пикселами (pixel, от англ. picture element). Код пиксела содержит информацию о его цвете.

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

Объем графического файла в битах определяется как произведение количества пикселей на разрядность цвета (битовую глубину) N*M.

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

Рисунок 12 – Кодирование звука

Для того чтобы воспроизвести закодированный таким образом звук, нужно выполнить обратное преобразование (для него служит цифро-аналоговый преобразователь – ЦАП), а затем сгладить получившийся ступенчатый сигнал.

Кодирование видеоинформации. Число кадров вычисляется как произведение длительности видеоклипа на скорость кадров, то есть их количество в 1с.

V=N*M*C*v*Dt

При разрешении 800*600 точек, разрядности цвета C=16, скорости кадров v=25 кадров/c, видеоклип длительностью 30 с будет иметь объем:

V=800*600*16*25*30=576*107(бит)=72*107(байт)=687(Мбайт)