Файл: Методы кодирования данных (Ключевые понятия кодирования данных).pdf

ВВЕДЕНИЕ

Процесс кодирования данных - проблема, возникшая достаточно давно, намного раньше, чем история развития вычислительной техники, которая в основном всегда шла синхронно с историей развития проблемы сжатия и шифровки данных [20, c.71].

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

Например, кодирование Хаффмана представляет простой алгоритм для построения кодов переменной длины, обладающих минимальной средней длиной. Данный алгоритм является довольно распространенным и представляет собой основу множества компьютерных программ сжатия текстовых и графических данных. Некоторые из них применяют именно алгоритм Хаффмана, а другие берут его в качестве одного из этапов многоуровневого процесса сжатия. Метод Хаффмана осуществляет идеальное сжатие (т.е. сжимает данные до их энтропии), если вероятности символов точно равны отрицательным степеням числа 2. Алгоритм начинает строить кодовое дерево снизу вверх, далее скользит вниз по дереву, чтобы построить каждый индивидуальный код справа налево (от наиболее младшего бита к наиболее старшему). Начиная с работ Д. Хаффмана 1952 г., данный алгоритм представляет собой предмет множества исследований [1, c.14].

Коды Хаффмана изучаются во всех технических ВУЗах мира и, помимо всего прочего, включены в программу для углубленного изучения информатики в школе.

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

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

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

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

Для реализации поставленной цели необходимо выполнить ряд задач, а именно:

1. рассмотреть ключевые понятия и принципы кодирования данных;
2. осуществить сравнительный анализ методов кодирования данных;

3) исследовать метод кодирования Хаффмана;

4) разработать алгоритмы и программу для реализации программного продукта «Код Хаффмана» с применением современной технологии программирования;

5) представить пример листинга.

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

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

1.1 Ключевые понятия кодирования данных

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

Кодирование - это преобразование сообщений в сигнал, т.е. преобразование сообщений в кодовые комбинации.

Код - система соответствия между элементами сообщений и кодовыми комбинациями [2, c.24].

Кодер - устройство, реализующее кодирование.

Декодер - устройство, реализующее обратную операцию, т.е. преобразование кодовой комбинации в сообщение.

Алфавит - множество возможных элементов кода, т.е. элементарных символов (кодовых символов) X = {x_i}, где i = 1, 2,..., m [2, c.31].

Количество элементов кода m является его основанием. Для двоичного кода x_i = {0, 1} и m = 2. Конечная последовательность символов такого алфавита именуется кодовой комбинацией (кодовым словом). Число элементов в кодовой комбинации n именуется значностью (длиной комбинации). Число разных кодовых комбинаций (N = mn) именуется объемом или мощностью кода [3, c.17].

Цели кодирования:

1) увеличение эффективности передачи данных благодаря достижению максимальной скорости их передачи;

2) улучшение помехоустойчивости при передаче данных.

В соответствии с данными целями теория кодирования развивается в двух ключевых направлениях, а именно:

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

2. Теория помехоустойчивого кодирования занимается поиском кодов, повышающих достоверность передачи данных в каналах с помехами [19, c.54].

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

Декодирование — процесс обратного преобразования кода к форме исходной символьной системы, т.е. получение исходного сообщения. Например: перевод с азбуки Морзе в письменный текст на русском языке [4, c.56].

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

Способ кодирования одного и того же сообщения может отличаться. Так, русский текст мы привыкли записывать при помощи русского алфавита. Но то же самое можно сделать, применяя английский алфавит [4, c.59]. Иногда так приходится поступать, посылая SMS по мобильному телефону, где нет русских букв, или отправляя электронное письмо на русском языке из-за границы, если на компьютере нет русифицированного программного обеспечения. Например, фразу: «Здравствуй, дорогой Саша!» приходится писать так: «Zdravstvui, dorogoi Sasha!».

Есть и иные способы кодирования речи. Например, стенография — быстрый способ записи устной речи. Ею владеют лишь немногие специально обученные люди — стенографисты. Стенографист успевает записывать текст синхронно с речью говорящего человека. В стенограмме один значок обозначал целое слово или словосочетание. Расшифровать (декодировать) стенограмму может только стенографист [18, c.44].

Вышеуказанные примеры иллюстрируют следующее важное правило: для кодирования одних и тех же данных могут применяться различные способы; их выбор находится в зависимости от многих обстоятельств: цели кодирования, условий, имеющихся средств [5, c.40]. Если необходимо записать текст в темпе речи — применяем стенографию; если нужно передать текст за границу — применяем английский алфавит; если требуется представить текст в виде, понятном для грамотного русского человека, — записываем его по правилам грамматики русского языка.

Еще одно важное обстоятельство: выбор способа кодирования данных может быть связан с предполагаемым способом ее обработки. Покажем это на примере представления чисел — количественной информации. Применяя русский алфавит, можно записать число «тридцать пять». Применяя же алфавит арабской десятичной системы счисления, пишем: «35». Второй способ не только короче первого, но и удобнее для осуществления вычислений. Какая запись удобнее для осуществления расчетов: «тридцать пять умножить на сто двадцать семь» или «35 х 127»? Очевидно — вторая [17, c.61].

