Файл: Методы кодирования данных (Основы и основные понятия кодирования информации).pdf

Введение

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

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

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

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

Поэтому изучение кодирования информации и методов кодирования, в частности метода кодирования Хаффмана является актуальным.

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

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

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

1) рассмотреть основные понятия и принципы кодирования информации;

2) изучить метод кодирования Хаффмана,

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

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

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

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

Кодирование - это преобразование сообщений в сигнал, то есть преобразование сообщений в кодовые комбинации. Код - система соответствия между элементами сообщения и кодовыми комбинациями. Кодировщик - это устройство кодирования. Декодер - устройство, которое выполняет обратную операцию, то есть преобразование шаблона кода в сообщение. Алфавит - это набор возможных элементов кода, то есть элементарных символов (кодовых символов) X = {xi}, где i = 1, 2, ..., m. Количество элементов кода - m называется его базой. Для двоичного кода xi = {0, 1} и m = 2. Конечная последовательность символов в данном алфавите называется кодовой комбинацией (кодовым словом). Количество элементов в кодовой комбинации - n называется значимостью (длина комбинации). Количество различных кодовых комбинаций (N = mn) называется объемом или мощностью кода.

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

1) Повышение эффективности передачи данных путем достижения максимальной скорости передачи данных.

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

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

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

2. Теория кодирования с исправлением ошибок занимается поиском кодов, повышающих надежность передачи информации по каналам с помехами.

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

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

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

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

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

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

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

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

В некоторых случаях необходимо классифицировать текст сообщения или документа так, чтобы он не мог быть прочитан теми, кто не должен это делать. Это называется защитой от несанкционированного доступа. В этом случае секретный текст зашифрован. Шифрование - это процесс преобразования открытого текста в зашифрованный, а дешифрование - это процесс обратного преобразования, при котором исходный текст восстанавливается. Шифрование также является шифрованием, но секретным методом, известным только источнику и получателю. Шифрование - это наука, называемая криптографией. [3 2004. - 320с]

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

Рассмотрим эксперимент А, состоящий из экспериментов и имеющих вероятности. Тогда общая неопределенность для эксперимента А будет равна:

Это последнее число будет называться энтропией опыта и обозначаться как.

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

Здесь мы рассмотрим только простейший случай сообщений, записанных с использованием нескольких n «букв», частота проявления которых в любой точке сообщения полностью характеризуется вероятностями p1, p2, ..., pn, где, конечно, p1 + p2 + ... + pn = 1, в котором вероятность pi проявления i-й буквы в любом месте сообщения считается одинаковой независимо от того, какие буквы были во всех предыдущих местах, т.е. последовательные буквы сообщения не зависят друг от друга. На самом деле в реальных сообщениях это часто не так; в частности, в русском языке вероятность появления того или иного письма существенно зависит от предыдущего письма. Однако строгий учет взаимозависимости букв усложнит все дальнейшие рассуждения, но не изменит будущих результатов. [4- 2005. - 544с]

Сейчас мы рассмотрим двоичные коды; Обобщение результатов, полученных в этом случае, для кодов, использующих произвольное число m элементарных сигналов, как всегда, чрезвычайно просто. Начнем с самого простого случая, когда коды соответствуют отдельному обозначению кода - последовательности чисел 0 и 1 - каждой «букве» сообщения. Каждый двоичный код для n-буквенного алфавита может быть связан с некоторым методом угадывания некоторого загадочного числа x, не превышающего n, используя вопросы, которые отвечают только «да» (1) или «нет» (0), что приводит нас к двоичному код. Для заданных вероятностей p1, p2, ..., pn отдельных букв передача многобуквенного сообщения является наиболее экономичным кодом, для которого для этих вероятностей n значений x среднее число задаваемых вопросов (двоичные знаки : 0 и 1 или элементарные сигналы) оказывается наименьшим.

Прежде всего, среднее число двоичных элементарных сигналов, которые встречаются в закодированном сообщении на букву исходного сообщения, не может быть меньше H, где H = - p1 log p1 - p2 log p2 - ... - pn log pn - это энтропия опыта, заключающаяся в распознавании одной буквы текста (или, короче говоря, только энтропия одной буквы). Из этого сразу следует, что для любого метода кодирования запись длинного сообщения из M букв требует не менее MN двоичных символов и ни в коем случае не может превышать один бит.

Если вероятности p1, p2, ... ..., pn не все равны, то H <log n; следовательно, естественно думать, что учет статистических закономерностей сообщения может позволить создать код, который является более экономичным, чем лучший унифицированный код, который требует по меньшей мере M log n двоичных символов для записи текста из M букв.

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

Коды могут быть классифицированы по различным критериям:

1. На основании (количество символов в алфавите): двоичный (бинарный m = 2) и недвоичный (м № 2).

2. По длине кодовых комбинаций (слов): равномерно, если все кодовые комбинации имеют одинаковую длину, и неравномерно, если кодовая комбинация не постоянна.

3. По способам передачи: последовательный и параллельный; блок - данные сначала буферизуются, а затем передаются в канал и непрерывно двоично.

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