Меню Рубрики

Что такое оптимальный код с точки зрения шеннона

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

Вопрос 1. Основные положения, термины и определения. Классификация кодов

Формально-математическое определение кодирования:

Пусть даны конечные множества Х, Y. Будем интерпретировать Х как множество исходных дискретных сообщений, Y как множество кодовых слов.

Тогда: отображение Т: Х → Y называется кодированием, если для ∀ yY
Т -1 (у) = х.

Правило, сопоставляющее каждому дискретному сообщению — букве или последовательности букв — кодовое слово называется правилом кодирования.

Сама операция сопоставления называемся кодированием сообщения.

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

Множество кодовых букв (символов) называется кодовым алфавитом, а их количество — объемом алфавита или осно­ванием кода. Количество букв в кодовом слове называется длиной ко­дового слова или значностью кода.

Классификация кодов

1. По наличию избыточности:

2. По значности (длине кодового слова):

3. По типу оператора кодирования:

Классификация избыточных кодов:

1. По возможностям коррекции ошибок:

2. По количеству кодируемых символов:

— непрерывные (древовидные, рекуррентные сверточные, цепные);

2. По возможности разделения информационных и проверочных символов:

Вопрос 2. Оптимальное кодирование

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

Естественно полагать оптимальным такое правило кодирования (критерий), при котором:

–во-первых, кодовые слова могут быть декодированы в исходную последовательность букв источника;

–во-вторых, число кодовых букв, затрачиваемых на одну букву источника, в среднем минимально.

Первое требование определяет обратимость операции кодирования – однозначность декодирования, а второе — экономность кодирования или быстродействие кодера.

Очевидно, что «экономнее» будет кодер, в котором более вероятным буквам источника сопоставляются более короткие кодовые слова, т.е. в общем случае оптимальный код должен быть неравномерным.

Среднее число кодовых букв на одну букву источника можно определить по формуле

, (2.1)

где ni– число кодовых букв, кодирующих слово xi источника,

P(xi) – вероятность появления буквы xi на выходе дискретного источника.

Нижним теоретическим пределом для Nср является энтропия Шеннона

В оптимальном коде избыточность, связанная с неравномерностью появления символов полностью исключается.

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

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Студент — человек, постоянно откладывающий неизбежность. 10559 — | 7323 — или читать все.

195.133.146.119 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.

Отключите adBlock!
и обновите страницу (F5)

очень нужно

источник

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

1. Код Хаффмана — неравномерный код. Чтобы он был оптимальным, необходимо, чтобы средняя длина кодовой комбинации для определенного алфавита, закодированного этим кодом, была меньше длины кодовой комбинации равномерного двоичного кода, которым можно закодировать этот алфавит.

По формуле (5) найдем среднюю длину кодовой комбинации для нашего алфавита (количество символов алфавита n = 16), закодированного кодом Хаффмана, и получим следующее значение:

,

то есть в среднем на один символ нашего алфавита приходится 3,8131 двоичных символов.

Длина кодовой комбинации равномерного двоичного кода, которым можно закодировать наш алфавит, будет равняться 4, поскольку таким кодом можно закодировать алфавит, максимальное количество символов которого будет равняться 2 4 = 16.

Это означает, что необходимая длина кодовой комбинации равномерного двоичного кода больше средней длины кодовой комбинации Хаффмана.

2. Сравним энтропию источника первичного ансамбля сообщений A (нашего алфавита) с энтропией этого же источника при кодировании его ансамбля сообщений кодом Хаффмана.

Рассчитаем энтропию источника сообщений вторичного алфавита BH(B). Для этого необходимо найти вероятность появления символов этого алфавита. Положим, что длина текста

.

Подсчет количества “0” и “1” в закодированном тексте (исходный текст длиной L = 10 000 символов)

Символ первичного алфавита Вероятность появления символа первичного алфавита Закодированный кодом Хаффмена символ Количество символов в кодовой комбинации Количество символов в тексте
о 0,1067
а 0,1067
и 0,0933
в 0,0933
к 0,08
н 0,08
с 0,08
е 0,08
л 0,0667
я 0,0667
ч 0,0533
й 0,0267
т 0,0267
ь 0,0133
р 0,0133
г 0,0133
Количество каждого из двоичных символов в закодированном тексте
Длина закодированного текста

Подсчитаем вероятность появления двоичных символов в закодированном тексте:

По формуле (3) рассчитаем энтропию источника вторичного ансамбля сообщений BH(B) (количество символов алфавита n = 2):

Теперь по формуле (6) найдем энтропию источника при кодировании его первичного ансамбля сообщений A кодом Хаффмана:

.

Энтропия источника первичного ансамбля сообщений A:

.

≈ .

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

Коды, обнаруживающие ошибки

Код с проверкой на чётность

