Файл: Методы кодирования данных (Программная реализация алгоритма кодирования Хаффмана).pdf

ВВЕДЕНИЕ

Необходимость кодирования данных появилась раньше, чем появился первый персональный компьютер.

Для любого метода кодирования характерно наличие начальных данных, наименьшая единица которых – бит, а наибольшая - несколько бит, байт или несколько байт.

Методику, изобретенную Дэвидом Хаффманом, можно без преувеличения назвать популярнейшим способом кодировки. Данная методика — это простейший алгоритм, призванный создавать кодировки с изменчивой длиной, имеющие самое малое среднее протяжение. Многие приложения для ПК, сжимающие информацию, основываются на данной методике. Отдельные приложения полностью используют методику, а другие пользуются методом частично на разных уровнях. Методика Хаффмана позволяет достичь идеала в сжатии данных и довести их до энтропического состояния при равенстве символьных данных степени с отрицательным значением «два». Данная методика использует также выстраивание древа кодировки от низа до верха. После этого производится скольжение в нижний уровень, чтобы создать личные кодировки, начиная с правой стороны в сторону левой.

Объект исследования: процесс кодирования данных.

Предмет исследования: методы кодирования данных.

Цель курсовой работы – анализ методов кодирования данных.

Для достижения поставленной цели требуется решить следующие задачи:

1) рассмотреть теоретические основы кодирования данных;

2) рассмотреть методы кодирования данных;

3) разработать программу для демонстрации метода кодирования.

1. Теоретические основы кодирования данных

1.1 Основные понятия кодирования данных

Остановимся на базовых понятиях, которые имеют отношение к кодированию данных. С целью отправки в канал связи информация трансформируется в сигнал. Символы, которые используются в формировании данных, формируют первичный алфавит. Любому символу соответствует определённая степень вероятности того, что он будет содержаться в сообщении. Для любой переданной информации всегда имеется некоторый сигнал, который является строгой последовательностью кодовых комбинаций.

Кодирование представляет собой трансформацию информации в комбинацию кода.

Под кодом понимается структура соответствия передаваемой информации и сигналов.

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

Алфавит – совокупность допустимых частей кода.

X = {xi}, где i = 1, 2,..

Основание кода – это число возможных его элементов. Если код состоит только из нулей и единиц, то основание кода равно двум.

Кодовая комбинация – итоговая комбинация символов алфавита. Значность комбинации – количество её элементов.

Объём кода – количество отличающихся кодовых комбинаций.

Кодирование может быть использовано для решения следующих задач:

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

2) Снижение влияния помех в процессе передачи данных.

Согласно данным задачам, теория кодирования имеет две главные отрасли развития:

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

2. Устойчивость к помехам. Происходит поиск комбинаций, которые увеличивают точность передачи данных в каналах, которые имеют помехи.

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

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

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

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

Рассмотренные примеры подтверждают одно очень важное правило: кодирование одних и тех же данных возможно с применением различных методов. На применение того или иного метода влияют различные условия, например, задача кодирования или имеющиеся средства.

Также выбор метода кодирования данных может зависеть от того, каким образом предполагается осуществление обработки. Продемонстрируем это на примере представления чисел. Применив латинские символы, имеется возможность написать число «сорок девять». Применив десятичную систему исчисления, это же число будет написано так: «49». Использование десятичной системы исчисления является более коротким и удобным для того, чтобы проводить подсчёты. Как более просто выполнять вычисления: «сорок девять разделить на семь» или «49/7»? Очевидно — второй способ является более удобным.

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

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

Шифрование – трансформация читаемой формы документа в зашифрованную. Дешифрование является обратной процедурой, при которой происходит восстановление читаемой формы. Процесс шифрования отличается от кодирования тем, что при шифровании используется секретный метод, который знают только источник и адресат. Разработкой методов шифрования занимается наука криптография.

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

Для примера берем стандартные опыты «А» и «В»; усложненный опыт «А/В», в котором идет одновременное исполнение опытов «А» и «В». Опыт «А» включает в себя «х» результатов с одинаково точной вероятностью. «В», в свою очередь, включает в себя наличие только одного результата с такой степенью. Таким образом, становится очевидным факт превосходства неопределенного значения у опыта «А/В» над опытом «А», так как в данном опыте появляются еще и неопределенные вероятности от опыта «В». То есть, градация неопределенного состояния опыта «А/В» — это результат сложения неопределенных значений опытов «А» и «В», а именно:

.

Условиям:

,

при удовлетворяет только одна функция - :

.

Рассмотрим эксперимент С, который содержит эксперименты и имеет вероятности . Общая неопределенность для эксперимента С будет:

Это последнее число будем называть энтропией эксперимента А, которое будет отражаться как Н(А).

Если «алфавит» содержит количество символов x, а количество задействованных элементарных сигналов – y, то в независимости от того, какой метод кодирования применяется, среднее количество элементарных сигналов, которое приходится на один символ алфавита, всегда будет больше или равным:

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

Остановимся на простом случае данных, которые были записаны некоторыми x «символами», вероятность появления которых в том или ином месте целиком характеризуется вероятностями р1, р2, … …, рх, где, р1 + р2 + … + рх = 1, при котором степень вероятности pi проявления i-й буквы в произвольном месте будет одна и та же, независимо от того, какие символы были во всех других местах. На практике, как правило, бывает по-другому, если взять русский язык, то на вероятность появления буквы сильно влияет предыдущая буква. Но если мы будем учитывать, как буквы зависят друг от друга, то дальнейшие рассмотрения станут очень сложными, но не окажут влияния на будущий результат.

Сделаем остановку на кодировках с двоичными системами. В таких системах обычно очень простое суммирование итогов кодировок, использующих неопределенную сумму стандартных сигнализаций. Можно рассмотреть простейшее событие, в пределах которого каждая кодировка — числовое последовательное выражение, состоящее из чисел «1» и «0». Эти числа заменяют символику события. При данном обозначении любая сумма с двоичным кодом использует отдельную методику, определяющую точную задуманную цифру, являющуюся, в свою очередь, равной «х» или меньше этого значения. При этой методике применяется некоторое количество вопросов с ответами только ДА/НЕТ (1/0). Все это в сумме заставляет применять двоичную кодировку.

Когда вероятные значения «Р1», «Р2», «Рх» указаны точно, идеальной кодировкой для отсылки сообщений с множеством символов является та кодировка, которая обладает самым меньшим количеством заданных вопросов при точных вероятных значениях «х» (двоичная символика или стандартная сигнализация).

Прежде всего, средняя сумма двоичной стандартной сигнализации сообщений с кодировкой в отношении единичного значения в стандартном событии в любом случае превышает или равняется «Н» (Н = - p1 log p1 – p2 log p2 - .. - pn log pn — энтропическое свойство опыта, распознающего единичные символы события). Таким образом подводится итог: при применении любой методики кодировки обязательно нужно минимально «ХН» символов с двоичным значением (при передаче данных из «Х» значений).

1.2 Классификация назначения и способы представления кодов

Классификация кодировок производится с использованием следующих критериев:

1. Основа — количество алфавитных значений, букв. Различаются бинарный и небинарный типы (m=2/m№2).

2. Протяженность суммы кодировки. Различаются равные (длина любой комбинации одинакова) и неравные (длина различается).

3. Методика отправки. Различаются постепенная и параллельная методики.

4. Степень устойчивости к помехам. Простой уровень: для отправки сообщений используются разные кодировки; коррекционный уровень — отправка сообщений осуществляется заданными кодировками.

5. По использованию и предназначению. Кодировки внутреннего характера (такие коды свойственны разным системам; сюда можно отнести кодировки машинного типа и кодировки, использующие двоичные, десятичные и прочие системы позиционного типа). Наиболее распространенной кодировкой для электронно-вычислительных машин можно назвать кодировку двоичного типа. Данный код помогает создать аппарат, которые может осуществлять обработку, передачу и хранение информации. В результате применения данной кодировки, аппараты становятся максимально надежными. При этом сложность операций сводится к минимуму. В случае объединения информации двоичного типа (по 4) происходит превращение в кодировку шестнадцатеричного типа. Такой код обладает удобством в использовании с архитектурным строением электронно-вычислительных машин, работающих в 8-битной системе.