Методы арифметического кодирования информации и сравнение их коэффициентов сжатия - Программирование, компьютеры и кибернетика дипломная работа

Главная

Программирование, компьютеры и кибернетика
Методы арифметического кодирования информации и сравнение их коэффициентов сжатия

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


посмотреть текст работы


скачать работу можно здесь


полная информация о работе


весь список подобных работ


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

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
1. Методы арифметического кодирования
2. Обоснование и описание алгоритмов кодирования
2.1 Описание алгоритма, реализующего код Хаффмана
2.2 Описание алгоритма, реализующего код Голомба
2.3 Описание алгоритма, реализующего кодирование при помощи чисел Фибоначчи
2.4 Описание алгоритма, реализующего гамма-код Элиаса
2.5 Описание алгоритма, реализующего дельта-код Элиаса
3. Обоснование и описание программ кодирования
3.1 Обоснование выбора инструментальных средств
3.2 Описание основных функций программы, реализующей алгоритмы кодирования по методу Хаффмана
3.3 Описание основных функций программы, реализующей алгоритмы кодирования по методу Голомба
3.4 Описание основных функций программы, реализующей алгоритмы кодирования с помощью чисел Фибоначчи
3.5 Описание основных функций программы, реализующей алгоритмы гамма-кодирования Элиаса
3.5 Описание основных функций программы, реализующей алгоритмы дельта-кодирования Элиаса
4. Технико-экономическое обоснование разработки программно-аппаратных средств оптимального арифметического кодирования
4.2 Расчет себестоимости и цены изделия
4.2.3 Дополнительная заработная плата
4.2.4 отчисления на социальные мероприятия
4.3 Экономическая эффективность НИР
5.1 Общие вопросы охраны труда и окружающей среды
5.2 Опасные и вредные производственные факторы
5.3.1 Метеорологические условия помещения при работе
5.3.2 Освещение производственного помещения
Приложение А - Листинг программы кодирования-декодирования
ДНАОП - державний нормативний акт про охорону праці
КЕО - коэффициент естественного освещения
НДС - Налог на добавленную стоимость
НИР - научно-исследовательская работа
НИОКР - коэффициент научно-технического эффекта
ПУЭ - правила устройства электроустановок
Современное общество использует цифровой вид представления информации во многих сферах жизнедеятельности. Большой объем информации требует большой протяженности и пропускной способности каналов передачи данных. На данный момент развития информационной инфраструктуры, существующие каналы не справляются с требуемым трафиком. Следовательно, задача сжатия данных является актуальной во многих приложениях обработки и передачи информации.
Сжатием блока данных называется такое его описание, при котором создаваемый сжатый блок содержит меньше битов, чем исходный, но по нему возможно однозначное восстановление каждого бита исходного блока. Обратный процесс, восстановление по описанию, называется разжатием. Используют и такие пары терминов: компрессия /декомпрессия, кодирование /декодирование, упаковка /распаковка.
Большинство методов компрессии самых разных типов цифровой информации часто используют на определённых стадиях алгоритмы сжатия без потерь. Это такое кодирование при котором энтропия сжатых данных совпадает с энтропией исходного источника и по сжатым данным можно полностью восстановить исходную информацию. Можно сказать, что компрессия без потерь является экстремальным случаем сжатия, при котором энтропия данных остается неизменной.
В основе всех методов сжатия лежит простая идея: если представлять часто используемые элементы короткими кодами, а редко используемые - длинными кодами, то для хранения блока данных требуется меньший объем памяти, чем если бы все элементы представлялись кодами одинаковой длины.
Эффективность сжатия учитывает степень сжатия (отношение длины несжатых данных к длине соответствующих им сжатых данных) и скорости сжатия и разжатия. Часто пользуются обратной к степени сжатия величиной - коэффициентом сжатия, определяемым как отношение длины сжатых данных к длине соответствующих им несжатых.
Настоящая работа посвящена исследованию различных методов арифметического кодирования информации и сравнению их коэффициентов сжатия. Теоретическое и экспериментальное исследование алгоритмов.
1. МЕТОДЫ АРИФМЕТИЧЕСКОГО КОДИРОВАНИЯ
Компактное представление информации -- очень важная проблема в областях, где приходится работать со сжатием данных. Цель -- сжатие потока R-битовых элементов. В общем случае никаких предположений о свойствах значений элементов не делается, поэтому можно говорить об описании способов представления целых чисел.
Арифметическое кодирование известно сегодня как один из наиболее эффективных методов сжатия данных, который применим для большого класса источников информации. Основная идея арифметического кодирования была сформулирована Элайесом ещё в начале 60-х годов. Преимущество арифметического кода по отношению к другим методам заключается в том, что он позволяет достичь произвольно низкой избыточности на символ источника (избыточность - центральное понятие в теории сжатия информации. Любые данные с избыточной информацией можно сжать; в которых нет избыточности - сжать нельзя). Показывает высокую эффективность для дробных неравномерных интервалов распределения вероятностей кодируемых символов.
Основная идея состоит в том, чтобы отдельно хранить порядок значения элемента X i («экспоненту» E i ) и отдельно -- значащие цифры значения («мантиссу» M i ).
Методы данной группы являются трансформирующими и поточными, то есть могут применяться даже в том случае, когда объем входных данных заранее не известен. В общем случае скорость работы компрессора (содержащего прямое, «сжимающее» преобразование) равна скорости декомпрессора (реализующего обратное, «разжимающее» преобразование) и зависит только от объема исходных данных. Памяти потребуется всего несколько байтов.
Существует четыре варианта этого метода:
· Fixed+Fixed (фиксированная длина экспоненты - фиксированная длина мантиссы)
· Fixed+Variable (фиксированная длина экспоненты - переменная длина мантиссы)
· Variable+Variable (переменная длина экспоненты - переменная длина мантиссы)
· Variable+Fixed (переменная длина экспоненты - фиксированная длина мантиссы)
В данной работе будут рассмотрены коды переменной длины (Variable+Variable).
Унарный код сопоставляет числу i двоичную комбинацию вида 10.Запись вида 0 или 1 означает соответственно серию из m нулей или единиц. Например, унарными кодами чисел 1, 2, и 3 являются последовательности unar(1)=10, unar(2)=110 и unar(3)=1110 соответственно. Длина кодового слова для числа n равна l n =n+1. На рисунке 1.1 приведен унарный код чисел от 0 до 6.
Рисунок 1.1 - Унарный код чисел от 0 до 6
Унарный код оптимален, если числа i распределены по геометрическому закону (1.1) с параметром =:
Для значений < более эффективен код Голомба.
Коды Голомба - это семейство энтропийных кодеров, являющихся общим случаем унарного кода. Кодирование энтропии- кодирование словами (кодами) переменной длины, при которой длина кода символа имеет обратную зависимость от вероятности появления символа в передаваемом сообщении. Обычно энтропийные кодировщики используют для сжатия данных коды, длины которых пропорциональны отрицательному логарифму вероятности символа. Таким образом, наиболее вероятные символы используют наиболее наиболее короткие коды. Согласно теореме Шеннона оптимальная длина кода для символа равна -logP, где b- это количество символов, используемых для изготовления выходного кода, и Р- вероятность входного символа. Унарный код - это энтропийное кодирование, которое представляет число n в виде n единиц с замыкающим нулем ( либо n нулей и единица). Например, 5 представляется в виде 111110. Унарное кодирование оптимально для распределения вероятности: P(x)=2. Также под кодом Голомба может подразумеваться один из представителей этого семейства.
Код Голомба позволяет представить последовательность символов в виде последовательности двоичных слов. Это представление будет оптимальным при условии, что распределение вероятности символов подчиняется геометрическому закону (1.2):
где i - номер символа, а р - параметр геометрического распределения. Также должно соблюдаться условие (1.3):
где m - основной параметр кода Голомба.
Для кодирования символа с номером n необходимо представить n в виде (1.4):
где q и r - целые положительные числа, 0 r < m.Затем r кодируется унарным кодом, а q - бинарным. Полученные двоичные последовательности объединяются в результирующее слово.
Пример: Основной параметр кода m=4, кодируемое число n=13 .
· результирующее кодовое слово - 111001.
Рассмотрим несколько примеров кодов Голомба для различного параметра m в таблице 1.1:
Таблица 1.1 - Коды Голомба для различных параметров m
Ниже приводится рисунок 1.2, поясняющий устройство данных кодов: как именно двоичное представление остатка следует за унарным кодом :
Рисунок 1.2 - Формирование кодов Голомба
Код Райса идентичен коду Голомба, когда m является степенью двойки. На самом деле данные коды имеют параметр k, по которому вычисляется значение m = 2 k .
Введем параметр Т=2 . Код Райса для числа n состоит из двух частей. Первая часть - унарный код числа [], вторая часть - двоичная запись в виде последовательности длины k остатка от деления n на T. Очевидно, длина кода Райса для числа n равна l n =[]+1+k. Например, при k=3 и n=21 имеем []=2, остаток равен 5. Поэтому кодом Райса числа 21 будет последовательность 110101.
Рассмотрим несколько примеров кодов Райса для различных параметров k, которые представлены в таблице 1.2:
Таблица 1.2 - Коды Райса для различных параметров k
Код Райса - это частный случай кода Голомба, это легко увидеть из таблицы 1.3, представленной ниже:
Таблица 1.3 - Сравнительная таблица кода Райса и кода Голомба
Самые интересные, нетривиальные коды. В данном кодировании исходное число n раскладывается в сумму чисел Фибоначчи f i (f 1 = 1; f 2 = 2; f i = f i ?1 + f i ?2 ). Известно, что любое натуральное число однозначно представимо в виде суммы чисел Фибоначчи. Поэтому можно построить код числа как последовательность битов, каждый из которых указывает на факт наличия в n определенного числа Фибоначчи.
Заметим также, что если в разложении числа n присутствует f i , то в этом разложении не может быть числа f i +1 . Поэтому логично для конца кода использовать дополнительную единицу. Тогда две идущие подряд единицы будут означать окончание кодирования текущего числа.
Рассмотрим несколько примеров кодов Фибоначчи в таблице 1.4:
Таблица 1.4 - Примеры кода Фибоначчи
Числа Фибоначчи - элементы числовой последовательности:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, …,
в которой каждое последующее число равно сумме двух предыдущих чисел. Название по имени средневекового математика Леонардо Пизанского (или Фибоначчи).
Более формально, последовательность чисел Фибоначчи {F} задается рекуррентным соотношением:
Иногда числа Фибоначчи рассматривают и для неположительных номеров n как двусторонне бесконечную последовательность, удовлетворяющую основному соотношению. Члены с такими номерами легко получить с помощью эквивалентной формулы «назад» (1.5):
Пример двусторонне бесконечной последовательности чисел Фибоначчи представлен в таблице 1.5:
Таблица 1.5-Двусторонняя последовательность чисел Фибоначчи в интервале [-7..7]
Гамма-код Элиаса -- двоичный префиксный код представления натуральных чисел. Число кодируется в два этапа. Определяется количество двоичных разрядов кодируемого числа. Вначале кодируется n посредством инвертированного унарного кода, после чего в неизменном виде дописываются n младших разрядов (старший единичный разряд, таким образом, опускается). Иными словами, код представляет собой число в двоичном представлении, заполненное нулями на 1 меньшей длины. В сумме длина кода должна равняться 2 n + 1. В таблице 1.6 приведены гамма-коды Элиаса малых натуральных чисел:
Таблица 1.6 - Гамма-коды Элиаса малых натуральных чисел
Дельта-код Элиаса является производным от гамма-кода. В начале кодируется количество значащих двоичных разрядов в числе посредством гамма-кода, после чего записываются все значащие разряды, за исключением старшей единицы (общим количеством на 1 меньше закодированного количества). В таблице 1.7 приведены дельта-коды Элиаса для некоторых чисел. Закодированное количество разрядов и остальная часть числа разделены пробелом. Знаки х соответствуют разрядам двоичного представления кодируемого числа.
Таблица 1.7 - Дельта-коды Элиаса для некоторых чисел
Дельта-код даёт более оптимальное распределение длин для больших чисел, чем для малых (отношение длины кода к числу его разрядов стремится к единице).
Несколько примеров г и д кодов Элиаса приведены в таблице 1.8:
Омега-код Элиаса (рекурсивный код Элиаса) состоит из нескольких битовых групп, начинающихся с единичного бита, и замыкаемых нулевым битом [1]. Первая группа всегда имеет длину 2 бита. Длина каждой последующей группы определяется как на единицу большая, чем значение предыдущей. Последняя группа выражает кодируемое число. Исключение составляет число 1, оно кодируется единственным битом 0. Примеры кодов приведены в таблице 1.9:
Количество групп в коде возрастает быстро вначале, но далее -- очень медленно:
· 2 ... 3 (2 1 ... 2 2 ? 1) -- 1 группа;
· 4 ... 15 (2 2 ... 2 22 ? 1) -- 2 группы;
· 16 ... 65536 (2 22 ... 2 222 ? 1) -- 3 группы;
· 65536 ... 2 · 10 19728 (2 222 ... 2 2222 ? 1) -- всего 4 группы.
Данные коды, также как и омега-коды Элиаса, состоят из последовательности групп длинной L 1 , L 2 , L 3 , …, L m бит [1], которые начинаются с бита 1. В конце последовательности следует 0. Длина каждой следующей (n+1)-й группы задается значением битов предыдущей n-й группы. Значение битов последней группы является итоговым значением всего кода, то есть всей последовательности групп. В сущности, все первые m?1 групп служат лишь для указания длины последней группы.
В Ивэн-Родэ-кодах длина первой группы -- 3 бита, а длина каждой последующей группы равна значению предыдущей. Первые три значения заданы особым образом.
При кодировании формируется сначала последняя группа, следующая непосредственно перед нулем, а потом по очереди восстанавливаются все предыдущие группы одна за другой, пока процесс не будет завершен.
При декодировании, наоборот, группы получаются, начиная с первой, одна за другой, то есть по значению битов уже найденной группы определяется длина последующей и так далее, пока не будет найдена итоговая группа, после которой идет ноль.
Рассмотрим несколько примеров кодов Ивэн-Родэ - таблица 1.10:
Этот код проще всего объяснить на конкретном примере. Предположим, что нужно передать число n=21. Двоичное представление этого числа имеет вид 10101. Непосредственно использовать при кодировании двоичные представления натуральных чисел нельзя. Самый простой выход состоит в том, чтобы приписать в начале слова префикс, указывающий длину двоичной записи числа (в данном случае это число 5). Если это число закодировать унарным кодом и приписать слева к двоичной записи числа, то код получится однозначно декодируемым. В данном примере для числа 21 получим кодовое слово 11111010101. В общем случае длина двоичного представления будет равна 2[logn].
Шаг за шагом будем улучшать этот способ кодирования. Важно заметить, что первая значащая цифра двоичной записи числа - всегда 1. Её можно не передавать, декодер сам допишет недостающую единицу, если будет знать длину двоичной записи числа. Обозначим через bin'(n) двоичную запись натурального числа n без первой единицы.
Чтобы сделать запись ещё короче, с длиной двоичной записи числа можно поступить так же, как и с самим числом, т.е. передать его значащие разряды (кроме первой единицы), затем длину двоичной записи числа значащих разрядов и т.д. Итерации продолжаются, пока не останется один значащий разряд. Чтобы декодирование было однозначным, достаточно приписать префикс, содержащий закодированное префиксным кодом (Префиксный код - это код, в котором код одного символа не может быть началом кода другого символа) число итераций. Минимальное число итераций равно 0 (при кодировании числа 1). Поэтому в качестве префиксного кода можно выбрать унарный код увеличенного на 1 числа итераций. Полученное кодовое слово будет кодовым словом кода Левенштейна.
Например, для числа 21 вычисляется bin'(21)=0101, затем bin'(4)=00, bin'(2)=0. Число итераций равно 3, поэтому кодовое слово кода Левенштейна имеет вид lev(21)=(1110)(0)(00)(0101)=11100000101. Декодер кода Левенштейна, декодируя унарный код, узнает, что итераций было три. Прочитав один значащий разряд (0) и дописав к нему в начало 1, получает последовательность 10. Это означает, что на предпоследней итерации длина числа была 2. Прочитав 2 разряда и дописав слева 1, получает 100. Теперь декодер считает 4 разряда и дописывает слева 1. Получается последовательность 10101, ей соответствует число 21. Поскольку это уже последняя 3-я итерация, число 21 является результатом декодирования.
Ниже приведена таблица 1.11 - таблица кодов Левенштейна для некоторых чисел натурального ряда.
Таблица 1.11 - примеры кодов Левенштейна
Коды Левенштейна и Элиаса практически эквивалентны, выигрыш кода Левенштейна проявляется только при астрономически больших значениях n.
Данный код для числа n получается путем обращения последовательности битов в двоичной записи этого числа и добавления перед каждым битом, кроме последнего, флагового (flag bit) бита 0. Последним флаговым битом является бит 1, который совпадает с самым старшим битом в исходной двоичной записи числа n.
Рассмотрим несколько примеров кодов Левенштейна в таблице 1.12:
Подчеркиванием показаны флаговые биты. Заметим, что последним таким битом всегда будет единица, которая являлась старшим битом в двоичном представлении кодируемого числа.
1.11 Старт-шаг-стоп коды (Start-step-stop codes)
Эти коды определяются тремя параметрами {i, j, k}. Код определяет серии блоков кодовых слов возрастающей длины: первый блок с числовой частью длиной i битов, второй -- i + j битов, затем -- i + 2j битов, и так далее до длины k битов. Группы кодовых слов имеют унарный префикс, дающий номер группы. Таким образом, код {3, 2, 9} имеет кодовые слова с числовой частью 3, 5, 7 и 9 бит и префиксы 0, 10, 110 и 111 (опуская последний 0 в последнем префиксе). Данные коды представлены в таблице 1.13 и выглядят так:
Далее приводится общая формула для восстановления числа по коду, а также алгоритм, позволяющий получить код по заданному числу n.
Пусть дан { i, j, k}-код и пусть количество единиц в унарной части (экспоненты) равно Q. Тогда число n (закодированное число) равно (1.7):
где в -- мантисса записанного кода, Dec(x) -- функция, переводящая x в десятичную систему счисления.
Теперь наоборот, пусть задано число n. Для получения его кода необходимо найти такое минимальное положительное число Q 0 , чтобы выполнялось неравенство (1.8):
При этом сам код будет выглядеть так (1.9):
б(Q 0 ? 1) : в(n + 2 IQ 0 ? S). (1.9)
В качестве частных случаев Start-step-stop кодов могут быть получены следующие коды и они сведены в таблицу 1.14:
Таблица 1.14 - Частный случай старт-шаг-стоп кодов
простой бинарный код для целых чисел
Код Хаффмана (Huffman code) ещё называют минимально-избыточным префиксным кодом (minimum-redundancy prefix code). Идея, лежащая в основе кода Хаффмана, достаточно проста. Вместо того чтобы кодировать все символы одинаковым числом бит (как это сделано, например, в ASCII кодировке, где на каждый символ отводится ровно по 8 бит), символы которые встречаются чаще, кодируются меньшим числом бит, чем те, которые встречаются реже. Код при этом должен быть оптимален или, другими словами, минимально-избыточен.
Первым такой алгоритм опубликовал Дэвид Хаффман в 1952 году. Алгоритм Хаффмана двухпроходный. На первом проходе строится частотный словарь и генерируются коды. На втором проходе происходит непосредственно кодирование.
Стоит отметить, что за 50 лет со дня опубликования, код Хаффмана ничуть не потерял своей актуальности и значимости. Так с уверенностью можно сказать, что мы сталкиваемся с ним, в той или иной форме (дело в том, что код Хаффмана редко используется отдельно, чаще работая в связке с другими алгоритмами), практически каждый раз, когда архивируем файлы, смотрим фотографии, фильмы, посылаем факс или слушаем музыку.
Задача построения кода Хаффмана равносильна задаче построения соответствующего ему дерева. Общая схема построения дерева Хаффмана:
1. Составляется список кодируемых символов (при этом каждый символ рассматривается как одноэлементное бинарное дерево, вес которого равен весу символа).
2. Из списка выбирается 2 узла с наименьшим весом.
3. Формируется новый узел и к нему присоединяется, в качестве дочерних, два узла выбранных из списка. При этом полагается, что вес сформированного узла равен сумме весов дочерних узлов.
4. Сформированный узел добавляется к списку.
5. Если в списке больше одного узла, то повторяется 2-5.
2. ОБОСНОВАНИЕ И ОПИСАНИЕ АЛГОРИТМОВ КОДИРОВАНИЯ
2.1 Описание алгоритма, реализующего код Хаффмана
Во входящей последовательности для каждого символа подсчитывается частота его «встречаемости» в ней. Затем по полученным частотам строится бинарное дерево по восходящему принципу: листья - это самые низкие частоты; узлы, которые стоят выше листьев по иерархии - это суммарное количество частот листьев-детей; корень дерева - это сумма всех частот.
По бинарному дереву составляется бинарный код для каждого символа последовательности по принципу: совершается обход дерева с корня до необходимого символа, при проходе влево - в код записывается «0», вправо - «1».
Благодаря такому подходу символ, который встречается чаще всего, кодируется меньшим количеством битов, чем символ с меньшей частотой.
Ниже приведен пример кодирования последовательности «adamand» кодом Хаффмана. Итак, пошагово распишем действия:
1. Следует подсчитать частоты встречаемости всех символов во входящей последовательности:
«a» - 3 ; «d» - 2 ; «m» - 1 ; «n» - 1
2. Строим бинарное дерево, исходя из частот встречаемости. Полученное дерево изображено на рисунке 2.1:
Рисунок 2.1- Бинарное дерево Хаффмана
4. Итак, закодированная последовательность имеет вид: 0100110011110.
Блок-схемы, описывающие логику вышеописанного алгоритма, показаны на рисунках 2.2 - 2.5.
Рисунок 2.2 - Блок-схема алгоритма кодирования методом Хаффмана
Рисунок 2.3 - Блок-схема алгоритма построения дерева для кода Хаффмана
Рисунок 2.4 - Блок-схема алгоритма обхода дерева, формирования кодовой таблицы
Рисунок 2.5 - Блок-схема алгоритма декодирования методом Хаффмана
2.2 Описание алгоритма, реализующего код Голомба
Этот метод требует ввод определенного параметра М. Если значение M равно двойке в целой положительной степени, то код Голомба переходит в свой частный случай - код Райса.
Пусть есть число N, которое требуется закодировать, и фиксированное число М.
1. Находим частное q = N /М - деление целочисленное.
2. Находим остаток от деления N /М: r = N %М.
3. Закодированное число N имеет формат: <код q><код r>
3.1 Код q является просто унарным кодированием числа q, то есть представимо в виде: 111…110, где количество единиц равно самому числу q.
3.2 Для нахождения кода r введем параметр b=[log 2 (M)], причем b округляется в сторону большего целого, и параметр с = 2 b -M. Далее, если число 0 ? r < c, то код r - это просто бинарный код числа r, помещенный в количество бит, равное b-1;
если же r ? c, то код r - это бинарный код числа (r + c), помещенный в количество бит, равное b.
Блок-схема, описывающая логику вышеописанного алгоритма, показана на рисунке 2.6.
Рисунок 2.6 - Блок-схема алгоритма кодирования методом Голомба
2.3 Описание алгоритма, реализующего кодирование при помощи чисел Фибоначчи
Числа Фибоначчи - это последовательность чисел, в которой каждое последующее равно сумме двух предыдущих. То есть, 1,2,3,5,8,13…
Пусть числа Фибоначчи имеют свой порядковый номер, то есть F(1)=1;
F(2)=2; F(3)=3; F(4)=5; F(6)=8 и т.д.
Пусть есть число Х, которое следует закодировать с помощью чисел Фибоначчи. По сути, требуется разложить это число Х на числа Фибоначчи.
1. Находим число Фибоначчи наиболее близкое к числу Х. Пусть это будет число F x ; а i x - порядковый номер числа F x , то есть F(i x ) = F x .
3. Вычитаем из Х число F x . Повторяем шаги 1,2,3 до тех пор, пока Х>0.
4. В полученной кодовой последовательности на местах, где нет «1», ставим «0», а после последней «1» ставим еще одну «1».
Блок-схема, описывающая логику вышеописанного алгоритма, показана на рисунке 2.7.
Рисунок 2.7 - Блок-схема алгоритма кодирования с помощью чисел Фибоначчи
2.4 Описание алгоритма, реализующего гамма-код Элиаса
Пусть есть целое положительное число N, которое требуется закодировать.
1. Находим b = log 2 (N) - максимальная целая степень, возводя в которую «2», получаем число, максимально приближенное к N.
3. Гамма-код числа N имеет вид: <код b><код q>
3.1. Код b - инверсный унарный код числа b, то есть представимо в виде: 000…001, где количество нулей равно самому числу b.
3.2. Код q - просто бинарный код числа q, помещенный в количество бит, равное b.
Блок-схема, описывающая логику вышеописанного алгоритма, показана на рисунке 2.8.
Рисунок 2. 8 - Блок-схема алгоритма гамма - кодирования Элиаса
2.5 Описание алгоритма, реализующего дельта-код Элиаса
Пусть есть целое положительное число N, которое требуется закодировать.
1. Находим b = log 2 (N) - максимальная целая степень, возводя в которую «2»,
получаем число, максимально приближенное к N.
4. Дельта-код числа N имеет вид: <код b1><код q>
4.1. Код b1 - гамма-код Элайеса числа b1.
4.2. Код q - просто бинарный код числа q, помещенный в количество бит, равное b.
Блок-схема, описывающая логику вышеописанного алгоритма, показана на рисунке 2.9.
Рисунок 2. 9 - Блок-схема алгоритма дельта - кодирования Элиаса
3. ОБОСНОВАНИЕ И ОПИСАНИЕ ПРОГРАММ КОДИРОВАНИЯ
- базируясь на стандартных компонентах создавать интерфейс приложения в зависимости от состояния системы передавать управление различным процессам;
- создавать базы данных и оболочки для баз данных;
- выполнять корректную обработку исключительных ситуаций, что позволяет повысить надёжность ПО.
Современные средства разработки характеризуются следующими параметрами:
- поддержка объектно-ориентированного стиля программирования;
- возможность использования CASE-технологий для проектирования разрабатываемой системы, использование визуальных компонент для наглядного проектирования интерфейса;
- наличие визуальной технологии разработки интерфейса;
- возможность использования алгоритмов реляционной алгебры для управления реляционными базами данных;
- предоставление средств синхронизации и контроля версий составных частей проекта (эти средства используются при разработке программного обеспечения группами программистов);
- создание инсталляционных пакетов для распространения разработанного программного обеспечения.
При создании прототипа программного обеспечения главными критериями выбора программно-инструментальных средств разработки являются:
- возможность быстрого внесения изменений в программу;
Обеспечить минимальное время разработки можно только при выполнении этих условий. Исходя из приведенных требований, выделим следующие характеристики средств разработки программного обеспечения:
- наглядность разработки интерфейса;
- предоставляемые возможности работы с базами данных;
- скорость работы разработанного программного обеспечения;
- обработка исключительных ситуаций;
- время создания разработанного программного обеспечения;
- средства контроля версий составных частей проекта;
- наличие удобной справочной системы.
Для выбора инструментального средства воспользуемся методом вариантных сетей. Этот метод предназначен для выбора наилучшего варианта из нескольких предложенных и состоит из следующих этапов:
- определение критериев, по которым будет произведено сравнение и
- каждый вариант оценивается по полученному перечню критериев (получается численное значение - оценка);
- нахождение общего количества баллов для каждого из вариантов (можно учитывать важность критериев).
Для решения поставленной задачи будем использовать перечень характеристик, приведенный выше. Каждую характеристику будем оценивать балом в диапазоне [1..10], а так же весовым коэффициентом в том же диапазоне. Выбор будем проводить из таких программно-инструментальных средств разработки как: Java Eclipse,Borland Delphi 7, Microsoft VC++ 6. Лучшим будет тот вариант, который наберёт максимальное количество баллов. Выбор средств разработки методом вариантных сетей представлен в табл. 3.1.
Таблица 3.1 - Сравнение сред разработки методом вариантных сетей
Скорость работы разработанного программного обеспечения
Минимальное время создания разработанного программного обеспечения
В результате применения метода вариантных сетей установлено, что лучшим инструментальным средством с точки зрения разработчика в данном случае является среда Borland Delphi7.
3.2 Описание основных функций программы, реализующей алгоритмы кодирования по методу Хаффмана
Для программирования алгоритмов кодирования и декодирования с помощью кода Хаффмана реализованы два класса:
1. Класс Tree реализует структуру бинарного дерева, а также осуществляет обход дерева.
public child0: Tree; // левый потомок
public child1: Tree; // правый потомок
public leaf:boolean; // признак листа
public character:integer; // входной символ
public weight: integer; // частота вхождений символа
public constructor Create;overload;// создание пустого дерева
public constructor Create( character:integer; weight:integer; leaf:boolean);overload; // создание дерева с определенными параметрами
public procedure traverse( code:String ; h:Huffman); // обход дерева, //формирование таблицы кодировок символов
процедура Tree.traverse(code:String; h:Huffman);
if (leaf) then //если добрались до листа
writeln(Gf, chr(character),' ',weight ,' ', code); //сохраняем в файл
h.code[character] := code; // запоминаем код листа
if ( child0 <> nil) then child0.traverse(code + '0', h); //обход по левой //ветви
if ( child1 <> nil) then child1.traverse(code + '1', h);//обход по правой //ветви
2. Класс Huffman реализует всю логику построения и обработки
Методы арифметического кодирования информации и сравнение их коэффициентов сжатия дипломная работа. Программирование, компьютеры и кибернетика.
Доклад: Понятие и виды фандрайзинга
Вшэ Пермь Темы Курсовых Работ
Азиатский Способ Производства Эссе
Сочинение По Картине Финогеновой
Контрольная работа по теме Электронная техника
Дипломная работа по теме Розробка комплексних програм реабілітації дітей
Контрольная работа по теме Double electric layer. Mechanism of formation and theory of structure
Эссе Оператор Года Хрустальная Гарнитура
Курсовая Работа На Тему Пробелы В Праве
Курсовая работа по теме Задачи и функции уголовного права России
Курсовая работа по теме Разработка технологического процесса на ремонт нажимного диска сцепления ЗИЛ-431410, деталь № 130-161093
Реферат: Административно-правовые нормы 2
Реферат: Договор энергоснабжения: особенности заключения и исполнения условий договора с физическими лицами
Реферат по теме Федеральное собрание РФ
Отчет по практике: Хозяйственная деятельность предприятия ОАО "Комбинат Южуралникель"
Контрольная работа: Анализ данных как составляющая часть принятия решений
Курсовая работа по теме Проектирование червячной передачи редуктора
Реферат: Contrast Essay Research Paper The Perceptual ProcessThe
Ақшаның Адам Өміріндегі Рөлі Эссе
Курсовая работа по теме Методы повышения уровня общей лексической компетенции студентов-иностранцев, изучающих русский язык
Реализация норм права - Государство и право курсовая работа
Разработка оптико-электронного пеленгатора с фокальным матричным приёмником излучения - Коммуникации, связь, цифровые приборы и радиоэлектроника контрольная работа
Разработка базы данных по акту о приеме работ, выполненных по срочному трудовому договору, заключенному на время выполнения определенной работы - Государство и право курсовая работа