Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь FAQ Написать работу КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Основы эффективного кодированияСодержание книги
Похожие статьи вашей тематики
Поиск на нашем сайте
Задача статистического кодирования, которую часто приходится решать в технике документальной электросвязи формулируется следующим образом. Пусть имеется сообщение, записанное с помощью букв некоторого алфавита A={a1,a2,...,aк}, содержащего К букв. Алфавит А назовем входным. Требуется закодировать это сообщение, т. е. указать правило, которое сопоставляет каждой букве алфавита последовательность из символов «0» и «1». Выбранный код, во-первых, должен обеспечивать возможность однозначного декодирования, т. е. позволять по принятой последовательности символов «0» и «1» однозначно восстановить переданное сообщение (букву). Во-вторых, на передачу сообщения в среднем должно быть затрачено минимальное число нулей и единиц, что позволит передать за единицу времени максимальное число сообщений.
Таблица 2.1.
Пример 1. Пусть A={a1, а2, a3}. Некоторые возможные коды для букв алфавита А представлены в табл.1. Код 1 не является однозначно декодируемым кодом. Для доказательства этого рассмотрим, например, двоичную последовательность 0101. Она может быть декодирована одним из сообщений: а2а1а2a1; а3a3; а2a1а3; a3a2a1. Код 2 декодируется однозначно, поскольку все кодовые слова этого кода имеют равные длины и различны. Код 3 также однозначно декодируемый, поскольку никакое его кодовое слово не является началом {префиксом} другого кодового слова. Код, обладающий тем свойством, что никакое более короткое слово не является началом другого более длинного слова кода, называют префиксным. Префиксные коды всегда однозначно декодируемы. Кодовое дерево для множества кодовых слов. Наглядное графическое изображение множества кодовых слов можно получить, установив соответствие между сообщениями и концевыми узлами двоичного дерева. Пример двоичного дерева изображен на рис. 1. Две ветви, идущие от корня дерева к узлам первого порядка, соответствуют выбору между «0» и «1» в качестве первого символа кодового слова: левая ветвь соответствует «0», а правая—«1». Две ветви, идущие из узлов первого порядка, соответствуют второму символу кодовых слов, левая означает «0», а правая—«1» и т. д. Ясно, что последовательность символов каждого кодового слова определяет необходимые правила продвижения от корня дерева до концевого узла, соответствующего рассматриваемому сообщению. Формально кодовые слова могут быть приписаны также промежуточным узлам. Например, промежуточному узлу второго порядка на рис. 2.1 можно приписать кодовое слово 11, т. е. первые два символа кодовых слов, соответствующих концевым узлам, порождаемых этим узлом. Однако кодовые слова, соответ ствующие промежуточным узлам, не могут быть использованы для представления сообщений, так как в этом случае нарушается требование префиксности кода
Требование, чтобы только концевые узлы сопоставлялись сообщениям, эквивалентно условию, чтобы ни одно из кодовых слов не совпало с началом (префиксом) более длинного кодового слова. Любой код, кодовые слова которого соответствуют различным концевым вершинам некоторого двоичного дерева, является префиксным, т. е. декодируемым. На рис. 2.2 изображены кодовые деревья, соответствующие кодам 2 и 3 (см. табл. 2.1). Вернемся к рассмотренному ранее примеру 1. Пусть вероятность появления в сообщении буквы a1 равна 0,2; буквы a2 — 0,3; a3—0,5. Тогда среднее число двоичных символов, приходящихся на одну букву для кода 3 составляет 0,2*1+0,3*2+0,5*3=2,3, а для кода 2-0,2*2+0,3*2+0,5*2= 2,0, т. е. код 2 в среднем экономичнее кода 3. Рассмотрим еще один код—код 4, который букве a1 ставит в соответствие 10; a2 — 11; a3—0. Среднее число двоичных символов, приходящихся на одну букву этого кода: 0,2*2+0,3*2+0,5*1 =1,5, т. е. код 4 экономичнее и кода 3, и кода 2. Спрашивается, можно ли предложить код, который будет экономичнее кода 4? Как построить самый экономичный код для данного сообщения? Ответы на эти и многие другие вопросы дает основная теорема кодирования, сформулированная и доказанная впервые К. Шенноном. Пусть буквы a i, i= , входного алфавита А порождаются независимо с вероятностью pi, т. е. р(аi)=рi, некоторым источником сообщений. Количество информации, приходящееся на сообщение ai, равно—log2pi. Среднее количество информации в битах на одно сообщение (букву) обозначается Н(А) и называется энтропией источника сообщений (2.1) Энтропию Н(А) можно рассматривать как меру «неопределенности» сообщения до того, как оно было принято. В приведенной ниже основной теореме кодирования устанавливается связь между Н(А) и средним числом символов «0» и «1» в кодовом слове. Теорема 1. Для любого однозначно декодируемого кода всегда выполняется неравенство ³H(A) и существует однозначно декодируемый код, для которого выполняется неравенство <H(A)+1. Теорема 1 имеет глубокий смысл. В частности, из нее следует, что нельзя закодировать сообщение таким образом, чтобы средняя длина кодовых слов была меньше, чем энтропия сообщений. Кроме того, теорема утверждает, что существует кодирование, при котором средняя длина кодового слова немногим отличается от энтропии сообщения. Покажем, что среднее число символов на сообщение можно уменьшить, если кодировать не каждую букву в отдельности, а блоки по п букв из алфавита А. Пусть буквы алфавита А появляются независимо с вероятностями р1,...,рK. Множество всех блоков длины п в алфавите А обозначим An. Как хорошо известно, H(An)=nH(A). (2.2) Обозначим среднее число «0» и «1», приходящихся на один блок из п букв, взятых из алфавита A, через n. Тогда среднее число символов, приходящихся на одну букву алфавита, определяется формулой = n/n (2.3) Теорема 2. При любом сколь угодно малом положительном eможно найти натуральное число N, такое, что среднее число символов на одно сообщение при n >N удовлетворяет неравенству <H(A)+e (2.4) Наоборот невозможно найти натуральное число N и однозначно декодируемый код, такие, чтобы выполнялось неравенство <H(A). (2.5) Доказательство. Эта теорема вытекает из теоремы 1. Подставляя в нее n вместо , получаем n£H(An)+1. (2.6) Разделив (6) на n и учитывая (2) и (3), получим H(A)£ <H(A)+1/n (2.7) Из неравенства (7) следует неравенство (4), если положить n= 1/e. В то же время неравенство (5) несовместимо с неравенством (7). Теорема доказана. Из теоремы 2 следует, что, используя кодирование блоков, можно получить среднее число символов на сообщение (букву), сколь угодно мало отличающееся от энтропии, но при этом увеличивается сложность кодирования.
|
||||||||||||||||||||||||
Последнее изменение этой страницы: 2016-06-29; просмотров: 556; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.119.124.24 (0.007 с.) |