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

 

СОДЕРЖАНИЕ

Перечень обозначений и сокращений

Введение

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

.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 50000000000001100101000100121101000110100103111010110001101104111101100101010000111511111011011011100110006111111011100110010101001711111110111011101010111010811111111011110011011110001011091111111110111101111001100110111101111111111011111001110101101011000111111111111101111101111011110111100112111111111111011111100111100111000110101311111111111110111111011111010111001110110141111111111111101111111001111011111010110111151111111111111110111111101111110011101111100016111111111111111101111111100111110101111000111001171111111111111111101111111101111110111111001111010

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

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

.3 Код Райса

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

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

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

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

n\ k 1 2 3 456000000000000000000000000000110001000100001000001000000121100100010000100000100000010311100110011000011000011000001141111010000100000100000100000010051111101001010100010100010100001016111111010100110000110000110000011071111111010110111000111000111000011181111111101100010000001000001000000100091111111110110011000100100100100100010011011111111110110101001000101000101000010101111111111111011011100110010110010110001011121111111111110111000101000011000011000001100131111111111111011100110101001101001101000110114111111111111110111010101100011100011100001110151111111111111110111011101110011110011110001111

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

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

Код Голомбаm=1m=2m=3m=4m=5m=6m=7m=8Код Райсаk=0k=1k=2k=3n=1000000000000000000000 2100101000100100100100001 3110100011010010010000110010 411101011000110110010101000011 5111101100101010000111011001010100 61111101101101110011000011101100101 7111111011100110010101001100001110110 8…111011101010111010100110000111 9…111100110111100010110101001001010000

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

Самые интересные, нетривиальные коды. В данном кодировании исходное число n раскладывается в сумму чисел Фибоначчи fi (f1 = 1; f2 = 2; fi = fi?1 + fi?2). Известно, что любое натуральное число однозначно представимо в виде суммы чисел Фибоначчи. Поэтому можно построить код числа как последовательность битов, каждый из которых указывает на факт наличия в n определенного числа Фибоначчи.

Заметим также, что если в разложении числа n присутствует fi, то в этом разложении не может быть числа fi+1. Поэтому логично для конца кода использовать дополнительную единицу. Тогда две идущие подряд единицы будут означать окончание кодирования текущего числа.

Рассмотрим несколько примеров кодов Фибоначчи в таблице 1.4:

Таблица 1.4 - Примеры кода Фибоначчи

n\f1235813213411(1)201(1)3001(1)4101(1)50001(1)61001(1)70101(1)800001(1)…………………1210101(1)13000001(1)……………………20010101(1)210000001(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=F- F (1.5)

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

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

n -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7F 13 -8 5 -3 2 -1 1 0 1 1 2 3 5 8 13

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

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

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

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

ЧислаКодДлина1112-301х34-7001хх58-150001ххх716-3100001хххх932-63000001ххххх1164-1270000001хххххх13

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

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

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

ЧислаКодДлина1112-3010 х44-7011 хх58-1500100 ххх816-3100101 хххх932-6300110 ххххх1064-12700111 хххххх11128-2550001000 ххххххх14256-5110001001 хххххххх15

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

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

Таблица 1.8 - ? и ? коды Элиаса

n-код-код0-1110 12…301х0 01х4…7001хх0 001хх8…150001ххх0 0001ххх16…3100001хххх0 00001хххх32…63000001ххххх0 000001ххххх

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

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

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

ЧислоКодДлина1012-31х 034-710 1хх 068-1511 1ххх 0716-3110 100 1хххх 01132-6310 101 1ххххх 01264-12710 110 1хххххх 013128-25510 111 1ххххххх 014256-51111 1000 1хххххххх 016512-102311 1001 1ххххххххх 017

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

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

·2 ... 3 (21 ... 22 ? 1) - 1 группа;

·4 ... 15 (22 ... 222 ? 1) - 2 группы;

·16 ... 65536 (222 ... 2222 ? 1) - 3 группы;

·65536 ... 2 · 1019728 (2222 ... 22222 ? 1) - всего 4 группы.

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

Данные коды, также как и омега-коды Элиаса, состоят из последовательности групп длинной L1, L2, L3, …, Lm бит [1], которые начинаются с бита 1. В конце последовательности следует 0. Длина каждой следующей (n+1)-й группы задается значением битов предыдущей n-й группы. Значение битов последней группы является итоговым значением всего кода, то есть всей последовательности групп. В сущности, все первые m?1 групп служат лишь для указания длины последней группы.

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

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

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

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

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

nКод Ивэн-Родэ00001001201030114100 016101 10000 032110 100000 0100111 1100100 0

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

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

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

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

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)=11100000101. Декодер кода Левенштейна, декодируя унарный код, узнает, что итераций было три. Прочитав один значащий разряд (0) и дописав к нему в начало 1, получает последовательность 10. Это означает, что на предпоследней итерации длина числа была 2. Прочитав 2 разряда и дописав слева 1, получает 100. Теперь декодер считает 4 разряда и дописывает слева 1. Получается последовательность 10101, ей соответствует число 21. Поскольку это уже последняя 3-я итерация, число 21 является результатом декодирования.

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

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

nКод ЛевенштейнаLev(n)ln101210033101341100006……671100116811010007……71511011117161110000000011……113111100001111113211100010000012……1263111000111111122101111110262101001101041

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

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

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

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

Таблица 1.12 - Коды Левенштейна

nГамма-код Левенштейна115010011301000116301010101011129010000000000001

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

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 - Старт-шаг-стоп коды

Кодовое словоДиапазон0xxx0-710xxxxx8-39110xxxxxxx40-167111xxxxxxxxx168-679

Далее приводится общая формула для восстановления числа по коду, а также алгоритм, позволяющий получить код по заданному числу 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. Для получения его кода необходимо найти такое минимальное положительное число Q0, чтобы выполнялось неравенство (1.8):

.(1.8)

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

?(Q0 ? 1) : ?(n + 2IQ0 ? S). (1.9)

Замечание

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

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

{i, j, k}Диапазонk, 1, kпростой бинарный код для целых чисел0, 1, ??-код Элиасаk, k, ??-код Элиаса по основанию 2k

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

