Кодирование методом шеннона фано онлайн

Вопрос: Метод кодирования шенона фано. Помогите закодировать мое ФИо этим методом ( корнилов алексей олегович)

Шива

Помните, как ловко расправились с шифрованными письменами герои рассказов По и Дойла ("Золотой жук" и "Пляшущие человечки")? А всё - от наблюдательности своей! Подметили тот очевидный факт, что каждая буква в тексте имеет свою частоту. Мы это и сами интуитивно чувствуем. Буква "и" в любом отвлеченном тексте, например, встречается в сотни раз чаще, чем "ъ". И если любую подстановочную криптограмму подвергнуть частотному анализу, а затем присовокупить чуток логики - расшифровке поддаётся она очень легко. Но, отвлечёмся от детективной тематики и обратим внимание на такое свойство, как ЧАСТОТА ВСТРЕЧАЕМОСТИ различных элементов. Это свойство присуще любому относительно осмысленному множеству элементов - будь то мелодия (как последовательность звуков) или - картина (как сочетание различных мазков там, завитков, штрихов и линий) . А частота встречаемости различных букв в письменной речи, так она и вовсе выражена очень чётко.
Так вот, метод кодирования Шенона-Фано стоит на принципе экономии места. То есть, - наиболее часто встречаемые символы кодируем коротко, а те символы, что встречаются пореже – длинно. Потому что если наоборот – «палучица многа цыфар, ниасилят» . А как определить – что встречается пореже, а что – почаще? Можно, конечно, и на глазок. Но на глазок в матеметике не принято. Математики – оне народ точный – даже водку на глазок не наливают, а уж цифры – так это ж вааще святое. Надо точно и четко. Как? А с помощью дихтомии (не путать с лоботомией! ) – т. е. процесса разделения на два.
Вот, взять, к примеру Ваш текст «Корнилов Алексей Олегович» и применить к нему метод Шеннона-Фано то мы все символы, встречающиеся в нём разделим на две примерно равные группы – по 11 и 12 букв. Оговоримся сразу «и» = «й» .
В первую группу попадут буквы К*2,О*4,Р, Н, И*3 (итого11букв)
Во вторую – Л*3,В*2,А, Е*3,Г, Ч (итого 12 букв)
Первую гуппу тоже разобьём на две примерно равные подгруппы по 5 и 6 букв
В первой подгруппе будут буквы К*2 и О*4 (итого 6 букв) ,
Во второй – буквы Р, Н, И*3 (итого 5 букв)
Каждую из подгрупп опять половиним.
Первая подгруппа у нас распадается на 2 подподгруппы:
-К*2
-О*4
А вторая подподгруппа распадается на
-Р, Н
-И*2…
Словом, мы занимаемся тем, что делим каждое из двух получаемых подмножеств ещё раз на два аж до упора, до состояния полной неделимости…
После этого – мы попросту записываем «адреса» каждой из букв. То есть буква «К» -1-я группа, 1-я подгруппа, 1-я подподгруппа и 1-я подподгруппа (код – 1111), «адрес» буквы «О» - 1112 (первая группа, первая подгруппа, первая подподгрупа, вторая подподгрупа) . И таким вот нехитрым способом мы записываем «адреса» каждой буквы, превращая каждую из букв в кодовый символ.
Пааанравилось? Думаю - да! Это прикоооольна! Наслаждайтесь.

4.3.4. Кодирование источника дискретных сообщений методом Шеннона-Фано

4.3.4. Кодирование источника дискретных сообщений методом Шеннона-Фано

Кодирование методом Шеннона – Фано рассмотрим на примере. Пусть алфавит источника содержит шесть элементов {А, Б, В, Г, Д, Е}, появляющихся с вероятностями ,

Алгоритм построения сжимающего кода Шеннона – Фано заключается в следующем.

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

Таблица 4.2. Построение кода Шеннона-Фано

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

3. Верхняя группа кодируется символом «1», а нижняя – «0».

