Провести эффективное кодирование ансамбля из восьми знаков m 8 используя метод шеннона фано

Обновлено: 10.01.2025

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

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

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

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

Убедимся в этом. Рассмотрим алфавит:

Буквы	Вероятность	Кодовые комбинации
Z₁	1/2	1	1
Z₂	1/4	01	1	2
Z₃	1/8	001		2	3
Z₄	1/16	0001			3
Z₅	1/32	00001
Z₆	1/64	000001
Z₇	1/128	0000001
Z₈	1/128	0000000

Вычислим энтропию алфавита:

Вычислим среднее число символов на букву по формуле:

В более общем случае для алфавита из 8 букв среднее число символов на букву будет меньше 3, но больше энтропии алфавита H(Z).

Например, для случая (см. таблицу 3.2):

Буквы	Вероятность	Кодовые комбинации
Z₁	0.22	11	1	2.1
Z₂	0.20	101		2.1
Z₃	0.16	100		2.1
Z₄	0.16	01	1	2.2
Z₅	0.10	001		2.2
Z₆	0.10	0001
Z₇	0.04	00001
Z₈	0.02	00000

l_ср = 0.22 · 2 + 0.2 · 3 + 0.16 · 3 + 0.16 · 2 + 0.1 · 3 + 0.1 · 4 + 0.04 · 5 + 0.02 · 5 = 0.38 · 2 + 3 · 0.46 + 0.4 + 0.3 = 0.76 + 1.38 + 0.7 = 2.84;

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

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

Поскольку P(Z₁) не равно P(Z₂), то последовательность из таких букв будет обладать избыточностью. Однако при буквенном кодировании мы никакого эффекта не получим.

Действительно, на передачу каждой буквы требуется либо 1, либо 0, то есть

Перейдем к кодированию блоками. Сначала рассмотрим блоки из 2-х букв.

Буквы	Вероятность	Кодовые комбинации
Z₁Z₁	0.81	1	1
Z₁Z₂	0.09	01	1	2
Z₂Z₁	0.09	001		2	3
Z₂Z₂	0.01	000		2	3

Так как буквы статистически не связаны, то вероятности появления блоков определяются как произведение вероятностей составляющих букв:

l_{ср.на блок} = 1 · 0.81 + 2 · 0.09 + 3 · 0.09 + 3 · 0.01 = 1.29;

Еще больший эффект дает кодирование блоков, содержащих по 3-и буквы:

Таблица 3.4

Буквы	Вероятность	Кодовые комбинации
Z₁Z₁Z₁	0.729	1
Z₂Z₁Z₁	0.081	011
Z₁Z₂Z₁	0.081	010
Z₁Z₁Z₂	0.081	001
Z₂Z₂Z₁	0.009	00011
Z₂Z₁Z₂	0.009	00010
Z₁Z₂Z₂	0.009	00001
Z₂Z₂Z₂	0.1	00000

l_{ср.на блок} = 1 · 0.729 + 3 · 0.0081 · (2 + 1) + 5 · (0.009 · 3 + 0.001) = 1.598;

Теоретически min H(Z) = 0,47 можно достигнуть при кодировании блоками, содержащими бесконечное число букв .

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

Рассмотренная нами методика Шеннона-Фено не всегда приводит к однозначному построению кода. Ведь при разбиении на подгруппы можно сделать большей по вероятности как верхнюю, так и нижнюю подгруппы.

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

Рубрика	Программирование, компьютеры и кибернетика
Вид	курсовая работа
Язык	русский
Дата добавления	06.08.2013
Размер файла	565,5 K

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

Министерство образования Российской Федерации

КУБАНСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ

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

на курсовое проектирование

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

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

Группы 10-К-ПИ-1 3 курса

Министерство образования Российской Федерации

КУБАНСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ

Кафедра ВТ и АСУ

к курсовому проекту (работе)

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

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

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

Допущен к защите_______________________________________

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

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

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

Количество приложений - 1

Количество источников - 3

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

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

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

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