Код Хаффмана (Huffman code) ещё называют минимально-избыточным префиксным кодом (minimum-redundancy prefix code). Идея, лежащая в основе кода Хаффмана, достаточно проста. Вместо того чтобы кодировать все символы одинаковым числом бит (как это сделано, например, в ASCII кодировке, где на каждый символ отводится ровно по 8 бит), символы которые встречаются чаще, кодируются меньшим числом бит, чем те, которые встречаются реже. Код при этом должен быть оптимален или, другими словами, минимально-избыточен.

Первым такой алгоритм опубликовал Дэвид Хаффман в 1952 году. Алгоритм Хаффмана двухпроходный. На первом проходе строится частотный словарь и генерируются коды. На втором проходе происходит непосредственно кодирование.

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

Задача построения кода Хаффмана равносильна задаче построения соответствующего ему дерева. Общая схема построения дерева Хаффмана:

1.Составляется список кодируемых символов (при этом каждый символ рассматривается как одноэлементное бинарное дерево, вес которого равен весу символа).

2.Из списка выбирается 2 узла с наименьшим весом.

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

.Сформированный узел добавляется к списку.

.Если в списке больше одного узла, то повторяется 2-5.

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

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

Суть алгоритма:

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

По бинарному дереву составляется бинарный код для каждого символа последовательности по принципу: совершается обход дерева с корня до необходимого символа, при проходе влево - в код записывается «0», вправо - «1».

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

Ниже приведен пример кодирования последовательности «adamand» кодом Хаффмана. Итак, пошагово распишем действия:

. Следует подсчитать частоты встречаемости всех символов во входящей последовательности:

«a» - 3 ; «d» - 2 ; «m» - 1 ; «n» - 1

. Строим бинарное дерево, исходя из частот встречаемости. Полученное дерево изображено на рисунке 2.1:

Рисунок 2.1- Бинарное дерево Хаффмана

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

«a» - 0

«d» - 10

«m» - 110

«n» - 111

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

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

Рисунок 2.2 - Блок-схема алгоритма кодирования методом Хаффмана

Рисунок 2.3 - Блок-схема алгоритма построения дерева для кода Хаффмана

Рисунок 2.4 - Блок-схема алгоритма обхода дерева, формирования кодовой таблицы

Рисунок 2.5 - Блок-схема алгоритма декодирования методом Хаффмана

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

Суть алгоритма кодирования:

Этот метод требует ввод определенного параметра М. Если значение M равно двойке в целой положительной степени, то код Голомба переходит в свой частный случай - код Райса.

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

Шаги алгоритма:

. Находим частное q = N /М - деление целочисленное.

. Находим остаток от деления N /М: r = N %М.

. Закодированное число N имеет формат: <код q><код r>

.1 Код q является просто унарным кодированием числа q, то есть представимо в виде: 111…110, где количество единиц равно самому числу q.

.2 Для нахождения кода r введем параметр b=[log2(M)], причем b округляется в сторону большего целого, и параметр с = 2b-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 и т.д.

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

Итак, опишем пошагово алгоритм:

. Находим число Фибоначчи наиболее близкое к числу Х. Пусть это будет число Fx ; а ix - порядковый номер числа Fx, то есть F(ix) = Fx.

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

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

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

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

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

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

Суть алгоритма кодирования:

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

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

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

. Гамма-код числа N имеет вид: <код b><код q>

.1. Код b - инверсный унарный код числа b, то есть представимо в виде: 000…001, где количество нулей равно самому числу b.

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

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

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

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

Суть алгоритма кодирования:

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

. Находим b = log2(N) - максимальная целая степень, возводя в которую «2»,

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

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

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

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

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

.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 - Сравнение сред разработки методом вариантных сетей

Характеристика средства разработкиВесОценка средств разработкиJava EclipseBorland Delphi7Microsoft VC++ 6Минимальная стоимость IDE71055Невысокая потребность ресурсов6788Наглядность разработки интерфейса5596Скорость работы разработанного программного обеспечения8789Обработка исключительных ситуаций8988Минимальное время создания разработанного программного обеспечения8595Удобство эксплуатации7886Наличие удобной справочной системы5689Итого391424376

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

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

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

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

Tree = class child0: Tree; // левый потомок child1: Tree; // правый потомокleaf:boolean; // признак листаcharacter:integer; // входной символweight: integer; // частота вхождений символаconstructor Create;overload;// создание пустого дереваconstructor Create( character:integer; weight:integer; leaf:boolean);overload; // создание дерева с определенными параметрамиprocedure traverse( code:String ; h:Huffman); // обход дерева, //формирование таблицы кодировок символов;

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

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

begin(Gf, chr(character),' ',weight ,' ', code); //сохраняем в файл.code[character] := code; // запоминаем код листа;( child0 <> nil) then child0.traverse(code + '0', h); //обход по левой //ветви( child1 <> nil) then child1.traverse(code + '1', h);//обход по правой //ветви

end;

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

Huffman = class

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

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

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

end;

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

-процедура построения дерева Huffman.growTree( data:array of integer );i,used,c,w,min,weight0:integer ;:Tree;i:=0 to length(data)-1 do[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;;(used > 1)do // просмотр всех деревьев в массиве:= getLowestTree( used ); //поиск дерева с мин.частотой 0 := Gtree[min].weight;

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

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

used:=used-1;[min] := Gtree[used];:= getLowestTree( used );.child1 := Gtree[min];.weight := weight0 + Gtree[min].weight;

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

end; ;

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

var str:string; :integer;:= '';i:=0 to length(data)-1 do // просмотр всех символов посл-ти data :=str+ code[data[i]]; // извлечение кода из полученной таблицы

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

result:=str;;

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

var str:string;:integer;

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;:=str;;

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

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

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

function GolombCodingOne(n:integer):string;

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

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

var q,r,b,cutoff,i:integer;: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<cutoff) then // диапазон 0 ? r < c

begin

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

for i:=1 to (b-1)-length(bin) do:=result+'0';:=result+bin; // наращивание строки-кода// диапазон r ? c:=GetBinary(r+cutoff); //получаем бинарный код числа r+с в виде

//строкиi:=1 to (b)-length(bin) do:=result+'0';:=result+bin; // наращивание строки-кода;;

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

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

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

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

s_temp:string;:textfile;:char;(f,name); //привязка логического файла к физическому(f); // открытие файла для чтения

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

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

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

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