4. Каждая группа делится на две подгруппы с близкими суммарными вероятностями; верхняя подгруппа кодируется символом «1», а нижняя – «0».

5. Процесс деления и кодирования продолжается до тех пор, пока в каждой подгруппе не окажется по одному символу сообщения источника.

6. Записывается код для каждого символа источника; считывание кода осуществляется слева направо.

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

,

что меньше, чем при простейшем равномерном коде и незначительно отличается от энтропии источника.

sernam.ru

Код Шеннона-Фано

Оптимальное кодирование

{Код шеннона внизу}

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

Пример 1.

Пусть имеется случайная величина  X(x1,x2,x3,x4,x5,x6,x7,x8), имеющая восемь состояний  с распределением вероятностей

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

   Это         000, 001, 010, 011, 100, 101, 110, 111

Чтобы ответить, хорош этот код или нет, необходимо сравнить его с оптимальным значением, то есть определить энтропию

Определив избыточность L по формуле L=1-H/H0=1-2,75/3=0,084,  видим, что возможно сокращение длины кода  на 8,4%.

Возникает вопрос: возможно ли составить код, в котором на одну букву будет, в среднем приходится меньше элементарных символов.

Такие коды существуют. Это коды Шеннона-Фано и Хаффмана.

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

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

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

Код Шеннона-Фано

Пример 2. Закодируем буквы алфавита из примера 1 в коде Шеннона-Фано.

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

Средняя длина полученного кода будет равна

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

Пример 3{этот пример необязателен к списыванию, так для общего развития(прим.автор)} .

Возьмем 32 две буквы русского алфавита. Частоты этих букв известны. В алфавит включен и пробел, частота которого составляет 0,145. Метод кодирования представлен в таблице 4.2.

 Средняя длина данного кода будет равна, бит/букву;

Энтропия  H=4.42 бит/буква.  Эффективность полученного кода можно определить как отношение энтропии к средней длине кода. Она равна 0,994. При значении равном единице код является оптимальным. Если бы мы кодировали кодом равномерной длины , то эффективность была бы значительно ниже.

ra-scorpion.narod.ru

Код Шеннона - Фано

Дата добавления: 2016-03-21; просмотров: 377; Нарушение авторских прав

Метод двоичной системы счисления

Этот метод используется для построения наиболее экономного двоичного кода. В деся-тичной системе счисления каждое число представляется в виде суммы степеней числа 10: k = ak · 10k + ak1· 10k−1 + : : : + a0· 100, где числа ak; : : : ; a1; a0 - цифры числа,

принимающие значения от 0 до 9. Число N при этом обозначается последовательностью своих цифр akak1: : : a0. Аналогично этому число n можно представить в виде степе-ней числа 2: n = bl · 10l + : : : + b0· 100, где числа bl; : : : ; b0 - цифры числа, принимаю-щие значения 0 и 1. Число n обозначается последовательностью соответствующих цифр (6 = 1 22 + 1 21 + 0 20). Аналогично можно представить число в виде суммы степеней числа m - т.н. m-ичная система счисления.

Число k цифр в десятичной системе для записи числа n удовлетворяет неравенству 10k−1 6 n < 10k. В промежутке между 101 и 102 1 все цифры будут двузначными, а в промежутке 102::103 1 - трёхзначными и.т.д. В двоичной системе счисления число k удовлетворяет неравенству 2k−1 6 n < 2k, значит, число 6 - трёхзначное, а число 9 - че-тырёхзначное. При добавлении к двоичной записи ведущих нулей, мы придём к равно-мерномудвоичному коду дляn-буквенного алфавита с минимальной длиной кодовогообозначения k.

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

среднее число k элементарных сигналов, приходящихся на одну букву алфавита должно быть k >loglogmn . (из неравенства 2k−1 6 n < 2k⇒ log n < k · log m).

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

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

месте сообщения характеризуются вероятностями p1; : : : ; pn, причём pn = 1. Вероят-

n

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