Содержание

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Кликают по значку принтера Adobe PDF правой кнопкой мыши и выбирают Настройку печати. Все самое полезное размещено на вкладке Adobe PDF Settings.Можно выбрать шаблон, по которому будут создаваться файлы: High Quality (для создания PDF с высоким разрешением и повышенным качеством) или Smallest file size (для уменьшения объема файла). А можно создать собственные шаблоны, нажав на кнопку Edit.

Здесь же можно задать настройки безопасности. Можно установить отсутствие защиты (None) или предписать программе спрашивать об опциях безопасности при каждом создании PDF (Reconfirm security for each job) — в этом случае необходимо нажать расположенную рядом кнопку Edit и задать пароль, которым будет блокироваться доступ к новым файлам. Там же скрываются такие полезные функции, как парольный запрет некоторых возможностей работы с файлом: можно разрешить открытие файла, но запретить его печать или сохранение в др

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

Если исходный алфавит содержит m букв, то для построения равномерного кода с использованием k кодовых букв необходимо удовлетворить соотношение m £ k_q , где q - количество элементов в кодовой последовательности.

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

Например, при двоичном кодировании 32 букв русского алфавита используется q = log₂32 = 5 разрядов, на чем и основывается телетайпный код.

Кроме двоичных кодов, наибольшее распространение получили восьмеричные коды.

Пусть, например, необходимо закодировать алфавит, состоящий из 64 букв. Для этого потребуется q = log₂64 = 6 двоичных разрядов или q = log₈64 = 2 восьмеричных разрядов. При этом буква с номером 13 при двоичном кодировании получает код 001101, а при восьмеричном кодировании 15.

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

Единица каждого следующего разряда больше единицы предыдущего разряда в m раз, где m - основание системы счисления. Полное число получают, суммируя значения по разрядам:

где i - номер разряда данного числа; l - количество рядов; а_i - множитель, принимающий любые целочисленные значения в пределах от 0 до m-1 и показывающий, сколько единиц i - ого ряда содержится в числе.

Часто используются двоично-десятичные коды, в которых цифры десятичного номера буквы представляются двоичными кодами. Так, например, для рассматриваемого примера буква с номером 13 кодируется как 0001 0011. Ясно, что при различной вероятности появления букв исходного алфавита равномерный код является избыточным, т.к. его энтропия (полученная при условии, что все буквы его алфавита равновероятны): log_km = H₀

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

Например, для телетайпного кода Н0 = log_k m = log₂32 = 5 бит, а с учетом неравномерности появления различных букв исходного алфавита Н » 4,35 бит. Устранение избыточности достигается применением неравномерных кодов, в которых буквы, имеющие наибольшую вероятность, кодируются наиболее короткими кодовыми последовательностями, а более длинные комбинации присваиваются редким буквам. Если i-я буква, вероятность которой Р_i, получает кодовую комбинацию длины q_i, то средняя длина комбинации

Считая кодовые буквы равномерными, определяем наибольшую энтропию закодированного алфавита как q_ср log m, которая не может быть меньше энтропии исходного алфавита Н, т.е. q_ср log m ³ Н.

При двоичном кодировании (m=2) приходим к соотношению q_ср ³ Н, или

Чем ближе значение q_ср к энтропии Н, тем более эффективно кодирование. В идеальном случае, когда q_ср » Н, код называют эффективным.

Если же отказаться от разделительных символов, то следует запретить такие кодовые комбинации, начальные части которых уже использованы в качестве самостоятельной комбинации. Например, если 101 означает код какой-то буквы, то нельзя использовать комбинации 1, 10 или 10101.

Практические методы оптимального кодирования просты и основаны на очевидных соображениях( метод Шеннона – Фано ).

Пример16: Провести эффективное кодирование ансамбля из восьми знаков:

Буква (знак) x_i	Вероят-ность Рi	Кодовые последовательности	Длина q_i	р_i q_i	-р_ilog р_i
Номер разбиения
x1	0,25	0,5	0,50
x2	0,25	0,5	0,50
x3	0,15	0,45	0,41
x4	0,15	0,45	0,41
x5	0,05	0,2	0,22
x6	0,05	0,2	0,22
x7	0,05	0,2	0,22
x8	0,05	0,2	0,22

= 2,7

Как видно, q_ср = H, следовательно, полученный код является оптимальным.