источник

а) результаты работы программы

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

К работе прилагается программа, написанная на языке программирования высокого уровня (Turbo Pascal).

In this work on the given numbeof symbols in the alphabet their probabilities, amount of the information if symbols meet equal probabilities and with different probabilities, speed of message transfer and redundancy of messages pay off. Besides in the given work the optimum binary code by technique of Shennon and Fano is under construction. Performance of this course work fixes our knowledge on discipline «The Theory of the Information».

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

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

Одним из методов защиты является кодирование.

Кодирование – это отображение сообщений кодом по определенному правилу присвоения символов.

Код – это правило, описывающее отображение одного набора знаков в другой набор знаков (или слов). Кодом также называют и множество образов при этом отображении.

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

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

Таким образом, информатика занимается изучением обработки и передачи информации.

В работе отражается применение базовых понятий информатики.

Для проведения расчетов разработать программу на языке ПАСКАЛЬ.

1.1. Число символов алфавита k = m (номер варианта задания) + 10. Определить количество информации на символ сообщения, составленного из этого алфавита:

а) если символы алфавита встречаются с равными вероятностями;

б) если символы алфавита встречаются в сообщении с вероятностями:

Сумма всех вероятностей должна быть равой единице, поэтому:

Определить, насколько недогружены символы во втором слу­чае.

1.2. Число символов алфавита = m (номер варианта задания). Вероятности появления символов равны соответственно

Длительности символов τ1 = 1 сек; τ2 = 2 сек;

Чему равна скорость передачи сообщений, составленных из таких символов?

Определить количество информации на символ сообщения, составленного из этого алфавита:

а) если символы алфавита встречаются с равными вероятностями;

Определить, насколько недогружены символы во втором случае.

1.3. Сообщения составляются из алфавита с числом символов = m. Вероятность появления символов алфавита равна соответственно:

Найти избыточность сообщений, составленных из данного алфавита.

Построить оптимальный код сообщения.

КОЛИЧЕСТВЕННАЯ ОЦЕНКА ИНФОРМАЦИИ

Общее число неповторяющихся сообщений, которое может быть составлено из алфавита m путем комбинирования по n символов в сообщении,

Неопределенность, приходящаяся на символ первичного (кодируемого) алфавита, составленного из равновероятных и взаимонезависимых символов,

Так как информация есть неопределенность, снимаемая при получении сообщения, то количество информации может быть представлено как произведение общего числа сообщений k на среднюю энтропию H, приходящуюся на одно сообщение:

Читайте также:  Личность человека с точки зрения философии

Для случаев равновероятных и взаимонезависимых символов первичного алфавита количество информации в k сообщениях алфавита m равно:

Для неравновероятных алфавитов энтропия на символ алфавита:

А количество информации в сообщении, составленном из k неравновероятных символов,

ВЫЧИСЛЕНИЕ СКОРОСТИ ПЕРЕДАЧИ ИНФОРМАЦИИ И ПРОПУСКНОЙ СПОСОБНОСТИ КАНАЛОВ СВЯЗИ

В условиях отсутствия помех скорость передачи информации определяется количеством информации, переносимым символом сообщения в единицу времени, и равна

где n — количество символов, вырабатываемых источником сообщений за единицу времени; H — энтропия (неопределенность), снимаемая при получении одного символа сообщений, вырабатываемых данным источником.

Скорость передачи информации также может быть представлена как

бит/сек,

где тау — время передачи одного двоичного символа.

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

В случае неравновероятных символов равной длительности:

В случае неравновероятных и взаимонезависимых символов разной длительности:

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

Смакс = бит/сек

Смаксбит/сек

При наличии помех пропускная способность канала связи вычисляется как произведение количества принятых в секунду знаков n на разность энтропии источника сообщений и условной энтропии источника сообщений относительно принятого сигнала:

бит/сек (15)

бит/сек

бит/сек (16)

Если символы источника сообщений неравновероятны и взаи­мозависимы, то энтропия источника считается по формуле общей условной энтропии.

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

бит/сек (17)

пропускная способность таких каналов

бит/сек (18)

Для симметричного бинарного канала

бит/сек (19)

Для симметричных дискретных каналов связи с числом качест­венных признаков m > 2 пропускная способность

бит/сек (20)

ОПРЕДЕЛЕНИЕ ИЗБЫТОЧНОСТИ СООБЩЕНИЙ. ОПТИМАЛЬНОЕ КОДИРОВАНИЕ

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

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

,

где = μ — коэффициент сжатия (относительная энтропия). Н и Нмакс берутся относительно одного и того же алфавита.

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

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

Фактически для передачи сообщения достаточно иметь длину кодовой комбинации

где N — общее количество передаваемых сообщений.

L можно представить и как

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

дв. симв.

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

