Методы арифметического кодирования информации и сравнение их коэффициентов сжатия

скачать (4425.3 kb.)

  1   2   3   4   5   6   7
СОДЕРЖАНИЕ
Перечень обозначений и сокращений

Введение

. Методы арифметического кодирования

.1 Унарный код

.2 Код Голомба

.3 Код Райса

.4 Коды Фибоначчи

.5 Гамма - коды Элиаса

.6 Дельта - коды Элиаса

.7 Омега код Элиаса

.8 Коды Ивэн-Родэ

.9 Код Левенштейна

.10 Гамма коды Левенштейна

.11 Старт - шаг - стоп коды

.12 Код Хаффмана

. Обоснование и описание алгоритмов кодирования

.1 Описание алгоритма, реализующего код Хаффмана

.2 Описание алгоритма, реализующего код Голомба

.3 Описание алгоритма, реализующего кодирование при помощи чисел Фибоначчи

.4 Описание алгоритма, реализующего гамма-код Элиаса

.5 Описание алгоритма, реализующего дельта-код Элиаса

. Обоснование и описание программ кодирования

.1 Обоснование выбора инструментальных средств

.2 Описание основных функций программы, реализующей алгоритмы кодирования по методу Хаффмана

.3 Описание основных функций программы, реализующей алгоритмы кодирования по методу Голомба

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

.5 Описание основных функций программы, реализующей алгоритмы гамма-кодирования Элиаса

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

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

.1 Цель и назначение

.2 Расчет себестоимости и цены изделия

.2.1 Расчет материальных расходов

.2.2 Расходы на оплату труда

.2.3 Дополнительная заработная плата

.2.4 отчисления на социальные мероприятия

.2.5 Амортизационные отчисления

.2.6 Затраты на машинное время

.2.7 Накладные расходы

.3 Экономическая эффективность НИР

.4 Выводы

Охрана труда и окружающей среды

.1 Общие вопросы охраны труда и окружающей среды

.2 Опасные и вредные производственные факторы

.3 Промышленная санитария

.3.1 Метеорологические условия помещения при работе

.3.2 Освещение производственного помещения

.3.3 Излучение от экрана

.3.4 Шум и вибрация

.3.5 Электробезопасность

.3.6 Пожарная безопасность

.4 Охрана окружающей среды

Заключение

Список источников информации

Приложение А - Листинг программы кодирования-декодирования
ПЕРЕЧЕНЬ ОБОЗНАЧЕНИЙ И СОКРАЩЕНИЙ
Unar - унарный код

ДБН - державні будівельні норми

ДНАОП - державний нормативний акт про охорону праці

КЕО - коэффициент естественного освещения

НДС - Налог на добавленную стоимость

НИР - научно-исследовательская работа

НИОКР - коэффициент научно-технического эффекта

ПУЭ - правила устройства электроустановок

СНиП - Система норм и правил
ВВЕДЕНИЕ
Современное общество использует цифровой вид представления информации во многих сферах жизнедеятельности. Большой объем информации требует большой протяженности и пропускной способности каналов передачи данных. На данный момент развития информационной инфраструктуры, существующие каналы не справляются с требуемым трафиком. Следовательно, задача сжатия данных является актуальной во многих приложениях обработки и передачи информации.

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

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

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

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

Настоящая работа посвящена исследованию различных методов арифметического кодирования информации и сравнению их коэффициентов сжатия. Теоретическое и экспериментальное исследование алгоритмов.
1. МЕТОДЫ АРИФМЕТИЧЕСКОГО КОДИРОВАНИЯ
Компактное представление информации - очень важная проблема в областях, где приходится работать со сжатием данных. Цель - сжатие потока R-битовых элементов. В общем случае никаких предположений о свойствах значений элементов не делается, поэтому можно говорить об описании способов представления целых чисел.

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

Основная идея состоит в том, чтобы отдельно хранить порядок значения элемента Xi («экспоненту» Ei) и отдельно - значащие цифры значения («мантиссу» Mi).

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

Существует четыре варианта этого метода:

· Fixed+Fixed (фиксированная длина экспоненты - фиксированная длина мантиссы)

· Fixed+Variable (фиксированная длина экспоненты - переменная длина мантиссы)

· Variable+Variable (переменная длина экспоненты - переменная длина мантиссы)

· Variable+Fixed (переменная длина экспоненты - фиксированная длина мантиссы)

В данной работе будут рассмотрены коды переменной длины (Variable+Variable).
.1 Унарный код
Унарный код сопоставляет числу i двоичную комбинацию вида 10.Запись вида 0 или 1 означает соответственно серию из m нулей или единиц. Например, унарными кодами чисел 1, 2, и 3 являются последовательности unar(1)=10, unar(2)=110 и unar(3)=1110 соответственно. Длина кодового слова для числа n равна ln=n+1. На рисунке 1.1 приведен унарный код чисел от 0 до 6.


Рисунок 1.1 - Унарный код чисел от 0 до 6
Унарный код оптимален, если числа i распределены по геометрическому закону (1.1) с параметром =:

p=(1-), (1.1)
где i=1,2,

Для значений < более эффективен код Голомба.
.2 Код Голомба
Коды Голомба - это семейство энтропийных кодеров, являющихся общим случаем унарного кода. Кодирование энтропии- кодирование словами (кодами) переменной длины, при которой длина кода символа имеет обратную зависимость от вероятности появления символа в передаваемом сообщении. Обычно энтропийные кодировщики используют для сжатия данных коды, длины которых пропорциональны отрицательному логарифму вероятности символа. Таким образом, наиболее вероятные символы используют наиболее наиболее короткие коды. Согласно теореме Шеннона оптимальная длина кода для символа равна -logP, где b- это количество символов, используемых для изготовления выходного кода, и Р- вероятность входного символа. Унарный код - это энтропийное кодирование, которое представляет число n в виде n единиц с замыкающим нулем ( либо n нулей и единица). Например, 5 представляется в виде 111110. Унарное кодирование оптимально для распределения вероятности: P(x)=2. Также под кодом Голомба может подразумеваться один из представителей этого семейства.

Код Голомба позволяет представить последовательность символов в виде последовательности двоичных слов. Это представление будет оптимальным при условии, что распределение вероятности символов подчиняется геометрическому закону (1.2):

P(i) = (1-p)p, (1.2)

где i - номер символа, а р - параметр геометрического распределения. Также должно соблюдаться условие (1.3):

p= , (1.3)
где m - основной параметр кода Голомба.

Для кодирования символа с номером n необходимо представить n в виде (1.4):
n = qm + r, (1.4)
где q и r - целые положительные числа, 0 r < m.Затем r кодируется унарным кодом, а q - бинарным. Полученные двоичные последовательности объединяются в результирующее слово.

Пример: Основной параметр кода m=4, кодируемое число n=13 .

· Частное q===3;

· унарный код q - 1110;

· остаток r=n mod m=13 mod 4=1;

· бинарный код r - 01;

· результирующее кодовое слово - 111001.

Рассмотрим несколько примеров кодов Голомба для различного параметра m в таблице 1.1:
Таблица 1.1 - Коды Голомба для различных параметров m

n\ m

1

2

3

4

5

0

0

00

00

000

000

1

10

01

010

001

001

2

110

100

011

010

010

3

1110

101

100

011

0110

4

11110

1100

1010

1000

0111

5

111110

1101

1011

1001

1000

6

1111110

11100

1100

1010

1001

7

11111110

11101

11010

1011

1010

8

111111110

111100

11011

11000

10110

9

1111111110

111101

11100

11001

10111

10

11111111110

1111100

111010

11010

11000

11

111111111110

1111101

111011

11011

11001

12

1111111111110

11111100

111100

111000

11010

13

11111111111110

11111101

1111010

111001

110110

14

111111111111110

111111100

1111011

111010

110111

15

1111111111111110

111111101

1111100

111011

111000

16

11111111111111110

1111111100

11111010

1111000

111001

17

111111111111111110

1111111101

11111011

1111001

111010


Ниже приводится рисунок 1.2, поясняющий устройство данных кодов: как именно двоичное представление остатка следует за унарным кодом :
  1   2   3   4   5   6   7



Рефераты Практические задания Лекции
Учебный контент

© ref.rushkolnik.ru
При копировании укажите ссылку.
обратиться к администрации