Будем далее рассматривать только двоичные коды с элементарными сигналами 0 и 1. Среднее число k двоичных элементарных сигналов, приходящихся в закодированном сообщении на 1 букву исходного сообщения должно быть больше числа энтропии H : (k > H = −p1 log p1− p2 log p2− : : : − pn log pn), где H - энтропия опыта, состояще-го в распознавании одной буквы текста (энтропии одной буквы). Отсюда сразу следует, что при любом методе кодирования, для записи сообщения из M букв не меньше MH элементарных сигналов.

Загрузка...

Если вероятности p1; : : : ; pn - не все равны между собой, тогда H < log n = H( 0), по-этому учёт статистических закономерностей сообщения может позволить построить код более экономный, чем наилучший равномерный код, требующий M ·log n двоичных зна-ков для записи текста из M букв.

Код Шеннона - Фано

Для получения наиболее экономного кода удобно начать с того, чтобы расположить все n букв алфавита в один столбец в порядке убывания вероятностей.Затем все эти буквыследует разбить на 2 группы: верхнюю и нижнюю, так, чтобы суммарные вероятности для буквы сообщения принадлежать каждой из этих групп были возможно более близки одна к другой. Для букв первой группы в качестве первой цифры кодового обозначения используется 1, для букв второй группы - 0.

Далее, каждую из 2 полученных групп снова надо разделить на 2 части с возможно бо-лее близкой суммарной вероятностью. В качестве второй цифры кодового обозначения используют 1 или 0 в зависимости, принадлежит ли наша буква к первой или ко второй подгруппе. Процесс повторяется до тех пор, пока мы не придём к группам, каждая из ко-торых не содержит по одной букве. Такой метод кодирования сообщений был впервые предложен в 1948-49 гг. независимо друг от друга Р.Фано, К.Шенноном.

ПримерПустьn= 6(алфавит из6букв),вероятности которых равны соответственно

0:4; 0:2; 0:2; 0:1; 0:05; 0:05:

На первом этапе деления на группы отщепим одну первую букву, оставив во второй груп-пе все остальные. Далее, вторая буква составит первую подгруппу второй группы …

life-prog.ru

Расчет оптимального кода по методике Шеннона-Фано – Учил? Нет!

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

 бит/сек (20)

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

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

∆D=(Нмакс-Н) бит/символ

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

,

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

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

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

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

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

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

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

 дв. симв.

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

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

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

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

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

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

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

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

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

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

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

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

ПРАКТИЧЕСКАЯ ЧАСТЬ

uchil.net

Метод Шеннона – Фано

Дата добавления: 2013-12-23; просмотров: 1304; Нарушение авторских прав

Оптимальное кодирование

Теорема кодирования Шеннона. Методы побуквенного оптимального кодирования. Критерии оптимальности кода. Блочное кодирование. Единая система кодирования текстовой информации.

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

Вопрос существования таких кодов составляет суть одной из основных теорем теории информации – теоремы кодирования, доказанной К. Шенноном. Приведем одну из эквивалентных формулировок данной теоремы.

Теорема кодирования. Сообщения произвольного источника информации Z с энтропией H(Z) всегда можно закодировать последовательностями в алфавите B, состоящем из M символов, так, что средняя длина кодового слова будет сколь угодно близка к величине, но не меньше нее.

Доказательство этой теоремы в силу его сложности не рассматривается.

Теорема утверждает, что разность можно сделать как угодно малой. В этом и заключается задача методов оптимального кодирования.

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

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

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

Шаг 1. Упорядочиваем символы исходного алфавита в порядке невозрастания их вероятностей. (Записываем их в строку.)

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

Шаг 3. Приписываем группе слева "0", а группе справа "1" в качестве элементов их кодов.

Шаг 4. Просматриваем группы. Если число элементов в группе более одного, идем на Шаг 2. Если в группе один элемент, построение кода для него завершено.

Рис. 4.1. Двоичное дерево, соответствующее кодированию по методу Шеннона – Фано