В общем случае, избыточность от округления:

где , k — округленное до ближайшего целого числа значение . Для нашего примера

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

Для уменьшения избыточности используют оптимальные коды. При построении оптимальных кодов наибольшее распространение получили методики Шеннона-Фано и Хаффмена. Согласно методике Шеннона-Фано построение оптимального кода ансамбля из сообщений сводится к следующему:

1) множество из сообщений располагается в порядке убывания вероятностей;

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

Если равной вероятности в подгруппах нельзя достичь, то их делят так, чтобы в верхней части (верхней подгруппе) оставались символы, суммарная вероятность которых меньше суммарной вероятности символов в нижней части (нижней подгруппе);

3) первой группе присваивается символ 0, а второй группе — символ 1;

4) каждую из образованных подгрупп делят на две части таким образом, чтобы суммарные вероятности вновь образованных подгрупп были по возможности равны;

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

Построенный код называют оптимальным неравномерным кодом (ОНК).

1) рассчитывается первоначальные вероятности для неравновероятных символов алфавита.

2) выполняет нормирование указанных вероятностей.

3) рассчитывается энтропия алфавита из равновероятных символов.

4) производится расчет энтропии алфавита с неравновероятными символами и недогруженность в этом случае.

5) с учетом заданных длительностей символов вычисляется скорость передачи и избыточность.

6) строится оптимальный код по методу Шеннона-Фано.

рi = pi /( pi )

рi = 3,6

рi = 1

Определение количества информации на символ сообщения, составленного из данного алфавита.

Количество информации на символ сообщения для символов данного алфавита, встречающихся с равными вероятностями:

Hmax = log2 24 = ln 24/ln 2 = 4,5850 бит/символ

Количество информации на символ сообщения для символов данного алфавита, встречающихся в сообщении с разными вероятностями:

H = – (0,0417*log2 0,0417 + 0,0018*log2 0,0018 + 0,020*log2 0,0020 + 0,0022*log2 0,0022 + 0,0024*log2 0,0024 + 0,0026*log2 0,0026 + 0,0029*log2 0,0029 + 0,0033*log2 0,0033 + 0,0037*log2 0,0037 + 0,0042*log2 0,0042 + 0,0048*log2 0,0048 + 0,0055*log2 0,0055 + 0,0064*log2 0,0064 + 0,0076*log2 0,0076 + 0,0091*log2 0,0091 + 0,0111*log2 0,0111 + 0,0139*log2 0,0139 + 0,0179*log2 0,0179 + 0,0238*log2 0,0238 + 0,0333*log2 0,0333 + 0,0500*log2 0,0500 + 0,0833*log2 0,0833 + 0,1667*log2 0,1667 + 0,5000*log2 0,5000) =

Недогруженность символов в данном случае:

N = Нmax – Н = 4,5850 – 2,6409 = 1,9441 бит/символ

Вычисление скорости передачи информации.

С= – (0,0417*log2 0,0417 + 0,0018*log2 0,0018 + 0,020*log2 0,0020 + 0,0022*log2 0,0022 + 0,0024*log2 0,0024 + 0,0026*log2 0,0026 + 0,0029*log2 0,0029 + 0,0033*log2 0,0033 + 0,0037*log2 0,0037 + 0,0042*log2 0,0042 + 0,0048*log2 0,0048 + 0,0055*log2 0,0055 + 0,0064*log2 0,0064 + 0,0076*log2 0,0076 + 0,0091*log2 0,0091 + 0,0111*log2 0,0111 + 0,0139*log2 0,0139 + 0,0179*log2 0,0179 + 0,0238*log2 0,0238 + 0,0333*log2 0,0333 + 0,0500*log2 0,0500 + 0,0833*log2 0,0833 + 0,1667*log2 0,1667 + 0,5000*log2 0,5000) /

(1*0,0417 + 2*0,0018 + 3*0,020 + 4*0,0022 + 5*0,0024 + 6*0,0026 + 7*0,0029 + 8*0,0033 + 9*0,0037 + 10*0,0042 + 11*0,0048 + 12*0,0055 + 13*0,0064 + 14*0,0076 + 15*0,0091 + 16*0,0111 + 17*0,0139 + 18*0,0179 + 19*0,0238 + 20*0,0333 + 21*0,0500 + 22*0,0833 + 23*0,1667 + 24*0,5000) = 0,1244 бит/сек

Избыточность сообщений, составленных из данного алфавита.

D = 1 – (Н/Нmax ) = 1 – (2,6409 / 4,5850) = 0,4240

Построение оптимального кода