Однако если важно сохранить число без искажения, то его лучше записать в текстовой форме. Например, в денежных документах нередко сумму записывают в текстовой форме: «триста семьдесят пять руб.» вместо «375 руб.». Во втором случае искажение одной цифры изменит все значение. При применении текстовой формы даже грамматические ошибки могут не изменить смысла. Например, малограмотный человек написал: «Тристо семдесять пят руб.». Однако смысл сохранился.

Иногда появляется потребность засекречивания текста сообщения или документа для того, чтобы его не смогли прочитать те, кому не положено. Это называется защитой от несанкционированного доступа. В такой ситуации секретный текст шифруется. Шифрование представляет собой процесс превращения открытого текста в зашифрованный, а дешифрование — процесс обратного преобразования, когда восстанавливается исходный текст. Шифрование — это тоже кодирование, но с засекреченным методом, известным лишь источнику и адресату. Методами шифрования занимается наука криптография [6, c.48].

Пусть имеется сообщение, записанное с помощью некоторого «алфавита», содержащего n «букв». Нужно «закодировать» это сообщение, т.е. указать правило, сопоставляющее каждому такому сообщению определенную последовательность из t различных «элементарных сигналов», составляющих «алфавит» передачи. Мы будем считать кодирование тем более выгодным, чем меньше элементарных сигналов приходится затратить на передачу сообщения. Если считать, что каждый из элементарных сигналов продолжается одно и то же время, то наиболее выгодный код даст возможность затратить на передачу сообщения меньше всего времени [6, c.71].

Главным свойством случайных событий является отсутствие полной уверенности в их наступлении, создающее известную неопределенность при выполнении связанных с данными событиями опытов. Однако совершенно ясно, что степень такой неопределенности в разных ситуациях будет абсолютно различной. Для практики важно уметь численно оценивать степень неопределенности самых разнообразных опытов, чтобы иметь возможность сравнить их с этой стороны. Рассмотрим два независимых опыта и , а также сложный опыт , состоящий в одновременном выполнении опытов и . Пусть опыт имеет k равновероятных исходов, а опыт имеет l равновероятных исходов [16, c.31]. Очевидно, что неопределенность опыта больше неопределенности опыта , так как к неопределенности здесь добавляется еще неопределенность исхода опыта . Естественно считать, что степень неопределенности опыта равна сумме неопределенностей, характеризующих опыты и, т.е.

Условиям:

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

log(kl)=log(k)+log(l).

Рассмотрим опыт А, состоящий из опытов A₁, A₂,…,A_k и имеющих вероятности p(A₁), p(A₂),…,p(A_k). Тогда общая неопределенность для опыта А будет равна:

-p(A₁)logp(A₁)-p(A₂)logp(A₂)-…-p(A_k)logp(A_k)

Это последнее число будем называть энтропией опыта и обозначать через . [15, c.39]

Если число букв в «алфавите» равно n, а число используемых элементарных сигналов равно m, то при любом методе кодирования среднее число элементарных сигналов, приходящихся на одну букву алфавита, не может быть меньше чем log(n)/log(m); однако он всегда может быть сделано сколь угодно близким к этому отношению, если только отдельные кодовые обозначения сопоставлять сразу достаточно длинными «блоками», состоящими из большого числа букв [7, c.84].

Мы рассмотрим здесь только простейший случай сообщений, записанных при помощи некоторых n «букв», частоты проявления которых на любом месте сообщения полностью характеризуется вероятностями р₁, р₂, … …, р_n, где, разумеется, р₁ + р₂ + … + р_n = 1, при котором вероятность p_i проявления i-й буквы на любом месте сообщения предполагается одной и той же, вне зависимости от того, какие буквы стояли на всех предыдущих местах, т.е. последовательные буквы сообщения независимы друг от друга [7, c.91]. На самом деле в реальных сообщениях это чаще бывает не так; в частности, в русском языке вероятность появления той или иной буквы существенно зависит от предыдущей буквы. Однако строгий учет взаимной зависимости букв сделал бы все дельнейшие рассмотрения очень сложными, но никак не изменит будущие результаты.

Будем пока рассматривать двоичные коды; обобщение полученных при этом результатов на коды, использующие произвольное число t элементарных сигналов, является, как всегда, крайне простым. Начнем с простейшего случая кодов, сопоставляющих отдельное кодовое обозначение – последовательность цифр 0 и 1 – каждой «букве» сообщения [10, c.84]. Каждому двоичному коду для n-буквенного алфавита может быть сопоставлен некоторый метод отгадывания некоторого загаданного числа х, не превосходящего n, при помощи вопросов, на которые отвечается лишь «да» (1) или «нет» (0) , что и приводит нас к двоичному коду. При заданных вероятностях р₁, р₂, … …, р_n отдельных букв передача многобуквенного сообщения наиболее экономный код будет тот, для которого при этих именно вероятностях n значений х среднее значение числа задаваемых вопросов (двоичных знаков: 0 и 1 или элементарных сигналов) оказывается наименьшим [8, c.11].