Пример17: Построить код Шеннона - Фано, если известны вероятности: Р(x₁) = 0,5; P(x₂)= 0,25; P(x₃) = 0,125; P(x₄) = 0,125

Пример18: Провести эффективное кодирование ансамбля из восьми знаков (m=8), используя метод Шеннона - Фано.

Решение: При обычном (не учитывающем статистических характеристик) двоичном кодировании с использованием k=2 знаков при построении равномерного кода количество элементов в кодовой последовательности будет q ³ log_k m = log₂ 8 = 3, т.е. для представления каждого знака использованного алфавита потребуется три двоичных символа.

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

Знаки (буквы) x_i	Вероятность Pi	Кодовые комбинации
номер разбиения
x1	1/2
x2	1/4
x3	1/8
x4	1/16
x5	1/32
x6	1/64
x7	1/128
x8	1/128

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

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

Вычислим среднее число символов на знак:

где q(x_i) - число символов в кодовой комбинации, соответствующей знаку x_i.

Пример19: Определить среднюю длину кодовой комбинации при эффективном кодировании по методу Шеннона - Фано ансамбля - из восьми знаков и энтропию алфавита.

Знаки (буквы) x_i	Вероятность Pi	Кодовые комбинации
номер разбиения
x1	0,22
x2	0,20
x3	0,16
x4	0,16
x5	0,10
x6	0,10
x7	0,04
x8	0,02

Решение: 1. Средняя длина кодовых комбинаций

2. Энтропия алфавита

При кодировании по методу Шеннона - Фано некоторая избыточность в последовательностях символов, как правило, остается (q_ср > H).

дз на зиму КиЦОИ / Прохоров_Теория_информации

на плаву за счет одной своей особенности: в нем позволительно создавать анимированные изображения. Хотя кто знает, может быть, анимированная версия PNG появится уже завтра, a GIF навсегда уйдет в историю.

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

ХАРАКТЕРИСТИКИ ВИДЕОФАЙЛОВ И ВИДЕОПЛЕЕРОВ

Операционная система Windows может работать с большим количеством видеофайлов различных форматов, что объясняется многообразием алгоритмов компрессии цифрового видео. Многие из них принадлежат разным производителям и основаны на разных принципах. Например, самый популярный на сегодня стандарт MPEG используется для записи DVDфильмов и дисков с фильмами в формате DivX, a RealVideo используется для живой телевизионной трансляции в Интернете. Например, телекомпания CNN одной из первых стала вещать в Сети.

Большинство видеофайлов сжаты с использованием стандарта MPEG-4 (сжатие – устранение избыточности цифровой информации).

История стандарта MPEG-4 началась с работы группы экспертов (Motion Picture Experts Group), no аббревиатуре которой и сложились современные названия стандартов, а также расширения многих других видеофайлов. Файлы с расширением AVI, которые используют этот кодек, не имеют постоянных параметров, так как существуют в двух ипостасях: без компрессии и файлы, сжатые, например, кодеком DivX, которые также имеют расширение AVI. Кодек – это программа для кодирования – декодирования потока данных.

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

Залог успешного просмотра видеофайлов на компьютере — это наличие современного программного видеоплеера. В Windows XP по умолчанию это Windows Media Player, причем в комплект его поставки уже входят несколько встроенных кодеков. Установка двух-трех плееров обеспечивает гарантированное воспроизведение видеофайлов различных типов, потому что

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

проигрывать. Каждый из них обеспечивает воспроизведение не только файлов в собственном формате, но и почти всех видеофайлов ближайших конкурентов. Особняком здесь стоит только Real Player, потому что данные в формате RealVideo и RealAudio (файлы с расширением RM, RA, RAM) может воспроизводить только этот плеер.

Формат компрессии DivX (технология компрессии от DivXNetworks): модификация MPEG-4, использует высокую степень компрессии с приемлемым качеством.

Формат компрессии RealVideo (собственный формат компании RealNetworks): RealVideo, использует очень высокую степень сжатия видео для прямой трансляции в Интернете.

Формат компрессии Windows Media (собственный формат файлов Microsoft): аналогичен MPEG-4, собственный формат фирмы Microsoft.

Программный видеоплеер Windows Media Player: типы воспроизводимых файлов WMV, ASF, AVI. MPEG, MPG, IVF, M1V, МР1, МР2, VOB и др.