1 p24=0,5000 0,5
2 p23=0,1667 0,5 1 0,25 1 0,1666 1 111
3 p22=0,0833 1 1 0,0833 110
4 p21=0,0500 1 0,25 0,05 1 0 1000
5 p1=0,0417 1 0,0690 1 0,0357 1 10011
6 p20=0,0333 1 0,1190 1 0,0333 10010
7 p19=0,0238 1 1 1 0,0428 1 0,0178 1 101111
8 p18=0,0179 1 1 1 1 0,025 0,0138 1011100
9 p17=0,0139 1 1 1 0,025 1 101101
10 p16=0,0111 1 1 0,0666 1 1 101110
11 p15=0,0091 1 1 0,0642 1 0,0090 1 1010011
12 p14=0,0076 1 1 1 0,0102 0,0054 10100100
13 p13=0,0064 1 1 0,0166 0,0064 1 1010001
14 p12=0,0055 1 1 0,0166 1 0,0064 1 1010011
15 p11=0,0048 1 1 0,0333 1 1 1 0,0047 1 10101111
16 p10=0,0042 1 1 1 1 0,0088 1 0,0032 101011100
17 p9=0,0037 1 1 1 1 0,0078 0,0036 1 10101101
18 p8=0,0033 1 1 1 1 0,0078 1 0,0036 10101110
19 p7=0,0029 1 1 1 1 10101010
20 p6=0,0026 1 1 1 0,0167 1 0,0026 1 0,0026 1 101010111
21 p5=0,0024 1 1 1 0,0147 1 1 0,0024 101010110
22 p4=0,0022 1 1 1 0,0022 10101000
23 p3=0,0020 1 1 1 0,0038 1 0,0020 1 101010011
24 p2=0,0018 1 1 1 0,0083 1 0,0018 101010010

Буква Вероятность появления буквы Кодовые слова Число знаков в кодовом слове Pi ·li
A[1] (p24) 0,5000 1 0,5
A[2] (p23) 0,1667 111 3 0,50001
A[3] (p22) 0,0833 110 3 0,2500
A[4] (p21) 0,0500 1000 4 0,2000
A[5] (p1) 0,0417 10011 5 0,2083
A[6] (p20) 0,0333 10010 5 0,1667
A[7] (p19) 0,0238 101111 6 0,1429
A[8] (p18) 0,0179 1011100 7 0,1250
A[9] (p17) 0,0139 101101 6 0,0833
A[10] (p16) 0,0111 101110 6 0,0667
A[11] (p15) 0,0091 1010011 7 0,0636
A[12] (p14) 0,0076 10100100 8 0,0606
A[13] (p13) 0,0064 1010001 7 0,0449
A[14] (p12) 0,0055 1010011 7 0,0385
A[15] (p11) 0,0048 10101111 8 0,0381
A[16] (p10) 0,0042 101011100 9 0,0375
A[17] (p9) 0,0037 10101101 8 0,0294
A[18] (p8) 0,0033 10101110 8 0,0261
A[19] (p7) 0,0029 10101010 8 0,0234
A[20] (p6) 0,0026 101010111 9 0,0237
A[21] (p5) 0,0024 101010110 9 0,0214
A[22] (p4) 0,0022 10101000 8 0,0173
A[23] (p3) 0,0020 101010011 9 0,0178
A[24] (p2) 0,0018 101010010 9 0,0163
Читайте также:  С точки зрения аристотеля политика была

Определение количества информации на символ сообщения. Построение оптимального кода.

С начало множество из сообщений расположим в порядке убывания вероятностей. Затем, разобьем данное множество на две группы таким образом, чтобы суммарные вероятности сообщений обеих групп были по возможности равны. Но поскольку равенство не достигается, то мы их делим так, чтобы в верхней части оставались символы, суммарная вероятность которых меньше суммарной вероятности символов в нижней части. Первой группе присваиваем символ 0, а второй группе = символ 1. каждую из образованных подгрупп делим на две части таким образом, чтобы суммарные вероятности вновь образованных подгрупп были по возможности равны. Первым группам каждой из подгрупп вновь присваиваем 0, а вторым 1. таким образам мы получаем мы получаем вторые цифры кода. Затем каждую из четырех групп вновь делим на равные части до тех пор, пока в каждой из подгрупп не останется по одной букве.

Оптимальный код (получившийся результат):

Кодовое слово Число знаков в кодовом слове pi li P1 0,055 000 3 0,165 P2 0,053 0010 4 0,212 P3 0,051 00110 5 0,255 P4 0,050 00111 5 0,250 P5 0,048 0100 4 0,192 P6 0,046 0101 4 0,176 P7 0,044 0110 4 0,114 P8 0,043 01110 5 0,215 P9 0,041 011110 6 0,246 P10 0,040 011111 6 0,240 P11 0,039 1000 4 0,156 P12 0,038 10010 5 0,190 P13 0,036 10011 5 0,180 P14 0,035 1010 4 0,140 P15 0,033 10110 5 0,165 P16 0,032 101110 6 0,192 P17 0,030 101111 6 0,180 P18 0,029 11000 5 0,145 P19 0,027 11001 5 0,135 P20 0,026 11010 5 0,130 P21 0,025 110110 6 0,150 P22 0,023 110111 6 0,138 P23 0,022 11100 5 0,110 P24 0,020 111010 6 0,120 P25 0,019 111011 6 0,114 P26 0,018 111100 6 0,108 P27 0,017 111101 6 0,102 P28 0,016 111110 6 0,096 P29 0,013 1111110 7 0,091 P30 0,012 11111110 8 0,096 P31 0,010 11111111 8 0,080

