Вопрос 48.doc
Оценка 4.9

Вопрос 48.doc

Оценка 4.9
doc
13.05.2020
Вопрос 48.doc
Вопрос 48.doc

Префиксные коды, условие Фано.

Как следует из названия, знаки первичного алфавита (например, русского) кодируются комбинациями символов двоичного алфавита (т.е0 и 1), причем, длина кодов и, соответственно, длительность передачи отдельного кода, могут различаться. Длительности элементарных сигналов при этом одинаковы. Очевидно, для передачи информации, в среднем приходящейся на знак первичного алфавита, необходимо время К(A,2). Таким образом, задачу оптимизации неравномерного кодирования можно сформулировать следующим образом: построить такую схему кодирования, в которой суммарная длительность кодов при передаче (или суммарное число кодов при хранении) данного сообщения была бы наименьшей.

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

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

Параллельно должна решаться проблема различимости кодов.

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

00100010000111010101110000110

Каким образом она может быть декодирована? Если бы код был равномерным, приемное устройство просто отсчитывало бы заданное (фиксированное) число элементарных сигналов (например, 5, как в коде Бодо) и интерпретировало их в соответствии с кодовой таблицей. При использовании неравномерного кодирования возможны два подхода к обеспечению различимости кодов. Первый состоит в использовании специальной комбинации элементарных сигналов, которая интерпретируется декодером как разделитель знаков. Второй - в применении префиксных кодов.

Рассмотрим подробнее каждый из подходов.

Неравномерный код с разделителем

Условимся, что разделителем отдельных кодов букв будет последовательность 00 (признак конца знака), а разделителем слов - 000 (признак конца слова - пробел). Довольно очевидными оказываются следующие правила построения кодов:

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

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

• код буквы (кроме пробела) всегда должен начинаться с 1;

• разделителю слов (000) всегда предшествует признак конца знака; при этом реализуется последовательность 00000 (т.е., если в конце кода встречается комбинация ...000 или ...0000, они не воспринимаются как разделитель слов); следовательно, коды букв могут оканчиваться на 0 или 00 (до признака конца знака).

Длина всех кодовых цепочек лежит в пределах 0<=Xi<=8.

Средняя длина кода K(A,2).

Избыточность кода составляет Q=0,14.

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

Неравномерный код может быть однозначно декодирован, если никакой из кодов не совпадает с началом (префиксом ) какого-либо иного более длинного кода.

Например, если имеется код 110, то уже не могут использоваться коды 1, 11, 1101, 110101 и пр. Если условие Фано выполняется, то при прочтении (расшифровке) закодированного сообщения путем

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

 

Алгоритмы построения префиксных кодов Шеннона-Фано и Хаффмана.

Данный вариант кодирования был предложен в 1948-1949 гг. независимо Р. Фано и К. Шенноном и по этой причине назван по их именам. Рассмотрим схему на следующем примере: пусть имеется первичный алфавит А, состоящий из шести знаков a1 ...a6 с вероятностями появления в сообщении, соответственно, 0,3; 0,2; 0,2; 0,15; 0,1; 0,05. Расположим эти знаки в таблице в порядке убывания вероятностей (см. табл. 3.2). Разделим знаки на две группы таким образом, чтобы суммы вероятностей в каждой из них были бы приблизительно равными. В нашем примере в первую группу попадут а1 и а2 с суммой вероятностей 0,5 - им присвоим первый знак кода "0". Сумма вероятностей для остальных четырех знаков также 0,5; у них первый знак кода будет "1". Продолжим деление каждой из групп на подгруппы по этой же схеме, т.е. так, чтобы суммы вероятностей на каждом шаге в соседних подгруппах были бы возможно более близкими. В результате получаем:

знак

Р

Разряды кода

Код

1

2

3

4

а1

0,3

0

0

 

 

00

а2

0,2

0

1

 

 

01

а3

0,2

1

0

 

 

10

а4

0,15

1

1

0

 

110

а5

