Файл: Изучение основных методов кодирования данных..pdf

Таблица 3 - Некоторые ASCII-коды

Вторая часть кодовой таблицы – она считается расширением основной – охватывает коды в интервале от 128 до 255 (первый бит всех кодов 1). Она используется для представления символов национальных алфавитов (например, русского или греческого), а также символов псевдографики. Для этой части также имеются стандарты, например, для символов русского языка это КОИ–8, КОИ–7 и др [15, c. 126].

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

В настоящее время появился и находит все более широкое применение еще один международный стандарт кодировки – Unicode. Его особенность в том, что в нем использовано 16-битное кодирование, т.е. для представления каждого символа отводится 2 байта. Такая длина кода обеспечивает включения в первичный алфавит 65536 знаков. Это, в свою очередь, позволяет создать и использовать единую для всех распространенных алфавитов кодовую таблицу.

3. Азбука Морзе.

В качестве примера использования кодирования с неравной длительностью элементарных сигналов рассмотрим телеграфный код Морзе («азбука Морзе»). В нём каждой букве или цифре сопоставляется некоторая последовательность кратковременных импульсов – точек и тире, разделяемых паузами. Длительности импульсов и пауз различны: если продолжительность импульса, соответствующего точке, обозначить , то длительность импульса тире составляет 3, длительность паузы между точкой и тире , пауза между буквами слова 3, пауза между словами (пробел) – 6. Таким образом, под знаками кода Морзе следует понимать: « » – «короткий импульс + короткая пауза», «-» – «длинный импульс + короткая пауза», «0» – «длинная пауза», т.е. код оказывается троичным.

Собственный код Морзе создал в 1838 г., т.е. за длительное время до изучений относительной частоты возникновения разных букв в текстах. Вместе с тем им был конкретно выбран закон кодирования – буквы, которые попадаются чаще, должны обладать более непродолжительными кодами, чтобы свести к минимуму совокупное время передачи. Условные частоты букв английского алфавита он расценил обычным подсчетом литер в ячейках типографской наборной машины. В связи с этим самая популярная английская буква «Е» приобрела код «точка». При синтезировании кодов Морзе для букв русского алфавита учёт условной частоты букв не выполнялся, что, естественно, нарастило его избыточность. Как и в разобранных ранее вариантах кодирования, осуществим анализ избыточности. По-прежнему для комфорта сравнения данные изобразим в приведенном ниже формате. Признак конца буквы («0») в их кодах не отражается, но учтён в величине k_i – длине кода буквы I [15, c. 128].

Среднее значение длины кода K⁽³⁾ = 3,361. Полагая появление знаков вторичного алфавита равновероятным, получаем среднюю информацию на знак равной I⁽²⁾ = log₂3 = 1,585 бит. Так как для русского алфавита I₁⁽¹⁾= 4,356 бит, то:

Q^(r) = 1 – 4,356/(3,361 – 1,585)≈ 0,182

т.е. избыточность составляет около 18% (для английского языка ≈15%). Код Морзе обладал в недальнем прошлом очень обширным распространении в обстановках, когда источником и приемником сигналов считался человек (не техническое устройство) и на первый план выходила не экономичность кода, а практичность его оценки человеком.

Таблица 4 - Таблица кодов Морзе

4. Блочное двоичное кодирование.

Рассмотрим проблему рационального кодирования. Пока что оптимальный итог (минимальная избыточность) был получен при кодировании по методу Хаффмана – для русского алфавита избыточность оказалась меньше 1%. При этом указывалось, что код Хаффмана выправить нельзя. По началу данное возражает первой теореме Шеннона, заявляющей, что всякий раз можно рекомендовать метод кодирования, при котором избыточность будет сколь угодно маленькой величиной. На самом деле данное опровержение появилось из-за того, что рассматривалось алфавитное кодирование. При алфавитном кодировании передаваемое сообщение выступать в роли очередности кодов самостоятельных знаков первичного алфавита. Тем не менее вероятны варианты кодирования, при которых кодовый знак принадлежит сразу к многим буквам изначального алфавита (блок) или даже к целостному слову первичного языка. Кодирование блоков убавляет избыточность. В данном можно удостовериться на примере [15, c. 129].

Пусть имеется в наличии словарь определенного языка, охватывающий n = 16000 слов. Назначим в соответствие каждому слову размеренный двоичный код. Разумеется, длина кода может быть определена из соответствия K⁽²⁾≥log₂n≥13,97=14. Следовательно, каждому слову будет поставлена в соответствие комбинация из 14 нулей и единиц – получатся своего рода двоичные иероглифы.

Нетрудно выяснить, что при средней длине русского слова K^(r) = 6,3 буквы (5,3 буквы + пробел между словами) средняя информация на знак первичного алфавита оказывается равной I⁽²⁾=K⁽²⁾/K^(r) = 14/6,3 = 2,222 бит, что почти в 2 раза меньше, чем 4,395 бит при алфавитном кодировании. Для английского языка подобный способ кодирования дает 2,545 бит на знак. Таким образом, кодирование слов оказывается более выгодным, чем алфавитное.

Ещё более действенным станет кодирование в том случае, если первоначально ввести условную частоту явления разнообразных слов в текстах и затем применять код Хаффмана. По условным частотам 8727 более применимых в английском языке слов Шеннон, что средняя информация на знак первичного алфавита оказывается равной 2,15 бит. Вместо слов можно кодировать совокупности букв – блоки. В принципе блоки можно расценивать словами одинаковой длиной, не обладающими, однако, смыслового содержания. Удлиняя блоки и используя код Хаффмана можно достигнуть того, что средняя информация на знак кода будет сколь угодно близиться к I∞. Однако, применение блочного и словесного метода кодирования имеет свои недостатки.

1) Необходимо хранить огромную кодовую таблицу и постоянно к ней обращаться при кодировании и декодировании, что замедлит работу и потребует значительных ресурсов памяти.

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

3) Возникает проблема согласования (стандартизации) этих громадных таблиц, что непросто.

4) Алфавитное кодирование имеет то преимущество, что буквами можно закодировать любое слово, а при кодировании слов – использовать только имеющийся словарный запас.

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

Заключение

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

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

Существуют два классических метода эффективного кодирования: метод Шеннона-Фано и метод Хаффмена. Входными данными для обоих методов является заданное множество исходных символов для кодирования с их частотами; результат - эффективные коды.

Метод Хаффмена имеет два преимущества по сравнению с методом Шеннона-Фано: он устраняет неоднозначность кодирования, возникающую из-за примерного равенства сумм частот при разделении списка на две части (линия деления проводится неоднозначно), и имеет, в общем случае, большую эффективность кода.

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