Ручное построение ОНК по методике Шеннона-Фано:

0,010 P2 0,012 11111110 0,012 P3 0,013 1111110 0,013 P4 0,016 111110 0,016 P5 0,017 111101 0,035 0,017 P6 0,018 111100 0,018 P7 0,019 111011 0,061 0,039 0,019 P8 0,020 111010 0,020 P9 0,022 11100 0,022 P10 0,023 110111 0,130 0,074 0,048 0,023 P11 0,025 110110 0,025 P12 0,026 11010 0,026 P13 0,027 11001 0,056 0,027 P14 0,029 11000 0,029 P15 0,030 101111 0,243 0,130 0,095 0,062 0,030 P16 0,032 101110 0,032 P17 0,033 10110 0,033 P18 0,035 1010 0,035 P19 0,036 10011 0,113 0,074 0,036 P20 0,038 10010 0,038 P21 0,039 1000 0,039 P22 0,040 011111 0,471 0,262 0,168 0,124 0,081 0,040 P23 0,041 011110 0,041 P24 0,043 01110 0,043 P25 0,044 0110 0,044 P26 0,046 0101 0,094 0,046 P27 0,048 0100 0,048 P28 0,050 00111 0,209 0,154 0,101 0,050 P29 0,051 00110 0,051 P30 0,053 0010 0,053 P31 0,055 000 0,055

code: array [1..k] of string[20];

procedure divide(var nS:integer; n1,n2:integer);

источник

Кодирование

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

Коды, представляющие первичные алфавиты с неравномерным распределением символов, имеющие среднюю минимальную длину кодового слова во вторичном алфавите, называются оптимальными неравномерными кодами (ОНК).

Эффективность ОНК оценивают при помощи двух коэффициентов:

1. коэффициента статического сжатия

,

который характеризует уменьшение количества двоичных знаков на символ сообщения при применении ОНК по сравнению с применением методов нестатистического кодирования.

2. коэффициента относительной эффективности

,

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

Из свойств оптимальных кодов вытекают принципы их построения:

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

— буквам первичного алфавита, имеющим большую вероятность, присваиваются более короткие кодовые слова во вторичном алфавите.

Принципы оптимального кодирования определяют методики построения оптимальных кодов.

I. Построение ОНК по методике Шеннона-Фано для ансамбля из M сообщений сводится к следующей процедуре:

1) множество из M сообщений располагают в порядке убывания вероятностей;

2) первоначальный ансамбль кодируемых сигналов разбивают на две группы таким образом, чтобы суммарные вероятности сообщений обеих групп были по возможности равны;

3) первой группе присваивают символ 0, второй группе символ 1;

4) каждую из подгрупп делят на две группы так, чтобы их суммарные вероятности были по возможности равны;

5) первым подгруппам каждой из групп вновь присваивают 0, а вторым — 1, в результате чего получают вторые цифры кода. Затем каждую из четырех подгрупп вновь делят на равные (с точки зрения суммарной вероятности) части и т. д. До тех пор, пока в каждой из подгрупп останется по одной букве.