s_temp:=''; result:='';(f,c);not(eof(f)) do //идем до конца файла:=0; c<>'0' do //считываем унарный код

begin(f,c);:=kol+1;; //q

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

s_temp:='';i:=1 to b-1 do //считывание b-1битов кода(f,c);_temp:=s_temp+c;;

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

read(f,c);_temp:=s_temp+c//считывание b битов кода2:=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]:=result+Code_table[q*M+b2-cutoff];(f,c);;;

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

.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_arr[i]:=Fib_arr[i-1]+Fib_arr[i-2]; //число Фиб. = сумме предыдущих двух

//чисел Фиб.

end;

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

function FibCodingOne(one:integer):string;

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

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

var i,kol:integer;_temp:integer;:boolean;_temp:=one;:=0;

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

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

last:=true;

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

for i:=1 to FIB_MAX-1 do //ищем большее число Фиб.(one_temp>=Fib_arr[i])and(one_temp<Fib_arr[i+1])then //нашли его на месте i

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

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

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

last:=false;

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

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

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

if (result[i]<>'1') then[i]:='0';;

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

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];// складываем число из чисел Фибоначчи:=kol;;

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

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

function ElGammaCodingOne(one:integer):string;

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

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

var kol,temp,i:integer;:string;:=one;:=0;

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

begin

temp:=temp div 2;

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

end;

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

result:='';i:=1 to kol do:=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+'0';one>1 then

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

//остатка q;

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

function ElGammaDecoding(name:string):string;

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

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

begin

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

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

s_temp:='';:='';not(eof(f)) do //идем до конца файла:=0;

read(f,c);

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

begin

read(f,c);

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

end;_temp:='';i:=1 to kol do //количество «0» унарного кода = кол-ву битов после «1» (f,c);_temp:=s_temp+c; //формируем бинарную строку числа q из схемы

//решения

end;

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

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

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

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

function ElDeltaCodingOne(one:integer):string;

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

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

var kol,temp,i:integer;:string;

begin

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

begin:='1';;;:=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+'0';one>1 then

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

//остатка q;

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

function ElDeltaDecoding(name:string):string;

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

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

var kol,i,pow:integer;_temp:string;:textfile;:char;

begin

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

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

s_temp:='';:='';not(eof(f)) do //идем до конца файла:=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(f,c);_temp:=s_temp+c; ;:= BinToInt(s_temp)+strtoint(floattostr(power(2,kol))); //нашли

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

s_temp:='';

for i:=1 to pow-1 do(f,c);

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

//решения;:=result+ Chr(BinToInt(s_temp)+strtoint(floattostr(power(2,pow-1))));

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

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

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

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

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

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

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

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

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

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

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

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

амортизация

прочие операционные расходы

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

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

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

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

(4.1)

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

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

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

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

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

МатериалыКоличество, шт.Стоимость единицы в гривнахСумма, грнНазначениеКомпакт-диски41,004,00Хранение программы и программного обеспеченияБумага(в пачках по 500 л)125,0025,00Документирование, реклама

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

МатериалыКоличество, шт.Стоимость единицы в гривняхСумма, грнНазначениеКартридж для принтера140,0040,00Печать рекламы и документации.Всего63,00

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

Расчет затрат на основную заработную плату по теме приведенной в табл. 4.2:

Таблица 4.2 - Расчет затрат на основную заработную плату

ДолжностьОклад, грн./мес.Количество месяцевДолевое участие, %Сумма, грн.Руководитель темы1900,003201140,00Инженер1100,0031003300,00Итого за 3 месяца 4440,00

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

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

грн

.2.4 В состав элемента Отчисления на социальные мероприятия включаются:

отчисления на обязательное государственное пенсионное страхование - 32% от;

отчисления на обязательное социальное страхование - 2,5% от ;

отчисления на общеобязательное государственное социальное страхование на фонд занятости - 2,5% от ;

- отчисления на индивидуальное страхование персонала предприятия - 1% от .

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

Амортизационные отчисления составляют 25 % от стоимости специального оборудования, и рассчитывается по формуле (4.2):

(4.2)

где - цена специального оборудования;

- кол-во месяцев работы.

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

Таблица 4.3 -Стоимость специального оборудования

Оборудованиекол-во месяцев работыСумма, грнПримечаниеЭВМ33300,00Разработка и тестирование программыПринтер1650,00распечаткаИтого3950,00

;

.2.6 Затраты на машинное время рассчитываются по формуле (4.3):

(4.3)

где - кол-во дней в месяце;

- число часов работы на ПК;

- стоимость Машино-час, грн.

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

Вспомогательные расходы по управлению предприятием, амортизационные отчисления по действующим нормам, затраты на охрану труда, отопление, освещение, услуги сторонних организаций. Накладные расходы рассчитываются как 25% - 30 % .

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

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

Наименование статей калькуляции Сумма, грн.1. Сырье и материалы 69,002. Основная заработная плата4440,003. Дополнительная заработная плата 444,00 4. Отчисления на социальные мероприятия: - отчисления на обязательное государственное пенсионное страхование - отчисления на обязательное социальное страхование - отчисления на общеобязательное государственное социальное страхование на фонд занятости - отчисления на индивидуальное страхование персонала предприятия1855,82 1562,88 122,10 122,10 48,845. Амортизационные отчисления 219,796. Затраты на машинное время 480,007. Накладные расходы1110,00 8. Сметная стоимость8618,719. Прибыль (35%)3016,5510. Оптовая цена11635,2611. Сумма НДС 12. Цена продажи 2327,05 13962,30

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

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

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

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

В действующих методологических положениях о порядке образования, распределение и использование фондов экономического стимулирования технического прогресса рекомендуется относить на организации, выполняющие научно-исследовательские и опытно-конструктивные работы, от 30% до 50% экономического эффекта; на технологические работы от 20% до 30%; на освоение и организацию производства новой техники от 25% до 40% экономического эффекта.

Экономическую эффективность некоторых поисковых и прикладных научно-исследовательских работ рассчитать не удается. В таком случае приводят качественное описание социально-экономической эффективности научно-исследовательской работы.

Сущность этой методики состоит в том, что на основе оценок работы определяется коэффициент научно-технического эффекта НИОКР (4.4):

(4.4)

