Файл: Методы кодирования данных.pdf

Введение

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

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

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

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

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

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

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

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

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

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

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

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

---

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

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

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

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

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

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

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

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

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

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

---

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

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

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

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

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

---

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

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

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

---

.

Условиям:

,

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

.

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

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

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

Мы рассмотрим здесь только простейший случай сообщений, написанных с помощью определенных n "букв", частота проявления которых в любом месте сообщения полностью характеризуется вероятностями p1, p2, ..., pn, где , конечно, p1 + p2 + ... + pn = 1, при котором вероятность pi развития i-й буквы в любом месте сообщения считается одинаковой, независимо от того, какие буквы стояли вообще предыдущие места, то есть последовательные буквы сообщения не зависят друг от друга. Фактически, в реальных сообщениях это часто бывает не так; в частности, на русском языке вероятность наступления той или иной буквы существенно зависит от предыдущего письма. Тем не менее, строгое рассмотрение взаимной зависимости букв сделало бы все дальнейшее обсуждение очень сложным, но это не изменит будущих результатов.

---