Файл: МЕТОДЫ КОДИРОВАНИЯ ИФОРМАЦИИ.pdf

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

Пусть A={a1,a2,...,an} – алфавит, содержащий n различных символов, W={w1,w2,...,wn} - соответствующий ему набор положительных целых весов. Тогда набор бинарных кодов C={c1,c2,...,cn}, имеет следующие свойства [8]:

- ci не является префиксом для cj, при i=j;минимальна (|ci| - длина кода ci)выступает в качестве минимально-избыточного префиксного кодаили иначе кода Хаффмана.

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

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

Пусть Т- бинарное дерево, А=(0,1)- двоичный алфавит для каждого ребра Т-дерева прописан один из символов алфавита таким образом, что все ребра, выходящие из одной вершины, отмечены различными буквами. Тогда для любого листа Т-дерева прописывается уникальный кодовый идентификатор, образованный из букв, которыми отмечены ребра, которые встречаются при движении от корня к соответствующему листу. Особенностью описанного метода кодирования является то, что полученные коды являются префиксными.

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

В классическом алгоритме Хаффмана на входе генерируется таблица частот повторяемости символов в сообщении. Далее на основании данной таблицы проводится построение дерева кодирования Хаффмана (Н-дерева).

1. Из символов входного алфавита образуется список свободных узлов. Каждому листу сопоставляется вес, который соответствует либо вероятности, либо числу вхождений данного символа в сжимаемое сообщение;

2. Проводится выбор двух свободных узлов дерева с минимальными весами.

Проводится создание их родителя с весом, соответствующим их суммарному весу;

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

Одной дуге, которая выходит из родительского узла, сопоставляется бит 1, другой - бит 0;

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

Допустим, имеется следующая таблица частот.

На первой итерации проводится выбор листьев, имеющих минимальные веса. (в данном случае Г и Д). Проводится их присоединение к новому узлу- родителю, которому устанавливается вес 4+5= 9. Далее проводится удаление узлов Г и Д из перечня свободных. Узлу Г сопоставляется ветвь 0 родителя, узлу Д- ветвь 1.

На следующем итерации то же производится с узлами Б и В, так как теперь данная пара обладает самым меньшим весом в дереве. Проводится создание нового узла с весом 11, удаление узлов Б и В из списка свободных.

Далее «наилегчайшими» парами выступают узлы Б/В и Г/Д.

Для них еще раз проводится создание родителя, теперь уже с весом 20. Узел Б/В соответствует нулевой ветви родителя, Г/Д - ветви 1.

На последней итерации в списке свободных находится только 2 узла - это узел А и узел Б (Б/В)/(Г/Д). Проводится создание родителя с весом 34, и бывшие свободные узлы присоединяются к различным его ветвям.

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

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

Для данной таблицы символов коды Хаффмана принимают следующий вид:

Наиболее часто используемый символ сообщения А закодирован минимальным числом бит, а наиболее редкий символ Д - максимальным. Величина стоимости хранения кодированного потока, определяемая через сумму длин взвешенных путей, рассчитывается выражением 14*1+6*3+5*3+5*3+4*3=74, что значительно ниже стоимости хранения входного потока (312).

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

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

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

2. Использование систем кодирования информации в технологиях информационной безопасности

2.1. Штриховое кодирование

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

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

К основным функциям штрихового кода относятся [2]:

• оперативная идентификация объекта и производителя;
• проведение торговых сделок в безбумажной форме: с помощью штрихового кода сокращаются издержки, связанные с делопроизводством с 15% до 0,5-0,3% от стоимости товара;
• автоматизация учета и  контроля товарных запасов;
• обеспечение оперативности управления процессами движения товаров: отгрузкой, транспортировкой и складированием (производительность труда по обеспечению товародвижения повышается на 30%, в некоторых случаях – на 80%);
• информационное обеспечение маркетинговых исследований [4, с. 146].

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

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

Ширина самого узкого элемента (штриха или пробела) принимается в качестве основного размера –модуля. Ширина любого элемента должна быть либо кратна модулю (например, в символике «Код 128» допустимы элементы шириной 1, 2, 3 или 4 модуля), либо должна выдерживаться постоянность отношения между широкими и узкими элементами (например, в символике «Код 39» элементы двух размеров – с заданным отношением ширины широких элементов к узким).

С помощью определенных комбинаций штрихов и пробелов можно образовать набор знаков штриховых кодов. Так, в символике «Код 39» для каждому знаку штрихового кода сопоставляется девять элементов (из которых три широких и шесть узких) и должен быть представлен в пяти и четырех пробелах. Каждой комбинацией штрихов и пробелов – знаку штрихового кода сопоставляется, как правило, знак данных или специальный символ.

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

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

Таким образом, основными областями использования технологий штрихового кодирования являются:

- идентификация товаров в технологии продаж;

- складской учет;

- инвентаризация;

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

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

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

Штрих-коды типа EAN / UPC. Данная технология штрихового кодирования предполагает генерацию уникального сочетания из 13 цифровых символов. Первые 7 символов кода соответствуют производителям (или фирмам, проводящим упаковку товаров). Для кодировки малогабаритных товаров используются аналогичные коды, включающие из 8 цифровых символов. Данные символики широко используются для маркировки потребительских товаров.

Штрих-коды типа Interleaved 2 of 5 (ITF). Для указанного типа штрихового кодирования характерна высокая плотность, при этом длина кода может быть различной. Символика данной системы находит широкое применение при перевозке или хранении товара на складах предприятий оптовой торговли, то есть в тех областях, где необходимо обеспечить уникальность маркировки упаковок с использованием многосимвольных идентификаторов. Так же данный тип штрихового кодирования используется для хранения на складах обувной продукции.

Первый и последний символы кода имеют наименование соответственно, «стартовых» и стоповых. Расположенные между ними символы, находящиеся на нечетных позициях (то есть, первые, третьи, пятые и т.д. символы) кодируются через последовательности, включающие два широких и три узких штриха. Символы, находящиеся на четных позициях (то есть, вторые,