0,10

1

1

1

0

1110

а6

0,05

1

1

1

1

1111

Из процедуры построения кодов легко видеть, что они удовлетворяют условию Фано и, следовательно, код является префиксным. Средняя длина кода равна:

К(А,2) = 0,3*2 + 0,2*2 + 0,2*2 + 0,15*3 + 0,1 *4 + 0,05*4 = 2,45 = 2,390 бит. Получаем избыточность кода Q(A,2) = 0,0249, т.е. около 2,5%. Однако, данный код нельзя считать оптимальным, поскольку вероятности появления 0 и 1 неодинаковы (0,35 и 0,65, соответственно). Применение изложенной схемы построения к русскому алфавиту дает избыточность кода 0,0147.

Префиксный код ХаФФмана

Способ оптимального префиксного двоичного кодирования был предложен Д. Хаффманом. Построение кодов Хаффмана мы рассмотрим на том же примере. Создадим новый вспомогательный алфавит A, объединив два знака с наименьшими вероятностями (а5 и а6) и заменив их одним знаком (например, а(1)); вероятность нового знака будет равна сумме вероятностей тех, что в него вошли, т.е. 0,15; остальные знаки исходного алфавита включим в новый без изменений; общее число знаков в новом алфавите, очевидно, будет на 1 меньше, чем в исходном. Аналогичным образом продолжим создавать новые алфавиты, пока в последнем не останется два знака; ясно, что количество таких шагов будет равно N - 2, где N - число знаков исходного алфавита (в нашем случае N = 6, следовательно, необходимо построить 4 вспомогательных алфавита). В промежуточных алфавитах каждый раз будем переупорядочивать знаки по убыванию вероятностей.

Теперь в обратном направлении проведем процедуру кодирования. Двум знакам последнего алфавита присвоим коды 0 и 1 (которому какой - роли не играет; условимся, что верхний знак будет иметь код 0, а нижний - 1). В нашем примере знак а1 алфавита A(4), имеющий вероятность 0,6 , получит код 0, а а2 вероятностью 0,4 - код 1. В алфавите А(3) знак а1 получает от а1 его вероятность 0,4 и код (1); коды знаков а2и а3, происходящие от знака а1(из A(4)) с вероятностью 0,6, будут уже двузначным: их первой цифрой станет код их «родителя» (т.е. 0), а вторая цифра – как условились - у верхнего 0, у нижнего - 1; таким образом, а2 будет иметь код 00, а а3 - код 01.

Из процедуры построения кодов вновь видно, что они удовлетворяют условию Фано и, следовательно, не требуют разделителя.

Средняя длина кода, как и в предыдущем примере оказывается:

К(А,2) = 0,3*2 + 0,2*2 + 0,2*2 +0,15*3 + 0,1*4 + 0,05*4 = 2,45.

Избыточность снова оказывается равной О(А,2) = 0,0249, однако, вероятности 0 и 1 сблизились (0,47 и 0,53, соответственно). Более высокая эффективность кодов Хаффмана по сравнению с кодами Шеннона-Фано становится очевидной, если сравнить избыточности кодов для какого-либо естественного языка. Код Хаффмана важен в теоретическом отношении, поскольку можно доказать, что он является самым экономичным из всех возможных, т.е. ни для какого метода алфавитного кодирова­ния длина кода не может оказаться меньше, чем код Хаффма­на .

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

Адаптивное кодироваие.

В этом случае двоичный код первичного алфавита строится цепочками равной длины, т.е. со всеми знаками связано одинаковое количество информации равное (А) = Iog2 N. Формировать признак конца знака не требуется, поэтому для определения длины кода можно воспользоваться формулой К(А,2) > Iog2 N. Приемное устройство просто отсчитывает оговоренное заранее количество элементарных сигналов и интерпретирует цепочку (устанавливает, какому знаку она соответствует), соотнося ее с таблицей кодов. Правда, при этом недопустимы сбои, например, пропуск (непрочтение) одного элементарного сигнала приведет к сдвигу всей кодовой последовательности и неправильной ее интерпретации; решается проблема путем синхронизации передачи. С другой стороны, применение равномерного кода оказывается одним из средств контроля правильности передачи