где ri - весовой коэффициент і-го признака научно-технического эффекта (таблица 5.8);

ki - количественная оценка і-го признака научно-технического эффекта научно-исследовательской работы.

Значения весовых коэффициентов НИОКР сведем в таблицу 1.5:

Таблица 1.5 - Коэффициент весомости признаков

Признак научно-технического эффекта НИОКРЗначение весового коэффициентаУровень новизны Теоретический уровень Возможность реализации0,6 0,6 0,4

Классификатор признаков научной новизны принимается равным k1=7, так как уровень новизны разработки определяется как новая.

В таблице 1.6 представлено описание уровня новизны разработки - новая.

Таблица 1.6- классификатор признаков научной новизны

Уровень новизны разработкиХарактеристика новизныБаллыНоваяПо-новому или впервые объяснены известные факты, закономерности, введены новые понятия, проведено существенное усовершенствование, дополнение и уточнение ранее достигнутых результатов., закономерности, введены в их работы:5-7

Классификатор признаков теоретического уровня принимается равным k2=6, так как производится разработка нового способа.

В таблице 1.7 представлено описание признаков теоретического уровня при котором k=6:

Таблица 1.7 - классификатор признаков теоретического уровня

Теоретический уровень полученных результатовБаллыРазработка способа (алгоритм, программа мероприятий, устройство, вещество) 6

Классификатор признаков времени реализации принимается равным:

k3=k31+k32;

k31=4, так как время реализации в течение первых 4 лет;

k32=4, так как масштабы реализации в пределах нескольких предприятий.

В таблице 1.8 представим описание признаков времени и масштабов реализации для наших данных:

Таблица 1.8 - Классификатор признаков времени и масштабов реализации

Время реализацииБаллыОт 5 до 10 лет4Масштабы реализацииБаллыОтрасль, министерство4

Отсюда коэффициент научно-технического эффекта будет равен:

Нт = 0,6?7+0,6?6+0,4?(4+4)=11

Так как максимально возможное значение коэффициента научно-технического эффекта НИОКР Нт=12, то

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

.4 Выводы

В результате проведенных расчетов была составлена калькуляция себестоимости программирования методов арифметического кодирования, которые по сути являются архиваторами. Сметная стоимость разрабатываемого продукта-8618,71грн. Поскольку предполагаемая область применения достаточно широкая, то цена может быть снижена за счет увеличения количества продаваемых копий исходной программной продукции. Прибыль составляет 3016,55 грн., а цена продажи - 1 3962,30.Стоимость специального оборудования - 3950,00.

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

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

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

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

В ходе работы была разработаны программы вычисления различных кодов, с помощью которых возможно оптимизировать арифметическое кодирование информации. Эти программы написаны на языке программирования DALPHI. Разработка программ велась на компьютере AMD Athlon Dual Core Processor 3600+. Все разработки проводилась в НТУ ХПИ, в компьютерной лаборатории электротехнического корпуса. Компьютерная лаборатория находится на первом этаже трёхэтажного здания. Размер помещения 10x4=40 м2. Для работы одного человека в компьютерной лаборатории необходимо:

;

;

В данной лаборатории находится 6 рабочих мест, что соответствует санитарным нормам проектирования промышленных предприятий [13,32].

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

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

Вредные факторы при определённой интенсивности воздействий могут быть опасными.

В таблице 5.1 приведен перечень вредных и опасных факторов, воздействующих на человека при работе с электронно-вычислительной техникой согласно ГОСТ 12.0.003-74 [20].

Таблица 5.1 - Опасные и вредные факторы

Наименование фактораИсточник фактораНормированное значениеХарактер воздействияЛитератураПовышенное напряжениеСеть 220 В, электроприборыI = 0,6 мA U=12 BПоражение электрическим током и ожоги[30,28,32]Шум и вибрацииПечатающая техника вентиляторы системного блока и процессора50 дБАУтомление организма, снижение слуха, утомление ЦНС [26]Повышенный уровень статического электричестваНезаземлённые мониторы или части корпуса 15 кВ/мПоражение током[29,28]Повышенная яркость светаМощные осветительные приборыВ = 100 кд/мОтрицательное воздействие на зрительные органы[21,28,25]Пониженная контрастностьНеисправность мониторовК=0.9 %Переутомление и физическое перенапряжение[28,25]Повышенный уровень рентгеновского излученияЭкраны и другие поверхности ЭВМ100 мкР/ч на расстоянии 5 см от экранаМутагенные процессы во внутренних органах[27]Перенапряжение глазных анализаторовМонитор ЭВМУдлинение времени реакции на свет на 40-50%Головная боль, боль в глазах[21,28]Статическая перегрузкаПостоянная поза сиденияСнижение статической выносливости на 10%Мышечная усталость[21]

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

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

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

Длительное воздействие на человека неблагоприятных условий резко ухудшает его самочувствие, снижает производительность труда, и частично приводит к заболеваниям. ГОСТ 12.1.005-88 [22] устанавливает в лабораториях оптимальные метеоусловия, учитывая время года и тяжесть выполняемых работ.

Важной составляющей трудового процесса пользователя ПК является значительная информационная нагрузка, поэтому категория выполняемой работы относится к легкой физической Iа (работа производимая сидя не требующая систематического физического напряжения, энэргозатраты до 120 Ккал/ч.), но умственно напряженной согласно ГОСТ 12.1.005-88.

По характеру окружающей среды помещение лаборатории относится к классу нормальных, так как в нем отсутствуют признаки свойственные помещениям, жарким, пыльным, с химически активной средой, так работа с ПК требует большой концентрации внимания, то микроклимат помещения должен характеризоваться оптимальными значениями параметров. Учитывая специфику работы за компьютером, оптимальные климатические параметры приведены в таблице 5.2 согласно ГОСТ 12-1.005-88 .

Таблица 5.2 - Микроклимат в рабочей зоне

Категория работПериод годаТемпература, Относительная влажность, %Скорость движения воздуха, м/сЛегкая физическая Iа, напряженная умственнаяХолодный20...2340...600.1Тёплый23...2540...600.1

Для обеспечения вышеуказанных оптимальных метеорологических условий и защиты от пыли, в помещении предусмотрено согласно СНиП 2.04.05-92 [24].:

-система отопления общая паровая,