Функция Med находит медиану указанной части массива Р [b..e], т.е. определяет такой индекс m (bm

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

Решение. Так вероятности данного ансамбля сообщений равны p1 = = p2 = . = p8 = 2 -3 и порядок их расположения не играет роли, то расположим их так, как показано в таблице 2.1.1. Затем разбиваем данное множество на две равновероятные группы. Первой группе в качестве первого символа кодовых слов присваиваем 0, а второй — 1. Во второй колонке таблицы записываем четыре нуля и четыре единицы. После чего разбиваем каждую из групп еще на две равновероятные подгруппы. Затем каждой первой подгруппе присваиваем 0, а второй — 1 и записываем в третью колонку таблицы. Далее каждую из четырех подгрупп разбиваем на две равновероятные части и первой из них присваиваем 0, а второй — 1. Таким образом в четвертой колонке появится значение третьего символа кодовых слов.

Таблица 5.4 – Оптимальный код равновероятных букв

Буква Кодовое слово полученное после разбиения
первого второго третьего
А1 А2 А3 А4 А5 А6 А7 А8

Проверка оптимальности кода осуществляется путем сравнения энтропии кодируемого (первичного) алфавита со средней длиной кодового слова во вторичном алфавите.

Для рассматриваемого примера энтропия источника сообщений

а среднее число двоичных знаков на букву кода

бит

где li — длина i-ой кодовой комбинации; pi — вероятность появления i-го символа комбинации длиной в li.

Таким образом, H = L, т. е. код является оптимальным для данного ансамбля сообщений.

Вывод: Для ансамблей равновероятных сообщений оптимальным является равномерный код. Если число исходных элементов ансамбля равно целой степени двух, то всегда H = L.

Пример. Первичный алфавит состоит из 8 символов со следующими вероятностями появления: a1 = 0,5; a2 = 0,25; a3 = 0,098; a4 = = 0,052; a5 = 0,04; a6 = 0,03; a7 = 0,019; a8 = 0,011. Построить ОНК по методу Шеннона — Фано и подсчитать коэффициенты.

Решение проиллюстрируем в таблице 5.5.

Таблица 5.5 – Оптимальный код неравновероятных букв

ai pi Кодовое слово после разбиения Знаков lipi
0,5 0,5
0,25 0,5
0,098 0,392
0,052 0,208
0,04 0,16
0,03 0,15
0,019 0,114
0,011 0,066

Недостатком методики Шеннона – Фано является неоднозначность построения ОНК. В методике Хаффмена этого недостатка нет.

ІІ. Хаффмен предложил следующий метод построения ОНК:

1) Символы первичного алфавита выписываются в порядке убывания вероятностей.

2) Последние nсимволов, где 2 £ n £ m и N — n / m — 1 — целое число, объединяют в некоторый новый символ с вероятностью, равной сумме вероятностей объединяемых символов.

3) Последние символы с учетом образованного символа вновь объединяют и получают новый, вспомогательный, символ.

4) Опять выписывают символы в порядке убывания вероятноьстей с учетом вспомогательного символа и т. д. До тех пор, пока вероятности m оставшихся символов после N — n/m — 1-го выписывания не дадут в сумме 1.

На практике обычно не производят многократного выписывания вероятностей символов, а обходятся элементарными геометрическими построениями, суть которых для кодов с числом качественных признаков m = 2 сводится к тому, что символы кодируемого алфавита попарно объединяются в новые символы, начиная с символов, имеющих наименьшую вероятность, а затем, с учетом вероятностей вновь образованных символов, опять производят попарное объединение символов с наименьшими вероятностями и таким образом строят двоичное кодовое дерево, в вершине которого стоит символ с вероятностью 1.

Читайте также:  Портит ли зрение чтение при плохом освещении

Пример.

Построить методом Хаффмена оптимальный код для алфавита со следующим распределением вероятностей появления букв в тексте: A = 0,5; B = 0,15; C = 0,12; D = 0,1;

Сначала находят буквы с наименьшими вероятностями 0,02 (H) и 0,03 (G), затем проводят от них линию к точке, в которой вероятность появления буквы G равна 0,05. Затем берут две наименьшие вероятности 0,04 (F) и 0,04 (E) и получают новую точку с вероятностью 0,08.

Теперь наименьшими вероятностями обладают точки, соответствующие вспомогательным символам с вероятностями 0,05 и 0,08. Соединяем их линией с новой точкой, соответствующей вспомогательному символу с вероятностью 0,13.

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

Обозначим каждую верхнюю линию (см. рисунок 2.1.1) цифрой 1, а нижнюю — цифрой 0. Получим ОНК, который для каждого слова представляет собой последовательность нулей и единиц, которые встречаются по пути к данному слову от конечной точки (1,00).

Полученные коды представлены в таблице 5.6.

Таблица 5.6 – Двоичный код Хаффмена для восьми сообщений

Буква Вероятность ОНК Число знаков в кодовом слове pili
A B C D E F G H 0,50 0,15 0,12 0,10 0,04 0,04 0,03 0,02 0 0 1 0 1 1 0 1 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0,50 0,45 0,36 0,30 0,20 0,20 0,15 0,10

Построить код Хаффмена для передачи сообщений при помощи трех частот f1, f2, f3, если символы первичного алфавита встречаются в сообщениях со следующими вероятностями: А = 0,24; Б = 0,18; В = 0,38;

Таблица 5.7 – Троичный код Хаффмена для семи сообщений

Буква Вероятность Дерево Код
В А Б Г Д Е Ж 0,38 0,24 0,18 0,1 0,06 0,02 0,02 f1 f2 f3f1 f3f2 f3f3f1 f3f3f2 f3f3f3

Полученный код легко декодируется, так как ни один код не начинается с f1и f2, кроме одного одноразрядного кода.

К недостаткам алгоритма относятся:

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

второй – непостредственно для кодирования.

2. Необходимость хранения вместе с сжатым файлом декодирующего дерева для возможности восстановления файла.

Дата добавления: 2014-01-06 ; Просмотров: 6998 ; Нарушение авторских прав? ;

Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет

источник

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

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

Фактически для передачи сообщения достаточно иметь длину кодовой комбинации

где N — общее количество передаваемых сообщений.

L можно представить и как

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

В общем случае, избыточность от округления:

Избыточность необходима для повышения помехоустойчивости кодов и ее вводят искусственно в виде добавочных

Для уменьшения избыточности используют оптимальные коды. При построении оптимальных кодов наибольшее распространение получили методики Шеннона-Фано и Хаффмена. Согласно методике Шеннона-Фано построение оптимального кода ансамбля из сообщений сводится к следующему:

1) множество из сообщений располагается в порядке убывания вероятностей;

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

Если равной вероятности в подгруппах нельзя достичь, то их делят так, чтобы в верхней части (верхней подгруппе) оставались символы, суммарная вероятность которых меньше суммарной вероятности символов в нижней части (нижней подгруппе);

3) первой группе присваивается символ 0, а второй группе — символ 1;

4) каждую из образованных подгрупп делят на две части таким образом, чтобы суммарные вероятности вновь образованных подгрупп были по возможности равны;

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

Построенный код называют оптимальным неравномерным кодом (ОНК).

1) рассчитывается первоначальные вероятности для неравновероятных символов алфавита.

2) выполняет нормирование указанных вероятностей.

3) рассчитывается энтропия алфавита из равновероятных символов.

4) производится расчет энтропии алфавита с неравновероятными символами и недогруженность в этом случае.

5) с учетом заданных длительностей символов вычисляется скорость передачи и избыточность.

6) строится оптимальный код по методу Шеннона-Фано.

pi )

p1 = 0,1500 p2 = 0,0065 p3 = 0,0071 p4 = 0,0078 p5 = 0,0086 p6 = 0,0095 p7 = 0,0105 p8 = 0,0118 p9 = 0,0132 p10 = 0,0150 p11 = 0,0171 p12 = 0,0198 p13 = 0,0231 p14 = 0,0273 p15 = 0,0327 p16 = 0,0400 p17 = 0,0500 p18 = 0,0643 p19 = 0,0857 p20 = 0,1200 p21 = 0,1800 p22 = 0,3000 p23 = 0,6000 p24 = 1,8000
рi = 3,6 p1 =0,0417 p2 =0,0018 p3 =0,0020 p4 =0,0022 p5 =0,0024 p6 =0,0026 p7 =0,0029 p8 =0,0033 p9 =0,0037 p10 =0,0042 p11 =0,0048 p12 =0,0055 p13 =0,0064 p14 =0,0076 p15 =0,0091 p16 =0,0111 p17 =0,0139 p18 =0,0179 p19 =0,0238 p20 =0,0333 p21 =0,0500 p22 =0,0833 p23 =0,1667 p24 =0,5000

Определение количества информации на символ сообщения, составленного из данного алфавита.

Количество информации на символ сообщения для символов данного алфавита, встречающихся с равными вероятностями:

Hmax = log2 24 = ln 24/ln 2 = 4,5850 бит/символ

Количество информации на символ сообщения для символов данного алфавита, встречающихся в сообщении с разными вероятностями:

H = – (0,0417*log2 0,0417 + 0,0018*log2 0,0018 + 0,020*log2 0,0020 + 0,0022*log2 0,0022 + 0,0024*log2 0,0024 + 0,0026*log2 0,0026 + 0,0029*log2 0,0029 + 0,0033*log2 0,0033 + 0,0037*log2 0,0037 + 0,0042*log2 0,0042 + 0,0048*log2 0,0048 + 0,0055*log2 0,0055 + 0,0064*log2 0,0064 + 0,0076*log2 0,0076 + 0,0091*log2 0,0091 + 0,0111*log2 0,0111 + 0,0139*log2 0,0139 + 0,0179*log2 0,0179 + 0,0238*log2 0,0238 + 0,0333*log2 0,0333 + 0,0500*log2 0,0500 + 0,0833*log2 0,0833 + 0,1667*log2 0,1667 + 0,5000*log2 0,5000) =

Недогруженность символов в данном случае:

N = Нmax – Н = 4,5850 – 2,6409 = 1,9441 бит/символ

Вычисление скорости передачи информации.