Примером равномерного алфавитного кодирования является телеграфный код Бодо, пришедший на смену азбуке Морзе. Исходный алфавит должен содержать не более 32-х символов; тогда К(А,2) = log2 32 = 5, т.е. каждый знак первичного алфавита содержит 5 бит информации и кодируется цепочкой из 5 двоичных знаков.

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

• 26 х 2 = 52 букв латинского алфавита (с учетом прописных и строчных);

• 33 х 2 = 66 букв русского алфавита;

• цифры 0.. .9 - всего 10;

• знаки математических операций, знаки препинания, спецсимволы 20.

Получаем, что общее число символов N ~ 148. Теперь можно оценить длину кодовой цепочки: К(C,2) > Iog2148 > 7,21. Поскольку длина кода выражается целым числом, очевидно, К(C,2) = 8. Именно такой способ кодирования принят в компьютерных системах: любому символу ставится в соответствие код из 8 двоичных разрядов (8 бит). Эта последовательность сохраняется и обрабатывается как единое целое (т.е. отсутствует доступ к отдельному биту) - по этой причине разрядность устройств компьютера, предназначенных для хранения или обработки информации, кратна 8.

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

Байт наряду с битом может использоваться как единица измерения количества информации в сообщении. Один байт соответствует количеству информации в одном знаке алфавита при их равновероятном распределении. Этот способ измерения количества информации называется также объемным.

1 Кбайт = 210 байт = 1024 байт (килобайт)

1 Мбайт = 220 байт = 1024 Кбайт (мегабайт)

1 Гбайт = 230 байт = 1024 Мбайт (гигабайт)

1 Тбайт = 240 байт = 1024 Гбайт (терабайт)

Использование 8-битных цепочек позволяет закодировать 28=256 символов, что превышает оцененное выше N и, следовательно, дает возможность употребить оставшуюся часть кодовой таблицы для представления дополнительных символов.

 В персональных компьютерах и телекоммуникационных системах применяется международный байтовый код ASCII (American Standard Code for Information Interchange - «американский стандартный код обмена информацией»).

Блочное кодирование.

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

Пусть имеется словарь некоторого языка, содержащий п =16000 слов (это, безусловно, более чем солидный словарный запас!). Поставим в соответствие каждому слову равномерный двоичный код. Очевидно, длина кода может быть найдена из соотношения К(А,2) > log216000 > 13,97 = 14. Следовательно, каждое слово кодируется комбинацией из 14 нулей и единиц - получатся своего рода двоичные иероглифы.

Легко оценить, что при средней длине русского слова К(r,2) = 6,3 буквы (5,3 буквы + пробел между словами) средняя информация на знак первичного алфавита оказывается равной I(A) = K(A,2)/ К(r,2) 14/6,3  2,222 бит, что более чем в 2 раза меньше, чем 5 бит при равномерном алфавитном кодировании.

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

 


Префиксные коды, условие Фано.

Префиксные коды, условие Фано.

Длина всех кодовых цепочек лежит в пределах 0<=

Длина всех кодовых цепочек лежит в пределах 0<=

Длина всех кодовых цепочек лежит в пределах 0<=

Длина всех кодовых цепочек лежит в пределах 0<=

Из процедуры построения кодов вновь видно, что они удовлетворяют условию

Из процедуры построения кодов вновь видно, что они удовлетворяют условию

Компьютерный алфавит должен включать: • 26 х 2 = 52 букв латинского алфавита (с учетом прописных и строчных); • 33 х 2 = 66 букв…

Компьютерный алфавит должен включать: • 26 х 2 = 52 букв латинского алфавита (с учетом прописных и строчных); • 33 х 2 = 66 букв…

Кодирование блоков понижает избыточность

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