Рассмотрим работу описанного алгоритма на примере кодирования алфавита , символы которого встречаются с вероятностями (0,25; 0,05; 0,25; 0,1; 0,25; 0,1) соответственно. Результат кодирования изображен на рис. 4.1.

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

life-prog.ru

Код Шеннона-Фано — Студопедия

Код Шеннона-Фано

Алгоритм Шеннона — Фано — один из первых алгоритмов сжатия, который впервые сформулировали американские учёные Шеннон и Фано (англ. Fano). Данный метод сжатия имеет большое сходство с алгоритмом Хаффмана, который появился на несколько лет позже. Алгоритм использует коды переменной длины: часто встречающийся символ кодируется кодом меньшей длины, редко встречающийся — кодом большей длины. Коды Шеннона — Фано префиксные, то есть никакое кодовое слово не является префиксом любого другого. Это свойство позволяет однозначно декодировать любую последовательность кодовых слов.

Кодирование Шеннона — Фано (англ. Shannon-Fano coding) — алгоритм префиксного неоднородного кодирования. Относится к вероятностным методам сжатия (точнее, методам контекстного моделирования нулевого порядка). Подобно алгоритму Хаффмана, алгоритм Шеннона — Фано использует избыточность сообщения, заключённую в неоднородном распределении частот символов его (первичного) алфавита, то есть заменяет коды более частых символов короткими двоичными последовательностями, а коды более редких символов — более длинными двоичными последовательностями.

Алгоритм был независимо друг от друга разработан Шенноном (публикация «Математическая теория связи», 1948 год) и, позже, Фано (опубликовано как технический отчёт).

Основные этапы

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

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

В префиксном коде для первой части алфавита присваивается двоичная цифра «0», второй части — «1».

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

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

studopedia.ru

Кодирование методом Шеннона-Фано

Шаг 1. Символы исходного алфавита упорядочиваются по невозрастанию вероятностей. В результате получаем последовательность (ai1,...,aiN).

В этой последовательности для всех j = 1, 2,:, N - 1 выполняется соотношение aij≥ aij+1

Шаг 2. Переменной-счётчику t присваивается значение 1: t := 1.

Шаг 3. Рассматриваемую последовательность разбиваем на M групп, не меняя порядка следования символов, так чтобы суммарные вероятности символов в каждой группе были примерно одинаковы и максимально близки к 1/M. Получаем совокупность подпоследовательностей G1, G2,..., GM:

G1 = (ai1, ai2, : ,ai k1),

G2 = (ai k1+1, ai k1+2, ... ,ai k2), :

Шаг 4. Формируем t-й символ кодовых слов. Всем символам из подпоследовательности GS приписываем символ bS, s = 1, 2,.., M.

Шаг 5. Переменная-счётчик увеличивается на 1: t := t + 1.

Шаг 6. Просматриваем все группы- подпоследовательности.

Если некоторая группа GS состоит из одного символа aj то для этого aj процесс построения кодового слова считается законченным.

Для каждой из этих групп, содержащих по 2 и более символов, выполняем действия, соответствующие Шагу 3 и Шагу 4. В результате чего получаем очередные t-е символы кодовых слов.

После просмотра всех групп, осуществляется переход к Шагу 5.

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

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

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

Второе. Разбиение на группы не всегда выполняется однозначным образом. Это связано с тем, что иногда некоторый "пограничный" символ ai может быть присоединён к любой из двух подгрупп GS или GS+1 равноценным образом. Если ai присоединяется последним символом в GS, то в ней суммарная вероятность станет на p(ai) больше, чем в группе GS+1. Если же ai включить первым символом в GS+1, то большая сумма вероятностей будет в GS+1. Подобная ситуация может возникнуть не один раз, следовательно, результат кодирования однозначно не определяется. Можно получить несколько равноценных между собой кодов для одного и того же алфавита. Иногда с целью получения однозначности вводят дополнительные условия. Например, можно потребовать, чтобы большее значение суммы "%`.ob-.ab%) было в группе с меньшим номером. Однако такое требование не является обязательным.

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

Обсудить на форуме»

distedu.ru

Статьи по теме