Код Шеннона- Фано
Как известно, большинство сообщений, формируемых источником, содержат избыточность. Удаление или уменьшение избыточности является одной из задач кодирования. Кодирование, которое осуществляет удаление или уменьшение избыточности из закодированных сообщений, называется эффективным.
Очень нуженкод реализаций метода Шеннона-Фано на с++. Разборчивый и не сложный код только.
Не могу доделать код Шеннона-Фано - c# Суть метода описана здесь. Метод оптимального кодирования Шеннона-Фано позволяет минимизировать избыточность кода. Под кодированием понимается процесс отображения одного набора.
Возможность эффективного кодирования основана на теореме Шеннона, согласно которой: Минимальное среднее количество элементов на выходе кодирующего устройства, соответствующее одному символу дискретного сообщения, можно сделать сколь угодно близким к максимальной энтропии источника. Эффективное кодирование осуществляется с применением неравномерных кодов, в которых более короткие кодовые комбинации соответствуют более вероятным символам сообщения, а более длинные — менее вероятным символам. Основными требованиями, предъявляемыми к эффективному коду, являются:. однозначность декодирования, т. Каждому символу кодируемого сообщения должна соответствовать своя кодовая комбинация и для всех символов комбинации должны быть различны;.
Код Шеннона Фано Для Русского Алфавита
в среднем на один символ сообщения должно приходиться минимальное число элементов кодовой комбинации эффективного кода;. ни какая более короткая комбинация эффективного кода не должна являться началом другой, более длинной комбинации. Рассмотрим построение эффективного кода на примере кода Шеннона-Фано и кода Хаффмена. Источник вырабатывает восемь сообщений с вероятностями Р(а 1) = Р(а 4) =0,25; Р(а 5) = Р(а 7) = 0,125; Р(а 2) = Р(а 3) = Р(а 6) = Р(а 8) = 0,0625.
Осуществить эффективное кодирование кодом Шеннона-Фано. Для построения кода необходимо составить таблицу 1.
Заполнение таблицы осуществляется в три этапа. Записываются сообщения a i в порядке убывания их вероятностей (более вероятные вверху, менее вероятные внизу). Все сообщения делятся на две группы, таким образом, чтобы в каждой группе суммарные вероятности были примерно равны.
Верхней группе присваивается ноль нижней единица. Затем каждая группа разбивается на две подгруппы, также, по возможности, с равными суммарными вероятностями. Верхней подгруппе присваивается ноль, нижней единица, и т. Деление подгрупп производится до тех пор, пока в каждой подгруппе не окажется по одному элементу a i. Записываются кодовые комбинации, соответствующие каждому элементу сообщения, при этом 1-я группа соответствует старшему разряду, 2-я следующему и т. По всем столбцам.
Если в столбце элемента a i отсутствует символ «0» или «1», то в соответствующем разряде кодовой комбинации он не пишется. Как видно из таблицы, каждому элементу a i соответствует своя, нигде не повторяющаяся, кодовая комбинация.
Ни одна более короткая кодовая комбинация не является началом другой более длинной. При этом более вероятные символы сообщения имеют более короткие комбинации, а менее вероятные — более длинные. Определим, удалена ли избыточность в результате кодирования. Энтропия, приходящаяся на один символ сообщения, определяется как Максимальная энтропия источника формирующего восемь сообщений равна Н max(A) = log 2N a = log 2 1/8 = 3 бит / сообщ. Избыточность сообщения вырабатываемого источником равна c с = (Нmax(A) – Н(А))/Нmax(А) = (3 – 2,75)/3 = 0,09 Для определения избыточности сообщения после кодирования определим среднюю длину кодовой комбинации Энтропия, приходящаяся на один разряд кодовой комбинации, определяется как Нр(А) = Н(А)/n ср = 2,75/2,75 = 1 бит/разряд Максимальная энтропия на выходе двоичного дискретного источника равна Нmax(А) = log 22 = 1 бит/сообщ. Определим коэффициент избыточности источника. C с = (1 – 1)/1 = 0 Таким образом, избыточность удалена.
По приведенным в примере 1 данным необходимо осуществить эффективное кодирование кодом Хаффмена. Построение данного кода, также удобно оформить в виде таблицы 2. Таблица заполняется следующим образом. Записываются сообщения a i в порядке убывания их вероятностей (более вероятные вверху, менее вероятные внизу).
Строится дерево кода, для этого два сообщения с наименьшей вероятностью (снизу таблицы) объединяются в группу. Верхней ветви присваивается единица, нижней? Если четыре символа имеют одинаковую минимальную вероятность, то организуются две одинаковые группы. Затем формируется следующая группа: нижняя ветвь графа исходит из предыдущей группы, а верхняя? Из следующего элемента, расположенного на одну позицию выше (этот элемент может иметь большую вероятность, или такую же, как и в предыдущей группе). Верхней ветви присваивается единица, нижней? Такая организация групп продолжается до тех пор, пока не образуется последняя группа с элементом имеющим наибольшую вероятность ( в самом верху таблицы).
Формируются кодовые комбинации, для этого записывают значение ветвей графа справа налево. N ср = 3,125.
Кодирование методом Шеннона-Фано Путь: » » Метод Шеннона-Фано Кодирование методом Шеннона-Фано Шаг 1. Символы исходного алфавита упорядочиваются по невозрастанию вероятностей. В результате получаем последовательность (a i1.,a iN).
В этой последовательности для всех j = 1, 2,:, N - 1 выполняется соотношение a ij ≥ a ij+1 Шаг 2. Переменной-счётчику t присваивается значение 1: t:= 1. Рассматриваемую последовательность разбиваем на M групп, не меняя порядка следования символов, так чтобы суммарные вероятности символов в каждой группе были примерно одинаковы и максимально близки к 1/M. Получаем совокупность подпоследовательностей G 1, G 2., G M: G1 = (a i1, a i2,:,a i k1), G2 = (a i k1+1, a i k1+2.,a i k2),: Шаг 4. Формируем t-й символ кодовых слов.
Всем символам из подпоследовательности G S приписываем символ b S, s = 1, 2., M. Переменная-счётчик увеличивается на 1: t:= t + 1.
Просматриваем все группы- подпоследовательности. Если некоторая группа G S состоит из одного символа a j то для этого a j процесс построения кодового слова считается законченным. Для каждой из этих групп, содержащих по 2 и более символов, выполняем действия, соответствующие Шагу 3 и Шагу 4. В результате чего получаем очередные t-е символы кодовых слов. После просмотра всех групп, осуществляется переход к Шагу 5. Процесс работы алгоритма заканчивается, когда все группы будут содержать ровно по одному символу исходного алфавита.
Обратим внимание на ряд особенностей, которые нужно иметь в виду при практическом применении этого метода. При разбиении на группы не разрешается переставлять элементы с целью выравнивания сумм вероятностей. Порядок, полученный на Шаге 1, сохраняется в течение всего времени работы алгоритма. Разбиение на группы не всегда выполняется однозначным образом. Это связано с тем, что иногда некоторый 'пограничный' символ a i может быть присоединён к любой из двух подгрупп G S или G S+1 равноценным образом. Если a i присоединяется последним символом в G S, то в ней суммарная вероятность станет на p(a i) больше, чем в группе G S+1.
Избыточность Кода Шеннона-фано
Если же a i включить первым символом в G S+1, то большая сумма вероятностей будет в G S+1. Подобная ситуация может возникнуть не один раз, следовательно, результат кодирования однозначно не определяется. Можно получить несколько равноценных между собой кодов для одного и того же алфавита. Иногда с целью получения однозначности вводят дополнительные условия.
Префиксный Код
Например, можно потребовать, чтобы большее значение суммы '%`.ob.ab%) было в группе с меньшим номером. Однако такое требование не является обязательным. Следует на всех шагах придерживаться одинаковой последовательности приписывания символов кодового алфавита группам символов исходного алфавита. Эту последовательность приписывания следует зафиксировать до начала работы алгоритма. Возможны различные способы, но обычно придерживаются следующего правила: символам из группы с номером S приписывают S-й символ кодового алфавита. Это правило присутствует и в приведённом выше алгоритме.