Программный видеоплеер Real Player: типы воспроизводимых файлов RM, RA, RAM, MPG, MPEG, AVI, ASF, MID, MOV и др.

Программный видеоплеер Quick Time Player: типы воспроизводимых файлов QT, MOV, PNG, AVI, FIX, MPG, MPEG, MP1, MK и др.

В комплекте Windows имеется программный пакет для домашнего видеомонтажа Movie Maker. В нем реализованы все основные этапы работы с цифровым видео: захват, монтирование и сохранение (отправление в Интернет) видеофайлов. Существует достаточно много и других профессиональных программ. Их обычно начинают применять, когда компьютер превращается в домашнюю видеостудию: с приобретением ТВ-тюнера, цифровой видеокамеры, Firewire - оборудования или специальных плат видеозахвата.

Firewire – это стандарт обмена данными между периферийными устройствами. Видеомонтаж – программная обработка видеоматериала.

Захват видеосигнала: перенос аналогового или цифрового сигнала на жесткий диск ПК.

Для сохранения звука пользуются специальными программами — кодаками. Хотя качество результата у всех кодаков разное, принцип работы у них один.

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

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

МРЗ и WMA. Если стандарт WMA разрабатывается исключительно фирмой Microsoft, то кодек для сжатия цифрового звука в стандарте МРЗ может создать любой программист. В результате это привело к появлению большого количества алгоритмов кодирования. В условиях конкурентной борьбы за качество МРЗ-файлов на первое место вышел проект нескольких программистов — Lame.

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

Многие фирмы стали разрабатывать программы для кодирования аудиосигнала с наименьшими потерями в качестве. Группа специалистов (MPEG), входящая в состав Международной организации стандартов (ISO), еще в конце 80-х годов разработала стандарт MPEG, на основе которого был создан современный стандарт сжатия звука MPEG 1.0 Audio Layer III — впоследствии он стал известен как МРЗ. Так как изначально утилиты для создания МРЗ-файлов распространялись за деньги, программисты стали искать способ бесплатно использовать алгоритмы работы кодека. Так среди многих других проектов появился кодек Lame, постепенно получивший огромную популярность. Основной особенностью Lame стало то, что разработчики сделали акцент на улучшении алгоритма специальной психоакустической модели. Принцип ее действия заключается в том, что из звукового файла удаляются те частоты, которые человеческое ухо воспринимать не в состоянии.

При кодировании цифрового звука (файлы с расширением WAV) основным параметром, влияющим на качество результата, является величина битрейта . Если использовать максимальное значение этого параметра, то получают звук, наиболее соответствующий оригиналу. Примерно до 2000 года широко использовалось значение битрейта 128 Кбит/с, а затем, с возросшей пропускной способностью современных каналов связи, наиболее распространенным стал битрейт 192 Кбит/с.

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

Кодек WMA фирмы Microsoft

Кодек WMA был разработан фирмой Microsoft как стандарт хранения сжатой аудиоинформации в операционной системе Windows. Microsoft не стала пользоваться разработками организации MPEG, поэтому стандарт WMA является закрытым для использования другими разработчиками.

Microsoft стремится максимально использовать коммерческий потенциал WMA и поэтому защищает музыку в этом формате от нелегального копирования: WMA-файлы нельзя переконвертировать в файлы с расширением WAV.

Тем не менее популярность WMA растет. Это связано с тем, что при том же качестве звука, что и у стандарта МРЗ (по заявлению самой Microsoft), этот кодек позволяет получить меньший размер файла. Такой результат достигается за счет использования более низкого значения параметров битрейта, чем у МРЗ-файлов.

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

Выбор кодека для звука

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

Другие кодеки для звука

Программистам и компаниям хочется сделать кодек, который станет всеобщим стандартом. Однако до сих пор ни один разработанный формат, отличный от WMA и МРЗ, не смог получить широкого распространения. Это произошло по двум причинам: либо кодек не очень хорошо сжимал аудиофайлы, либо программное обеспечение для его использования было полностью платным. Список кодеков, пытавшихся заменить МРЗ, достаточно велик:

ААС — улучшенный вариант стандарта MPEG по соотношению «размер файла/качество звука». Не получил особого распространения, потому что при кодировании аудиофайлов сильно загружает ресурсы компьютера.

Liquid Audio — коммерческий кодек, в котором содержание файла шифруется для пресечения нелегального копирования. Несмотря на то, что этот кодек по качеству результата превосходит МРЗ, отсутствие бесплатных программ для кодирования файлов помешало распространению этого формата.

МРЗрго — кодек, разработанный фирмой Tomson Multimedia. Был призван улучшить качество формата МРЗ на низких битрейтах. Особой популярности не получил из-за достаточно высокой цены и узкой области применения.

OGG Vorbis — этот сравнительно недавно появившийся кодек стоит особняком среди всех перечисленных форматов. Получаемые с его помощью файлы как по качеству, так и по размеру значительно превосходят стандарт МРЗ, что дает разработчикам право надеяться на то, что в будущем файлы с расширением OGG станут единственным средством хранения и распространения музыки через Интернет. Однако ни один современный портативный МРЗ-плеер

не умеет воспроизводить файлы в этом формате — так же, как и большинство программных мультимедийных проигрывателей. TwinVQ — стандарт, разработанный фирмой Yamaha. Предназначался для кодирования звука с очень низким битрейтом и более высоким качеством, чем МРЗ. Не пользовался популярностью из-за больших требований к системным ресурсам как при воспроизведении музыки в этом формате, так и при кодировании файлов.

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

Назначение формата PDF

Portable Document Format или просто PDF, был создан специально для ликвидации проблем с отображением информации в файлах. В чем же его преимущество? Во-первых, документ, сохраненный в формате PDF, будет одинаково выглядеть в любой операционной системе: в Windows XP, в Windows 95, и в Linux. Во-вторых, PDF использует качественные алгоритмы сжатия: если объем файла Word, содержащего пару картинок, вряд ли получится меньше мегабайта, то точно такой же PDF вполне уместится в 300-400 Кбайт. В-третьих, PDF умеет встраивать в себя все используемые в документе шрифты — будь то рукописные, готические или славянская вязь, так что можно забыть о тех случаях, когда какого-либо шрифта не оказывается на компьютере. В-четвертых, в формат PDF можно преобразовать любой электронный документ. А для прочтения и печати PDF понадобится бесплатная программа

Сделать PDF просто. Первое, что необходимо, — программа Adobe Acrobat Professional, желательно последней версии 6.0. На практике все происходит очень просто, а во всех приложениях Microsoft Office и продуктах Adobe это можно сделать одним нажатием кнопки.

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

Открывают файл, который нужно преобразовать в PDF-формат, нажимают кнопку Convert to Adobe PDF на вышеуказанной Панели инструментов. В открывшемся окне указывают желаемое Имя создаваемого в формате PDF файла и Путь (месторасположение), где он будет находиться. Нажимают ОК, и через некоторое время новый файл будет готов и автоматически откроется для просмотра. Не сложнее этот процесс и во многих других программах. После установки Acrobat Professional в системе появляется новый виртуальный принтер под названием Adobe PDF —можно увидеть его ярлычк, открыв папку Принтеры через Панель управления. Он называется виртуальным, потому что реально не существует и используется именно для создания

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

Дополнительные настройки при создании PDF-файла

3. Эффективное кодирование

Если исходный алфавит содержит m букв, то для построения равномерного кода с использованием k кодовых букв необходимо удовлетворить соотношение m ≤ k q , где q - количество элементов в кодовой последовательности.

q ≥ log k = log k m

Для построения равномерного кода достаточно пронумеровать буквы исходного алфавита и записать их коды как q - разрядные числа в k-ичной системе счисления. Например, при двоичном кодировании 32 букв русского алфавита используется q = log 2 32 = 5 разрядов, на чем и основывается телетайпный код. Кроме двоичных кодов, наибольшее распространение получили восьмеричные коды. Пусть, например, необходимо закодировать алфавит, состоящий из 64 букв. Для этого потребуется q = log 2 64 = 6 двоичных разрядов или q = log 8 64 = 2 восьмеричных разрядов. При этом буква с номером 13 при двоичном кодировании получает код 001101, а при восьмеричном кодировании 15. Общепризнанным в настоящее время является позиционный

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

Q = ∑ l a i m i − 1 = a l m l − 1 + a l − 1 m l − 2 + . + a 2 m 1 + a 1 m 0 , i = 1

где i - номер разряда данного числа; l - количество рядов; а i - множитель, принимающий любые целочисленные значения в пределах от 0 до m-1 и показывающий, сколько единиц i - ого ряда содержится в числе.

Часто используются двоично-десятичные коды , в которых цифры десятичного номера буквы представляются двоичными кодами. Так, например, для рассматриваемого примера буква с номером 13 кодируется как 0001 0011. Ясно, что при различной вероятности появления букв исходного алфавита равномерный код является избыточным, т.к. его энтропия (полученная при условии, что все буквы его алфавита равновероятны): log k m = H 0

Например, для телетайпного кода Н0 = log k m = log 2 32 = 5 бит, а с учетом неравномерности появления различных букв исходного алфавита Н ≈ 4,35 бит. Устранение избыточности достигается применением неравномерных кодов, в которых буквы, имеющие наибольшую вероятность, кодируются наиболее короткими кодовыми последовательностями, а более длинные комбинации присваиваются редким буквам. Если i-я буква, вероятность которой Р i , получает кодовую комбинацию длины q i , то средняя длина комбинации

q с р = i ∑ = 1 p i q i

Считая кодовые буквы равномерными, определяем наибольшую энтропию закодированного алфавита как q ср log m, которая не может быть меньше энтропии исходного алфавита Н, т.е. q ср log m ≥ Н.

При двоичном кодировании (m=2) приходим к соотношению q ср ≥ Н, или

i = 1 P i q i ≥ − i = 1 P i log P i

Чем ближе значение q ср к энтропии Н, тем более эффективно кодирование. В идеальном случае, когда q ср ≈ Н, код называют эффективным .

Практические методы оптимального кодирования просты и основаны на очевидных соображениях ( метод Шеннона – Фано ) .

Пример16 : Провести эффективное кодирование ансамбля из восьми знаков: Таблица 3.1.

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

Пример. Провести эффективное кодирование ансамбля из восьми знаков:

Вероят-ность p_i

-р_ilog р_i

= 2,7 и .

Как видно, l_ср = H, следовательно, полученный код является оптимальным.

Заметим, что при равномерном (не учитывающем статистических характеристик) кодировании с использованием m=2 знаков количество элементов в кодовой последовательности будет l  log_m n = log₂ 8 = 3, т.е. для представления каждого знака использованного алфавита потребуется три двоичных символа.

При кодировании по методике Шеннона - Фано некоторая избыточность в последовательностях символов, как правило, остается (l_ср > H).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1 Интерфейс пользователя

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

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

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

Алгоритм Шеннона-Фано

Алгоритм метода Шеннона-Фано — один из первых алгоритмов сжатия, который впервые сформулировали американские учёные Шеннон и Фано, и он имеет большое сходство с алгоритмом Хаффмана. Алгоритм основан на частоте повторения. Так, часто встречающийся символ кодируется кодом меньшей длины, а редко встречающийся — кодом большей длины.
В свою очередь, коды, полученные при кодировании, префиксные. Это и позволяет однозначно декодировать любую последовательность кодовых слов. Но все это вступление.

Для работы оба алгоритма должны иметь таблицу частот элементов алфавита.

На вход приходят упорядоченные по невозрастанию частот данные.
Выбираются две наименьших по частоте буквы алфавита, и создается родитель (сумма двух частот этих «листков»).
Потомки удаляются и вместо них записывается родитель, «ветви» родителя нумеруются: левой ветви ставится в соответствие «1», правой «0».
Шаг два повторяется до тех пор, пока не будет найден главный родитель — «корень».

На вход приходят упорядоченные по невозрастанию частот данные.
Находится середина, которая делит алфавит примерно на две части. Эти части (суммы частот алфавита) примерно равны. Для левой части присваивается «1», для правой «0», таким образом мы получим листья дерева
Шаг 2 повторяется до тех пор, пока мы не получим единственный элемент последовательности, т.е. листок

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

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

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

Читайте также: