Кодирование по методу шеннона

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

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

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

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

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

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

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

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

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

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

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

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

,

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

sernam.ru

Реферат: Кодирование - Xreferat.com - Банк рефератов, сочинений, докладов, курсовых и дипломных работ

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

Внесение избыточности за счет увеличения длины кодовой комбинации приводит к снижению скорости передачи информации.

Если скорость идеально использует канал, то

. (11)

Если кодовая комбинация длиной n содержит k информационных и m контрольных разрядов (n = k + m), то

.

Для кода ASCII n = 8 и k = 7

,

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

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

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

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

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

1 0 1 1 0 1 1 1

0 1 0 0 0 1 0 0

1 0 1 0 0 1 0 1

1 1 0 0 1 0 1 0

0 0 0 1 0 1 0 0

1 0 0 0 1 0 0

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

Проверка на четность широко используется на ЭВМ, как на аппаратном, так и на программном уровне.

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

Пример 1. Символы алфавита источника кодируются семиразрядным двоичным кодом с весом кодовых векторов (количеством единиц в кодовой комбинации) w = 3. Определить необходимую мощность кода и его избыточность.

Решение: Мощность семиразрядного кода равна N = 27 = 128.

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

Избыточность кода равна R = 1 – log2K/ log2N = 0,265.

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

Семенюк В. В. Экономное кодирование дискретной информации. – СПб.: СПб ГИТМО (ТУ), 2001;

Мастрюков Д. Алгоритмы сжатия информации. Ч. 1. Сжатие по Хаффмену //Монитор, 1993. – № 7 – 8 – С. 14 – 20;

Мастрюков Д. Алгоритмы сжатия информации. Ч. 2. Арифметическое кодирование //Монитор, 1994 – № 1 – С. 20 – 23;

Ф.Дж.Мак-Вильямс, Н.Дж.А.Слоэн, Теория кодов, исправляющих ошибки, Москва, “Связь”, 1979.

.Лидл, Г.Нидеррайтер, Конечные поля, Т. 1,2, Москва, “Мир”, 1988.

Т.Касами, Н.Токура, Е.Ивадари, Я.Инагаки, Теория кодирования, Москва, “Мир”, 1978.

У.Петерсон, Э.Уэлдон, Коды, исправляющие ошибки, Москва, “Мир”, 1976.

Э.Берлекэмп, Алгебраическая теория кодирования, Москва, “Мир”, 1971.

Дискретная математика и математические вопросы кибернетики. Т.1. /Ю.Л. Васильев, Ф. Я. Ветухновский, В. В. Глаголев, Ю. И. Журавлев, В. И. Левенштейн, С. В. Яблонский. Под общей редакцией С. В. Яблонского и О. Б. Лупанова. – М.: Главная редакция физико – математической литературы изд–ва «Наука», 1974

Лидовский В. В. Теория информации: Учебное пособие. — М.: Компания Спутник+, 2004

Похожие рефераты:

xreferat.com

Исследование эффективного кодирования. Метод Шеннона-Фано

Понятие эффективного кодирования информации. Разработка программы для построения кода Шеннона-Фано, в котором вероятности появления букв подчиняются определенному закону. Интерфейс и листинг программы. Поле изображения закодированного сообщения.

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Подобные документы

  • Общее число неповторяющихся сообщений. Вычисление скорости передачи информации и пропускной способности каналов связи. Определение избыточности сообщений и оптимальное кодирование. Процедура построения оптимального кода по методике Шеннона-Фано. курсовая работа , добавлен 17.04.2009

  • Типы сжатия данных: с потерями (lossy) и без потерь (lossless). Сжатие с минимальной избыточностью. Кодирование методом Шеннона-Фано. Проверка работы программы по сжатию файлов формата bmp и xls. Реализация на Delphi алгоритма сжатия Шеннона и Хаффмана. курсовая работа , добавлен 26.01.2011

  • Определение понятий кода, кодирования и декодирования, виды, правила и задачи кодирования. Применение теорем Шеннона в теории связи. Классификация, параметры и построение помехоустойчивых кодов. Методы передачи кодов. Пример построения кода Шеннона. курсовая работа , добавлен 25.02.2009

  • Определение среднего количества информации. Зависимость между символами матрицы условных вероятностей. Кодирование методом Шеннона–Фано. Пропускная способность канала связи. Эффективность кодирования сообщений методом Д. Хаффмана, характеристика кода. контрольная работа , добавлен 04.05.2016

  • Изучение методов кодирования Хаффмана, Фано. Модель информационной системы Шеннона. Среднестатистическая информационная емкость сообщений для эргодических источников с заданным распределением частот символов. Формулы Хартли для удельной емкости на символ. презентация , добавлен 19.10.2016

  • Краткий обзор основных теорий сжатия. Концепции идей и их реализация. Сжатие данных с использованием преобразования Барроуза-Вилера. Статический алгоритм Хафмана. Локально адаптивный алгоритм сжатия. Алгоритм Зива-Лемпеля (Welch) и метод Шеннона-Фано. практическая работа , добавлен 24.04.2016

  • Анализ эффективности способов кодирования. Средний размер одного разряда и средняя длина кодового слова. Кодирование по методу Хаффмена. Кодирование информации по методу Шенона-Фано. Построение кодового дерево для различных методов кодирования. контрольная работа , добавлен 15.10.2013

  • Кодирование и декодирование, преобразование дискретного сообщения в дискретный сигнал. Построение математической модели корректирующего кода. Образующая матрица информационного кода. Модульная структура программы. Спецификация на программные модули. курсовая работа , добавлен 28.11.2016

  • Основные понятия теории информации как науки. Среднее количество информации, приходящееся на 1 знак определяемое формулой Шеннона. Общая схема передачи сообщения. Пропускная способность канала. Булева алгебра и техническая реализация процесса вычисления. презентация , добавлен 13.08.2013

  • Понятие о кинематике. Относительность, траектория и виды движений. Движение тела, брошенного под углом к горизонту. Разработка компьютерной программы для моделирования. Описание интерфейса программы и программного кода. Инструкция пользования интерфейсом. курсовая работа , добавлен 25.11.2013

специальность 080801 Прикладная информатика в экономике

ЗАДАНИЕ

Тема проекта: Исследование эффективного кодирования. Метод Шеннона-Фано

Выполнила студентка

по дисциплине ``Теория информации и сигналов''

на тему ``Исследование квантования сигналов по уровню``

Выполнила студентка __Пащенко Андрей Васильевич_____

группы _10-К-ПИ-1______________________________________

Руководитель проекта д.тех.н.проф.Ключко В.И.__________

Нормоконтролер________________________________________

Пояснительная записка курсовой работы - 19 стр.

Количество рисунков - 2

Ключевые слова: КОДИРОВАНИЕ, МЕТОД, КОД

Объектом исследования работы является изучение эффективного кодирования.

Цель работы состоит в создании программы для реализации исследования эффективного кодирования.

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

Содержание

2. Требования к программному изделию

3. Описание программы

4. Результаты и листинг программы

Заключение

Список использованной литературы

Введение

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

В курсовой работе будет исследовано построение эффективного кода по методу Шеннона - Фано.

1. Теоретические сведения

Эффективное кодирование информации

Понятие о кодировании.

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

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

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

Исторически первый код, предназначенный для передачи сообщений, связан с именем изобретателя телеграфного аппарата Сэмюэля Морзе и известен всем как азбука Морзе. Другим кодом, столь же широко распространенным в телеграфии, является код Бодо. Оба они используют два различных элементарных сигнала. Такие коды принято называть двоичными.

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

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

Коды могут быть представлены формулой, геометрической фигурой, таблицей, графом, многочленом, матрицей и.т.д.

Представление кода числа А в виде многочлена для любой позиционной системы счисления есть сумма произведений коэффициента аi и веса xi i-го разряда кода:

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

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

Принципы эффективного кодирования.

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

Различают избыточность естественную и искусственную. Естественная избыточность характерна для первичных алфавитов, а искусственная - для вторичных.

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

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

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

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

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

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

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

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

Эффективными называются коды, представляющие кодируемые понятия кодовыми словами минимальной средней длины. В литературе вместо термина "эффективное кодирование" часто используют так же термины оптимальное или статистическое кодирование.

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

Для двоичных кодов

и разность (Lcp - H) будет тем меньше, чем больше Н, а H достигает максимума при равновероятных и взаимно независимых символах. Отсюда вытекают основные свойства эффективных кодов:

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

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

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

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

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

Построение эффективного кода по методу Шеннона-Фано.

Построение эффективного кода по методу Шеннона-Фано сводится к следующей процедуре:

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

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

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

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

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

В качестве примера построим код Шеннона - Фано, в котором вероятности появления букв подчиняются закону, представленному в таблице.

Выводы:

Число элементарных символов на букву сообщения с распределением вероятностей появления букв по закону Р=2-i возрастает в порядке убывания вдроятност?й как натуральный ряд чисел.

Кодовые слова одинаковой вероятности появления имеют равную длину.

Для ансамблей равновероятных сообщений эффективным является равномерный код.

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

Эффективность ОНК оценивают с помощью коэффициента статистического сжатия

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

который показывает, насколько используется статистическая избыточность передаваемого сообщения. Для рассмотренного примера Ксс=1.1; Коэ=1 .

2.Требования к программному изделию

2.1 Требования к функциональным характеристикам

Разработанная программа пригодна для исследования метода кодирования Шеннона - Фано.

2.2 Контроль входной и выходной информации

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

3.Описание программы

На рисунке показан внешний вид программы при запуске

кодирование информация шеннон фано

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

Также в программе находится поле для изображения закодированного сообщения.

4. Результаты и листинг программы

4.1 Листинг программы

otherreferats.allbest.ru

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

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

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

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

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

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

Теорема кодирования. Сообщения произвольного источника информации 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

Методы кодирования

Лабораторная работа №4 «Кодирование дискретных источников информации методом Шеннона-Фано»

Цель работы

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

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

Для передачи и хранения информации, как правило, используется двоичное кодирование. Если алфавит Aсостоит изNсимволов, то для их двоичного кодирования необходимо слово разрядностьюn, которая определяется

n =log2 N, где значение округляется до верхнего целого числа.

Это справедливо при использовании стандартных кодовых таблиц, например, ASCII, KOI-8 и т.п., обеспечивающих кодирование до 256 символов.

Если в используемом алфавите символов меньше, чем используется в стандартной кодовой таблице, то возможно использование некоторой другой таблицы кодирования если необходимо передавать или хранить сообщение, состоящее из символов кириллицы, цифр и семи символов разделителей {«.», «,», «:», «;», «!», « кавычки », «?»} ( всего 50 символов), мы можем воспользоваться способами кодирования:

  • Кодировать каждый символ в соответствии со стандартной кодовой таблицей, например, KOI-8R. По этой таблице n1 = 8;

  • Составить и использовать отдельную кодовую таблицу, это может быть некоторый усеченный вариант стандартной таблицы, не учитывающую возможность кодирования символов, не входящих в передаваемое сообщение, тогда необходимый размер кодового слова n2 = log2 N= log2 50=6, где значение округляется так же, как и при определении основной формулы разрядности.

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

Код строится следующим образом:

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

Можно вычислить среднее количество двоичных разрядов, используемых при кодировании символов по алгоритму Шеннона-Фано

где: A— размер (или объем) алфавита, используемого для передачи сообщения;

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

nср= 4,628325 бит

Iср = ∑ *p(ai) *n(ai) , гдеp(ai) - вероятностьp,n(ai) - число двоичных разрядов в кодовой комбинации, соответствующей символуai.

nср =∑ p(ai)* n(ai) ,

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

Т – 0111

StudFiles.ru

Принцип построения оптимального кода Шеннона-Фано следующий.

  1. Сообщения, входящие в ансамбль, располагаются в строку (в столбец) по мере убывания вероятностей.
  2. Выбирается основание кода K.
  3. Все сообщения ансамбля разбиваются на K групп с равными суммарными вероятностями внутри каждой группы. Всем сообщениям первой группы в качестве первого символа присваивается 0, сообщениям второй группы – символ 1, а сообщениям K-й группы – символ (K – 1); тем самым обеспечивается равная вероятность появления всех символов 0, 1,…, K на первой позиции в кодовых словах.
  4. Каждая из групп делится на K подгрупп с равной суммарной вероятностью в каждой подгруппе. Всем сообщениям первых подгрупп в качестве второго символа присваивается 0, всем сообщениям вторых подгрупп – 1, а сообщениям K -х подгрупп – символ (K – 1).
  5. Процесс продолжается до тех пор, пока в каждой подгруппе не окажется по одной комбинации.

Пример 1. Пусть дан ансамбль сообщений

Построить двоичный оптимальный код.

Оптимальный код строится в соответствии с приведенными правилами:

Наиболее вероятное сообщение кодируется самым коротким сигналом.

Для двоичного кода условие оптимальности выглядит так:

С другой стороны,

То есть в данном случае nCP= HИ.

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

Пример 2. Дан ансамбль сообщений:

Построить двоичный оптимальный код.

Для данного кода

.

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

Коды Шеннона-Фано могут быть построены для любого основания K по той же методике.

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

Решение:

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

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

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

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

estohard.narod.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-й символ кодового алфавита. Это правило присутствует и в приведённом выше алгоритме.

algolist.manual.ru

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