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

СОДЕРЖАНИЕ Перечень обозначений и сокращений

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

1.1 Унарный код

1.2 Код Голомба

1.3 Код Райса

1.4 Коды Фибоначчи

1.5 Гамма — коды Элиаса

1.6 Дельта — коды Элиаса

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

1.8 Коды Ивэн-Родэ

1.9 Код Левенштейна

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

1.11 Старт — шаг — стоп коды

1.12 Код Хаффмана

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.1 Цель и назначение

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

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

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

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

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

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

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

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

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

4.4 Выводы

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

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

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

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

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

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

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

5.3.4 Шум и вибрация

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

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

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

Заключение

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

Приложение, А — Листинг программы кодирования-декодирования

ПЕРЕЧЕНЬ ОБОЗНАЧЕНИЙ И СОКРАЩЕНИЙ

Unar — унарный код ДБН — державні будівельні норми ДНАОП — державний нормативний акт про охорону праці

КЕО — коэффициент естественного освещения НДС — Налог на добавленную стоимость НИР — научно-исследовательская работа НИОКР — коэффициент научно-технического эффекта ПУЭ — правила устройства электроустановок СНиП — Система норм и правил

ВВЕДЕНИЕ

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

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

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

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

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

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

1. МЕТОДЫ АРИФМЕТИЧЕСКОГО КОДИРОВАНИЯ

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

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

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

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

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

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

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

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

· Variable+Fixed (переменная длина экспоненты — фиксированная длина мантиссы) В данной работе будут рассмотрены коды переменной длины (Variable+Variable).

1.1 Унарный код Унарный код сопоставляет числу 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) с параметром =:

p=(1-), (1.1)

где i=1,2,

Для значений < более эффективен код Голомба.

1.2 Код Голомба Коды Голомба — это семейство энтропийных кодеров, являющихся общим случаем унарного кода. Кодирование энтропиикодирование словами (кодами) переменной длины, при которой длина кода символа имеет обратную зависимость от вероятности появления символа в передаваемом сообщении. Обычно энтропийные кодировщики используют для сжатия данных коды, длины которых пропорциональны отрицательному логарифму вероятности символа. Таким образом, наиболее вероятные символы используют наиболее наиболее короткие коды. Согласно теореме Шеннона оптимальная длина кода для символа равнаlogP, где bэто количество символов, используемых для изготовления выходного кода, и Рвероятность входного символа. Унарный код — это энтропийное кодирование, которое представляет число n в виде n единиц с замыкающим нулем (либо n нулей и единица). Например, 5 представляется в виде 111 110. Унарное кодирование оптимально для распределения вероятности: 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;

· результирующее кодовое слово — 111 001.

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

Таблица 1.1 — Коды Голомба для различных параметров m

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

Рисунок 1.2 — Формирование кодов Голомба

1.3 Код Райса Код Райса идентичен коду Голомба, когда m является степенью двойки. На самом деле данные коды имеют параметр k, по которому вычисляется значение m = 2^k.

Введем параметр Т=2. Код Райса для числа n состоит из двух частей. Первая часть — унарный код числа [], вторая часть — двоичная запись в виде последовательности длины k остатка от деления n на T. Очевидно, длина кода Райса для числа n равна l_n=[]+1+k. Например, при k=3 и n=21 имеем []=2, остаток равен 5. Поэтому кодом Райса числа 21 будет последовательность 110 101.

Рассмотрим несколько примеров кодов Райса для различных параметров k, которые представлены в таблице 1.2:

Таблица 1.2 — Коды Райса для различных параметров k

Код Райса — это частный случай кода Голомба, это легко увидеть из таблицы 1.3, представленной ниже:

Таблица 1.3 — Сравнительная таблица кода Райса и кода Голомба

1.4 Коды Фибоначчи Самые интересные, нетривиальные коды. В данном кодировании исходное число n раскладывается в сумму чисел Фибоначчи f_i (f₁ = 1; f₂ = 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} задается рекуррентным соотношением:

F =1, F=1, F=F+F, nN

Иногда числа Фибоначчи рассматривают и для неположительных номеров n как двусторонне бесконечную последовательность, удовлетворяющую основному соотношению. Члены с такими номерами легко получить с помощью эквивалентной формулы «назад» (1.5):

F=FF (1.5)

Пример двусторонне бесконечной последовательности чисел Фибоначчи представлен в таблице 1.5:

Таблица 1.5-Двусторонняя последовательность чисел Фибоначчи в интервале [-7.7]

Легко видеть, что F =(-1)F.

1.5 Гаммакоды Элиаса Гамма-код Элиаса — двоичный префиксный код представления натуральных чисел. Число кодируется в два этапа. Определяется количество двоичных разрядов кодируемого числа. Вначале кодируется n посредством инвертированного унарного кода, после чего в неизменном виде дописываются n младших разрядов (старший единичный разряд, таким образом, опускается). Иными словами, код представляет собой число в двоичном представлении, заполненное нулями на 1 меньшей длины. В сумме длина кода должна равняться 2 n + 1. В таблице 1.6 приведены гамма-коды Элиаса малых натуральных чисел:

Таблица 1.6 — Гамма-коды Элиаса малых натуральных чисел

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

Дельта-код Элиаса является производным от гамма-кода. В начале кодируется количество значащих двоичных разрядов в числе посредством гамма-кода, после чего записываются все значащие разряды, за исключением старшей единицы (общим количеством на 1 меньше закодированного количества). В таблице 1.7 приведены дельта-коды Элиаса для некоторых чисел. Закодированное количество разрядов и остальная часть числа разделены пробелом. Знаки х соответствуют разрядам двоичного представления кодируемого числа.

Таблица 1.7 — Дельта-коды Элиаса для некоторых чисел

Дельта-код даёт более оптимальное распределение длин для больших чисел, чем для малых (отношение длины кода к числу его разрядов стремится к единице).

Несколько примеров г и д кодов Элиаса приведены в таблице 1.8:

Таблица 1.8 — г и д коды Элиаса

1.7 Омега-код Элиаса Омега-код Элиаса (рекурсивный код Элиаса) состоит из нескольких битовых групп, начинающихся с единичного бита, и замыкаемых нулевым битом. Первая группа всегда имеет длину 2 бита. Длина каждой последующей группы определяется как на единицу большая, чем значение предыдущей. Последняя группа выражает кодируемое число. Исключение составляет число 1, оно кодируется единственным битом 0. Примеры кодов приведены в таблице 1.9:

Таблица 1.9 — Омега коды Элиаса

Количество групп в коде возрастает быстро вначале, но далее — очень медленно:

· для 1 будет 0 групп;

· 2 … 3 (2¹ … 2²? 1) — 1 группа;

· 4 … 15 (2² … 2²²? 1) — 2 группы;

· 16 … 65 536 (2²² … 2²²²? 1) — 3 группы;

· 65 536 … 2 · 10^19 728 (2²²² … 2²²²²? 1) — всего 4 группы.

1.8 Коды ИвэнРодэ Данные коды, также как и омега-коды Элиаса, состоят из последовательности групп длинной L₁, L₂, L₃, …, L_m бит [1], которые начинаются с бита 1. В конце последовательности следует 0. Длина каждой следующей (n+1)-й группы задается значением битов предыдущей n-й группы. Значение битов последней группы является итоговым значением всего кода, то есть всей последовательности групп. В сущности, все первые m?1 групп служат лишь для указания длины последней группы.

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

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

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

Рассмотрим несколько примеров кодов Ивэн-Родэ — таблица 1.10:

Таблица 1.10 — Коды Ивэн-Родэ

1.9 Код Левенштейна Этот код проще всего объяснить на конкретном примере. Предположим, что нужно передать число n=21. Двоичное представление этого числа имеет вид 10 101. Непосредственно использовать при кодировании двоичные представления натуральных чисел нельзя. Самый простой выход состоит в том, чтобы приписать в начале слова префикс, указывающий длину двоичной записи числа (в данном случае это число 5). Если это число закодировать унарным кодом и приписать слева к двоичной записи числа, то код получится однозначно декодируемым. В данном примере для числа 21 получим кодовое слово 11 111 010 101. В общем случае длина двоичного представления будет равна 2[logn].

Шаг за шагом будем улучшать этот способ кодирования. Важно заметить, что первая значащая цифра двоичной записи числа — всегда 1. Её можно не передавать, декодер сам допишет недостающую единицу, если будет знать длину двоичной записи числа. Обозначим через bin'(n) двоичную запись натурального числа n без первой единицы.

Длины кодовых слов равны (1.6):

l_n=2[log n]+1 (1.6)

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

Например, для числа 21 вычисляется bin'(21)=0101, затем bin'(4)=00, bin'(2)=0. Число итераций равно 3, поэтому кодовое слово кода Левенштейна имеет вид lev (21)=(1110)(0)(00)(0101)=11 100 000 101. Декодер кода Левенштейна, декодируя унарный код, узнает, что итераций было три. Прочитав один значащий разряд (0) и дописав к нему в начало 1, получает последовательность 10. Это означает, что на предпоследней итерации длина числа была 2. Прочитав 2 разряда и дописав слева 1, получает 100. Теперь декодер считает 4 разряда и дописывает слева 1. Получается последовательность 10 101, ей соответствует число 21. Поскольку это уже последняя 3-я итерация, число 21 является результатом декодирования.

Ниже приведена таблица 1.11 — таблица кодов Левенштейна для некоторых чисел натурального ряда.

Таблица 1.11 — примеры кодов Левенштейна

Коды Левенштейна и Элиаса практически эквивалентны, выигрыш кода Левенштейна проявляется только при астрономически больших значениях n.

1.10 Гамма-коды Левенштейна Данный код для числа n получается путем обращения последовательности битов в двоичной записи этого числа и добавления перед каждым битом, кроме последнего, флагового (flag bit) бита 0. Последним флаговым битом является бит 1, который совпадает с самым старшим битом в исходной двоичной записи числа n.

Рассмотрим несколько примеров кодов Левенштейна в таблице 1.12:

Таблица 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 и выглядят так:

Таблица 1.13 — Старт-шаг-стоп коды

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

Восстановление числа n по заданному {i, j, k}-start-step-stop коду

Пусть дан {i, j, k}-код и пусть количество единиц в унарной части (экспоненты) равно Q. Тогда число n (закодированное число) равно (1.7):

(1.7)

где в — мантисса записанного кода, Dec (x) — функция, переводящая x в десятичную систему счисления.

Получение {i, j, k}-start-step-stop кода по заданному числу n

Теперь наоборот, пусть задано число n. Для получения его кода необходимо найти такое минимальное положительное число Q₀, чтобы выполнялось неравенство (1.8):

. (1.8)

При этом сам код будет выглядеть так (1.9):

б (Q₀? 1): в (n + 2^IQ₀? S). (1.9)

Замечание

В качестве частных случаев Start-step-stop кодов могут быть получены следующие коды и они сведены в таблицу 1.14:

Таблица 1.14 — Частный случай старт-шаг-стоп кодов

1.12 Код Хаффмана Код Хаффмана (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- Бинарное дерево Хаффмана

3. Выписываем полученные коды:

«a» — 0

«d» — 10

«m» — 110

«n» — 111

4. Итак, закодированная последовательность имеет вид: 100 110 011 110.

Блок-схемы, описывающие логику вышеописанного алгоритма, показаны на рисунках 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₂(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.

2. В i_x-м бите кода ставим «1».

3. Вычитаем из Х число F_x. Повторяем шаги 1,2,3 до тех пор, пока Х>0.

4. В полученной кодовой последовательности на местах, где нет «1», ставим «0», а после последней «1» ставим еще одну «1».

Блок-схема, описывающая логику вышеописанного алгоритма, показана на рисунке 2.7.

Рисунок 2.7 — Блок-схема алгоритма кодирования с помощью чисел Фибоначчи

2.4 Описание алгоритма, реализующего гамма-код Элиаса Суть алгоритма кодирования:

Пусть есть целое положительное число N, которое требуется закодировать.

1. Находим b = log₂(N) — максимальная целая степень, возводя в которую «2», получаем число, максимально приближенное к N.

2. Находим число q = N — 2^b.

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₂(N) — максимальная целая степень, возводя в которую «2»,

получаем число, максимально приближенное к N.

2. Находим число q = N — 2^b.

3. Находим параметр b1=b+1

4. Дельта-код числа N имеет вид: <�код b1><�код q>

4.1. Код b1 — гамма-код Элайеса числа b1.

4.2. Код q — просто бинарный код числа q, помещенный в количество бит, равное b.

Блок-схема, описывающая логику вышеописанного алгоритма, показана на рисунке 2.9.

Рисунок 2. 9 — Блок-схема алгоритма дельта — кодирования Элиаса

3. ОБОСНОВАНИЕ И ОПИСАНИЕ ПРОГРАММ КОДИРОВАНИЯ

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

Современные программно-инструментальные средства разработки ПО характеризуются большим разнообразием характеристик. Так, в настоящее время инструментальные средства позволяют:

— базируясь на стандартных компонентах создавать интерфейс приложения в зависимости от состояния системы передавать управление различным процессам;

— создавать базы данных и оболочки для баз данных;

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

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

— поддержка объектно-ориентированного стиля программирования;

— возможность использования CASE-технологий для проектирования разрабатываемой системы, использование визуальных компонент для наглядного проектирования интерфейса;

— наличие визуальной технологии разработки интерфейса;

— возможность использования алгоритмов реляционной алгебры для управления реляционными базами данных;

— предоставление средств синхронизации и контроля версий составных частей проекта (эти средства используются при разработке программного обеспечения группами программистов);

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

При создании прототипа программного обеспечения главными критериями выбора программно-инструментальных средств разработки являются:

— скорость разработки приложений;

— удобство использования;

— возможность быстрого внесения изменений в программу;

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

— стоимость IDE;

— невысокая потребность ресурсов;

— наглядность разработки интерфейса;

— предоставляемые возможности работы с базами данных;

— скорость работы разработанного программного обеспечения;

— обработка исключительных ситуаций;

— время создания разработанного программного обеспечения;

— удобство эксплуатации;

— средства контроля версий составных частей проекта;

— наличие удобной справочной системы.

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

— определение критериев, по которым будет произведено сравнение и

— степени их важности;

— каждый вариант оценивается по полученному перечню критериев (получается численное значение — оценка);

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

Для решения поставленной задачи будем использовать перечень характеристик, приведенный выше. Каждую характеристику будем оценивать балом в диапазоне [1.10], а так же весовым коэффициентом в том же диапазоне. Выбор будем проводить из таких программно-инструментальных средств разработки как: Java Eclipse, Borland Delphi 7, Microsoft VC++ 6. Лучшим будет тот вариант, который наберёт максимальное количество баллов. Выбор средств разработки методом вариантных сетей представлен в табл. 3.1.

Таблица 3.1 — Сравнение сред разработки методом вариантных сетей

В результате применения метода вариантных сетей установлено, что лучшим инструментальным средством с точки зрения разработчика в данном случае является среда Borland Delphi7.

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

Для программирования алгоритмов кодирования и декодирования с помощью кода Хаффмана реализованы два класса:

1. Класс Tree реализует структуру бинарного дерева, а также осуществляет обход дерева.

Tree = class

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); // обход дерева, //формирование таблицы кодировок символов

end;

процедура Tree. traverse (code:String; h: Huffman);

begin

if (leaf) then //если добрались до листа

begin

writeln (Gf, chr (character),' ', weight ,' ', code); //сохраняем в файл

h.code[character] := code; // запоминаем код листа

end;

if (child0 <> nil) then child0. traverse (code + '0', h); //обход по левой //ветви

if (child1 <> nil) then child1. traverse (code + '1', h);//обход по правой //ветви

end;

2. Класс Huffman реализует всю логику построения и обработки бинарного дерева, а также осуществляет принципы кодирования и декодирования методом Хаффмана.

Huffman = class

weights:array[0.ALPHABETSIZE] of integer; // массив частот //вхождений символов в последовательности

public code: array[0.ALPHABETSIZE]of string; // массив строк-кодов //для символов последовательности

public procedure growTree (data:array of integer);// рост дерева из //источника data

public function coder (data:array of integer):string;//кодирование //последовательности data по дереву

public function decoder (data:String):string;//декодирование кода data по //дереву

end;

Gtreeмассив деревьев, глобальная переменная.

— процедура построения дерева Huffman. growTree (data:array of integer);

var i, used, c, w, min, weight0: integer ;

temp:Tree;

begin

for i:=0 to length (data)-1 do

weights[data[i]]: = weights[data[i]]+1; //вычисление и запоминание //частот в массив weights

used := 0; // количество ненулевых частот символов

for c:=0 to ALPHABETSIZE-1 do //обход по всевозможным символам

begin

w := weights[c];

if (w <> 0) then begin // если частота символа с не равна 0

Gtree[used] := Tree. Create (c, w, true); //в массив деревьев

//добавляем новое дерево

used:=used+1;

end;

end;

while (used > 1) do // просмотр всех деревьев в массиве

begin

min := getLowestTree (used); //поиск дерева с мин. частотой

weight0 := Gtree[min]. weight;

temp := Tree. Create; //создаем узел, связывающего деревья с //минимальными частотами

temp.child0 := Gtree[min]; // создаем левого потомка узла

used:=used-1;

Gtree[min] := Gtree[used];

min := getLowestTree (used);

temp.child1 := Gtree[min];

temp.weight := weight0 + Gtree[min]. weight;

Gtree[min] := temp; //ставим узел на место правого потомка узла

end;

end;

— функция кодирования Huffman. coder (data:array of integer):string;

var str: string;

i:integer;

begin

str := '';

for i:=0 to length (data)-1 do // просмотр всех символов посл-ти data

str :=str+ code[data[i]]; // извлечение кода из полученной таблицы

//code и накопление строки-кода всей посл-ти

result:=str;

end;

— функция декодирования Huffman. decoder (data:String):string;

var str: string;

c:integer;

begin

str:='';

while (length (data) > 0) do // пока строка для декодирования существует

for c:=0 to ALPHABETSIZE-1 do //просмотр всевозможных символов

if (weights[c]>0) and (Pos (code[c], data)=1) then // если символ с хотя бы //раз встречался и его код стоит вначале строки-кода, то можно его //преобразовать

begin

data:= copy (data, Length (code[c])+1,length (data)); //сокращаем //строку-код на код символа с

str := str+chr (c); //формируем строку-декодинг

end;

result:=str;

end;

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

Golomb_M — параметр M в кодировании методом Голомба

— функция кодирования одного целого положительного числа

function GolombCodingOne (n:integer):string;

// n — число, которое следует закодировать

// возвращаемый результат — строка-код числа

var q, r, b, cutoff, i: integer;

bin:string;

begin

q:= n div Golomb_M; //нахождение частного от деления числа n на

//параметр Golomb_M

r:= n mod Golomb_M; //нахождение остатка от деления числа n на

//параметр Golomb_M

result:=UnaringCode (q); //получаем первую часть кода — унарный код

//частного q

b:= ceil (math.Log2(Golomb_M));// получаем параметр b

cutoff:=round (power (2,b))-Golomb_M; // получаем параметр с

if (r< c

begin

bin:=GetBinary®; //получаем бинарный код числа r в виде строки

for i:=1 to (b-1)-length (bin) do

result:=result+'0';

result:=result+bin; // наращивание строки-кода

end

else // диапазон r? c

begin

bin:=GetBinary (r+cutoff); //получаем бинарный код числа r+с в виде

//строки

for i:=1 to (b)-length (bin) do

result:=result+'0';

result:=result+bin; // наращивание строки-кода

end;

end;

— функция декодирования GolombDecoding (name:string):string;

// name — имя файла, в котором содержится закодированная //последовательность;

//возвращаемое значение — строка-декодинг

var kol, i, M, q, b, b1, b2,cutoff:integer;

s_temp:string;

f:textfile;

c:char;

begin

assignfile (f, name); //привязка логического файла к физическому

reset (f); // открытие файла для чтения

readln (f); // пропускаем первую строку в файле

readln (f, M); // считываем с файла число Голомба — М

b:=ceil (math.Log2(M)); //считаем параметр b

cutoff:=round (power (2,b))-M; //считаем параметр с

s_temp:=''; result:='';

read (f, c);

while not (eof (f)) do //идем до конца файла

begin

kol:=0;

while c<>'0' do //считываем унарный код

begin

read (f, c);

kol:=kol+1;

end; //q

q:=kol; //по считанному унарному коду определяем частное q

s_temp:='';

for i:=1 to b-1 do //считывание b-1битов кода

begin

read (f, c);

s_temp:=s_temp+c;

end;

b1:=BinToInt (s_temp); //считаем возможный остаток b1

read (f, c);

s_temp:=s_temp+c//считывание b битов кода

b2:=BinToInt (s_temp);// считаем возможный остаток b2

if (b2<=cutoff)or (b2-cutoff>=M)or (b2-cutoff<=cutoff-1) then //проверка

//условия формирования кода остатка по методу Голомба

//в зависимости от условия остатком является либо b1, либо b2

result:=result+Code_table[q*M+b1]

else

begin

result:=result+Code_table[q*M+b2-cutoff];

read (f, c);

end;

end;

closefile (f); //закрываем файл

end;

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

Fib_arr — массив с числами Фибоначчи, глобальная переменная.

— процедура генерации чисел Фибоначчи

procedure GenerateFib (n:integer);

//n — количество генерируемых чисел

var i: integer;

begin

Fib_arr[1]: =1; //инициализация первого числа Фиб.

Fib_arr[2]: =2; //инициализация второго числа Фиб.

for i:=3 to n do

Fib_arr[i]: =Fib_arr[i-1]+Fib_arr[i-2]; //число Фиб. = сумме предыдущих двух

//чисел Фиб.

end;

— функция кодирования одного целого положительного числа

function FibCodingOne (one:integer):string;

// one — число, которое надо закодировать

// возвращаемое значение — строка-код числа one

var i, kol: integer;

one_temp:integer;

last:boolean;

begin

one_temp:=one;

kol:=0;

result:='';//инициализация выходной строки

for i:=1 to FIB_MAX_LENGTH do

result:=result+'$'; // забиваем выходную строку символами «$»

last:=true;

//search closest Fib number

while (one_temp>0) do //пока число можно разложить на числа Фиб.

for i:=1 to FIB_MAX-1 do //ищем большее число Фиб.

if (one_temp>=Fib_arr[i])and (one_temp

begin //нашли его на месте i

result[i]: ='1'; // в i-й бит записываем «1»

one_temp:=one_temp-Fib_arr[i]; // уменьшаем число на большее число Фиб.

if (last) then begin

result[i+1]: ='1'; //записываем дополнит. «1» в конце кодовой посл-ти

last:=false;

kol:=i+1;

end;

break;

end;

delete (result, kol+1,length (result)-kol); // урезаем кодовую строку до

//оптимального размера

for i:=1 to length (result) do //обнуляем неединичные символы кодовой строки

if (result[i]<>'1') then

result[i]: ='0';

end;

— функция декодирования одного числа

function FibOneDecoding (s_tmp:string):integer;

// s_tmp — строка-код числа

// возвращаемое значение — раскодированное число

var i, kol: integer;

begin

kol:=0; // начальная инициализация числа-декодинга

for i:=1 to length (s_tmp)-1 do // проход по всем символам строки-кода

if (s_tmp[i]='1') then // нашли единичный бит

kol:=kol+ Fib_arr[i]; // складываем число из чисел Фибоначчи

result:=kol;

end;

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

— функция кодирования одного положительного целого числа методом гамма-кодирования Элиаса

function ElGammaCodingOne (one:integer):string;

// one — число, которое требуется закодировать

// возвращаемое значение — строка-гамма-код для числа one

var kol, temp, i: integer;

bin:string;

begin

temp:=one;

kol:=0;

while (temp>0)do // делим на «2» число one максимальное кол-во раз

begin

temp:=temp div 2;

kol:=kol+1; //считаем количество «2», на которые поделили число one

end;

kol:=kol-1; // kol = параметру b схемы решения

result:='';

for i:=1 to kol do

result:=result+'0'; //заполняем «0» унарный код

result:=result+'1'; //в строку-код занесен унарный код числа b

bin:=GetBinary (one mod strtoint (floattostr ((power (2,kol))))); // получаем

//бинарное представление числа q схемы решения

for i:=1 to kol-length (bin) do

result:=result+'0';

if one>1 then

result:=result+bin; //добавляем в гамма-код бинарное представление

//остатка q

end;

— функция декодирования гамма-кода

function ElGammaDecoding (name:string):string;

// name — имя файла с дельта-кодом

// возвращаемое значение — раскодированная информация в виде строки

begin

assignfile (f, name); //связывание логического и физического имен файла

reset (f); //открываем файл для чтения

s_temp:='';

result:='';

while not (eof (f)) do //идем до конца файла

begin

kol:=0;

read (f, c);

while c<>'1' do // читаем с файла символы, пока не достигнем «1»

begin

read (f, c);

kol:=kol+1; // считаем количество «0» унарного кода

end;

s_temp:='';

for i:=1 to kol do //количество «0» унарного кода = кол-ву битов после «1»

begin

read (f, c);

s_temp:=s_temp+c; //формируем бинарную строку числа q из схемы

//решения

end;

result:=result+chr (BinToInt (s_temp)+strtoint (floattostr (power (2,kol))));// //накапливаем строку-декодинг, высчитывая код посчитанного числа из //параметров q, b

end;

closefile (f); //закрываем файл

end;

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

— функция дельта-кодирования одного положительного целого числа

function ElDeltaCodingOne (one:integer):string;

// one — число, которое необходимо закодировать

// возвращаемое значение — строка-дельта-код числа one

var kol, temp, i: integer;

bin:string;

begin

if one=1 then //если число one=1, то сразу определяем его дельта-код = «1»

begin

result:='1';

exit;

end;

temp:=one;

kol:=0;

while (temp>0)do // делим на «2» число one максимальное кол-во раз

begin

temp:=temp div 2; //считаем количество «2», на которые поделили число one

kol:=kol+1;

end;

result:=ElGammaCodingOne (kol); //kol = b1 из схемы решения, ищем гамма;

//код Элайеса параметра b1 (kol)

bin:=GetBinary (one mod strtoint (floattostr ((power (2,kol-1)))));//получаем

//бинарное представление числа q схемы решения

for i:=1 to kol-length (bin)-1 do

result:=result+'0';

if one>1 then

result:=result+bin; //добавляем в дельта-код бинарное представление

//остатка q

end;

— функция декодирования дельта-кода Элайеса

function ElDeltaDecoding (name:string):string;

// name — имя файла с дельта-кодом

// возвращаемое значение — декодированная информация в виде строки

var kol, i, pow:integer;

s_temp:string;

f:textfile;

c:char;

begin

assignfile (f, name); //связывание логического имени файла с физическим

reset (f); // открытие файла для чтения

s_temp:='';

result:='';

while not (eof (f)) do //идем до конца файла

begin

kol:=0;

read (f, c);

while c<>'1' do //считываем «0» пока не встретим «1»

begin

read (f, c);

kol:=kol+1;// считаем количество нулей kol

end;

s_temp:='';

for i:=1 to kol do //накапливаем строкубинарный код гамма-части кода

begin

read (f, c);

s_temp:=s_temp+c;

end;

pow := BinToInt (s_temp)+strtoint (floattostr (power (2,kol))); //нашли

//параметр b1 из схемы решения

s_temp:='';

for i:=1 to pow-1 do

begin

read (f, c);

s_temp:=s_temp+c; //накапливаем строкубинарный код числа q из схемы

//решения

end;

result:=result+ Chr (BinToInt (s_temp)+strtoint (floattostr (power (2,pow-1))));

//вычисляем дельта-закодированное число и добавляем его к //результирующей строке-декодинга

end;

closefile (f); //закрываем файл

end;

4 ТЕХНИКО-ЭКОНОМИЧЕСКОЕ ОБОСНОВАНИЕ РАЗРАБОТКИ ПРОГРАММНО-АППАРАТНЫХ СРЕДСТВ ОПТИМАЛЬНОГО АРИФМЕТИ-ЧЕСКОГО КОДИРОВАНИЯ

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

4.2 Расчет себестоимости и цены изделия Производственная себестоимость промышленной продукции (работ, услуг) — это выраженные в денежной форме текущие расходы предприятия на её производство. Это один из основных экономических показателей предприятия, и это обуславливает необходимость однозначного определения методики его расчета не зависимо от того, где будет использоваться показатель производственной себестоимости. В качестве такой методики являются «Методические указания по формированию себестоимости продукции (работ, услуг) в промышленности», утвержденной приказом № 7 Госкомитета промышленной политики Украины от 2.02.2002г.

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

Расходы, включаемые в себестоимость продукции (работ, услуг) группируются по следующим экономическим элементам

— материальные расходы

— расходы на оплату труда

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

— амортизация

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

4.2.1 В состав элемента «Материальные расходы» включаются расходы:

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

Расчет ведется по формуле (4.1):

(4.1)

где — норма расходаго материала на единицу продукции;

— цена единицыго материала;

— количество видов материала.

Расчеты приведены в таблице 4.1:

Таблица 4.1 — Расчет стоимости сырья и материалов

Продолжение таблицы 4.1

4.2.2 Расходы на оплату труда в состав элемента включается: заработная плата по окладам и тарифам, надбавки и доплаты к тарифным ставкам и должностным окладам в размерах, предусмотренным действующим законодательством; премии и поощрения материальная помощь, компенсационные выплаты, оплату отпусков и другого неотработанного времени, другие расходы на оплату труда персонала, занятого непосредственно на выполнении конкретной темы (научные работники, научно-технический, научно-вспомогательный персонал и производственные рабочие)