-кондиционирование - кондиционеры типа БК-2000;

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

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

Для обеспечения комфорта зрительных работ в помещениях с ПК применяется естественное и искусственное освещение, а также комбинированное, учитывая напряженность глазного анализатора, согласно ДБН В.2.5.-28-2006 [25] и СНиП II-4-79 [33].

Естественное освещение нормируется коэффициентом естественного освещения (КЕО) согласно ДБН В.2.5.-28-2006.

Нормированные значения КЕО (ен) для зданий расположенных в IV поясе светового климата (Украина) определяются по формуле (5.1)

(5.1)

где - значение КЕО для зданий, которые расположены в третьем поясе светового климата Украины, с учетом характеристик зрительной работы = 1,5%;

m - коэффициент светового климата (для IV светового пояса m=0.9);

с - коэффициент солнечности климата, учитывает дополнительный световой поток, проникающий через световые проемы в помещение за счет прямого и отраженного от подстилающей поверхности солнечного света в течение года (определяется исходя из ориентации окон по сторонам света, для окон выходящих на юго-восток и IV-го пояса светового климата c=1).

Характеристики зрительной работы пользователя ПЭВМ следующие:

-разряд зрительных работ III - высокой точности;

-подразряд в;

наименьший размер объекта различения от 0,3 до 0,5 мм;

Контраст объекта различения с фоном средний или большой;

Характеристика фона светлый и средний.

В тёмное время суток используется искусственное освещение. Согласно

ДБН В.2.5.-28-2006 освещенность комбинированная 750 лк, общая 300 лк.

Общее освещение выполнено в виде прерывистой линии светильников. Учитывая возможности и требования к экономии электроэнергии, выберем для общего освещения компьютерного класса электролюминесцентные светильники ЛДЦ-40, световой поток 750 Лм. Выбранный светильник прямого света характеризуется диффузным отражением, защитным устройством, предохраняющим от ослепления и отражённого блеска, и оснащённого защитным устройством для регулирования яркости. Кроме того, они имеют больший срок службы - 10000 ч. Степень защиты соответствующая классу помещения П-IIа для светильников IP2X.

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

ЭЛТ генерирует несколько типов излучения: рентгеновское, радиочастотное, ультрафиолетовое и инфракрасное.

Уровни этих излучений низкие и не превышают допустимых норм. Конструктивное решение экрана дисплея таково, что рентгеновское излучение от экрана на расстоянии 5 см не превышает 100 мкР/ч., что отвечает эквивалентной дозе 0.1 мбер/год ( НРБУ-97 [27] ).

Следует учитывать, что мягкое рентгеновское излучение, возникающее при напряжениях на аноде 20-22 кВ, а также напряжение на токоведущих участках схемы вызывают ионизацию воздуха с образованием положительных ионов, неблагоприятных для человека. Уровни ионизации воздуха помещения для работы на ПЭВМ приведены в таблице 3 согласно ДНАОП 0.03-3.06-80 [23].

В таблице 5.3 приведены нормы допустимых уровней ионизации воздуха:

Таблица 5.3 - Нормы допустимых уровней ионизации воздуха

Уровень ионизацииКоличество ионов в 1 см³ воздухаnnМинимально необходимый400600Оптимальный1500-30003000-5000Максимально допустимый5000050000

Поддержание допустимых уровней ионизации воздуха обеспечивается кондиционерами типа БК-2000 согласно СНиП 2.04.05-91.

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

В компьютерной лаборатории наиболее сильными источниками шума и вибрации являются печатающая техника, а также вентиляторы процессора и блока питания. Уровень их звукового давления в рабочих местах не превышает 50 дБа, что соответствует нормам ГОСТ 12.1.003.-83* [26],и вибрация в помещениях незначительная, так как незначительны источники вибрации ГОСТ 12.1.012.-90. Так как для источников шума и вибрации предусмотрены конструктивные меры защиты (исполнение шумовиброустойчивом варианте), то дополнительные средства защиты от шума и вибрации не используются.

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

Все оборудование используемое при работе, является потребителем однофазной сети переменного тока с частотой 50 Гц, напряжением 220/380 В, мощность, потребляемая от сети переменного тока, не превышает 1 КВт, и оборудована глухозаземленной нейтралью от поражения электрическим током обслуживающего персонала согласно ГОСТ 12.1.038-82* [30].Этим обеспечивается невозможность появления напряжения относительно земли больше 220В. Электропитание осуществляется от электроустановки (трансформатора), с регулируемым напряжением под нагрузкой. Напряжение от сети подаётся в распределительные шкафы. Лаборатория, где находится много энергоёмкого оборудования, относится к классу помещений с повышенной опасностью поражения человека электрическим током ГОСТ 12.2.007.0-75* [31]. Для обеспечения электробезопасности, предусмотрены конструктивные, схемно-конструктивные и эксплуатационные меры электробезопасности.

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

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

Классификация:

Здание, где находится компьютерный класс, по пожарной безопасности относится к категории В - пожароопасное, в нём находятся твёрдые сгораемые материалы и вещества, НАПБ Б 07.005-86 [15], степень огнестойкости здания относится к III-й степени (конструкции выполнены из естественных и искусственных каменных материалов, бетона или железобетона с применением листовых и плиточных негорючих материалов) в соответствии со ДБН В.1.1-7-2002 [18]. Класс помещения согласно ПУЭ-87 [17] по пожарной опасности П-Iiа, так как в нем находятся твердые горючие вещества, не способные переходить во взвешенное состояние.

Пожарная безопасность в соответствии с ГОСТ 12.1.004-91 [16] обеспечивается системами предотвращения пожара, пожарной защиты, организационно-техническими мероприятиями.

Система предотвращения пожара включает:

контроль и профилактику изоляции;

наличие плавких вставок и предохранителей в оборудовании;

для защиты от статического напряжения используется защитное заземление;

Для данного класса здания с учётом количества грозовых часов в году (г. Харьков) устанавливается 3 категория молниезащиты.

Степень защиты, соответствующая классу помещения П IIа:

Для оборудования IP 44.

Для светильников IP 2Х.

Система пожарной защиты:

Предусматривается наличие углекислотных огнетушителей ОУ-2 в количестве 4 штук (1 шт. на 10 кв.м), в связи с использованием в помещении электроустановок, а также система автоматической пожарной сигнализации, которая оснащена дымовыми сигнализаторами.

Организационные меры защиты:

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

Для успешной эвакуации персонала двери помещения имеют следующие размеры:

Ширина не менее 1.5 м

Высота не менее 2.0 м

Ширина коридора 1.8 м. Рабочее помещение должно иметь два выхода. Расстояние от наиболее удаленного рабочего места не должно превышать 100 м. В здании имеются два эвакуационных выхода.

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

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

Заключение

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

В данной работе разрабатывались программно-аппаратные средства оптимального арифметического кодирования. Рассмотрены методы оптимального кодирования, которые являются трансформирующими и поточными, то есть могут применяться даже в том случае, когда объем входных данных заранее не известен. В общем случае скорость работы компрессора (содержащего прямое, «сжимающее» преобразование) равна скорости декомпрессора (реализующего обратное, «разжимающее» преобразование) и зависит только от объема исходных данных. При этом нет необходимости в больших объемах буферной памяти. К таким методам относятся: гамма-коды Элиаса, коды Хаффмана, коды Голомба, Фибоначчи и т.д. Эти коды были запрограммированы на кодирование и декодирование на языке программирования DELPHI.

Анализ показывает, что для значений ошибки (e<0.05) и коэффициента сжатия (3..4) целесообразно кодировать сигналы ЭКГ кодами Левенштейна и Фибоначчи. Близки к ним по эффективности коды Голомба с параметром m=3. Оптимальное число отброшенных коэффициентов составляет порядка 25% от длины блока. Длину блока нецелесообразно выбирать как слишком малую (8..16), так и слишком большую (128). Оптимальной длиной блока представляется значение 32..64.

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

арифметическое кодирование алгоритм

СПИСОК ИСТОЧНИКОВ ИНФОРМАЦИИ

1.Ватолин Д., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных. <#"justify">12.Закон України «Про охорону праці»,листопад 2002 р.

13.Санитарные нормы проектирования промышленных предприятий. СН 245-Н-М.:Стройиздат,1972.-96с.

.Долин П.А. «Справочник по технике безопасности». -Энергоатомиздат, 1984-824с.

.НАПБ Б 07.005-86. Определение категорий помещений и зданий по взрывопожарной и пожарной опасности. -Действует с 01.01.87.

.ГОСТ 12.1.004-91 ССБТ. Пожарная безопасность. Общие требования.-Введ.01.07.92.

.ДНАОП 0.01-1.01-95 «Правила пожежної безпеки в Україні.-Дії з 22.06.95

.ДБН В.1.1-7-2002 «Пожежна безпека обєктів будівництва.-Діє з 01.01.03

19.«Правила устройства электроустановок».Энергоатомиздат,1987.

.ГОСТ 12.0.003-74 ССВБТ. Опасные и вредные производственные факторы. Классификация.-Введ.01.01.76

.Жидецький В.Ц. «Охорона праці користувачів компютерів».-Львів:Афіша,2000.-176 с.

.ГОСТ 12.1.005-88 ССБТ. Общие санитарно-гигиенические требования к воздуху рабочей зоны.-Введ.01.01.89.

.ДНАОП 0.03-3.06-80. Санітарно-гігієнічні норми допустимих рівнів іонізації повітря виробничих та громадських приміщєнь. - Діє з 01.01.81.

.СНиП 2.04.05-92 Нормы проектирования. Отопление, вентиляция и кондиционирование воздуха. - М.:Стройиздат,1992г.

.ДБН В.2.5-28-2006.Інженерне обладнання будівель та споруд. Природне і штучне освітлення. - К.:Мінбуд Укр.,2006.

.ГОСТ 12.1.003-83*.ССБТ. Шум. Общие требования безопасности.-Введ.01.07.1989.

.НРБУ-97. Норми радіаційної безпеки України.-Київ,1997.

.ДСан ПіН 3.3.2-0.07-98.Державні санітарні правила і норми роботи з візуальними дісплеями і терміналами електронно-обчислювальних машин.-Київ,1998.

.ГОСТ 12.1.045-84.ССБТ.Электростатические поля. Допустимые уровни на рабочих местах и требования к проведению контроля. -Введен 01.01.86

.ГОСТ 12.1.038-82.ССБТ.Электробезопасность. Предельно допустимые значения напряжения прикосновения и токов. -Введен 01.01.88.

ГОСТ 12.2.007.0-75*. Изделия электротехнические. Общие требования безопасности. -Введен 01.01.76

31.НПАОП 0.00-1.31-99. Правила охорони праці при експлуатації електронно-обчислювальних машин.-Діє з 01.01.00.

32.СНиП 11-4-79/80. Естественное и искусственное освещение. Нормы проектирования.- М.: Стройиздат,1980-110с.

ПРИЛОЖЕНИЕ А

Листинг программы кодирования-декодирования

unit Coding;

, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,, StdCtrls, Math, Golomb;

_TABLE_MAX = 39;_MAX = 13;_MAX_LENGTH = 377;_M_INFO = 'Golomb param M is ';= 256;_str_NotSuchMeth = 'Can''t choose coding method';_str_WrongSymbols = 'Wrong symbol!! Input integer number or small latin letter';

= class

:array[0..ALPHABETSIZE] of integer;code:array[0..ALPHABETSIZE]of string;

function getLowestTree( used: integer):integer;procedure growTree (data:array of integer);procedure makeCode;

function coder(data:array of integer):string;

function decoder(data:String):string;

;

= classchild0: Tree;child1: Tree;leaf:boolean;character:integer;weight: integer;

constructor Create;overload;constructor Create( character:integer; weight:integer; leaf:boolean);overload;procedure traverse( code:String ; h:Huffman);;

= class(TForm): TGroupBox;: TComboBox;: TLabel;: TEdit;: TLabel;: TMemo;: TLabel;: TButton;: TButton;: TEdit;: TLabel;: TButton;: TLabel;: TLabel;FormCreate(Sender: TObject);ComboBox1Select(Sender: TObject);Edit1KeyPress(Sender: TObject; var Key: Char);Button1Click(Sender: TObject);Button2Click(Sender: TObject);Button3Click(Sender: TObject);

{ Private declarations }

{ Public declarations };

: TForm1;

/////Our code table///_table: array[0..CODING_TABLE_MAX]of char;// 0..9 - '0'..'9'

// 10..36 - 'a'..'z'

// 37 - ' '

// 38 - #13

// 39 - #10

_arr:array [1..FIB_MAX]of integer; // array with Fib numbers_M: integer;_meth: 0..5; // 0 - Fibonacci

// 1 - Haffman

// 2 - Unaring: array[0..ALPHABETSIZE] of Tree;: textfile;: Huffman;

StrUtils;

{$R *.dfm}

/////////////////////////////////////////////////////////////////////////////

//////////////////////////Coding procedures /////////////////////////////////

GenerateCode_table;i:integer;i:=0 to 9 do_table[i]:=chr(48+i);i:=10 to 36 do_table[i]:=chr(87+i);_table[37]:=' ';_table[38]:=#13;_table[39]:=#10;;

CT_ord(c:char):integer;i:integer;:=0;i:=0 to CODING_TABLE_MAX do(c=Code_table[i]) then begin:=i;;;;

//////////////////////////////Fibonacci//////////////////////////////////////GenerateFib(n:integer);i:integer;_arr[1]:=1;_arr[2]:=2;i:=3 to n do_arr[i]:=Fib_arr[i-1]+Fib_arr[i-2];;

FibCodingOne(one:integer):string;i,kol:integer;_temp:integer;:boolean;_temp:=one;:=0;:='';i:=1 to FIB_MAX_LENGTH do:=result+'$';:=true;

//search closest Fib number(one_temp>0) doi:=1 to FIB_MAX-1 do(one_temp>=Fib_arr[i])and(one_temp<Fib_arr[i+1])then[i]:='1';_temp:=one_temp-Fib_arr[i];(last) then begin[i+1]:='1';:=false;:=i+1;;;;

(result,kol+1,length(result)-kol);i:=1 to length(result) do(result[i]<>'1') then[i]:='0';;

FibCoding(s_str:string);i:integer;:textfile;(FIB_MAX);(f,'FibCoding.txt');(f);i:=1 to length(s_str) dos_str[i]<>'0' then(f,FibCodingOne(CT_ord(s_str[i])));(f);;

FibOneDecoding(s_tmp:string):integer;i,kol:integer;:=0;i:=1 to length(s_tmp)-1 do(s_tmp[i]='1') then:=kol+ Fib_arr[i];:=kol;;

FibDecoding(name:string):string;_temp:string;:textfile;:char;(f,name);(f);_temp:='';not(eof(f)) do(f,c);_temp:=s_temp+c;(length(s_temp)>1) and (s_temp[length(s_temp)]='1') and (s_temp[length(s_temp)-1]='1') then:=result+Code_table[FibOneDecoding(s_temp)];_temp:='';;;(f);;

/////////////////////////////////Elias Gamma/////////////////////////////////

GetBinary(numb:integer):string;t,k:integer;:=numb;:='';(t>1) do:=t mod 2;:=result+inttostr(k);:=t div 2;;:=result+inttostr(t);:=ReverseString(result);;

BinToInt(bin:string):integer;i:integer;_bin:string;:=0;_bin:=ReverseString(bin);i:=1 to length(t_bin) do(t_bin[i]='1')then:=result+strtoint(floattostr(power(2,i-1)));;

ElGammaCodingOne(one:integer):string;kol,temp,i:integer;:string;:=one;:=0;(temp>0)do:=temp div 2;:=kol+1;;:=kol-1;:='';i:=1 to kol do:=result+'0';

:=GetBinary(one mod strtoint(floattostr((power(2,kol)))));:=result+'1';i:=1 to kol-length(bin) do:=result+'0';one>1 then:=result+bin;;

ElGammaCoding(s_str:string);i:integer;:textfile;(f,'GammaElias.txt');(f);i:=1 to length(s_str) dos_str[i]<>'0' then(f,ElGammaCodingOne(CT_ord(s_str[i])));

(f);;

ElGammaDecoding(name:string):string;kol,i:integer;_temp:string;:textfile;:char;(f,name);(f);_temp:='';:='';not(eof(f)) do:=0;(f,c);c<>'1' do(f,c);:=kol+1;;_temp:='';i:=1 to kol do(f,c);_temp:=s_temp+c;;:=result+Code_table[BinToInt(s_temp)+strtoint(floattostr(power(2,kol)))];;(f);;

///////////////////////////////Elias delta///////////////////////////////////

ElDeltaCodingOne(one:integer):string;kol,temp,i:integer;:string;one=1 then:='1';;;:=one;:=0;(temp>0)do:=temp div 2;:=kol+1;;:=ElGammaCodingOne(kol);:=GetBinary(one mod strtoint(floattostr((power(2,kol-1)))));i:=1 to kol-length(bin)-1 do:=result+'0';one>1 then:=result+bin;

;

ElDeltaCoding(s_str:string);i:integer;:textfile;(f,'DeltaElias.txt');(f);i:=1 to length(s_str) dos_str[i]<>'0' then(f,ElDeltaCodingOne(CT_ord(s_str[i]))); (f);;

ElDeltaDecoding(name:string):string;kol,i,pow:integer;_temp:string;:textfile;:char;(f,name);(f);_temp:='';:='';not(eof(f)) do:=0;(f,c);c<>'1' do(f,c);:=kol+1;;_temp:='';i:=1 to kol do(f,c);_temp:=s_temp+c;;:= BinToInt(s_temp)+strtoint(floattostr(power(2,kol)));_temp:='';i:=1 to pow-1 do(f,c);_temp:=s_temp+c;;:=result+ Code_table[BinToInt(s_temp)+strtoint(floattostr(power(2,pow-1)))];;(f);;

///////////////////////////////////Golomb////////////////////////////////////UnaringCode(n:integer):string;i:integer;:='';i:=1 to n do:=result+'1';:=result+'0';;

GolombCodingOne(n:integer):string;q,r,b,cutoff,i:integer;:string;:= n div Golomb_M;:= n mod Golomb_M;:=UnaringCode(q);:= ceil(math.Log2(Golomb_M));:=round(power(2,b))-Golomb_M;(r<cutoff) then:=GetBinary(r);i:=1 to (b-1)-length(bin) do:=result+'0';:=result+bin;:=GetBinary(r+cutoff);i:=1 to (b)-length(bin) do:=result+'0';:=result+bin;;

