 ПОЗНАВАТЕЛЬНОЕ Сила воли ведет к действию, а позитивные действия формируют позитивное отношение Как определить диапазон голоса - ваш вокал Игровые автоматы с быстрым выводом Как самому избавиться от обидчивости Противоречивые взгляды на качества, присущие мужчинам Вкуснейший "Салат из свеклы с чесноком" Натюрморт и его изобразительные возможности Применение, как принимать мумие? Мумие для волос, лица, при переломах, при кровотечении и т.д. Как научиться брать на себя ответственность Зачем нужны границы в отношениях с детьми? Световозвращающие элементы на детской одежде Как победить свой возраст? Восемь уникальных способов, которые помогут достичь долголетия Классификация ожирения по ИМТ (ВОЗ) Глава 3. Завет мужчины с женщиной
Оси и плоскости тела человека - Тело человека состоит из определенных топографических частей и участков, в которых расположены органы, мышцы, сосуды, нервы и т.д.
| Асинхронное и синхронное кодирование.
Лабораторная работа №3 Кодирование и сжатие информации В современных методах сжатия прослеживается тенденция к разделению алгоритма сжатия на две задачи: моделирование и кодирование. Моделирование - попытка предсказать с той или иной вероятностью появление следующего символа в сжимаемом тексте, кодирование - представление появившегося в тексте символа с помощью того количества бит, которое указано моделировщиком (моделирующей программой). Кодировщик переделывает символ на входе в код на выходе, используя вероятности символов, которые поставляет ему моделировщик. Кодирование - представление сообщения последовательностью элементарных символов. Рассмотрим кодирование дискретных сообщений. Символы в сообщениях могут относиться к алфавиту, включающему n букв (буква - символ сообщения). Однако число элементов кода k существенно ограничено сверху энергетическими соображениями, т.е. часто n > k. Так, если отношение сигнал/помеха для надежного различения уровня сигнала должно быть не менее q, то наименьшая амплитуда для представления одного из k символов должна быть q*g, где g - амплитуда помехи, а наибольшая амплитуда соответственно q*g*k. Мощность передатчика пропорциональна квадрату амплитуды сигнала (тока или напряжения), т.е. должна превышать величину, пропорциональную (q*g*k)2. В связи с этим распространено двоичное кодирование с k = 2. При двоичном кодировании сообщений с n типами букв, каждая из n букв кодируется определенной комбинацией 1 и 0 (например, код ASCII). Кодирование аналоговых сообщений после их предварительной дискретизации должно выполняться в соответствии с теоремой Котельникова: если в спектре функции f(t) нет частот выше FВ, то эта функция может быть полностью восстановлена по совокупности своих значений, определенных в моменты времени tk, отстоящие друг от друга на величину 1/(2*Fв). Для передачи аналогового сигнала производится его дискретизация с частотой отсчетов 2*FВ и выполняется кодово-импульсная модуляция последовательности отсчетов. Количество информациив сообщении (элементе сообщения) определяется по формуле I = -log2 P, где Р - вероятность появления сообщения (элемента сообщения). Из этой формулы следует, что единица измерения количества информации есть количество информации, содержащееся в одном бите двоичного кода при условии равной вероятности появления в нем 1 и 0. В то же время один разряд десятичного кода содержит I = -log2Р = 3,32 единиц информации (при том же условии равновероятности появления десятичных символов, т.е. при Р = 0,1). Асинхронное и синхронное кодирование. Для правильного распознавания позиций символов в передаваемом сообщении получатель должен знать границы передаваемых элементов сообщения. Для этого необходима синхронизация передатчика и приемника. Использование специального дополнительного провода для сигналов синхронизации (в этом случае имеем битовую синхронизацию) слишком дорого, поэтому используют другие способы синхронизации. В асинхронном режиме применяют коды, в которых явно выделены границы каждого символа (байта) специальными стартовым и стоповым символами. Подобные побайтно выделенные коды называют байт-ориентированными, а способ передачи - байтовой синхронизацией. Однако это увеличивает число битов, не относящихся собственно к сообщению. В синхронном режиме синхронизм поддерживается во время передачи всего информационного блока без обрамления каждого байта. Такие коды называют бит-ориентированными. Для входа в синхронизм нужно обозначать границы лишь всего передаваемого блока информации с помощью специальных начальной и конечной комбинаций байтов (обычно это двубайтовые комбинации). В этом случае синхронизация называется блочной (фреймовой). Для обрамления текстового блока (текст состоит только из печатаемых символов) можно использовать символы, отличающиеся от печатаемых. Для обрамления двоичных блоков применяют специальный символ (обозначим его DLE), который благодаря стаффингу становится уникальным. Уникальность заключается в том, что если DLE встречается внутри блока, то сразу вслед за ним вставляется еще один DLE. Приемник будет игнорировать каждый второй идущий подряд символ DLE. Если же DLE встречается без добавления, то это граница блока.
Рассмотрим два самых распространенных и известных методах кодирования информации во время сжатия: кодирование Хаффмана (Huffman) и арифметическое кодирование и его разновидности. Кодирование Хаффмана Этот метод кодирования появился очень давно и получил широкое распространение из-за простоты реализации и высокой скорости. Метод не требует огромных вычислительных мощностей в отличие от арифметического кодирования, производящего целочисленные умножения и деления. На заре компьютерной эры метод оказался простым в применении. Для работы алгоритма необходимо иметь таблицу значений вероятностей различных символов, которые могут встретиться в данный момент кодирования (в данном месте обрабатываемого текста, где кодер в данный момент будет кодировать очередной символ). На основе этой таблицы строится бинарное дерево Хаффмана следующим образом: Отсортировать символы по возрастанию вероятности их появления Первые два символа в получившемся ряде объединить в один, сопоставив первому символу ноль, второму символу - единицу. Вероятности этих двух символов сложить. Если в ряде остался один символ, то закончить, иначе перейти к пункту 1 Пример построения дерева Предположим, что мы имеем алфавит из 8 символов. Подпрограмма, осуществляющая моделирование задает нам следующие возможные вероятности этих символов: Сортируем символы по возрастанию вероятности: Левые два объединяем в один: В данном случае сортировка не требуется. Заметим также, что для символа C теперь появился код 0, для H - 1. Эти символы находятся в самом низу кроны дерева Хаффмана (дерево растет вниз, т.е. крона его внизу), и к ним впоследствии будут добавлены новые узлы дерева, которые будут стоять выше. Пока же дерево выглядит следующим образом:
Снова объединяем два левых символа в один: После сортировки получим: Дерево выглядит следующим образом:
Когда мы обработаем все символы дерево примет вид:
Теперь, чтобы закодировать любой символ нужно пройти от корня дерева до символа запоминая биты, определяющие направление движения. Коды символов получились следующие: Таким образом, самые вероятные символы: D и F имеют наименьшую длину кода: 2 бита, а менее вероятные символы имеют коды большей длины. Все коды уникально идентифицируют символ, т.е. из кода можно получить исходный текст в полном объеме. Недостаток метода Хаффмана Основным и, возможно, единственным существенным недостатком этого метода кодирования является то, что он кодирует символы с помощью целого количества бит, что снижает степень сжатия и сводит на нет точное предсказание вероятностей, которое дают некоторые отличные современные алгоритмы моделирования. Представим себе, что символ встречается в тексте с 99% вероятностью. Метод Хаффмана присвоит этому символу код 1, длиной в 1 бит. Имея файл размером 1 Мбайт, сжат он будет до 1 бит/байт, т.е. до 128 Кбайт, хотя сжать его можно гораздо эффективней: буквально до нескольких сот байт! Быстрое кодирование Быстрое кодирование обладает недостатком, присущим алгоритму Хаффмана, но позволяет не производить сортировку таблицы символов по частоте их встречаемости. Быстрота достигнута путем замены умножения битовыми сдвигами, т.е. в данном случае используется только умножение и деление на степень двойки. Ширина интервала в данном случае округляется в большую сторону до ближайшей степени двойки, из-за чего становится возможным значительно ускорить алгоритм, но плата в данном случае - снижение степени сжатия из-за потери точности, в некоторых случаях очень существенной. Этот алгоритм следует рассматривать как альтернативу алгоритму Хаффмана.
|