С= – (0,0417*log2 0,0417 + 0,0018*log2 0,0018 + 0,020*log2 0,0020 + 0,0022*log2 0,0022 + 0,0024*log2 0,0024 + 0,0026*log2 0,0026 + 0,0029*log2 0,0029 + 0,0033*log2 0,0033 + 0,0037*log2 0,0037 + 0,0042*log2 0,0042 + 0,0048*log2 0,0048 + 0,0055*log2 0,0055 + 0,0064*log2 0,0064 + 0,0076*log2 0,0076 + 0,0091*log2 0,0091 + 0,0111*log2 0,0111 + 0,0139*log2 0,0139 + 0,0179*log2 0,0179 + 0,0238*log2 0,0238 + 0,0333*log2 0,0333 + 0,0500*log2 0,0500 + 0,0833*log2 0,0833 + 0,1667*log2 0,1667 + 0,5000*log2 0,5000) /

(1*0,0417 + 2*0,0018 + 3*0,020 + 4*0,0022 + 5*0,0024 + 6*0,0026 + 7*0,0029 + 8*0,0033 + 9*0,0037 + 10*0,0042 + 11*0,0048 + 12*0,0055 + 13*0,0064 + 14*0,0076 + 15*0,0091 + 16*0,0111 + 17*0,0139 + 18*0,0179 + 19*0,0238 + 20*0,0333 + 21*0,0500 + 22*0,0833 + 23*0,1667 + 24*0,5000) = 0,1244 бит/сек

Избыточность сообщений, составленных из данного алфавита.

D = 1 – (Н/Нmax ) = 1 – (2,6409 / 4,5850) = 0,4240

Построение оптимального кода

1 p24=0,5000 0,5
2 p23=0,1667 0,5 1 0,25 1 0,1666 1 111
3 p22=0,0833 1 1 0,0833 110
4 p21=0,0500 1 0,25 0,05 1 0 1000
5 p1=0,0417 1 0,0690 1 0,0357 1 10011
6 p20=0,0333 1 0,1190 1 0,0333 10010
7 p19=0,0238 1 1 1 0,0428 1 0,0178 1 101111
8 p18=0,0179 1 1 1 1 0,025 0,0138 1011100
9 p17=0,0139 1 1 1 0,025 1 101101
10 p16=0,0111 1 1 0,0666 1 1 101110
11 p15=0,0091 1 1 0,0642 1 0,0090 1 1010011
12 p14=0,0076 1 1 1 0,0102 0,0054 10100100
13 p13=0,0064 1 1 0,0166 0,0064 1 1010001
14 p12=0,0055 1 1 0,0166 1 0,0064 1 1010011
15 p11=0,0048 1 1 0,0333 1 1 1 0,0047 1 10101111
16 p10=0,0042 1 1 1 1 0,0088 1 0,0032 101011100
17 p9=0,0037 1 1 1 1 0,0078 0,0036 1 10101101
18 p8=0,0033 1 1 1 1 0,0078 1 0,0036 10101110
19 p7=0,0029 1 1 1 1 10101010
20 p6=0,0026 1 1 1 0,0167 1 0,0026 1 0,0026 1 101010111
21 p5=0,0024 1 1 1 0,0147 1 1 0,0024 101010110
22 p4=0,0022 1 1 1 0,0022 10101000
23 p3=0,0020 1 1 1 0,0038 1 0,0020 1 101010011
24 p2=0,0018 1 1 1 0,0083 1 0,0018 101010010
Буква Вероятность появления буквы Кодовые слова Число знаков в кодовом слове Pi ·li
A[1] (p24) 0,5000 1 0,5
A[2] (p23) 0,1667 111 3 0,50001
A[3] (p22) 0,0833 110 3 0,2500
A[4] (p21) 0,0500 1000 4 0,2000
A[5] (p1) 0,0417 10011 5 0,2083
A[6] (p20) 0,0333 10010 5 0,1667
A[7] (p19) 0,0238 101111 6 0,1429
A[8] (p18) 0,0179 1011100 7 0,1250
A[9] (p17) 0,0139 101101 6 0,0833
A[10] (p16) 0,0111 101110 6 0,0667
A[11] (p15) 0,0091 1010011 7 0,0636
A[12] (p14) 0,0076 10100100 8 0,0606
A[13] (p13) 0,0064 1010001 7 0,0449
A[14] (p12) 0,0055 1010011 7 0,0385
A[15] (p11) 0,0048 10101111 8 0,0381
A[16] (p10) 0,0042 101011100 9 0,0375
A[17] (p9) 0,0037 10101101 8 0,0294
A[18] (p8) 0,0033 10101110 8 0,0261
A[19] (p7) 0,0029 10101010 8 0,0234
A[20] (p6) 0,0026 101010111 9 0,0237
A[21] (p5) 0,0024 101010110 9 0,0214
A[22] (p4) 0,0022 10101000 8 0,0173
A[23] (p3) 0,0020 101010011 9 0,0178
A[24] (p2) 0,0018 101010010 9 0,0163

Определение количества информации на символ сообщения. Построение оптимального кода.

источник