// Showmessage(result);

//skolko volka ne kormi vse ravno v les smotrit431;

GolombCoding(s_str:string);i:integer;:textfile;(f,'Golomb.txt');(f);(f, GLOMB_M_INFO);(f, Golomb_M);i:=1 to length(s_str) dos_str[i]<>'0' then(f,GolombCodingOne(CT_ord(s_str[i])));(f);;

GolombDecoding(name:string):string;kol,i,M,q,b,b1,b2,cutoff:integer;_temp:string;:textfile;:char;(f,name);(f);(f);(f,M);:=ceil(math.Log2(M));:=round(power(2,b))-M;_temp:='';:='';(f,c);not(eof(f)) do:=0; c<>'0' do(f,c);:=kol+1;; //q:=kol;_temp:='';i:=1 to b-1 do(f,c);_temp:=s_temp+c;;:=BinToInt(s_temp);(f,c);_temp:=s_temp+c;:=BinToInt(s_temp);(b2<=cutoff)or(b2-cutoff>=M)or(b2-cutoff<=cutoff-1) then:=result+Code_table[q*M+b1];:=result+Code_table[q*M+b2-cutoff];(f,c);;;(f);;

/////////////////////////////Haffman/////////////////////////////////////////Tree.Create;;

Tree.Create( character:integer; weight:integer; leaf:boolean);.leaf := leaf;.character := character;.weight := weight;;

Tree.traverse(code:String; h:Huffman);(leaf) then(Gf, chr(character),' ',weight ,' ', code);.code[character] := code;;( child0 <> nil) then child0.traverse(code + '0', h);( child1 <> nil) then child1.traverse(code + '1', h);;

Huffman.getLowestTree( used: integer):integer;min,i:integer;:=0;i:=1 to used-1 do(Gtree[i].weight < Gtree[min].weight )then min := i;:= min;;

Huffman.growTree( data:array of integer );i,used,c,w,min,weight0:integer ;:Tree;i:=0 to length(data)-1 do[data[i]]:= weights[data[i]]+1;:= 0;c:=0 to ALPHABETSIZE-1 do:= weights[c];(w <> 0)then begin[used] := Tree.Create(c, w, true);:=used+1;;;(used > 1)do:= getLowestTree( used );:= Gtree[min].weight;:= Tree.Create;.child0 := Gtree[min];:=used-1;[min] := Gtree[used];:= getLowestTree( used );.child1 := Gtree[min];.weight := weight0 + Gtree[min].weight;[min] := temp;; ;

Huffman.makeCode;[0].traverse('', self);;

Huffman.coder( data:array of integer ):string;str:string;:integer;:= '';i:=0 to length(data)-1 do:=str+ code[data[i]];:=str;;

Huffman.decoder(data:String):string;str:string;:integer;:='';(length(data) > 0)doc:=0 to ALPHABETSIZE-1 do(weights[c]>0)then(weights[c]>0) and (Pos(code[c],data)=1) then:= copy(data,Length(code[c])+1,length(data));:= str+chr(c);;;;:=str;;

HuffmanCoding(s_str:string);i:integer;:textfile;:array of integer;:string;(f,'Huffman.txt');(f);:= Huffman.Create;(data,length(s_str));i:=0 to length(data)-1 do[i]:= ord(s_str[i+1]);.growTree(data);.makeCode;:= Gh.coder(data);(f, str); (Gf);(f);;

HuffmanDecoding(f_name:string):string;f: textfile;_temp:string;:char;(f,f_name);(f);_temp:='';not eof(f) do(f,c);_temp:=s_temp+c;;:= Gh.decoder(s_temp);(f);;

/////////////////////////////////////////////////////////////////////////////

DoCoding(code_id: integer);

code_id of

: begin(Form1.Edit1.Text);.Memo1.Lines.LoadFromFile('FibCoding.txt');

// Showmessage('Size of code '+inttostr(length(Form1.Memo1.Lines.GetText)));;

: // Elias Gamma(Form1.Edit1.Text);.Memo1.Lines.LoadFromFile('GammaElias.txt');;

: // Ellias delta(Form1.Edit1.Text);.Memo1.Lines.LoadFromFile('DeltaElias.txt');;

: // Golomb.Form2.ShowModal;_M:=Golomb.Form2.SpinEdit1.Value;(Form1.Edit1.Text);.Memo1.Lines.LoadFromFile('Golomb.txt');;

: // Huffman(Form1.Edit1.Text);.Memo1.Lines.LoadFromFile('Huffman.txt');;

: ;(Err_str_NotSuchMeth);;.Label6.Caption:=inttostr(length(Form1.Memo1.Lines.GetText));;

DoDecoding(code_id: integer);code_id of

: begin.Edit2.Text:=FibDecoding('FibCoding.txt');;

: begin.Edit2.Text:= ElGammaDecoding('GammaElias.txt');;

: begin.Edit2.Text:=ElDeltaDecoding('DeltaElias.txt');;

: begin.Edit2.Text:=GolombDecoding('Golomb.txt');;

: begin.Edit2.Text:=HuffmanDecoding('Huffman.txt');;

: ;(Err_str_NotSuchMeth);;;

TForm1.FormCreate(Sender: TObject);_meth:=0;_table;(Gf,'HuffmanTemp.txt');(Gf);;TForm1.ComboBox1Select(Sender: TObject);_meth:=ComboBox1.ItemIndex;

//ShowMessage(inttostr(Coding_meth));;TForm1.Edit1KeyPress(Sender: TObject; var Key: Char);not((Key in ['0'..'9'])or (Key in ['a'..'z'])or (Key in [' ',#13,#10])) then(Err_str_WrongSymbols);:=#0;;

;TForm1.Button1Click(Sender: TObject);(Coding_meth);

;TForm1.Button2Click(Sender: TObject);(Coding_meth);;

TForm1.Button3Click(Sender: TObject);i:integer;

//Golomb_M:=8;

// for i:=1 to 10 do

// GolombCodingOne(42);(inttostr(CT_ord('v')));

end;

.

СОДЕРЖАНИЕ Перечень обозначений и сокращений Введение . Методы арифметического кодирования .1 Унарный код .2 Код Голомба .3 Код Райса

Больше работ по теме: